2013-02-25 Tom de Vries <tom@codesourcery.com>
[official-gcc.git] / gcc / bb-reorder.c
blob20c25bd59e5b1d3b0de5124278bffe246587bf31
1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000-2013 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This (greedy) algorithm constructs traces in several rounds.
21 The construction starts from "seeds". The seed for the first round
22 is the entry point of the function. When there are more than one seed,
23 the one with the lowest key in the heap is selected first (see bb_to_key).
24 Then the algorithm repeatedly adds the most probable successor to the end
25 of a trace. Finally it connects the traces.
27 There are two parameters: Branch Threshold and Exec Threshold.
28 If the probability of an edge to a successor of the current basic block is
29 lower than Branch Threshold or its frequency is lower than Exec Threshold,
30 then the successor will be the seed in one of the next rounds.
31 Each round has these parameters lower than the previous one.
32 The last round has to have these parameters set to zero so that the
33 remaining blocks are picked up.
35 The algorithm selects the most probable successor from all unvisited
36 successors and successors that have been added to this trace.
37 The other successors (that has not been "sent" to the next round) will be
38 other seeds for this round and the secondary traces will start from them.
39 If the successor has not been visited in this trace, it is added to the
40 trace (however, there is some heuristic for simple branches).
41 If the successor has been visited in this trace, a loop has been found.
42 If the loop has many iterations, the loop is rotated so that the source
43 block of the most probable edge going out of the loop is the last block
44 of the trace.
45 If the loop has few iterations and there is no edge from the last block of
46 the loop going out of the loop, the loop header is duplicated.
48 When connecting traces, the algorithm first checks whether there is an edge
49 from the last block of a trace to the first block of another trace.
50 When there are still some unconnected traces it checks whether there exists
51 a basic block BB such that BB is a successor of the last block of a trace
52 and BB is a predecessor of the first block of another trace. In this case,
53 BB is duplicated, added at the end of the first trace and the traces are
54 connected through it.
55 The rest of traces are simply connected so there will be a jump to the
56 beginning of the rest of traces.
58 The above description is for the full algorithm, which is used when the
59 function is optimized for speed. When the function is optimized for size,
60 in order to reduce long jumps and connect more fallthru edges, the
61 algorithm is modified as follows:
62 (1) Break long traces to short ones. A trace is broken at a block that has
63 multiple predecessors/ successors during trace discovery. When connecting
64 traces, only connect Trace n with Trace n + 1. This change reduces most
65 long jumps compared with the above algorithm.
66 (2) Ignore the edge probability and frequency for fallthru edges.
67 (3) Keep the original order of blocks when there is no chance to fall
68 through. We rely on the results of cfg_cleanup.
70 To implement the change for code size optimization, block's index is
71 selected as the key and all traces are found in one round.
73 References:
75 "Software Trace Cache"
76 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
77 http://citeseer.nj.nec.com/15361.html
81 #include "config.h"
82 #include "system.h"
83 #include "coretypes.h"
84 #include "tm.h"
85 #include "rtl.h"
86 #include "regs.h"
87 #include "flags.h"
88 #include "output.h"
89 #include "fibheap.h"
90 #include "target.h"
91 #include "function.h"
92 #include "tm_p.h"
93 #include "obstack.h"
94 #include "expr.h"
95 #include "params.h"
96 #include "diagnostic-core.h"
97 #include "toplev.h" /* user_defined_section_attribute */
98 #include "tree-pass.h"
99 #include "df.h"
100 #include "bb-reorder.h"
101 #include "except.h"
103 /* The number of rounds. In most cases there will only be 4 rounds, but
104 when partitioning hot and cold basic blocks into separate sections of
105 the object file there will be an extra round. */
106 #define N_ROUNDS 5
108 /* Stubs in case we don't have a return insn.
109 We have to check at run time too, not only compile time. */
111 #ifndef HAVE_return
112 #define HAVE_return 0
113 #define gen_return() NULL_RTX
114 #endif
117 struct target_bb_reorder default_target_bb_reorder;
118 #if SWITCHABLE_TARGET
119 struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder;
120 #endif
122 #define uncond_jump_length \
123 (this_target_bb_reorder->x_uncond_jump_length)
125 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
126 static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
128 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
129 static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
131 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
132 block the edge destination is not duplicated while connecting traces. */
133 #define DUPLICATION_THRESHOLD 100
135 /* Structure to hold needed information for each basic block. */
136 typedef struct bbro_basic_block_data_def
138 /* Which trace is the bb start of (-1 means it is not a start of any). */
139 int start_of_trace;
141 /* Which trace is the bb end of (-1 means it is not an end of any). */
142 int end_of_trace;
144 /* Which trace is the bb in? */
145 int in_trace;
147 /* Which trace was this bb visited in? */
148 int visited;
150 /* Which heap is BB in (if any)? */
151 fibheap_t heap;
153 /* Which heap node is BB in (if any)? */
154 fibnode_t node;
155 } bbro_basic_block_data;
157 /* The current size of the following dynamic array. */
158 static int array_size;
160 /* The array which holds needed information for basic blocks. */
161 static bbro_basic_block_data *bbd;
163 /* To avoid frequent reallocation the size of arrays is greater than needed,
164 the number of elements is (not less than) 1.25 * size_wanted. */
165 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
167 /* Free the memory and set the pointer to NULL. */
168 #define FREE(P) (gcc_assert (P), free (P), P = 0)
170 /* Structure for holding information about a trace. */
171 struct trace
173 /* First and last basic block of the trace. */
174 basic_block first, last;
176 /* The round of the STC creation which this trace was found in. */
177 int round;
179 /* The length (i.e. the number of basic blocks) of the trace. */
180 int length;
183 /* Maximum frequency and count of one of the entry blocks. */
184 static int max_entry_frequency;
185 static gcov_type max_entry_count;
187 /* Local function prototypes. */
188 static void find_traces (int *, struct trace *);
189 static basic_block rotate_loop (edge, struct trace *, int);
190 static void mark_bb_visited (basic_block, int);
191 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
192 int, fibheap_t *, int);
193 static basic_block copy_bb (basic_block, edge, basic_block, int);
194 static fibheapkey_t bb_to_key (basic_block);
195 static bool better_edge_p (const_basic_block, const_edge, int, int, int, int,
196 const_edge);
197 static bool connect_better_edge_p (const_edge, bool, int, const_edge,
198 struct trace *);
199 static void connect_traces (int, struct trace *);
200 static bool copy_bb_p (const_basic_block, int);
201 static bool push_to_next_round_p (const_basic_block, int, int, int, gcov_type);
203 /* Return the trace number in which BB was visited. */
205 static int
206 bb_visited_trace (const_basic_block bb)
208 gcc_assert (bb->index < array_size);
209 return bbd[bb->index].visited;
212 /* This function marks BB that it was visited in trace number TRACE. */
214 static void
215 mark_bb_visited (basic_block bb, int trace)
217 bbd[bb->index].visited = trace;
218 if (bbd[bb->index].heap)
220 fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
221 bbd[bb->index].heap = NULL;
222 bbd[bb->index].node = NULL;
226 /* Check to see if bb should be pushed into the next round of trace
227 collections or not. Reasons for pushing the block forward are 1).
228 If the block is cold, we are doing partitioning, and there will be
229 another round (cold partition blocks are not supposed to be
230 collected into traces until the very last round); or 2). There will
231 be another round, and the basic block is not "hot enough" for the
232 current round of trace collection. */
234 static bool
235 push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
236 int exec_th, gcov_type count_th)
238 bool there_exists_another_round;
239 bool block_not_hot_enough;
241 there_exists_another_round = round < number_of_rounds - 1;
243 block_not_hot_enough = (bb->frequency < exec_th
244 || bb->count < count_th
245 || probably_never_executed_bb_p (cfun, bb));
247 if (there_exists_another_round
248 && block_not_hot_enough)
249 return true;
250 else
251 return false;
254 /* Find the traces for Software Trace Cache. Chain each trace through
255 RBI()->next. Store the number of traces to N_TRACES and description of
256 traces to TRACES. */
258 static void
259 find_traces (int *n_traces, struct trace *traces)
261 int i;
262 int number_of_rounds;
263 edge e;
264 edge_iterator ei;
265 fibheap_t heap;
267 /* Add one extra round of trace collection when partitioning hot/cold
268 basic blocks into separate sections. The last round is for all the
269 cold blocks (and ONLY the cold blocks). */
271 number_of_rounds = N_ROUNDS - 1;
273 /* Insert entry points of function into heap. */
274 heap = fibheap_new ();
275 max_entry_frequency = 0;
276 max_entry_count = 0;
277 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
279 bbd[e->dest->index].heap = heap;
280 bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
281 e->dest);
282 if (e->dest->frequency > max_entry_frequency)
283 max_entry_frequency = e->dest->frequency;
284 if (e->dest->count > max_entry_count)
285 max_entry_count = e->dest->count;
288 /* Find the traces. */
289 for (i = 0; i < number_of_rounds; i++)
291 gcov_type count_threshold;
293 if (dump_file)
294 fprintf (dump_file, "STC - round %d\n", i + 1);
296 if (max_entry_count < INT_MAX / 1000)
297 count_threshold = max_entry_count * exec_threshold[i] / 1000;
298 else
299 count_threshold = max_entry_count / 1000 * exec_threshold[i];
301 find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
302 max_entry_frequency * exec_threshold[i] / 1000,
303 count_threshold, traces, n_traces, i, &heap,
304 number_of_rounds);
306 fibheap_delete (heap);
308 if (dump_file)
310 for (i = 0; i < *n_traces; i++)
312 basic_block bb;
313 fprintf (dump_file, "Trace %d (round %d): ", i + 1,
314 traces[i].round + 1);
315 for (bb = traces[i].first;
316 bb != traces[i].last;
317 bb = (basic_block) bb->aux)
318 fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
319 fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
321 fflush (dump_file);
325 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
326 (with sequential number TRACE_N). */
328 static basic_block
329 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
331 basic_block bb;
333 /* Information about the best end (end after rotation) of the loop. */
334 basic_block best_bb = NULL;
335 edge best_edge = NULL;
336 int best_freq = -1;
337 gcov_type best_count = -1;
338 /* The best edge is preferred when its destination is not visited yet
339 or is a start block of some trace. */
340 bool is_preferred = false;
342 /* Find the most frequent edge that goes out from current trace. */
343 bb = back_edge->dest;
346 edge e;
347 edge_iterator ei;
349 FOR_EACH_EDGE (e, ei, bb->succs)
350 if (e->dest != EXIT_BLOCK_PTR
351 && bb_visited_trace (e->dest) != trace_n
352 && (e->flags & EDGE_CAN_FALLTHRU)
353 && !(e->flags & EDGE_COMPLEX))
355 if (is_preferred)
357 /* The best edge is preferred. */
358 if (!bb_visited_trace (e->dest)
359 || bbd[e->dest->index].start_of_trace >= 0)
361 /* The current edge E is also preferred. */
362 int freq = EDGE_FREQUENCY (e);
363 if (freq > best_freq || e->count > best_count)
365 best_freq = freq;
366 best_count = e->count;
367 best_edge = e;
368 best_bb = bb;
372 else
374 if (!bb_visited_trace (e->dest)
375 || bbd[e->dest->index].start_of_trace >= 0)
377 /* The current edge E is preferred. */
378 is_preferred = true;
379 best_freq = EDGE_FREQUENCY (e);
380 best_count = e->count;
381 best_edge = e;
382 best_bb = bb;
384 else
386 int freq = EDGE_FREQUENCY (e);
387 if (!best_edge || freq > best_freq || e->count > best_count)
389 best_freq = freq;
390 best_count = e->count;
391 best_edge = e;
392 best_bb = bb;
397 bb = (basic_block) bb->aux;
399 while (bb != back_edge->dest);
401 if (best_bb)
403 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
404 the trace. */
405 if (back_edge->dest == trace->first)
407 trace->first = (basic_block) best_bb->aux;
409 else
411 basic_block prev_bb;
413 for (prev_bb = trace->first;
414 prev_bb->aux != back_edge->dest;
415 prev_bb = (basic_block) prev_bb->aux)
417 prev_bb->aux = best_bb->aux;
419 /* Try to get rid of uncond jump to cond jump. */
420 if (single_succ_p (prev_bb))
422 basic_block header = single_succ (prev_bb);
424 /* Duplicate HEADER if it is a small block containing cond jump
425 in the end. */
426 if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
427 && !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
428 NULL_RTX))
429 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
433 else
435 /* We have not found suitable loop tail so do no rotation. */
436 best_bb = back_edge->src;
438 best_bb->aux = NULL;
439 return best_bb;
442 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
443 not include basic blocks whose probability is lower than BRANCH_TH or whose
444 frequency is lower than EXEC_TH into traces (or whose count is lower than
445 COUNT_TH). Store the new traces into TRACES and modify the number of
446 traces *N_TRACES. Set the round (which the trace belongs to) to ROUND.
447 The function expects starting basic blocks to be in *HEAP and will delete
448 *HEAP and store starting points for the next round into new *HEAP. */
450 static void
451 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
452 struct trace *traces, int *n_traces, int round,
453 fibheap_t *heap, int number_of_rounds)
455 /* Heap for discarded basic blocks which are possible starting points for
456 the next round. */
457 fibheap_t new_heap = fibheap_new ();
458 bool for_size = optimize_function_for_size_p (cfun);
460 while (!fibheap_empty (*heap))
462 basic_block bb;
463 struct trace *trace;
464 edge best_edge, e;
465 fibheapkey_t key;
466 edge_iterator ei;
468 bb = (basic_block) fibheap_extract_min (*heap);
469 bbd[bb->index].heap = NULL;
470 bbd[bb->index].node = NULL;
472 if (dump_file)
473 fprintf (dump_file, "Getting bb %d\n", bb->index);
475 /* If the BB's frequency is too low, send BB to the next round. When
476 partitioning hot/cold blocks into separate sections, make sure all
477 the cold blocks (and ONLY the cold blocks) go into the (extra) final
478 round. When optimizing for size, do not push to next round. */
480 if (!for_size
481 && push_to_next_round_p (bb, round, number_of_rounds, exec_th,
482 count_th))
484 int key = bb_to_key (bb);
485 bbd[bb->index].heap = new_heap;
486 bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
488 if (dump_file)
489 fprintf (dump_file,
490 " Possible start point of next round: %d (key: %d)\n",
491 bb->index, key);
492 continue;
495 trace = traces + *n_traces;
496 trace->first = bb;
497 trace->round = round;
498 trace->length = 0;
499 bbd[bb->index].in_trace = *n_traces;
500 (*n_traces)++;
504 int prob, freq;
505 bool ends_in_call;
507 /* The probability and frequency of the best edge. */
508 int best_prob = INT_MIN / 2;
509 int best_freq = INT_MIN / 2;
511 best_edge = NULL;
512 mark_bb_visited (bb, *n_traces);
513 trace->length++;
515 if (dump_file)
516 fprintf (dump_file, "Basic block %d was visited in trace %d\n",
517 bb->index, *n_traces - 1);
519 ends_in_call = block_ends_with_call_p (bb);
521 /* Select the successor that will be placed after BB. */
522 FOR_EACH_EDGE (e, ei, bb->succs)
524 gcc_assert (!(e->flags & EDGE_FAKE));
526 if (e->dest == EXIT_BLOCK_PTR)
527 continue;
529 if (bb_visited_trace (e->dest)
530 && bb_visited_trace (e->dest) != *n_traces)
531 continue;
533 if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
534 continue;
536 prob = e->probability;
537 freq = e->dest->frequency;
539 /* The only sensible preference for a call instruction is the
540 fallthru edge. Don't bother selecting anything else. */
541 if (ends_in_call)
543 if (e->flags & EDGE_CAN_FALLTHRU)
545 best_edge = e;
546 best_prob = prob;
547 best_freq = freq;
549 continue;
552 /* Edge that cannot be fallthru or improbable or infrequent
553 successor (i.e. it is unsuitable successor). When optimizing
554 for size, ignore the probability and frequency. */
555 if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
556 || ((prob < branch_th || EDGE_FREQUENCY (e) < exec_th
557 || e->count < count_th) && (!for_size)))
558 continue;
560 /* If partitioning hot/cold basic blocks, don't consider edges
561 that cross section boundaries. */
563 if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
564 best_edge))
566 best_edge = e;
567 best_prob = prob;
568 best_freq = freq;
572 /* If the best destination has multiple predecessors, and can be
573 duplicated cheaper than a jump, don't allow it to be added
574 to a trace. We'll duplicate it when connecting traces. */
575 if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2
576 && copy_bb_p (best_edge->dest, 0))
577 best_edge = NULL;
579 /* If the best destination has multiple successors or predecessors,
580 don't allow it to be added when optimizing for size. This makes
581 sure predecessors with smaller index are handled before the best
582 destinarion. It breaks long trace and reduces long jumps.
584 Take if-then-else as an example.
590 If we do not remove the best edge B->D/C->D, the final order might
591 be A B D ... C. C is at the end of the program. If D's successors
592 and D are complicated, might need long jumps for A->C and C->D.
593 Similar issue for order: A C D ... B.
595 After removing the best edge, the final result will be ABCD/ ACBD.
596 It does not add jump compared with the previous order. But it
597 reduces the possiblity of long jumps. */
598 if (best_edge && for_size
599 && (EDGE_COUNT (best_edge->dest->succs) > 1
600 || EDGE_COUNT (best_edge->dest->preds) > 1))
601 best_edge = NULL;
603 /* Add all non-selected successors to the heaps. */
604 FOR_EACH_EDGE (e, ei, bb->succs)
606 if (e == best_edge
607 || e->dest == EXIT_BLOCK_PTR
608 || bb_visited_trace (e->dest))
609 continue;
611 key = bb_to_key (e->dest);
613 if (bbd[e->dest->index].heap)
615 /* E->DEST is already in some heap. */
616 if (key != bbd[e->dest->index].node->key)
618 if (dump_file)
620 fprintf (dump_file,
621 "Changing key for bb %d from %ld to %ld.\n",
622 e->dest->index,
623 (long) bbd[e->dest->index].node->key,
624 key);
626 fibheap_replace_key (bbd[e->dest->index].heap,
627 bbd[e->dest->index].node, key);
630 else
632 fibheap_t which_heap = *heap;
634 prob = e->probability;
635 freq = EDGE_FREQUENCY (e);
637 if (!(e->flags & EDGE_CAN_FALLTHRU)
638 || (e->flags & EDGE_COMPLEX)
639 || prob < branch_th || freq < exec_th
640 || e->count < count_th)
642 /* When partitioning hot/cold basic blocks, make sure
643 the cold blocks (and only the cold blocks) all get
644 pushed to the last round of trace collection. When
645 optimizing for size, do not push to next round. */
647 if (!for_size && push_to_next_round_p (e->dest, round,
648 number_of_rounds,
649 exec_th, count_th))
650 which_heap = new_heap;
653 bbd[e->dest->index].heap = which_heap;
654 bbd[e->dest->index].node = fibheap_insert (which_heap,
655 key, e->dest);
657 if (dump_file)
659 fprintf (dump_file,
660 " Possible start of %s round: %d (key: %ld)\n",
661 (which_heap == new_heap) ? "next" : "this",
662 e->dest->index, (long) key);
668 if (best_edge) /* Suitable successor was found. */
670 if (bb_visited_trace (best_edge->dest) == *n_traces)
672 /* We do nothing with one basic block loops. */
673 if (best_edge->dest != bb)
675 if (EDGE_FREQUENCY (best_edge)
676 > 4 * best_edge->dest->frequency / 5)
678 /* The loop has at least 4 iterations. If the loop
679 header is not the first block of the function
680 we can rotate the loop. */
682 if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
684 if (dump_file)
686 fprintf (dump_file,
687 "Rotating loop %d - %d\n",
688 best_edge->dest->index, bb->index);
690 bb->aux = best_edge->dest;
691 bbd[best_edge->dest->index].in_trace =
692 (*n_traces) - 1;
693 bb = rotate_loop (best_edge, trace, *n_traces);
696 else
698 /* The loop has less than 4 iterations. */
700 if (single_succ_p (bb)
701 && copy_bb_p (best_edge->dest,
702 optimize_edge_for_speed_p
703 (best_edge)))
705 bb = copy_bb (best_edge->dest, best_edge, bb,
706 *n_traces);
707 trace->length++;
712 /* Terminate the trace. */
713 break;
715 else
717 /* Check for a situation
725 where
726 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
727 >= EDGE_FREQUENCY (AC).
728 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
729 Best ordering is then A B C.
731 When optimizing for size, A B C is always the best order.
733 This situation is created for example by:
735 if (A) B;
740 FOR_EACH_EDGE (e, ei, bb->succs)
741 if (e != best_edge
742 && (e->flags & EDGE_CAN_FALLTHRU)
743 && !(e->flags & EDGE_COMPLEX)
744 && !bb_visited_trace (e->dest)
745 && single_pred_p (e->dest)
746 && !(e->flags & EDGE_CROSSING)
747 && single_succ_p (e->dest)
748 && (single_succ_edge (e->dest)->flags
749 & EDGE_CAN_FALLTHRU)
750 && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
751 && single_succ (e->dest) == best_edge->dest
752 && (2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge)
753 || for_size))
755 best_edge = e;
756 if (dump_file)
757 fprintf (dump_file, "Selecting BB %d\n",
758 best_edge->dest->index);
759 break;
762 bb->aux = best_edge->dest;
763 bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
764 bb = best_edge->dest;
768 while (best_edge);
769 trace->last = bb;
770 bbd[trace->first->index].start_of_trace = *n_traces - 1;
771 bbd[trace->last->index].end_of_trace = *n_traces - 1;
773 /* The trace is terminated so we have to recount the keys in heap
774 (some block can have a lower key because now one of its predecessors
775 is an end of the trace). */
776 FOR_EACH_EDGE (e, ei, bb->succs)
778 if (e->dest == EXIT_BLOCK_PTR
779 || bb_visited_trace (e->dest))
780 continue;
782 if (bbd[e->dest->index].heap)
784 key = bb_to_key (e->dest);
785 if (key != bbd[e->dest->index].node->key)
787 if (dump_file)
789 fprintf (dump_file,
790 "Changing key for bb %d from %ld to %ld.\n",
791 e->dest->index,
792 (long) bbd[e->dest->index].node->key, key);
794 fibheap_replace_key (bbd[e->dest->index].heap,
795 bbd[e->dest->index].node,
796 key);
802 fibheap_delete (*heap);
804 /* "Return" the new heap. */
805 *heap = new_heap;
808 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
809 it to trace after BB, mark OLD_BB visited and update pass' data structures
810 (TRACE is a number of trace which OLD_BB is duplicated to). */
812 static basic_block
813 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
815 basic_block new_bb;
817 new_bb = duplicate_block (old_bb, e, bb);
818 BB_COPY_PARTITION (new_bb, old_bb);
820 gcc_assert (e->dest == new_bb);
822 if (dump_file)
823 fprintf (dump_file,
824 "Duplicated bb %d (created bb %d)\n",
825 old_bb->index, new_bb->index);
827 if (new_bb->index >= array_size || last_basic_block > array_size)
829 int i;
830 int new_size;
832 new_size = MAX (last_basic_block, new_bb->index + 1);
833 new_size = GET_ARRAY_SIZE (new_size);
834 bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
835 for (i = array_size; i < new_size; i++)
837 bbd[i].start_of_trace = -1;
838 bbd[i].end_of_trace = -1;
839 bbd[i].in_trace = -1;
840 bbd[i].visited = 0;
841 bbd[i].heap = NULL;
842 bbd[i].node = NULL;
844 array_size = new_size;
846 if (dump_file)
848 fprintf (dump_file,
849 "Growing the dynamic array to %d elements.\n",
850 array_size);
854 gcc_assert (!bb_visited_trace (e->dest));
855 mark_bb_visited (new_bb, trace);
856 new_bb->aux = bb->aux;
857 bb->aux = new_bb;
859 bbd[new_bb->index].in_trace = trace;
861 return new_bb;
864 /* Compute and return the key (for the heap) of the basic block BB. */
866 static fibheapkey_t
867 bb_to_key (basic_block bb)
869 edge e;
870 edge_iterator ei;
871 int priority = 0;
873 /* Use index as key to align with its original order. */
874 if (optimize_function_for_size_p (cfun))
875 return bb->index;
877 /* Do not start in probably never executed blocks. */
879 if (BB_PARTITION (bb) == BB_COLD_PARTITION
880 || probably_never_executed_bb_p (cfun, bb))
881 return BB_FREQ_MAX;
883 /* Prefer blocks whose predecessor is an end of some trace
884 or whose predecessor edge is EDGE_DFS_BACK. */
885 FOR_EACH_EDGE (e, ei, bb->preds)
887 if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
888 || (e->flags & EDGE_DFS_BACK))
890 int edge_freq = EDGE_FREQUENCY (e);
892 if (edge_freq > priority)
893 priority = edge_freq;
897 if (priority)
898 /* The block with priority should have significantly lower key. */
899 return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
901 return -bb->frequency;
904 /* Return true when the edge E from basic block BB is better than the temporary
905 best edge (details are in function). The probability of edge E is PROB. The
906 frequency of the successor is FREQ. The current best probability is
907 BEST_PROB, the best frequency is BEST_FREQ.
908 The edge is considered to be equivalent when PROB does not differ much from
909 BEST_PROB; similarly for frequency. */
911 static bool
912 better_edge_p (const_basic_block bb, const_edge e, int prob, int freq,
913 int best_prob, int best_freq, const_edge cur_best_edge)
915 bool is_better_edge;
917 /* The BEST_* values do not have to be best, but can be a bit smaller than
918 maximum values. */
919 int diff_prob = best_prob / 10;
920 int diff_freq = best_freq / 10;
922 /* The smaller one is better to keep the original order. */
923 if (optimize_function_for_size_p (cfun))
924 return !cur_best_edge
925 || cur_best_edge->dest->index > e->dest->index;
927 if (prob > best_prob + diff_prob)
928 /* The edge has higher probability than the temporary best edge. */
929 is_better_edge = true;
930 else if (prob < best_prob - diff_prob)
931 /* The edge has lower probability than the temporary best edge. */
932 is_better_edge = false;
933 else if (freq < best_freq - diff_freq)
934 /* The edge and the temporary best edge have almost equivalent
935 probabilities. The higher frequency of a successor now means
936 that there is another edge going into that successor.
937 This successor has lower frequency so it is better. */
938 is_better_edge = true;
939 else if (freq > best_freq + diff_freq)
940 /* This successor has higher frequency so it is worse. */
941 is_better_edge = false;
942 else if (e->dest->prev_bb == bb)
943 /* The edges have equivalent probabilities and the successors
944 have equivalent frequencies. Select the previous successor. */
945 is_better_edge = true;
946 else
947 is_better_edge = false;
949 /* If we are doing hot/cold partitioning, make sure that we always favor
950 non-crossing edges over crossing edges. */
952 if (!is_better_edge
953 && flag_reorder_blocks_and_partition
954 && cur_best_edge
955 && (cur_best_edge->flags & EDGE_CROSSING)
956 && !(e->flags & EDGE_CROSSING))
957 is_better_edge = true;
959 return is_better_edge;
962 /* Return true when the edge E is better than the temporary best edge
963 CUR_BEST_EDGE. If SRC_INDEX_P is true, the function compares the src bb of
964 E and CUR_BEST_EDGE; otherwise it will compare the dest bb.
965 BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE.
966 TRACES record the information about traces.
967 When optimizing for size, the edge with smaller index is better.
968 When optimizing for speed, the edge with bigger probability or longer trace
969 is better. */
971 static bool
972 connect_better_edge_p (const_edge e, bool src_index_p, int best_len,
973 const_edge cur_best_edge, struct trace *traces)
975 int e_index;
976 int b_index;
977 bool is_better_edge;
979 if (!cur_best_edge)
980 return true;
982 if (optimize_function_for_size_p (cfun))
984 e_index = src_index_p ? e->src->index : e->dest->index;
985 b_index = src_index_p ? cur_best_edge->src->index
986 : cur_best_edge->dest->index;
987 /* The smaller one is better to keep the original order. */
988 return b_index > e_index;
991 if (src_index_p)
993 e_index = e->src->index;
995 if (e->probability > cur_best_edge->probability)
996 /* The edge has higher probability than the temporary best edge. */
997 is_better_edge = true;
998 else if (e->probability < cur_best_edge->probability)
999 /* The edge has lower probability than the temporary best edge. */
1000 is_better_edge = false;
1001 else if (traces[bbd[e_index].end_of_trace].length > best_len)
1002 /* The edge and the temporary best edge have equivalent probabilities.
1003 The edge with longer trace is better. */
1004 is_better_edge = true;
1005 else
1006 is_better_edge = false;
1008 else
1010 e_index = e->dest->index;
1012 if (e->probability > cur_best_edge->probability)
1013 /* The edge has higher probability than the temporary best edge. */
1014 is_better_edge = true;
1015 else if (e->probability < cur_best_edge->probability)
1016 /* The edge has lower probability than the temporary best edge. */
1017 is_better_edge = false;
1018 else if (traces[bbd[e_index].start_of_trace].length > best_len)
1019 /* The edge and the temporary best edge have equivalent probabilities.
1020 The edge with longer trace is better. */
1021 is_better_edge = true;
1022 else
1023 is_better_edge = false;
1026 return is_better_edge;
1029 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
1031 static void
1032 connect_traces (int n_traces, struct trace *traces)
1034 int i;
1035 bool *connected;
1036 bool two_passes;
1037 int last_trace;
1038 int current_pass;
1039 int current_partition;
1040 int freq_threshold;
1041 gcov_type count_threshold;
1042 bool for_size = optimize_function_for_size_p (cfun);
1044 freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
1045 if (max_entry_count < INT_MAX / 1000)
1046 count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
1047 else
1048 count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
1050 connected = XCNEWVEC (bool, n_traces);
1051 last_trace = -1;
1052 current_pass = 1;
1053 current_partition = BB_PARTITION (traces[0].first);
1054 two_passes = false;
1056 if (flag_reorder_blocks_and_partition)
1057 for (i = 0; i < n_traces && !two_passes; i++)
1058 if (BB_PARTITION (traces[0].first)
1059 != BB_PARTITION (traces[i].first))
1060 two_passes = true;
1062 for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
1064 int t = i;
1065 int t2;
1066 edge e, best;
1067 int best_len;
1069 if (i >= n_traces)
1071 gcc_assert (two_passes && current_pass == 1);
1072 i = 0;
1073 t = i;
1074 current_pass = 2;
1075 if (current_partition == BB_HOT_PARTITION)
1076 current_partition = BB_COLD_PARTITION;
1077 else
1078 current_partition = BB_HOT_PARTITION;
1081 if (connected[t])
1082 continue;
1084 if (two_passes
1085 && BB_PARTITION (traces[t].first) != current_partition)
1086 continue;
1088 connected[t] = true;
1090 /* Find the predecessor traces. */
1091 for (t2 = t; t2 > 0;)
1093 edge_iterator ei;
1094 best = NULL;
1095 best_len = 0;
1096 FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
1098 int si = e->src->index;
1100 if (e->src != ENTRY_BLOCK_PTR
1101 && (e->flags & EDGE_CAN_FALLTHRU)
1102 && !(e->flags & EDGE_COMPLEX)
1103 && bbd[si].end_of_trace >= 0
1104 && !connected[bbd[si].end_of_trace]
1105 && (BB_PARTITION (e->src) == current_partition)
1106 && connect_better_edge_p (e, true, best_len, best, traces))
1108 best = e;
1109 best_len = traces[bbd[si].end_of_trace].length;
1112 if (best)
1114 best->src->aux = best->dest;
1115 t2 = bbd[best->src->index].end_of_trace;
1116 connected[t2] = true;
1118 if (dump_file)
1120 fprintf (dump_file, "Connection: %d %d\n",
1121 best->src->index, best->dest->index);
1124 else
1125 break;
1128 if (last_trace >= 0)
1129 traces[last_trace].last->aux = traces[t2].first;
1130 last_trace = t;
1132 /* Find the successor traces. */
1133 while (1)
1135 /* Find the continuation of the chain. */
1136 edge_iterator ei;
1137 best = NULL;
1138 best_len = 0;
1139 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1141 int di = e->dest->index;
1143 if (e->dest != EXIT_BLOCK_PTR
1144 && (e->flags & EDGE_CAN_FALLTHRU)
1145 && !(e->flags & EDGE_COMPLEX)
1146 && bbd[di].start_of_trace >= 0
1147 && !connected[bbd[di].start_of_trace]
1148 && (BB_PARTITION (e->dest) == current_partition)
1149 && connect_better_edge_p (e, false, best_len, best, traces))
1151 best = e;
1152 best_len = traces[bbd[di].start_of_trace].length;
1156 if (for_size)
1158 if (!best)
1159 /* Stop finding the successor traces. */
1160 break;
1162 /* It is OK to connect block n with block n + 1 or a block
1163 before n. For others, only connect to the loop header. */
1164 if (best->dest->index > (traces[t].last->index + 1))
1166 int count = EDGE_COUNT (best->dest->preds);
1168 FOR_EACH_EDGE (e, ei, best->dest->preds)
1169 if (e->flags & EDGE_DFS_BACK)
1170 count--;
1172 /* If dest has multiple predecessors, skip it. We expect
1173 that one predecessor with smaller index connects with it
1174 later. */
1175 if (count != 1)
1176 break;
1179 /* Only connect Trace n with Trace n + 1. It is conservative
1180 to keep the order as close as possible to the original order.
1181 It also helps to reduce long jumps. */
1182 if (last_trace != bbd[best->dest->index].start_of_trace - 1)
1183 break;
1185 if (dump_file)
1186 fprintf (dump_file, "Connection: %d %d\n",
1187 best->src->index, best->dest->index);
1189 t = bbd[best->dest->index].start_of_trace;
1190 traces[last_trace].last->aux = traces[t].first;
1191 connected[t] = true;
1192 last_trace = t;
1194 else if (best)
1196 if (dump_file)
1198 fprintf (dump_file, "Connection: %d %d\n",
1199 best->src->index, best->dest->index);
1201 t = bbd[best->dest->index].start_of_trace;
1202 traces[last_trace].last->aux = traces[t].first;
1203 connected[t] = true;
1204 last_trace = t;
1206 else
1208 /* Try to connect the traces by duplication of 1 block. */
1209 edge e2;
1210 basic_block next_bb = NULL;
1211 bool try_copy = false;
1213 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1214 if (e->dest != EXIT_BLOCK_PTR
1215 && (e->flags & EDGE_CAN_FALLTHRU)
1216 && !(e->flags & EDGE_COMPLEX)
1217 && (!best || e->probability > best->probability))
1219 edge_iterator ei;
1220 edge best2 = NULL;
1221 int best2_len = 0;
1223 /* If the destination is a start of a trace which is only
1224 one block long, then no need to search the successor
1225 blocks of the trace. Accept it. */
1226 if (bbd[e->dest->index].start_of_trace >= 0
1227 && traces[bbd[e->dest->index].start_of_trace].length
1228 == 1)
1230 best = e;
1231 try_copy = true;
1232 continue;
1235 FOR_EACH_EDGE (e2, ei, e->dest->succs)
1237 int di = e2->dest->index;
1239 if (e2->dest == EXIT_BLOCK_PTR
1240 || ((e2->flags & EDGE_CAN_FALLTHRU)
1241 && !(e2->flags & EDGE_COMPLEX)
1242 && bbd[di].start_of_trace >= 0
1243 && !connected[bbd[di].start_of_trace]
1244 && BB_PARTITION (e2->dest) == current_partition
1245 && EDGE_FREQUENCY (e2) >= freq_threshold
1246 && e2->count >= count_threshold
1247 && (!best2
1248 || e2->probability > best2->probability
1249 || (e2->probability == best2->probability
1250 && traces[bbd[di].start_of_trace].length
1251 > best2_len))))
1253 best = e;
1254 best2 = e2;
1255 if (e2->dest != EXIT_BLOCK_PTR)
1256 best2_len = traces[bbd[di].start_of_trace].length;
1257 else
1258 best2_len = INT_MAX;
1259 next_bb = e2->dest;
1260 try_copy = true;
1265 if (flag_reorder_blocks_and_partition)
1266 try_copy = false;
1268 /* Copy tiny blocks always; copy larger blocks only when the
1269 edge is traversed frequently enough. */
1270 if (try_copy
1271 && copy_bb_p (best->dest,
1272 optimize_edge_for_speed_p (best)
1273 && EDGE_FREQUENCY (best) >= freq_threshold
1274 && best->count >= count_threshold))
1276 basic_block new_bb;
1278 if (dump_file)
1280 fprintf (dump_file, "Connection: %d %d ",
1281 traces[t].last->index, best->dest->index);
1282 if (!next_bb)
1283 fputc ('\n', dump_file);
1284 else if (next_bb == EXIT_BLOCK_PTR)
1285 fprintf (dump_file, "exit\n");
1286 else
1287 fprintf (dump_file, "%d\n", next_bb->index);
1290 new_bb = copy_bb (best->dest, best, traces[t].last, t);
1291 traces[t].last = new_bb;
1292 if (next_bb && next_bb != EXIT_BLOCK_PTR)
1294 t = bbd[next_bb->index].start_of_trace;
1295 traces[last_trace].last->aux = traces[t].first;
1296 connected[t] = true;
1297 last_trace = t;
1299 else
1300 break; /* Stop finding the successor traces. */
1302 else
1303 break; /* Stop finding the successor traces. */
1308 if (dump_file)
1310 basic_block bb;
1312 fprintf (dump_file, "Final order:\n");
1313 for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
1314 fprintf (dump_file, "%d ", bb->index);
1315 fprintf (dump_file, "\n");
1316 fflush (dump_file);
1319 FREE (connected);
1322 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1323 when code size is allowed to grow by duplication. */
1325 static bool
1326 copy_bb_p (const_basic_block bb, int code_may_grow)
1328 int size = 0;
1329 int max_size = uncond_jump_length;
1330 rtx insn;
1332 if (!bb->frequency)
1333 return false;
1334 if (EDGE_COUNT (bb->preds) < 2)
1335 return false;
1336 if (!can_duplicate_block_p (bb))
1337 return false;
1339 /* Avoid duplicating blocks which have many successors (PR/13430). */
1340 if (EDGE_COUNT (bb->succs) > 8)
1341 return false;
1343 if (code_may_grow && optimize_bb_for_speed_p (bb))
1344 max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
1346 FOR_BB_INSNS (bb, insn)
1348 if (INSN_P (insn))
1349 size += get_attr_min_length (insn);
1352 if (size <= max_size)
1353 return true;
1355 if (dump_file)
1357 fprintf (dump_file,
1358 "Block %d can't be copied because its size = %d.\n",
1359 bb->index, size);
1362 return false;
1365 /* Return the length of unconditional jump instruction. */
1368 get_uncond_jump_length (void)
1370 rtx label, jump;
1371 int length;
1373 label = emit_label_before (gen_label_rtx (), get_insns ());
1374 jump = emit_jump_insn (gen_jump (label));
1376 length = get_attr_min_length (jump);
1378 delete_insn (jump);
1379 delete_insn (label);
1380 return length;
1383 /* Emit a barrier into the footer of BB. */
1385 static void
1386 emit_barrier_after_bb (basic_block bb)
1388 rtx barrier = emit_barrier_after (BB_END (bb));
1389 BB_FOOTER (bb) = unlink_insn_chain (barrier, barrier);
1392 /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1393 Duplicate the landing pad and split the edges so that no EH edge
1394 crosses partitions. */
1396 static void
1397 fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
1399 eh_landing_pad new_lp;
1400 basic_block new_bb, last_bb, post_bb;
1401 rtx new_label, jump, post_label;
1402 unsigned new_partition;
1403 edge_iterator ei;
1404 edge e;
1406 /* Generate the new landing-pad structure. */
1407 new_lp = gen_eh_landing_pad (old_lp->region);
1408 new_lp->post_landing_pad = old_lp->post_landing_pad;
1409 new_lp->landing_pad = gen_label_rtx ();
1410 LABEL_PRESERVE_P (new_lp->landing_pad) = 1;
1412 /* Put appropriate instructions in new bb. */
1413 new_label = emit_label (new_lp->landing_pad);
1415 expand_dw2_landing_pad_for_region (old_lp->region);
1417 post_bb = BLOCK_FOR_INSN (old_lp->landing_pad);
1418 post_bb = single_succ (post_bb);
1419 post_label = block_label (post_bb);
1420 jump = emit_jump_insn (gen_jump (post_label));
1421 JUMP_LABEL (jump) = post_label;
1423 /* Create new basic block to be dest for lp. */
1424 last_bb = EXIT_BLOCK_PTR->prev_bb;
1425 new_bb = create_basic_block (new_label, jump, last_bb);
1426 new_bb->aux = last_bb->aux;
1427 last_bb->aux = new_bb;
1429 emit_barrier_after_bb (new_bb);
1431 make_edge (new_bb, post_bb, 0);
1433 /* Make sure new bb is in the other partition. */
1434 new_partition = BB_PARTITION (old_bb);
1435 new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1436 BB_SET_PARTITION (new_bb, new_partition);
1438 /* Fix up the edges. */
1439 for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
1440 if (BB_PARTITION (e->src) == new_partition)
1442 rtx insn = BB_END (e->src);
1443 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1445 gcc_assert (note != NULL);
1446 gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index);
1447 XEXP (note, 0) = GEN_INT (new_lp->index);
1449 /* Adjust the edge to the new destination. */
1450 redirect_edge_succ (e, new_bb);
1452 else
1453 ei_next (&ei);
1456 /* Find the basic blocks that are rarely executed and need to be moved to
1457 a separate section of the .o file (to cut down on paging and improve
1458 cache locality). Return a vector of all edges that cross. */
1460 static vec<edge>
1461 find_rarely_executed_basic_blocks_and_crossing_edges (void)
1463 vec<edge> crossing_edges = vNULL;
1464 basic_block bb;
1465 edge e;
1466 edge_iterator ei;
1468 /* Mark which partition (hot/cold) each basic block belongs in. */
1469 FOR_EACH_BB (bb)
1471 if (probably_never_executed_bb_p (cfun, bb))
1472 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1473 else
1474 BB_SET_PARTITION (bb, BB_HOT_PARTITION);
1477 /* The format of .gcc_except_table does not allow landing pads to
1478 be in a different partition as the throw. Fix this by either
1479 moving or duplicating the landing pads. */
1480 if (cfun->eh->lp_array)
1482 unsigned i;
1483 eh_landing_pad lp;
1485 FOR_EACH_VEC_ELT (*cfun->eh->lp_array, i, lp)
1487 bool all_same, all_diff;
1489 if (lp == NULL
1490 || lp->landing_pad == NULL_RTX
1491 || !LABEL_P (lp->landing_pad))
1492 continue;
1494 all_same = all_diff = true;
1495 bb = BLOCK_FOR_INSN (lp->landing_pad);
1496 FOR_EACH_EDGE (e, ei, bb->preds)
1498 gcc_assert (e->flags & EDGE_EH);
1499 if (BB_PARTITION (bb) == BB_PARTITION (e->src))
1500 all_diff = false;
1501 else
1502 all_same = false;
1505 if (all_same)
1507 else if (all_diff)
1509 int which = BB_PARTITION (bb);
1510 which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1511 BB_SET_PARTITION (bb, which);
1513 else
1514 fix_up_crossing_landing_pad (lp, bb);
1518 /* Mark every edge that crosses between sections. */
1520 FOR_EACH_BB (bb)
1521 FOR_EACH_EDGE (e, ei, bb->succs)
1523 unsigned int flags = e->flags;
1525 /* We should never have EDGE_CROSSING set yet. */
1526 gcc_checking_assert ((flags & EDGE_CROSSING) == 0);
1528 if (e->src != ENTRY_BLOCK_PTR
1529 && e->dest != EXIT_BLOCK_PTR
1530 && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1532 crossing_edges.safe_push (e);
1533 flags |= EDGE_CROSSING;
1536 /* Now that we've split eh edges as appropriate, allow landing pads
1537 to be merged with the post-landing pads. */
1538 flags &= ~EDGE_PRESERVE;
1540 e->flags = flags;
1543 return crossing_edges;
1546 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
1548 static void
1549 set_edge_can_fallthru_flag (void)
1551 basic_block bb;
1553 FOR_EACH_BB (bb)
1555 edge e;
1556 edge_iterator ei;
1558 FOR_EACH_EDGE (e, ei, bb->succs)
1560 e->flags &= ~EDGE_CAN_FALLTHRU;
1562 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
1563 if (e->flags & EDGE_FALLTHRU)
1564 e->flags |= EDGE_CAN_FALLTHRU;
1567 /* If the BB ends with an invertible condjump all (2) edges are
1568 CAN_FALLTHRU edges. */
1569 if (EDGE_COUNT (bb->succs) != 2)
1570 continue;
1571 if (!any_condjump_p (BB_END (bb)))
1572 continue;
1573 if (!invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0))
1574 continue;
1575 invert_jump (BB_END (bb), JUMP_LABEL (BB_END (bb)), 0);
1576 EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
1577 EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
1581 /* If any destination of a crossing edge does not have a label, add label;
1582 Convert any easy fall-through crossing edges to unconditional jumps. */
1584 static void
1585 add_labels_and_missing_jumps (vec<edge> crossing_edges)
1587 size_t i;
1588 edge e;
1590 FOR_EACH_VEC_ELT (crossing_edges, i, e)
1592 basic_block src = e->src;
1593 basic_block dest = e->dest;
1594 rtx label, new_jump;
1596 if (dest == EXIT_BLOCK_PTR)
1597 continue;
1599 /* Make sure dest has a label. */
1600 label = block_label (dest);
1602 /* Nothing to do for non-fallthru edges. */
1603 if (src == ENTRY_BLOCK_PTR)
1604 continue;
1605 if ((e->flags & EDGE_FALLTHRU) == 0)
1606 continue;
1608 /* If the block does not end with a control flow insn, then we
1609 can trivially add a jump to the end to fixup the crossing.
1610 Otherwise the jump will have to go in a new bb, which will
1611 be handled by fix_up_fall_thru_edges function. */
1612 if (control_flow_insn_p (BB_END (src)))
1613 continue;
1615 /* Make sure there's only one successor. */
1616 gcc_assert (single_succ_p (src));
1618 new_jump = emit_jump_insn_after (gen_jump (label), BB_END (src));
1619 BB_END (src) = new_jump;
1620 JUMP_LABEL (new_jump) = label;
1621 LABEL_NUSES (label) += 1;
1623 emit_barrier_after_bb (src);
1625 /* Mark edge as non-fallthru. */
1626 e->flags &= ~EDGE_FALLTHRU;
1630 /* Find any bb's where the fall-through edge is a crossing edge (note that
1631 these bb's must also contain a conditional jump or end with a call
1632 instruction; we've already dealt with fall-through edges for blocks
1633 that didn't have a conditional jump or didn't end with call instruction
1634 in the call to add_labels_and_missing_jumps). Convert the fall-through
1635 edge to non-crossing edge by inserting a new bb to fall-through into.
1636 The new bb will contain an unconditional jump (crossing edge) to the
1637 original fall through destination. */
1639 static void
1640 fix_up_fall_thru_edges (void)
1642 basic_block cur_bb;
1643 basic_block new_bb;
1644 edge succ1;
1645 edge succ2;
1646 edge fall_thru;
1647 edge cond_jump = NULL;
1648 edge e;
1649 bool cond_jump_crosses;
1650 int invert_worked;
1651 rtx old_jump;
1652 rtx fall_thru_label;
1654 FOR_EACH_BB (cur_bb)
1656 fall_thru = NULL;
1657 if (EDGE_COUNT (cur_bb->succs) > 0)
1658 succ1 = EDGE_SUCC (cur_bb, 0);
1659 else
1660 succ1 = NULL;
1662 if (EDGE_COUNT (cur_bb->succs) > 1)
1663 succ2 = EDGE_SUCC (cur_bb, 1);
1664 else
1665 succ2 = NULL;
1667 /* Find the fall-through edge. */
1669 if (succ1
1670 && (succ1->flags & EDGE_FALLTHRU))
1672 fall_thru = succ1;
1673 cond_jump = succ2;
1675 else if (succ2
1676 && (succ2->flags & EDGE_FALLTHRU))
1678 fall_thru = succ2;
1679 cond_jump = succ1;
1681 else if (succ1
1682 && (block_ends_with_call_p (cur_bb)
1683 || can_throw_internal (BB_END (cur_bb))))
1685 edge e;
1686 edge_iterator ei;
1688 /* Find EDGE_CAN_FALLTHRU edge. */
1689 FOR_EACH_EDGE (e, ei, cur_bb->succs)
1690 if (e->flags & EDGE_CAN_FALLTHRU)
1692 fall_thru = e;
1693 break;
1697 if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
1699 /* Check to see if the fall-thru edge is a crossing edge. */
1701 if (fall_thru->flags & EDGE_CROSSING)
1703 /* The fall_thru edge crosses; now check the cond jump edge, if
1704 it exists. */
1706 cond_jump_crosses = true;
1707 invert_worked = 0;
1708 old_jump = BB_END (cur_bb);
1710 /* Find the jump instruction, if there is one. */
1712 if (cond_jump)
1714 if (!(cond_jump->flags & EDGE_CROSSING))
1715 cond_jump_crosses = false;
1717 /* We know the fall-thru edge crosses; if the cond
1718 jump edge does NOT cross, and its destination is the
1719 next block in the bb order, invert the jump
1720 (i.e. fix it so the fall through does not cross and
1721 the cond jump does). */
1723 if (!cond_jump_crosses
1724 && cur_bb->aux == cond_jump->dest)
1726 /* Find label in fall_thru block. We've already added
1727 any missing labels, so there must be one. */
1729 fall_thru_label = block_label (fall_thru->dest);
1731 if (old_jump && JUMP_P (old_jump) && fall_thru_label)
1732 invert_worked = invert_jump (old_jump,
1733 fall_thru_label,0);
1734 if (invert_worked)
1736 fall_thru->flags &= ~EDGE_FALLTHRU;
1737 cond_jump->flags |= EDGE_FALLTHRU;
1738 update_br_prob_note (cur_bb);
1739 e = fall_thru;
1740 fall_thru = cond_jump;
1741 cond_jump = e;
1742 cond_jump->flags |= EDGE_CROSSING;
1743 fall_thru->flags &= ~EDGE_CROSSING;
1748 if (cond_jump_crosses || !invert_worked)
1750 /* This is the case where both edges out of the basic
1751 block are crossing edges. Here we will fix up the
1752 fall through edge. The jump edge will be taken care
1753 of later. The EDGE_CROSSING flag of fall_thru edge
1754 is unset before the call to force_nonfallthru
1755 function because if a new basic-block is created
1756 this edge remains in the current section boundary
1757 while the edge between new_bb and the fall_thru->dest
1758 becomes EDGE_CROSSING. */
1760 fall_thru->flags &= ~EDGE_CROSSING;
1761 new_bb = force_nonfallthru (fall_thru);
1763 if (new_bb)
1765 new_bb->aux = cur_bb->aux;
1766 cur_bb->aux = new_bb;
1768 /* Make sure new fall-through bb is in same
1769 partition as bb it's falling through from. */
1771 BB_COPY_PARTITION (new_bb, cur_bb);
1772 single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
1774 else
1776 /* If a new basic-block was not created; restore
1777 the EDGE_CROSSING flag. */
1778 fall_thru->flags |= EDGE_CROSSING;
1781 /* Add barrier after new jump */
1782 emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
1789 /* This function checks the destination block of a "crossing jump" to
1790 see if it has any crossing predecessors that begin with a code label
1791 and end with an unconditional jump. If so, it returns that predecessor
1792 block. (This is to avoid creating lots of new basic blocks that all
1793 contain unconditional jumps to the same destination). */
1795 static basic_block
1796 find_jump_block (basic_block jump_dest)
1798 basic_block source_bb = NULL;
1799 edge e;
1800 rtx insn;
1801 edge_iterator ei;
1803 FOR_EACH_EDGE (e, ei, jump_dest->preds)
1804 if (e->flags & EDGE_CROSSING)
1806 basic_block src = e->src;
1808 /* Check each predecessor to see if it has a label, and contains
1809 only one executable instruction, which is an unconditional jump.
1810 If so, we can use it. */
1812 if (LABEL_P (BB_HEAD (src)))
1813 for (insn = BB_HEAD (src);
1814 !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
1815 insn = NEXT_INSN (insn))
1817 if (INSN_P (insn)
1818 && insn == BB_END (src)
1819 && JUMP_P (insn)
1820 && !any_condjump_p (insn))
1822 source_bb = src;
1823 break;
1827 if (source_bb)
1828 break;
1831 return source_bb;
1834 /* Find all BB's with conditional jumps that are crossing edges;
1835 insert a new bb and make the conditional jump branch to the new
1836 bb instead (make the new bb same color so conditional branch won't
1837 be a 'crossing' edge). Insert an unconditional jump from the
1838 new bb to the original destination of the conditional jump. */
1840 static void
1841 fix_crossing_conditional_branches (void)
1843 basic_block cur_bb;
1844 basic_block new_bb;
1845 basic_block dest;
1846 edge succ1;
1847 edge succ2;
1848 edge crossing_edge;
1849 edge new_edge;
1850 rtx old_jump;
1851 rtx set_src;
1852 rtx old_label = NULL_RTX;
1853 rtx new_label;
1855 FOR_EACH_BB (cur_bb)
1857 crossing_edge = NULL;
1858 if (EDGE_COUNT (cur_bb->succs) > 0)
1859 succ1 = EDGE_SUCC (cur_bb, 0);
1860 else
1861 succ1 = NULL;
1863 if (EDGE_COUNT (cur_bb->succs) > 1)
1864 succ2 = EDGE_SUCC (cur_bb, 1);
1865 else
1866 succ2 = NULL;
1868 /* We already took care of fall-through edges, so only one successor
1869 can be a crossing edge. */
1871 if (succ1 && (succ1->flags & EDGE_CROSSING))
1872 crossing_edge = succ1;
1873 else if (succ2 && (succ2->flags & EDGE_CROSSING))
1874 crossing_edge = succ2;
1876 if (crossing_edge)
1878 old_jump = BB_END (cur_bb);
1880 /* Check to make sure the jump instruction is a
1881 conditional jump. */
1883 set_src = NULL_RTX;
1885 if (any_condjump_p (old_jump))
1887 if (GET_CODE (PATTERN (old_jump)) == SET)
1888 set_src = SET_SRC (PATTERN (old_jump));
1889 else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
1891 set_src = XVECEXP (PATTERN (old_jump), 0,0);
1892 if (GET_CODE (set_src) == SET)
1893 set_src = SET_SRC (set_src);
1894 else
1895 set_src = NULL_RTX;
1899 if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
1901 if (GET_CODE (XEXP (set_src, 1)) == PC)
1902 old_label = XEXP (set_src, 2);
1903 else if (GET_CODE (XEXP (set_src, 2)) == PC)
1904 old_label = XEXP (set_src, 1);
1906 /* Check to see if new bb for jumping to that dest has
1907 already been created; if so, use it; if not, create
1908 a new one. */
1910 new_bb = find_jump_block (crossing_edge->dest);
1912 if (new_bb)
1913 new_label = block_label (new_bb);
1914 else
1916 basic_block last_bb;
1917 rtx new_jump;
1919 /* Create new basic block to be dest for
1920 conditional jump. */
1922 /* Put appropriate instructions in new bb. */
1924 new_label = gen_label_rtx ();
1925 emit_label (new_label);
1927 gcc_assert (GET_CODE (old_label) == LABEL_REF);
1928 old_label = JUMP_LABEL (old_jump);
1929 new_jump = emit_jump_insn (gen_jump (old_label));
1930 JUMP_LABEL (new_jump) = old_label;
1932 last_bb = EXIT_BLOCK_PTR->prev_bb;
1933 new_bb = create_basic_block (new_label, new_jump, last_bb);
1934 new_bb->aux = last_bb->aux;
1935 last_bb->aux = new_bb;
1937 emit_barrier_after_bb (new_bb);
1939 /* Make sure new bb is in same partition as source
1940 of conditional branch. */
1941 BB_COPY_PARTITION (new_bb, cur_bb);
1944 /* Make old jump branch to new bb. */
1946 redirect_jump (old_jump, new_label, 0);
1948 /* Remove crossing_edge as predecessor of 'dest'. */
1950 dest = crossing_edge->dest;
1952 redirect_edge_succ (crossing_edge, new_bb);
1954 /* Make a new edge from new_bb to old dest; new edge
1955 will be a successor for new_bb and a predecessor
1956 for 'dest'. */
1958 if (EDGE_COUNT (new_bb->succs) == 0)
1959 new_edge = make_edge (new_bb, dest, 0);
1960 else
1961 new_edge = EDGE_SUCC (new_bb, 0);
1963 crossing_edge->flags &= ~EDGE_CROSSING;
1964 new_edge->flags |= EDGE_CROSSING;
1970 /* Find any unconditional branches that cross between hot and cold
1971 sections. Convert them into indirect jumps instead. */
1973 static void
1974 fix_crossing_unconditional_branches (void)
1976 basic_block cur_bb;
1977 rtx last_insn;
1978 rtx label;
1979 rtx label_addr;
1980 rtx indirect_jump_sequence;
1981 rtx jump_insn = NULL_RTX;
1982 rtx new_reg;
1983 rtx cur_insn;
1984 edge succ;
1986 FOR_EACH_BB (cur_bb)
1988 last_insn = BB_END (cur_bb);
1990 if (EDGE_COUNT (cur_bb->succs) < 1)
1991 continue;
1993 succ = EDGE_SUCC (cur_bb, 0);
1995 /* Check to see if bb ends in a crossing (unconditional) jump. At
1996 this point, no crossing jumps should be conditional. */
1998 if (JUMP_P (last_insn)
1999 && (succ->flags & EDGE_CROSSING))
2001 rtx label2, table;
2003 gcc_assert (!any_condjump_p (last_insn));
2005 /* Make sure the jump is not already an indirect or table jump. */
2007 if (!computed_jump_p (last_insn)
2008 && !tablejump_p (last_insn, &label2, &table))
2010 /* We have found a "crossing" unconditional branch. Now
2011 we must convert it to an indirect jump. First create
2012 reference of label, as target for jump. */
2014 label = JUMP_LABEL (last_insn);
2015 label_addr = gen_rtx_LABEL_REF (Pmode, label);
2016 LABEL_NUSES (label) += 1;
2018 /* Get a register to use for the indirect jump. */
2020 new_reg = gen_reg_rtx (Pmode);
2022 /* Generate indirect the jump sequence. */
2024 start_sequence ();
2025 emit_move_insn (new_reg, label_addr);
2026 emit_indirect_jump (new_reg);
2027 indirect_jump_sequence = get_insns ();
2028 end_sequence ();
2030 /* Make sure every instruction in the new jump sequence has
2031 its basic block set to be cur_bb. */
2033 for (cur_insn = indirect_jump_sequence; cur_insn;
2034 cur_insn = NEXT_INSN (cur_insn))
2036 if (!BARRIER_P (cur_insn))
2037 BLOCK_FOR_INSN (cur_insn) = cur_bb;
2038 if (JUMP_P (cur_insn))
2039 jump_insn = cur_insn;
2042 /* Insert the new (indirect) jump sequence immediately before
2043 the unconditional jump, then delete the unconditional jump. */
2045 emit_insn_before (indirect_jump_sequence, last_insn);
2046 delete_insn (last_insn);
2048 /* Make BB_END for cur_bb be the jump instruction (NOT the
2049 barrier instruction at the end of the sequence...). */
2051 BB_END (cur_bb) = jump_insn;
2057 /* Add REG_CROSSING_JUMP note to all crossing jump insns. */
2059 static void
2060 add_reg_crossing_jump_notes (void)
2062 basic_block bb;
2063 edge e;
2064 edge_iterator ei;
2066 FOR_EACH_BB (bb)
2067 FOR_EACH_EDGE (e, ei, bb->succs)
2068 if ((e->flags & EDGE_CROSSING)
2069 && JUMP_P (BB_END (e->src)))
2070 add_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX);
2073 /* Verify, in the basic block chain, that there is at most one switch
2074 between hot/cold partitions. This is modelled on
2075 rtl_verify_flow_info_1, but it cannot go inside that function
2076 because this condition will not be true until after
2077 reorder_basic_blocks is called. */
2079 static void
2080 verify_hot_cold_block_grouping (void)
2082 basic_block bb;
2083 int err = 0;
2084 bool switched_sections = false;
2085 int current_partition = 0;
2087 FOR_EACH_BB (bb)
2089 if (!current_partition)
2090 current_partition = BB_PARTITION (bb);
2091 if (BB_PARTITION (bb) != current_partition)
2093 if (switched_sections)
2095 error ("multiple hot/cold transitions found (bb %i)",
2096 bb->index);
2097 err = 1;
2099 else
2101 switched_sections = true;
2102 current_partition = BB_PARTITION (bb);
2107 gcc_assert(!err);
2110 /* Reorder basic blocks. The main entry point to this file. FLAGS is
2111 the set of flags to pass to cfg_layout_initialize(). */
2113 static void
2114 reorder_basic_blocks (void)
2116 int n_traces;
2117 int i;
2118 struct trace *traces;
2120 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
2122 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
2123 return;
2125 set_edge_can_fallthru_flag ();
2126 mark_dfs_back_edges ();
2128 /* We are estimating the length of uncond jump insn only once since the code
2129 for getting the insn length always returns the minimal length now. */
2130 if (uncond_jump_length == 0)
2131 uncond_jump_length = get_uncond_jump_length ();
2133 /* We need to know some information for each basic block. */
2134 array_size = GET_ARRAY_SIZE (last_basic_block);
2135 bbd = XNEWVEC (bbro_basic_block_data, array_size);
2136 for (i = 0; i < array_size; i++)
2138 bbd[i].start_of_trace = -1;
2139 bbd[i].end_of_trace = -1;
2140 bbd[i].in_trace = -1;
2141 bbd[i].visited = 0;
2142 bbd[i].heap = NULL;
2143 bbd[i].node = NULL;
2146 traces = XNEWVEC (struct trace, n_basic_blocks);
2147 n_traces = 0;
2148 find_traces (&n_traces, traces);
2149 connect_traces (n_traces, traces);
2150 FREE (traces);
2151 FREE (bbd);
2153 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
2155 if (dump_file)
2157 if (dump_flags & TDF_DETAILS)
2158 dump_reg_info (dump_file);
2159 dump_flow_info (dump_file, dump_flags);
2162 if (flag_reorder_blocks_and_partition)
2163 verify_hot_cold_block_grouping ();
2166 /* Determine which partition the first basic block in the function
2167 belongs to, then find the first basic block in the current function
2168 that belongs to a different section, and insert a
2169 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
2170 instruction stream. When writing out the assembly code,
2171 encountering this note will make the compiler switch between the
2172 hot and cold text sections. */
2174 static void
2175 insert_section_boundary_note (void)
2177 basic_block bb;
2178 rtx new_note;
2179 int first_partition = 0;
2181 if (!flag_reorder_blocks_and_partition)
2182 return;
2184 FOR_EACH_BB (bb)
2186 if (!first_partition)
2187 first_partition = BB_PARTITION (bb);
2188 if (BB_PARTITION (bb) != first_partition)
2190 new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS,
2191 BB_HEAD (bb));
2192 /* ??? This kind of note always lives between basic blocks,
2193 but add_insn_before will set BLOCK_FOR_INSN anyway. */
2194 BLOCK_FOR_INSN (new_note) = NULL;
2195 break;
2200 static bool
2201 gate_handle_reorder_blocks (void)
2203 if (targetm.cannot_modify_jumps_p ())
2204 return false;
2205 return (optimize > 0
2206 && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
2209 static unsigned int
2210 rest_of_handle_reorder_blocks (void)
2212 basic_block bb;
2214 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2215 splitting possibly introduced more crossjumping opportunities. */
2216 cfg_layout_initialize (CLEANUP_EXPENSIVE);
2218 reorder_basic_blocks ();
2219 cleanup_cfg (CLEANUP_EXPENSIVE);
2221 FOR_EACH_BB (bb)
2222 if (bb->next_bb != EXIT_BLOCK_PTR)
2223 bb->aux = bb->next_bb;
2224 cfg_layout_finalize ();
2226 /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */
2227 insert_section_boundary_note ();
2228 return 0;
2231 struct rtl_opt_pass pass_reorder_blocks =
2234 RTL_PASS,
2235 "bbro", /* name */
2236 OPTGROUP_NONE, /* optinfo_flags */
2237 gate_handle_reorder_blocks, /* gate */
2238 rest_of_handle_reorder_blocks, /* execute */
2239 NULL, /* sub */
2240 NULL, /* next */
2241 0, /* static_pass_number */
2242 TV_REORDER_BLOCKS, /* tv_id */
2243 0, /* properties_required */
2244 0, /* properties_provided */
2245 0, /* properties_destroyed */
2246 0, /* todo_flags_start */
2247 TODO_verify_rtl_sharing, /* todo_flags_finish */
2251 /* Duplicate the blocks containing computed gotos. This basically unfactors
2252 computed gotos that were factored early on in the compilation process to
2253 speed up edge based data flow. We used to not unfactoring them again,
2254 which can seriously pessimize code with many computed jumps in the source
2255 code, such as interpreters. See e.g. PR15242. */
2257 static bool
2258 gate_duplicate_computed_gotos (void)
2260 if (targetm.cannot_modify_jumps_p ())
2261 return false;
2262 return (optimize > 0
2263 && flag_expensive_optimizations
2264 && ! optimize_function_for_size_p (cfun));
2268 static unsigned int
2269 duplicate_computed_gotos (void)
2271 basic_block bb, new_bb;
2272 bitmap candidates;
2273 int max_size;
2275 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
2276 return 0;
2278 clear_bb_flags ();
2279 cfg_layout_initialize (0);
2281 /* We are estimating the length of uncond jump insn only once
2282 since the code for getting the insn length always returns
2283 the minimal length now. */
2284 if (uncond_jump_length == 0)
2285 uncond_jump_length = get_uncond_jump_length ();
2287 max_size
2288 = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
2289 candidates = BITMAP_ALLOC (NULL);
2291 /* Look for blocks that end in a computed jump, and see if such blocks
2292 are suitable for unfactoring. If a block is a candidate for unfactoring,
2293 mark it in the candidates. */
2294 FOR_EACH_BB (bb)
2296 rtx insn;
2297 edge e;
2298 edge_iterator ei;
2299 int size, all_flags;
2301 /* Build the reorder chain for the original order of blocks. */
2302 if (bb->next_bb != EXIT_BLOCK_PTR)
2303 bb->aux = bb->next_bb;
2305 /* Obviously the block has to end in a computed jump. */
2306 if (!computed_jump_p (BB_END (bb)))
2307 continue;
2309 /* Only consider blocks that can be duplicated. */
2310 if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX)
2311 || !can_duplicate_block_p (bb))
2312 continue;
2314 /* Make sure that the block is small enough. */
2315 size = 0;
2316 FOR_BB_INSNS (bb, insn)
2317 if (INSN_P (insn))
2319 size += get_attr_min_length (insn);
2320 if (size > max_size)
2321 break;
2323 if (size > max_size)
2324 continue;
2326 /* Final check: there must not be any incoming abnormal edges. */
2327 all_flags = 0;
2328 FOR_EACH_EDGE (e, ei, bb->preds)
2329 all_flags |= e->flags;
2330 if (all_flags & EDGE_COMPLEX)
2331 continue;
2333 bitmap_set_bit (candidates, bb->index);
2336 /* Nothing to do if there is no computed jump here. */
2337 if (bitmap_empty_p (candidates))
2338 goto done;
2340 /* Duplicate computed gotos. */
2341 FOR_EACH_BB (bb)
2343 if (bb->flags & BB_VISITED)
2344 continue;
2346 bb->flags |= BB_VISITED;
2348 /* BB must have one outgoing edge. That edge must not lead to
2349 the exit block or the next block.
2350 The destination must have more than one predecessor. */
2351 if (!single_succ_p (bb)
2352 || single_succ (bb) == EXIT_BLOCK_PTR
2353 || single_succ (bb) == bb->next_bb
2354 || single_pred_p (single_succ (bb)))
2355 continue;
2357 /* The successor block has to be a duplication candidate. */
2358 if (!bitmap_bit_p (candidates, single_succ (bb)->index))
2359 continue;
2361 new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
2362 new_bb->aux = bb->aux;
2363 bb->aux = new_bb;
2364 new_bb->flags |= BB_VISITED;
2367 done:
2368 cfg_layout_finalize ();
2370 BITMAP_FREE (candidates);
2371 return 0;
2374 struct rtl_opt_pass pass_duplicate_computed_gotos =
2377 RTL_PASS,
2378 "compgotos", /* name */
2379 OPTGROUP_NONE, /* optinfo_flags */
2380 gate_duplicate_computed_gotos, /* gate */
2381 duplicate_computed_gotos, /* execute */
2382 NULL, /* sub */
2383 NULL, /* next */
2384 0, /* static_pass_number */
2385 TV_REORDER_BLOCKS, /* tv_id */
2386 0, /* properties_required */
2387 0, /* properties_provided */
2388 0, /* properties_destroyed */
2389 0, /* todo_flags_start */
2390 TODO_verify_rtl_sharing,/* todo_flags_finish */
2394 static bool
2395 gate_handle_partition_blocks (void)
2397 /* The optimization to partition hot/cold basic blocks into separate
2398 sections of the .o file does not work well with linkonce or with
2399 user defined section attributes. Don't call it if either case
2400 arises. */
2401 return (flag_reorder_blocks_and_partition
2402 && optimize
2403 /* See gate_handle_reorder_blocks. We should not partition if
2404 we are going to omit the reordering. */
2405 && optimize_function_for_speed_p (cfun)
2406 && !DECL_ONE_ONLY (current_function_decl)
2407 && !user_defined_section_attribute);
2410 /* This function is the main 'entrance' for the optimization that
2411 partitions hot and cold basic blocks into separate sections of the
2412 .o file (to improve performance and cache locality). Ideally it
2413 would be called after all optimizations that rearrange the CFG have
2414 been called. However part of this optimization may introduce new
2415 register usage, so it must be called before register allocation has
2416 occurred. This means that this optimization is actually called
2417 well before the optimization that reorders basic blocks (see
2418 function above).
2420 This optimization checks the feedback information to determine
2421 which basic blocks are hot/cold, updates flags on the basic blocks
2422 to indicate which section they belong in. This information is
2423 later used for writing out sections in the .o file. Because hot
2424 and cold sections can be arbitrarily large (within the bounds of
2425 memory), far beyond the size of a single function, it is necessary
2426 to fix up all edges that cross section boundaries, to make sure the
2427 instructions used can actually span the required distance. The
2428 fixes are described below.
2430 Fall-through edges must be changed into jumps; it is not safe or
2431 legal to fall through across a section boundary. Whenever a
2432 fall-through edge crossing a section boundary is encountered, a new
2433 basic block is inserted (in the same section as the fall-through
2434 source), and the fall through edge is redirected to the new basic
2435 block. The new basic block contains an unconditional jump to the
2436 original fall-through target. (If the unconditional jump is
2437 insufficient to cross section boundaries, that is dealt with a
2438 little later, see below).
2440 In order to deal with architectures that have short conditional
2441 branches (which cannot span all of memory) we take any conditional
2442 jump that attempts to cross a section boundary and add a level of
2443 indirection: it becomes a conditional jump to a new basic block, in
2444 the same section. The new basic block contains an unconditional
2445 jump to the original target, in the other section.
2447 For those architectures whose unconditional branch is also
2448 incapable of reaching all of memory, those unconditional jumps are
2449 converted into indirect jumps, through a register.
2451 IMPORTANT NOTE: This optimization causes some messy interactions
2452 with the cfg cleanup optimizations; those optimizations want to
2453 merge blocks wherever possible, and to collapse indirect jump
2454 sequences (change "A jumps to B jumps to C" directly into "A jumps
2455 to C"). Those optimizations can undo the jump fixes that
2456 partitioning is required to make (see above), in order to ensure
2457 that jumps attempting to cross section boundaries are really able
2458 to cover whatever distance the jump requires (on many architectures
2459 conditional or unconditional jumps are not able to reach all of
2460 memory). Therefore tests have to be inserted into each such
2461 optimization to make sure that it does not undo stuff necessary to
2462 cross partition boundaries. This would be much less of a problem
2463 if we could perform this optimization later in the compilation, but
2464 unfortunately the fact that we may need to create indirect jumps
2465 (through registers) requires that this optimization be performed
2466 before register allocation.
2468 Hot and cold basic blocks are partitioned and put in separate
2469 sections of the .o file, to reduce paging and improve cache
2470 performance (hopefully). This can result in bits of code from the
2471 same function being widely separated in the .o file. However this
2472 is not obvious to the current bb structure. Therefore we must take
2473 care to ensure that: 1). There are no fall_thru edges that cross
2474 between sections; 2). For those architectures which have "short"
2475 conditional branches, all conditional branches that attempt to
2476 cross between sections are converted to unconditional branches;
2477 and, 3). For those architectures which have "short" unconditional
2478 branches, all unconditional branches that attempt to cross between
2479 sections are converted to indirect jumps.
2481 The code for fixing up fall_thru edges that cross between hot and
2482 cold basic blocks does so by creating new basic blocks containing
2483 unconditional branches to the appropriate label in the "other"
2484 section. The new basic block is then put in the same (hot or cold)
2485 section as the original conditional branch, and the fall_thru edge
2486 is modified to fall into the new basic block instead. By adding
2487 this level of indirection we end up with only unconditional branches
2488 crossing between hot and cold sections.
2490 Conditional branches are dealt with by adding a level of indirection.
2491 A new basic block is added in the same (hot/cold) section as the
2492 conditional branch, and the conditional branch is retargeted to the
2493 new basic block. The new basic block contains an unconditional branch
2494 to the original target of the conditional branch (in the other section).
2496 Unconditional branches are dealt with by converting them into
2497 indirect jumps. */
2499 static unsigned
2500 partition_hot_cold_basic_blocks (void)
2502 vec<edge> crossing_edges;
2504 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
2505 return 0;
2507 df_set_flags (DF_DEFER_INSN_RESCAN);
2509 crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
2510 if (!crossing_edges.exists ())
2511 return 0;
2513 /* Make sure the source of any crossing edge ends in a jump and the
2514 destination of any crossing edge has a label. */
2515 add_labels_and_missing_jumps (crossing_edges);
2517 /* Convert all crossing fall_thru edges to non-crossing fall
2518 thrus to unconditional jumps (that jump to the original fall
2519 through dest). */
2520 fix_up_fall_thru_edges ();
2522 /* If the architecture does not have conditional branches that can
2523 span all of memory, convert crossing conditional branches into
2524 crossing unconditional branches. */
2525 if (!HAS_LONG_COND_BRANCH)
2526 fix_crossing_conditional_branches ();
2528 /* If the architecture does not have unconditional branches that
2529 can span all of memory, convert crossing unconditional branches
2530 into indirect jumps. Since adding an indirect jump also adds
2531 a new register usage, update the register usage information as
2532 well. */
2533 if (!HAS_LONG_UNCOND_BRANCH)
2534 fix_crossing_unconditional_branches ();
2536 add_reg_crossing_jump_notes ();
2538 /* Clear bb->aux fields that the above routines were using. */
2539 clear_aux_for_blocks ();
2541 crossing_edges.release ();
2543 /* ??? FIXME: DF generates the bb info for a block immediately.
2544 And by immediately, I mean *during* creation of the block.
2546 #0 df_bb_refs_collect
2547 #1 in df_bb_refs_record
2548 #2 in create_basic_block_structure
2550 Which means that the bb_has_eh_pred test in df_bb_refs_collect
2551 will *always* fail, because no edges can have been added to the
2552 block yet. Which of course means we don't add the right
2553 artificial refs, which means we fail df_verify (much) later.
2555 Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
2556 that we also shouldn't grab data from the new blocks those new
2557 insns are in either. In this way one can create the block, link
2558 it up properly, and have everything Just Work later, when deferred
2559 insns are processed.
2561 In the meantime, we have no other option but to throw away all
2562 of the DF data and recompute it all. */
2563 if (cfun->eh->lp_array)
2565 df_finish_pass (true);
2566 df_scan_alloc (NULL);
2567 df_scan_blocks ();
2568 /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
2569 data. We blindly generated all of them when creating the new
2570 landing pad. Delete those assignments we don't use. */
2571 df_set_flags (DF_LR_RUN_DCE);
2572 df_analyze ();
2575 return TODO_verify_flow | TODO_verify_rtl_sharing;
2578 struct rtl_opt_pass pass_partition_blocks =
2581 RTL_PASS,
2582 "bbpart", /* name */
2583 OPTGROUP_NONE, /* optinfo_flags */
2584 gate_handle_partition_blocks, /* gate */
2585 partition_hot_cold_basic_blocks, /* execute */
2586 NULL, /* sub */
2587 NULL, /* next */
2588 0, /* static_pass_number */
2589 TV_REORDER_BLOCKS, /* tv_id */
2590 PROP_cfglayout, /* properties_required */
2591 0, /* properties_provided */
2592 0, /* properties_destroyed */
2593 0, /* todo_flags_start */
2594 0 /* todo_flags_finish */