Mercurial > hg > CbC > CbC_gcc
annotate gcc/bb-reorder.c @ 67:f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
| author | nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 22 Mar 2011 17:18:12 +0900 |
| parents | b7f97abdc517 |
| children | 04ced10e8804 |
| rev | line source |
|---|---|
| 0 | 1 /* Basic block reordering routines for the GNU compiler. |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
2 Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010 |
| 0 | 3 Free Software Foundation, Inc. |
| 4 | |
| 5 This file is part of GCC. | |
| 6 | |
| 7 GCC is free software; you can redistribute it and/or modify it | |
| 8 under the terms of the GNU General Public License as published by | |
| 9 the Free Software Foundation; either version 3, or (at your option) | |
| 10 any later version. | |
| 11 | |
| 12 GCC is distributed in the hope that it will be useful, but WITHOUT | |
| 13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | |
| 14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public | |
| 15 License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along with GCC; see the file COPYING3. If not see | |
| 19 <http://www.gnu.org/licenses/>. */ | |
| 20 | |
| 21 /* This (greedy) algorithm constructs traces in several rounds. | |
| 22 The construction starts from "seeds". The seed for the first round | |
| 23 is the entry point of function. When there are more than one seed | |
| 24 that one is selected first that has the lowest key in the heap | |
| 25 (see function bb_to_key). Then the algorithm repeatedly adds the most | |
| 26 probable successor to the end of a trace. Finally it connects the traces. | |
| 27 | |
| 28 There are two parameters: Branch Threshold and Exec Threshold. | |
| 29 If the edge to a successor of the actual basic block is lower than | |
| 30 Branch Threshold or the frequency of the successor is lower than | |
| 31 Exec Threshold the successor will be the seed in one of the next rounds. | |
| 32 Each round has these parameters lower than the previous one. | |
| 33 The last round has to have these parameters set to zero | |
| 34 so that the remaining blocks are picked up. | |
| 35 | |
| 36 The algorithm selects the most probable successor from all unvisited | |
| 37 successors and successors that have been added to this trace. | |
| 38 The other successors (that has not been "sent" to the next round) will be | |
| 39 other seeds for this round and the secondary traces will start in them. | |
| 40 If the successor has not been visited in this trace it is added to the trace | |
| 41 (however, there is some heuristic for simple branches). | |
| 42 If the successor has been visited in this trace the loop has been found. | |
| 43 If the loop has many iterations the loop is rotated so that the | |
| 44 source block of the most probable edge going out from the loop | |
| 45 is the last block of the trace. | |
| 46 If the loop has few iterations and there is no edge from the last block of | |
| 47 the loop going out from loop the loop header is duplicated. | |
| 48 Finally, the construction of the trace is terminated. | |
| 49 | |
| 50 When connecting traces it first checks whether there is an edge from the | |
| 51 last block of one trace to the first block of another trace. | |
| 52 When there are still some unconnected traces it checks whether there exists | |
| 53 a basic block BB such that BB is a successor of the last bb of one trace | |
| 54 and BB is a predecessor of the first block of another trace. In this case, | |
| 55 BB is duplicated and the traces are connected through this duplicate. | |
| 56 The rest of traces are simply connected so there will be a jump to the | |
| 57 beginning of the rest of trace. | |
| 58 | |
| 59 | |
| 60 References: | |
| 61 | |
| 62 "Software Trace Cache" | |
| 63 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999 | |
| 64 http://citeseer.nj.nec.com/15361.html | |
| 65 | |
| 66 */ | |
| 67 | |
| 68 #include "config.h" | |
| 69 #include "system.h" | |
| 70 #include "coretypes.h" | |
| 71 #include "tm.h" | |
| 72 #include "rtl.h" | |
| 73 #include "regs.h" | |
| 74 #include "flags.h" | |
| 75 #include "timevar.h" | |
| 76 #include "output.h" | |
| 77 #include "cfglayout.h" | |
| 78 #include "fibheap.h" | |
| 79 #include "target.h" | |
| 80 #include "function.h" | |
| 81 #include "tm_p.h" | |
| 82 #include "obstack.h" | |
| 83 #include "expr.h" | |
| 84 #include "params.h" | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
85 #include "diagnostic-core.h" |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
86 #include "toplev.h" /* user_defined_section_attribute */ |
| 0 | 87 #include "tree-pass.h" |
| 88 #include "df.h" | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
89 #include "bb-reorder.h" |
| 0 | 90 |
| 91 /* The number of rounds. In most cases there will only be 4 rounds, but | |
| 92 when partitioning hot and cold basic blocks into separate sections of | |
| 93 the .o file there will be an extra round.*/ | |
| 94 #define N_ROUNDS 5 | |
| 95 | |
| 96 /* Stubs in case we don't have a return insn. | |
| 97 We have to check at runtime too, not only compiletime. */ | |
| 98 | |
| 99 #ifndef HAVE_return | |
| 100 #define HAVE_return 0 | |
| 101 #define gen_return() NULL_RTX | |
| 102 #endif | |
| 103 | |
| 104 | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
105 struct target_bb_reorder default_target_bb_reorder; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
106 #if SWITCHABLE_TARGET |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
107 struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
108 #endif |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
109 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
110 #define uncond_jump_length \ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
111 (this_target_bb_reorder->x_uncond_jump_length) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
112 |
| 0 | 113 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */ |
| 114 static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0}; | |
| 115 | |
| 116 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */ | |
| 117 static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0}; | |
| 118 | |
| 119 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry | |
| 120 block the edge destination is not duplicated while connecting traces. */ | |
| 121 #define DUPLICATION_THRESHOLD 100 | |
| 122 | |
| 123 /* Structure to hold needed information for each basic block. */ | |
| 124 typedef struct bbro_basic_block_data_def | |
| 125 { | |
| 126 /* Which trace is the bb start of (-1 means it is not a start of a trace). */ | |
| 127 int start_of_trace; | |
| 128 | |
| 129 /* Which trace is the bb end of (-1 means it is not an end of a trace). */ | |
| 130 int end_of_trace; | |
| 131 | |
| 132 /* Which trace is the bb in? */ | |
| 133 int in_trace; | |
| 134 | |
| 135 /* Which heap is BB in (if any)? */ | |
| 136 fibheap_t heap; | |
| 137 | |
| 138 /* Which heap node is BB in (if any)? */ | |
| 139 fibnode_t node; | |
| 140 } bbro_basic_block_data; | |
| 141 | |
| 142 /* The current size of the following dynamic array. */ | |
| 143 static int array_size; | |
| 144 | |
| 145 /* The array which holds needed information for basic blocks. */ | |
| 146 static bbro_basic_block_data *bbd; | |
| 147 | |
| 148 /* To avoid frequent reallocation the size of arrays is greater than needed, | |
| 149 the number of elements is (not less than) 1.25 * size_wanted. */ | |
| 150 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5) | |
| 151 | |
| 152 /* Free the memory and set the pointer to NULL. */ | |
| 153 #define FREE(P) (gcc_assert (P), free (P), P = 0) | |
| 154 | |
| 155 /* Structure for holding information about a trace. */ | |
| 156 struct trace | |
| 157 { | |
| 158 /* First and last basic block of the trace. */ | |
| 159 basic_block first, last; | |
| 160 | |
| 161 /* The round of the STC creation which this trace was found in. */ | |
| 162 int round; | |
| 163 | |
| 164 /* The length (i.e. the number of basic blocks) of the trace. */ | |
| 165 int length; | |
| 166 }; | |
| 167 | |
| 168 /* Maximum frequency and count of one of the entry blocks. */ | |
| 169 static int max_entry_frequency; | |
| 170 static gcov_type max_entry_count; | |
| 171 | |
| 172 /* Local function prototypes. */ | |
| 173 static void find_traces (int *, struct trace *); | |
| 174 static basic_block rotate_loop (edge, struct trace *, int); | |
| 175 static void mark_bb_visited (basic_block, int); | |
| 176 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *, | |
| 177 int, fibheap_t *, int); | |
| 178 static basic_block copy_bb (basic_block, edge, basic_block, int); | |
| 179 static fibheapkey_t bb_to_key (basic_block); | |
| 180 static bool better_edge_p (const_basic_block, const_edge, int, int, int, int, const_edge); | |
| 181 static void connect_traces (int, struct trace *); | |
| 182 static bool copy_bb_p (const_basic_block, int); | |
| 183 static int get_uncond_jump_length (void); | |
| 184 static bool push_to_next_round_p (const_basic_block, int, int, int, gcov_type); | |
| 185 static void find_rarely_executed_basic_blocks_and_crossing_edges (edge **, | |
| 186 int *, | |
| 187 int *); | |
| 188 static void add_labels_and_missing_jumps (edge *, int); | |
| 189 static void add_reg_crossing_jump_notes (void); | |
| 190 static void fix_up_fall_thru_edges (void); | |
| 191 static void fix_edges_for_rarely_executed_code (edge *, int); | |
| 192 static void fix_crossing_conditional_branches (void); | |
| 193 static void fix_crossing_unconditional_branches (void); | |
| 194 | |
| 195 /* Check to see if bb should be pushed into the next round of trace | |
| 196 collections or not. Reasons for pushing the block forward are 1). | |
| 197 If the block is cold, we are doing partitioning, and there will be | |
| 198 another round (cold partition blocks are not supposed to be | |
| 199 collected into traces until the very last round); or 2). There will | |
| 200 be another round, and the basic block is not "hot enough" for the | |
| 201 current round of trace collection. */ | |
| 202 | |
| 203 static bool | |
| 204 push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds, | |
| 205 int exec_th, gcov_type count_th) | |
| 206 { | |
| 207 bool there_exists_another_round; | |
| 208 bool block_not_hot_enough; | |
| 209 | |
| 210 there_exists_another_round = round < number_of_rounds - 1; | |
| 211 | |
| 212 block_not_hot_enough = (bb->frequency < exec_th | |
| 213 || bb->count < count_th | |
| 214 || probably_never_executed_bb_p (bb)); | |
| 215 | |
| 216 if (there_exists_another_round | |
| 217 && block_not_hot_enough) | |
| 218 return true; | |
| 219 else | |
| 220 return false; | |
| 221 } | |
| 222 | |
| 223 /* Find the traces for Software Trace Cache. Chain each trace through | |
| 224 RBI()->next. Store the number of traces to N_TRACES and description of | |
| 225 traces to TRACES. */ | |
| 226 | |
| 227 static void | |
| 228 find_traces (int *n_traces, struct trace *traces) | |
| 229 { | |
| 230 int i; | |
| 231 int number_of_rounds; | |
| 232 edge e; | |
| 233 edge_iterator ei; | |
| 234 fibheap_t heap; | |
| 235 | |
| 236 /* Add one extra round of trace collection when partitioning hot/cold | |
| 237 basic blocks into separate sections. The last round is for all the | |
| 238 cold blocks (and ONLY the cold blocks). */ | |
| 239 | |
| 240 number_of_rounds = N_ROUNDS - 1; | |
| 241 | |
| 242 /* Insert entry points of function into heap. */ | |
| 243 heap = fibheap_new (); | |
| 244 max_entry_frequency = 0; | |
| 245 max_entry_count = 0; | |
| 246 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) | |
| 247 { | |
| 248 bbd[e->dest->index].heap = heap; | |
| 249 bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest), | |
| 250 e->dest); | |
| 251 if (e->dest->frequency > max_entry_frequency) | |
| 252 max_entry_frequency = e->dest->frequency; | |
| 253 if (e->dest->count > max_entry_count) | |
| 254 max_entry_count = e->dest->count; | |
| 255 } | |
| 256 | |
| 257 /* Find the traces. */ | |
| 258 for (i = 0; i < number_of_rounds; i++) | |
| 259 { | |
| 260 gcov_type count_threshold; | |
| 261 | |
| 262 if (dump_file) | |
| 263 fprintf (dump_file, "STC - round %d\n", i + 1); | |
| 264 | |
| 265 if (max_entry_count < INT_MAX / 1000) | |
| 266 count_threshold = max_entry_count * exec_threshold[i] / 1000; | |
| 267 else | |
| 268 count_threshold = max_entry_count / 1000 * exec_threshold[i]; | |
| 269 | |
| 270 find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000, | |
| 271 max_entry_frequency * exec_threshold[i] / 1000, | |
| 272 count_threshold, traces, n_traces, i, &heap, | |
| 273 number_of_rounds); | |
| 274 } | |
| 275 fibheap_delete (heap); | |
| 276 | |
| 277 if (dump_file) | |
| 278 { | |
| 279 for (i = 0; i < *n_traces; i++) | |
| 280 { | |
| 281 basic_block bb; | |
| 282 fprintf (dump_file, "Trace %d (round %d): ", i + 1, | |
| 283 traces[i].round + 1); | |
| 284 for (bb = traces[i].first; bb != traces[i].last; bb = (basic_block) bb->aux) | |
| 285 fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency); | |
| 286 fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency); | |
| 287 } | |
| 288 fflush (dump_file); | |
| 289 } | |
| 290 } | |
| 291 | |
| 292 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE | |
| 293 (with sequential number TRACE_N). */ | |
| 294 | |
| 295 static basic_block | |
| 296 rotate_loop (edge back_edge, struct trace *trace, int trace_n) | |
| 297 { | |
| 298 basic_block bb; | |
| 299 | |
| 300 /* Information about the best end (end after rotation) of the loop. */ | |
| 301 basic_block best_bb = NULL; | |
| 302 edge best_edge = NULL; | |
| 303 int best_freq = -1; | |
| 304 gcov_type best_count = -1; | |
| 305 /* The best edge is preferred when its destination is not visited yet | |
| 306 or is a start block of some trace. */ | |
| 307 bool is_preferred = false; | |
| 308 | |
| 309 /* Find the most frequent edge that goes out from current trace. */ | |
| 310 bb = back_edge->dest; | |
| 311 do | |
| 312 { | |
| 313 edge e; | |
| 314 edge_iterator ei; | |
| 315 | |
| 316 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 317 if (e->dest != EXIT_BLOCK_PTR | |
| 318 && e->dest->il.rtl->visited != trace_n | |
| 319 && (e->flags & EDGE_CAN_FALLTHRU) | |
| 320 && !(e->flags & EDGE_COMPLEX)) | |
| 321 { | |
| 322 if (is_preferred) | |
| 323 { | |
| 324 /* The best edge is preferred. */ | |
| 325 if (!e->dest->il.rtl->visited | |
| 326 || bbd[e->dest->index].start_of_trace >= 0) | |
| 327 { | |
| 328 /* The current edge E is also preferred. */ | |
| 329 int freq = EDGE_FREQUENCY (e); | |
| 330 if (freq > best_freq || e->count > best_count) | |
| 331 { | |
| 332 best_freq = freq; | |
| 333 best_count = e->count; | |
| 334 best_edge = e; | |
| 335 best_bb = bb; | |
| 336 } | |
| 337 } | |
| 338 } | |
| 339 else | |
| 340 { | |
| 341 if (!e->dest->il.rtl->visited | |
| 342 || bbd[e->dest->index].start_of_trace >= 0) | |
| 343 { | |
| 344 /* The current edge E is preferred. */ | |
| 345 is_preferred = true; | |
| 346 best_freq = EDGE_FREQUENCY (e); | |
| 347 best_count = e->count; | |
| 348 best_edge = e; | |
| 349 best_bb = bb; | |
| 350 } | |
| 351 else | |
| 352 { | |
| 353 int freq = EDGE_FREQUENCY (e); | |
| 354 if (!best_edge || freq > best_freq || e->count > best_count) | |
| 355 { | |
| 356 best_freq = freq; | |
| 357 best_count = e->count; | |
| 358 best_edge = e; | |
| 359 best_bb = bb; | |
| 360 } | |
| 361 } | |
| 362 } | |
| 363 } | |
| 364 bb = (basic_block) bb->aux; | |
| 365 } | |
| 366 while (bb != back_edge->dest); | |
| 367 | |
| 368 if (best_bb) | |
| 369 { | |
| 370 /* Rotate the loop so that the BEST_EDGE goes out from the last block of | |
| 371 the trace. */ | |
| 372 if (back_edge->dest == trace->first) | |
| 373 { | |
| 374 trace->first = (basic_block) best_bb->aux; | |
| 375 } | |
| 376 else | |
| 377 { | |
| 378 basic_block prev_bb; | |
| 379 | |
| 380 for (prev_bb = trace->first; | |
| 381 prev_bb->aux != back_edge->dest; | |
| 382 prev_bb = (basic_block) prev_bb->aux) | |
| 383 ; | |
| 384 prev_bb->aux = best_bb->aux; | |
| 385 | |
| 386 /* Try to get rid of uncond jump to cond jump. */ | |
| 387 if (single_succ_p (prev_bb)) | |
| 388 { | |
| 389 basic_block header = single_succ (prev_bb); | |
| 390 | |
| 391 /* Duplicate HEADER if it is a small block containing cond jump | |
| 392 in the end. */ | |
| 393 if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0) | |
| 394 && !find_reg_note (BB_END (header), REG_CROSSING_JUMP, | |
| 395 NULL_RTX)) | |
| 396 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n); | |
| 397 } | |
| 398 } | |
| 399 } | |
| 400 else | |
| 401 { | |
| 402 /* We have not found suitable loop tail so do no rotation. */ | |
| 403 best_bb = back_edge->src; | |
| 404 } | |
| 405 best_bb->aux = NULL; | |
| 406 return best_bb; | |
| 407 } | |
| 408 | |
| 409 /* This function marks BB that it was visited in trace number TRACE. */ | |
| 410 | |
| 411 static void | |
| 412 mark_bb_visited (basic_block bb, int trace) | |
| 413 { | |
| 414 bb->il.rtl->visited = trace; | |
| 415 if (bbd[bb->index].heap) | |
| 416 { | |
| 417 fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node); | |
| 418 bbd[bb->index].heap = NULL; | |
| 419 bbd[bb->index].node = NULL; | |
| 420 } | |
| 421 } | |
| 422 | |
| 423 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do | |
| 424 not include basic blocks their probability is lower than BRANCH_TH or their | |
| 425 frequency is lower than EXEC_TH into traces (or count is lower than | |
| 426 COUNT_TH). It stores the new traces into TRACES and modifies the number of | |
| 427 traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It | |
| 428 expects that starting basic blocks are in *HEAP and at the end it deletes | |
| 429 *HEAP and stores starting points for the next round into new *HEAP. */ | |
| 430 | |
| 431 static void | |
| 432 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th, | |
| 433 struct trace *traces, int *n_traces, int round, | |
| 434 fibheap_t *heap, int number_of_rounds) | |
| 435 { | |
| 436 /* Heap for discarded basic blocks which are possible starting points for | |
| 437 the next round. */ | |
| 438 fibheap_t new_heap = fibheap_new (); | |
| 439 | |
| 440 while (!fibheap_empty (*heap)) | |
| 441 { | |
| 442 basic_block bb; | |
| 443 struct trace *trace; | |
| 444 edge best_edge, e; | |
| 445 fibheapkey_t key; | |
| 446 edge_iterator ei; | |
| 447 | |
| 448 bb = (basic_block) fibheap_extract_min (*heap); | |
| 449 bbd[bb->index].heap = NULL; | |
| 450 bbd[bb->index].node = NULL; | |
| 451 | |
| 452 if (dump_file) | |
| 453 fprintf (dump_file, "Getting bb %d\n", bb->index); | |
| 454 | |
| 455 /* If the BB's frequency is too low send BB to the next round. When | |
| 456 partitioning hot/cold blocks into separate sections, make sure all | |
| 457 the cold blocks (and ONLY the cold blocks) go into the (extra) final | |
| 458 round. */ | |
| 459 | |
| 460 if (push_to_next_round_p (bb, round, number_of_rounds, exec_th, | |
| 461 count_th)) | |
| 462 { | |
| 463 int key = bb_to_key (bb); | |
| 464 bbd[bb->index].heap = new_heap; | |
| 465 bbd[bb->index].node = fibheap_insert (new_heap, key, bb); | |
| 466 | |
| 467 if (dump_file) | |
| 468 fprintf (dump_file, | |
| 469 " Possible start point of next round: %d (key: %d)\n", | |
| 470 bb->index, key); | |
| 471 continue; | |
| 472 } | |
| 473 | |
| 474 trace = traces + *n_traces; | |
| 475 trace->first = bb; | |
| 476 trace->round = round; | |
| 477 trace->length = 0; | |
| 478 bbd[bb->index].in_trace = *n_traces; | |
| 479 (*n_traces)++; | |
| 480 | |
| 481 do | |
| 482 { | |
| 483 int prob, freq; | |
| 484 bool ends_in_call; | |
| 485 | |
| 486 /* The probability and frequency of the best edge. */ | |
| 487 int best_prob = INT_MIN / 2; | |
| 488 int best_freq = INT_MIN / 2; | |
| 489 | |
| 490 best_edge = NULL; | |
| 491 mark_bb_visited (bb, *n_traces); | |
| 492 trace->length++; | |
| 493 | |
| 494 if (dump_file) | |
| 495 fprintf (dump_file, "Basic block %d was visited in trace %d\n", | |
| 496 bb->index, *n_traces - 1); | |
| 497 | |
| 498 ends_in_call = block_ends_with_call_p (bb); | |
| 499 | |
| 500 /* Select the successor that will be placed after BB. */ | |
| 501 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 502 { | |
| 503 gcc_assert (!(e->flags & EDGE_FAKE)); | |
| 504 | |
| 505 if (e->dest == EXIT_BLOCK_PTR) | |
| 506 continue; | |
| 507 | |
| 508 if (e->dest->il.rtl->visited | |
| 509 && e->dest->il.rtl->visited != *n_traces) | |
| 510 continue; | |
| 511 | |
| 512 if (BB_PARTITION (e->dest) != BB_PARTITION (bb)) | |
| 513 continue; | |
| 514 | |
| 515 prob = e->probability; | |
| 516 freq = e->dest->frequency; | |
| 517 | |
| 518 /* The only sensible preference for a call instruction is the | |
| 519 fallthru edge. Don't bother selecting anything else. */ | |
| 520 if (ends_in_call) | |
| 521 { | |
| 522 if (e->flags & EDGE_CAN_FALLTHRU) | |
| 523 { | |
| 524 best_edge = e; | |
| 525 best_prob = prob; | |
| 526 best_freq = freq; | |
| 527 } | |
| 528 continue; | |
| 529 } | |
| 530 | |
| 531 /* Edge that cannot be fallthru or improbable or infrequent | |
| 532 successor (i.e. it is unsuitable successor). */ | |
| 533 if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX) | |
| 534 || prob < branch_th || EDGE_FREQUENCY (e) < exec_th | |
| 535 || e->count < count_th) | |
| 536 continue; | |
| 537 | |
| 538 /* If partitioning hot/cold basic blocks, don't consider edges | |
| 539 that cross section boundaries. */ | |
| 540 | |
| 541 if (better_edge_p (bb, e, prob, freq, best_prob, best_freq, | |
| 542 best_edge)) | |
| 543 { | |
| 544 best_edge = e; | |
| 545 best_prob = prob; | |
| 546 best_freq = freq; | |
| 547 } | |
| 548 } | |
| 549 | |
| 550 /* If the best destination has multiple predecessors, and can be | |
| 551 duplicated cheaper than a jump, don't allow it to be added | |
| 552 to a trace. We'll duplicate it when connecting traces. */ | |
| 553 if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2 | |
| 554 && copy_bb_p (best_edge->dest, 0)) | |
| 555 best_edge = NULL; | |
| 556 | |
| 557 /* Add all non-selected successors to the heaps. */ | |
| 558 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 559 { | |
| 560 if (e == best_edge | |
| 561 || e->dest == EXIT_BLOCK_PTR | |
| 562 || e->dest->il.rtl->visited) | |
| 563 continue; | |
| 564 | |
| 565 key = bb_to_key (e->dest); | |
| 566 | |
| 567 if (bbd[e->dest->index].heap) | |
| 568 { | |
| 569 /* E->DEST is already in some heap. */ | |
| 570 if (key != bbd[e->dest->index].node->key) | |
| 571 { | |
| 572 if (dump_file) | |
| 573 { | |
| 574 fprintf (dump_file, | |
| 575 "Changing key for bb %d from %ld to %ld.\n", | |
| 576 e->dest->index, | |
| 577 (long) bbd[e->dest->index].node->key, | |
| 578 key); | |
| 579 } | |
| 580 fibheap_replace_key (bbd[e->dest->index].heap, | |
| 581 bbd[e->dest->index].node, key); | |
| 582 } | |
| 583 } | |
| 584 else | |
| 585 { | |
| 586 fibheap_t which_heap = *heap; | |
| 587 | |
| 588 prob = e->probability; | |
| 589 freq = EDGE_FREQUENCY (e); | |
| 590 | |
| 591 if (!(e->flags & EDGE_CAN_FALLTHRU) | |
| 592 || (e->flags & EDGE_COMPLEX) | |
| 593 || prob < branch_th || freq < exec_th | |
| 594 || e->count < count_th) | |
| 595 { | |
| 596 /* When partitioning hot/cold basic blocks, make sure | |
| 597 the cold blocks (and only the cold blocks) all get | |
| 598 pushed to the last round of trace collection. */ | |
| 599 | |
| 600 if (push_to_next_round_p (e->dest, round, | |
| 601 number_of_rounds, | |
| 602 exec_th, count_th)) | |
| 603 which_heap = new_heap; | |
| 604 } | |
| 605 | |
| 606 bbd[e->dest->index].heap = which_heap; | |
| 607 bbd[e->dest->index].node = fibheap_insert (which_heap, | |
| 608 key, e->dest); | |
| 609 | |
| 610 if (dump_file) | |
| 611 { | |
| 612 fprintf (dump_file, | |
| 613 " Possible start of %s round: %d (key: %ld)\n", | |
| 614 (which_heap == new_heap) ? "next" : "this", | |
| 615 e->dest->index, (long) key); | |
| 616 } | |
| 617 | |
| 618 } | |
| 619 } | |
| 620 | |
| 621 if (best_edge) /* Suitable successor was found. */ | |
| 622 { | |
| 623 if (best_edge->dest->il.rtl->visited == *n_traces) | |
| 624 { | |
| 625 /* We do nothing with one basic block loops. */ | |
| 626 if (best_edge->dest != bb) | |
| 627 { | |
| 628 if (EDGE_FREQUENCY (best_edge) | |
| 629 > 4 * best_edge->dest->frequency / 5) | |
| 630 { | |
| 631 /* The loop has at least 4 iterations. If the loop | |
| 632 header is not the first block of the function | |
| 633 we can rotate the loop. */ | |
| 634 | |
| 635 if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb) | |
| 636 { | |
| 637 if (dump_file) | |
| 638 { | |
| 639 fprintf (dump_file, | |
| 640 "Rotating loop %d - %d\n", | |
| 641 best_edge->dest->index, bb->index); | |
| 642 } | |
| 643 bb->aux = best_edge->dest; | |
| 644 bbd[best_edge->dest->index].in_trace = | |
| 645 (*n_traces) - 1; | |
| 646 bb = rotate_loop (best_edge, trace, *n_traces); | |
| 647 } | |
| 648 } | |
| 649 else | |
| 650 { | |
| 651 /* The loop has less than 4 iterations. */ | |
| 652 | |
| 653 if (single_succ_p (bb) | |
| 654 && copy_bb_p (best_edge->dest, | |
| 655 optimize_edge_for_speed_p (best_edge))) | |
| 656 { | |
| 657 bb = copy_bb (best_edge->dest, best_edge, bb, | |
| 658 *n_traces); | |
| 659 trace->length++; | |
| 660 } | |
| 661 } | |
| 662 } | |
| 663 | |
| 664 /* Terminate the trace. */ | |
| 665 break; | |
| 666 } | |
| 667 else | |
| 668 { | |
| 669 /* Check for a situation | |
| 670 | |
| 671 A | |
| 672 /| | |
| 673 B | | |
| 674 \| | |
| 675 C | |
| 676 | |
| 677 where | |
| 678 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC) | |
| 679 >= EDGE_FREQUENCY (AC). | |
| 680 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) ) | |
| 681 Best ordering is then A B C. | |
| 682 | |
| 683 This situation is created for example by: | |
| 684 | |
| 685 if (A) B; | |
| 686 C; | |
| 687 | |
| 688 */ | |
| 689 | |
| 690 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 691 if (e != best_edge | |
| 692 && (e->flags & EDGE_CAN_FALLTHRU) | |
| 693 && !(e->flags & EDGE_COMPLEX) | |
| 694 && !e->dest->il.rtl->visited | |
| 695 && single_pred_p (e->dest) | |
| 696 && !(e->flags & EDGE_CROSSING) | |
| 697 && single_succ_p (e->dest) | |
| 698 && (single_succ_edge (e->dest)->flags | |
| 699 & EDGE_CAN_FALLTHRU) | |
| 700 && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX) | |
| 701 && single_succ (e->dest) == best_edge->dest | |
| 702 && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge)) | |
| 703 { | |
| 704 best_edge = e; | |
| 705 if (dump_file) | |
| 706 fprintf (dump_file, "Selecting BB %d\n", | |
| 707 best_edge->dest->index); | |
| 708 break; | |
| 709 } | |
| 710 | |
| 711 bb->aux = best_edge->dest; | |
| 712 bbd[best_edge->dest->index].in_trace = (*n_traces) - 1; | |
| 713 bb = best_edge->dest; | |
| 714 } | |
| 715 } | |
| 716 } | |
| 717 while (best_edge); | |
| 718 trace->last = bb; | |
| 719 bbd[trace->first->index].start_of_trace = *n_traces - 1; | |
| 720 bbd[trace->last->index].end_of_trace = *n_traces - 1; | |
| 721 | |
| 722 /* The trace is terminated so we have to recount the keys in heap | |
| 723 (some block can have a lower key because now one of its predecessors | |
| 724 is an end of the trace). */ | |
| 725 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 726 { | |
| 727 if (e->dest == EXIT_BLOCK_PTR | |
| 728 || e->dest->il.rtl->visited) | |
| 729 continue; | |
| 730 | |
| 731 if (bbd[e->dest->index].heap) | |
| 732 { | |
| 733 key = bb_to_key (e->dest); | |
| 734 if (key != bbd[e->dest->index].node->key) | |
| 735 { | |
| 736 if (dump_file) | |
| 737 { | |
| 738 fprintf (dump_file, | |
| 739 "Changing key for bb %d from %ld to %ld.\n", | |
| 740 e->dest->index, | |
| 741 (long) bbd[e->dest->index].node->key, key); | |
| 742 } | |
| 743 fibheap_replace_key (bbd[e->dest->index].heap, | |
| 744 bbd[e->dest->index].node, | |
| 745 key); | |
| 746 } | |
| 747 } | |
| 748 } | |
| 749 } | |
| 750 | |
| 751 fibheap_delete (*heap); | |
| 752 | |
| 753 /* "Return" the new heap. */ | |
| 754 *heap = new_heap; | |
| 755 } | |
| 756 | |
| 757 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add | |
| 758 it to trace after BB, mark OLD_BB visited and update pass' data structures | |
| 759 (TRACE is a number of trace which OLD_BB is duplicated to). */ | |
| 760 | |
| 761 static basic_block | |
| 762 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace) | |
| 763 { | |
| 764 basic_block new_bb; | |
| 765 | |
| 766 new_bb = duplicate_block (old_bb, e, bb); | |
| 767 BB_COPY_PARTITION (new_bb, old_bb); | |
| 768 | |
| 769 gcc_assert (e->dest == new_bb); | |
| 770 gcc_assert (!e->dest->il.rtl->visited); | |
| 771 | |
| 772 if (dump_file) | |
| 773 fprintf (dump_file, | |
| 774 "Duplicated bb %d (created bb %d)\n", | |
| 775 old_bb->index, new_bb->index); | |
| 776 new_bb->il.rtl->visited = trace; | |
| 777 new_bb->aux = bb->aux; | |
| 778 bb->aux = new_bb; | |
| 779 | |
| 780 if (new_bb->index >= array_size || last_basic_block > array_size) | |
| 781 { | |
| 782 int i; | |
| 783 int new_size; | |
| 784 | |
| 785 new_size = MAX (last_basic_block, new_bb->index + 1); | |
| 786 new_size = GET_ARRAY_SIZE (new_size); | |
| 787 bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size); | |
| 788 for (i = array_size; i < new_size; i++) | |
| 789 { | |
| 790 bbd[i].start_of_trace = -1; | |
| 791 bbd[i].in_trace = -1; | |
| 792 bbd[i].end_of_trace = -1; | |
| 793 bbd[i].heap = NULL; | |
| 794 bbd[i].node = NULL; | |
| 795 } | |
| 796 array_size = new_size; | |
| 797 | |
| 798 if (dump_file) | |
| 799 { | |
| 800 fprintf (dump_file, | |
| 801 "Growing the dynamic array to %d elements.\n", | |
| 802 array_size); | |
| 803 } | |
| 804 } | |
| 805 | |
| 806 bbd[new_bb->index].in_trace = trace; | |
| 807 | |
| 808 return new_bb; | |
| 809 } | |
| 810 | |
| 811 /* Compute and return the key (for the heap) of the basic block BB. */ | |
| 812 | |
| 813 static fibheapkey_t | |
| 814 bb_to_key (basic_block bb) | |
| 815 { | |
| 816 edge e; | |
| 817 edge_iterator ei; | |
| 818 int priority = 0; | |
| 819 | |
| 820 /* Do not start in probably never executed blocks. */ | |
| 821 | |
| 822 if (BB_PARTITION (bb) == BB_COLD_PARTITION | |
| 823 || probably_never_executed_bb_p (bb)) | |
| 824 return BB_FREQ_MAX; | |
| 825 | |
| 826 /* Prefer blocks whose predecessor is an end of some trace | |
| 827 or whose predecessor edge is EDGE_DFS_BACK. */ | |
| 828 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 829 { | |
| 830 if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0) | |
| 831 || (e->flags & EDGE_DFS_BACK)) | |
| 832 { | |
| 833 int edge_freq = EDGE_FREQUENCY (e); | |
| 834 | |
| 835 if (edge_freq > priority) | |
| 836 priority = edge_freq; | |
| 837 } | |
| 838 } | |
| 839 | |
| 840 if (priority) | |
| 841 /* The block with priority should have significantly lower key. */ | |
| 842 return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency); | |
| 843 return -bb->frequency; | |
| 844 } | |
| 845 | |
| 846 /* Return true when the edge E from basic block BB is better than the temporary | |
| 847 best edge (details are in function). The probability of edge E is PROB. The | |
| 848 frequency of the successor is FREQ. The current best probability is | |
| 849 BEST_PROB, the best frequency is BEST_FREQ. | |
| 850 The edge is considered to be equivalent when PROB does not differ much from | |
| 851 BEST_PROB; similarly for frequency. */ | |
| 852 | |
| 853 static bool | |
| 854 better_edge_p (const_basic_block bb, const_edge e, int prob, int freq, int best_prob, | |
| 855 int best_freq, const_edge cur_best_edge) | |
| 856 { | |
| 857 bool is_better_edge; | |
| 858 | |
| 859 /* The BEST_* values do not have to be best, but can be a bit smaller than | |
| 860 maximum values. */ | |
| 861 int diff_prob = best_prob / 10; | |
| 862 int diff_freq = best_freq / 10; | |
| 863 | |
| 864 if (prob > best_prob + diff_prob) | |
| 865 /* The edge has higher probability than the temporary best edge. */ | |
| 866 is_better_edge = true; | |
| 867 else if (prob < best_prob - diff_prob) | |
| 868 /* The edge has lower probability than the temporary best edge. */ | |
| 869 is_better_edge = false; | |
| 870 else if (freq < best_freq - diff_freq) | |
| 871 /* The edge and the temporary best edge have almost equivalent | |
| 872 probabilities. The higher frequency of a successor now means | |
| 873 that there is another edge going into that successor. | |
| 874 This successor has lower frequency so it is better. */ | |
| 875 is_better_edge = true; | |
| 876 else if (freq > best_freq + diff_freq) | |
| 877 /* This successor has higher frequency so it is worse. */ | |
| 878 is_better_edge = false; | |
| 879 else if (e->dest->prev_bb == bb) | |
| 880 /* The edges have equivalent probabilities and the successors | |
| 881 have equivalent frequencies. Select the previous successor. */ | |
| 882 is_better_edge = true; | |
| 883 else | |
| 884 is_better_edge = false; | |
| 885 | |
| 886 /* If we are doing hot/cold partitioning, make sure that we always favor | |
| 887 non-crossing edges over crossing edges. */ | |
| 888 | |
| 889 if (!is_better_edge | |
| 890 && flag_reorder_blocks_and_partition | |
| 891 && cur_best_edge | |
| 892 && (cur_best_edge->flags & EDGE_CROSSING) | |
| 893 && !(e->flags & EDGE_CROSSING)) | |
| 894 is_better_edge = true; | |
| 895 | |
| 896 return is_better_edge; | |
| 897 } | |
| 898 | |
| 899 /* Connect traces in array TRACES, N_TRACES is the count of traces. */ | |
| 900 | |
| 901 static void | |
| 902 connect_traces (int n_traces, struct trace *traces) | |
| 903 { | |
| 904 int i; | |
| 905 bool *connected; | |
| 906 bool two_passes; | |
| 907 int last_trace; | |
| 908 int current_pass; | |
| 909 int current_partition; | |
| 910 int freq_threshold; | |
| 911 gcov_type count_threshold; | |
| 912 | |
| 913 freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000; | |
| 914 if (max_entry_count < INT_MAX / 1000) | |
| 915 count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000; | |
| 916 else | |
| 917 count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD; | |
| 918 | |
| 919 connected = XCNEWVEC (bool, n_traces); | |
| 920 last_trace = -1; | |
| 921 current_pass = 1; | |
| 922 current_partition = BB_PARTITION (traces[0].first); | |
| 923 two_passes = false; | |
| 924 | |
| 925 if (flag_reorder_blocks_and_partition) | |
| 926 for (i = 0; i < n_traces && !two_passes; i++) | |
| 927 if (BB_PARTITION (traces[0].first) | |
| 928 != BB_PARTITION (traces[i].first)) | |
| 929 two_passes = true; | |
| 930 | |
| 931 for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++) | |
| 932 { | |
| 933 int t = i; | |
| 934 int t2; | |
| 935 edge e, best; | |
| 936 int best_len; | |
| 937 | |
| 938 if (i >= n_traces) | |
| 939 { | |
| 940 gcc_assert (two_passes && current_pass == 1); | |
| 941 i = 0; | |
| 942 t = i; | |
| 943 current_pass = 2; | |
| 944 if (current_partition == BB_HOT_PARTITION) | |
| 945 current_partition = BB_COLD_PARTITION; | |
| 946 else | |
| 947 current_partition = BB_HOT_PARTITION; | |
| 948 } | |
| 949 | |
| 950 if (connected[t]) | |
| 951 continue; | |
| 952 | |
| 953 if (two_passes | |
| 954 && BB_PARTITION (traces[t].first) != current_partition) | |
| 955 continue; | |
| 956 | |
| 957 connected[t] = true; | |
| 958 | |
| 959 /* Find the predecessor traces. */ | |
| 960 for (t2 = t; t2 > 0;) | |
| 961 { | |
| 962 edge_iterator ei; | |
| 963 best = NULL; | |
| 964 best_len = 0; | |
| 965 FOR_EACH_EDGE (e, ei, traces[t2].first->preds) | |
| 966 { | |
| 967 int si = e->src->index; | |
| 968 | |
| 969 if (e->src != ENTRY_BLOCK_PTR | |
| 970 && (e->flags & EDGE_CAN_FALLTHRU) | |
| 971 && !(e->flags & EDGE_COMPLEX) | |
| 972 && bbd[si].end_of_trace >= 0 | |
| 973 && !connected[bbd[si].end_of_trace] | |
| 974 && (BB_PARTITION (e->src) == current_partition) | |
| 975 && (!best | |
| 976 || e->probability > best->probability | |
| 977 || (e->probability == best->probability | |
| 978 && traces[bbd[si].end_of_trace].length > best_len))) | |
| 979 { | |
| 980 best = e; | |
| 981 best_len = traces[bbd[si].end_of_trace].length; | |
| 982 } | |
| 983 } | |
| 984 if (best) | |
| 985 { | |
| 986 best->src->aux = best->dest; | |
| 987 t2 = bbd[best->src->index].end_of_trace; | |
| 988 connected[t2] = true; | |
| 989 | |
| 990 if (dump_file) | |
| 991 { | |
| 992 fprintf (dump_file, "Connection: %d %d\n", | |
| 993 best->src->index, best->dest->index); | |
| 994 } | |
| 995 } | |
| 996 else | |
| 997 break; | |
| 998 } | |
| 999 | |
| 1000 if (last_trace >= 0) | |
| 1001 traces[last_trace].last->aux = traces[t2].first; | |
| 1002 last_trace = t; | |
| 1003 | |
| 1004 /* Find the successor traces. */ | |
| 1005 while (1) | |
| 1006 { | |
| 1007 /* Find the continuation of the chain. */ | |
| 1008 edge_iterator ei; | |
| 1009 best = NULL; | |
| 1010 best_len = 0; | |
| 1011 FOR_EACH_EDGE (e, ei, traces[t].last->succs) | |
| 1012 { | |
| 1013 int di = e->dest->index; | |
| 1014 | |
| 1015 if (e->dest != EXIT_BLOCK_PTR | |
| 1016 && (e->flags & EDGE_CAN_FALLTHRU) | |
| 1017 && !(e->flags & EDGE_COMPLEX) | |
| 1018 && bbd[di].start_of_trace >= 0 | |
| 1019 && !connected[bbd[di].start_of_trace] | |
| 1020 && (BB_PARTITION (e->dest) == current_partition) | |
| 1021 && (!best | |
| 1022 || e->probability > best->probability | |
| 1023 || (e->probability == best->probability | |
| 1024 && traces[bbd[di].start_of_trace].length > best_len))) | |
| 1025 { | |
| 1026 best = e; | |
| 1027 best_len = traces[bbd[di].start_of_trace].length; | |
| 1028 } | |
| 1029 } | |
| 1030 | |
| 1031 if (best) | |
| 1032 { | |
| 1033 if (dump_file) | |
| 1034 { | |
| 1035 fprintf (dump_file, "Connection: %d %d\n", | |
| 1036 best->src->index, best->dest->index); | |
| 1037 } | |
| 1038 t = bbd[best->dest->index].start_of_trace; | |
| 1039 traces[last_trace].last->aux = traces[t].first; | |
| 1040 connected[t] = true; | |
| 1041 last_trace = t; | |
| 1042 } | |
| 1043 else | |
| 1044 { | |
| 1045 /* Try to connect the traces by duplication of 1 block. */ | |
| 1046 edge e2; | |
| 1047 basic_block next_bb = NULL; | |
| 1048 bool try_copy = false; | |
| 1049 | |
| 1050 FOR_EACH_EDGE (e, ei, traces[t].last->succs) | |
| 1051 if (e->dest != EXIT_BLOCK_PTR | |
| 1052 && (e->flags & EDGE_CAN_FALLTHRU) | |
| 1053 && !(e->flags & EDGE_COMPLEX) | |
| 1054 && (!best || e->probability > best->probability)) | |
| 1055 { | |
| 1056 edge_iterator ei; | |
| 1057 edge best2 = NULL; | |
| 1058 int best2_len = 0; | |
| 1059 | |
| 1060 /* If the destination is a start of a trace which is only | |
| 1061 one block long, then no need to search the successor | |
| 1062 blocks of the trace. Accept it. */ | |
| 1063 if (bbd[e->dest->index].start_of_trace >= 0 | |
| 1064 && traces[bbd[e->dest->index].start_of_trace].length | |
| 1065 == 1) | |
| 1066 { | |
| 1067 best = e; | |
| 1068 try_copy = true; | |
| 1069 continue; | |
| 1070 } | |
| 1071 | |
| 1072 FOR_EACH_EDGE (e2, ei, e->dest->succs) | |
| 1073 { | |
| 1074 int di = e2->dest->index; | |
| 1075 | |
| 1076 if (e2->dest == EXIT_BLOCK_PTR | |
| 1077 || ((e2->flags & EDGE_CAN_FALLTHRU) | |
| 1078 && !(e2->flags & EDGE_COMPLEX) | |
| 1079 && bbd[di].start_of_trace >= 0 | |
| 1080 && !connected[bbd[di].start_of_trace] | |
| 1081 && (BB_PARTITION (e2->dest) == current_partition) | |
| 1082 && (EDGE_FREQUENCY (e2) >= freq_threshold) | |
| 1083 && (e2->count >= count_threshold) | |
| 1084 && (!best2 | |
| 1085 || e2->probability > best2->probability | |
| 1086 || (e2->probability == best2->probability | |
| 1087 && traces[bbd[di].start_of_trace].length | |
| 1088 > best2_len)))) | |
| 1089 { | |
| 1090 best = e; | |
| 1091 best2 = e2; | |
| 1092 if (e2->dest != EXIT_BLOCK_PTR) | |
| 1093 best2_len = traces[bbd[di].start_of_trace].length; | |
| 1094 else | |
| 1095 best2_len = INT_MAX; | |
| 1096 next_bb = e2->dest; | |
| 1097 try_copy = true; | |
| 1098 } | |
| 1099 } | |
| 1100 } | |
| 1101 | |
| 1102 if (flag_reorder_blocks_and_partition) | |
| 1103 try_copy = false; | |
| 1104 | |
| 1105 /* Copy tiny blocks always; copy larger blocks only when the | |
| 1106 edge is traversed frequently enough. */ | |
| 1107 if (try_copy | |
| 1108 && copy_bb_p (best->dest, | |
| 1109 optimize_edge_for_speed_p (best) | |
| 1110 && EDGE_FREQUENCY (best) >= freq_threshold | |
| 1111 && best->count >= count_threshold)) | |
| 1112 { | |
| 1113 basic_block new_bb; | |
| 1114 | |
| 1115 if (dump_file) | |
| 1116 { | |
| 1117 fprintf (dump_file, "Connection: %d %d ", | |
| 1118 traces[t].last->index, best->dest->index); | |
| 1119 if (!next_bb) | |
| 1120 fputc ('\n', dump_file); | |
| 1121 else if (next_bb == EXIT_BLOCK_PTR) | |
| 1122 fprintf (dump_file, "exit\n"); | |
| 1123 else | |
| 1124 fprintf (dump_file, "%d\n", next_bb->index); | |
| 1125 } | |
| 1126 | |
| 1127 new_bb = copy_bb (best->dest, best, traces[t].last, t); | |
| 1128 traces[t].last = new_bb; | |
| 1129 if (next_bb && next_bb != EXIT_BLOCK_PTR) | |
| 1130 { | |
| 1131 t = bbd[next_bb->index].start_of_trace; | |
| 1132 traces[last_trace].last->aux = traces[t].first; | |
| 1133 connected[t] = true; | |
| 1134 last_trace = t; | |
| 1135 } | |
| 1136 else | |
| 1137 break; /* Stop finding the successor traces. */ | |
| 1138 } | |
| 1139 else | |
| 1140 break; /* Stop finding the successor traces. */ | |
| 1141 } | |
| 1142 } | |
| 1143 } | |
| 1144 | |
| 1145 if (dump_file) | |
| 1146 { | |
| 1147 basic_block bb; | |
| 1148 | |
| 1149 fprintf (dump_file, "Final order:\n"); | |
| 1150 for (bb = traces[0].first; bb; bb = (basic_block) bb->aux) | |
| 1151 fprintf (dump_file, "%d ", bb->index); | |
| 1152 fprintf (dump_file, "\n"); | |
| 1153 fflush (dump_file); | |
| 1154 } | |
| 1155 | |
| 1156 FREE (connected); | |
| 1157 } | |
| 1158 | |
| 1159 /* Return true when BB can and should be copied. CODE_MAY_GROW is true | |
| 1160 when code size is allowed to grow by duplication. */ | |
| 1161 | |
| 1162 static bool | |
| 1163 copy_bb_p (const_basic_block bb, int code_may_grow) | |
| 1164 { | |
| 1165 int size = 0; | |
| 1166 int max_size = uncond_jump_length; | |
| 1167 rtx insn; | |
| 1168 | |
| 1169 if (!bb->frequency) | |
| 1170 return false; | |
| 1171 if (EDGE_COUNT (bb->preds) < 2) | |
| 1172 return false; | |
| 1173 if (!can_duplicate_block_p (bb)) | |
| 1174 return false; | |
| 1175 | |
| 1176 /* Avoid duplicating blocks which have many successors (PR/13430). */ | |
| 1177 if (EDGE_COUNT (bb->succs) > 8) | |
| 1178 return false; | |
| 1179 | |
| 1180 if (code_may_grow && optimize_bb_for_speed_p (bb)) | |
| 1181 max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS); | |
| 1182 | |
| 1183 FOR_BB_INSNS (bb, insn) | |
| 1184 { | |
| 1185 if (INSN_P (insn)) | |
| 1186 size += get_attr_min_length (insn); | |
| 1187 } | |
| 1188 | |
| 1189 if (size <= max_size) | |
| 1190 return true; | |
| 1191 | |
| 1192 if (dump_file) | |
| 1193 { | |
| 1194 fprintf (dump_file, | |
| 1195 "Block %d can't be copied because its size = %d.\n", | |
| 1196 bb->index, size); | |
| 1197 } | |
| 1198 | |
| 1199 return false; | |
| 1200 } | |
| 1201 | |
| 1202 /* Return the length of unconditional jump instruction. */ | |
| 1203 | |
| 1204 static int | |
| 1205 get_uncond_jump_length (void) | |
| 1206 { | |
| 1207 rtx label, jump; | |
| 1208 int length; | |
| 1209 | |
| 1210 label = emit_label_before (gen_label_rtx (), get_insns ()); | |
| 1211 jump = emit_jump_insn (gen_jump (label)); | |
| 1212 | |
| 1213 length = get_attr_min_length (jump); | |
| 1214 | |
| 1215 delete_insn (jump); | |
| 1216 delete_insn (label); | |
| 1217 return length; | |
| 1218 } | |
| 1219 | |
| 1220 /* Find the basic blocks that are rarely executed and need to be moved to | |
| 1221 a separate section of the .o file (to cut down on paging and improve | |
| 1222 cache locality). */ | |
| 1223 | |
| 1224 static void | |
| 1225 find_rarely_executed_basic_blocks_and_crossing_edges (edge **crossing_edges, | |
| 1226 int *n_crossing_edges, | |
| 1227 int *max_idx) | |
| 1228 { | |
| 1229 basic_block bb; | |
| 1230 edge e; | |
| 1231 int i; | |
| 1232 edge_iterator ei; | |
| 1233 | |
| 1234 /* Mark which partition (hot/cold) each basic block belongs in. */ | |
| 1235 | |
| 1236 FOR_EACH_BB (bb) | |
| 1237 { | |
| 1238 if (probably_never_executed_bb_p (bb)) | |
| 1239 BB_SET_PARTITION (bb, BB_COLD_PARTITION); | |
| 1240 else | |
| 1241 BB_SET_PARTITION (bb, BB_HOT_PARTITION); | |
| 1242 } | |
| 1243 | |
| 1244 /* Mark every edge that crosses between sections. */ | |
| 1245 | |
| 1246 i = 0; | |
| 1247 FOR_EACH_BB (bb) | |
| 1248 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 1249 { | |
| 1250 if (e->src != ENTRY_BLOCK_PTR | |
| 1251 && e->dest != EXIT_BLOCK_PTR | |
| 1252 && BB_PARTITION (e->src) != BB_PARTITION (e->dest)) | |
| 1253 { | |
| 1254 e->flags |= EDGE_CROSSING; | |
| 1255 if (i == *max_idx) | |
| 1256 { | |
| 1257 *max_idx *= 2; | |
| 1258 *crossing_edges = XRESIZEVEC (edge, *crossing_edges, *max_idx); | |
| 1259 } | |
| 1260 (*crossing_edges)[i++] = e; | |
| 1261 } | |
| 1262 else | |
| 1263 e->flags &= ~EDGE_CROSSING; | |
| 1264 } | |
| 1265 *n_crossing_edges = i; | |
| 1266 } | |
| 1267 | |
| 1268 /* If any destination of a crossing edge does not have a label, add label; | |
| 1269 Convert any fall-through crossing edges (for blocks that do not contain | |
| 1270 a jump) to unconditional jumps. */ | |
| 1271 | |
| 1272 static void | |
| 1273 add_labels_and_missing_jumps (edge *crossing_edges, int n_crossing_edges) | |
| 1274 { | |
| 1275 int i; | |
| 1276 basic_block src; | |
| 1277 basic_block dest; | |
| 1278 rtx label; | |
| 1279 rtx barrier; | |
| 1280 rtx new_jump; | |
| 1281 | |
| 1282 for (i=0; i < n_crossing_edges; i++) | |
| 1283 { | |
| 1284 if (crossing_edges[i]) | |
| 1285 { | |
| 1286 src = crossing_edges[i]->src; | |
| 1287 dest = crossing_edges[i]->dest; | |
| 1288 | |
| 1289 /* Make sure dest has a label. */ | |
| 1290 | |
| 1291 if (dest && (dest != EXIT_BLOCK_PTR)) | |
| 1292 { | |
| 1293 label = block_label (dest); | |
| 1294 | |
| 1295 /* Make sure source block ends with a jump. If the | |
| 1296 source block does not end with a jump it might end | |
| 1297 with a call_insn; this case will be handled in | |
| 1298 fix_up_fall_thru_edges function. */ | |
| 1299 | |
| 1300 if (src && (src != ENTRY_BLOCK_PTR)) | |
| 1301 { | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1302 if (!JUMP_P (BB_END (src)) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1303 && !block_ends_with_call_p (src) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1304 && !can_throw_internal (BB_END (src))) |
| 0 | 1305 /* bb just falls through. */ |
| 1306 { | |
| 1307 /* make sure there's only one successor */ | |
| 1308 gcc_assert (single_succ_p (src)); | |
| 1309 | |
| 1310 /* Find label in dest block. */ | |
| 1311 label = block_label (dest); | |
| 1312 | |
| 1313 new_jump = emit_jump_insn_after (gen_jump (label), | |
| 1314 BB_END (src)); | |
| 1315 barrier = emit_barrier_after (new_jump); | |
| 1316 JUMP_LABEL (new_jump) = label; | |
| 1317 LABEL_NUSES (label) += 1; | |
| 1318 src->il.rtl->footer = unlink_insn_chain (barrier, barrier); | |
| 1319 /* Mark edge as non-fallthru. */ | |
| 1320 crossing_edges[i]->flags &= ~EDGE_FALLTHRU; | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1321 } /* end: 'if (!JUMP_P ... ' */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1322 } /* end: 'if (src && src !=...' */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1323 } /* end: 'if (dest && dest !=...' */ |
| 0 | 1324 } /* end: 'if (crossing_edges[i]...' */ |
| 1325 } /* end for loop */ | |
| 1326 } | |
| 1327 | |
| 1328 /* Find any bb's where the fall-through edge is a crossing edge (note that | |
| 1329 these bb's must also contain a conditional jump or end with a call | |
| 1330 instruction; we've already dealt with fall-through edges for blocks | |
| 1331 that didn't have a conditional jump or didn't end with call instruction | |
| 1332 in the call to add_labels_and_missing_jumps). Convert the fall-through | |
| 1333 edge to non-crossing edge by inserting a new bb to fall-through into. | |
| 1334 The new bb will contain an unconditional jump (crossing edge) to the | |
| 1335 original fall through destination. */ | |
| 1336 | |
| 1337 static void | |
| 1338 fix_up_fall_thru_edges (void) | |
| 1339 { | |
| 1340 basic_block cur_bb; | |
| 1341 basic_block new_bb; | |
| 1342 edge succ1; | |
| 1343 edge succ2; | |
| 1344 edge fall_thru; | |
| 1345 edge cond_jump = NULL; | |
| 1346 edge e; | |
| 1347 bool cond_jump_crosses; | |
| 1348 int invert_worked; | |
| 1349 rtx old_jump; | |
| 1350 rtx fall_thru_label; | |
| 1351 rtx barrier; | |
| 1352 | |
| 1353 FOR_EACH_BB (cur_bb) | |
| 1354 { | |
| 1355 fall_thru = NULL; | |
| 1356 if (EDGE_COUNT (cur_bb->succs) > 0) | |
| 1357 succ1 = EDGE_SUCC (cur_bb, 0); | |
| 1358 else | |
| 1359 succ1 = NULL; | |
| 1360 | |
| 1361 if (EDGE_COUNT (cur_bb->succs) > 1) | |
| 1362 succ2 = EDGE_SUCC (cur_bb, 1); | |
| 1363 else | |
| 1364 succ2 = NULL; | |
| 1365 | |
| 1366 /* Find the fall-through edge. */ | |
| 1367 | |
| 1368 if (succ1 | |
| 1369 && (succ1->flags & EDGE_FALLTHRU)) | |
| 1370 { | |
| 1371 fall_thru = succ1; | |
| 1372 cond_jump = succ2; | |
| 1373 } | |
| 1374 else if (succ2 | |
| 1375 && (succ2->flags & EDGE_FALLTHRU)) | |
| 1376 { | |
| 1377 fall_thru = succ2; | |
| 1378 cond_jump = succ1; | |
| 1379 } | |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1380 else if (succ1 |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1381 && (block_ends_with_call_p (cur_bb) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1382 || can_throw_internal (BB_END (cur_bb)))) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1383 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1384 edge e; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1385 edge_iterator ei; |
| 0 | 1386 |
|
67
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1387 /* Find EDGE_CAN_FALLTHRU edge. */ |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1388 FOR_EACH_EDGE (e, ei, cur_bb->succs) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1389 if (e->flags & EDGE_CAN_FALLTHRU) |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1390 { |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1391 fall_thru = e; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1392 break; |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1393 } |
|
f6334be47118
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
63
diff
changeset
|
1394 } |
| 0 | 1395 |
| 1396 if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR)) | |
| 1397 { | |
| 1398 /* Check to see if the fall-thru edge is a crossing edge. */ | |
| 1399 | |
| 1400 if (fall_thru->flags & EDGE_CROSSING) | |
| 1401 { | |
| 1402 /* The fall_thru edge crosses; now check the cond jump edge, if | |
| 1403 it exists. */ | |
| 1404 | |
| 1405 cond_jump_crosses = true; | |
| 1406 invert_worked = 0; | |
| 1407 old_jump = BB_END (cur_bb); | |
| 1408 | |
| 1409 /* Find the jump instruction, if there is one. */ | |
| 1410 | |
| 1411 if (cond_jump) | |
| 1412 { | |
| 1413 if (!(cond_jump->flags & EDGE_CROSSING)) | |
| 1414 cond_jump_crosses = false; | |
| 1415 | |
| 1416 /* We know the fall-thru edge crosses; if the cond | |
| 1417 jump edge does NOT cross, and its destination is the | |
| 1418 next block in the bb order, invert the jump | |
| 1419 (i.e. fix it so the fall thru does not cross and | |
| 1420 the cond jump does). */ | |
| 1421 | |
| 1422 if (!cond_jump_crosses | |
| 1423 && cur_bb->aux == cond_jump->dest) | |
| 1424 { | |
| 1425 /* Find label in fall_thru block. We've already added | |
| 1426 any missing labels, so there must be one. */ | |
| 1427 | |
| 1428 fall_thru_label = block_label (fall_thru->dest); | |
| 1429 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1430 if (old_jump && JUMP_P (old_jump) && fall_thru_label) |
| 0 | 1431 invert_worked = invert_jump (old_jump, |
| 1432 fall_thru_label,0); | |
| 1433 if (invert_worked) | |
| 1434 { | |
| 1435 fall_thru->flags &= ~EDGE_FALLTHRU; | |
| 1436 cond_jump->flags |= EDGE_FALLTHRU; | |
| 1437 update_br_prob_note (cur_bb); | |
| 1438 e = fall_thru; | |
| 1439 fall_thru = cond_jump; | |
| 1440 cond_jump = e; | |
| 1441 cond_jump->flags |= EDGE_CROSSING; | |
| 1442 fall_thru->flags &= ~EDGE_CROSSING; | |
| 1443 } | |
| 1444 } | |
| 1445 } | |
| 1446 | |
| 1447 if (cond_jump_crosses || !invert_worked) | |
| 1448 { | |
| 1449 /* This is the case where both edges out of the basic | |
| 1450 block are crossing edges. Here we will fix up the | |
| 1451 fall through edge. The jump edge will be taken care | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1452 of later. The EDGE_CROSSING flag of fall_thru edge |
| 0 | 1453 is unset before the call to force_nonfallthru |
| 1454 function because if a new basic-block is created | |
| 1455 this edge remains in the current section boundary | |
| 1456 while the edge between new_bb and the fall_thru->dest | |
| 1457 becomes EDGE_CROSSING. */ | |
| 1458 | |
| 1459 fall_thru->flags &= ~EDGE_CROSSING; | |
| 1460 new_bb = force_nonfallthru (fall_thru); | |
| 1461 | |
| 1462 if (new_bb) | |
| 1463 { | |
| 1464 new_bb->aux = cur_bb->aux; | |
| 1465 cur_bb->aux = new_bb; | |
| 1466 | |
| 1467 /* Make sure new fall-through bb is in same | |
| 1468 partition as bb it's falling through from. */ | |
| 1469 | |
| 1470 BB_COPY_PARTITION (new_bb, cur_bb); | |
| 1471 single_succ_edge (new_bb)->flags |= EDGE_CROSSING; | |
| 1472 } | |
| 1473 else | |
| 1474 { | |
| 1475 /* If a new basic-block was not created; restore | |
| 1476 the EDGE_CROSSING flag. */ | |
| 1477 fall_thru->flags |= EDGE_CROSSING; | |
| 1478 } | |
| 1479 | |
| 1480 /* Add barrier after new jump */ | |
| 1481 | |
| 1482 if (new_bb) | |
| 1483 { | |
| 1484 barrier = emit_barrier_after (BB_END (new_bb)); | |
| 1485 new_bb->il.rtl->footer = unlink_insn_chain (barrier, | |
| 1486 barrier); | |
| 1487 } | |
| 1488 else | |
| 1489 { | |
| 1490 barrier = emit_barrier_after (BB_END (cur_bb)); | |
| 1491 cur_bb->il.rtl->footer = unlink_insn_chain (barrier, | |
| 1492 barrier); | |
| 1493 } | |
| 1494 } | |
| 1495 } | |
| 1496 } | |
| 1497 } | |
| 1498 } | |
| 1499 | |
| 1500 /* This function checks the destination block of a "crossing jump" to | |
| 1501 see if it has any crossing predecessors that begin with a code label | |
| 1502 and end with an unconditional jump. If so, it returns that predecessor | |
| 1503 block. (This is to avoid creating lots of new basic blocks that all | |
| 1504 contain unconditional jumps to the same destination). */ | |
| 1505 | |
| 1506 static basic_block | |
| 1507 find_jump_block (basic_block jump_dest) | |
| 1508 { | |
| 1509 basic_block source_bb = NULL; | |
| 1510 edge e; | |
| 1511 rtx insn; | |
| 1512 edge_iterator ei; | |
| 1513 | |
| 1514 FOR_EACH_EDGE (e, ei, jump_dest->preds) | |
| 1515 if (e->flags & EDGE_CROSSING) | |
| 1516 { | |
| 1517 basic_block src = e->src; | |
| 1518 | |
| 1519 /* Check each predecessor to see if it has a label, and contains | |
| 1520 only one executable instruction, which is an unconditional jump. | |
| 1521 If so, we can use it. */ | |
| 1522 | |
| 1523 if (LABEL_P (BB_HEAD (src))) | |
| 1524 for (insn = BB_HEAD (src); | |
| 1525 !INSN_P (insn) && insn != NEXT_INSN (BB_END (src)); | |
| 1526 insn = NEXT_INSN (insn)) | |
| 1527 { | |
| 1528 if (INSN_P (insn) | |
| 1529 && insn == BB_END (src) | |
| 1530 && JUMP_P (insn) | |
| 1531 && !any_condjump_p (insn)) | |
| 1532 { | |
| 1533 source_bb = src; | |
| 1534 break; | |
| 1535 } | |
| 1536 } | |
| 1537 | |
| 1538 if (source_bb) | |
| 1539 break; | |
| 1540 } | |
| 1541 | |
| 1542 return source_bb; | |
| 1543 } | |
| 1544 | |
| 1545 /* Find all BB's with conditional jumps that are crossing edges; | |
| 1546 insert a new bb and make the conditional jump branch to the new | |
| 1547 bb instead (make the new bb same color so conditional branch won't | |
| 1548 be a 'crossing' edge). Insert an unconditional jump from the | |
| 1549 new bb to the original destination of the conditional jump. */ | |
| 1550 | |
| 1551 static void | |
| 1552 fix_crossing_conditional_branches (void) | |
| 1553 { | |
| 1554 basic_block cur_bb; | |
| 1555 basic_block new_bb; | |
| 1556 basic_block last_bb; | |
| 1557 basic_block dest; | |
| 1558 edge succ1; | |
| 1559 edge succ2; | |
| 1560 edge crossing_edge; | |
| 1561 edge new_edge; | |
| 1562 rtx old_jump; | |
| 1563 rtx set_src; | |
| 1564 rtx old_label = NULL_RTX; | |
| 1565 rtx new_label; | |
| 1566 rtx new_jump; | |
| 1567 rtx barrier; | |
| 1568 | |
| 1569 last_bb = EXIT_BLOCK_PTR->prev_bb; | |
| 1570 | |
| 1571 FOR_EACH_BB (cur_bb) | |
| 1572 { | |
| 1573 crossing_edge = NULL; | |
| 1574 if (EDGE_COUNT (cur_bb->succs) > 0) | |
| 1575 succ1 = EDGE_SUCC (cur_bb, 0); | |
| 1576 else | |
| 1577 succ1 = NULL; | |
| 1578 | |
| 1579 if (EDGE_COUNT (cur_bb->succs) > 1) | |
| 1580 succ2 = EDGE_SUCC (cur_bb, 1); | |
| 1581 else | |
| 1582 succ2 = NULL; | |
| 1583 | |
| 1584 /* We already took care of fall-through edges, so only one successor | |
| 1585 can be a crossing edge. */ | |
| 1586 | |
| 1587 if (succ1 && (succ1->flags & EDGE_CROSSING)) | |
| 1588 crossing_edge = succ1; | |
| 1589 else if (succ2 && (succ2->flags & EDGE_CROSSING)) | |
| 1590 crossing_edge = succ2; | |
| 1591 | |
| 1592 if (crossing_edge) | |
| 1593 { | |
| 1594 old_jump = BB_END (cur_bb); | |
| 1595 | |
| 1596 /* Check to make sure the jump instruction is a | |
| 1597 conditional jump. */ | |
| 1598 | |
| 1599 set_src = NULL_RTX; | |
| 1600 | |
| 1601 if (any_condjump_p (old_jump)) | |
| 1602 { | |
| 1603 if (GET_CODE (PATTERN (old_jump)) == SET) | |
| 1604 set_src = SET_SRC (PATTERN (old_jump)); | |
| 1605 else if (GET_CODE (PATTERN (old_jump)) == PARALLEL) | |
| 1606 { | |
| 1607 set_src = XVECEXP (PATTERN (old_jump), 0,0); | |
| 1608 if (GET_CODE (set_src) == SET) | |
| 1609 set_src = SET_SRC (set_src); | |
| 1610 else | |
| 1611 set_src = NULL_RTX; | |
| 1612 } | |
| 1613 } | |
| 1614 | |
| 1615 if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE)) | |
| 1616 { | |
| 1617 if (GET_CODE (XEXP (set_src, 1)) == PC) | |
| 1618 old_label = XEXP (set_src, 2); | |
| 1619 else if (GET_CODE (XEXP (set_src, 2)) == PC) | |
| 1620 old_label = XEXP (set_src, 1); | |
| 1621 | |
| 1622 /* Check to see if new bb for jumping to that dest has | |
| 1623 already been created; if so, use it; if not, create | |
| 1624 a new one. */ | |
| 1625 | |
| 1626 new_bb = find_jump_block (crossing_edge->dest); | |
| 1627 | |
| 1628 if (new_bb) | |
| 1629 new_label = block_label (new_bb); | |
| 1630 else | |
| 1631 { | |
| 1632 /* Create new basic block to be dest for | |
| 1633 conditional jump. */ | |
| 1634 | |
| 1635 new_bb = create_basic_block (NULL, NULL, last_bb); | |
| 1636 new_bb->aux = last_bb->aux; | |
| 1637 last_bb->aux = new_bb; | |
| 1638 last_bb = new_bb; | |
| 1639 /* Put appropriate instructions in new bb. */ | |
| 1640 | |
| 1641 new_label = gen_label_rtx (); | |
| 1642 emit_label_before (new_label, BB_HEAD (new_bb)); | |
| 1643 BB_HEAD (new_bb) = new_label; | |
| 1644 | |
| 1645 if (GET_CODE (old_label) == LABEL_REF) | |
| 1646 { | |
| 1647 old_label = JUMP_LABEL (old_jump); | |
| 1648 new_jump = emit_jump_insn_after (gen_jump | |
| 1649 (old_label), | |
| 1650 BB_END (new_bb)); | |
| 1651 } | |
| 1652 else | |
| 1653 { | |
| 1654 gcc_assert (HAVE_return | |
| 1655 && GET_CODE (old_label) == RETURN); | |
| 1656 new_jump = emit_jump_insn_after (gen_return (), | |
| 1657 BB_END (new_bb)); | |
| 1658 } | |
| 1659 | |
| 1660 barrier = emit_barrier_after (new_jump); | |
| 1661 JUMP_LABEL (new_jump) = old_label; | |
| 1662 new_bb->il.rtl->footer = unlink_insn_chain (barrier, | |
| 1663 barrier); | |
| 1664 | |
| 1665 /* Make sure new bb is in same partition as source | |
| 1666 of conditional branch. */ | |
| 1667 BB_COPY_PARTITION (new_bb, cur_bb); | |
| 1668 } | |
| 1669 | |
| 1670 /* Make old jump branch to new bb. */ | |
| 1671 | |
| 1672 redirect_jump (old_jump, new_label, 0); | |
| 1673 | |
| 1674 /* Remove crossing_edge as predecessor of 'dest'. */ | |
| 1675 | |
| 1676 dest = crossing_edge->dest; | |
| 1677 | |
| 1678 redirect_edge_succ (crossing_edge, new_bb); | |
| 1679 | |
| 1680 /* Make a new edge from new_bb to old dest; new edge | |
| 1681 will be a successor for new_bb and a predecessor | |
| 1682 for 'dest'. */ | |
| 1683 | |
| 1684 if (EDGE_COUNT (new_bb->succs) == 0) | |
| 1685 new_edge = make_edge (new_bb, dest, 0); | |
| 1686 else | |
| 1687 new_edge = EDGE_SUCC (new_bb, 0); | |
| 1688 | |
| 1689 crossing_edge->flags &= ~EDGE_CROSSING; | |
| 1690 new_edge->flags |= EDGE_CROSSING; | |
| 1691 } | |
| 1692 } | |
| 1693 } | |
| 1694 } | |
| 1695 | |
| 1696 /* Find any unconditional branches that cross between hot and cold | |
| 1697 sections. Convert them into indirect jumps instead. */ | |
| 1698 | |
| 1699 static void | |
| 1700 fix_crossing_unconditional_branches (void) | |
| 1701 { | |
| 1702 basic_block cur_bb; | |
| 1703 rtx last_insn; | |
| 1704 rtx label; | |
| 1705 rtx label_addr; | |
| 1706 rtx indirect_jump_sequence; | |
| 1707 rtx jump_insn = NULL_RTX; | |
| 1708 rtx new_reg; | |
| 1709 rtx cur_insn; | |
| 1710 edge succ; | |
| 1711 | |
| 1712 FOR_EACH_BB (cur_bb) | |
| 1713 { | |
| 1714 last_insn = BB_END (cur_bb); | |
| 1715 | |
| 1716 if (EDGE_COUNT (cur_bb->succs) < 1) | |
| 1717 continue; | |
| 1718 | |
| 1719 succ = EDGE_SUCC (cur_bb, 0); | |
| 1720 | |
| 1721 /* Check to see if bb ends in a crossing (unconditional) jump. At | |
| 1722 this point, no crossing jumps should be conditional. */ | |
| 1723 | |
| 1724 if (JUMP_P (last_insn) | |
| 1725 && (succ->flags & EDGE_CROSSING)) | |
| 1726 { | |
| 1727 rtx label2, table; | |
| 1728 | |
| 1729 gcc_assert (!any_condjump_p (last_insn)); | |
| 1730 | |
| 1731 /* Make sure the jump is not already an indirect or table jump. */ | |
| 1732 | |
| 1733 if (!computed_jump_p (last_insn) | |
| 1734 && !tablejump_p (last_insn, &label2, &table)) | |
| 1735 { | |
| 1736 /* We have found a "crossing" unconditional branch. Now | |
| 1737 we must convert it to an indirect jump. First create | |
| 1738 reference of label, as target for jump. */ | |
| 1739 | |
| 1740 label = JUMP_LABEL (last_insn); | |
| 1741 label_addr = gen_rtx_LABEL_REF (Pmode, label); | |
| 1742 LABEL_NUSES (label) += 1; | |
| 1743 | |
| 1744 /* Get a register to use for the indirect jump. */ | |
| 1745 | |
| 1746 new_reg = gen_reg_rtx (Pmode); | |
| 1747 | |
| 1748 /* Generate indirect the jump sequence. */ | |
| 1749 | |
| 1750 start_sequence (); | |
| 1751 emit_move_insn (new_reg, label_addr); | |
| 1752 emit_indirect_jump (new_reg); | |
| 1753 indirect_jump_sequence = get_insns (); | |
| 1754 end_sequence (); | |
| 1755 | |
| 1756 /* Make sure every instruction in the new jump sequence has | |
| 1757 its basic block set to be cur_bb. */ | |
| 1758 | |
| 1759 for (cur_insn = indirect_jump_sequence; cur_insn; | |
| 1760 cur_insn = NEXT_INSN (cur_insn)) | |
| 1761 { | |
| 1762 if (!BARRIER_P (cur_insn)) | |
| 1763 BLOCK_FOR_INSN (cur_insn) = cur_bb; | |
| 1764 if (JUMP_P (cur_insn)) | |
| 1765 jump_insn = cur_insn; | |
| 1766 } | |
| 1767 | |
| 1768 /* Insert the new (indirect) jump sequence immediately before | |
| 1769 the unconditional jump, then delete the unconditional jump. */ | |
| 1770 | |
| 1771 emit_insn_before (indirect_jump_sequence, last_insn); | |
| 1772 delete_insn (last_insn); | |
| 1773 | |
| 1774 /* Make BB_END for cur_bb be the jump instruction (NOT the | |
| 1775 barrier instruction at the end of the sequence...). */ | |
| 1776 | |
| 1777 BB_END (cur_bb) = jump_insn; | |
| 1778 } | |
| 1779 } | |
| 1780 } | |
| 1781 } | |
| 1782 | |
| 1783 /* Add REG_CROSSING_JUMP note to all crossing jump insns. */ | |
| 1784 | |
| 1785 static void | |
| 1786 add_reg_crossing_jump_notes (void) | |
| 1787 { | |
| 1788 basic_block bb; | |
| 1789 edge e; | |
| 1790 edge_iterator ei; | |
| 1791 | |
| 1792 FOR_EACH_BB (bb) | |
| 1793 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 1794 if ((e->flags & EDGE_CROSSING) | |
| 1795 && JUMP_P (BB_END (e->src))) | |
| 1796 add_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX); | |
| 1797 } | |
| 1798 | |
| 1799 /* Hot and cold basic blocks are partitioned and put in separate | |
| 1800 sections of the .o file, to reduce paging and improve cache | |
| 1801 performance (hopefully). This can result in bits of code from the | |
| 1802 same function being widely separated in the .o file. However this | |
| 1803 is not obvious to the current bb structure. Therefore we must take | |
| 1804 care to ensure that: 1). There are no fall_thru edges that cross | |
| 1805 between sections; 2). For those architectures which have "short" | |
| 1806 conditional branches, all conditional branches that attempt to | |
| 1807 cross between sections are converted to unconditional branches; | |
| 1808 and, 3). For those architectures which have "short" unconditional | |
| 1809 branches, all unconditional branches that attempt to cross between | |
| 1810 sections are converted to indirect jumps. | |
| 1811 | |
| 1812 The code for fixing up fall_thru edges that cross between hot and | |
| 1813 cold basic blocks does so by creating new basic blocks containing | |
| 1814 unconditional branches to the appropriate label in the "other" | |
| 1815 section. The new basic block is then put in the same (hot or cold) | |
| 1816 section as the original conditional branch, and the fall_thru edge | |
| 1817 is modified to fall into the new basic block instead. By adding | |
| 1818 this level of indirection we end up with only unconditional branches | |
| 1819 crossing between hot and cold sections. | |
| 1820 | |
| 1821 Conditional branches are dealt with by adding a level of indirection. | |
| 1822 A new basic block is added in the same (hot/cold) section as the | |
| 1823 conditional branch, and the conditional branch is retargeted to the | |
| 1824 new basic block. The new basic block contains an unconditional branch | |
| 1825 to the original target of the conditional branch (in the other section). | |
| 1826 | |
| 1827 Unconditional branches are dealt with by converting them into | |
| 1828 indirect jumps. */ | |
| 1829 | |
| 1830 static void | |
| 1831 fix_edges_for_rarely_executed_code (edge *crossing_edges, | |
| 1832 int n_crossing_edges) | |
| 1833 { | |
| 1834 /* Make sure the source of any crossing edge ends in a jump and the | |
| 1835 destination of any crossing edge has a label. */ | |
| 1836 | |
| 1837 add_labels_and_missing_jumps (crossing_edges, n_crossing_edges); | |
| 1838 | |
| 1839 /* Convert all crossing fall_thru edges to non-crossing fall | |
| 1840 thrus to unconditional jumps (that jump to the original fall | |
| 1841 thru dest). */ | |
| 1842 | |
| 1843 fix_up_fall_thru_edges (); | |
| 1844 | |
| 1845 /* If the architecture does not have conditional branches that can | |
| 1846 span all of memory, convert crossing conditional branches into | |
| 1847 crossing unconditional branches. */ | |
| 1848 | |
| 1849 if (!HAS_LONG_COND_BRANCH) | |
| 1850 fix_crossing_conditional_branches (); | |
| 1851 | |
| 1852 /* If the architecture does not have unconditional branches that | |
| 1853 can span all of memory, convert crossing unconditional branches | |
| 1854 into indirect jumps. Since adding an indirect jump also adds | |
| 1855 a new register usage, update the register usage information as | |
| 1856 well. */ | |
| 1857 | |
| 1858 if (!HAS_LONG_UNCOND_BRANCH) | |
| 1859 fix_crossing_unconditional_branches (); | |
| 1860 | |
| 1861 add_reg_crossing_jump_notes (); | |
| 1862 } | |
| 1863 | |
| 1864 /* Verify, in the basic block chain, that there is at most one switch | |
| 1865 between hot/cold partitions. This is modelled on | |
| 1866 rtl_verify_flow_info_1, but it cannot go inside that function | |
| 1867 because this condition will not be true until after | |
| 1868 reorder_basic_blocks is called. */ | |
| 1869 | |
| 1870 static void | |
| 1871 verify_hot_cold_block_grouping (void) | |
| 1872 { | |
| 1873 basic_block bb; | |
| 1874 int err = 0; | |
| 1875 bool switched_sections = false; | |
| 1876 int current_partition = 0; | |
| 1877 | |
| 1878 FOR_EACH_BB (bb) | |
| 1879 { | |
| 1880 if (!current_partition) | |
| 1881 current_partition = BB_PARTITION (bb); | |
| 1882 if (BB_PARTITION (bb) != current_partition) | |
| 1883 { | |
| 1884 if (switched_sections) | |
| 1885 { | |
| 1886 error ("multiple hot/cold transitions found (bb %i)", | |
| 1887 bb->index); | |
| 1888 err = 1; | |
| 1889 } | |
| 1890 else | |
| 1891 { | |
| 1892 switched_sections = true; | |
| 1893 current_partition = BB_PARTITION (bb); | |
| 1894 } | |
| 1895 } | |
| 1896 } | |
| 1897 | |
| 1898 gcc_assert(!err); | |
| 1899 } | |
| 1900 | |
| 1901 /* Reorder basic blocks. The main entry point to this file. FLAGS is | |
| 1902 the set of flags to pass to cfg_layout_initialize(). */ | |
| 1903 | |
| 1904 void | |
| 1905 reorder_basic_blocks (void) | |
| 1906 { | |
| 1907 int n_traces; | |
| 1908 int i; | |
| 1909 struct trace *traces; | |
| 1910 | |
| 1911 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT); | |
| 1912 | |
| 1913 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1) | |
| 1914 return; | |
| 1915 | |
| 1916 set_edge_can_fallthru_flag (); | |
| 1917 mark_dfs_back_edges (); | |
| 1918 | |
| 1919 /* We are estimating the length of uncond jump insn only once since the code | |
| 1920 for getting the insn length always returns the minimal length now. */ | |
| 1921 if (uncond_jump_length == 0) | |
| 1922 uncond_jump_length = get_uncond_jump_length (); | |
| 1923 | |
| 1924 /* We need to know some information for each basic block. */ | |
| 1925 array_size = GET_ARRAY_SIZE (last_basic_block); | |
| 1926 bbd = XNEWVEC (bbro_basic_block_data, array_size); | |
| 1927 for (i = 0; i < array_size; i++) | |
| 1928 { | |
| 1929 bbd[i].start_of_trace = -1; | |
| 1930 bbd[i].in_trace = -1; | |
| 1931 bbd[i].end_of_trace = -1; | |
| 1932 bbd[i].heap = NULL; | |
| 1933 bbd[i].node = NULL; | |
| 1934 } | |
| 1935 | |
| 1936 traces = XNEWVEC (struct trace, n_basic_blocks); | |
| 1937 n_traces = 0; | |
| 1938 find_traces (&n_traces, traces); | |
| 1939 connect_traces (n_traces, traces); | |
| 1940 FREE (traces); | |
| 1941 FREE (bbd); | |
| 1942 | |
| 1943 relink_block_chain (/*stay_in_cfglayout_mode=*/true); | |
| 1944 | |
| 1945 if (dump_file) | |
| 1946 dump_flow_info (dump_file, dump_flags); | |
| 1947 | |
| 1948 if (flag_reorder_blocks_and_partition) | |
| 1949 verify_hot_cold_block_grouping (); | |
| 1950 } | |
| 1951 | |
| 1952 /* Determine which partition the first basic block in the function | |
| 1953 belongs to, then find the first basic block in the current function | |
| 1954 that belongs to a different section, and insert a | |
| 1955 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the | |
| 1956 instruction stream. When writing out the assembly code, | |
| 1957 encountering this note will make the compiler switch between the | |
| 1958 hot and cold text sections. */ | |
| 1959 | |
| 1960 static void | |
| 1961 insert_section_boundary_note (void) | |
| 1962 { | |
| 1963 basic_block bb; | |
| 1964 rtx new_note; | |
| 1965 int first_partition = 0; | |
| 1966 | |
| 1967 if (flag_reorder_blocks_and_partition) | |
| 1968 FOR_EACH_BB (bb) | |
| 1969 { | |
| 1970 if (!first_partition) | |
| 1971 first_partition = BB_PARTITION (bb); | |
| 1972 if (BB_PARTITION (bb) != first_partition) | |
| 1973 { | |
| 1974 new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS, | |
| 1975 BB_HEAD (bb)); | |
| 1976 /* ??? This kind of note always lives between basic blocks, | |
| 1977 but add_insn_before will set BLOCK_FOR_INSN anyway. */ | |
| 1978 BLOCK_FOR_INSN (new_note) = NULL; | |
| 1979 break; | |
| 1980 } | |
| 1981 } | |
| 1982 } | |
| 1983 | |
| 1984 /* Duplicate the blocks containing computed gotos. This basically unfactors | |
| 1985 computed gotos that were factored early on in the compilation process to | |
| 1986 speed up edge based data flow. We used to not unfactoring them again, | |
| 1987 which can seriously pessimize code with many computed jumps in the source | |
| 1988 code, such as interpreters. See e.g. PR15242. */ | |
| 1989 | |
| 1990 static bool | |
| 1991 gate_duplicate_computed_gotos (void) | |
| 1992 { | |
| 1993 if (targetm.cannot_modify_jumps_p ()) | |
| 1994 return false; | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1995 return (optimize > 0 |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1996 && flag_expensive_optimizations |
|
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
55
diff
changeset
|
1997 && ! optimize_function_for_size_p (cfun)); |
| 0 | 1998 } |
| 1999 | |
| 2000 | |
| 2001 static unsigned int | |
| 2002 duplicate_computed_gotos (void) | |
| 2003 { | |
| 2004 basic_block bb, new_bb; | |
| 2005 bitmap candidates; | |
| 2006 int max_size; | |
| 2007 | |
| 2008 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1) | |
| 2009 return 0; | |
| 2010 | |
| 2011 cfg_layout_initialize (0); | |
| 2012 | |
| 2013 /* We are estimating the length of uncond jump insn only once | |
| 2014 since the code for getting the insn length always returns | |
| 2015 the minimal length now. */ | |
| 2016 if (uncond_jump_length == 0) | |
| 2017 uncond_jump_length = get_uncond_jump_length (); | |
| 2018 | |
| 2019 max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS); | |
| 2020 candidates = BITMAP_ALLOC (NULL); | |
| 2021 | |
| 2022 /* Look for blocks that end in a computed jump, and see if such blocks | |
| 2023 are suitable for unfactoring. If a block is a candidate for unfactoring, | |
| 2024 mark it in the candidates. */ | |
| 2025 FOR_EACH_BB (bb) | |
| 2026 { | |
| 2027 rtx insn; | |
| 2028 edge e; | |
| 2029 edge_iterator ei; | |
| 2030 int size, all_flags; | |
| 2031 | |
| 2032 /* Build the reorder chain for the original order of blocks. */ | |
| 2033 if (bb->next_bb != EXIT_BLOCK_PTR) | |
| 2034 bb->aux = bb->next_bb; | |
| 2035 | |
| 2036 /* Obviously the block has to end in a computed jump. */ | |
| 2037 if (!computed_jump_p (BB_END (bb))) | |
| 2038 continue; | |
| 2039 | |
| 2040 /* Only consider blocks that can be duplicated. */ | |
| 2041 if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX) | |
| 2042 || !can_duplicate_block_p (bb)) | |
| 2043 continue; | |
| 2044 | |
| 2045 /* Make sure that the block is small enough. */ | |
| 2046 size = 0; | |
| 2047 FOR_BB_INSNS (bb, insn) | |
| 2048 if (INSN_P (insn)) | |
| 2049 { | |
| 2050 size += get_attr_min_length (insn); | |
| 2051 if (size > max_size) | |
| 2052 break; | |
| 2053 } | |
| 2054 if (size > max_size) | |
| 2055 continue; | |
| 2056 | |
| 2057 /* Final check: there must not be any incoming abnormal edges. */ | |
| 2058 all_flags = 0; | |
| 2059 FOR_EACH_EDGE (e, ei, bb->preds) | |
| 2060 all_flags |= e->flags; | |
| 2061 if (all_flags & EDGE_COMPLEX) | |
| 2062 continue; | |
| 2063 | |
| 2064 bitmap_set_bit (candidates, bb->index); | |
| 2065 } | |
| 2066 | |
| 2067 /* Nothing to do if there is no computed jump here. */ | |
| 2068 if (bitmap_empty_p (candidates)) | |
| 2069 goto done; | |
| 2070 | |
| 2071 /* Duplicate computed gotos. */ | |
| 2072 FOR_EACH_BB (bb) | |
| 2073 { | |
| 2074 if (bb->il.rtl->visited) | |
| 2075 continue; | |
| 2076 | |
| 2077 bb->il.rtl->visited = 1; | |
| 2078 | |
| 2079 /* BB must have one outgoing edge. That edge must not lead to | |
| 2080 the exit block or the next block. | |
| 2081 The destination must have more than one predecessor. */ | |
| 2082 if (!single_succ_p (bb) | |
| 2083 || single_succ (bb) == EXIT_BLOCK_PTR | |
| 2084 || single_succ (bb) == bb->next_bb | |
| 2085 || single_pred_p (single_succ (bb))) | |
| 2086 continue; | |
| 2087 | |
| 2088 /* The successor block has to be a duplication candidate. */ | |
| 2089 if (!bitmap_bit_p (candidates, single_succ (bb)->index)) | |
| 2090 continue; | |
| 2091 | |
| 2092 new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb); | |
| 2093 new_bb->aux = bb->aux; | |
| 2094 bb->aux = new_bb; | |
| 2095 new_bb->il.rtl->visited = 1; | |
| 2096 } | |
| 2097 | |
| 2098 done: | |
| 2099 cfg_layout_finalize (); | |
| 2100 | |
| 2101 BITMAP_FREE (candidates); | |
| 2102 return 0; | |
| 2103 } | |
| 2104 | |
| 2105 struct rtl_opt_pass pass_duplicate_computed_gotos = | |
| 2106 { | |
| 2107 { | |
| 2108 RTL_PASS, | |
| 2109 "compgotos", /* name */ | |
| 2110 gate_duplicate_computed_gotos, /* gate */ | |
| 2111 duplicate_computed_gotos, /* execute */ | |
| 2112 NULL, /* sub */ | |
| 2113 NULL, /* next */ | |
| 2114 0, /* static_pass_number */ | |
| 2115 TV_REORDER_BLOCKS, /* tv_id */ | |
| 2116 0, /* properties_required */ | |
| 2117 0, /* properties_provided */ | |
| 2118 0, /* properties_destroyed */ | |
| 2119 0, /* todo_flags_start */ | |
| 2120 TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */ | |
| 2121 } | |
| 2122 }; | |
| 2123 | |
| 2124 | |
| 2125 /* This function is the main 'entrance' for the optimization that | |
| 2126 partitions hot and cold basic blocks into separate sections of the | |
| 2127 .o file (to improve performance and cache locality). Ideally it | |
| 2128 would be called after all optimizations that rearrange the CFG have | |
| 2129 been called. However part of this optimization may introduce new | |
| 2130 register usage, so it must be called before register allocation has | |
| 2131 occurred. This means that this optimization is actually called | |
| 2132 well before the optimization that reorders basic blocks (see | |
| 2133 function above). | |
| 2134 | |
| 2135 This optimization checks the feedback information to determine | |
| 2136 which basic blocks are hot/cold, updates flags on the basic blocks | |
| 2137 to indicate which section they belong in. This information is | |
| 2138 later used for writing out sections in the .o file. Because hot | |
| 2139 and cold sections can be arbitrarily large (within the bounds of | |
| 2140 memory), far beyond the size of a single function, it is necessary | |
| 2141 to fix up all edges that cross section boundaries, to make sure the | |
| 2142 instructions used can actually span the required distance. The | |
| 2143 fixes are described below. | |
| 2144 | |
| 2145 Fall-through edges must be changed into jumps; it is not safe or | |
| 2146 legal to fall through across a section boundary. Whenever a | |
| 2147 fall-through edge crossing a section boundary is encountered, a new | |
| 2148 basic block is inserted (in the same section as the fall-through | |
| 2149 source), and the fall through edge is redirected to the new basic | |
| 2150 block. The new basic block contains an unconditional jump to the | |
| 2151 original fall-through target. (If the unconditional jump is | |
| 2152 insufficient to cross section boundaries, that is dealt with a | |
| 2153 little later, see below). | |
| 2154 | |
| 2155 In order to deal with architectures that have short conditional | |
| 2156 branches (which cannot span all of memory) we take any conditional | |
| 2157 jump that attempts to cross a section boundary and add a level of | |
| 2158 indirection: it becomes a conditional jump to a new basic block, in | |
| 2159 the same section. The new basic block contains an unconditional | |
| 2160 jump to the original target, in the other section. | |
| 2161 | |
| 2162 For those architectures whose unconditional branch is also | |
| 2163 incapable of reaching all of memory, those unconditional jumps are | |
| 2164 converted into indirect jumps, through a register. | |
| 2165 | |
| 2166 IMPORTANT NOTE: This optimization causes some messy interactions | |
| 2167 with the cfg cleanup optimizations; those optimizations want to | |
| 2168 merge blocks wherever possible, and to collapse indirect jump | |
| 2169 sequences (change "A jumps to B jumps to C" directly into "A jumps | |
| 2170 to C"). Those optimizations can undo the jump fixes that | |
| 2171 partitioning is required to make (see above), in order to ensure | |
| 2172 that jumps attempting to cross section boundaries are really able | |
| 2173 to cover whatever distance the jump requires (on many architectures | |
| 2174 conditional or unconditional jumps are not able to reach all of | |
| 2175 memory). Therefore tests have to be inserted into each such | |
| 2176 optimization to make sure that it does not undo stuff necessary to | |
| 2177 cross partition boundaries. This would be much less of a problem | |
| 2178 if we could perform this optimization later in the compilation, but | |
| 2179 unfortunately the fact that we may need to create indirect jumps | |
| 2180 (through registers) requires that this optimization be performed | |
| 2181 before register allocation. */ | |
| 2182 | |
| 2183 static void | |
| 2184 partition_hot_cold_basic_blocks (void) | |
| 2185 { | |
| 2186 edge *crossing_edges; | |
| 2187 int n_crossing_edges; | |
| 2188 int max_edges = 2 * last_basic_block; | |
| 2189 | |
| 2190 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1) | |
| 2191 return; | |
| 2192 | |
| 2193 crossing_edges = XCNEWVEC (edge, max_edges); | |
| 2194 | |
| 2195 find_rarely_executed_basic_blocks_and_crossing_edges (&crossing_edges, | |
| 2196 &n_crossing_edges, | |
| 2197 &max_edges); | |
| 2198 | |
| 2199 if (n_crossing_edges > 0) | |
| 2200 fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges); | |
| 2201 | |
| 2202 free (crossing_edges); | |
| 2203 } | |
| 2204 | |
| 2205 static bool | |
| 2206 gate_handle_reorder_blocks (void) | |
| 2207 { | |
| 2208 if (targetm.cannot_modify_jumps_p ()) | |
| 2209 return false; | |
| 2210 return (optimize > 0); | |
| 2211 } | |
| 2212 | |
| 2213 | |
| 2214 /* Reorder basic blocks. */ | |
| 2215 static unsigned int | |
| 2216 rest_of_handle_reorder_blocks (void) | |
| 2217 { | |
| 2218 basic_block bb; | |
| 2219 | |
| 2220 /* Last attempt to optimize CFG, as scheduling, peepholing and insn | |
| 2221 splitting possibly introduced more crossjumping opportunities. */ | |
| 2222 cfg_layout_initialize (CLEANUP_EXPENSIVE); | |
| 2223 | |
| 2224 if ((flag_reorder_blocks || flag_reorder_blocks_and_partition) | |
| 2225 /* Don't reorder blocks when optimizing for size because extra jump insns may | |
| 2226 be created; also barrier may create extra padding. | |
| 2227 | |
| 2228 More correctly we should have a block reordering mode that tried to | |
| 2229 minimize the combined size of all the jumps. This would more or less | |
| 2230 automatically remove extra jumps, but would also try to use more short | |
| 2231 jumps instead of long jumps. */ | |
| 2232 && optimize_function_for_speed_p (cfun)) | |
| 2233 { | |
| 2234 reorder_basic_blocks (); | |
| 2235 cleanup_cfg (CLEANUP_EXPENSIVE); | |
| 2236 } | |
| 2237 | |
| 2238 FOR_EACH_BB (bb) | |
| 2239 if (bb->next_bb != EXIT_BLOCK_PTR) | |
| 2240 bb->aux = bb->next_bb; | |
| 2241 cfg_layout_finalize (); | |
| 2242 | |
| 2243 /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */ | |
| 2244 insert_section_boundary_note (); | |
| 2245 return 0; | |
| 2246 } | |
| 2247 | |
| 2248 struct rtl_opt_pass pass_reorder_blocks = | |
| 2249 { | |
| 2250 { | |
| 2251 RTL_PASS, | |
| 2252 "bbro", /* name */ | |
| 2253 gate_handle_reorder_blocks, /* gate */ | |
| 2254 rest_of_handle_reorder_blocks, /* execute */ | |
| 2255 NULL, /* sub */ | |
| 2256 NULL, /* next */ | |
| 2257 0, /* static_pass_number */ | |
| 2258 TV_REORDER_BLOCKS, /* tv_id */ | |
| 2259 0, /* properties_required */ | |
| 2260 0, /* properties_provided */ | |
| 2261 0, /* properties_destroyed */ | |
| 2262 0, /* todo_flags_start */ | |
| 2263 TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */ | |
| 2264 } | |
| 2265 }; | |
| 2266 | |
| 2267 static bool | |
| 2268 gate_handle_partition_blocks (void) | |
| 2269 { | |
| 2270 /* The optimization to partition hot/cold basic blocks into separate | |
| 2271 sections of the .o file does not work well with linkonce or with | |
| 2272 user defined section attributes. Don't call it if either case | |
| 2273 arises. */ | |
| 2274 | |
| 2275 return (flag_reorder_blocks_and_partition | |
| 2276 && !DECL_ONE_ONLY (current_function_decl) | |
| 2277 && !user_defined_section_attribute); | |
| 2278 } | |
| 2279 | |
| 2280 /* Partition hot and cold basic blocks. */ | |
| 2281 static unsigned int | |
| 2282 rest_of_handle_partition_blocks (void) | |
| 2283 { | |
| 2284 partition_hot_cold_basic_blocks (); | |
| 2285 return 0; | |
| 2286 } | |
| 2287 | |
| 2288 struct rtl_opt_pass pass_partition_blocks = | |
| 2289 { | |
| 2290 { | |
| 2291 RTL_PASS, | |
| 2292 "bbpart", /* name */ | |
| 2293 gate_handle_partition_blocks, /* gate */ | |
| 2294 rest_of_handle_partition_blocks, /* execute */ | |
| 2295 NULL, /* sub */ | |
| 2296 NULL, /* next */ | |
| 2297 0, /* static_pass_number */ | |
| 2298 TV_REORDER_BLOCKS, /* tv_id */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2299 PROP_cfglayout, /* properties_required */ |
| 0 | 2300 0, /* properties_provided */ |
| 2301 0, /* properties_destroyed */ | |
| 2302 0, /* todo_flags_start */ | |
| 2303 TODO_dump_func | TODO_verify_rtl_sharing/* todo_flags_finish */ | |
| 2304 } | |
| 2305 }; |