1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2002, 2003, 2004, 2005 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 2, or (at your option)
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 COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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.
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.
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.
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.
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
70 #include "coretypes.h"
77 #include "cfglayout.h"
86 /* The number of rounds. In most cases there will only be 4 rounds, but
87 when partitioning hot and cold basic blocks into separate sections of
88 the .o file there will be an extra round.*/
91 /* Stubs in case we don't have a return insn.
92 We have to check at runtime too, not only compiletime. */
96 #define gen_return() NULL_RTX
100 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
101 static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
103 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
104 static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
106 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
107 block the edge destination is not duplicated while connecting traces. */
108 #define DUPLICATION_THRESHOLD 100
110 /* Length of unconditional jump instruction. */
111 static int uncond_jump_length;
113 /* Structure to hold needed information for each basic block. */
114 typedef struct bbro_basic_block_data_def
116 /* Which trace is the bb start of (-1 means it is not a start of a trace). */
119 /* Which trace is the bb end of (-1 means it is not an end of a trace). */
122 /* Which heap is BB in (if any)? */
125 /* Which heap node is BB in (if any)? */
127 } bbro_basic_block_data;
129 /* The current size of the following dynamic array. */
130 static int array_size;
132 /* The array which holds needed information for basic blocks. */
133 static bbro_basic_block_data *bbd;
135 /* To avoid frequent reallocation the size of arrays is greater than needed,
136 the number of elements is (not less than) 1.25 * size_wanted. */
137 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
139 /* Free the memory and set the pointer to NULL. */
140 #define FREE(P) (gcc_assert (P), free (P), P = 0)
142 /* Structure for holding information about a trace. */
145 /* First and last basic block of the trace. */
146 basic_block first, last;
148 /* The round of the STC creation which this trace was found in. */
151 /* The length (i.e. the number of basic blocks) of the trace. */
155 /* Maximum frequency and count of one of the entry blocks. */
156 int max_entry_frequency;
157 gcov_type max_entry_count;
159 /* Local function prototypes. */
160 static void find_traces (int *, struct trace *);
161 static basic_block rotate_loop (edge, struct trace *, int);
162 static void mark_bb_visited (basic_block, int);
163 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
164 int, fibheap_t *, int);
165 static basic_block copy_bb (basic_block, edge, basic_block, int);
166 static fibheapkey_t bb_to_key (basic_block);
167 static bool better_edge_p (basic_block, edge, int, int, int, int, edge);
168 static void connect_traces (int, struct trace *);
169 static bool copy_bb_p (basic_block, int);
170 static int get_uncond_jump_length (void);
171 static bool push_to_next_round_p (basic_block, int, int, int, gcov_type);
172 static void add_unlikely_executed_notes (void);
173 static void find_rarely_executed_basic_blocks_and_crossing_edges (edge *,
176 static void mark_bb_for_unlikely_executed_section (basic_block);
177 static void add_labels_and_missing_jumps (edge *, int);
178 static void add_reg_crossing_jump_notes (void);
179 static void fix_up_fall_thru_edges (void);
180 static void fix_edges_for_rarely_executed_code (edge *, int);
181 static void fix_crossing_conditional_branches (void);
182 static void fix_crossing_unconditional_branches (void);
184 /* Check to see if bb should be pushed into the next round of trace
185 collections or not. Reasons for pushing the block forward are 1).
186 If the block is cold, we are doing partitioning, and there will be
187 another round (cold partition blocks are not supposed to be
188 collected into traces until the very last round); or 2). There will
189 be another round, and the basic block is not "hot enough" for the
190 current round of trace collection. */
193 push_to_next_round_p (basic_block bb, int round, int number_of_rounds,
194 int exec_th, gcov_type count_th)
196 bool there_exists_another_round;
198 bool block_not_hot_enough;
199 bool next_round_is_last;
201 there_exists_another_round = round < number_of_rounds - 1;
202 next_round_is_last = round + 1 == number_of_rounds - 1;
204 cold_block = (flag_reorder_blocks_and_partition
205 && BB_PARTITION (bb) == BB_COLD_PARTITION);
207 block_not_hot_enough = (bb->frequency < exec_th
208 || bb->count < count_th
209 || probably_never_executed_bb_p (bb));
211 if (flag_reorder_blocks_and_partition
212 && next_round_is_last
213 && BB_PARTITION (bb) != BB_COLD_PARTITION)
215 else if (there_exists_another_round
216 && (cold_block || block_not_hot_enough))
222 /* Find the traces for Software Trace Cache. Chain each trace through
223 RBI()->next. Store the number of traces to N_TRACES and description of
227 find_traces (int *n_traces, struct trace *traces)
230 int number_of_rounds;
235 /* Add one extra round of trace collection when partitioning hot/cold
236 basic blocks into separate sections. The last round is for all the
237 cold blocks (and ONLY the cold blocks). */
239 number_of_rounds = N_ROUNDS - 1;
240 if (flag_reorder_blocks_and_partition)
241 number_of_rounds = N_ROUNDS;
243 /* Insert entry points of function into heap. */
244 heap = fibheap_new ();
245 max_entry_frequency = 0;
247 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
249 bbd[e->dest->index].heap = heap;
250 bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
252 if (e->dest->frequency > max_entry_frequency)
253 max_entry_frequency = e->dest->frequency;
254 if (e->dest->count > max_entry_count)
255 max_entry_count = e->dest->count;
258 /* Find the traces. */
259 for (i = 0; i < number_of_rounds; i++)
261 gcov_type count_threshold;
264 fprintf (dump_file, "STC - round %d\n", i + 1);
266 if (max_entry_count < INT_MAX / 1000)
267 count_threshold = max_entry_count * exec_threshold[i] / 1000;
269 count_threshold = max_entry_count / 1000 * exec_threshold[i];
271 find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
272 max_entry_frequency * exec_threshold[i] / 1000,
273 count_threshold, traces, n_traces, i, &heap,
276 fibheap_delete (heap);
280 for (i = 0; i < *n_traces; i++)
283 fprintf (dump_file, "Trace %d (round %d): ", i + 1,
284 traces[i].round + 1);
285 for (bb = traces[i].first; bb != traces[i].last; bb = bb->rbi->next)
286 fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
287 fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
293 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
294 (with sequential number TRACE_N). */
297 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
301 /* Information about the best end (end after rotation) of the loop. */
302 basic_block best_bb = NULL;
303 edge best_edge = NULL;
305 gcov_type best_count = -1;
306 /* The best edge is preferred when its destination is not visited yet
307 or is a start block of some trace. */
308 bool is_preferred = false;
310 /* Find the most frequent edge that goes out from current trace. */
311 bb = back_edge->dest;
317 FOR_EACH_EDGE (e, ei, bb->succs)
318 if (e->dest != EXIT_BLOCK_PTR
319 && e->dest->rbi->visited != trace_n
320 && (e->flags & EDGE_CAN_FALLTHRU)
321 && !(e->flags & EDGE_COMPLEX))
325 /* The best edge is preferred. */
326 if (!e->dest->rbi->visited
327 || bbd[e->dest->index].start_of_trace >= 0)
329 /* The current edge E is also preferred. */
330 int freq = EDGE_FREQUENCY (e);
331 if (freq > best_freq || e->count > best_count)
334 best_count = e->count;
342 if (!e->dest->rbi->visited
343 || bbd[e->dest->index].start_of_trace >= 0)
345 /* The current edge E is preferred. */
347 best_freq = EDGE_FREQUENCY (e);
348 best_count = e->count;
354 int freq = EDGE_FREQUENCY (e);
355 if (!best_edge || freq > best_freq || e->count > best_count)
358 best_count = e->count;
367 while (bb != back_edge->dest);
371 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
373 if (back_edge->dest == trace->first)
375 trace->first = best_bb->rbi->next;
381 for (prev_bb = trace->first;
382 prev_bb->rbi->next != back_edge->dest;
383 prev_bb = prev_bb->rbi->next)
385 prev_bb->rbi->next = best_bb->rbi->next;
387 /* Try to get rid of uncond jump to cond jump. */
388 if (EDGE_COUNT (prev_bb->succs) == 1)
390 basic_block header = EDGE_SUCC (prev_bb, 0)->dest;
392 /* Duplicate HEADER if it is a small block containing cond jump
394 if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
395 && !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
398 copy_bb (header, EDGE_SUCC (prev_bb, 0), prev_bb, trace_n);
405 /* We have not found suitable loop tail so do no rotation. */
406 best_bb = back_edge->src;
408 best_bb->rbi->next = NULL;
412 /* This function marks BB that it was visited in trace number TRACE. */
415 mark_bb_visited (basic_block bb, int trace)
417 bb->rbi->visited = trace;
418 if (bbd[bb->index].heap)
420 fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
421 bbd[bb->index].heap = NULL;
422 bbd[bb->index].node = NULL;
426 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
427 not include basic blocks their probability is lower than BRANCH_TH or their
428 frequency is lower than EXEC_TH into traces (or count is lower than
429 COUNT_TH). It stores the new traces into TRACES and modifies the number of
430 traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
431 expects that starting basic blocks are in *HEAP and at the end it deletes
432 *HEAP and stores starting points for the next round into new *HEAP. */
435 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
436 struct trace *traces, int *n_traces, int round,
437 fibheap_t *heap, int number_of_rounds)
439 /* The following variable refers to the last round in which non-"cold"
440 blocks may be collected into a trace. */
442 int last_round = N_ROUNDS - 1;
444 /* Heap for discarded basic blocks which are possible starting points for
446 fibheap_t new_heap = fibheap_new ();
448 while (!fibheap_empty (*heap))
456 bb = fibheap_extract_min (*heap);
457 bbd[bb->index].heap = NULL;
458 bbd[bb->index].node = NULL;
461 fprintf (dump_file, "Getting bb %d\n", bb->index);
463 /* If the BB's frequency is too low send BB to the next round. When
464 partitioning hot/cold blocks into separate sections, make sure all
465 the cold blocks (and ONLY the cold blocks) go into the (extra) final
468 if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
471 int key = bb_to_key (bb);
472 bbd[bb->index].heap = new_heap;
473 bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
477 " Possible start point of next round: %d (key: %d)\n",
482 trace = traces + *n_traces;
484 trace->round = round;
493 /* The probability and frequency of the best edge. */
494 int best_prob = INT_MIN / 2;
495 int best_freq = INT_MIN / 2;
498 mark_bb_visited (bb, *n_traces);
502 fprintf (dump_file, "Basic block %d was visited in trace %d\n",
503 bb->index, *n_traces - 1);
505 ends_in_call = block_ends_with_call_p (bb);
507 /* Select the successor that will be placed after BB. */
508 FOR_EACH_EDGE (e, ei, bb->succs)
510 gcc_assert (!(e->flags & EDGE_FAKE));
512 if (e->dest == EXIT_BLOCK_PTR)
515 if (e->dest->rbi->visited
516 && e->dest->rbi->visited != *n_traces)
519 if (BB_PARTITION (e->dest) == BB_COLD_PARTITION
520 && round < last_round)
523 prob = e->probability;
524 freq = EDGE_FREQUENCY (e);
526 /* The only sensible preference for a call instruction is the
527 fallthru edge. Don't bother selecting anything else. */
530 if (e->flags & EDGE_CAN_FALLTHRU)
539 /* Edge that cannot be fallthru or improbable or infrequent
540 successor (i.e. it is unsuitable successor). */
541 if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
542 || prob < branch_th || freq < exec_th || e->count < count_th)
545 /* If partitioning hot/cold basic blocks, don't consider edges
546 that cross section boundaries. */
548 if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
557 /* If the best destination has multiple predecessors, and can be
558 duplicated cheaper than a jump, don't allow it to be added
559 to a trace. We'll duplicate it when connecting traces. */
560 if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2
561 && copy_bb_p (best_edge->dest, 0))
564 /* Add all non-selected successors to the heaps. */
565 FOR_EACH_EDGE (e, ei, bb->succs)
568 || e->dest == EXIT_BLOCK_PTR
569 || e->dest->rbi->visited)
572 key = bb_to_key (e->dest);
574 if (bbd[e->dest->index].heap)
576 /* E->DEST is already in some heap. */
577 if (key != bbd[e->dest->index].node->key)
582 "Changing key for bb %d from %ld to %ld.\n",
584 (long) bbd[e->dest->index].node->key,
587 fibheap_replace_key (bbd[e->dest->index].heap,
588 bbd[e->dest->index].node, key);
593 fibheap_t which_heap = *heap;
595 prob = e->probability;
596 freq = EDGE_FREQUENCY (e);
598 if (!(e->flags & EDGE_CAN_FALLTHRU)
599 || (e->flags & EDGE_COMPLEX)
600 || prob < branch_th || freq < exec_th
601 || e->count < count_th)
603 /* When partitioning hot/cold basic blocks, make sure
604 the cold blocks (and only the cold blocks) all get
605 pushed to the last round of trace collection. */
607 if (push_to_next_round_p (e->dest, round,
610 which_heap = new_heap;
613 bbd[e->dest->index].heap = which_heap;
614 bbd[e->dest->index].node = fibheap_insert (which_heap,
620 " Possible start of %s round: %d (key: %ld)\n",
621 (which_heap == new_heap) ? "next" : "this",
622 e->dest->index, (long) key);
628 if (best_edge) /* Suitable successor was found. */
630 if (best_edge->dest->rbi->visited == *n_traces)
632 /* We do nothing with one basic block loops. */
633 if (best_edge->dest != bb)
635 if (EDGE_FREQUENCY (best_edge)
636 > 4 * best_edge->dest->frequency / 5)
638 /* The loop has at least 4 iterations. If the loop
639 header is not the first block of the function
640 we can rotate the loop. */
642 if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
647 "Rotating loop %d - %d\n",
648 best_edge->dest->index, bb->index);
650 bb->rbi->next = best_edge->dest;
651 bb = rotate_loop (best_edge, trace, *n_traces);
656 /* The loop has less than 4 iterations. */
658 if (EDGE_COUNT (bb->succs) == 1
659 && copy_bb_p (best_edge->dest, !optimize_size))
661 bb = copy_bb (best_edge->dest, best_edge, bb,
667 /* Terminate the trace. */
672 /* Check for a situation
681 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
682 >= EDGE_FREQUENCY (AC).
683 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
684 Best ordering is then A B C.
686 This situation is created for example by:
693 FOR_EACH_EDGE (e, ei, bb->succs)
695 && (e->flags & EDGE_CAN_FALLTHRU)
696 && !(e->flags & EDGE_COMPLEX)
697 && !e->dest->rbi->visited
698 && EDGE_COUNT (e->dest->preds) == 1
699 && !(e->flags & EDGE_CROSSING)
700 && EDGE_COUNT (e->dest->succs) == 1
701 && (EDGE_SUCC (e->dest, 0)->flags & EDGE_CAN_FALLTHRU)
702 && !(EDGE_SUCC (e->dest, 0)->flags & EDGE_COMPLEX)
703 && EDGE_SUCC (e->dest, 0)->dest == best_edge->dest
704 && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
708 fprintf (dump_file, "Selecting BB %d\n",
709 best_edge->dest->index);
713 bb->rbi->next = best_edge->dest;
714 bb = best_edge->dest;
720 bbd[trace->first->index].start_of_trace = *n_traces - 1;
721 bbd[trace->last->index].end_of_trace = *n_traces - 1;
723 /* The trace is terminated so we have to recount the keys in heap
724 (some block can have a lower key because now one of its predecessors
725 is an end of the trace). */
726 FOR_EACH_EDGE (e, ei, bb->succs)
728 if (e->dest == EXIT_BLOCK_PTR
729 || e->dest->rbi->visited)
732 if (bbd[e->dest->index].heap)
734 key = bb_to_key (e->dest);
735 if (key != bbd[e->dest->index].node->key)
740 "Changing key for bb %d from %ld to %ld.\n",
742 (long) bbd[e->dest->index].node->key, key);
744 fibheap_replace_key (bbd[e->dest->index].heap,
745 bbd[e->dest->index].node,
752 fibheap_delete (*heap);
754 /* "Return" the new heap. */
758 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
759 it to trace after BB, mark OLD_BB visited and update pass' data structures
760 (TRACE is a number of trace which OLD_BB is duplicated to). */
763 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
767 new_bb = duplicate_block (old_bb, e);
768 BB_COPY_PARTITION (new_bb, old_bb);
770 gcc_assert (e->dest == new_bb);
771 gcc_assert (!e->dest->rbi->visited);
775 "Duplicated bb %d (created bb %d)\n",
776 old_bb->index, new_bb->index);
777 new_bb->rbi->visited = trace;
778 new_bb->rbi->next = bb->rbi->next;
779 bb->rbi->next = new_bb;
781 if (new_bb->index >= array_size || last_basic_block > array_size)
786 new_size = MAX (last_basic_block, new_bb->index + 1);
787 new_size = GET_ARRAY_SIZE (new_size);
788 bbd = xrealloc (bbd, new_size * sizeof (bbro_basic_block_data));
789 for (i = array_size; i < new_size; i++)
791 bbd[i].start_of_trace = -1;
792 bbd[i].end_of_trace = -1;
796 array_size = new_size;
801 "Growing the dynamic array to %d elements.\n",
809 /* Compute and return the key (for the heap) of the basic block BB. */
812 bb_to_key (basic_block bb)
818 /* Do not start in probably never executed blocks. */
820 if (BB_PARTITION (bb) == BB_COLD_PARTITION
821 || probably_never_executed_bb_p (bb))
824 /* Prefer blocks whose predecessor is an end of some trace
825 or whose predecessor edge is EDGE_DFS_BACK. */
826 FOR_EACH_EDGE (e, ei, bb->preds)
828 if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
829 || (e->flags & EDGE_DFS_BACK))
831 int edge_freq = EDGE_FREQUENCY (e);
833 if (edge_freq > priority)
834 priority = edge_freq;
839 /* The block with priority should have significantly lower key. */
840 return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
841 return -bb->frequency;
844 /* Return true when the edge E from basic block BB is better than the temporary
845 best edge (details are in function). The probability of edge E is PROB. The
846 frequency of the successor is FREQ. The current best probability is
847 BEST_PROB, the best frequency is BEST_FREQ.
848 The edge is considered to be equivalent when PROB does not differ much from
849 BEST_PROB; similarly for frequency. */
852 better_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob,
853 int best_freq, edge cur_best_edge)
857 /* The BEST_* values do not have to be best, but can be a bit smaller than
859 int diff_prob = best_prob / 10;
860 int diff_freq = best_freq / 10;
862 if (prob > best_prob + diff_prob)
863 /* The edge has higher probability than the temporary best edge. */
864 is_better_edge = true;
865 else if (prob < best_prob - diff_prob)
866 /* The edge has lower probability than the temporary best edge. */
867 is_better_edge = false;
868 else if (freq < best_freq - diff_freq)
869 /* The edge and the temporary best edge have almost equivalent
870 probabilities. The higher frequency of a successor now means
871 that there is another edge going into that successor.
872 This successor has lower frequency so it is better. */
873 is_better_edge = true;
874 else if (freq > best_freq + diff_freq)
875 /* This successor has higher frequency so it is worse. */
876 is_better_edge = false;
877 else if (e->dest->prev_bb == bb)
878 /* The edges have equivalent probabilities and the successors
879 have equivalent frequencies. Select the previous successor. */
880 is_better_edge = true;
882 is_better_edge = false;
884 /* If we are doing hot/cold partitioning, make sure that we always favor
885 non-crossing edges over crossing edges. */
888 && flag_reorder_blocks_and_partition
890 && (cur_best_edge->flags & EDGE_CROSSING)
891 && !(e->flags & EDGE_CROSSING))
892 is_better_edge = true;
894 return is_better_edge;
897 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
900 connect_traces (int n_traces, struct trace *traces)
903 int unconnected_hot_trace_count = 0;
904 bool cold_connected = true;
909 gcov_type count_threshold;
911 freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
912 if (max_entry_count < INT_MAX / 1000)
913 count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
915 count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
917 connected = xcalloc (n_traces, sizeof (bool));
920 /* If we are partitioning hot/cold basic blocks, mark the cold
921 traces as already connected, to remove them from consideration
922 for connection to the hot traces. After the hot traces have all
923 been connected (determined by "unconnected_hot_trace_count"), we
924 will go back and connect the cold traces. */
926 cold_traces = xcalloc (n_traces, sizeof (bool));
928 if (flag_reorder_blocks_and_partition)
929 for (i = 0; i < n_traces; i++)
931 if (BB_PARTITION (traces[i].first) == BB_COLD_PARTITION)
934 cold_traces[i] = true;
935 cold_connected = false;
938 unconnected_hot_trace_count++;
941 for (i = 0; i < n_traces || !cold_connected ; i++)
948 /* If we are partitioning hot/cold basic blocks, check to see
949 if all the hot traces have been connected. If so, go back
950 and mark the cold traces as unconnected so we can connect
951 them up too. Re-set "i" to the first (unconnected) cold
952 trace. Use flag "cold_connected" to make sure we don't do
953 this step more than once. */
955 if (flag_reorder_blocks_and_partition
956 && (i >= n_traces || unconnected_hot_trace_count <= 0)
960 int first_cold_trace = -1;
962 for (j = 0; j < n_traces; j++)
965 connected[j] = false;
966 if (first_cold_trace == -1)
967 first_cold_trace = j;
969 i = t = first_cold_trace;
970 cold_connected = true;
977 if (unconnected_hot_trace_count > 0)
978 unconnected_hot_trace_count--;
980 /* Find the predecessor traces. */
981 for (t2 = t; t2 > 0;)
986 FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
988 int si = e->src->index;
990 if (e->src != ENTRY_BLOCK_PTR
991 && (e->flags & EDGE_CAN_FALLTHRU)
992 && !(e->flags & EDGE_COMPLEX)
993 && bbd[si].end_of_trace >= 0
994 && !connected[bbd[si].end_of_trace]
996 || e->probability > best->probability
997 || (e->probability == best->probability
998 && traces[bbd[si].end_of_trace].length > best_len)))
1001 best_len = traces[bbd[si].end_of_trace].length;
1006 best->src->rbi->next = best->dest;
1007 t2 = bbd[best->src->index].end_of_trace;
1008 connected[t2] = true;
1010 if (unconnected_hot_trace_count > 0)
1011 unconnected_hot_trace_count--;
1015 fprintf (dump_file, "Connection: %d %d\n",
1016 best->src->index, best->dest->index);
1023 if (last_trace >= 0)
1024 traces[last_trace].last->rbi->next = traces[t2].first;
1027 /* Find the successor traces. */
1030 /* Find the continuation of the chain. */
1034 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1036 int di = e->dest->index;
1038 if (e->dest != EXIT_BLOCK_PTR
1039 && (e->flags & EDGE_CAN_FALLTHRU)
1040 && !(e->flags & EDGE_COMPLEX)
1041 && bbd[di].start_of_trace >= 0
1042 && !connected[bbd[di].start_of_trace]
1044 || e->probability > best->probability
1045 || (e->probability == best->probability
1046 && traces[bbd[di].start_of_trace].length > best_len)))
1049 best_len = traces[bbd[di].start_of_trace].length;
1057 fprintf (dump_file, "Connection: %d %d\n",
1058 best->src->index, best->dest->index);
1060 t = bbd[best->dest->index].start_of_trace;
1061 traces[last_trace].last->rbi->next = traces[t].first;
1062 connected[t] = true;
1063 if (unconnected_hot_trace_count > 0)
1064 unconnected_hot_trace_count--;
1069 /* Try to connect the traces by duplication of 1 block. */
1071 basic_block next_bb = NULL;
1072 bool try_copy = false;
1074 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1075 if (e->dest != EXIT_BLOCK_PTR
1076 && (e->flags & EDGE_CAN_FALLTHRU)
1077 && !(e->flags & EDGE_COMPLEX)
1078 && (!best || e->probability > best->probability))
1084 /* If the destination is a start of a trace which is only
1085 one block long, then no need to search the successor
1086 blocks of the trace. Accept it. */
1087 if (bbd[e->dest->index].start_of_trace >= 0
1088 && traces[bbd[e->dest->index].start_of_trace].length
1096 FOR_EACH_EDGE (e2, ei, e->dest->succs)
1098 int di = e2->dest->index;
1100 if (e2->dest == EXIT_BLOCK_PTR
1101 || ((e2->flags & EDGE_CAN_FALLTHRU)
1102 && !(e2->flags & EDGE_COMPLEX)
1103 && bbd[di].start_of_trace >= 0
1104 && !connected[bbd[di].start_of_trace]
1105 && (EDGE_FREQUENCY (e2) >= freq_threshold)
1106 && (e2->count >= count_threshold)
1108 || e2->probability > best2->probability
1109 || (e2->probability == best2->probability
1110 && traces[bbd[di].start_of_trace].length
1115 if (e2->dest != EXIT_BLOCK_PTR)
1116 best2_len = traces[bbd[di].start_of_trace].length;
1118 best2_len = INT_MAX;
1125 if (flag_reorder_blocks_and_partition)
1128 /* Copy tiny blocks always; copy larger blocks only when the
1129 edge is traversed frequently enough. */
1131 && copy_bb_p (best->dest,
1133 && EDGE_FREQUENCY (best) >= freq_threshold
1134 && best->count >= count_threshold))
1140 fprintf (dump_file, "Connection: %d %d ",
1141 traces[t].last->index, best->dest->index);
1143 fputc ('\n', dump_file);
1144 else if (next_bb == EXIT_BLOCK_PTR)
1145 fprintf (dump_file, "exit\n");
1147 fprintf (dump_file, "%d\n", next_bb->index);
1150 new_bb = copy_bb (best->dest, best, traces[t].last, t);
1151 traces[t].last = new_bb;
1152 if (next_bb && next_bb != EXIT_BLOCK_PTR)
1154 t = bbd[next_bb->index].start_of_trace;
1155 traces[last_trace].last->rbi->next = traces[t].first;
1156 connected[t] = true;
1157 if (unconnected_hot_trace_count > 0)
1158 unconnected_hot_trace_count--;
1162 break; /* Stop finding the successor traces. */
1165 break; /* Stop finding the successor traces. */
1174 fprintf (dump_file, "Final order:\n");
1175 for (bb = traces[0].first; bb; bb = bb->rbi->next)
1176 fprintf (dump_file, "%d ", bb->index);
1177 fprintf (dump_file, "\n");
1185 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1186 when code size is allowed to grow by duplication. */
1189 copy_bb_p (basic_block bb, int code_may_grow)
1192 int max_size = uncond_jump_length;
1197 if (EDGE_COUNT (bb->preds) < 2)
1199 if (!can_duplicate_block_p (bb))
1202 /* Avoid duplicating blocks which have many successors (PR/13430). */
1203 if (EDGE_COUNT (bb->succs) > 8)
1206 if (code_may_grow && maybe_hot_bb_p (bb))
1209 FOR_BB_INSNS (bb, insn)
1212 size += get_attr_length (insn);
1215 if (size <= max_size)
1221 "Block %d can't be copied because its size = %d.\n",
1228 /* Return the length of unconditional jump instruction. */
1231 get_uncond_jump_length (void)
1236 label = emit_label_before (gen_label_rtx (), get_insns ());
1237 jump = emit_jump_insn (gen_jump (label));
1239 length = get_attr_length (jump);
1242 delete_insn (label);
1247 add_unlikely_executed_notes (void)
1251 /* Add the UNLIKELY_EXECUTED_NOTES to each cold basic block. */
1254 if (BB_PARTITION (bb) == BB_COLD_PARTITION)
1255 mark_bb_for_unlikely_executed_section (bb);
1258 /* Find the basic blocks that are rarely executed and need to be moved to
1259 a separate section of the .o file (to cut down on paging and improve
1263 find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges,
1264 int *n_crossing_edges,
1268 bool has_hot_blocks = false;
1273 /* Mark which partition (hot/cold) each basic block belongs in. */
1277 if (probably_never_executed_bb_p (bb))
1278 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1281 BB_SET_PARTITION (bb, BB_HOT_PARTITION);
1282 has_hot_blocks = true;
1286 /* Since all "hot" basic blocks will eventually be scheduled before all
1287 cold basic blocks, make *sure* the real function entry block is in
1288 the hot partition (if there is one). */
1291 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1292 if (e->dest->index >= 0)
1294 BB_SET_PARTITION (e->dest, BB_HOT_PARTITION);
1298 /* Mark every edge that crosses between sections. */
1301 if (targetm.have_named_sections)
1304 FOR_EACH_EDGE (e, ei, bb->succs)
1306 if (e->src != ENTRY_BLOCK_PTR
1307 && e->dest != EXIT_BLOCK_PTR
1308 && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1310 e->flags |= EDGE_CROSSING;
1314 crossing_edges = xrealloc (crossing_edges,
1315 (*max_idx) * sizeof (edge));
1317 crossing_edges[i++] = e;
1320 e->flags &= ~EDGE_CROSSING;
1323 *n_crossing_edges = i;
1326 /* Add NOTE_INSN_UNLIKELY_EXECUTED_CODE to top of basic block. This note
1327 is later used to mark the basic block to be put in the
1328 unlikely-to-be-executed section of the .o file. */
1331 mark_bb_for_unlikely_executed_section (basic_block bb)
1334 rtx insert_insn = NULL;
1337 /* Insert new NOTE immediately after BASIC_BLOCK note. */
1339 for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb));
1340 cur_insn = NEXT_INSN (cur_insn))
1341 if (GET_CODE (cur_insn) == NOTE
1342 && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_BASIC_BLOCK)
1344 insert_insn = cur_insn;
1348 /* If basic block does not contain a NOTE_INSN_BASIC_BLOCK, there is
1350 gcc_assert (insert_insn);
1352 /* Insert note and assign basic block number to it. */
1354 new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
1356 NOTE_BASIC_BLOCK (new_note) = bb;
1359 /* If any destination of a crossing edge does not have a label, add label;
1360 Convert any fall-through crossing edges (for blocks that do not contain
1361 a jump) to unconditional jumps. */
1364 add_labels_and_missing_jumps (edge *crossing_edges, int n_crossing_edges)
1373 for (i=0; i < n_crossing_edges; i++)
1375 if (crossing_edges[i])
1377 src = crossing_edges[i]->src;
1378 dest = crossing_edges[i]->dest;
1380 /* Make sure dest has a label. */
1382 if (dest && (dest != EXIT_BLOCK_PTR))
1384 label = block_label (dest);
1386 /* Make sure source block ends with a jump. */
1388 if (src && (src != ENTRY_BLOCK_PTR))
1390 if (!JUMP_P (BB_END (src)))
1391 /* bb just falls through. */
1393 /* make sure there's only one successor */
1394 gcc_assert (EDGE_COUNT (src->succs) == 1);
1396 /* Find label in dest block. */
1397 label = block_label (dest);
1399 new_jump = emit_jump_insn_after (gen_jump (label),
1401 barrier = emit_barrier_after (new_jump);
1402 JUMP_LABEL (new_jump) = label;
1403 LABEL_NUSES (label) += 1;
1404 src->rbi->footer = unlink_insn_chain (barrier, barrier);
1405 /* Mark edge as non-fallthru. */
1406 crossing_edges[i]->flags &= ~EDGE_FALLTHRU;
1407 } /* end: 'if (GET_CODE ... ' */
1408 } /* end: 'if (src && src->index...' */
1409 } /* end: 'if (dest && dest->index...' */
1410 } /* end: 'if (crossing_edges[i]...' */
1411 } /* end for loop */
1414 /* Find any bb's where the fall-through edge is a crossing edge (note that
1415 these bb's must also contain a conditional jump; we've already
1416 dealt with fall-through edges for blocks that didn't have a
1417 conditional jump in the call to add_labels_and_missing_jumps).
1418 Convert the fall-through edge to non-crossing edge by inserting a
1419 new bb to fall-through into. The new bb will contain an
1420 unconditional jump (crossing edge) to the original fall through
1424 fix_up_fall_thru_edges (void)
1431 edge cond_jump = NULL;
1433 bool cond_jump_crosses;
1436 rtx fall_thru_label;
1439 FOR_EACH_BB (cur_bb)
1442 if (EDGE_COUNT (cur_bb->succs) > 0)
1443 succ1 = EDGE_SUCC (cur_bb, 0);
1447 if (EDGE_COUNT (cur_bb->succs) > 1)
1448 succ2 = EDGE_SUCC (cur_bb, 1);
1452 /* Find the fall-through edge. */
1455 && (succ1->flags & EDGE_FALLTHRU))
1461 && (succ2->flags & EDGE_FALLTHRU))
1467 if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
1469 /* Check to see if the fall-thru edge is a crossing edge. */
1471 if (fall_thru->flags & EDGE_CROSSING)
1473 /* The fall_thru edge crosses; now check the cond jump edge, if
1476 cond_jump_crosses = true;
1478 old_jump = BB_END (cur_bb);
1480 /* Find the jump instruction, if there is one. */
1484 if (!(cond_jump->flags & EDGE_CROSSING))
1485 cond_jump_crosses = false;
1487 /* We know the fall-thru edge crosses; if the cond
1488 jump edge does NOT cross, and its destination is the
1489 next block in the bb order, invert the jump
1490 (i.e. fix it so the fall thru does not cross and
1491 the cond jump does). */
1493 if (!cond_jump_crosses
1494 && cur_bb->rbi->next == cond_jump->dest)
1496 /* Find label in fall_thru block. We've already added
1497 any missing labels, so there must be one. */
1499 fall_thru_label = block_label (fall_thru->dest);
1501 if (old_jump && fall_thru_label)
1502 invert_worked = invert_jump (old_jump,
1506 fall_thru->flags &= ~EDGE_FALLTHRU;
1507 cond_jump->flags |= EDGE_FALLTHRU;
1508 update_br_prob_note (cur_bb);
1510 fall_thru = cond_jump;
1512 cond_jump->flags |= EDGE_CROSSING;
1513 fall_thru->flags &= ~EDGE_CROSSING;
1518 if (cond_jump_crosses || !invert_worked)
1520 /* This is the case where both edges out of the basic
1521 block are crossing edges. Here we will fix up the
1522 fall through edge. The jump edge will be taken care
1525 new_bb = force_nonfallthru (fall_thru);
1529 new_bb->rbi->next = cur_bb->rbi->next;
1530 cur_bb->rbi->next = new_bb;
1532 /* Make sure new fall-through bb is in same
1533 partition as bb it's falling through from. */
1535 BB_COPY_PARTITION (new_bb, cur_bb);
1536 EDGE_SUCC (new_bb, 0)->flags |= EDGE_CROSSING;
1539 /* Add barrier after new jump */
1543 barrier = emit_barrier_after (BB_END (new_bb));
1544 new_bb->rbi->footer = unlink_insn_chain (barrier,
1549 barrier = emit_barrier_after (BB_END (cur_bb));
1550 cur_bb->rbi->footer = unlink_insn_chain (barrier,
1559 /* This function checks the destination blockof a "crossing jump" to
1560 see if it has any crossing predecessors that begin with a code label
1561 and end with an unconditional jump. If so, it returns that predecessor
1562 block. (This is to avoid creating lots of new basic blocks that all
1563 contain unconditional jumps to the same destination). */
1566 find_jump_block (basic_block jump_dest)
1568 basic_block source_bb = NULL;
1573 FOR_EACH_EDGE (e, ei, jump_dest->preds)
1574 if (e->flags & EDGE_CROSSING)
1576 basic_block src = e->src;
1578 /* Check each predecessor to see if it has a label, and contains
1579 only one executable instruction, which is an unconditional jump.
1580 If so, we can use it. */
1582 if (LABEL_P (BB_HEAD (src)))
1583 for (insn = BB_HEAD (src);
1584 !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
1585 insn = NEXT_INSN (insn))
1588 && insn == BB_END (src)
1590 && !any_condjump_p (insn))
1604 /* Find all BB's with conditional jumps that are crossing edges;
1605 insert a new bb and make the conditional jump branch to the new
1606 bb instead (make the new bb same color so conditional branch won't
1607 be a 'crossing' edge). Insert an unconditional jump from the
1608 new bb to the original destination of the conditional jump. */
1611 fix_crossing_conditional_branches (void)
1615 basic_block last_bb;
1617 basic_block prev_bb;
1624 rtx old_label = NULL_RTX;
1629 last_bb = EXIT_BLOCK_PTR->prev_bb;
1631 FOR_EACH_BB (cur_bb)
1633 crossing_edge = NULL;
1634 if (EDGE_COUNT (cur_bb->succs) > 0)
1635 succ1 = EDGE_SUCC (cur_bb, 0);
1639 if (EDGE_COUNT (cur_bb->succs) > 1)
1640 succ2 = EDGE_SUCC (cur_bb, 1);
1644 /* We already took care of fall-through edges, so only one successor
1645 can be a crossing edge. */
1647 if (succ1 && (succ1->flags & EDGE_CROSSING))
1648 crossing_edge = succ1;
1649 else if (succ2 && (succ2->flags & EDGE_CROSSING))
1650 crossing_edge = succ2;
1654 old_jump = BB_END (cur_bb);
1656 /* Check to make sure the jump instruction is a
1657 conditional jump. */
1661 if (any_condjump_p (old_jump))
1663 if (GET_CODE (PATTERN (old_jump)) == SET)
1664 set_src = SET_SRC (PATTERN (old_jump));
1665 else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
1667 set_src = XVECEXP (PATTERN (old_jump), 0,0);
1668 if (GET_CODE (set_src) == SET)
1669 set_src = SET_SRC (set_src);
1675 if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
1677 if (GET_CODE (XEXP (set_src, 1)) == PC)
1678 old_label = XEXP (set_src, 2);
1679 else if (GET_CODE (XEXP (set_src, 2)) == PC)
1680 old_label = XEXP (set_src, 1);
1682 /* Check to see if new bb for jumping to that dest has
1683 already been created; if so, use it; if not, create
1686 new_bb = find_jump_block (crossing_edge->dest);
1689 new_label = block_label (new_bb);
1692 /* Create new basic block to be dest for
1693 conditional jump. */
1695 new_bb = create_basic_block (NULL, NULL, last_bb);
1696 new_bb->rbi->next = last_bb->rbi->next;
1697 last_bb->rbi->next = new_bb;
1701 /* Update register liveness information. */
1703 new_bb->global_live_at_start = ALLOC_REG_SET (®_obstack);
1704 new_bb->global_live_at_end = ALLOC_REG_SET (®_obstack);
1705 COPY_REG_SET (new_bb->global_live_at_end,
1706 prev_bb->global_live_at_end);
1707 COPY_REG_SET (new_bb->global_live_at_start,
1708 prev_bb->global_live_at_end);
1710 /* Put appropriate instructions in new bb. */
1712 new_label = gen_label_rtx ();
1713 emit_label_before (new_label, BB_HEAD (new_bb));
1714 BB_HEAD (new_bb) = new_label;
1716 if (GET_CODE (old_label) == LABEL_REF)
1718 old_label = JUMP_LABEL (old_jump);
1719 new_jump = emit_jump_insn_after (gen_jump
1725 gcc_assert (HAVE_return
1726 && GET_CODE (old_label) == RETURN);
1727 new_jump = emit_jump_insn_after (gen_return (),
1731 barrier = emit_barrier_after (new_jump);
1732 JUMP_LABEL (new_jump) = old_label;
1733 new_bb->rbi->footer = unlink_insn_chain (barrier,
1736 /* Make sure new bb is in same partition as source
1737 of conditional branch. */
1738 BB_COPY_PARTITION (new_bb, cur_bb);
1741 /* Make old jump branch to new bb. */
1743 redirect_jump (old_jump, new_label, 0);
1745 /* Remove crossing_edge as predecessor of 'dest'. */
1747 dest = crossing_edge->dest;
1749 redirect_edge_succ (crossing_edge, new_bb);
1751 /* Make a new edge from new_bb to old dest; new edge
1752 will be a successor for new_bb and a predecessor
1755 if (EDGE_COUNT (new_bb->succs) == 0)
1756 new_edge = make_edge (new_bb, dest, 0);
1758 new_edge = EDGE_SUCC (new_bb, 0);
1760 crossing_edge->flags &= ~EDGE_CROSSING;
1761 new_edge->flags |= EDGE_CROSSING;
1767 /* Find any unconditional branches that cross between hot and cold
1768 sections. Convert them into indirect jumps instead. */
1771 fix_crossing_unconditional_branches (void)
1777 rtx indirect_jump_sequence;
1778 rtx jump_insn = NULL_RTX;
1783 FOR_EACH_BB (cur_bb)
1785 last_insn = BB_END (cur_bb);
1786 succ = EDGE_SUCC (cur_bb, 0);
1788 /* Check to see if bb ends in a crossing (unconditional) jump. At
1789 this point, no crossing jumps should be conditional. */
1791 if (JUMP_P (last_insn)
1792 && (succ->flags & EDGE_CROSSING))
1796 gcc_assert (!any_condjump_p (last_insn));
1798 /* Make sure the jump is not already an indirect or table jump. */
1800 if (!computed_jump_p (last_insn)
1801 && !tablejump_p (last_insn, &label2, &table))
1803 /* We have found a "crossing" unconditional branch. Now
1804 we must convert it to an indirect jump. First create
1805 reference of label, as target for jump. */
1807 label = JUMP_LABEL (last_insn);
1808 label_addr = gen_rtx_LABEL_REF (Pmode, label);
1809 LABEL_NUSES (label) += 1;
1811 /* Get a register to use for the indirect jump. */
1813 new_reg = gen_reg_rtx (Pmode);
1815 /* Generate indirect the jump sequence. */
1818 emit_move_insn (new_reg, label_addr);
1819 emit_indirect_jump (new_reg);
1820 indirect_jump_sequence = get_insns ();
1823 /* Make sure every instruction in the new jump sequence has
1824 its basic block set to be cur_bb. */
1826 for (cur_insn = indirect_jump_sequence; cur_insn;
1827 cur_insn = NEXT_INSN (cur_insn))
1829 BLOCK_FOR_INSN (cur_insn) = cur_bb;
1830 if (JUMP_P (cur_insn))
1831 jump_insn = cur_insn;
1834 /* Insert the new (indirect) jump sequence immediately before
1835 the unconditional jump, then delete the unconditional jump. */
1837 emit_insn_before (indirect_jump_sequence, last_insn);
1838 delete_insn (last_insn);
1840 /* Make BB_END for cur_bb be the jump instruction (NOT the
1841 barrier instruction at the end of the sequence...). */
1843 BB_END (cur_bb) = jump_insn;
1849 /* Add REG_CROSSING_JUMP note to all crossing jump insns. */
1852 add_reg_crossing_jump_notes (void)
1859 FOR_EACH_EDGE (e, ei, bb->succs)
1860 if ((e->flags & EDGE_CROSSING)
1861 && JUMP_P (BB_END (e->src)))
1862 REG_NOTES (BB_END (e->src)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
1868 /* Basic blocks containing NOTE_INSN_UNLIKELY_EXECUTED_CODE will be
1869 put in a separate section of the .o file, to reduce paging and
1870 improve cache performance (hopefully). This can result in bits of
1871 code from the same function being widely separated in the .o file.
1872 However this is not obvious to the current bb structure. Therefore
1873 we must take care to ensure that: 1). There are no fall_thru edges
1874 that cross between sections; 2). For those architectures which
1875 have "short" conditional branches, all conditional branches that
1876 attempt to cross between sections are converted to unconditional
1877 branches; and, 3). For those architectures which have "short"
1878 unconditional branches, all unconditional branches that attempt
1879 to cross between sections are converted to indirect jumps.
1881 The code for fixing up fall_thru edges that cross between hot and
1882 cold basic blocks does so by creating new basic blocks containing
1883 unconditional branches to the appropriate label in the "other"
1884 section. The new basic block is then put in the same (hot or cold)
1885 section as the original conditional branch, and the fall_thru edge
1886 is modified to fall into the new basic block instead. By adding
1887 this level of indirection we end up with only unconditional branches
1888 crossing between hot and cold sections.
1890 Conditional branches are dealt with by adding a level of indirection.
1891 A new basic block is added in the same (hot/cold) section as the
1892 conditional branch, and the conditional branch is retargeted to the
1893 new basic block. The new basic block contains an unconditional branch
1894 to the original target of the conditional branch (in the other section).
1896 Unconditional branches are dealt with by converting them into
1900 fix_edges_for_rarely_executed_code (edge *crossing_edges,
1901 int n_crossing_edges)
1903 /* Make sure the source of any crossing edge ends in a jump and the
1904 destination of any crossing edge has a label. */
1906 add_labels_and_missing_jumps (crossing_edges, n_crossing_edges);
1908 /* Convert all crossing fall_thru edges to non-crossing fall
1909 thrus to unconditional jumps (that jump to the original fall
1912 fix_up_fall_thru_edges ();
1914 /* Only do the parts necessary for writing separate sections if
1915 the target architecture has the ability to write separate sections
1916 (i.e. it has named sections). Otherwise, the hot/cold partitioning
1917 information will be used when reordering blocks to try to put all
1918 the hot blocks together, then all the cold blocks, but no actual
1919 section partitioning will be done. */
1921 if (targetm.have_named_sections)
1923 /* If the architecture does not have conditional branches that can
1924 span all of memory, convert crossing conditional branches into
1925 crossing unconditional branches. */
1927 if (!HAS_LONG_COND_BRANCH)
1928 fix_crossing_conditional_branches ();
1930 /* If the architecture does not have unconditional branches that
1931 can span all of memory, convert crossing unconditional branches
1932 into indirect jumps. Since adding an indirect jump also adds
1933 a new register usage, update the register usage information as
1936 if (!HAS_LONG_UNCOND_BRANCH)
1938 fix_crossing_unconditional_branches ();
1939 reg_scan (get_insns(), max_reg_num ());
1942 add_reg_crossing_jump_notes ();
1946 /* Reorder basic blocks. The main entry point to this file. FLAGS is
1947 the set of flags to pass to cfg_layout_initialize(). */
1950 reorder_basic_blocks (unsigned int flags)
1954 struct trace *traces;
1956 if (n_basic_blocks <= 1)
1959 if (targetm.cannot_modify_jumps_p ())
1962 timevar_push (TV_REORDER_BLOCKS);
1964 cfg_layout_initialize (flags);
1966 set_edge_can_fallthru_flag ();
1967 mark_dfs_back_edges ();
1969 /* We are estimating the length of uncond jump insn only once since the code
1970 for getting the insn length always returns the minimal length now. */
1971 if (uncond_jump_length == 0)
1972 uncond_jump_length = get_uncond_jump_length ();
1974 /* We need to know some information for each basic block. */
1975 array_size = GET_ARRAY_SIZE (last_basic_block);
1976 bbd = xmalloc (array_size * sizeof (bbro_basic_block_data));
1977 for (i = 0; i < array_size; i++)
1979 bbd[i].start_of_trace = -1;
1980 bbd[i].end_of_trace = -1;
1985 traces = xmalloc (n_basic_blocks * sizeof (struct trace));
1987 find_traces (&n_traces, traces);
1988 connect_traces (n_traces, traces);
1993 dump_flow_info (dump_file);
1995 if (flag_reorder_blocks_and_partition
1996 && targetm.have_named_sections)
1997 add_unlikely_executed_notes ();
1999 cfg_layout_finalize ();
2001 timevar_pop (TV_REORDER_BLOCKS);
2004 /* Duplicate the blocks containing computed gotos. This basically unfactors
2005 computed gotos that were factored early on in the compilation process to
2006 speed up edge based data flow. We used to not unfactoring them again,
2007 which can seriously pessimize code with many computed jumps in the source
2008 code, such as interpreters. See e.g. PR15242. */
2011 duplicate_computed_gotos (void)
2013 basic_block bb, new_bb;
2017 if (n_basic_blocks <= 1)
2020 if (targetm.cannot_modify_jumps_p ())
2023 timevar_push (TV_REORDER_BLOCKS);
2025 cfg_layout_initialize (0);
2027 /* We are estimating the length of uncond jump insn only once
2028 since the code for getting the insn length always returns
2029 the minimal length now. */
2030 if (uncond_jump_length == 0)
2031 uncond_jump_length = get_uncond_jump_length ();
2033 max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
2034 candidates = BITMAP_ALLOC (NULL);
2036 /* Look for blocks that end in a computed jump, and see if such blocks
2037 are suitable for unfactoring. If a block is a candidate for unfactoring,
2038 mark it in the candidates. */
2044 int size, all_flags;
2046 /* Build the reorder chain for the original order of blocks. */
2047 if (bb->next_bb != EXIT_BLOCK_PTR)
2048 bb->rbi->next = bb->next_bb;
2050 /* Obviously the block has to end in a computed jump. */
2051 if (!computed_jump_p (BB_END (bb)))
2054 /* Only consider blocks that can be duplicated. */
2055 if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX)
2056 || !can_duplicate_block_p (bb))
2059 /* Make sure that the block is small enough. */
2061 FOR_BB_INSNS (bb, insn)
2064 size += get_attr_length (insn);
2065 if (size > max_size)
2068 if (size > max_size)
2071 /* Final check: there must not be any incoming abnormal edges. */
2073 FOR_EACH_EDGE (e, ei, bb->preds)
2074 all_flags |= e->flags;
2075 if (all_flags & EDGE_COMPLEX)
2078 bitmap_set_bit (candidates, bb->index);
2081 /* Nothing to do if there is no computed jump here. */
2082 if (bitmap_empty_p (candidates))
2085 /* Duplicate computed gotos. */
2088 if (bb->rbi->visited)
2091 bb->rbi->visited = 1;
2093 /* BB must have one outgoing edge. That edge must not lead to
2094 the exit block or the next block.
2095 The destination must have more than one predecessor. */
2096 if (EDGE_COUNT(bb->succs) != 1
2097 || EDGE_SUCC(bb,0)->dest == EXIT_BLOCK_PTR
2098 || EDGE_SUCC(bb,0)->dest == bb->next_bb
2099 || EDGE_COUNT(EDGE_SUCC(bb,0)->dest->preds) <= 1)
2102 /* The successor block has to be a duplication candidate. */
2103 if (!bitmap_bit_p (candidates, EDGE_SUCC(bb,0)->dest->index))
2106 new_bb = duplicate_block (EDGE_SUCC(bb,0)->dest, EDGE_SUCC(bb,0));
2107 new_bb->rbi->next = bb->rbi->next;
2108 bb->rbi->next = new_bb;
2109 new_bb->rbi->visited = 1;
2113 cfg_layout_finalize ();
2115 BITMAP_FREE (candidates);
2117 timevar_pop (TV_REORDER_BLOCKS);
2120 /* This function is the main 'entrance' for the optimization that
2121 partitions hot and cold basic blocks into separate sections of the
2122 .o file (to improve performance and cache locality). Ideally it
2123 would be called after all optimizations that rearrange the CFG have
2124 been called. However part of this optimization may introduce new
2125 register usage, so it must be called before register allocation has
2126 occurred. This means that this optimization is actually called
2127 well before the optimization that reorders basic blocks (see
2130 This optimization checks the feedback information to determine
2131 which basic blocks are hot/cold and causes reorder_basic_blocks to
2132 add NOTE_INSN_UNLIKELY_EXECUTED_CODE to non-hot basic blocks. The
2133 presence or absence of this note is later used for writing out
2134 sections in the .o file. Because hot and cold sections can be
2135 arbitrarily large (within the bounds of memory), far beyond the
2136 size of a single function, it is necessary to fix up all edges that
2137 cross section boundaries, to make sure the instructions used can
2138 actually span the required distance. The fixes are described
2141 Fall-through edges must be changed into jumps; it is not safe or
2142 legal to fall through across a section boundary. Whenever a
2143 fall-through edge crossing a section boundary is encountered, a new
2144 basic block is inserted (in the same section as the fall-through
2145 source), and the fall through edge is redirected to the new basic
2146 block. The new basic block contains an unconditional jump to the
2147 original fall-through target. (If the unconditional jump is
2148 insufficient to cross section boundaries, that is dealt with a
2149 little later, see below).
2151 In order to deal with architectures that have short conditional
2152 branches (which cannot span all of memory) we take any conditional
2153 jump that attempts to cross a section boundary and add a level of
2154 indirection: it becomes a conditional jump to a new basic block, in
2155 the same section. The new basic block contains an unconditional
2156 jump to the original target, in the other section.
2158 For those architectures whose unconditional branch is also
2159 incapable of reaching all of memory, those unconditional jumps are
2160 converted into indirect jumps, through a register.
2162 IMPORTANT NOTE: This optimization causes some messy interactions
2163 with the cfg cleanup optimizations; those optimizations want to
2164 merge blocks wherever possible, and to collapse indirect jump
2165 sequences (change "A jumps to B jumps to C" directly into "A jumps
2166 to C"). Those optimizations can undo the jump fixes that
2167 partitioning is required to make (see above), in order to ensure
2168 that jumps attempting to cross section boundaries are really able
2169 to cover whatever distance the jump requires (on many architectures
2170 conditional or unconditional jumps are not able to reach all of
2171 memory). Therefore tests have to be inserted into each such
2172 optimization to make sure that it does not undo stuff necessary to
2173 cross partition boundaries. This would be much less of a problem
2174 if we could perform this optimization later in the compilation, but
2175 unfortunately the fact that we may need to create indirect jumps
2176 (through registers) requires that this optimization be performed
2177 before register allocation. */
2180 partition_hot_cold_basic_blocks (void)
2183 edge *crossing_edges;
2184 int n_crossing_edges;
2185 int max_edges = 2 * last_basic_block;
2187 if (n_basic_blocks <= 1)
2190 crossing_edges = xcalloc (max_edges, sizeof (edge));
2192 cfg_layout_initialize (0);
2194 FOR_EACH_BB (cur_bb)
2195 if (cur_bb->index >= 0
2196 && cur_bb->next_bb->index >= 0)
2197 cur_bb->rbi->next = cur_bb->next_bb;
2199 find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges,
2203 if (n_crossing_edges > 0)
2204 fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges);
2206 free (crossing_edges);
2208 cfg_layout_finalize();