190075Sobrien/* Basic block reordering routines for the GNU compiler. 2169689Skan Copyright (C) 2000, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. 390075Sobrien 490075Sobrien This file is part of GCC. 590075Sobrien 690075Sobrien GCC is free software; you can redistribute it and/or modify it 790075Sobrien under the terms of the GNU General Public License as published by 890075Sobrien the Free Software Foundation; either version 2, or (at your option) 990075Sobrien any later version. 1090075Sobrien 1190075Sobrien GCC is distributed in the hope that it will be useful, but WITHOUT 1290075Sobrien ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 1390075Sobrien or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public 1490075Sobrien License for more details. 1590075Sobrien 1690075Sobrien You should have received a copy of the GNU General Public License 1790075Sobrien along with GCC; see the file COPYING. If not, write to the Free 18169689Skan Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 19169689Skan 02110-1301, USA. */ 2090075Sobrien 21132718Skan/* This (greedy) algorithm constructs traces in several rounds. 22132718Skan The construction starts from "seeds". The seed for the first round 23132718Skan is the entry point of function. When there are more than one seed 24132718Skan that one is selected first that has the lowest key in the heap 25132718Skan (see function bb_to_key). Then the algorithm repeatedly adds the most 26132718Skan probable successor to the end of a trace. Finally it connects the traces. 2790075Sobrien 28132718Skan There are two parameters: Branch Threshold and Exec Threshold. 29132718Skan If the edge to a successor of the actual basic block is lower than 30132718Skan Branch Threshold or the frequency of the successor is lower than 31132718Skan Exec Threshold the successor will be the seed in one of the next rounds. 32132718Skan Each round has these parameters lower than the previous one. 33132718Skan The last round has to have these parameters set to zero 34132718Skan so that the remaining blocks are picked up. 3590075Sobrien 36132718Skan The algorithm selects the most probable successor from all unvisited 37132718Skan successors and successors that have been added to this trace. 38132718Skan The other successors (that has not been "sent" to the next round) will be 39132718Skan other seeds for this round and the secondary traces will start in them. 40132718Skan If the successor has not been visited in this trace it is added to the trace 41132718Skan (however, there is some heuristic for simple branches). 42132718Skan If the successor has been visited in this trace the loop has been found. 43132718Skan If the loop has many iterations the loop is rotated so that the 44132718Skan source block of the most probable edge going out from the loop 45132718Skan is the last block of the trace. 46132718Skan If the loop has few iterations and there is no edge from the last block of 47132718Skan the loop going out from loop the loop header is duplicated. 48132718Skan Finally, the construction of the trace is terminated. 4990075Sobrien 50132718Skan When connecting traces it first checks whether there is an edge from the 51132718Skan last block of one trace to the first block of another trace. 52132718Skan When there are still some unconnected traces it checks whether there exists 53132718Skan a basic block BB such that BB is a successor of the last bb of one trace 54132718Skan and BB is a predecessor of the first block of another trace. In this case, 55132718Skan BB is duplicated and the traces are connected through this duplicate. 56132718Skan The rest of traces are simply connected so there will be a jump to the 57132718Skan beginning of the rest of trace. 5890075Sobrien 5990075Sobrien 60132718Skan References: 6190075Sobrien 62132718Skan "Software Trace Cache" 63132718Skan A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999 64132718Skan http://citeseer.nj.nec.com/15361.html 6590075Sobrien 6690075Sobrien*/ 6790075Sobrien 6890075Sobrien#include "config.h" 6990075Sobrien#include "system.h" 70132718Skan#include "coretypes.h" 71132718Skan#include "tm.h" 7290075Sobrien#include "rtl.h" 73169689Skan#include "regs.h" 7490075Sobrien#include "flags.h" 75132718Skan#include "timevar.h" 7690075Sobrien#include "output.h" 7790075Sobrien#include "cfglayout.h" 78132718Skan#include "fibheap.h" 7996263Sobrien#include "target.h" 80169689Skan#include "function.h" 81169689Skan#include "tm_p.h" 82169689Skan#include "obstack.h" 83169689Skan#include "expr.h" 84169689Skan#include "params.h" 85169689Skan#include "toplev.h" 86169689Skan#include "tree-pass.h" 8790075Sobrien 88169689Skan#ifndef HAVE_conditional_execution 89169689Skan#define HAVE_conditional_execution 0 90169689Skan#endif 91132718Skan 92169689Skan/* The number of rounds. In most cases there will only be 4 rounds, but 93169689Skan when partitioning hot and cold basic blocks into separate sections of 94169689Skan the .o file there will be an extra round.*/ 95169689Skan#define N_ROUNDS 5 96169689Skan 97169689Skan/* Stubs in case we don't have a return insn. 98169689Skan We have to check at runtime too, not only compiletime. */ 99169689Skan 100169689Skan#ifndef HAVE_return 101169689Skan#define HAVE_return 0 102169689Skan#define gen_return() NULL_RTX 103169689Skan#endif 104169689Skan 105169689Skan 106132718Skan/* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */ 107169689Skanstatic int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0}; 108132718Skan 109132718Skan/* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */ 110169689Skanstatic int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0}; 111132718Skan 112132718Skan/* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry 113132718Skan block the edge destination is not duplicated while connecting traces. */ 114132718Skan#define DUPLICATION_THRESHOLD 100 115132718Skan 116132718Skan/* Length of unconditional jump instruction. */ 117132718Skanstatic int uncond_jump_length; 118132718Skan 119132718Skan/* Structure to hold needed information for each basic block. */ 120132718Skantypedef struct bbro_basic_block_data_def 121132718Skan{ 122132718Skan /* Which trace is the bb start of (-1 means it is not a start of a trace). */ 123132718Skan int start_of_trace; 124132718Skan 125132718Skan /* Which trace is the bb end of (-1 means it is not an end of a trace). */ 126132718Skan int end_of_trace; 127132718Skan 128169689Skan /* Which trace is the bb in? */ 129169689Skan int in_trace; 130169689Skan 131132718Skan /* Which heap is BB in (if any)? */ 132132718Skan fibheap_t heap; 133132718Skan 134132718Skan /* Which heap node is BB in (if any)? */ 135132718Skan fibnode_t node; 136132718Skan} bbro_basic_block_data; 137132718Skan 138132718Skan/* The current size of the following dynamic array. */ 139132718Skanstatic int array_size; 140132718Skan 141132718Skan/* The array which holds needed information for basic blocks. */ 142132718Skanstatic bbro_basic_block_data *bbd; 143132718Skan 144132718Skan/* To avoid frequent reallocation the size of arrays is greater than needed, 145132718Skan the number of elements is (not less than) 1.25 * size_wanted. */ 146132718Skan#define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5) 147132718Skan 148132718Skan/* Free the memory and set the pointer to NULL. */ 149169689Skan#define FREE(P) (gcc_assert (P), free (P), P = 0) 150132718Skan 151132718Skan/* Structure for holding information about a trace. */ 152132718Skanstruct trace 153132718Skan{ 154132718Skan /* First and last basic block of the trace. */ 155132718Skan basic_block first, last; 156132718Skan 157132718Skan /* The round of the STC creation which this trace was found in. */ 158132718Skan int round; 159132718Skan 160132718Skan /* The length (i.e. the number of basic blocks) of the trace. */ 161132718Skan int length; 162132718Skan}; 163132718Skan 164132718Skan/* Maximum frequency and count of one of the entry blocks. */ 165169689Skanstatic int max_entry_frequency; 166169689Skanstatic gcov_type max_entry_count; 167132718Skan 16890075Sobrien/* Local function prototypes. */ 169132718Skanstatic void find_traces (int *, struct trace *); 170132718Skanstatic basic_block rotate_loop (edge, struct trace *, int); 171132718Skanstatic void mark_bb_visited (basic_block, int); 172132718Skanstatic void find_traces_1_round (int, int, gcov_type, struct trace *, int *, 173169689Skan int, fibheap_t *, int); 174132718Skanstatic basic_block copy_bb (basic_block, edge, basic_block, int); 175132718Skanstatic fibheapkey_t bb_to_key (basic_block); 176169689Skanstatic bool better_edge_p (basic_block, edge, int, int, int, int, edge); 177132718Skanstatic void connect_traces (int, struct trace *); 178132718Skanstatic bool copy_bb_p (basic_block, int); 179132718Skanstatic int get_uncond_jump_length (void); 180169689Skanstatic bool push_to_next_round_p (basic_block, int, int, int, gcov_type); 181169689Skanstatic void find_rarely_executed_basic_blocks_and_crossing_edges (edge *, 182169689Skan int *, 183169689Skan int *); 184169689Skanstatic void add_labels_and_missing_jumps (edge *, int); 185169689Skanstatic void add_reg_crossing_jump_notes (void); 186169689Skanstatic void fix_up_fall_thru_edges (void); 187169689Skanstatic void fix_edges_for_rarely_executed_code (edge *, int); 188169689Skanstatic void fix_crossing_conditional_branches (void); 189169689Skanstatic void fix_crossing_unconditional_branches (void); 19090075Sobrien 191169689Skan/* Check to see if bb should be pushed into the next round of trace 192169689Skan collections or not. Reasons for pushing the block forward are 1). 193169689Skan If the block is cold, we are doing partitioning, and there will be 194169689Skan another round (cold partition blocks are not supposed to be 195169689Skan collected into traces until the very last round); or 2). There will 196169689Skan be another round, and the basic block is not "hot enough" for the 197169689Skan current round of trace collection. */ 198169689Skan 199169689Skanstatic bool 200169689Skanpush_to_next_round_p (basic_block bb, int round, int number_of_rounds, 201169689Skan int exec_th, gcov_type count_th) 202169689Skan{ 203169689Skan bool there_exists_another_round; 204169689Skan bool block_not_hot_enough; 205169689Skan 206169689Skan there_exists_another_round = round < number_of_rounds - 1; 207169689Skan 208169689Skan block_not_hot_enough = (bb->frequency < exec_th 209169689Skan || bb->count < count_th 210169689Skan || probably_never_executed_bb_p (bb)); 211169689Skan 212169689Skan if (there_exists_another_round 213169689Skan && block_not_hot_enough) 214169689Skan return true; 215169689Skan else 216169689Skan return false; 217169689Skan} 218169689Skan 219132718Skan/* Find the traces for Software Trace Cache. Chain each trace through 220132718Skan RBI()->next. Store the number of traces to N_TRACES and description of 221132718Skan traces to TRACES. */ 22290075Sobrien 22390075Sobrienstatic void 224132718Skanfind_traces (int *n_traces, struct trace *traces) 22590075Sobrien{ 226132718Skan int i; 227169689Skan int number_of_rounds; 228132718Skan edge e; 229169689Skan edge_iterator ei; 230132718Skan fibheap_t heap; 23190075Sobrien 232169689Skan /* Add one extra round of trace collection when partitioning hot/cold 233169689Skan basic blocks into separate sections. The last round is for all the 234169689Skan cold blocks (and ONLY the cold blocks). */ 235169689Skan 236169689Skan number_of_rounds = N_ROUNDS - 1; 237169689Skan 238132718Skan /* Insert entry points of function into heap. */ 239132718Skan heap = fibheap_new (); 240132718Skan max_entry_frequency = 0; 241132718Skan max_entry_count = 0; 242169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 24390075Sobrien { 244132718Skan bbd[e->dest->index].heap = heap; 245132718Skan bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest), 246132718Skan e->dest); 247132718Skan if (e->dest->frequency > max_entry_frequency) 248132718Skan max_entry_frequency = e->dest->frequency; 249132718Skan if (e->dest->count > max_entry_count) 250132718Skan max_entry_count = e->dest->count; 251132718Skan } 25290075Sobrien 253132718Skan /* Find the traces. */ 254169689Skan for (i = 0; i < number_of_rounds; i++) 255132718Skan { 256132718Skan gcov_type count_threshold; 25790075Sobrien 258169689Skan if (dump_file) 259169689Skan fprintf (dump_file, "STC - round %d\n", i + 1); 260117395Skan 261132718Skan if (max_entry_count < INT_MAX / 1000) 262132718Skan count_threshold = max_entry_count * exec_threshold[i] / 1000; 263132718Skan else 264132718Skan count_threshold = max_entry_count / 1000 * exec_threshold[i]; 265132718Skan 266132718Skan find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000, 267132718Skan max_entry_frequency * exec_threshold[i] / 1000, 268169689Skan count_threshold, traces, n_traces, i, &heap, 269169689Skan number_of_rounds); 27090075Sobrien } 271132718Skan fibheap_delete (heap); 272132718Skan 273169689Skan if (dump_file) 274132718Skan { 275132718Skan for (i = 0; i < *n_traces; i++) 276132718Skan { 277132718Skan basic_block bb; 278169689Skan fprintf (dump_file, "Trace %d (round %d): ", i + 1, 279132718Skan traces[i].round + 1); 280169689Skan for (bb = traces[i].first; bb != traces[i].last; bb = bb->aux) 281169689Skan fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency); 282169689Skan fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency); 283132718Skan } 284169689Skan fflush (dump_file); 285132718Skan } 28690075Sobrien} 28790075Sobrien 288132718Skan/* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE 289132718Skan (with sequential number TRACE_N). */ 290117395Skan 291132718Skanstatic basic_block 292132718Skanrotate_loop (edge back_edge, struct trace *trace, int trace_n) 293117395Skan{ 294132718Skan basic_block bb; 295117395Skan 296132718Skan /* Information about the best end (end after rotation) of the loop. */ 297132718Skan basic_block best_bb = NULL; 298132718Skan edge best_edge = NULL; 299132718Skan int best_freq = -1; 300132718Skan gcov_type best_count = -1; 301132718Skan /* The best edge is preferred when its destination is not visited yet 302132718Skan or is a start block of some trace. */ 303132718Skan bool is_preferred = false; 304117395Skan 305132718Skan /* Find the most frequent edge that goes out from current trace. */ 306132718Skan bb = back_edge->dest; 307132718Skan do 308132718Skan { 309132718Skan edge e; 310169689Skan edge_iterator ei; 311169689Skan 312169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 313132718Skan if (e->dest != EXIT_BLOCK_PTR 314169689Skan && e->dest->il.rtl->visited != trace_n 315132718Skan && (e->flags & EDGE_CAN_FALLTHRU) 316132718Skan && !(e->flags & EDGE_COMPLEX)) 317132718Skan { 318132718Skan if (is_preferred) 319132718Skan { 320132718Skan /* The best edge is preferred. */ 321169689Skan if (!e->dest->il.rtl->visited 322132718Skan || bbd[e->dest->index].start_of_trace >= 0) 323132718Skan { 324132718Skan /* The current edge E is also preferred. */ 325132718Skan int freq = EDGE_FREQUENCY (e); 326132718Skan if (freq > best_freq || e->count > best_count) 327132718Skan { 328132718Skan best_freq = freq; 329132718Skan best_count = e->count; 330132718Skan best_edge = e; 331132718Skan best_bb = bb; 332132718Skan } 333132718Skan } 334132718Skan } 335132718Skan else 336132718Skan { 337169689Skan if (!e->dest->il.rtl->visited 338132718Skan || bbd[e->dest->index].start_of_trace >= 0) 339132718Skan { 340132718Skan /* The current edge E is preferred. */ 341132718Skan is_preferred = true; 342132718Skan best_freq = EDGE_FREQUENCY (e); 343132718Skan best_count = e->count; 344132718Skan best_edge = e; 345132718Skan best_bb = bb; 346132718Skan } 347132718Skan else 348132718Skan { 349132718Skan int freq = EDGE_FREQUENCY (e); 350132718Skan if (!best_edge || freq > best_freq || e->count > best_count) 351132718Skan { 352132718Skan best_freq = freq; 353132718Skan best_count = e->count; 354132718Skan best_edge = e; 355132718Skan best_bb = bb; 356132718Skan } 357132718Skan } 358132718Skan } 359132718Skan } 360169689Skan bb = bb->aux; 361132718Skan } 362132718Skan while (bb != back_edge->dest); 363117395Skan 364132718Skan if (best_bb) 365132718Skan { 366132718Skan /* Rotate the loop so that the BEST_EDGE goes out from the last block of 367132718Skan the trace. */ 368132718Skan if (back_edge->dest == trace->first) 369132718Skan { 370169689Skan trace->first = best_bb->aux; 371132718Skan } 372132718Skan else 373132718Skan { 374132718Skan basic_block prev_bb; 375117395Skan 376132718Skan for (prev_bb = trace->first; 377169689Skan prev_bb->aux != back_edge->dest; 378169689Skan prev_bb = prev_bb->aux) 379132718Skan ; 380169689Skan prev_bb->aux = best_bb->aux; 381132718Skan 382132718Skan /* Try to get rid of uncond jump to cond jump. */ 383169689Skan if (single_succ_p (prev_bb)) 384132718Skan { 385169689Skan basic_block header = single_succ (prev_bb); 386132718Skan 387132718Skan /* Duplicate HEADER if it is a small block containing cond jump 388132718Skan in the end. */ 389169689Skan if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0) 390169689Skan && !find_reg_note (BB_END (header), REG_CROSSING_JUMP, 391169689Skan NULL_RTX)) 392169689Skan copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n); 393132718Skan } 394132718Skan } 395132718Skan } 396132718Skan else 397117395Skan { 398132718Skan /* We have not found suitable loop tail so do no rotation. */ 399132718Skan best_bb = back_edge->src; 400117395Skan } 401169689Skan best_bb->aux = NULL; 402132718Skan return best_bb; 403132718Skan} 404117395Skan 405132718Skan/* This function marks BB that it was visited in trace number TRACE. */ 406132718Skan 407132718Skanstatic void 408132718Skanmark_bb_visited (basic_block bb, int trace) 409132718Skan{ 410169689Skan bb->il.rtl->visited = trace; 411132718Skan if (bbd[bb->index].heap) 412132718Skan { 413132718Skan fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node); 414132718Skan bbd[bb->index].heap = NULL; 415132718Skan bbd[bb->index].node = NULL; 416132718Skan } 417117395Skan} 418117395Skan 419132718Skan/* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do 420132718Skan not include basic blocks their probability is lower than BRANCH_TH or their 421132718Skan frequency is lower than EXEC_TH into traces (or count is lower than 422132718Skan COUNT_TH). It stores the new traces into TRACES and modifies the number of 423132718Skan traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It 424132718Skan expects that starting basic blocks are in *HEAP and at the end it deletes 425132718Skan *HEAP and stores starting points for the next round into new *HEAP. */ 42690075Sobrien 427132718Skanstatic void 428132718Skanfind_traces_1_round (int branch_th, int exec_th, gcov_type count_th, 429132718Skan struct trace *traces, int *n_traces, int round, 430169689Skan fibheap_t *heap, int number_of_rounds) 431132718Skan{ 432132718Skan /* Heap for discarded basic blocks which are possible starting points for 433132718Skan the next round. */ 434132718Skan fibheap_t new_heap = fibheap_new (); 43590075Sobrien 436132718Skan while (!fibheap_empty (*heap)) 437132718Skan { 438132718Skan basic_block bb; 439132718Skan struct trace *trace; 440132718Skan edge best_edge, e; 441132718Skan fibheapkey_t key; 442169689Skan edge_iterator ei; 44390075Sobrien 444132718Skan bb = fibheap_extract_min (*heap); 445132718Skan bbd[bb->index].heap = NULL; 446132718Skan bbd[bb->index].node = NULL; 447132718Skan 448169689Skan if (dump_file) 449169689Skan fprintf (dump_file, "Getting bb %d\n", bb->index); 450132718Skan 451169689Skan /* If the BB's frequency is too low send BB to the next round. When 452169689Skan partitioning hot/cold blocks into separate sections, make sure all 453169689Skan the cold blocks (and ONLY the cold blocks) go into the (extra) final 454169689Skan round. */ 455169689Skan 456169689Skan if (push_to_next_round_p (bb, round, number_of_rounds, exec_th, 457169689Skan count_th)) 458132718Skan { 459132718Skan int key = bb_to_key (bb); 460132718Skan bbd[bb->index].heap = new_heap; 461132718Skan bbd[bb->index].node = fibheap_insert (new_heap, key, bb); 462132718Skan 463169689Skan if (dump_file) 464169689Skan fprintf (dump_file, 465132718Skan " Possible start point of next round: %d (key: %d)\n", 466132718Skan bb->index, key); 467132718Skan continue; 468132718Skan } 469132718Skan 470132718Skan trace = traces + *n_traces; 471132718Skan trace->first = bb; 472132718Skan trace->round = round; 473132718Skan trace->length = 0; 474169689Skan bbd[bb->index].in_trace = *n_traces; 475132718Skan (*n_traces)++; 476132718Skan 477132718Skan do 478132718Skan { 479132718Skan int prob, freq; 480169689Skan bool ends_in_call; 481132718Skan 482132718Skan /* The probability and frequency of the best edge. */ 483132718Skan int best_prob = INT_MIN / 2; 484132718Skan int best_freq = INT_MIN / 2; 485132718Skan 486132718Skan best_edge = NULL; 487132718Skan mark_bb_visited (bb, *n_traces); 488132718Skan trace->length++; 489132718Skan 490169689Skan if (dump_file) 491169689Skan fprintf (dump_file, "Basic block %d was visited in trace %d\n", 492132718Skan bb->index, *n_traces - 1); 493132718Skan 494169689Skan ends_in_call = block_ends_with_call_p (bb); 495169689Skan 496132718Skan /* Select the successor that will be placed after BB. */ 497169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 498132718Skan { 499169689Skan gcc_assert (!(e->flags & EDGE_FAKE)); 500132718Skan 501132718Skan if (e->dest == EXIT_BLOCK_PTR) 502132718Skan continue; 503132718Skan 504169689Skan if (e->dest->il.rtl->visited 505169689Skan && e->dest->il.rtl->visited != *n_traces) 506132718Skan continue; 507132718Skan 508169689Skan if (BB_PARTITION (e->dest) != BB_PARTITION (bb)) 509169689Skan continue; 510169689Skan 511132718Skan prob = e->probability; 512169689Skan freq = e->dest->frequency; 513132718Skan 514169689Skan /* The only sensible preference for a call instruction is the 515169689Skan fallthru edge. Don't bother selecting anything else. */ 516169689Skan if (ends_in_call) 517169689Skan { 518169689Skan if (e->flags & EDGE_CAN_FALLTHRU) 519169689Skan { 520169689Skan best_edge = e; 521169689Skan best_prob = prob; 522169689Skan best_freq = freq; 523169689Skan } 524169689Skan continue; 525169689Skan } 526169689Skan 527132718Skan /* Edge that cannot be fallthru or improbable or infrequent 528169689Skan successor (i.e. it is unsuitable successor). */ 529132718Skan if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX) 530169689Skan || prob < branch_th || EDGE_FREQUENCY (e) < exec_th 531169689Skan || e->count < count_th) 532132718Skan continue; 533132718Skan 534169689Skan /* If partitioning hot/cold basic blocks, don't consider edges 535169689Skan that cross section boundaries. */ 536169689Skan 537169689Skan if (better_edge_p (bb, e, prob, freq, best_prob, best_freq, 538169689Skan best_edge)) 539132718Skan { 540132718Skan best_edge = e; 541132718Skan best_prob = prob; 542132718Skan best_freq = freq; 543132718Skan } 544132718Skan } 545132718Skan 546132718Skan /* If the best destination has multiple predecessors, and can be 547132718Skan duplicated cheaper than a jump, don't allow it to be added 548132718Skan to a trace. We'll duplicate it when connecting traces. */ 549169689Skan if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2 550132718Skan && copy_bb_p (best_edge->dest, 0)) 551132718Skan best_edge = NULL; 552132718Skan 553132718Skan /* Add all non-selected successors to the heaps. */ 554169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 555132718Skan { 556132718Skan if (e == best_edge 557132718Skan || e->dest == EXIT_BLOCK_PTR 558169689Skan || e->dest->il.rtl->visited) 559132718Skan continue; 560132718Skan 561132718Skan key = bb_to_key (e->dest); 562132718Skan 563132718Skan if (bbd[e->dest->index].heap) 564132718Skan { 565132718Skan /* E->DEST is already in some heap. */ 566132718Skan if (key != bbd[e->dest->index].node->key) 567132718Skan { 568169689Skan if (dump_file) 569132718Skan { 570169689Skan fprintf (dump_file, 571132718Skan "Changing key for bb %d from %ld to %ld.\n", 572132718Skan e->dest->index, 573132718Skan (long) bbd[e->dest->index].node->key, 574132718Skan key); 575132718Skan } 576132718Skan fibheap_replace_key (bbd[e->dest->index].heap, 577132718Skan bbd[e->dest->index].node, key); 578132718Skan } 579132718Skan } 580132718Skan else 581132718Skan { 582132718Skan fibheap_t which_heap = *heap; 583132718Skan 584132718Skan prob = e->probability; 585132718Skan freq = EDGE_FREQUENCY (e); 586132718Skan 587132718Skan if (!(e->flags & EDGE_CAN_FALLTHRU) 588132718Skan || (e->flags & EDGE_COMPLEX) 589132718Skan || prob < branch_th || freq < exec_th 590132718Skan || e->count < count_th) 591132718Skan { 592169689Skan /* When partitioning hot/cold basic blocks, make sure 593169689Skan the cold blocks (and only the cold blocks) all get 594169689Skan pushed to the last round of trace collection. */ 595169689Skan 596169689Skan if (push_to_next_round_p (e->dest, round, 597169689Skan number_of_rounds, 598169689Skan exec_th, count_th)) 599132718Skan which_heap = new_heap; 600132718Skan } 601132718Skan 602132718Skan bbd[e->dest->index].heap = which_heap; 603132718Skan bbd[e->dest->index].node = fibheap_insert (which_heap, 604132718Skan key, e->dest); 605132718Skan 606169689Skan if (dump_file) 607132718Skan { 608169689Skan fprintf (dump_file, 609132718Skan " Possible start of %s round: %d (key: %ld)\n", 610132718Skan (which_heap == new_heap) ? "next" : "this", 611132718Skan e->dest->index, (long) key); 612132718Skan } 613132718Skan 614132718Skan } 615132718Skan } 616132718Skan 617132718Skan if (best_edge) /* Suitable successor was found. */ 618132718Skan { 619169689Skan if (best_edge->dest->il.rtl->visited == *n_traces) 620132718Skan { 621132718Skan /* We do nothing with one basic block loops. */ 622132718Skan if (best_edge->dest != bb) 623132718Skan { 624132718Skan if (EDGE_FREQUENCY (best_edge) 625132718Skan > 4 * best_edge->dest->frequency / 5) 626132718Skan { 627132718Skan /* The loop has at least 4 iterations. If the loop 628132718Skan header is not the first block of the function 629132718Skan we can rotate the loop. */ 630132718Skan 631132718Skan if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb) 632132718Skan { 633169689Skan if (dump_file) 634132718Skan { 635169689Skan fprintf (dump_file, 636132718Skan "Rotating loop %d - %d\n", 637132718Skan best_edge->dest->index, bb->index); 638132718Skan } 639169689Skan bb->aux = best_edge->dest; 640169689Skan bbd[best_edge->dest->index].in_trace = 641169689Skan (*n_traces) - 1; 642132718Skan bb = rotate_loop (best_edge, trace, *n_traces); 643132718Skan } 644132718Skan } 645132718Skan else 646132718Skan { 647132718Skan /* The loop has less than 4 iterations. */ 648132718Skan 649169689Skan if (single_succ_p (bb) 650169689Skan && copy_bb_p (best_edge->dest, !optimize_size)) 651132718Skan { 652132718Skan bb = copy_bb (best_edge->dest, best_edge, bb, 653132718Skan *n_traces); 654169689Skan trace->length++; 655132718Skan } 656132718Skan } 657132718Skan } 658132718Skan 659132718Skan /* Terminate the trace. */ 660132718Skan break; 661132718Skan } 662132718Skan else 663132718Skan { 664132718Skan /* Check for a situation 665132718Skan 666132718Skan A 667132718Skan /| 668132718Skan B | 669132718Skan \| 670132718Skan C 671132718Skan 672132718Skan where 673132718Skan EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC) 674132718Skan >= EDGE_FREQUENCY (AC). 675132718Skan (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) ) 676132718Skan Best ordering is then A B C. 677132718Skan 678132718Skan This situation is created for example by: 679132718Skan 680132718Skan if (A) B; 681132718Skan C; 682132718Skan 683132718Skan */ 684132718Skan 685169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 686132718Skan if (e != best_edge 687132718Skan && (e->flags & EDGE_CAN_FALLTHRU) 688132718Skan && !(e->flags & EDGE_COMPLEX) 689169689Skan && !e->dest->il.rtl->visited 690169689Skan && single_pred_p (e->dest) 691169689Skan && !(e->flags & EDGE_CROSSING) 692169689Skan && single_succ_p (e->dest) 693169689Skan && (single_succ_edge (e->dest)->flags 694169689Skan & EDGE_CAN_FALLTHRU) 695169689Skan && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX) 696169689Skan && single_succ (e->dest) == best_edge->dest 697132718Skan && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge)) 698132718Skan { 699132718Skan best_edge = e; 700169689Skan if (dump_file) 701169689Skan fprintf (dump_file, "Selecting BB %d\n", 702132718Skan best_edge->dest->index); 703132718Skan break; 704132718Skan } 705132718Skan 706169689Skan bb->aux = best_edge->dest; 707169689Skan bbd[best_edge->dest->index].in_trace = (*n_traces) - 1; 708132718Skan bb = best_edge->dest; 709132718Skan } 710132718Skan } 711132718Skan } 712132718Skan while (best_edge); 713132718Skan trace->last = bb; 714132718Skan bbd[trace->first->index].start_of_trace = *n_traces - 1; 715132718Skan bbd[trace->last->index].end_of_trace = *n_traces - 1; 716132718Skan 717132718Skan /* The trace is terminated so we have to recount the keys in heap 718132718Skan (some block can have a lower key because now one of its predecessors 719132718Skan is an end of the trace). */ 720169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 721132718Skan { 722132718Skan if (e->dest == EXIT_BLOCK_PTR 723169689Skan || e->dest->il.rtl->visited) 724132718Skan continue; 725132718Skan 726132718Skan if (bbd[e->dest->index].heap) 727132718Skan { 728132718Skan key = bb_to_key (e->dest); 729132718Skan if (key != bbd[e->dest->index].node->key) 730132718Skan { 731169689Skan if (dump_file) 732132718Skan { 733169689Skan fprintf (dump_file, 734132718Skan "Changing key for bb %d from %ld to %ld.\n", 735132718Skan e->dest->index, 736132718Skan (long) bbd[e->dest->index].node->key, key); 737132718Skan } 738132718Skan fibheap_replace_key (bbd[e->dest->index].heap, 739132718Skan bbd[e->dest->index].node, 740132718Skan key); 741132718Skan } 742132718Skan } 743132718Skan } 744132718Skan } 745132718Skan 746132718Skan fibheap_delete (*heap); 747132718Skan 748132718Skan /* "Return" the new heap. */ 749132718Skan *heap = new_heap; 750132718Skan} 751132718Skan 752132718Skan/* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add 753132718Skan it to trace after BB, mark OLD_BB visited and update pass' data structures 754132718Skan (TRACE is a number of trace which OLD_BB is duplicated to). */ 755132718Skan 75690075Sobrienstatic basic_block 757132718Skancopy_bb (basic_block old_bb, edge e, basic_block bb, int trace) 75890075Sobrien{ 759132718Skan basic_block new_bb; 76090075Sobrien 761169689Skan new_bb = duplicate_block (old_bb, e, bb); 762169689Skan BB_COPY_PARTITION (new_bb, old_bb); 763169689Skan 764169689Skan gcc_assert (e->dest == new_bb); 765169689Skan gcc_assert (!e->dest->il.rtl->visited); 766169689Skan 767169689Skan if (dump_file) 768169689Skan fprintf (dump_file, 769132718Skan "Duplicated bb %d (created bb %d)\n", 770132718Skan old_bb->index, new_bb->index); 771169689Skan new_bb->il.rtl->visited = trace; 772169689Skan new_bb->aux = bb->aux; 773169689Skan bb->aux = new_bb; 774132718Skan 775132718Skan if (new_bb->index >= array_size || last_basic_block > array_size) 77690075Sobrien { 777132718Skan int i; 778132718Skan int new_size; 77990075Sobrien 780132718Skan new_size = MAX (last_basic_block, new_bb->index + 1); 781132718Skan new_size = GET_ARRAY_SIZE (new_size); 782132718Skan bbd = xrealloc (bbd, new_size * sizeof (bbro_basic_block_data)); 783132718Skan for (i = array_size; i < new_size; i++) 784132718Skan { 785132718Skan bbd[i].start_of_trace = -1; 786169689Skan bbd[i].in_trace = -1; 787132718Skan bbd[i].end_of_trace = -1; 788132718Skan bbd[i].heap = NULL; 789132718Skan bbd[i].node = NULL; 790132718Skan } 791132718Skan array_size = new_size; 792132718Skan 793169689Skan if (dump_file) 794132718Skan { 795169689Skan fprintf (dump_file, 796132718Skan "Growing the dynamic array to %d elements.\n", 797132718Skan array_size); 798132718Skan } 79990075Sobrien } 800132718Skan 801169689Skan bbd[new_bb->index].in_trace = trace; 802169689Skan 803132718Skan return new_bb; 804132718Skan} 805132718Skan 806132718Skan/* Compute and return the key (for the heap) of the basic block BB. */ 807132718Skan 808132718Skanstatic fibheapkey_t 809132718Skanbb_to_key (basic_block bb) 810132718Skan{ 811132718Skan edge e; 812169689Skan edge_iterator ei; 813132718Skan int priority = 0; 814132718Skan 815132718Skan /* Do not start in probably never executed blocks. */ 816169689Skan 817169689Skan if (BB_PARTITION (bb) == BB_COLD_PARTITION 818169689Skan || probably_never_executed_bb_p (bb)) 819132718Skan return BB_FREQ_MAX; 820132718Skan 821132718Skan /* Prefer blocks whose predecessor is an end of some trace 822132718Skan or whose predecessor edge is EDGE_DFS_BACK. */ 823169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 82490075Sobrien { 825132718Skan if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0) 826132718Skan || (e->flags & EDGE_DFS_BACK)) 827132718Skan { 828132718Skan int edge_freq = EDGE_FREQUENCY (e); 829132718Skan 830132718Skan if (edge_freq > priority) 831132718Skan priority = edge_freq; 832132718Skan } 83390075Sobrien } 83490075Sobrien 835132718Skan if (priority) 836132718Skan /* The block with priority should have significantly lower key. */ 837132718Skan return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency); 838132718Skan return -bb->frequency; 839132718Skan} 84090075Sobrien 841132718Skan/* Return true when the edge E from basic block BB is better than the temporary 842132718Skan best edge (details are in function). The probability of edge E is PROB. The 843132718Skan frequency of the successor is FREQ. The current best probability is 844132718Skan BEST_PROB, the best frequency is BEST_FREQ. 845132718Skan The edge is considered to be equivalent when PROB does not differ much from 846132718Skan BEST_PROB; similarly for frequency. */ 84790075Sobrien 848132718Skanstatic bool 849132718Skanbetter_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob, 850169689Skan int best_freq, edge cur_best_edge) 851132718Skan{ 852132718Skan bool is_better_edge; 853132718Skan 854132718Skan /* The BEST_* values do not have to be best, but can be a bit smaller than 855132718Skan maximum values. */ 856132718Skan int diff_prob = best_prob / 10; 857132718Skan int diff_freq = best_freq / 10; 858132718Skan 859132718Skan if (prob > best_prob + diff_prob) 860132718Skan /* The edge has higher probability than the temporary best edge. */ 861132718Skan is_better_edge = true; 862132718Skan else if (prob < best_prob - diff_prob) 863132718Skan /* The edge has lower probability than the temporary best edge. */ 864132718Skan is_better_edge = false; 865132718Skan else if (freq < best_freq - diff_freq) 866132718Skan /* The edge and the temporary best edge have almost equivalent 867132718Skan probabilities. The higher frequency of a successor now means 868132718Skan that there is another edge going into that successor. 869132718Skan This successor has lower frequency so it is better. */ 870132718Skan is_better_edge = true; 871132718Skan else if (freq > best_freq + diff_freq) 872132718Skan /* This successor has higher frequency so it is worse. */ 873132718Skan is_better_edge = false; 874132718Skan else if (e->dest->prev_bb == bb) 875132718Skan /* The edges have equivalent probabilities and the successors 876132718Skan have equivalent frequencies. Select the previous successor. */ 877132718Skan is_better_edge = true; 878132718Skan else 879132718Skan is_better_edge = false; 880132718Skan 881169689Skan /* If we are doing hot/cold partitioning, make sure that we always favor 882169689Skan non-crossing edges over crossing edges. */ 883169689Skan 884169689Skan if (!is_better_edge 885169689Skan && flag_reorder_blocks_and_partition 886169689Skan && cur_best_edge 887169689Skan && (cur_best_edge->flags & EDGE_CROSSING) 888169689Skan && !(e->flags & EDGE_CROSSING)) 889169689Skan is_better_edge = true; 890169689Skan 891132718Skan return is_better_edge; 892132718Skan} 893132718Skan 894132718Skan/* Connect traces in array TRACES, N_TRACES is the count of traces. */ 895132718Skan 896132718Skanstatic void 897132718Skanconnect_traces (int n_traces, struct trace *traces) 898132718Skan{ 899132718Skan int i; 900132718Skan bool *connected; 901169689Skan bool two_passes; 902132718Skan int last_trace; 903169689Skan int current_pass; 904169689Skan int current_partition; 905132718Skan int freq_threshold; 906132718Skan gcov_type count_threshold; 907132718Skan 908132718Skan freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000; 909132718Skan if (max_entry_count < INT_MAX / 1000) 910132718Skan count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000; 911132718Skan else 912132718Skan count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD; 913132718Skan 914169689Skan connected = XCNEWVEC (bool, n_traces); 915132718Skan last_trace = -1; 916169689Skan current_pass = 1; 917169689Skan current_partition = BB_PARTITION (traces[0].first); 918169689Skan two_passes = false; 919169689Skan 920169689Skan if (flag_reorder_blocks_and_partition) 921169689Skan for (i = 0; i < n_traces && !two_passes; i++) 922169689Skan if (BB_PARTITION (traces[0].first) 923169689Skan != BB_PARTITION (traces[i].first)) 924169689Skan two_passes = true; 925169689Skan 926169689Skan for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++) 92790075Sobrien { 928132718Skan int t = i; 929132718Skan int t2; 930132718Skan edge e, best; 931132718Skan int best_len; 93290075Sobrien 933169689Skan if (i >= n_traces) 934169689Skan { 935169689Skan gcc_assert (two_passes && current_pass == 1); 936169689Skan i = 0; 937169689Skan t = i; 938169689Skan current_pass = 2; 939169689Skan if (current_partition == BB_HOT_PARTITION) 940169689Skan current_partition = BB_COLD_PARTITION; 941169689Skan else 942169689Skan current_partition = BB_HOT_PARTITION; 943169689Skan } 944169689Skan 945132718Skan if (connected[t]) 946132718Skan continue; 94790075Sobrien 948169689Skan if (two_passes 949169689Skan && BB_PARTITION (traces[t].first) != current_partition) 950169689Skan continue; 951169689Skan 952132718Skan connected[t] = true; 95390075Sobrien 954132718Skan /* Find the predecessor traces. */ 955132718Skan for (t2 = t; t2 > 0;) 956132718Skan { 957169689Skan edge_iterator ei; 958132718Skan best = NULL; 959132718Skan best_len = 0; 960169689Skan FOR_EACH_EDGE (e, ei, traces[t2].first->preds) 961132718Skan { 962132718Skan int si = e->src->index; 96390075Sobrien 964132718Skan if (e->src != ENTRY_BLOCK_PTR 965132718Skan && (e->flags & EDGE_CAN_FALLTHRU) 966132718Skan && !(e->flags & EDGE_COMPLEX) 967132718Skan && bbd[si].end_of_trace >= 0 968132718Skan && !connected[bbd[si].end_of_trace] 969169689Skan && (BB_PARTITION (e->src) == current_partition) 970132718Skan && (!best 971132718Skan || e->probability > best->probability 972132718Skan || (e->probability == best->probability 973132718Skan && traces[bbd[si].end_of_trace].length > best_len))) 974132718Skan { 975132718Skan best = e; 976132718Skan best_len = traces[bbd[si].end_of_trace].length; 977132718Skan } 978132718Skan } 979132718Skan if (best) 980132718Skan { 981169689Skan best->src->aux = best->dest; 982132718Skan t2 = bbd[best->src->index].end_of_trace; 983132718Skan connected[t2] = true; 984169689Skan 985169689Skan if (dump_file) 986132718Skan { 987169689Skan fprintf (dump_file, "Connection: %d %d\n", 988132718Skan best->src->index, best->dest->index); 989132718Skan } 990132718Skan } 991132718Skan else 992132718Skan break; 993132718Skan } 99490075Sobrien 995132718Skan if (last_trace >= 0) 996169689Skan traces[last_trace].last->aux = traces[t2].first; 997132718Skan last_trace = t; 998132718Skan 999132718Skan /* Find the successor traces. */ 1000132718Skan while (1) 100190075Sobrien { 1002132718Skan /* Find the continuation of the chain. */ 1003169689Skan edge_iterator ei; 1004132718Skan best = NULL; 1005132718Skan best_len = 0; 1006169689Skan FOR_EACH_EDGE (e, ei, traces[t].last->succs) 1007132718Skan { 1008132718Skan int di = e->dest->index; 1009132718Skan 1010132718Skan if (e->dest != EXIT_BLOCK_PTR 1011132718Skan && (e->flags & EDGE_CAN_FALLTHRU) 1012132718Skan && !(e->flags & EDGE_COMPLEX) 1013132718Skan && bbd[di].start_of_trace >= 0 1014132718Skan && !connected[bbd[di].start_of_trace] 1015169689Skan && (BB_PARTITION (e->dest) == current_partition) 1016132718Skan && (!best 1017132718Skan || e->probability > best->probability 1018132718Skan || (e->probability == best->probability 1019132718Skan && traces[bbd[di].start_of_trace].length > best_len))) 1020132718Skan { 1021132718Skan best = e; 1022132718Skan best_len = traces[bbd[di].start_of_trace].length; 1023132718Skan } 1024132718Skan } 1025132718Skan 1026132718Skan if (best) 1027132718Skan { 1028169689Skan if (dump_file) 1029132718Skan { 1030169689Skan fprintf (dump_file, "Connection: %d %d\n", 1031132718Skan best->src->index, best->dest->index); 1032132718Skan } 1033132718Skan t = bbd[best->dest->index].start_of_trace; 1034169689Skan traces[last_trace].last->aux = traces[t].first; 1035132718Skan connected[t] = true; 1036132718Skan last_trace = t; 1037132718Skan } 1038132718Skan else 1039132718Skan { 1040132718Skan /* Try to connect the traces by duplication of 1 block. */ 1041132718Skan edge e2; 1042132718Skan basic_block next_bb = NULL; 1043132718Skan bool try_copy = false; 1044132718Skan 1045169689Skan FOR_EACH_EDGE (e, ei, traces[t].last->succs) 1046132718Skan if (e->dest != EXIT_BLOCK_PTR 1047132718Skan && (e->flags & EDGE_CAN_FALLTHRU) 1048132718Skan && !(e->flags & EDGE_COMPLEX) 1049132718Skan && (!best || e->probability > best->probability)) 1050132718Skan { 1051169689Skan edge_iterator ei; 1052132718Skan edge best2 = NULL; 1053132718Skan int best2_len = 0; 1054132718Skan 1055132718Skan /* If the destination is a start of a trace which is only 1056132718Skan one block long, then no need to search the successor 1057132718Skan blocks of the trace. Accept it. */ 1058132718Skan if (bbd[e->dest->index].start_of_trace >= 0 1059132718Skan && traces[bbd[e->dest->index].start_of_trace].length 1060132718Skan == 1) 1061132718Skan { 1062132718Skan best = e; 1063132718Skan try_copy = true; 1064132718Skan continue; 1065132718Skan } 1066132718Skan 1067169689Skan FOR_EACH_EDGE (e2, ei, e->dest->succs) 1068132718Skan { 1069132718Skan int di = e2->dest->index; 1070132718Skan 1071132718Skan if (e2->dest == EXIT_BLOCK_PTR 1072132718Skan || ((e2->flags & EDGE_CAN_FALLTHRU) 1073132718Skan && !(e2->flags & EDGE_COMPLEX) 1074132718Skan && bbd[di].start_of_trace >= 0 1075132718Skan && !connected[bbd[di].start_of_trace] 1076169689Skan && (BB_PARTITION (e2->dest) == current_partition) 1077132718Skan && (EDGE_FREQUENCY (e2) >= freq_threshold) 1078132718Skan && (e2->count >= count_threshold) 1079132718Skan && (!best2 1080132718Skan || e2->probability > best2->probability 1081132718Skan || (e2->probability == best2->probability 1082132718Skan && traces[bbd[di].start_of_trace].length 1083132718Skan > best2_len)))) 1084132718Skan { 1085132718Skan best = e; 1086132718Skan best2 = e2; 1087132718Skan if (e2->dest != EXIT_BLOCK_PTR) 1088132718Skan best2_len = traces[bbd[di].start_of_trace].length; 1089132718Skan else 1090132718Skan best2_len = INT_MAX; 1091132718Skan next_bb = e2->dest; 1092132718Skan try_copy = true; 1093132718Skan } 1094132718Skan } 1095132718Skan } 1096132718Skan 1097169689Skan if (flag_reorder_blocks_and_partition) 1098169689Skan try_copy = false; 1099169689Skan 1100132718Skan /* Copy tiny blocks always; copy larger blocks only when the 1101132718Skan edge is traversed frequently enough. */ 1102132718Skan if (try_copy 1103132718Skan && copy_bb_p (best->dest, 1104132718Skan !optimize_size 1105132718Skan && EDGE_FREQUENCY (best) >= freq_threshold 1106132718Skan && best->count >= count_threshold)) 1107132718Skan { 1108132718Skan basic_block new_bb; 1109132718Skan 1110169689Skan if (dump_file) 1111132718Skan { 1112169689Skan fprintf (dump_file, "Connection: %d %d ", 1113132718Skan traces[t].last->index, best->dest->index); 1114132718Skan if (!next_bb) 1115169689Skan fputc ('\n', dump_file); 1116132718Skan else if (next_bb == EXIT_BLOCK_PTR) 1117169689Skan fprintf (dump_file, "exit\n"); 1118132718Skan else 1119169689Skan fprintf (dump_file, "%d\n", next_bb->index); 1120132718Skan } 1121132718Skan 1122132718Skan new_bb = copy_bb (best->dest, best, traces[t].last, t); 1123132718Skan traces[t].last = new_bb; 1124132718Skan if (next_bb && next_bb != EXIT_BLOCK_PTR) 1125132718Skan { 1126132718Skan t = bbd[next_bb->index].start_of_trace; 1127169689Skan traces[last_trace].last->aux = traces[t].first; 1128132718Skan connected[t] = true; 1129132718Skan last_trace = t; 1130132718Skan } 1131132718Skan else 1132132718Skan break; /* Stop finding the successor traces. */ 1133132718Skan } 1134132718Skan else 1135132718Skan break; /* Stop finding the successor traces. */ 1136132718Skan } 113790075Sobrien } 1138132718Skan } 113990075Sobrien 1140169689Skan if (dump_file) 1141132718Skan { 1142132718Skan basic_block bb; 1143132718Skan 1144169689Skan fprintf (dump_file, "Final order:\n"); 1145169689Skan for (bb = traces[0].first; bb; bb = bb->aux) 1146169689Skan fprintf (dump_file, "%d ", bb->index); 1147169689Skan fprintf (dump_file, "\n"); 1148169689Skan fflush (dump_file); 114990075Sobrien } 115090075Sobrien 1151132718Skan FREE (connected); 1152132718Skan} 1153117395Skan 1154132718Skan/* Return true when BB can and should be copied. CODE_MAY_GROW is true 1155132718Skan when code size is allowed to grow by duplication. */ 1156132718Skan 1157132718Skanstatic bool 1158132718Skancopy_bb_p (basic_block bb, int code_may_grow) 1159132718Skan{ 1160132718Skan int size = 0; 1161132718Skan int max_size = uncond_jump_length; 1162132718Skan rtx insn; 1163132718Skan 1164132718Skan if (!bb->frequency) 1165132718Skan return false; 1166169689Skan if (EDGE_COUNT (bb->preds) < 2) 1167132718Skan return false; 1168169689Skan if (!can_duplicate_block_p (bb)) 1169132718Skan return false; 1170132718Skan 1171132718Skan /* Avoid duplicating blocks which have many successors (PR/13430). */ 1172169689Skan if (EDGE_COUNT (bb->succs) > 8) 1173169689Skan return false; 117490075Sobrien 1175132718Skan if (code_may_grow && maybe_hot_bb_p (bb)) 1176169689Skan max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS); 117790075Sobrien 1178169689Skan FOR_BB_INSNS (bb, insn) 117990075Sobrien { 1180132718Skan if (INSN_P (insn)) 1181169689Skan size += get_attr_min_length (insn); 118290075Sobrien } 118390075Sobrien 1184132718Skan if (size <= max_size) 1185132718Skan return true; 1186132718Skan 1187169689Skan if (dump_file) 1188132718Skan { 1189169689Skan fprintf (dump_file, 1190132718Skan "Block %d can't be copied because its size = %d.\n", 1191132718Skan bb->index, size); 1192132718Skan } 1193132718Skan 1194132718Skan return false; 119590075Sobrien} 119690075Sobrien 1197132718Skan/* Return the length of unconditional jump instruction. */ 119890075Sobrien 1199132718Skanstatic int 1200132718Skanget_uncond_jump_length (void) 1201132718Skan{ 1202132718Skan rtx label, jump; 1203132718Skan int length; 1204132718Skan 1205132718Skan label = emit_label_before (gen_label_rtx (), get_insns ()); 1206132718Skan jump = emit_jump_insn (gen_jump (label)); 1207132718Skan 1208169689Skan length = get_attr_min_length (jump); 1209132718Skan 1210132718Skan delete_insn (jump); 1211132718Skan delete_insn (label); 1212132718Skan return length; 1213132718Skan} 1214132718Skan 1215169689Skan/* Find the basic blocks that are rarely executed and need to be moved to 1216169689Skan a separate section of the .o file (to cut down on paging and improve 1217169689Skan cache locality). */ 1218169689Skan 1219169689Skanstatic void 1220169689Skanfind_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges, 1221169689Skan int *n_crossing_edges, 1222169689Skan int *max_idx) 1223169689Skan{ 1224169689Skan basic_block bb; 1225169689Skan bool has_hot_blocks = false; 1226169689Skan edge e; 1227169689Skan int i; 1228169689Skan edge_iterator ei; 1229169689Skan 1230169689Skan /* Mark which partition (hot/cold) each basic block belongs in. */ 1231169689Skan 1232169689Skan FOR_EACH_BB (bb) 1233169689Skan { 1234169689Skan if (probably_never_executed_bb_p (bb)) 1235169689Skan BB_SET_PARTITION (bb, BB_COLD_PARTITION); 1236169689Skan else 1237169689Skan { 1238169689Skan BB_SET_PARTITION (bb, BB_HOT_PARTITION); 1239169689Skan has_hot_blocks = true; 1240169689Skan } 1241169689Skan } 1242169689Skan 1243169689Skan /* Mark every edge that crosses between sections. */ 1244169689Skan 1245169689Skan i = 0; 1246169689Skan FOR_EACH_BB (bb) 1247169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1248169689Skan { 1249169689Skan if (e->src != ENTRY_BLOCK_PTR 1250169689Skan && e->dest != EXIT_BLOCK_PTR 1251169689Skan && BB_PARTITION (e->src) != BB_PARTITION (e->dest)) 1252169689Skan { 1253169689Skan e->flags |= EDGE_CROSSING; 1254169689Skan if (i == *max_idx) 1255169689Skan { 1256169689Skan *max_idx *= 2; 1257169689Skan crossing_edges = xrealloc (crossing_edges, 1258169689Skan (*max_idx) * sizeof (edge)); 1259169689Skan } 1260169689Skan crossing_edges[i++] = e; 1261169689Skan } 1262169689Skan else 1263169689Skan e->flags &= ~EDGE_CROSSING; 1264169689Skan } 1265169689Skan *n_crossing_edges = i; 1266169689Skan} 1267169689Skan 1268169689Skan/* If any destination of a crossing edge does not have a label, add label; 1269169689Skan Convert any fall-through crossing edges (for blocks that do not contain 1270169689Skan a jump) to unconditional jumps. */ 1271169689Skan 1272169689Skanstatic void 1273169689Skanadd_labels_and_missing_jumps (edge *crossing_edges, int n_crossing_edges) 1274169689Skan{ 1275169689Skan int i; 1276169689Skan basic_block src; 1277169689Skan basic_block dest; 1278169689Skan rtx label; 1279169689Skan rtx barrier; 1280169689Skan rtx new_jump; 1281169689Skan 1282169689Skan for (i=0; i < n_crossing_edges; i++) 1283169689Skan { 1284169689Skan if (crossing_edges[i]) 1285169689Skan { 1286169689Skan src = crossing_edges[i]->src; 1287169689Skan dest = crossing_edges[i]->dest; 1288169689Skan 1289169689Skan /* Make sure dest has a label. */ 1290169689Skan 1291169689Skan if (dest && (dest != EXIT_BLOCK_PTR)) 1292169689Skan { 1293169689Skan label = block_label (dest); 1294169689Skan 1295169689Skan /* Make sure source block ends with a jump. */ 1296169689Skan 1297169689Skan if (src && (src != ENTRY_BLOCK_PTR)) 1298169689Skan { 1299169689Skan if (!JUMP_P (BB_END (src))) 1300169689Skan /* bb just falls through. */ 1301169689Skan { 1302169689Skan /* make sure there's only one successor */ 1303169689Skan gcc_assert (single_succ_p (src)); 1304169689Skan 1305169689Skan /* Find label in dest block. */ 1306169689Skan label = block_label (dest); 1307169689Skan 1308169689Skan new_jump = emit_jump_insn_after (gen_jump (label), 1309169689Skan BB_END (src)); 1310169689Skan barrier = emit_barrier_after (new_jump); 1311169689Skan JUMP_LABEL (new_jump) = label; 1312169689Skan LABEL_NUSES (label) += 1; 1313169689Skan src->il.rtl->footer = unlink_insn_chain (barrier, barrier); 1314169689Skan /* Mark edge as non-fallthru. */ 1315169689Skan crossing_edges[i]->flags &= ~EDGE_FALLTHRU; 1316169689Skan } /* end: 'if (GET_CODE ... ' */ 1317169689Skan } /* end: 'if (src && src->index...' */ 1318169689Skan } /* end: 'if (dest && dest->index...' */ 1319169689Skan } /* end: 'if (crossing_edges[i]...' */ 1320169689Skan } /* end for loop */ 1321169689Skan} 1322169689Skan 1323169689Skan/* Find any bb's where the fall-through edge is a crossing edge (note that 1324169689Skan these bb's must also contain a conditional jump; we've already 1325169689Skan dealt with fall-through edges for blocks that didn't have a 1326169689Skan conditional jump in the call to add_labels_and_missing_jumps). 1327169689Skan Convert the fall-through edge to non-crossing edge by inserting a 1328169689Skan new bb to fall-through into. The new bb will contain an 1329169689Skan unconditional jump (crossing edge) to the original fall through 1330169689Skan destination. */ 1331169689Skan 1332169689Skanstatic void 1333169689Skanfix_up_fall_thru_edges (void) 1334169689Skan{ 1335169689Skan basic_block cur_bb; 1336169689Skan basic_block new_bb; 1337169689Skan edge succ1; 1338169689Skan edge succ2; 1339169689Skan edge fall_thru; 1340169689Skan edge cond_jump = NULL; 1341169689Skan edge e; 1342169689Skan bool cond_jump_crosses; 1343169689Skan int invert_worked; 1344169689Skan rtx old_jump; 1345169689Skan rtx fall_thru_label; 1346169689Skan rtx barrier; 1347169689Skan 1348169689Skan FOR_EACH_BB (cur_bb) 1349169689Skan { 1350169689Skan fall_thru = NULL; 1351169689Skan if (EDGE_COUNT (cur_bb->succs) > 0) 1352169689Skan succ1 = EDGE_SUCC (cur_bb, 0); 1353169689Skan else 1354169689Skan succ1 = NULL; 1355169689Skan 1356169689Skan if (EDGE_COUNT (cur_bb->succs) > 1) 1357169689Skan succ2 = EDGE_SUCC (cur_bb, 1); 1358169689Skan else 1359169689Skan succ2 = NULL; 1360169689Skan 1361169689Skan /* Find the fall-through edge. */ 1362169689Skan 1363169689Skan if (succ1 1364169689Skan && (succ1->flags & EDGE_FALLTHRU)) 1365169689Skan { 1366169689Skan fall_thru = succ1; 1367169689Skan cond_jump = succ2; 1368169689Skan } 1369169689Skan else if (succ2 1370169689Skan && (succ2->flags & EDGE_FALLTHRU)) 1371169689Skan { 1372169689Skan fall_thru = succ2; 1373169689Skan cond_jump = succ1; 1374169689Skan } 1375169689Skan 1376169689Skan if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR)) 1377169689Skan { 1378169689Skan /* Check to see if the fall-thru edge is a crossing edge. */ 1379169689Skan 1380169689Skan if (fall_thru->flags & EDGE_CROSSING) 1381169689Skan { 1382169689Skan /* The fall_thru edge crosses; now check the cond jump edge, if 1383169689Skan it exists. */ 1384169689Skan 1385169689Skan cond_jump_crosses = true; 1386169689Skan invert_worked = 0; 1387169689Skan old_jump = BB_END (cur_bb); 1388169689Skan 1389169689Skan /* Find the jump instruction, if there is one. */ 1390169689Skan 1391169689Skan if (cond_jump) 1392169689Skan { 1393169689Skan if (!(cond_jump->flags & EDGE_CROSSING)) 1394169689Skan cond_jump_crosses = false; 1395169689Skan 1396169689Skan /* We know the fall-thru edge crosses; if the cond 1397169689Skan jump edge does NOT cross, and its destination is the 1398169689Skan next block in the bb order, invert the jump 1399169689Skan (i.e. fix it so the fall thru does not cross and 1400169689Skan the cond jump does). */ 1401169689Skan 1402169689Skan if (!cond_jump_crosses 1403169689Skan && cur_bb->aux == cond_jump->dest) 1404169689Skan { 1405169689Skan /* Find label in fall_thru block. We've already added 1406169689Skan any missing labels, so there must be one. */ 1407169689Skan 1408169689Skan fall_thru_label = block_label (fall_thru->dest); 1409169689Skan 1410169689Skan if (old_jump && fall_thru_label) 1411169689Skan invert_worked = invert_jump (old_jump, 1412169689Skan fall_thru_label,0); 1413169689Skan if (invert_worked) 1414169689Skan { 1415169689Skan fall_thru->flags &= ~EDGE_FALLTHRU; 1416169689Skan cond_jump->flags |= EDGE_FALLTHRU; 1417169689Skan update_br_prob_note (cur_bb); 1418169689Skan e = fall_thru; 1419169689Skan fall_thru = cond_jump; 1420169689Skan cond_jump = e; 1421169689Skan cond_jump->flags |= EDGE_CROSSING; 1422169689Skan fall_thru->flags &= ~EDGE_CROSSING; 1423169689Skan } 1424169689Skan } 1425169689Skan } 1426169689Skan 1427169689Skan if (cond_jump_crosses || !invert_worked) 1428169689Skan { 1429169689Skan /* This is the case where both edges out of the basic 1430169689Skan block are crossing edges. Here we will fix up the 1431169689Skan fall through edge. The jump edge will be taken care 1432169689Skan of later. */ 1433169689Skan 1434169689Skan new_bb = force_nonfallthru (fall_thru); 1435169689Skan 1436169689Skan if (new_bb) 1437169689Skan { 1438169689Skan new_bb->aux = cur_bb->aux; 1439169689Skan cur_bb->aux = new_bb; 1440169689Skan 1441169689Skan /* Make sure new fall-through bb is in same 1442169689Skan partition as bb it's falling through from. */ 1443169689Skan 1444169689Skan BB_COPY_PARTITION (new_bb, cur_bb); 1445169689Skan single_succ_edge (new_bb)->flags |= EDGE_CROSSING; 1446169689Skan } 1447169689Skan 1448169689Skan /* Add barrier after new jump */ 1449169689Skan 1450169689Skan if (new_bb) 1451169689Skan { 1452169689Skan barrier = emit_barrier_after (BB_END (new_bb)); 1453169689Skan new_bb->il.rtl->footer = unlink_insn_chain (barrier, 1454169689Skan barrier); 1455169689Skan } 1456169689Skan else 1457169689Skan { 1458169689Skan barrier = emit_barrier_after (BB_END (cur_bb)); 1459169689Skan cur_bb->il.rtl->footer = unlink_insn_chain (barrier, 1460169689Skan barrier); 1461169689Skan } 1462169689Skan } 1463169689Skan } 1464169689Skan } 1465169689Skan } 1466169689Skan} 1467169689Skan 1468169689Skan/* This function checks the destination blockof a "crossing jump" to 1469169689Skan see if it has any crossing predecessors that begin with a code label 1470169689Skan and end with an unconditional jump. If so, it returns that predecessor 1471169689Skan block. (This is to avoid creating lots of new basic blocks that all 1472169689Skan contain unconditional jumps to the same destination). */ 1473169689Skan 1474169689Skanstatic basic_block 1475169689Skanfind_jump_block (basic_block jump_dest) 1476169689Skan{ 1477169689Skan basic_block source_bb = NULL; 1478169689Skan edge e; 1479169689Skan rtx insn; 1480169689Skan edge_iterator ei; 1481169689Skan 1482169689Skan FOR_EACH_EDGE (e, ei, jump_dest->preds) 1483169689Skan if (e->flags & EDGE_CROSSING) 1484169689Skan { 1485169689Skan basic_block src = e->src; 1486169689Skan 1487169689Skan /* Check each predecessor to see if it has a label, and contains 1488169689Skan only one executable instruction, which is an unconditional jump. 1489169689Skan If so, we can use it. */ 1490169689Skan 1491169689Skan if (LABEL_P (BB_HEAD (src))) 1492169689Skan for (insn = BB_HEAD (src); 1493169689Skan !INSN_P (insn) && insn != NEXT_INSN (BB_END (src)); 1494169689Skan insn = NEXT_INSN (insn)) 1495169689Skan { 1496169689Skan if (INSN_P (insn) 1497169689Skan && insn == BB_END (src) 1498169689Skan && JUMP_P (insn) 1499169689Skan && !any_condjump_p (insn)) 1500169689Skan { 1501169689Skan source_bb = src; 1502169689Skan break; 1503169689Skan } 1504169689Skan } 1505169689Skan 1506169689Skan if (source_bb) 1507169689Skan break; 1508169689Skan } 1509169689Skan 1510169689Skan return source_bb; 1511169689Skan} 1512169689Skan 1513169689Skan/* Find all BB's with conditional jumps that are crossing edges; 1514169689Skan insert a new bb and make the conditional jump branch to the new 1515169689Skan bb instead (make the new bb same color so conditional branch won't 1516169689Skan be a 'crossing' edge). Insert an unconditional jump from the 1517169689Skan new bb to the original destination of the conditional jump. */ 1518169689Skan 1519169689Skanstatic void 1520169689Skanfix_crossing_conditional_branches (void) 1521169689Skan{ 1522169689Skan basic_block cur_bb; 1523169689Skan basic_block new_bb; 1524169689Skan basic_block last_bb; 1525169689Skan basic_block dest; 1526169689Skan basic_block prev_bb; 1527169689Skan edge succ1; 1528169689Skan edge succ2; 1529169689Skan edge crossing_edge; 1530169689Skan edge new_edge; 1531169689Skan rtx old_jump; 1532169689Skan rtx set_src; 1533169689Skan rtx old_label = NULL_RTX; 1534169689Skan rtx new_label; 1535169689Skan rtx new_jump; 1536169689Skan rtx barrier; 1537169689Skan 1538169689Skan last_bb = EXIT_BLOCK_PTR->prev_bb; 1539169689Skan 1540169689Skan FOR_EACH_BB (cur_bb) 1541169689Skan { 1542169689Skan crossing_edge = NULL; 1543169689Skan if (EDGE_COUNT (cur_bb->succs) > 0) 1544169689Skan succ1 = EDGE_SUCC (cur_bb, 0); 1545169689Skan else 1546169689Skan succ1 = NULL; 1547169689Skan 1548169689Skan if (EDGE_COUNT (cur_bb->succs) > 1) 1549169689Skan succ2 = EDGE_SUCC (cur_bb, 1); 1550169689Skan else 1551169689Skan succ2 = NULL; 1552169689Skan 1553169689Skan /* We already took care of fall-through edges, so only one successor 1554169689Skan can be a crossing edge. */ 1555169689Skan 1556169689Skan if (succ1 && (succ1->flags & EDGE_CROSSING)) 1557169689Skan crossing_edge = succ1; 1558169689Skan else if (succ2 && (succ2->flags & EDGE_CROSSING)) 1559169689Skan crossing_edge = succ2; 1560169689Skan 1561169689Skan if (crossing_edge) 1562169689Skan { 1563169689Skan old_jump = BB_END (cur_bb); 1564169689Skan 1565169689Skan /* Check to make sure the jump instruction is a 1566169689Skan conditional jump. */ 1567169689Skan 1568169689Skan set_src = NULL_RTX; 1569169689Skan 1570169689Skan if (any_condjump_p (old_jump)) 1571169689Skan { 1572169689Skan if (GET_CODE (PATTERN (old_jump)) == SET) 1573169689Skan set_src = SET_SRC (PATTERN (old_jump)); 1574169689Skan else if (GET_CODE (PATTERN (old_jump)) == PARALLEL) 1575169689Skan { 1576169689Skan set_src = XVECEXP (PATTERN (old_jump), 0,0); 1577169689Skan if (GET_CODE (set_src) == SET) 1578169689Skan set_src = SET_SRC (set_src); 1579169689Skan else 1580169689Skan set_src = NULL_RTX; 1581169689Skan } 1582169689Skan } 1583169689Skan 1584169689Skan if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE)) 1585169689Skan { 1586169689Skan if (GET_CODE (XEXP (set_src, 1)) == PC) 1587169689Skan old_label = XEXP (set_src, 2); 1588169689Skan else if (GET_CODE (XEXP (set_src, 2)) == PC) 1589169689Skan old_label = XEXP (set_src, 1); 1590169689Skan 1591169689Skan /* Check to see if new bb for jumping to that dest has 1592169689Skan already been created; if so, use it; if not, create 1593169689Skan a new one. */ 1594169689Skan 1595169689Skan new_bb = find_jump_block (crossing_edge->dest); 1596169689Skan 1597169689Skan if (new_bb) 1598169689Skan new_label = block_label (new_bb); 1599169689Skan else 1600169689Skan { 1601169689Skan /* Create new basic block to be dest for 1602169689Skan conditional jump. */ 1603169689Skan 1604169689Skan new_bb = create_basic_block (NULL, NULL, last_bb); 1605169689Skan new_bb->aux = last_bb->aux; 1606169689Skan last_bb->aux = new_bb; 1607169689Skan prev_bb = last_bb; 1608169689Skan last_bb = new_bb; 1609169689Skan 1610169689Skan /* Update register liveness information. */ 1611169689Skan 1612169689Skan new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (®_obstack); 1613169689Skan new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (®_obstack); 1614169689Skan COPY_REG_SET (new_bb->il.rtl->global_live_at_end, 1615169689Skan prev_bb->il.rtl->global_live_at_end); 1616169689Skan COPY_REG_SET (new_bb->il.rtl->global_live_at_start, 1617169689Skan prev_bb->il.rtl->global_live_at_end); 1618169689Skan 1619169689Skan /* Put appropriate instructions in new bb. */ 1620169689Skan 1621169689Skan new_label = gen_label_rtx (); 1622169689Skan emit_label_before (new_label, BB_HEAD (new_bb)); 1623169689Skan BB_HEAD (new_bb) = new_label; 1624169689Skan 1625169689Skan if (GET_CODE (old_label) == LABEL_REF) 1626169689Skan { 1627169689Skan old_label = JUMP_LABEL (old_jump); 1628169689Skan new_jump = emit_jump_insn_after (gen_jump 1629169689Skan (old_label), 1630169689Skan BB_END (new_bb)); 1631169689Skan } 1632169689Skan else 1633169689Skan { 1634169689Skan gcc_assert (HAVE_return 1635169689Skan && GET_CODE (old_label) == RETURN); 1636169689Skan new_jump = emit_jump_insn_after (gen_return (), 1637169689Skan BB_END (new_bb)); 1638169689Skan } 1639169689Skan 1640169689Skan barrier = emit_barrier_after (new_jump); 1641169689Skan JUMP_LABEL (new_jump) = old_label; 1642169689Skan new_bb->il.rtl->footer = unlink_insn_chain (barrier, 1643169689Skan barrier); 1644169689Skan 1645169689Skan /* Make sure new bb is in same partition as source 1646169689Skan of conditional branch. */ 1647169689Skan BB_COPY_PARTITION (new_bb, cur_bb); 1648169689Skan } 1649169689Skan 1650169689Skan /* Make old jump branch to new bb. */ 1651169689Skan 1652169689Skan redirect_jump (old_jump, new_label, 0); 1653169689Skan 1654169689Skan /* Remove crossing_edge as predecessor of 'dest'. */ 1655169689Skan 1656169689Skan dest = crossing_edge->dest; 1657169689Skan 1658169689Skan redirect_edge_succ (crossing_edge, new_bb); 1659169689Skan 1660169689Skan /* Make a new edge from new_bb to old dest; new edge 1661169689Skan will be a successor for new_bb and a predecessor 1662169689Skan for 'dest'. */ 1663169689Skan 1664169689Skan if (EDGE_COUNT (new_bb->succs) == 0) 1665169689Skan new_edge = make_edge (new_bb, dest, 0); 1666169689Skan else 1667169689Skan new_edge = EDGE_SUCC (new_bb, 0); 1668169689Skan 1669169689Skan crossing_edge->flags &= ~EDGE_CROSSING; 1670169689Skan new_edge->flags |= EDGE_CROSSING; 1671169689Skan } 1672169689Skan } 1673169689Skan } 1674169689Skan} 1675169689Skan 1676169689Skan/* Find any unconditional branches that cross between hot and cold 1677169689Skan sections. Convert them into indirect jumps instead. */ 1678169689Skan 1679169689Skanstatic void 1680169689Skanfix_crossing_unconditional_branches (void) 1681169689Skan{ 1682169689Skan basic_block cur_bb; 1683169689Skan rtx last_insn; 1684169689Skan rtx label; 1685169689Skan rtx label_addr; 1686169689Skan rtx indirect_jump_sequence; 1687169689Skan rtx jump_insn = NULL_RTX; 1688169689Skan rtx new_reg; 1689169689Skan rtx cur_insn; 1690169689Skan edge succ; 1691169689Skan 1692169689Skan FOR_EACH_BB (cur_bb) 1693169689Skan { 1694169689Skan last_insn = BB_END (cur_bb); 1695169689Skan 1696169689Skan if (EDGE_COUNT (cur_bb->succs) < 1) 1697169689Skan continue; 1698169689Skan 1699169689Skan succ = EDGE_SUCC (cur_bb, 0); 1700169689Skan 1701169689Skan /* Check to see if bb ends in a crossing (unconditional) jump. At 1702169689Skan this point, no crossing jumps should be conditional. */ 1703169689Skan 1704169689Skan if (JUMP_P (last_insn) 1705169689Skan && (succ->flags & EDGE_CROSSING)) 1706169689Skan { 1707169689Skan rtx label2, table; 1708169689Skan 1709169689Skan gcc_assert (!any_condjump_p (last_insn)); 1710169689Skan 1711169689Skan /* Make sure the jump is not already an indirect or table jump. */ 1712169689Skan 1713169689Skan if (!computed_jump_p (last_insn) 1714169689Skan && !tablejump_p (last_insn, &label2, &table)) 1715169689Skan { 1716169689Skan /* We have found a "crossing" unconditional branch. Now 1717169689Skan we must convert it to an indirect jump. First create 1718169689Skan reference of label, as target for jump. */ 1719169689Skan 1720169689Skan label = JUMP_LABEL (last_insn); 1721169689Skan label_addr = gen_rtx_LABEL_REF (Pmode, label); 1722169689Skan LABEL_NUSES (label) += 1; 1723169689Skan 1724169689Skan /* Get a register to use for the indirect jump. */ 1725169689Skan 1726169689Skan new_reg = gen_reg_rtx (Pmode); 1727169689Skan 1728169689Skan /* Generate indirect the jump sequence. */ 1729169689Skan 1730169689Skan start_sequence (); 1731169689Skan emit_move_insn (new_reg, label_addr); 1732169689Skan emit_indirect_jump (new_reg); 1733169689Skan indirect_jump_sequence = get_insns (); 1734169689Skan end_sequence (); 1735169689Skan 1736169689Skan /* Make sure every instruction in the new jump sequence has 1737169689Skan its basic block set to be cur_bb. */ 1738169689Skan 1739169689Skan for (cur_insn = indirect_jump_sequence; cur_insn; 1740169689Skan cur_insn = NEXT_INSN (cur_insn)) 1741169689Skan { 1742169689Skan if (!BARRIER_P (cur_insn)) 1743169689Skan BLOCK_FOR_INSN (cur_insn) = cur_bb; 1744169689Skan if (JUMP_P (cur_insn)) 1745169689Skan jump_insn = cur_insn; 1746169689Skan } 1747169689Skan 1748169689Skan /* Insert the new (indirect) jump sequence immediately before 1749169689Skan the unconditional jump, then delete the unconditional jump. */ 1750169689Skan 1751169689Skan emit_insn_before (indirect_jump_sequence, last_insn); 1752169689Skan delete_insn (last_insn); 1753169689Skan 1754169689Skan /* Make BB_END for cur_bb be the jump instruction (NOT the 1755169689Skan barrier instruction at the end of the sequence...). */ 1756169689Skan 1757169689Skan BB_END (cur_bb) = jump_insn; 1758169689Skan } 1759169689Skan } 1760169689Skan } 1761169689Skan} 1762169689Skan 1763169689Skan/* Add REG_CROSSING_JUMP note to all crossing jump insns. */ 1764169689Skan 1765169689Skanstatic void 1766169689Skanadd_reg_crossing_jump_notes (void) 1767169689Skan{ 1768169689Skan basic_block bb; 1769169689Skan edge e; 1770169689Skan edge_iterator ei; 1771169689Skan 1772169689Skan FOR_EACH_BB (bb) 1773169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1774169689Skan if ((e->flags & EDGE_CROSSING) 1775169689Skan && JUMP_P (BB_END (e->src))) 1776169689Skan REG_NOTES (BB_END (e->src)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP, 1777169689Skan NULL_RTX, 1778169689Skan REG_NOTES (BB_END 1779169689Skan (e->src))); 1780169689Skan} 1781169689Skan 1782169689Skan/* Hot and cold basic blocks are partitioned and put in separate 1783169689Skan sections of the .o file, to reduce paging and improve cache 1784169689Skan performance (hopefully). This can result in bits of code from the 1785169689Skan same function being widely separated in the .o file. However this 1786169689Skan is not obvious to the current bb structure. Therefore we must take 1787169689Skan care to ensure that: 1). There are no fall_thru edges that cross 1788169689Skan between sections; 2). For those architectures which have "short" 1789169689Skan conditional branches, all conditional branches that attempt to 1790169689Skan cross between sections are converted to unconditional branches; 1791169689Skan and, 3). For those architectures which have "short" unconditional 1792169689Skan branches, all unconditional branches that attempt to cross between 1793169689Skan sections are converted to indirect jumps. 1794169689Skan 1795169689Skan The code for fixing up fall_thru edges that cross between hot and 1796169689Skan cold basic blocks does so by creating new basic blocks containing 1797169689Skan unconditional branches to the appropriate label in the "other" 1798169689Skan section. The new basic block is then put in the same (hot or cold) 1799169689Skan section as the original conditional branch, and the fall_thru edge 1800169689Skan is modified to fall into the new basic block instead. By adding 1801169689Skan this level of indirection we end up with only unconditional branches 1802169689Skan crossing between hot and cold sections. 1803169689Skan 1804169689Skan Conditional branches are dealt with by adding a level of indirection. 1805169689Skan A new basic block is added in the same (hot/cold) section as the 1806169689Skan conditional branch, and the conditional branch is retargeted to the 1807169689Skan new basic block. The new basic block contains an unconditional branch 1808169689Skan to the original target of the conditional branch (in the other section). 1809169689Skan 1810169689Skan Unconditional branches are dealt with by converting them into 1811169689Skan indirect jumps. */ 1812169689Skan 1813169689Skanstatic void 1814169689Skanfix_edges_for_rarely_executed_code (edge *crossing_edges, 1815169689Skan int n_crossing_edges) 1816169689Skan{ 1817169689Skan /* Make sure the source of any crossing edge ends in a jump and the 1818169689Skan destination of any crossing edge has a label. */ 1819169689Skan 1820169689Skan add_labels_and_missing_jumps (crossing_edges, n_crossing_edges); 1821169689Skan 1822169689Skan /* Convert all crossing fall_thru edges to non-crossing fall 1823169689Skan thrus to unconditional jumps (that jump to the original fall 1824169689Skan thru dest). */ 1825169689Skan 1826169689Skan fix_up_fall_thru_edges (); 1827169689Skan 1828169689Skan /* If the architecture does not have conditional branches that can 1829169689Skan span all of memory, convert crossing conditional branches into 1830169689Skan crossing unconditional branches. */ 1831169689Skan 1832169689Skan if (!HAS_LONG_COND_BRANCH) 1833169689Skan fix_crossing_conditional_branches (); 1834169689Skan 1835169689Skan /* If the architecture does not have unconditional branches that 1836169689Skan can span all of memory, convert crossing unconditional branches 1837169689Skan into indirect jumps. Since adding an indirect jump also adds 1838169689Skan a new register usage, update the register usage information as 1839169689Skan well. */ 1840169689Skan 1841169689Skan if (!HAS_LONG_UNCOND_BRANCH) 1842169689Skan { 1843169689Skan fix_crossing_unconditional_branches (); 1844169689Skan reg_scan (get_insns(), max_reg_num ()); 1845169689Skan } 1846169689Skan 1847169689Skan add_reg_crossing_jump_notes (); 1848169689Skan} 1849169689Skan 1850169689Skan/* Verify, in the basic block chain, that there is at most one switch 1851169689Skan between hot/cold partitions. This is modelled on 1852169689Skan rtl_verify_flow_info_1, but it cannot go inside that function 1853169689Skan because this condition will not be true until after 1854169689Skan reorder_basic_blocks is called. */ 1855169689Skan 1856169689Skanstatic void 1857169689Skanverify_hot_cold_block_grouping (void) 1858169689Skan{ 1859169689Skan basic_block bb; 1860169689Skan int err = 0; 1861169689Skan bool switched_sections = false; 1862169689Skan int current_partition = 0; 1863169689Skan 1864169689Skan FOR_EACH_BB (bb) 1865169689Skan { 1866169689Skan if (!current_partition) 1867169689Skan current_partition = BB_PARTITION (bb); 1868169689Skan if (BB_PARTITION (bb) != current_partition) 1869169689Skan { 1870169689Skan if (switched_sections) 1871169689Skan { 1872169689Skan error ("multiple hot/cold transitions found (bb %i)", 1873169689Skan bb->index); 1874169689Skan err = 1; 1875169689Skan } 1876169689Skan else 1877169689Skan { 1878169689Skan switched_sections = true; 1879169689Skan current_partition = BB_PARTITION (bb); 1880169689Skan } 1881169689Skan } 1882169689Skan } 1883169689Skan 1884169689Skan gcc_assert(!err); 1885169689Skan} 1886169689Skan 1887132718Skan/* Reorder basic blocks. The main entry point to this file. FLAGS is 1888132718Skan the set of flags to pass to cfg_layout_initialize(). */ 1889132718Skan 189090075Sobrienvoid 1891132718Skanreorder_basic_blocks (unsigned int flags) 189290075Sobrien{ 1893132718Skan int n_traces; 1894132718Skan int i; 1895132718Skan struct trace *traces; 1896132718Skan 1897169689Skan if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1) 189890075Sobrien return; 189990075Sobrien 1900169689Skan if (targetm.cannot_modify_jumps_p ()) 190196263Sobrien return; 190296263Sobrien 1903132718Skan cfg_layout_initialize (flags); 190490075Sobrien 1905132718Skan set_edge_can_fallthru_flag (); 1906132718Skan mark_dfs_back_edges (); 1907132718Skan 1908132718Skan /* We are estimating the length of uncond jump insn only once since the code 1909132718Skan for getting the insn length always returns the minimal length now. */ 1910132718Skan if (uncond_jump_length == 0) 1911132718Skan uncond_jump_length = get_uncond_jump_length (); 1912132718Skan 1913132718Skan /* We need to know some information for each basic block. */ 1914132718Skan array_size = GET_ARRAY_SIZE (last_basic_block); 1915169689Skan bbd = XNEWVEC (bbro_basic_block_data, array_size); 1916132718Skan for (i = 0; i < array_size; i++) 1917132718Skan { 1918132718Skan bbd[i].start_of_trace = -1; 1919169689Skan bbd[i].in_trace = -1; 1920132718Skan bbd[i].end_of_trace = -1; 1921132718Skan bbd[i].heap = NULL; 1922132718Skan bbd[i].node = NULL; 1923132718Skan } 1924132718Skan 1925169689Skan traces = XNEWVEC (struct trace, n_basic_blocks); 1926132718Skan n_traces = 0; 1927132718Skan find_traces (&n_traces, traces); 1928132718Skan connect_traces (n_traces, traces); 1929132718Skan FREE (traces); 1930132718Skan FREE (bbd); 1931132718Skan 1932169689Skan if (dump_file) 1933169689Skan dump_flow_info (dump_file, dump_flags); 193490075Sobrien 193590075Sobrien cfg_layout_finalize (); 1936169689Skan if (flag_reorder_blocks_and_partition) 1937169689Skan verify_hot_cold_block_grouping (); 1938169689Skan} 1939132718Skan 1940169689Skan/* Determine which partition the first basic block in the function 1941169689Skan belongs to, then find the first basic block in the current function 1942169689Skan that belongs to a different section, and insert a 1943169689Skan NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the 1944169689Skan instruction stream. When writing out the assembly code, 1945169689Skan encountering this note will make the compiler switch between the 1946169689Skan hot and cold text sections. */ 1947169689Skan 1948169689Skanstatic void 1949169689Skaninsert_section_boundary_note (void) 1950169689Skan{ 1951169689Skan basic_block bb; 1952169689Skan rtx new_note; 1953169689Skan int first_partition = 0; 1954169689Skan 1955169689Skan if (flag_reorder_blocks_and_partition) 1956169689Skan FOR_EACH_BB (bb) 1957169689Skan { 1958169689Skan if (!first_partition) 1959169689Skan first_partition = BB_PARTITION (bb); 1960169689Skan if (BB_PARTITION (bb) != first_partition) 1961169689Skan { 1962169689Skan new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS, 1963169689Skan BB_HEAD (bb)); 1964169689Skan break; 1965169689Skan } 1966169689Skan } 196790075Sobrien} 1968169689Skan 1969169689Skan/* Duplicate the blocks containing computed gotos. This basically unfactors 1970169689Skan computed gotos that were factored early on in the compilation process to 1971169689Skan speed up edge based data flow. We used to not unfactoring them again, 1972169689Skan which can seriously pessimize code with many computed jumps in the source 1973169689Skan code, such as interpreters. See e.g. PR15242. */ 1974169689Skan 1975169689Skanstatic bool 1976169689Skangate_duplicate_computed_gotos (void) 1977169689Skan{ 1978169689Skan return (optimize > 0 && flag_expensive_optimizations && !optimize_size); 1979169689Skan} 1980169689Skan 1981169689Skan 1982169689Skanstatic unsigned int 1983169689Skanduplicate_computed_gotos (void) 1984169689Skan{ 1985169689Skan basic_block bb, new_bb; 1986169689Skan bitmap candidates; 1987169689Skan int max_size; 1988169689Skan 1989169689Skan if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1) 1990169689Skan return 0; 1991169689Skan 1992169689Skan if (targetm.cannot_modify_jumps_p ()) 1993169689Skan return 0; 1994169689Skan 1995169689Skan cfg_layout_initialize (0); 1996169689Skan 1997169689Skan /* We are estimating the length of uncond jump insn only once 1998169689Skan since the code for getting the insn length always returns 1999169689Skan the minimal length now. */ 2000169689Skan if (uncond_jump_length == 0) 2001169689Skan uncond_jump_length = get_uncond_jump_length (); 2002169689Skan 2003169689Skan max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS); 2004169689Skan candidates = BITMAP_ALLOC (NULL); 2005169689Skan 2006169689Skan /* Look for blocks that end in a computed jump, and see if such blocks 2007169689Skan are suitable for unfactoring. If a block is a candidate for unfactoring, 2008169689Skan mark it in the candidates. */ 2009169689Skan FOR_EACH_BB (bb) 2010169689Skan { 2011169689Skan rtx insn; 2012169689Skan edge e; 2013169689Skan edge_iterator ei; 2014169689Skan int size, all_flags; 2015169689Skan 2016169689Skan /* Build the reorder chain for the original order of blocks. */ 2017169689Skan if (bb->next_bb != EXIT_BLOCK_PTR) 2018169689Skan bb->aux = bb->next_bb; 2019169689Skan 2020169689Skan /* Obviously the block has to end in a computed jump. */ 2021169689Skan if (!computed_jump_p (BB_END (bb))) 2022169689Skan continue; 2023169689Skan 2024169689Skan /* Only consider blocks that can be duplicated. */ 2025169689Skan if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX) 2026169689Skan || !can_duplicate_block_p (bb)) 2027169689Skan continue; 2028169689Skan 2029169689Skan /* Make sure that the block is small enough. */ 2030169689Skan size = 0; 2031169689Skan FOR_BB_INSNS (bb, insn) 2032169689Skan if (INSN_P (insn)) 2033169689Skan { 2034169689Skan size += get_attr_min_length (insn); 2035169689Skan if (size > max_size) 2036169689Skan break; 2037169689Skan } 2038169689Skan if (size > max_size) 2039169689Skan continue; 2040169689Skan 2041169689Skan /* Final check: there must not be any incoming abnormal edges. */ 2042169689Skan all_flags = 0; 2043169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2044169689Skan all_flags |= e->flags; 2045169689Skan if (all_flags & EDGE_COMPLEX) 2046169689Skan continue; 2047169689Skan 2048169689Skan bitmap_set_bit (candidates, bb->index); 2049169689Skan } 2050169689Skan 2051169689Skan /* Nothing to do if there is no computed jump here. */ 2052169689Skan if (bitmap_empty_p (candidates)) 2053169689Skan goto done; 2054169689Skan 2055169689Skan /* Duplicate computed gotos. */ 2056169689Skan FOR_EACH_BB (bb) 2057169689Skan { 2058169689Skan if (bb->il.rtl->visited) 2059169689Skan continue; 2060169689Skan 2061169689Skan bb->il.rtl->visited = 1; 2062169689Skan 2063169689Skan /* BB must have one outgoing edge. That edge must not lead to 2064169689Skan the exit block or the next block. 2065169689Skan The destination must have more than one predecessor. */ 2066169689Skan if (!single_succ_p (bb) 2067169689Skan || single_succ (bb) == EXIT_BLOCK_PTR 2068169689Skan || single_succ (bb) == bb->next_bb 2069169689Skan || single_pred_p (single_succ (bb))) 2070169689Skan continue; 2071169689Skan 2072169689Skan /* The successor block has to be a duplication candidate. */ 2073169689Skan if (!bitmap_bit_p (candidates, single_succ (bb)->index)) 2074169689Skan continue; 2075169689Skan 2076169689Skan new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb); 2077169689Skan new_bb->aux = bb->aux; 2078169689Skan bb->aux = new_bb; 2079169689Skan new_bb->il.rtl->visited = 1; 2080169689Skan } 2081169689Skan 2082169689Skandone: 2083169689Skan cfg_layout_finalize (); 2084169689Skan 2085169689Skan BITMAP_FREE (candidates); 2086169689Skan return 0; 2087169689Skan} 2088169689Skan 2089169689Skanstruct tree_opt_pass pass_duplicate_computed_gotos = 2090169689Skan{ 2091169689Skan "compgotos", /* name */ 2092169689Skan gate_duplicate_computed_gotos, /* gate */ 2093169689Skan duplicate_computed_gotos, /* execute */ 2094169689Skan NULL, /* sub */ 2095169689Skan NULL, /* next */ 2096169689Skan 0, /* static_pass_number */ 2097169689Skan TV_REORDER_BLOCKS, /* tv_id */ 2098169689Skan 0, /* properties_required */ 2099169689Skan 0, /* properties_provided */ 2100169689Skan 0, /* properties_destroyed */ 2101169689Skan 0, /* todo_flags_start */ 2102169689Skan TODO_dump_func, /* todo_flags_finish */ 2103169689Skan 0 /* letter */ 2104169689Skan}; 2105169689Skan 2106169689Skan 2107169689Skan/* This function is the main 'entrance' for the optimization that 2108169689Skan partitions hot and cold basic blocks into separate sections of the 2109169689Skan .o file (to improve performance and cache locality). Ideally it 2110169689Skan would be called after all optimizations that rearrange the CFG have 2111169689Skan been called. However part of this optimization may introduce new 2112169689Skan register usage, so it must be called before register allocation has 2113169689Skan occurred. This means that this optimization is actually called 2114169689Skan well before the optimization that reorders basic blocks (see 2115169689Skan function above). 2116169689Skan 2117169689Skan This optimization checks the feedback information to determine 2118169689Skan which basic blocks are hot/cold, updates flags on the basic blocks 2119169689Skan to indicate which section they belong in. This information is 2120169689Skan later used for writing out sections in the .o file. Because hot 2121169689Skan and cold sections can be arbitrarily large (within the bounds of 2122169689Skan memory), far beyond the size of a single function, it is necessary 2123169689Skan to fix up all edges that cross section boundaries, to make sure the 2124169689Skan instructions used can actually span the required distance. The 2125169689Skan fixes are described below. 2126169689Skan 2127169689Skan Fall-through edges must be changed into jumps; it is not safe or 2128169689Skan legal to fall through across a section boundary. Whenever a 2129169689Skan fall-through edge crossing a section boundary is encountered, a new 2130169689Skan basic block is inserted (in the same section as the fall-through 2131169689Skan source), and the fall through edge is redirected to the new basic 2132169689Skan block. The new basic block contains an unconditional jump to the 2133169689Skan original fall-through target. (If the unconditional jump is 2134169689Skan insufficient to cross section boundaries, that is dealt with a 2135169689Skan little later, see below). 2136169689Skan 2137169689Skan In order to deal with architectures that have short conditional 2138169689Skan branches (which cannot span all of memory) we take any conditional 2139169689Skan jump that attempts to cross a section boundary and add a level of 2140169689Skan indirection: it becomes a conditional jump to a new basic block, in 2141169689Skan the same section. The new basic block contains an unconditional 2142169689Skan jump to the original target, in the other section. 2143169689Skan 2144169689Skan For those architectures whose unconditional branch is also 2145169689Skan incapable of reaching all of memory, those unconditional jumps are 2146169689Skan converted into indirect jumps, through a register. 2147169689Skan 2148169689Skan IMPORTANT NOTE: This optimization causes some messy interactions 2149169689Skan with the cfg cleanup optimizations; those optimizations want to 2150169689Skan merge blocks wherever possible, and to collapse indirect jump 2151169689Skan sequences (change "A jumps to B jumps to C" directly into "A jumps 2152169689Skan to C"). Those optimizations can undo the jump fixes that 2153169689Skan partitioning is required to make (see above), in order to ensure 2154169689Skan that jumps attempting to cross section boundaries are really able 2155169689Skan to cover whatever distance the jump requires (on many architectures 2156169689Skan conditional or unconditional jumps are not able to reach all of 2157169689Skan memory). Therefore tests have to be inserted into each such 2158169689Skan optimization to make sure that it does not undo stuff necessary to 2159169689Skan cross partition boundaries. This would be much less of a problem 2160169689Skan if we could perform this optimization later in the compilation, but 2161169689Skan unfortunately the fact that we may need to create indirect jumps 2162169689Skan (through registers) requires that this optimization be performed 2163169689Skan before register allocation. */ 2164169689Skan 2165169689Skanstatic void 2166169689Skanpartition_hot_cold_basic_blocks (void) 2167169689Skan{ 2168169689Skan basic_block cur_bb; 2169169689Skan edge *crossing_edges; 2170169689Skan int n_crossing_edges; 2171169689Skan int max_edges = 2 * last_basic_block; 2172169689Skan 2173169689Skan if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1) 2174169689Skan return; 2175169689Skan 2176169689Skan crossing_edges = XCNEWVEC (edge, max_edges); 2177169689Skan 2178169689Skan cfg_layout_initialize (0); 2179169689Skan 2180169689Skan FOR_EACH_BB (cur_bb) 2181169689Skan if (cur_bb->index >= NUM_FIXED_BLOCKS 2182169689Skan && cur_bb->next_bb->index >= NUM_FIXED_BLOCKS) 2183169689Skan cur_bb->aux = cur_bb->next_bb; 2184169689Skan 2185169689Skan find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges, 2186169689Skan &n_crossing_edges, 2187169689Skan &max_edges); 2188169689Skan 2189169689Skan if (n_crossing_edges > 0) 2190169689Skan fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges); 2191169689Skan 2192169689Skan free (crossing_edges); 2193169689Skan 2194169689Skan cfg_layout_finalize(); 2195169689Skan} 2196169689Skan 2197169689Skanstatic bool 2198169689Skangate_handle_reorder_blocks (void) 2199169689Skan{ 2200169689Skan return (optimize > 0); 2201169689Skan} 2202169689Skan 2203169689Skan 2204169689Skan/* Reorder basic blocks. */ 2205169689Skanstatic unsigned int 2206169689Skanrest_of_handle_reorder_blocks (void) 2207169689Skan{ 2208169689Skan bool changed; 2209169689Skan unsigned int liveness_flags; 2210169689Skan 2211169689Skan /* Last attempt to optimize CFG, as scheduling, peepholing and insn 2212169689Skan splitting possibly introduced more crossjumping opportunities. */ 2213169689Skan liveness_flags = (!HAVE_conditional_execution ? CLEANUP_UPDATE_LIFE : 0); 2214169689Skan changed = cleanup_cfg (CLEANUP_EXPENSIVE | liveness_flags); 2215169689Skan 2216169689Skan if (flag_sched2_use_traces && flag_schedule_insns_after_reload) 2217169689Skan { 2218169689Skan timevar_push (TV_TRACER); 2219169689Skan tracer (liveness_flags); 2220169689Skan timevar_pop (TV_TRACER); 2221169689Skan } 2222169689Skan 2223169689Skan if (flag_reorder_blocks || flag_reorder_blocks_and_partition) 2224169689Skan reorder_basic_blocks (liveness_flags); 2225169689Skan if (flag_reorder_blocks || flag_reorder_blocks_and_partition 2226169689Skan || (flag_sched2_use_traces && flag_schedule_insns_after_reload)) 2227169689Skan changed |= cleanup_cfg (CLEANUP_EXPENSIVE | liveness_flags); 2228169689Skan 2229169689Skan /* On conditional execution targets we can not update the life cheaply, so 2230169689Skan we deffer the updating to after both cleanups. This may lose some cases 2231169689Skan but should not be terribly bad. */ 2232169689Skan if (changed && HAVE_conditional_execution) 2233169689Skan update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, 2234169689Skan PROP_DEATH_NOTES); 2235169689Skan 2236169689Skan /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */ 2237169689Skan insert_section_boundary_note (); 2238169689Skan return 0; 2239169689Skan} 2240169689Skan 2241169689Skanstruct tree_opt_pass pass_reorder_blocks = 2242169689Skan{ 2243169689Skan "bbro", /* name */ 2244169689Skan gate_handle_reorder_blocks, /* gate */ 2245169689Skan rest_of_handle_reorder_blocks, /* execute */ 2246169689Skan NULL, /* sub */ 2247169689Skan NULL, /* next */ 2248169689Skan 0, /* static_pass_number */ 2249169689Skan TV_REORDER_BLOCKS, /* tv_id */ 2250169689Skan 0, /* properties_required */ 2251169689Skan 0, /* properties_provided */ 2252169689Skan 0, /* properties_destroyed */ 2253169689Skan 0, /* todo_flags_start */ 2254169689Skan TODO_dump_func, /* todo_flags_finish */ 2255169689Skan 'B' /* letter */ 2256169689Skan}; 2257169689Skan 2258169689Skanstatic bool 2259169689Skangate_handle_partition_blocks (void) 2260169689Skan{ 2261169689Skan /* The optimization to partition hot/cold basic blocks into separate 2262169689Skan sections of the .o file does not work well with linkonce or with 2263169689Skan user defined section attributes. Don't call it if either case 2264169689Skan arises. */ 2265169689Skan 2266169689Skan return (flag_reorder_blocks_and_partition 2267169689Skan && !DECL_ONE_ONLY (current_function_decl) 2268169689Skan && !user_defined_section_attribute); 2269169689Skan} 2270169689Skan 2271169689Skan/* Partition hot and cold basic blocks. */ 2272169689Skanstatic unsigned int 2273169689Skanrest_of_handle_partition_blocks (void) 2274169689Skan{ 2275169689Skan no_new_pseudos = 0; 2276169689Skan partition_hot_cold_basic_blocks (); 2277169689Skan allocate_reg_life_data (); 2278169689Skan update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES, 2279169689Skan PROP_LOG_LINKS | PROP_REG_INFO | PROP_DEATH_NOTES); 2280169689Skan no_new_pseudos = 1; 2281169689Skan return 0; 2282169689Skan} 2283169689Skan 2284169689Skanstruct tree_opt_pass pass_partition_blocks = 2285169689Skan{ 2286169689Skan "bbpart", /* name */ 2287169689Skan gate_handle_partition_blocks, /* gate */ 2288169689Skan rest_of_handle_partition_blocks, /* execute */ 2289169689Skan NULL, /* sub */ 2290169689Skan NULL, /* next */ 2291169689Skan 0, /* static_pass_number */ 2292169689Skan TV_REORDER_BLOCKS, /* tv_id */ 2293169689Skan 0, /* properties_required */ 2294169689Skan 0, /* properties_provided */ 2295169689Skan 0, /* properties_destroyed */ 2296169689Skan 0, /* todo_flags_start */ 2297169689Skan TODO_dump_func, /* todo_flags_finish */ 2298169689Skan 0 /* letter */ 2299169689Skan}; 2300169689Skan 2301169689Skan 2302