1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This (greedy) algorithm constructs traces in several rounds.
21 The construction starts from "seeds". The seed for the first round
22 is the entry point of function. When there are more than one seed
23 that one is selected first that has the lowest key in the heap
24 (see function bb_to_key). Then the algorithm repeatedly adds the most
25 probable successor to the end of a trace. Finally it connects the traces.
27 There are two parameters: Branch Threshold and Exec Threshold.
28 If the edge to a successor of the actual basic block is lower than
29 Branch Threshold or the frequency of the successor is lower than
30 Exec Threshold the successor will be the seed in one of the next rounds.
31 Each round has these parameters lower than the previous one.
32 The last round has to have these parameters set to zero
33 so that the remaining blocks are picked up.
35 The algorithm selects the most probable successor from all unvisited
36 successors and successors that have been added to this trace.
37 The other successors (that has not been "sent" to the next round) will be
38 other seeds for this round and the secondary traces will start in them.
39 If the successor has not been visited in this trace it is added to the trace
40 (however, there is some heuristic for simple branches).
41 If the successor has been visited in this trace the loop has been found.
42 If the loop has many iterations the loop is rotated so that the
43 source block of the most probable edge going out from the loop
44 is the last block of the trace.
45 If the loop has few iterations and there is no edge from the last block of
46 the loop going out from loop the loop header is duplicated.
47 Finally, the construction of the trace is terminated.
49 When connecting traces it first checks whether there is an edge from the
50 last block of one trace to the first block of another trace.
51 When there are still some unconnected traces it checks whether there exists
52 a basic block BB such that BB is a successor of the last bb of one trace
53 and BB is a predecessor of the first block of another trace. In this case,
54 BB is duplicated and the traces are connected through this duplicate.
55 The rest of traces are simply connected so there will be a jump to the
56 beginning of the rest of trace.
61 "Software Trace Cache"
62 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
63 http://citeseer.nj.nec.com/15361.html
69 #include "coretypes.h"
76 #include "cfglayout.h"
85 #include "tree-pass.h"
87 #ifndef HAVE_conditional_execution
88 #define HAVE_conditional_execution 0
91 /* The number of rounds. In most cases there will only be 4 rounds, but
92 when partitioning hot and cold basic blocks into separate sections of
93 the .o file there will be an extra round.*/
96 /* Stubs in case we don't have a return insn.
97 We have to check at runtime too, not only compiletime. */
100 #define HAVE_return 0
101 #define gen_return() NULL_RTX
105 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
106 static int branch_threshold
[N_ROUNDS
] = {400, 200, 100, 0, 0};
108 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
109 static int exec_threshold
[N_ROUNDS
] = {500, 200, 50, 0, 0};
111 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
112 block the edge destination is not duplicated while connecting traces. */
113 #define DUPLICATION_THRESHOLD 100
115 /* Length of unconditional jump instruction. */
116 static int uncond_jump_length
;
118 /* Structure to hold needed information for each basic block. */
119 typedef struct bbro_basic_block_data_def
121 /* Which trace is the bb start of (-1 means it is not a start of a trace). */
124 /* Which trace is the bb end of (-1 means it is not an end of a trace). */
127 /* Which trace is the bb in? */
130 /* Which heap is BB in (if any)? */
133 /* Which heap node is BB in (if any)? */
135 } bbro_basic_block_data
;
137 /* The current size of the following dynamic array. */
138 static int array_size
;
140 /* The array which holds needed information for basic blocks. */
141 static bbro_basic_block_data
*bbd
;
143 /* To avoid frequent reallocation the size of arrays is greater than needed,
144 the number of elements is (not less than) 1.25 * size_wanted. */
145 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
147 /* Free the memory and set the pointer to NULL. */
148 #define FREE(P) (gcc_assert (P), free (P), P = 0)
150 /* Structure for holding information about a trace. */
153 /* First and last basic block of the trace. */
154 basic_block first
, last
;
156 /* The round of the STC creation which this trace was found in. */
159 /* The length (i.e. the number of basic blocks) of the trace. */
163 /* Maximum frequency and count of one of the entry blocks. */
164 static int max_entry_frequency
;
165 static gcov_type max_entry_count
;
167 /* Local function prototypes. */
168 static void find_traces (int *, struct trace
*);
169 static basic_block
rotate_loop (edge
, struct trace
*, int);
170 static void mark_bb_visited (basic_block
, int);
171 static void find_traces_1_round (int, int, gcov_type
, struct trace
*, int *,
172 int, fibheap_t
*, int);
173 static basic_block
copy_bb (basic_block
, edge
, basic_block
, int);
174 static fibheapkey_t
bb_to_key (basic_block
);
175 static bool better_edge_p (basic_block
, edge
, int, int, int, int, edge
);
176 static void connect_traces (int, struct trace
*);
177 static bool copy_bb_p (basic_block
, int);
178 static int get_uncond_jump_length (void);
179 static bool push_to_next_round_p (basic_block
, int, int, int, gcov_type
);
180 static void find_rarely_executed_basic_blocks_and_crossing_edges (edge
*,
183 static void add_labels_and_missing_jumps (edge
*, int);
184 static void add_reg_crossing_jump_notes (void);
185 static void fix_up_fall_thru_edges (void);
186 static void fix_edges_for_rarely_executed_code (edge
*, int);
187 static void fix_crossing_conditional_branches (void);
188 static void fix_crossing_unconditional_branches (void);
190 /* Check to see if bb should be pushed into the next round of trace
191 collections or not. Reasons for pushing the block forward are 1).
192 If the block is cold, we are doing partitioning, and there will be
193 another round (cold partition blocks are not supposed to be
194 collected into traces until the very last round); or 2). There will
195 be another round, and the basic block is not "hot enough" for the
196 current round of trace collection. */
199 push_to_next_round_p (basic_block bb
, int round
, int number_of_rounds
,
200 int exec_th
, gcov_type count_th
)
202 bool there_exists_another_round
;
203 bool block_not_hot_enough
;
205 there_exists_another_round
= round
< number_of_rounds
- 1;
207 block_not_hot_enough
= (bb
->frequency
< exec_th
208 || bb
->count
< count_th
209 || probably_never_executed_bb_p (bb
));
211 if (there_exists_another_round
212 && block_not_hot_enough
)
218 /* Find the traces for Software Trace Cache. Chain each trace through
219 RBI()->next. Store the number of traces to N_TRACES and description of
223 find_traces (int *n_traces
, struct trace
*traces
)
226 int number_of_rounds
;
231 /* Add one extra round of trace collection when partitioning hot/cold
232 basic blocks into separate sections. The last round is for all the
233 cold blocks (and ONLY the cold blocks). */
235 number_of_rounds
= N_ROUNDS
- 1;
237 /* Insert entry points of function into heap. */
238 heap
= fibheap_new ();
239 max_entry_frequency
= 0;
241 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
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
->aux
)
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
;
311 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
312 if (e
->dest
!= EXIT_BLOCK_PTR
313 && e
->dest
->il
.rtl
->visited
!= trace_n
314 && (e
->flags
& EDGE_CAN_FALLTHRU
)
315 && !(e
->flags
& EDGE_COMPLEX
))
319 /* The best edge is preferred. */
320 if (!e
->dest
->il
.rtl
->visited
321 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
323 /* The current edge E is also preferred. */
324 int freq
= EDGE_FREQUENCY (e
);
325 if (freq
> best_freq
|| e
->count
> best_count
)
328 best_count
= e
->count
;
336 if (!e
->dest
->il
.rtl
->visited
337 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
339 /* The current edge E is preferred. */
341 best_freq
= EDGE_FREQUENCY (e
);
342 best_count
= e
->count
;
348 int freq
= EDGE_FREQUENCY (e
);
349 if (!best_edge
|| freq
> best_freq
|| e
->count
> best_count
)
352 best_count
= e
->count
;
361 while (bb
!= back_edge
->dest
);
365 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
367 if (back_edge
->dest
== trace
->first
)
369 trace
->first
= best_bb
->aux
;
375 for (prev_bb
= trace
->first
;
376 prev_bb
->aux
!= back_edge
->dest
;
377 prev_bb
= prev_bb
->aux
)
379 prev_bb
->aux
= best_bb
->aux
;
381 /* Try to get rid of uncond jump to cond jump. */
382 if (single_succ_p (prev_bb
))
384 basic_block header
= single_succ (prev_bb
);
386 /* Duplicate HEADER if it is a small block containing cond jump
388 if (any_condjump_p (BB_END (header
)) && copy_bb_p (header
, 0)
389 && !find_reg_note (BB_END (header
), REG_CROSSING_JUMP
,
391 copy_bb (header
, single_succ_edge (prev_bb
), prev_bb
, trace_n
);
397 /* We have not found suitable loop tail so do no rotation. */
398 best_bb
= back_edge
->src
;
404 /* This function marks BB that it was visited in trace number TRACE. */
407 mark_bb_visited (basic_block bb
, int trace
)
409 bb
->il
.rtl
->visited
= trace
;
410 if (bbd
[bb
->index
].heap
)
412 fibheap_delete_node (bbd
[bb
->index
].heap
, bbd
[bb
->index
].node
);
413 bbd
[bb
->index
].heap
= NULL
;
414 bbd
[bb
->index
].node
= NULL
;
418 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
419 not include basic blocks their probability is lower than BRANCH_TH or their
420 frequency is lower than EXEC_TH into traces (or count is lower than
421 COUNT_TH). It stores the new traces into TRACES and modifies the number of
422 traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
423 expects that starting basic blocks are in *HEAP and at the end it deletes
424 *HEAP and stores starting points for the next round into new *HEAP. */
427 find_traces_1_round (int branch_th
, int exec_th
, gcov_type count_th
,
428 struct trace
*traces
, int *n_traces
, int round
,
429 fibheap_t
*heap
, int number_of_rounds
)
431 /* Heap for discarded basic blocks which are possible starting points for
433 fibheap_t new_heap
= fibheap_new ();
435 while (!fibheap_empty (*heap
))
443 bb
= fibheap_extract_min (*heap
);
444 bbd
[bb
->index
].heap
= NULL
;
445 bbd
[bb
->index
].node
= NULL
;
448 fprintf (dump_file
, "Getting bb %d\n", bb
->index
);
450 /* If the BB's frequency is too low send BB to the next round. When
451 partitioning hot/cold blocks into separate sections, make sure all
452 the cold blocks (and ONLY the cold blocks) go into the (extra) final
455 if (push_to_next_round_p (bb
, round
, number_of_rounds
, exec_th
,
458 int key
= bb_to_key (bb
);
459 bbd
[bb
->index
].heap
= new_heap
;
460 bbd
[bb
->index
].node
= fibheap_insert (new_heap
, key
, bb
);
464 " Possible start point of next round: %d (key: %d)\n",
469 trace
= traces
+ *n_traces
;
471 trace
->round
= round
;
473 bbd
[bb
->index
].in_trace
= *n_traces
;
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 ends_in_call
= block_ends_with_call_p (bb
);
495 /* Select the successor that will be placed after BB. */
496 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
498 gcc_assert (!(e
->flags
& EDGE_FAKE
));
500 if (e
->dest
== EXIT_BLOCK_PTR
)
503 if (e
->dest
->il
.rtl
->visited
504 && e
->dest
->il
.rtl
->visited
!= *n_traces
)
507 if (BB_PARTITION (e
->dest
) != BB_PARTITION (bb
))
510 prob
= e
->probability
;
511 freq
= e
->dest
->frequency
;
513 /* The only sensible preference for a call instruction is the
514 fallthru edge. Don't bother selecting anything else. */
517 if (e
->flags
& EDGE_CAN_FALLTHRU
)
526 /* Edge that cannot be fallthru or improbable or infrequent
527 successor (i.e. it is unsuitable successor). */
528 if (!(e
->flags
& EDGE_CAN_FALLTHRU
) || (e
->flags
& EDGE_COMPLEX
)
529 || prob
< branch_th
|| EDGE_FREQUENCY (e
) < exec_th
530 || e
->count
< count_th
)
533 /* If partitioning hot/cold basic blocks, don't consider edges
534 that cross section boundaries. */
536 if (better_edge_p (bb
, e
, prob
, freq
, best_prob
, best_freq
,
545 /* If the best destination has multiple predecessors, and can be
546 duplicated cheaper than a jump, don't allow it to be added
547 to a trace. We'll duplicate it when connecting traces. */
548 if (best_edge
&& EDGE_COUNT (best_edge
->dest
->preds
) >= 2
549 && copy_bb_p (best_edge
->dest
, 0))
552 /* Add all non-selected successors to the heaps. */
553 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
556 || e
->dest
== EXIT_BLOCK_PTR
557 || e
->dest
->il
.rtl
->visited
)
560 key
= bb_to_key (e
->dest
);
562 if (bbd
[e
->dest
->index
].heap
)
564 /* E->DEST is already in some heap. */
565 if (key
!= bbd
[e
->dest
->index
].node
->key
)
570 "Changing key for bb %d from %ld to %ld.\n",
572 (long) bbd
[e
->dest
->index
].node
->key
,
575 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
576 bbd
[e
->dest
->index
].node
, key
);
581 fibheap_t which_heap
= *heap
;
583 prob
= e
->probability
;
584 freq
= EDGE_FREQUENCY (e
);
586 if (!(e
->flags
& EDGE_CAN_FALLTHRU
)
587 || (e
->flags
& EDGE_COMPLEX
)
588 || prob
< branch_th
|| freq
< exec_th
589 || e
->count
< count_th
)
591 /* When partitioning hot/cold basic blocks, make sure
592 the cold blocks (and only the cold blocks) all get
593 pushed to the last round of trace collection. */
595 if (push_to_next_round_p (e
->dest
, round
,
598 which_heap
= new_heap
;
601 bbd
[e
->dest
->index
].heap
= which_heap
;
602 bbd
[e
->dest
->index
].node
= fibheap_insert (which_heap
,
608 " Possible start of %s round: %d (key: %ld)\n",
609 (which_heap
== new_heap
) ? "next" : "this",
610 e
->dest
->index
, (long) key
);
616 if (best_edge
) /* Suitable successor was found. */
618 if (best_edge
->dest
->il
.rtl
->visited
== *n_traces
)
620 /* We do nothing with one basic block loops. */
621 if (best_edge
->dest
!= bb
)
623 if (EDGE_FREQUENCY (best_edge
)
624 > 4 * best_edge
->dest
->frequency
/ 5)
626 /* The loop has at least 4 iterations. If the loop
627 header is not the first block of the function
628 we can rotate the loop. */
630 if (best_edge
->dest
!= ENTRY_BLOCK_PTR
->next_bb
)
635 "Rotating loop %d - %d\n",
636 best_edge
->dest
->index
, bb
->index
);
638 bb
->aux
= best_edge
->dest
;
639 bbd
[best_edge
->dest
->index
].in_trace
=
641 bb
= rotate_loop (best_edge
, trace
, *n_traces
);
646 /* The loop has less than 4 iterations. */
648 if (single_succ_p (bb
)
649 && copy_bb_p (best_edge
->dest
, !optimize_size
))
651 bb
= copy_bb (best_edge
->dest
, best_edge
, bb
,
658 /* Terminate the trace. */
663 /* Check for a situation
672 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
673 >= EDGE_FREQUENCY (AC).
674 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
675 Best ordering is then A B C.
677 This situation is created for example by:
684 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
686 && (e
->flags
& EDGE_CAN_FALLTHRU
)
687 && !(e
->flags
& EDGE_COMPLEX
)
688 && !e
->dest
->il
.rtl
->visited
689 && single_pred_p (e
->dest
)
690 && !(e
->flags
& EDGE_CROSSING
)
691 && single_succ_p (e
->dest
)
692 && (single_succ_edge (e
->dest
)->flags
694 && !(single_succ_edge (e
->dest
)->flags
& EDGE_COMPLEX
)
695 && single_succ (e
->dest
) == best_edge
->dest
696 && 2 * e
->dest
->frequency
>= EDGE_FREQUENCY (best_edge
))
700 fprintf (dump_file
, "Selecting BB %d\n",
701 best_edge
->dest
->index
);
705 bb
->aux
= best_edge
->dest
;
706 bbd
[best_edge
->dest
->index
].in_trace
= (*n_traces
) - 1;
707 bb
= best_edge
->dest
;
713 bbd
[trace
->first
->index
].start_of_trace
= *n_traces
- 1;
714 bbd
[trace
->last
->index
].end_of_trace
= *n_traces
- 1;
716 /* The trace is terminated so we have to recount the keys in heap
717 (some block can have a lower key because now one of its predecessors
718 is an end of the trace). */
719 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
721 if (e
->dest
== EXIT_BLOCK_PTR
722 || e
->dest
->il
.rtl
->visited
)
725 if (bbd
[e
->dest
->index
].heap
)
727 key
= bb_to_key (e
->dest
);
728 if (key
!= bbd
[e
->dest
->index
].node
->key
)
733 "Changing key for bb %d from %ld to %ld.\n",
735 (long) bbd
[e
->dest
->index
].node
->key
, key
);
737 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
738 bbd
[e
->dest
->index
].node
,
745 fibheap_delete (*heap
);
747 /* "Return" the new heap. */
751 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
752 it to trace after BB, mark OLD_BB visited and update pass' data structures
753 (TRACE is a number of trace which OLD_BB is duplicated to). */
756 copy_bb (basic_block old_bb
, edge e
, basic_block bb
, int trace
)
760 new_bb
= duplicate_block (old_bb
, e
, bb
);
761 BB_COPY_PARTITION (new_bb
, old_bb
);
763 gcc_assert (e
->dest
== new_bb
);
764 gcc_assert (!e
->dest
->il
.rtl
->visited
);
768 "Duplicated bb %d (created bb %d)\n",
769 old_bb
->index
, new_bb
->index
);
770 new_bb
->il
.rtl
->visited
= trace
;
771 new_bb
->aux
= bb
->aux
;
774 if (new_bb
->index
>= array_size
|| last_basic_block
> array_size
)
779 new_size
= MAX (last_basic_block
, new_bb
->index
+ 1);
780 new_size
= GET_ARRAY_SIZE (new_size
);
781 bbd
= xrealloc (bbd
, new_size
* sizeof (bbro_basic_block_data
));
782 for (i
= array_size
; i
< new_size
; i
++)
784 bbd
[i
].start_of_trace
= -1;
785 bbd
[i
].in_trace
= -1;
786 bbd
[i
].end_of_trace
= -1;
790 array_size
= new_size
;
795 "Growing the dynamic array to %d elements.\n",
800 bbd
[new_bb
->index
].in_trace
= trace
;
805 /* Compute and return the key (for the heap) of the basic block BB. */
808 bb_to_key (basic_block bb
)
814 /* Do not start in probably never executed blocks. */
816 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
817 || probably_never_executed_bb_p (bb
))
820 /* Prefer blocks whose predecessor is an end of some trace
821 or whose predecessor edge is EDGE_DFS_BACK. */
822 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
824 if ((e
->src
!= ENTRY_BLOCK_PTR
&& bbd
[e
->src
->index
].end_of_trace
>= 0)
825 || (e
->flags
& EDGE_DFS_BACK
))
827 int edge_freq
= EDGE_FREQUENCY (e
);
829 if (edge_freq
> priority
)
830 priority
= edge_freq
;
835 /* The block with priority should have significantly lower key. */
836 return -(100 * BB_FREQ_MAX
+ 100 * priority
+ bb
->frequency
);
837 return -bb
->frequency
;
840 /* Return true when the edge E from basic block BB is better than the temporary
841 best edge (details are in function). The probability of edge E is PROB. The
842 frequency of the successor is FREQ. The current best probability is
843 BEST_PROB, the best frequency is BEST_FREQ.
844 The edge is considered to be equivalent when PROB does not differ much from
845 BEST_PROB; similarly for frequency. */
848 better_edge_p (basic_block bb
, edge e
, int prob
, int freq
, int best_prob
,
849 int best_freq
, edge cur_best_edge
)
853 /* The BEST_* values do not have to be best, but can be a bit smaller than
855 int diff_prob
= best_prob
/ 10;
856 int diff_freq
= best_freq
/ 10;
858 if (prob
> best_prob
+ diff_prob
)
859 /* The edge has higher probability than the temporary best edge. */
860 is_better_edge
= true;
861 else if (prob
< best_prob
- diff_prob
)
862 /* The edge has lower probability than the temporary best edge. */
863 is_better_edge
= false;
864 else if (freq
< best_freq
- diff_freq
)
865 /* The edge and the temporary best edge have almost equivalent
866 probabilities. The higher frequency of a successor now means
867 that there is another edge going into that successor.
868 This successor has lower frequency so it is better. */
869 is_better_edge
= true;
870 else if (freq
> best_freq
+ diff_freq
)
871 /* This successor has higher frequency so it is worse. */
872 is_better_edge
= false;
873 else if (e
->dest
->prev_bb
== bb
)
874 /* The edges have equivalent probabilities and the successors
875 have equivalent frequencies. Select the previous successor. */
876 is_better_edge
= true;
878 is_better_edge
= false;
880 /* If we are doing hot/cold partitioning, make sure that we always favor
881 non-crossing edges over crossing edges. */
884 && flag_reorder_blocks_and_partition
886 && (cur_best_edge
->flags
& EDGE_CROSSING
)
887 && !(e
->flags
& EDGE_CROSSING
))
888 is_better_edge
= true;
890 return is_better_edge
;
893 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
896 connect_traces (int n_traces
, struct trace
*traces
)
903 int current_partition
;
905 gcov_type count_threshold
;
907 freq_threshold
= max_entry_frequency
* DUPLICATION_THRESHOLD
/ 1000;
908 if (max_entry_count
< INT_MAX
/ 1000)
909 count_threshold
= max_entry_count
* DUPLICATION_THRESHOLD
/ 1000;
911 count_threshold
= max_entry_count
/ 1000 * DUPLICATION_THRESHOLD
;
913 connected
= XCNEWVEC (bool, n_traces
);
916 current_partition
= BB_PARTITION (traces
[0].first
);
919 if (flag_reorder_blocks_and_partition
)
920 for (i
= 0; i
< n_traces
&& !two_passes
; i
++)
921 if (BB_PARTITION (traces
[0].first
)
922 != BB_PARTITION (traces
[i
].first
))
925 for (i
= 0; i
< n_traces
|| (two_passes
&& current_pass
== 1) ; i
++)
934 gcc_assert (two_passes
&& current_pass
== 1);
938 if (current_partition
== BB_HOT_PARTITION
)
939 current_partition
= BB_COLD_PARTITION
;
941 current_partition
= BB_HOT_PARTITION
;
948 && BB_PARTITION (traces
[t
].first
) != current_partition
)
953 /* Find the predecessor traces. */
954 for (t2
= t
; t2
> 0;)
959 FOR_EACH_EDGE (e
, ei
, traces
[t2
].first
->preds
)
961 int si
= e
->src
->index
;
963 if (e
->src
!= ENTRY_BLOCK_PTR
964 && (e
->flags
& EDGE_CAN_FALLTHRU
)
965 && !(e
->flags
& EDGE_COMPLEX
)
966 && bbd
[si
].end_of_trace
>= 0
967 && !connected
[bbd
[si
].end_of_trace
]
968 && (BB_PARTITION (e
->src
) == current_partition
)
970 || e
->probability
> best
->probability
971 || (e
->probability
== best
->probability
972 && traces
[bbd
[si
].end_of_trace
].length
> best_len
)))
975 best_len
= traces
[bbd
[si
].end_of_trace
].length
;
980 best
->src
->aux
= best
->dest
;
981 t2
= bbd
[best
->src
->index
].end_of_trace
;
982 connected
[t2
] = true;
986 fprintf (dump_file
, "Connection: %d %d\n",
987 best
->src
->index
, best
->dest
->index
);
995 traces
[last_trace
].last
->aux
= traces
[t2
].first
;
998 /* Find the successor traces. */
1001 /* Find the continuation of the chain. */
1005 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1007 int di
= e
->dest
->index
;
1009 if (e
->dest
!= EXIT_BLOCK_PTR
1010 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1011 && !(e
->flags
& EDGE_COMPLEX
)
1012 && bbd
[di
].start_of_trace
>= 0
1013 && !connected
[bbd
[di
].start_of_trace
]
1014 && (BB_PARTITION (e
->dest
) == current_partition
)
1016 || e
->probability
> best
->probability
1017 || (e
->probability
== best
->probability
1018 && traces
[bbd
[di
].start_of_trace
].length
> best_len
)))
1021 best_len
= traces
[bbd
[di
].start_of_trace
].length
;
1029 fprintf (dump_file
, "Connection: %d %d\n",
1030 best
->src
->index
, best
->dest
->index
);
1032 t
= bbd
[best
->dest
->index
].start_of_trace
;
1033 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1034 connected
[t
] = true;
1039 /* Try to connect the traces by duplication of 1 block. */
1041 basic_block next_bb
= NULL
;
1042 bool try_copy
= false;
1044 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1045 if (e
->dest
!= EXIT_BLOCK_PTR
1046 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1047 && !(e
->flags
& EDGE_COMPLEX
)
1048 && (!best
|| e
->probability
> best
->probability
))
1054 /* If the destination is a start of a trace which is only
1055 one block long, then no need to search the successor
1056 blocks of the trace. Accept it. */
1057 if (bbd
[e
->dest
->index
].start_of_trace
>= 0
1058 && traces
[bbd
[e
->dest
->index
].start_of_trace
].length
1066 FOR_EACH_EDGE (e2
, ei
, e
->dest
->succs
)
1068 int di
= e2
->dest
->index
;
1070 if (e2
->dest
== EXIT_BLOCK_PTR
1071 || ((e2
->flags
& EDGE_CAN_FALLTHRU
)
1072 && !(e2
->flags
& EDGE_COMPLEX
)
1073 && bbd
[di
].start_of_trace
>= 0
1074 && !connected
[bbd
[di
].start_of_trace
]
1075 && (BB_PARTITION (e2
->dest
) == current_partition
)
1076 && (EDGE_FREQUENCY (e2
) >= freq_threshold
)
1077 && (e2
->count
>= count_threshold
)
1079 || e2
->probability
> best2
->probability
1080 || (e2
->probability
== best2
->probability
1081 && traces
[bbd
[di
].start_of_trace
].length
1086 if (e2
->dest
!= EXIT_BLOCK_PTR
)
1087 best2_len
= traces
[bbd
[di
].start_of_trace
].length
;
1089 best2_len
= INT_MAX
;
1096 if (flag_reorder_blocks_and_partition
)
1099 /* Copy tiny blocks always; copy larger blocks only when the
1100 edge is traversed frequently enough. */
1102 && copy_bb_p (best
->dest
,
1104 && EDGE_FREQUENCY (best
) >= freq_threshold
1105 && best
->count
>= count_threshold
))
1111 fprintf (dump_file
, "Connection: %d %d ",
1112 traces
[t
].last
->index
, best
->dest
->index
);
1114 fputc ('\n', dump_file
);
1115 else if (next_bb
== EXIT_BLOCK_PTR
)
1116 fprintf (dump_file
, "exit\n");
1118 fprintf (dump_file
, "%d\n", next_bb
->index
);
1121 new_bb
= copy_bb (best
->dest
, best
, traces
[t
].last
, t
);
1122 traces
[t
].last
= new_bb
;
1123 if (next_bb
&& next_bb
!= EXIT_BLOCK_PTR
)
1125 t
= bbd
[next_bb
->index
].start_of_trace
;
1126 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1127 connected
[t
] = true;
1131 break; /* Stop finding the successor traces. */
1134 break; /* Stop finding the successor traces. */
1143 fprintf (dump_file
, "Final order:\n");
1144 for (bb
= traces
[0].first
; bb
; bb
= bb
->aux
)
1145 fprintf (dump_file
, "%d ", bb
->index
);
1146 fprintf (dump_file
, "\n");
1153 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1154 when code size is allowed to grow by duplication. */
1157 copy_bb_p (basic_block bb
, int code_may_grow
)
1160 int max_size
= uncond_jump_length
;
1165 if (EDGE_COUNT (bb
->preds
) < 2)
1167 if (!can_duplicate_block_p (bb
))
1170 /* Avoid duplicating blocks which have many successors (PR/13430). */
1171 if (EDGE_COUNT (bb
->succs
) > 8)
1174 if (code_may_grow
&& maybe_hot_bb_p (bb
))
1175 max_size
*= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS
);
1177 FOR_BB_INSNS (bb
, insn
)
1180 size
+= get_attr_min_length (insn
);
1183 if (size
<= max_size
)
1189 "Block %d can't be copied because its size = %d.\n",
1196 /* Return the length of unconditional jump instruction. */
1199 get_uncond_jump_length (void)
1204 label
= emit_label_before (gen_label_rtx (), get_insns ());
1205 jump
= emit_jump_insn (gen_jump (label
));
1207 length
= get_attr_min_length (jump
);
1210 delete_insn (label
);
1214 /* Find the basic blocks that are rarely executed and need to be moved to
1215 a separate section of the .o file (to cut down on paging and improve
1219 find_rarely_executed_basic_blocks_and_crossing_edges (edge
*crossing_edges
,
1220 int *n_crossing_edges
,
1224 bool has_hot_blocks
= false;
1229 /* Mark which partition (hot/cold) each basic block belongs in. */
1233 if (probably_never_executed_bb_p (bb
))
1234 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
1237 BB_SET_PARTITION (bb
, BB_HOT_PARTITION
);
1238 has_hot_blocks
= true;
1242 /* Mark every edge that crosses between sections. */
1246 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1248 if (e
->src
!= ENTRY_BLOCK_PTR
1249 && e
->dest
!= EXIT_BLOCK_PTR
1250 && BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1252 e
->flags
|= EDGE_CROSSING
;
1256 crossing_edges
= xrealloc (crossing_edges
,
1257 (*max_idx
) * sizeof (edge
));
1259 crossing_edges
[i
++] = e
;
1262 e
->flags
&= ~EDGE_CROSSING
;
1264 *n_crossing_edges
= i
;
1267 /* If any destination of a crossing edge does not have a label, add label;
1268 Convert any fall-through crossing edges (for blocks that do not contain
1269 a jump) to unconditional jumps. */
1272 add_labels_and_missing_jumps (edge
*crossing_edges
, int n_crossing_edges
)
1281 for (i
=0; i
< n_crossing_edges
; i
++)
1283 if (crossing_edges
[i
])
1285 src
= crossing_edges
[i
]->src
;
1286 dest
= crossing_edges
[i
]->dest
;
1288 /* Make sure dest has a label. */
1290 if (dest
&& (dest
!= EXIT_BLOCK_PTR
))
1292 label
= block_label (dest
);
1294 /* Make sure source block ends with a jump. */
1296 if (src
&& (src
!= ENTRY_BLOCK_PTR
))
1298 if (!JUMP_P (BB_END (src
)))
1299 /* bb just falls through. */
1301 /* make sure there's only one successor */
1302 gcc_assert (single_succ_p (src
));
1304 /* Find label in dest block. */
1305 label
= block_label (dest
);
1307 new_jump
= emit_jump_insn_after (gen_jump (label
),
1309 barrier
= emit_barrier_after (new_jump
);
1310 JUMP_LABEL (new_jump
) = label
;
1311 LABEL_NUSES (label
) += 1;
1312 src
->il
.rtl
->footer
= unlink_insn_chain (barrier
, barrier
);
1313 /* Mark edge as non-fallthru. */
1314 crossing_edges
[i
]->flags
&= ~EDGE_FALLTHRU
;
1315 } /* end: 'if (GET_CODE ... ' */
1316 } /* end: 'if (src && src->index...' */
1317 } /* end: 'if (dest && dest->index...' */
1318 } /* end: 'if (crossing_edges[i]...' */
1319 } /* end for loop */
1322 /* Find any bb's where the fall-through edge is a crossing edge (note that
1323 these bb's must also contain a conditional jump; we've already
1324 dealt with fall-through edges for blocks that didn't have a
1325 conditional jump in the call to add_labels_and_missing_jumps).
1326 Convert the fall-through edge to non-crossing edge by inserting a
1327 new bb to fall-through into. The new bb will contain an
1328 unconditional jump (crossing edge) to the original fall through
1332 fix_up_fall_thru_edges (void)
1339 edge cond_jump
= NULL
;
1341 bool cond_jump_crosses
;
1344 rtx fall_thru_label
;
1347 FOR_EACH_BB (cur_bb
)
1350 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1351 succ1
= EDGE_SUCC (cur_bb
, 0);
1355 if (EDGE_COUNT (cur_bb
->succs
) > 1)
1356 succ2
= EDGE_SUCC (cur_bb
, 1);
1360 /* Find the fall-through edge. */
1363 && (succ1
->flags
& EDGE_FALLTHRU
))
1369 && (succ2
->flags
& EDGE_FALLTHRU
))
1375 if (fall_thru
&& (fall_thru
->dest
!= EXIT_BLOCK_PTR
))
1377 /* Check to see if the fall-thru edge is a crossing edge. */
1379 if (fall_thru
->flags
& EDGE_CROSSING
)
1381 /* The fall_thru edge crosses; now check the cond jump edge, if
1384 cond_jump_crosses
= true;
1386 old_jump
= BB_END (cur_bb
);
1388 /* Find the jump instruction, if there is one. */
1392 if (!(cond_jump
->flags
& EDGE_CROSSING
))
1393 cond_jump_crosses
= false;
1395 /* We know the fall-thru edge crosses; if the cond
1396 jump edge does NOT cross, and its destination is the
1397 next block in the bb order, invert the jump
1398 (i.e. fix it so the fall thru does not cross and
1399 the cond jump does). */
1401 if (!cond_jump_crosses
1402 && cur_bb
->aux
== cond_jump
->dest
)
1404 /* Find label in fall_thru block. We've already added
1405 any missing labels, so there must be one. */
1407 fall_thru_label
= block_label (fall_thru
->dest
);
1409 if (old_jump
&& fall_thru_label
)
1410 invert_worked
= invert_jump (old_jump
,
1414 fall_thru
->flags
&= ~EDGE_FALLTHRU
;
1415 cond_jump
->flags
|= EDGE_FALLTHRU
;
1416 update_br_prob_note (cur_bb
);
1418 fall_thru
= cond_jump
;
1420 cond_jump
->flags
|= EDGE_CROSSING
;
1421 fall_thru
->flags
&= ~EDGE_CROSSING
;
1426 if (cond_jump_crosses
|| !invert_worked
)
1428 /* This is the case where both edges out of the basic
1429 block are crossing edges. Here we will fix up the
1430 fall through edge. The jump edge will be taken care
1433 new_bb
= force_nonfallthru (fall_thru
);
1437 new_bb
->aux
= cur_bb
->aux
;
1438 cur_bb
->aux
= new_bb
;
1440 /* Make sure new fall-through bb is in same
1441 partition as bb it's falling through from. */
1443 BB_COPY_PARTITION (new_bb
, cur_bb
);
1444 single_succ_edge (new_bb
)->flags
|= EDGE_CROSSING
;
1447 /* Add barrier after new jump */
1451 barrier
= emit_barrier_after (BB_END (new_bb
));
1452 new_bb
->il
.rtl
->footer
= unlink_insn_chain (barrier
,
1457 barrier
= emit_barrier_after (BB_END (cur_bb
));
1458 cur_bb
->il
.rtl
->footer
= unlink_insn_chain (barrier
,
1467 /* This function checks the destination blockof a "crossing jump" to
1468 see if it has any crossing predecessors that begin with a code label
1469 and end with an unconditional jump. If so, it returns that predecessor
1470 block. (This is to avoid creating lots of new basic blocks that all
1471 contain unconditional jumps to the same destination). */
1474 find_jump_block (basic_block jump_dest
)
1476 basic_block source_bb
= NULL
;
1481 FOR_EACH_EDGE (e
, ei
, jump_dest
->preds
)
1482 if (e
->flags
& EDGE_CROSSING
)
1484 basic_block src
= e
->src
;
1486 /* Check each predecessor to see if it has a label, and contains
1487 only one executable instruction, which is an unconditional jump.
1488 If so, we can use it. */
1490 if (LABEL_P (BB_HEAD (src
)))
1491 for (insn
= BB_HEAD (src
);
1492 !INSN_P (insn
) && insn
!= NEXT_INSN (BB_END (src
));
1493 insn
= NEXT_INSN (insn
))
1496 && insn
== BB_END (src
)
1498 && !any_condjump_p (insn
))
1512 /* Find all BB's with conditional jumps that are crossing edges;
1513 insert a new bb and make the conditional jump branch to the new
1514 bb instead (make the new bb same color so conditional branch won't
1515 be a 'crossing' edge). Insert an unconditional jump from the
1516 new bb to the original destination of the conditional jump. */
1519 fix_crossing_conditional_branches (void)
1523 basic_block last_bb
;
1525 basic_block prev_bb
;
1532 rtx old_label
= NULL_RTX
;
1537 last_bb
= EXIT_BLOCK_PTR
->prev_bb
;
1539 FOR_EACH_BB (cur_bb
)
1541 crossing_edge
= NULL
;
1542 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1543 succ1
= EDGE_SUCC (cur_bb
, 0);
1547 if (EDGE_COUNT (cur_bb
->succs
) > 1)
1548 succ2
= EDGE_SUCC (cur_bb
, 1);
1552 /* We already took care of fall-through edges, so only one successor
1553 can be a crossing edge. */
1555 if (succ1
&& (succ1
->flags
& EDGE_CROSSING
))
1556 crossing_edge
= succ1
;
1557 else if (succ2
&& (succ2
->flags
& EDGE_CROSSING
))
1558 crossing_edge
= succ2
;
1562 old_jump
= BB_END (cur_bb
);
1564 /* Check to make sure the jump instruction is a
1565 conditional jump. */
1569 if (any_condjump_p (old_jump
))
1571 if (GET_CODE (PATTERN (old_jump
)) == SET
)
1572 set_src
= SET_SRC (PATTERN (old_jump
));
1573 else if (GET_CODE (PATTERN (old_jump
)) == PARALLEL
)
1575 set_src
= XVECEXP (PATTERN (old_jump
), 0,0);
1576 if (GET_CODE (set_src
) == SET
)
1577 set_src
= SET_SRC (set_src
);
1583 if (set_src
&& (GET_CODE (set_src
) == IF_THEN_ELSE
))
1585 if (GET_CODE (XEXP (set_src
, 1)) == PC
)
1586 old_label
= XEXP (set_src
, 2);
1587 else if (GET_CODE (XEXP (set_src
, 2)) == PC
)
1588 old_label
= XEXP (set_src
, 1);
1590 /* Check to see if new bb for jumping to that dest has
1591 already been created; if so, use it; if not, create
1594 new_bb
= find_jump_block (crossing_edge
->dest
);
1597 new_label
= block_label (new_bb
);
1600 /* Create new basic block to be dest for
1601 conditional jump. */
1603 new_bb
= create_basic_block (NULL
, NULL
, last_bb
);
1604 new_bb
->aux
= last_bb
->aux
;
1605 last_bb
->aux
= new_bb
;
1609 /* Update register liveness information. */
1611 new_bb
->il
.rtl
->global_live_at_start
= ALLOC_REG_SET (®_obstack
);
1612 new_bb
->il
.rtl
->global_live_at_end
= ALLOC_REG_SET (®_obstack
);
1613 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_end
,
1614 prev_bb
->il
.rtl
->global_live_at_end
);
1615 COPY_REG_SET (new_bb
->il
.rtl
->global_live_at_start
,
1616 prev_bb
->il
.rtl
->global_live_at_end
);
1618 /* Put appropriate instructions in new bb. */
1620 new_label
= gen_label_rtx ();
1621 emit_label_before (new_label
, BB_HEAD (new_bb
));
1622 BB_HEAD (new_bb
) = new_label
;
1624 if (GET_CODE (old_label
) == LABEL_REF
)
1626 old_label
= JUMP_LABEL (old_jump
);
1627 new_jump
= emit_jump_insn_after (gen_jump
1633 gcc_assert (HAVE_return
1634 && GET_CODE (old_label
) == RETURN
);
1635 new_jump
= emit_jump_insn_after (gen_return (),
1639 barrier
= emit_barrier_after (new_jump
);
1640 JUMP_LABEL (new_jump
) = old_label
;
1641 new_bb
->il
.rtl
->footer
= unlink_insn_chain (barrier
,
1644 /* Make sure new bb is in same partition as source
1645 of conditional branch. */
1646 BB_COPY_PARTITION (new_bb
, cur_bb
);
1649 /* Make old jump branch to new bb. */
1651 redirect_jump (old_jump
, new_label
, 0);
1653 /* Remove crossing_edge as predecessor of 'dest'. */
1655 dest
= crossing_edge
->dest
;
1657 redirect_edge_succ (crossing_edge
, new_bb
);
1659 /* Make a new edge from new_bb to old dest; new edge
1660 will be a successor for new_bb and a predecessor
1663 if (EDGE_COUNT (new_bb
->succs
) == 0)
1664 new_edge
= make_edge (new_bb
, dest
, 0);
1666 new_edge
= EDGE_SUCC (new_bb
, 0);
1668 crossing_edge
->flags
&= ~EDGE_CROSSING
;
1669 new_edge
->flags
|= EDGE_CROSSING
;
1675 /* Find any unconditional branches that cross between hot and cold
1676 sections. Convert them into indirect jumps instead. */
1679 fix_crossing_unconditional_branches (void)
1685 rtx indirect_jump_sequence
;
1686 rtx jump_insn
= NULL_RTX
;
1691 FOR_EACH_BB (cur_bb
)
1693 last_insn
= BB_END (cur_bb
);
1695 if (EDGE_COUNT (cur_bb
->succs
) < 1)
1698 succ
= EDGE_SUCC (cur_bb
, 0);
1700 /* Check to see if bb ends in a crossing (unconditional) jump. At
1701 this point, no crossing jumps should be conditional. */
1703 if (JUMP_P (last_insn
)
1704 && (succ
->flags
& EDGE_CROSSING
))
1708 gcc_assert (!any_condjump_p (last_insn
));
1710 /* Make sure the jump is not already an indirect or table jump. */
1712 if (!computed_jump_p (last_insn
)
1713 && !tablejump_p (last_insn
, &label2
, &table
))
1715 /* We have found a "crossing" unconditional branch. Now
1716 we must convert it to an indirect jump. First create
1717 reference of label, as target for jump. */
1719 label
= JUMP_LABEL (last_insn
);
1720 label_addr
= gen_rtx_LABEL_REF (Pmode
, label
);
1721 LABEL_NUSES (label
) += 1;
1723 /* Get a register to use for the indirect jump. */
1725 new_reg
= gen_reg_rtx (Pmode
);
1727 /* Generate indirect the jump sequence. */
1730 emit_move_insn (new_reg
, label_addr
);
1731 emit_indirect_jump (new_reg
);
1732 indirect_jump_sequence
= get_insns ();
1735 /* Make sure every instruction in the new jump sequence has
1736 its basic block set to be cur_bb. */
1738 for (cur_insn
= indirect_jump_sequence
; cur_insn
;
1739 cur_insn
= NEXT_INSN (cur_insn
))
1741 if (!BARRIER_P (cur_insn
))
1742 BLOCK_FOR_INSN (cur_insn
) = cur_bb
;
1743 if (JUMP_P (cur_insn
))
1744 jump_insn
= cur_insn
;
1747 /* Insert the new (indirect) jump sequence immediately before
1748 the unconditional jump, then delete the unconditional jump. */
1750 emit_insn_before (indirect_jump_sequence
, last_insn
);
1751 delete_insn (last_insn
);
1753 /* Make BB_END for cur_bb be the jump instruction (NOT the
1754 barrier instruction at the end of the sequence...). */
1756 BB_END (cur_bb
) = jump_insn
;
1762 /* Add REG_CROSSING_JUMP note to all crossing jump insns. */
1765 add_reg_crossing_jump_notes (void)
1772 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1773 if ((e
->flags
& EDGE_CROSSING
)
1774 && JUMP_P (BB_END (e
->src
)))
1775 REG_NOTES (BB_END (e
->src
)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP
,
1781 /* Hot and cold basic blocks are partitioned and put in separate
1782 sections of the .o file, to reduce paging and improve cache
1783 performance (hopefully). This can result in bits of code from the
1784 same function being widely separated in the .o file. However this
1785 is not obvious to the current bb structure. Therefore we must take
1786 care to ensure that: 1). There are no fall_thru edges that cross
1787 between sections; 2). For those architectures which have "short"
1788 conditional branches, all conditional branches that attempt to
1789 cross between sections are converted to unconditional branches;
1790 and, 3). For those architectures which have "short" unconditional
1791 branches, all unconditional branches that attempt to cross between
1792 sections are converted to indirect jumps.
1794 The code for fixing up fall_thru edges that cross between hot and
1795 cold basic blocks does so by creating new basic blocks containing
1796 unconditional branches to the appropriate label in the "other"
1797 section. The new basic block is then put in the same (hot or cold)
1798 section as the original conditional branch, and the fall_thru edge
1799 is modified to fall into the new basic block instead. By adding
1800 this level of indirection we end up with only unconditional branches
1801 crossing between hot and cold sections.
1803 Conditional branches are dealt with by adding a level of indirection.
1804 A new basic block is added in the same (hot/cold) section as the
1805 conditional branch, and the conditional branch is retargeted to the
1806 new basic block. The new basic block contains an unconditional branch
1807 to the original target of the conditional branch (in the other section).
1809 Unconditional branches are dealt with by converting them into
1813 fix_edges_for_rarely_executed_code (edge
*crossing_edges
,
1814 int n_crossing_edges
)
1816 /* Make sure the source of any crossing edge ends in a jump and the
1817 destination of any crossing edge has a label. */
1819 add_labels_and_missing_jumps (crossing_edges
, n_crossing_edges
);
1821 /* Convert all crossing fall_thru edges to non-crossing fall
1822 thrus to unconditional jumps (that jump to the original fall
1825 fix_up_fall_thru_edges ();
1827 /* If the architecture does not have conditional branches that can
1828 span all of memory, convert crossing conditional branches into
1829 crossing unconditional branches. */
1831 if (!HAS_LONG_COND_BRANCH
)
1832 fix_crossing_conditional_branches ();
1834 /* If the architecture does not have unconditional branches that
1835 can span all of memory, convert crossing unconditional branches
1836 into indirect jumps. Since adding an indirect jump also adds
1837 a new register usage, update the register usage information as
1840 if (!HAS_LONG_UNCOND_BRANCH
)
1842 fix_crossing_unconditional_branches ();
1843 reg_scan (get_insns(), max_reg_num ());
1846 add_reg_crossing_jump_notes ();
1849 /* Verify, in the basic block chain, that there is at most one switch
1850 between hot/cold partitions. This is modelled on
1851 rtl_verify_flow_info_1, but it cannot go inside that function
1852 because this condition will not be true until after
1853 reorder_basic_blocks is called. */
1856 verify_hot_cold_block_grouping (void)
1860 bool switched_sections
= false;
1861 int current_partition
= 0;
1865 if (!current_partition
)
1866 current_partition
= BB_PARTITION (bb
);
1867 if (BB_PARTITION (bb
) != current_partition
)
1869 if (switched_sections
)
1871 error ("multiple hot/cold transitions found (bb %i)",
1877 switched_sections
= true;
1878 current_partition
= BB_PARTITION (bb
);
1886 /* Reorder basic blocks. The main entry point to this file. FLAGS is
1887 the set of flags to pass to cfg_layout_initialize(). */
1890 reorder_basic_blocks (unsigned int flags
)
1894 struct trace
*traces
;
1896 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
1899 if (targetm
.cannot_modify_jumps_p ())
1902 cfg_layout_initialize (flags
);
1904 set_edge_can_fallthru_flag ();
1905 mark_dfs_back_edges ();
1907 /* We are estimating the length of uncond jump insn only once since the code
1908 for getting the insn length always returns the minimal length now. */
1909 if (uncond_jump_length
== 0)
1910 uncond_jump_length
= get_uncond_jump_length ();
1912 /* We need to know some information for each basic block. */
1913 array_size
= GET_ARRAY_SIZE (last_basic_block
);
1914 bbd
= XNEWVEC (bbro_basic_block_data
, array_size
);
1915 for (i
= 0; i
< array_size
; i
++)
1917 bbd
[i
].start_of_trace
= -1;
1918 bbd
[i
].in_trace
= -1;
1919 bbd
[i
].end_of_trace
= -1;
1924 traces
= XNEWVEC (struct trace
, n_basic_blocks
);
1926 find_traces (&n_traces
, traces
);
1927 connect_traces (n_traces
, traces
);
1932 dump_flow_info (dump_file
, dump_flags
);
1934 cfg_layout_finalize ();
1935 if (flag_reorder_blocks_and_partition
)
1936 verify_hot_cold_block_grouping ();
1939 /* Determine which partition the first basic block in the function
1940 belongs to, then find the first basic block in the current function
1941 that belongs to a different section, and insert a
1942 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
1943 instruction stream. When writing out the assembly code,
1944 encountering this note will make the compiler switch between the
1945 hot and cold text sections. */
1948 insert_section_boundary_note (void)
1952 int first_partition
= 0;
1954 if (flag_reorder_blocks_and_partition
)
1957 if (!first_partition
)
1958 first_partition
= BB_PARTITION (bb
);
1959 if (BB_PARTITION (bb
) != first_partition
)
1961 new_note
= emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS
,
1968 /* Duplicate the blocks containing computed gotos. This basically unfactors
1969 computed gotos that were factored early on in the compilation process to
1970 speed up edge based data flow. We used to not unfactoring them again,
1971 which can seriously pessimize code with many computed jumps in the source
1972 code, such as interpreters. See e.g. PR15242. */
1975 gate_duplicate_computed_gotos (void)
1977 return (optimize
> 0 && flag_expensive_optimizations
&& !optimize_size
);
1982 duplicate_computed_gotos (void)
1984 basic_block bb
, new_bb
;
1988 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
1991 if (targetm
.cannot_modify_jumps_p ())
1994 cfg_layout_initialize (0);
1996 /* We are estimating the length of uncond jump insn only once
1997 since the code for getting the insn length always returns
1998 the minimal length now. */
1999 if (uncond_jump_length
== 0)
2000 uncond_jump_length
= get_uncond_jump_length ();
2002 max_size
= uncond_jump_length
* PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS
);
2003 candidates
= BITMAP_ALLOC (NULL
);
2005 /* Look for blocks that end in a computed jump, and see if such blocks
2006 are suitable for unfactoring. If a block is a candidate for unfactoring,
2007 mark it in the candidates. */
2013 int size
, all_flags
;
2015 /* Build the reorder chain for the original order of blocks. */
2016 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2017 bb
->aux
= bb
->next_bb
;
2019 /* Obviously the block has to end in a computed jump. */
2020 if (!computed_jump_p (BB_END (bb
)))
2023 /* Only consider blocks that can be duplicated. */
2024 if (find_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
)
2025 || !can_duplicate_block_p (bb
))
2028 /* Make sure that the block is small enough. */
2030 FOR_BB_INSNS (bb
, insn
)
2033 size
+= get_attr_min_length (insn
);
2034 if (size
> max_size
)
2037 if (size
> max_size
)
2040 /* Final check: there must not be any incoming abnormal edges. */
2042 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2043 all_flags
|= e
->flags
;
2044 if (all_flags
& EDGE_COMPLEX
)
2047 bitmap_set_bit (candidates
, bb
->index
);
2050 /* Nothing to do if there is no computed jump here. */
2051 if (bitmap_empty_p (candidates
))
2054 /* Duplicate computed gotos. */
2057 if (bb
->il
.rtl
->visited
)
2060 bb
->il
.rtl
->visited
= 1;
2062 /* BB must have one outgoing edge. That edge must not lead to
2063 the exit block or the next block.
2064 The destination must have more than one predecessor. */
2065 if (!single_succ_p (bb
)
2066 || single_succ (bb
) == EXIT_BLOCK_PTR
2067 || single_succ (bb
) == bb
->next_bb
2068 || single_pred_p (single_succ (bb
)))
2071 /* The successor block has to be a duplication candidate. */
2072 if (!bitmap_bit_p (candidates
, single_succ (bb
)->index
))
2075 new_bb
= duplicate_block (single_succ (bb
), single_succ_edge (bb
), bb
);
2076 new_bb
->aux
= bb
->aux
;
2078 new_bb
->il
.rtl
->visited
= 1;
2082 cfg_layout_finalize ();
2084 BITMAP_FREE (candidates
);
2088 struct tree_opt_pass pass_duplicate_computed_gotos
=
2090 "compgotos", /* name */
2091 gate_duplicate_computed_gotos
, /* gate */
2092 duplicate_computed_gotos
, /* execute */
2095 0, /* static_pass_number */
2096 TV_REORDER_BLOCKS
, /* tv_id */
2097 0, /* properties_required */
2098 0, /* properties_provided */
2099 0, /* properties_destroyed */
2100 0, /* todo_flags_start */
2101 TODO_dump_func
, /* todo_flags_finish */
2106 /* This function is the main 'entrance' for the optimization that
2107 partitions hot and cold basic blocks into separate sections of the
2108 .o file (to improve performance and cache locality). Ideally it
2109 would be called after all optimizations that rearrange the CFG have
2110 been called. However part of this optimization may introduce new
2111 register usage, so it must be called before register allocation has
2112 occurred. This means that this optimization is actually called
2113 well before the optimization that reorders basic blocks (see
2116 This optimization checks the feedback information to determine
2117 which basic blocks are hot/cold, updates flags on the basic blocks
2118 to indicate which section they belong in. This information is
2119 later used for writing out sections in the .o file. Because hot
2120 and cold sections can be arbitrarily large (within the bounds of
2121 memory), far beyond the size of a single function, it is necessary
2122 to fix up all edges that cross section boundaries, to make sure the
2123 instructions used can actually span the required distance. The
2124 fixes are described below.
2126 Fall-through edges must be changed into jumps; it is not safe or
2127 legal to fall through across a section boundary. Whenever a
2128 fall-through edge crossing a section boundary is encountered, a new
2129 basic block is inserted (in the same section as the fall-through
2130 source), and the fall through edge is redirected to the new basic
2131 block. The new basic block contains an unconditional jump to the
2132 original fall-through target. (If the unconditional jump is
2133 insufficient to cross section boundaries, that is dealt with a
2134 little later, see below).
2136 In order to deal with architectures that have short conditional
2137 branches (which cannot span all of memory) we take any conditional
2138 jump that attempts to cross a section boundary and add a level of
2139 indirection: it becomes a conditional jump to a new basic block, in
2140 the same section. The new basic block contains an unconditional
2141 jump to the original target, in the other section.
2143 For those architectures whose unconditional branch is also
2144 incapable of reaching all of memory, those unconditional jumps are
2145 converted into indirect jumps, through a register.
2147 IMPORTANT NOTE: This optimization causes some messy interactions
2148 with the cfg cleanup optimizations; those optimizations want to
2149 merge blocks wherever possible, and to collapse indirect jump
2150 sequences (change "A jumps to B jumps to C" directly into "A jumps
2151 to C"). Those optimizations can undo the jump fixes that
2152 partitioning is required to make (see above), in order to ensure
2153 that jumps attempting to cross section boundaries are really able
2154 to cover whatever distance the jump requires (on many architectures
2155 conditional or unconditional jumps are not able to reach all of
2156 memory). Therefore tests have to be inserted into each such
2157 optimization to make sure that it does not undo stuff necessary to
2158 cross partition boundaries. This would be much less of a problem
2159 if we could perform this optimization later in the compilation, but
2160 unfortunately the fact that we may need to create indirect jumps
2161 (through registers) requires that this optimization be performed
2162 before register allocation. */
2165 partition_hot_cold_basic_blocks (void)
2168 edge
*crossing_edges
;
2169 int n_crossing_edges
;
2170 int max_edges
= 2 * last_basic_block
;
2172 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
2175 crossing_edges
= XCNEWVEC (edge
, max_edges
);
2177 cfg_layout_initialize (0);
2179 FOR_EACH_BB (cur_bb
)
2180 if (cur_bb
->index
>= NUM_FIXED_BLOCKS
2181 && cur_bb
->next_bb
->index
>= NUM_FIXED_BLOCKS
)
2182 cur_bb
->aux
= cur_bb
->next_bb
;
2184 find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges
,
2188 if (n_crossing_edges
> 0)
2189 fix_edges_for_rarely_executed_code (crossing_edges
, n_crossing_edges
);
2191 free (crossing_edges
);
2193 cfg_layout_finalize();
2197 gate_handle_reorder_blocks (void)
2199 return (optimize
> 0);
2203 /* Reorder basic blocks. */
2205 rest_of_handle_reorder_blocks (void)
2208 unsigned int liveness_flags
;
2210 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2211 splitting possibly introduced more crossjumping opportunities. */
2212 liveness_flags
= (!HAVE_conditional_execution
? CLEANUP_UPDATE_LIFE
: 0);
2213 changed
= cleanup_cfg (CLEANUP_EXPENSIVE
| liveness_flags
);
2215 if (flag_sched2_use_traces
&& flag_schedule_insns_after_reload
)
2217 timevar_push (TV_TRACER
);
2218 tracer (liveness_flags
);
2219 timevar_pop (TV_TRACER
);
2222 if (flag_reorder_blocks
|| flag_reorder_blocks_and_partition
)
2223 reorder_basic_blocks (liveness_flags
);
2224 if (flag_reorder_blocks
|| flag_reorder_blocks_and_partition
2225 || (flag_sched2_use_traces
&& flag_schedule_insns_after_reload
))
2226 changed
|= cleanup_cfg (CLEANUP_EXPENSIVE
| liveness_flags
);
2228 /* On conditional execution targets we can not update the life cheaply, so
2229 we deffer the updating to after both cleanups. This may lose some cases
2230 but should not be terribly bad. */
2231 if (changed
&& HAVE_conditional_execution
)
2232 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
2235 /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */
2236 insert_section_boundary_note ();
2240 struct tree_opt_pass pass_reorder_blocks
=
2243 gate_handle_reorder_blocks
, /* gate */
2244 rest_of_handle_reorder_blocks
, /* execute */
2247 0, /* static_pass_number */
2248 TV_REORDER_BLOCKS
, /* tv_id */
2249 0, /* properties_required */
2250 0, /* properties_provided */
2251 0, /* properties_destroyed */
2252 0, /* todo_flags_start */
2253 TODO_dump_func
, /* todo_flags_finish */
2258 gate_handle_partition_blocks (void)
2260 /* The optimization to partition hot/cold basic blocks into separate
2261 sections of the .o file does not work well with linkonce or with
2262 user defined section attributes. Don't call it if either case
2265 return (flag_reorder_blocks_and_partition
2266 && !DECL_ONE_ONLY (current_function_decl
)
2267 && !user_defined_section_attribute
);
2270 /* Partition hot and cold basic blocks. */
2272 rest_of_handle_partition_blocks (void)
2275 partition_hot_cold_basic_blocks ();
2276 allocate_reg_life_data ();
2277 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
2278 PROP_LOG_LINKS
| PROP_REG_INFO
| PROP_DEATH_NOTES
);
2283 struct tree_opt_pass pass_partition_blocks
=
2285 "bbpart", /* name */
2286 gate_handle_partition_blocks
, /* gate */
2287 rest_of_handle_partition_blocks
, /* execute */
2290 0, /* static_pass_number */
2291 TV_REORDER_BLOCKS
, /* tv_id */
2292 0, /* properties_required */
2293 0, /* properties_provided */
2294 0, /* properties_destroyed */
2295 0, /* todo_flags_start */
2296 TODO_dump_func
, /* todo_flags_finish */