1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2002, 2003, 2004 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"
73 #include "basic-block.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. */
141 do { if (P) { free (P); P = 0; } else { abort (); } } while (0)
143 /* Structure for holding information about a trace. */
146 /* First and last basic block of the trace. */
147 basic_block first, last;
149 /* The round of the STC creation which this trace was found in. */
152 /* The length (i.e. the number of basic blocks) of the trace. */
156 /* Maximum frequency and count of one of the entry blocks. */
157 int max_entry_frequency;
158 gcov_type max_entry_count;
160 /* Local function prototypes. */
161 static void find_traces (int *, struct trace *);
162 static basic_block rotate_loop (edge, struct trace *, int);
163 static void mark_bb_visited (basic_block, int);
164 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
165 int, fibheap_t *, int);
166 static basic_block copy_bb (basic_block, edge, basic_block, int);
167 static fibheapkey_t bb_to_key (basic_block);
168 static bool better_edge_p (basic_block, edge, int, int, int, int, edge);
169 static void connect_traces (int, struct trace *);
170 static bool copy_bb_p (basic_block, int);
171 static int get_uncond_jump_length (void);
172 static bool push_to_next_round_p (basic_block, int, int, int, gcov_type);
173 static void add_unlikely_executed_notes (void);
174 static void find_rarely_executed_basic_blocks_and_crossing_edges (edge *,
177 static void mark_bb_for_unlikely_executed_section (basic_block);
178 static void add_labels_and_missing_jumps (edge *, int);
179 static void add_reg_crossing_jump_notes (void);
180 static void fix_up_fall_thru_edges (void);
181 static void fix_edges_for_rarely_executed_code (edge *, int);
182 static void fix_crossing_conditional_branches (void);
183 static void fix_crossing_unconditional_branches (void);
185 /* Check to see if bb should be pushed into the next round of trace
186 collections or not. Reasons for pushing the block forward are 1).
187 If the block is cold, we are doing partitioning, and there will be
188 another round (cold partition blocks are not supposed to be
189 collected into traces until the very last round); or 2). There will
190 be another round, and the basic block is not "hot enough" for the
191 current round of trace collection. */
194 push_to_next_round_p (basic_block bb, int round, int number_of_rounds,
195 int exec_th, gcov_type count_th)
197 bool there_exists_another_round;
199 bool block_not_hot_enough;
201 there_exists_another_round = round < number_of_rounds - 1;
203 cold_block = (flag_reorder_blocks_and_partition
204 && bb->partition == COLD_PARTITION);
206 block_not_hot_enough = (bb->frequency < exec_th
207 || bb->count < count_th
208 || probably_never_executed_bb_p (bb));
210 if (there_exists_another_round
211 && (cold_block || block_not_hot_enough))
217 /* Find the traces for Software Trace Cache. Chain each trace through
218 RBI()->next. Store the number of traces to N_TRACES and description of
222 find_traces (int *n_traces, struct trace *traces)
225 int number_of_rounds;
229 /* Add one extra round of trace collection when partitioning hot/cold
230 basic blocks into separate sections. The last round is for all the
231 cold blocks (and ONLY the cold blocks). */
233 number_of_rounds = N_ROUNDS - 1;
234 if (flag_reorder_blocks_and_partition)
235 number_of_rounds = N_ROUNDS;
237 /* Insert entry points of function into heap. */
238 heap = fibheap_new ();
239 max_entry_frequency = 0;
241 for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
243 bbd[e->dest->index].heap = heap;
244 bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
246 if (e->dest->frequency > max_entry_frequency)
247 max_entry_frequency = e->dest->frequency;
248 if (e->dest->count > max_entry_count)
249 max_entry_count = e->dest->count;
252 /* Find the traces. */
253 for (i = 0; i < number_of_rounds; i++)
255 gcov_type count_threshold;
258 fprintf (dump_file, "STC - round %d\n", i + 1);
260 if (max_entry_count < INT_MAX / 1000)
261 count_threshold = max_entry_count * exec_threshold[i] / 1000;
263 count_threshold = max_entry_count / 1000 * exec_threshold[i];
265 find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
266 max_entry_frequency * exec_threshold[i] / 1000,
267 count_threshold, traces, n_traces, i, &heap,
270 fibheap_delete (heap);
274 for (i = 0; i < *n_traces; i++)
277 fprintf (dump_file, "Trace %d (round %d): ", i + 1,
278 traces[i].round + 1);
279 for (bb = traces[i].first; bb != traces[i].last; bb = bb->rbi->next)
280 fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
281 fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
287 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
288 (with sequential number TRACE_N). */
291 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
295 /* Information about the best end (end after rotation) of the loop. */
296 basic_block best_bb = NULL;
297 edge best_edge = NULL;
299 gcov_type best_count = -1;
300 /* The best edge is preferred when its destination is not visited yet
301 or is a start block of some trace. */
302 bool is_preferred = false;
304 /* Find the most frequent edge that goes out from current trace. */
305 bb = back_edge->dest;
309 for (e = bb->succ; e; e = e->succ_next)
310 if (e->dest != EXIT_BLOCK_PTR
311 && e->dest->rbi->visited != trace_n
312 && (e->flags & EDGE_CAN_FALLTHRU)
313 && !(e->flags & EDGE_COMPLEX))
317 /* The best edge is preferred. */
318 if (!e->dest->rbi->visited
319 || bbd[e->dest->index].start_of_trace >= 0)
321 /* The current edge E is also preferred. */
322 int freq = EDGE_FREQUENCY (e);
323 if (freq > best_freq || e->count > best_count)
326 best_count = e->count;
334 if (!e->dest->rbi->visited
335 || bbd[e->dest->index].start_of_trace >= 0)
337 /* The current edge E is preferred. */
339 best_freq = EDGE_FREQUENCY (e);
340 best_count = e->count;
346 int freq = EDGE_FREQUENCY (e);
347 if (!best_edge || freq > best_freq || e->count > best_count)
350 best_count = e->count;
359 while (bb != back_edge->dest);
363 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
365 if (back_edge->dest == trace->first)
367 trace->first = best_bb->rbi->next;
373 for (prev_bb = trace->first;
374 prev_bb->rbi->next != back_edge->dest;
375 prev_bb = prev_bb->rbi->next)
377 prev_bb->rbi->next = best_bb->rbi->next;
379 /* Try to get rid of uncond jump to cond jump. */
380 if (prev_bb->succ && !prev_bb->succ->succ_next)
382 basic_block header = prev_bb->succ->dest;
384 /* Duplicate HEADER if it is a small block containing cond jump
386 if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0))
388 copy_bb (header, prev_bb->succ, prev_bb, trace_n);
395 /* We have not found suitable loop tail so do no rotation. */
396 best_bb = back_edge->src;
398 best_bb->rbi->next = NULL;
402 /* This function marks BB that it was visited in trace number TRACE. */
405 mark_bb_visited (basic_block bb, int trace)
407 bb->rbi->visited = trace;
408 if (bbd[bb->index].heap)
410 fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
411 bbd[bb->index].heap = NULL;
412 bbd[bb->index].node = NULL;
416 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
417 not include basic blocks their probability is lower than BRANCH_TH or their
418 frequency is lower than EXEC_TH into traces (or count is lower than
419 COUNT_TH). It stores the new traces into TRACES and modifies the number of
420 traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
421 expects that starting basic blocks are in *HEAP and at the end it deletes
422 *HEAP and stores starting points for the next round into new *HEAP. */
425 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
426 struct trace *traces, int *n_traces, int round,
427 fibheap_t *heap, int number_of_rounds)
429 /* The following variable refers to the last round in which non-"cold"
430 blocks may be collected into a trace. */
432 int last_round = N_ROUNDS - 1;
434 /* Heap for discarded basic blocks which are possible starting points for
436 fibheap_t new_heap = fibheap_new ();
438 while (!fibheap_empty (*heap))
445 bb = fibheap_extract_min (*heap);
446 bbd[bb->index].heap = NULL;
447 bbd[bb->index].node = NULL;
450 fprintf (dump_file, "Getting bb %d\n", bb->index);
452 /* If the BB's frequency is too low send BB to the next round. When
453 partitioning hot/cold blocks into separate sections, make sure all
454 the cold blocks (and ONLY the cold blocks) go into the (extra) final
457 if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
460 int key = bb_to_key (bb);
461 bbd[bb->index].heap = new_heap;
462 bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
466 " Possible start point of next round: %d (key: %d)\n",
471 trace = traces + *n_traces;
473 trace->round = round;
481 /* The probability and frequency of the best edge. */
482 int best_prob = INT_MIN / 2;
483 int best_freq = INT_MIN / 2;
486 mark_bb_visited (bb, *n_traces);
490 fprintf (dump_file, "Basic block %d was visited in trace %d\n",
491 bb->index, *n_traces - 1);
493 /* Select the successor that will be placed after BB. */
494 for (e = bb->succ; e; e = e->succ_next)
496 #ifdef ENABLE_CHECKING
497 if (e->flags & EDGE_FAKE)
501 if (e->dest == EXIT_BLOCK_PTR)
504 if (e->dest->rbi->visited
505 && e->dest->rbi->visited != *n_traces)
508 if (e->dest->partition == COLD_PARTITION
509 && round < last_round)
512 prob = e->probability;
513 freq = EDGE_FREQUENCY (e);
515 /* Edge that cannot be fallthru or improbable or infrequent
516 successor (ie. it is unsuitable successor). */
517 if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
518 || prob < branch_th || freq < exec_th || e->count < count_th)
521 /* If partitioning hot/cold basic blocks, don't consider edges
522 that cross section boundaries. */
524 if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
533 /* If the best destination has multiple predecessors, and can be
534 duplicated cheaper than a jump, don't allow it to be added
535 to a trace. We'll duplicate it when connecting traces. */
536 if (best_edge && best_edge->dest->pred->pred_next
537 && copy_bb_p (best_edge->dest, 0))
540 /* Add all non-selected successors to the heaps. */
541 for (e = bb->succ; e; e = e->succ_next)
544 || e->dest == EXIT_BLOCK_PTR
545 || e->dest->rbi->visited)
548 key = bb_to_key (e->dest);
550 if (bbd[e->dest->index].heap)
552 /* E->DEST is already in some heap. */
553 if (key != bbd[e->dest->index].node->key)
558 "Changing key for bb %d from %ld to %ld.\n",
560 (long) bbd[e->dest->index].node->key,
563 fibheap_replace_key (bbd[e->dest->index].heap,
564 bbd[e->dest->index].node, key);
569 fibheap_t which_heap = *heap;
571 prob = e->probability;
572 freq = EDGE_FREQUENCY (e);
574 if (!(e->flags & EDGE_CAN_FALLTHRU)
575 || (e->flags & EDGE_COMPLEX)
576 || prob < branch_th || freq < exec_th
577 || e->count < count_th)
579 /* When partitioning hot/cold basic blocks, make sure
580 the cold blocks (and only the cold blocks) all get
581 pushed to the last round of trace collection. */
583 if (push_to_next_round_p (e->dest, round,
586 which_heap = new_heap;
589 bbd[e->dest->index].heap = which_heap;
590 bbd[e->dest->index].node = fibheap_insert (which_heap,
596 " Possible start of %s round: %d (key: %ld)\n",
597 (which_heap == new_heap) ? "next" : "this",
598 e->dest->index, (long) key);
604 if (best_edge) /* Suitable successor was found. */
606 if (best_edge->dest->rbi->visited == *n_traces)
608 /* We do nothing with one basic block loops. */
609 if (best_edge->dest != bb)
611 if (EDGE_FREQUENCY (best_edge)
612 > 4 * best_edge->dest->frequency / 5)
614 /* The loop has at least 4 iterations. If the loop
615 header is not the first block of the function
616 we can rotate the loop. */
618 if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
623 "Rotating loop %d - %d\n",
624 best_edge->dest->index, bb->index);
626 bb->rbi->next = best_edge->dest;
627 bb = rotate_loop (best_edge, trace, *n_traces);
632 /* The loop has less than 4 iterations. */
634 /* Check whether there is another edge from BB. */
636 for (another_edge = bb->succ;
638 another_edge = another_edge->succ_next)
639 if (another_edge != best_edge)
642 if (!another_edge && copy_bb_p (best_edge->dest,
645 bb = copy_bb (best_edge->dest, best_edge, bb,
651 /* Terminate the trace. */
656 /* Check for a situation
665 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
666 >= EDGE_FREQUENCY (AC).
667 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
668 Best ordering is then A B C.
670 This situation is created for example by:
677 for (e = bb->succ; e; e = e->succ_next)
679 && (e->flags & EDGE_CAN_FALLTHRU)
680 && !(e->flags & EDGE_COMPLEX)
681 && !e->dest->rbi->visited
682 && !e->dest->pred->pred_next
685 && (e->dest->succ->flags & EDGE_CAN_FALLTHRU)
686 && !(e->dest->succ->flags & EDGE_COMPLEX)
687 && !e->dest->succ->succ_next
688 && e->dest->succ->dest == best_edge->dest
689 && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
693 fprintf (dump_file, "Selecting BB %d\n",
694 best_edge->dest->index);
698 bb->rbi->next = best_edge->dest;
699 bb = best_edge->dest;
705 bbd[trace->first->index].start_of_trace = *n_traces - 1;
706 bbd[trace->last->index].end_of_trace = *n_traces - 1;
708 /* The trace is terminated so we have to recount the keys in heap
709 (some block can have a lower key because now one of its predecessors
710 is an end of the trace). */
711 for (e = bb->succ; e; e = e->succ_next)
713 if (e->dest == EXIT_BLOCK_PTR
714 || e->dest->rbi->visited)
717 if (bbd[e->dest->index].heap)
719 key = bb_to_key (e->dest);
720 if (key != bbd[e->dest->index].node->key)
725 "Changing key for bb %d from %ld to %ld.\n",
727 (long) bbd[e->dest->index].node->key, key);
729 fibheap_replace_key (bbd[e->dest->index].heap,
730 bbd[e->dest->index].node,
737 fibheap_delete (*heap);
739 /* "Return" the new heap. */
743 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
744 it to trace after BB, mark OLD_BB visited and update pass' data structures
745 (TRACE is a number of trace which OLD_BB is duplicated to). */
748 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
752 new_bb = cfg_layout_duplicate_bb (old_bb, e);
753 if (e->dest != new_bb)
755 if (e->dest->rbi->visited)
759 "Duplicated bb %d (created bb %d)\n",
760 old_bb->index, new_bb->index);
761 new_bb->rbi->visited = trace;
762 new_bb->rbi->next = bb->rbi->next;
763 bb->rbi->next = new_bb;
765 if (new_bb->index >= array_size || last_basic_block > array_size)
770 new_size = MAX (last_basic_block, new_bb->index + 1);
771 new_size = GET_ARRAY_SIZE (new_size);
772 bbd = xrealloc (bbd, new_size * sizeof (bbro_basic_block_data));
773 for (i = array_size; i < new_size; i++)
775 bbd[i].start_of_trace = -1;
776 bbd[i].end_of_trace = -1;
780 array_size = new_size;
785 "Growing the dynamic array to %d elements.\n",
793 /* Compute and return the key (for the heap) of the basic block BB. */
796 bb_to_key (basic_block bb)
802 /* Do not start in probably never executed blocks. */
804 if (bb->partition == COLD_PARTITION || probably_never_executed_bb_p (bb))
807 /* Prefer blocks whose predecessor is an end of some trace
808 or whose predecessor edge is EDGE_DFS_BACK. */
809 for (e = bb->pred; e; e = e->pred_next)
811 if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
812 || (e->flags & EDGE_DFS_BACK))
814 int edge_freq = EDGE_FREQUENCY (e);
816 if (edge_freq > priority)
817 priority = edge_freq;
822 /* The block with priority should have significantly lower key. */
823 return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
824 return -bb->frequency;
827 /* Return true when the edge E from basic block BB is better than the temporary
828 best edge (details are in function). The probability of edge E is PROB. The
829 frequency of the successor is FREQ. The current best probability is
830 BEST_PROB, the best frequency is BEST_FREQ.
831 The edge is considered to be equivalent when PROB does not differ much from
832 BEST_PROB; similarly for frequency. */
835 better_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob,
836 int best_freq, edge cur_best_edge)
840 /* The BEST_* values do not have to be best, but can be a bit smaller than
842 int diff_prob = best_prob / 10;
843 int diff_freq = best_freq / 10;
845 if (prob > best_prob + diff_prob)
846 /* The edge has higher probability than the temporary best edge. */
847 is_better_edge = true;
848 else if (prob < best_prob - diff_prob)
849 /* The edge has lower probability than the temporary best edge. */
850 is_better_edge = false;
851 else if (freq < best_freq - diff_freq)
852 /* The edge and the temporary best edge have almost equivalent
853 probabilities. The higher frequency of a successor now means
854 that there is another edge going into that successor.
855 This successor has lower frequency so it is better. */
856 is_better_edge = true;
857 else if (freq > best_freq + diff_freq)
858 /* This successor has higher frequency so it is worse. */
859 is_better_edge = false;
860 else if (e->dest->prev_bb == bb)
861 /* The edges have equivalent probabilities and the successors
862 have equivalent frequencies. Select the previous successor. */
863 is_better_edge = true;
865 is_better_edge = false;
867 /* If we are doing hot/cold partitioning, make sure that we always favor
868 non-crossing edges over crossing edges. */
871 && flag_reorder_blocks_and_partition
873 && cur_best_edge->crossing_edge
874 && !e->crossing_edge)
875 is_better_edge = true;
877 return is_better_edge;
880 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
883 connect_traces (int n_traces, struct trace *traces)
886 int unconnected_hot_trace_count = 0;
887 bool cold_connected = true;
892 gcov_type count_threshold;
894 freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
895 if (max_entry_count < INT_MAX / 1000)
896 count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
898 count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
900 connected = xcalloc (n_traces, sizeof (bool));
903 /* If we are partitioning hot/cold basic blocks, mark the cold
904 traces as already connnected, to remove them from consideration
905 for connection to the hot traces. After the hot traces have all
906 been connected (determined by "unconnected_hot_trace_count"), we
907 will go back and connect the cold traces. */
909 cold_traces = xcalloc (n_traces, sizeof (bool));
911 if (flag_reorder_blocks_and_partition)
912 for (i = 0; i < n_traces; i++)
914 if (traces[i].first->partition == COLD_PARTITION)
917 cold_traces[i] = true;
918 cold_connected = false;
921 unconnected_hot_trace_count++;
924 for (i = 0; i < n_traces || !cold_connected ; i++)
931 /* If we are partitioning hot/cold basic blocks, check to see
932 if all the hot traces have been connected. If so, go back
933 and mark the cold traces as unconnected so we can connect
934 them up too. Re-set "i" to the first (unconnected) cold
935 trace. Use flag "cold_connected" to make sure we don't do
936 this step more than once. */
938 if (flag_reorder_blocks_and_partition
939 && (i >= n_traces || unconnected_hot_trace_count <= 0)
943 int first_cold_trace = -1;
945 for (j = 0; j < n_traces; j++)
948 connected[j] = false;
949 if (first_cold_trace == -1)
950 first_cold_trace = j;
952 i = t = first_cold_trace;
953 cold_connected = true;
960 if (unconnected_hot_trace_count > 0)
961 unconnected_hot_trace_count--;
963 /* Find the predecessor traces. */
964 for (t2 = t; t2 > 0;)
968 for (e = traces[t2].first->pred; e; e = e->pred_next)
970 int si = e->src->index;
972 if (e->src != ENTRY_BLOCK_PTR
973 && (e->flags & EDGE_CAN_FALLTHRU)
974 && !(e->flags & EDGE_COMPLEX)
975 && bbd[si].end_of_trace >= 0
976 && !connected[bbd[si].end_of_trace]
978 || e->probability > best->probability
979 || (e->probability == best->probability
980 && traces[bbd[si].end_of_trace].length > best_len)))
983 best_len = traces[bbd[si].end_of_trace].length;
988 best->src->rbi->next = best->dest;
989 t2 = bbd[best->src->index].end_of_trace;
990 connected[t2] = true;
992 if (unconnected_hot_trace_count > 0)
993 unconnected_hot_trace_count--;
997 fprintf (dump_file, "Connection: %d %d\n",
998 best->src->index, best->dest->index);
1005 if (last_trace >= 0)
1006 traces[last_trace].last->rbi->next = traces[t2].first;
1009 /* Find the successor traces. */
1012 /* Find the continuation of the chain. */
1015 for (e = traces[t].last->succ; e; e = e->succ_next)
1017 int di = e->dest->index;
1019 if (e->dest != EXIT_BLOCK_PTR
1020 && (e->flags & EDGE_CAN_FALLTHRU)
1021 && !(e->flags & EDGE_COMPLEX)
1022 && bbd[di].start_of_trace >= 0
1023 && !connected[bbd[di].start_of_trace]
1025 || e->probability > best->probability
1026 || (e->probability == best->probability
1027 && traces[bbd[di].start_of_trace].length > best_len)))
1030 best_len = traces[bbd[di].start_of_trace].length;
1038 fprintf (dump_file, "Connection: %d %d\n",
1039 best->src->index, best->dest->index);
1041 t = bbd[best->dest->index].start_of_trace;
1042 traces[last_trace].last->rbi->next = traces[t].first;
1043 connected[t] = true;
1044 if (unconnected_hot_trace_count > 0)
1045 unconnected_hot_trace_count--;
1050 /* Try to connect the traces by duplication of 1 block. */
1052 basic_block next_bb = NULL;
1053 bool try_copy = false;
1055 for (e = traces[t].last->succ; e; e = e->succ_next)
1056 if (e->dest != EXIT_BLOCK_PTR
1057 && (e->flags & EDGE_CAN_FALLTHRU)
1058 && !(e->flags & EDGE_COMPLEX)
1059 && (!best || e->probability > best->probability))
1064 /* If the destination is a start of a trace which is only
1065 one block long, then no need to search the successor
1066 blocks of the trace. Accept it. */
1067 if (bbd[e->dest->index].start_of_trace >= 0
1068 && traces[bbd[e->dest->index].start_of_trace].length
1076 for (e2 = e->dest->succ; e2; e2 = e2->succ_next)
1078 int di = e2->dest->index;
1080 if (e2->dest == EXIT_BLOCK_PTR
1081 || ((e2->flags & EDGE_CAN_FALLTHRU)
1082 && !(e2->flags & EDGE_COMPLEX)
1083 && bbd[di].start_of_trace >= 0
1084 && !connected[bbd[di].start_of_trace]
1085 && (EDGE_FREQUENCY (e2) >= freq_threshold)
1086 && (e2->count >= count_threshold)
1088 || e2->probability > best2->probability
1089 || (e2->probability == best2->probability
1090 && traces[bbd[di].start_of_trace].length
1095 if (e2->dest != EXIT_BLOCK_PTR)
1096 best2_len = traces[bbd[di].start_of_trace].length;
1098 best2_len = INT_MAX;
1105 if (flag_reorder_blocks_and_partition)
1108 /* Copy tiny blocks always; copy larger blocks only when the
1109 edge is traversed frequently enough. */
1111 && copy_bb_p (best->dest,
1113 && EDGE_FREQUENCY (best) >= freq_threshold
1114 && best->count >= count_threshold))
1120 fprintf (dump_file, "Connection: %d %d ",
1121 traces[t].last->index, best->dest->index);
1123 fputc ('\n', dump_file);
1124 else if (next_bb == EXIT_BLOCK_PTR)
1125 fprintf (dump_file, "exit\n");
1127 fprintf (dump_file, "%d\n", next_bb->index);
1130 new_bb = copy_bb (best->dest, best, traces[t].last, t);
1131 traces[t].last = new_bb;
1132 if (next_bb && next_bb != EXIT_BLOCK_PTR)
1134 t = bbd[next_bb->index].start_of_trace;
1135 traces[last_trace].last->rbi->next = traces[t].first;
1136 connected[t] = true;
1137 if (unconnected_hot_trace_count > 0)
1138 unconnected_hot_trace_count--;
1142 break; /* Stop finding the successor traces. */
1145 break; /* Stop finding the successor traces. */
1154 fprintf (dump_file, "Final order:\n");
1155 for (bb = traces[0].first; bb; bb = bb->rbi->next)
1156 fprintf (dump_file, "%d ", bb->index);
1157 fprintf (dump_file, "\n");
1164 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1165 when code size is allowed to grow by duplication. */
1168 copy_bb_p (basic_block bb, int code_may_grow)
1171 int max_size = uncond_jump_length;
1178 if (!bb->pred || !bb->pred->pred_next)
1180 if (!cfg_layout_can_duplicate_bb_p (bb))
1183 /* Avoid duplicating blocks which have many successors (PR/13430). */
1185 for (e = bb->succ; e; e = e->succ_next)
1192 if (code_may_grow && maybe_hot_bb_p (bb))
1195 for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
1196 insn = NEXT_INSN (insn))
1199 size += get_attr_length (insn);
1202 if (size <= max_size)
1208 "Block %d can't be copied because its size = %d.\n",
1215 /* Return the length of unconditional jump instruction. */
1218 get_uncond_jump_length (void)
1223 label = emit_label_before (gen_label_rtx (), get_insns ());
1224 jump = emit_jump_insn (gen_jump (label));
1226 length = get_attr_length (jump);
1229 delete_insn (label);
1234 add_unlikely_executed_notes (void)
1239 if (bb->partition == COLD_PARTITION)
1240 mark_bb_for_unlikely_executed_section (bb);
1243 /* Find the basic blocks that are rarely executed and need to be moved to
1244 a separate section of the .o file (to cut down on paging and improve
1248 find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges,
1249 int *n_crossing_edges,
1256 /* Mark which partition (hot/cold) each basic block belongs in. */
1260 if (probably_never_executed_bb_p (bb))
1261 bb->partition = COLD_PARTITION;
1263 bb->partition = HOT_PARTITION;
1266 /* Mark every edge that crosses between sections. */
1270 for (e = bb->succ; e; e = e->succ_next)
1272 if (e->src != ENTRY_BLOCK_PTR
1273 && e->dest != EXIT_BLOCK_PTR
1274 && e->src->partition != e->dest->partition)
1276 e->crossing_edge = true;
1280 crossing_edges = xrealloc (crossing_edges,
1281 (*max_idx) * sizeof (edge));
1283 crossing_edges[i++] = e;
1286 e->crossing_edge = false;
1289 *n_crossing_edges = i;
1292 /* Add NOTE_INSN_UNLIKELY_EXECUTED_CODE to top of basic block. This note
1293 is later used to mark the basic block to be put in the
1294 unlikely-to-be-executed section of the .o file. */
1297 mark_bb_for_unlikely_executed_section (basic_block bb)
1300 rtx insert_insn = NULL;
1303 /* Find first non-note instruction and insert new NOTE before it (as
1304 long as new NOTE is not first instruction in basic block). */
1306 for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb));
1307 cur_insn = NEXT_INSN (cur_insn))
1308 if (GET_CODE (cur_insn) != NOTE
1309 && GET_CODE (cur_insn) != CODE_LABEL)
1311 insert_insn = cur_insn;
1315 /* Insert note and assign basic block number to it. */
1319 new_note = emit_note_before (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
1321 NOTE_BASIC_BLOCK (new_note) = bb;
1325 new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
1327 NOTE_BASIC_BLOCK (new_note) = bb;
1331 /* If any destination of a crossing edge does not have a label, add label;
1332 Convert any fall-through crossing edges (for blocks that do not contain
1333 a jump) to unconditional jumps. */
1336 add_labels_and_missing_jumps (edge *crossing_edges, int n_crossing_edges)
1345 for (i=0; i < n_crossing_edges; i++)
1347 if (crossing_edges[i])
1349 src = crossing_edges[i]->src;
1350 dest = crossing_edges[i]->dest;
1352 /* Make sure dest has a label. */
1354 if (dest && (dest != EXIT_BLOCK_PTR))
1356 label = block_label (dest);
1358 /* Make sure source block ends with a jump. */
1360 if (src && (src != ENTRY_BLOCK_PTR))
1362 if (GET_CODE (BB_END (src)) != JUMP_INSN)
1363 /* bb just falls through. */
1365 /* make sure there's only one successor */
1366 if (src->succ && (src->succ->succ_next == NULL))
1368 /* Find label in dest block. */
1369 label = block_label (dest);
1371 new_jump = emit_jump_insn_after (gen_jump (label),
1373 barrier = emit_barrier_after (new_jump);
1374 JUMP_LABEL (new_jump) = label;
1375 LABEL_NUSES (label) += 1;
1376 src->rbi->footer = unlink_insn_chain (barrier,
1378 /* Mark edge as non-fallthru. */
1379 crossing_edges[i]->flags &= ~EDGE_FALLTHRU;
1383 /* Basic block has two successors, but
1384 doesn't end in a jump; something is wrong
1388 } /* end: 'if (GET_CODE ... ' */
1389 } /* end: 'if (src && src->index...' */
1390 } /* end: 'if (dest && dest->index...' */
1391 } /* end: 'if (crossing_edges[i]...' */
1392 } /* end for loop */
1395 /* Find any bb's where the fall-through edge is a crossing edge (note that
1396 these bb's must also contain a conditional jump; we've already
1397 dealt with fall-through edges for blocks that didn't have a
1398 conditional jump in the call to add_labels_and_missing_jumps).
1399 Convert the fall-through edge to non-crossing edge by inserting a
1400 new bb to fall-through into. The new bb will contain an
1401 unconditional jump (crossing edge) to the original fall through
1405 fix_up_fall_thru_edges (void)
1414 bool cond_jump_crosses;
1417 rtx fall_thru_label;
1420 FOR_EACH_BB (cur_bb)
1423 succ1 = cur_bb->succ;
1425 succ2 = succ1->succ_next;
1429 /* Find the fall-through edge. */
1432 && (succ1->flags & EDGE_FALLTHRU))
1438 && (succ2->flags & EDGE_FALLTHRU))
1444 if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
1446 /* Check to see if the fall-thru edge is a crossing edge. */
1448 if (fall_thru->crossing_edge)
1450 /* The fall_thru edge crosses; now check the cond jump edge, if
1453 cond_jump_crosses = true;
1455 old_jump = BB_END (cur_bb);
1457 /* Find the jump instruction, if there is one. */
1461 if (!cond_jump->crossing_edge)
1462 cond_jump_crosses = false;
1464 /* We know the fall-thru edge crosses; if the cond
1465 jump edge does NOT cross, and its destination is the
1466 next block in the bb order, invert the jump
1467 (i.e. fix it so the fall thru does not cross and
1468 the cond jump does). */
1470 if (!cond_jump_crosses
1471 && cur_bb->rbi->next == cond_jump->dest)
1473 /* Find label in fall_thru block. We've already added
1474 any missing labels, so there must be one. */
1476 fall_thru_label = block_label (fall_thru->dest);
1478 if (old_jump && fall_thru_label)
1479 invert_worked = invert_jump (old_jump,
1483 fall_thru->flags &= ~EDGE_FALLTHRU;
1484 cond_jump->flags |= EDGE_FALLTHRU;
1485 update_br_prob_note (cur_bb);
1487 fall_thru = cond_jump;
1489 cond_jump->crossing_edge = true;
1490 fall_thru->crossing_edge = false;
1495 if (cond_jump_crosses || !invert_worked)
1497 /* This is the case where both edges out of the basic
1498 block are crossing edges. Here we will fix up the
1499 fall through edge. The jump edge will be taken care
1502 new_bb = force_nonfallthru (fall_thru);
1506 new_bb->rbi->next = cur_bb->rbi->next;
1507 cur_bb->rbi->next = new_bb;
1509 /* Make sure new fall-through bb is in same
1510 partition as bb it's falling through from. */
1512 new_bb->partition = cur_bb->partition;
1513 new_bb->succ->crossing_edge = true;
1516 /* Add barrier after new jump */
1520 barrier = emit_barrier_after (BB_END (new_bb));
1521 new_bb->rbi->footer = unlink_insn_chain (barrier,
1526 barrier = emit_barrier_after (BB_END (cur_bb));
1527 cur_bb->rbi->footer = unlink_insn_chain (barrier,
1536 /* This function checks the destination blockof a "crossing jump" to
1537 see if it has any crossing predecessors that begin with a code label
1538 and end with an unconditional jump. If so, it returns that predecessor
1539 block. (This is to avoid creating lots of new basic blocks that all
1540 contain unconditional jumps to the same destination). */
1543 find_jump_block (basic_block jump_dest)
1545 basic_block source_bb = NULL;
1549 for (e = jump_dest->pred; e; e = e->pred_next)
1550 if (e->crossing_edge)
1552 basic_block src = e->src;
1554 /* Check each predecessor to see if it has a label, and contains
1555 only one executable instruction, which is an unconditional jump.
1556 If so, we can use it. */
1558 if (GET_CODE (BB_HEAD (src)) == CODE_LABEL)
1559 for (insn = BB_HEAD (src);
1560 !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
1561 insn = NEXT_INSN (insn))
1564 && insn == BB_END (src)
1565 && GET_CODE (insn) == JUMP_INSN
1566 && !any_condjump_p (insn))
1580 /* Find all BB's with conditional jumps that are crossing edges;
1581 insert a new bb and make the conditional jump branch to the new
1582 bb instead (make the new bb same color so conditional branch won't
1583 be a 'crossing' edge). Insert an unconditional jump from the
1584 new bb to the original destination of the conditional jump. */
1587 fix_crossing_conditional_branches (void)
1591 basic_block last_bb;
1593 basic_block prev_bb;
1600 rtx old_label = NULL_RTX;
1605 last_bb = EXIT_BLOCK_PTR->prev_bb;
1607 FOR_EACH_BB (cur_bb)
1609 crossing_edge = NULL;
1610 succ1 = cur_bb->succ;
1612 succ2 = succ1->succ_next;
1616 /* We already took care of fall-through edges, so only one successor
1617 can be a crossing edge. */
1619 if (succ1 && succ1->crossing_edge)
1620 crossing_edge = succ1;
1621 else if (succ2 && succ2->crossing_edge)
1622 crossing_edge = succ2;
1626 old_jump = BB_END (cur_bb);
1628 /* Check to make sure the jump instruction is a
1629 conditional jump. */
1633 if (any_condjump_p (old_jump))
1635 if (GET_CODE (PATTERN (old_jump)) == SET)
1636 set_src = SET_SRC (PATTERN (old_jump));
1637 else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
1639 set_src = XVECEXP (PATTERN (old_jump), 0,0);
1640 if (GET_CODE (set_src) == SET)
1641 set_src = SET_SRC (set_src);
1647 if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
1649 if (GET_CODE (XEXP (set_src, 1)) == PC)
1650 old_label = XEXP (set_src, 2);
1651 else if (GET_CODE (XEXP (set_src, 2)) == PC)
1652 old_label = XEXP (set_src, 1);
1654 /* Check to see if new bb for jumping to that dest has
1655 already been created; if so, use it; if not, create
1658 new_bb = find_jump_block (crossing_edge->dest);
1661 new_label = block_label (new_bb);
1664 /* Create new basic block to be dest for
1665 conditional jump. */
1667 new_bb = create_basic_block (NULL, NULL, last_bb);
1668 new_bb->rbi->next = last_bb->rbi->next;
1669 last_bb->rbi->next = new_bb;
1673 /* Update register liveness information. */
1675 new_bb->global_live_at_start =
1676 OBSTACK_ALLOC_REG_SET (&flow_obstack);
1677 new_bb->global_live_at_end =
1678 OBSTACK_ALLOC_REG_SET (&flow_obstack);
1679 COPY_REG_SET (new_bb->global_live_at_end,
1680 prev_bb->global_live_at_end);
1681 COPY_REG_SET (new_bb->global_live_at_start,
1682 prev_bb->global_live_at_end);
1684 /* Put appropriate instructions in new bb. */
1686 new_label = gen_label_rtx ();
1687 emit_label_before (new_label, BB_HEAD (new_bb));
1688 BB_HEAD (new_bb) = new_label;
1690 if (GET_CODE (old_label) == LABEL_REF)
1692 old_label = JUMP_LABEL (old_jump);
1693 new_jump = emit_jump_insn_after (gen_jump
1697 else if (HAVE_return
1698 && GET_CODE (old_label) == RETURN)
1699 new_jump = emit_jump_insn_after (gen_return (),
1704 barrier = emit_barrier_after (new_jump);
1705 JUMP_LABEL (new_jump) = old_label;
1706 new_bb->rbi->footer = unlink_insn_chain (barrier,
1709 /* Make sure new bb is in same partition as source
1710 of conditional branch. */
1712 new_bb->partition = cur_bb->partition;
1715 /* Make old jump branch to new bb. */
1717 redirect_jump (old_jump, new_label, 0);
1719 /* Remove crossing_edge as predecessor of 'dest'. */
1721 dest = crossing_edge->dest;
1723 redirect_edge_succ (crossing_edge, new_bb);
1725 /* Make a new edge from new_bb to old dest; new edge
1726 will be a successor for new_bb and a predecessor
1730 new_edge = make_edge (new_bb, dest, 0);
1732 new_edge = new_bb->succ;
1734 crossing_edge->crossing_edge = false;
1735 new_edge->crossing_edge = true;
1741 /* Find any unconditional branches that cross between hot and cold
1742 sections. Convert them into indirect jumps instead. */
1745 fix_crossing_unconditional_branches (void)
1751 rtx indirect_jump_sequence;
1752 rtx jump_insn = NULL_RTX;
1757 FOR_EACH_BB (cur_bb)
1759 last_insn = BB_END (cur_bb);
1760 succ = cur_bb->succ;
1762 /* Check to see if bb ends in a crossing (unconditional) jump. At
1763 this point, no crossing jumps should be conditional. */
1765 if (GET_CODE (last_insn) == JUMP_INSN
1766 && succ->crossing_edge)
1770 if (any_condjump_p (last_insn))
1773 /* Make sure the jump is not already an indirect or table jump. */
1775 else if (!computed_jump_p (last_insn)
1776 && !tablejump_p (last_insn, &label2, &table))
1778 /* We have found a "crossing" unconditional branch. Now
1779 we must convert it to an indirect jump. First create
1780 reference of label, as target for jump. */
1782 label = JUMP_LABEL (last_insn);
1783 label_addr = gen_rtx_LABEL_REF (Pmode, label);
1784 LABEL_NUSES (label) += 1;
1786 /* Get a register to use for the indirect jump. */
1788 new_reg = gen_reg_rtx (Pmode);
1790 /* Generate indirect the jump sequence. */
1793 emit_move_insn (new_reg, label_addr);
1794 emit_indirect_jump (new_reg);
1795 indirect_jump_sequence = get_insns ();
1798 /* Make sure every instruction in the new jump sequence has
1799 its basic block set to be cur_bb. */
1801 for (cur_insn = indirect_jump_sequence; cur_insn;
1802 cur_insn = NEXT_INSN (cur_insn))
1804 BLOCK_FOR_INSN (cur_insn) = cur_bb;
1805 if (GET_CODE (cur_insn) == JUMP_INSN)
1806 jump_insn = cur_insn;
1809 /* Insert the new (indirect) jump sequence immediately before
1810 the unconditional jump, then delete the unconditional jump. */
1812 emit_insn_before (indirect_jump_sequence, last_insn);
1813 delete_insn (last_insn);
1815 /* Make BB_END for cur_bb be the jump instruction (NOT the
1816 barrier instruction at the end of the sequence...). */
1818 BB_END (cur_bb) = jump_insn;
1824 /* Add REG_CROSSING_JUMP note to all crossing jump insns. */
1827 add_reg_crossing_jump_notes (void)
1833 for (e = bb->succ; e; e = e->succ_next)
1834 if (e->crossing_edge
1835 && GET_CODE (BB_END (e->src)) == JUMP_INSN)
1836 REG_NOTES (BB_END (e->src)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
1842 /* Basic blocks containing NOTE_INSN_UNLIKELY_EXECUTED_CODE will be
1843 put in a separate section of the .o file, to reduce paging and
1844 improve cache performance (hopefully). This can result in bits of
1845 code from the same function being widely separated in the .o file.
1846 However this is not obvious to the current bb structure. Therefore
1847 we must take care to ensure that: 1). There are no fall_thru edges
1848 that cross between sections; 2). For those architectures which
1849 have "short" conditional branches, all conditional branches that
1850 attempt to cross between sections are converted to unconditional
1851 branches; and, 3). For those architectures which have "short"
1852 unconditional branches, all unconditional branches that attempt
1853 to cross between sections are converted to indirect jumps.
1855 The code for fixing up fall_thru edges that cross between hot and
1856 cold basic blocks does so by creating new basic blocks containing
1857 unconditional branches to the appropriate label in the "other"
1858 section. The new basic block is then put in the same (hot or cold)
1859 section as the original conditional branch, and the fall_thru edge
1860 is modified to fall into the new basic block instead. By adding
1861 this level of indirection we end up with only unconditional branches
1862 crossing between hot and cold sections.
1864 Conditional branches are dealt with by adding a level of indirection.
1865 A new basic block is added in the same (hot/cold) section as the
1866 conditional branch, and the conditional branch is retargeted to the
1867 new basic block. The new basic block contains an unconditional branch
1868 to the original target of the conditional branch (in the other section).
1870 Unconditional branches are dealt with by converting them into
1874 fix_edges_for_rarely_executed_code (edge *crossing_edges,
1875 int n_crossing_edges)
1877 /* Make sure the source of any crossing edge ends in a jump and the
1878 destination of any crossing edge has a label. */
1880 add_labels_and_missing_jumps (crossing_edges, n_crossing_edges);
1882 /* Convert all crossing fall_thru edges to non-crossing fall
1883 thrus to unconditional jumps (that jump to the original fall
1886 fix_up_fall_thru_edges ();
1888 /* If the architecture does not have conditional branches that can
1889 span all of memory, convert crossing conditional branches into
1890 crossing unconditional branches. */
1892 if (!HAS_LONG_COND_BRANCH)
1893 fix_crossing_conditional_branches ();
1895 /* If the architecture does not have unconditional branches that
1896 can span all of memory, convert crossing unconditional branches
1897 into indirect jumps. Since adding an indirect jump also adds
1898 a new register usage, update the register usage information as
1901 if (!HAS_LONG_UNCOND_BRANCH)
1903 fix_crossing_unconditional_branches ();
1904 reg_scan (get_insns(), max_reg_num (), 1);
1907 add_reg_crossing_jump_notes ();
1910 /* Reorder basic blocks. The main entry point to this file. */
1913 reorder_basic_blocks (void)
1917 struct trace *traces;
1919 if (n_basic_blocks <= 1)
1922 if (targetm.cannot_modify_jumps_p ())
1925 timevar_push (TV_REORDER_BLOCKS);
1927 cfg_layout_initialize ();
1929 set_edge_can_fallthru_flag ();
1930 mark_dfs_back_edges ();
1932 /* We are estimating the length of uncond jump insn only once since the code
1933 for getting the insn length always returns the minimal length now. */
1934 if (uncond_jump_length == 0)
1935 uncond_jump_length = get_uncond_jump_length ();
1937 /* We need to know some information for each basic block. */
1938 array_size = GET_ARRAY_SIZE (last_basic_block);
1939 bbd = xmalloc (array_size * sizeof (bbro_basic_block_data));
1940 for (i = 0; i < array_size; i++)
1942 bbd[i].start_of_trace = -1;
1943 bbd[i].end_of_trace = -1;
1948 traces = xmalloc (n_basic_blocks * sizeof (struct trace));
1950 find_traces (&n_traces, traces);
1951 connect_traces (n_traces, traces);
1956 dump_flow_info (dump_file);
1958 if (flag_reorder_blocks_and_partition)
1959 add_unlikely_executed_notes ();
1961 cfg_layout_finalize ();
1963 timevar_pop (TV_REORDER_BLOCKS);
1966 /* This function is the main 'entrance' for the optimization that
1967 partitions hot and cold basic blocks into separate sections of the
1968 .o file (to improve performance and cache locality). Ideally it
1969 would be called after all optimizations that rearrange the CFG have
1970 been called. However part of this optimization may introduce new
1971 register usage, so it must be called before register allocation has
1972 occurred. This means that this optimization is actually called
1973 well before the optimization that reorders basic blocks (see function
1976 This optimization checks the feedback information to determine
1977 which basic blocks are hot/cold and adds
1978 NOTE_INSN_UNLIKELY_EXECUTED_CODE to non-hot basic blocks. The
1979 presence or absence of this note is later used for writing out
1980 sections in the .o file. This optimization must also modify the
1981 CFG to make sure there are no fallthru edges between hot & cold
1982 blocks, as those blocks will not necessarily be contiguous in the
1983 .o (or assembly) file; and in those cases where the architecture
1984 requires it, conditional and unconditional branches that cross
1985 between sections are converted into unconditional or indirect
1986 jumps, depending on what is appropriate. */
1989 partition_hot_cold_basic_blocks (void)
1992 edge *crossing_edges;
1993 int n_crossing_edges;
1994 int max_edges = 2 * last_basic_block;
1996 if (n_basic_blocks <= 1)
1999 crossing_edges = xcalloc (max_edges, sizeof (edge));
2001 cfg_layout_initialize ();
2003 FOR_EACH_BB (cur_bb)
2004 if (cur_bb->index >= 0
2005 && cur_bb->next_bb->index >= 0)
2006 cur_bb->rbi->next = cur_bb->next_bb;
2008 find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges,
2012 if (n_crossing_edges > 0)
2013 fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges);
2015 free (crossing_edges);
2017 cfg_layout_finalize();