1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This (greedy) algorithm constructs traces in several rounds.
22 The construction starts from "seeds". The seed for the first round
23 is the entry point of function. When there are more than one seed
24 that one is selected first that has the lowest key in the heap
25 (see function bb_to_key). Then the algorithm repeatedly adds the most
26 probable successor to the end of a trace. Finally it connects the traces.
28 There are two parameters: Branch Threshold and Exec Threshold.
29 If the edge to a successor of the actual basic block is lower than
30 Branch Threshold or the frequency of the successor is lower than
31 Exec Threshold the successor will be the seed in one of the next rounds.
32 Each round has these parameters lower than the previous one.
33 The last round has to have these parameters set to zero
34 so that the remaining blocks are picked up.
36 The algorithm selects the most probable successor from all unvisited
37 successors and successors that have been added to this trace.
38 The other successors (that has not been "sent" to the next round) will be
39 other seeds for this round and the secondary traces will start in them.
40 If the successor has not been visited in this trace it is added to the trace
41 (however, there is some heuristic for simple branches).
42 If the successor has been visited in this trace the loop has been found.
43 If the loop has many iterations the loop is rotated so that the
44 source block of the most probable edge going out from the loop
45 is the last block of the trace.
46 If the loop has few iterations and there is no edge from the last block of
47 the loop going out from loop the loop header is duplicated.
48 Finally, the construction of the trace is terminated.
50 When connecting traces it first checks whether there is an edge from the
51 last block of one trace to the first block of another trace.
52 When there are still some unconnected traces it checks whether there exists
53 a basic block BB such that BB is a successor of the last bb of one trace
54 and BB is a predecessor of the first block of another trace. In this case,
55 BB is duplicated and the traces are connected through this duplicate.
56 The rest of traces are simply connected so there will be a jump to the
57 beginning of the rest of trace.
62 "Software Trace Cache"
63 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
64 http://citeseer.nj.nec.com/15361.html
70 #include "coretypes.h"
77 #include "cfglayout.h"
85 #include "diagnostic-core.h"
86 #include "toplev.h" /* user_defined_section_attribute */
87 #include "tree-pass.h"
89 #include "bb-reorder.h"
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 struct target_bb_reorder default_target_bb_reorder
;
106 #if SWITCHABLE_TARGET
107 struct target_bb_reorder
*this_target_bb_reorder
= &default_target_bb_reorder
;
110 #define uncond_jump_length \
111 (this_target_bb_reorder->x_uncond_jump_length)
113 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
114 static int branch_threshold
[N_ROUNDS
] = {400, 200, 100, 0, 0};
116 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
117 static int exec_threshold
[N_ROUNDS
] = {500, 200, 50, 0, 0};
119 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
120 block the edge destination is not duplicated while connecting traces. */
121 #define DUPLICATION_THRESHOLD 100
123 /* Structure to hold needed information for each basic block. */
124 typedef struct bbro_basic_block_data_def
126 /* Which trace is the bb start of (-1 means it is not a start of a trace). */
129 /* Which trace is the bb end of (-1 means it is not an end of a trace). */
132 /* Which trace is the bb in? */
135 /* Which heap is BB in (if any)? */
138 /* Which heap node is BB in (if any)? */
140 } bbro_basic_block_data
;
142 /* The current size of the following dynamic array. */
143 static int array_size
;
145 /* The array which holds needed information for basic blocks. */
146 static bbro_basic_block_data
*bbd
;
148 /* To avoid frequent reallocation the size of arrays is greater than needed,
149 the number of elements is (not less than) 1.25 * size_wanted. */
150 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
152 /* Free the memory and set the pointer to NULL. */
153 #define FREE(P) (gcc_assert (P), free (P), P = 0)
155 /* Structure for holding information about a trace. */
158 /* First and last basic block of the trace. */
159 basic_block first
, last
;
161 /* The round of the STC creation which this trace was found in. */
164 /* The length (i.e. the number of basic blocks) of the trace. */
168 /* Maximum frequency and count of one of the entry blocks. */
169 static int max_entry_frequency
;
170 static gcov_type max_entry_count
;
172 /* Local function prototypes. */
173 static void find_traces (int *, struct trace
*);
174 static basic_block
rotate_loop (edge
, struct trace
*, int);
175 static void mark_bb_visited (basic_block
, int);
176 static void find_traces_1_round (int, int, gcov_type
, struct trace
*, int *,
177 int, fibheap_t
*, int);
178 static basic_block
copy_bb (basic_block
, edge
, basic_block
, int);
179 static fibheapkey_t
bb_to_key (basic_block
);
180 static bool better_edge_p (const_basic_block
, const_edge
, int, int, int, int, const_edge
);
181 static void connect_traces (int, struct trace
*);
182 static bool copy_bb_p (const_basic_block
, int);
183 static int get_uncond_jump_length (void);
184 static bool push_to_next_round_p (const_basic_block
, int, int, int, gcov_type
);
186 /* Check to see if bb should be pushed into the next round of trace
187 collections or not. Reasons for pushing the block forward are 1).
188 If the block is cold, we are doing partitioning, and there will be
189 another round (cold partition blocks are not supposed to be
190 collected into traces until the very last round); or 2). There will
191 be another round, and the basic block is not "hot enough" for the
192 current round of trace collection. */
195 push_to_next_round_p (const_basic_block bb
, int round
, int number_of_rounds
,
196 int exec_th
, gcov_type count_th
)
198 bool there_exists_another_round
;
199 bool block_not_hot_enough
;
201 there_exists_another_round
= round
< number_of_rounds
- 1;
203 block_not_hot_enough
= (bb
->frequency
< exec_th
204 || bb
->count
< count_th
205 || probably_never_executed_bb_p (bb
));
207 if (there_exists_another_round
208 && block_not_hot_enough
)
214 /* Find the traces for Software Trace Cache. Chain each trace through
215 RBI()->next. Store the number of traces to N_TRACES and description of
219 find_traces (int *n_traces
, struct trace
*traces
)
222 int number_of_rounds
;
227 /* Add one extra round of trace collection when partitioning hot/cold
228 basic blocks into separate sections. The last round is for all the
229 cold blocks (and ONLY the cold blocks). */
231 number_of_rounds
= N_ROUNDS
- 1;
233 /* Insert entry points of function into heap. */
234 heap
= fibheap_new ();
235 max_entry_frequency
= 0;
237 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
239 bbd
[e
->dest
->index
].heap
= heap
;
240 bbd
[e
->dest
->index
].node
= fibheap_insert (heap
, bb_to_key (e
->dest
),
242 if (e
->dest
->frequency
> max_entry_frequency
)
243 max_entry_frequency
= e
->dest
->frequency
;
244 if (e
->dest
->count
> max_entry_count
)
245 max_entry_count
= e
->dest
->count
;
248 /* Find the traces. */
249 for (i
= 0; i
< number_of_rounds
; i
++)
251 gcov_type count_threshold
;
254 fprintf (dump_file
, "STC - round %d\n", i
+ 1);
256 if (max_entry_count
< INT_MAX
/ 1000)
257 count_threshold
= max_entry_count
* exec_threshold
[i
] / 1000;
259 count_threshold
= max_entry_count
/ 1000 * exec_threshold
[i
];
261 find_traces_1_round (REG_BR_PROB_BASE
* branch_threshold
[i
] / 1000,
262 max_entry_frequency
* exec_threshold
[i
] / 1000,
263 count_threshold
, traces
, n_traces
, i
, &heap
,
266 fibheap_delete (heap
);
270 for (i
= 0; i
< *n_traces
; i
++)
273 fprintf (dump_file
, "Trace %d (round %d): ", i
+ 1,
274 traces
[i
].round
+ 1);
275 for (bb
= traces
[i
].first
; bb
!= traces
[i
].last
; bb
= (basic_block
) bb
->aux
)
276 fprintf (dump_file
, "%d [%d] ", bb
->index
, bb
->frequency
);
277 fprintf (dump_file
, "%d [%d]\n", bb
->index
, bb
->frequency
);
283 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
284 (with sequential number TRACE_N). */
287 rotate_loop (edge back_edge
, struct trace
*trace
, int trace_n
)
291 /* Information about the best end (end after rotation) of the loop. */
292 basic_block best_bb
= NULL
;
293 edge best_edge
= NULL
;
295 gcov_type best_count
= -1;
296 /* The best edge is preferred when its destination is not visited yet
297 or is a start block of some trace. */
298 bool is_preferred
= false;
300 /* Find the most frequent edge that goes out from current trace. */
301 bb
= back_edge
->dest
;
307 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
308 if (e
->dest
!= EXIT_BLOCK_PTR
309 && e
->dest
->il
.rtl
->visited
!= trace_n
310 && (e
->flags
& EDGE_CAN_FALLTHRU
)
311 && !(e
->flags
& EDGE_COMPLEX
))
315 /* The best edge is preferred. */
316 if (!e
->dest
->il
.rtl
->visited
317 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
319 /* The current edge E is also preferred. */
320 int freq
= EDGE_FREQUENCY (e
);
321 if (freq
> best_freq
|| e
->count
> best_count
)
324 best_count
= e
->count
;
332 if (!e
->dest
->il
.rtl
->visited
333 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
335 /* The current edge E is preferred. */
337 best_freq
= EDGE_FREQUENCY (e
);
338 best_count
= e
->count
;
344 int freq
= EDGE_FREQUENCY (e
);
345 if (!best_edge
|| freq
> best_freq
|| e
->count
> best_count
)
348 best_count
= e
->count
;
355 bb
= (basic_block
) bb
->aux
;
357 while (bb
!= back_edge
->dest
);
361 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
363 if (back_edge
->dest
== trace
->first
)
365 trace
->first
= (basic_block
) best_bb
->aux
;
371 for (prev_bb
= trace
->first
;
372 prev_bb
->aux
!= back_edge
->dest
;
373 prev_bb
= (basic_block
) prev_bb
->aux
)
375 prev_bb
->aux
= best_bb
->aux
;
377 /* Try to get rid of uncond jump to cond jump. */
378 if (single_succ_p (prev_bb
))
380 basic_block header
= single_succ (prev_bb
);
382 /* Duplicate HEADER if it is a small block containing cond jump
384 if (any_condjump_p (BB_END (header
)) && copy_bb_p (header
, 0)
385 && !find_reg_note (BB_END (header
), REG_CROSSING_JUMP
,
387 copy_bb (header
, single_succ_edge (prev_bb
), prev_bb
, trace_n
);
393 /* We have not found suitable loop tail so do no rotation. */
394 best_bb
= back_edge
->src
;
400 /* This function marks BB that it was visited in trace number TRACE. */
403 mark_bb_visited (basic_block bb
, int trace
)
405 bb
->il
.rtl
->visited
= trace
;
406 if (bbd
[bb
->index
].heap
)
408 fibheap_delete_node (bbd
[bb
->index
].heap
, bbd
[bb
->index
].node
);
409 bbd
[bb
->index
].heap
= NULL
;
410 bbd
[bb
->index
].node
= NULL
;
414 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
415 not include basic blocks their probability is lower than BRANCH_TH or their
416 frequency is lower than EXEC_TH into traces (or count is lower than
417 COUNT_TH). It stores the new traces into TRACES and modifies the number of
418 traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
419 expects that starting basic blocks are in *HEAP and at the end it deletes
420 *HEAP and stores starting points for the next round into new *HEAP. */
423 find_traces_1_round (int branch_th
, int exec_th
, gcov_type count_th
,
424 struct trace
*traces
, int *n_traces
, int round
,
425 fibheap_t
*heap
, int number_of_rounds
)
427 /* Heap for discarded basic blocks which are possible starting points for
429 fibheap_t new_heap
= fibheap_new ();
431 while (!fibheap_empty (*heap
))
439 bb
= (basic_block
) fibheap_extract_min (*heap
);
440 bbd
[bb
->index
].heap
= NULL
;
441 bbd
[bb
->index
].node
= NULL
;
444 fprintf (dump_file
, "Getting bb %d\n", bb
->index
);
446 /* If the BB's frequency is too low send BB to the next round. When
447 partitioning hot/cold blocks into separate sections, make sure all
448 the cold blocks (and ONLY the cold blocks) go into the (extra) final
451 if (push_to_next_round_p (bb
, round
, number_of_rounds
, exec_th
,
454 int key
= bb_to_key (bb
);
455 bbd
[bb
->index
].heap
= new_heap
;
456 bbd
[bb
->index
].node
= fibheap_insert (new_heap
, key
, bb
);
460 " Possible start point of next round: %d (key: %d)\n",
465 trace
= traces
+ *n_traces
;
467 trace
->round
= round
;
469 bbd
[bb
->index
].in_trace
= *n_traces
;
477 /* The probability and frequency of the best edge. */
478 int best_prob
= INT_MIN
/ 2;
479 int best_freq
= INT_MIN
/ 2;
482 mark_bb_visited (bb
, *n_traces
);
486 fprintf (dump_file
, "Basic block %d was visited in trace %d\n",
487 bb
->index
, *n_traces
- 1);
489 ends_in_call
= block_ends_with_call_p (bb
);
491 /* Select the successor that will be placed after BB. */
492 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
494 gcc_assert (!(e
->flags
& EDGE_FAKE
));
496 if (e
->dest
== EXIT_BLOCK_PTR
)
499 if (e
->dest
->il
.rtl
->visited
500 && e
->dest
->il
.rtl
->visited
!= *n_traces
)
503 if (BB_PARTITION (e
->dest
) != BB_PARTITION (bb
))
506 prob
= e
->probability
;
507 freq
= e
->dest
->frequency
;
509 /* The only sensible preference for a call instruction is the
510 fallthru edge. Don't bother selecting anything else. */
513 if (e
->flags
& EDGE_CAN_FALLTHRU
)
522 /* Edge that cannot be fallthru or improbable or infrequent
523 successor (i.e. it is unsuitable successor). */
524 if (!(e
->flags
& EDGE_CAN_FALLTHRU
) || (e
->flags
& EDGE_COMPLEX
)
525 || prob
< branch_th
|| EDGE_FREQUENCY (e
) < exec_th
526 || e
->count
< count_th
)
529 /* If partitioning hot/cold basic blocks, don't consider edges
530 that cross section boundaries. */
532 if (better_edge_p (bb
, e
, prob
, freq
, best_prob
, best_freq
,
541 /* If the best destination has multiple predecessors, and can be
542 duplicated cheaper than a jump, don't allow it to be added
543 to a trace. We'll duplicate it when connecting traces. */
544 if (best_edge
&& EDGE_COUNT (best_edge
->dest
->preds
) >= 2
545 && copy_bb_p (best_edge
->dest
, 0))
548 /* Add all non-selected successors to the heaps. */
549 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
552 || e
->dest
== EXIT_BLOCK_PTR
553 || e
->dest
->il
.rtl
->visited
)
556 key
= bb_to_key (e
->dest
);
558 if (bbd
[e
->dest
->index
].heap
)
560 /* E->DEST is already in some heap. */
561 if (key
!= bbd
[e
->dest
->index
].node
->key
)
566 "Changing key for bb %d from %ld to %ld.\n",
568 (long) bbd
[e
->dest
->index
].node
->key
,
571 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
572 bbd
[e
->dest
->index
].node
, key
);
577 fibheap_t which_heap
= *heap
;
579 prob
= e
->probability
;
580 freq
= EDGE_FREQUENCY (e
);
582 if (!(e
->flags
& EDGE_CAN_FALLTHRU
)
583 || (e
->flags
& EDGE_COMPLEX
)
584 || prob
< branch_th
|| freq
< exec_th
585 || e
->count
< count_th
)
587 /* When partitioning hot/cold basic blocks, make sure
588 the cold blocks (and only the cold blocks) all get
589 pushed to the last round of trace collection. */
591 if (push_to_next_round_p (e
->dest
, round
,
594 which_heap
= new_heap
;
597 bbd
[e
->dest
->index
].heap
= which_heap
;
598 bbd
[e
->dest
->index
].node
= fibheap_insert (which_heap
,
604 " Possible start of %s round: %d (key: %ld)\n",
605 (which_heap
== new_heap
) ? "next" : "this",
606 e
->dest
->index
, (long) key
);
612 if (best_edge
) /* Suitable successor was found. */
614 if (best_edge
->dest
->il
.rtl
->visited
== *n_traces
)
616 /* We do nothing with one basic block loops. */
617 if (best_edge
->dest
!= bb
)
619 if (EDGE_FREQUENCY (best_edge
)
620 > 4 * best_edge
->dest
->frequency
/ 5)
622 /* The loop has at least 4 iterations. If the loop
623 header is not the first block of the function
624 we can rotate the loop. */
626 if (best_edge
->dest
!= ENTRY_BLOCK_PTR
->next_bb
)
631 "Rotating loop %d - %d\n",
632 best_edge
->dest
->index
, bb
->index
);
634 bb
->aux
= best_edge
->dest
;
635 bbd
[best_edge
->dest
->index
].in_trace
=
637 bb
= rotate_loop (best_edge
, trace
, *n_traces
);
642 /* The loop has less than 4 iterations. */
644 if (single_succ_p (bb
)
645 && copy_bb_p (best_edge
->dest
,
646 optimize_edge_for_speed_p (best_edge
)))
648 bb
= copy_bb (best_edge
->dest
, best_edge
, bb
,
655 /* Terminate the trace. */
660 /* Check for a situation
669 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
670 >= EDGE_FREQUENCY (AC).
671 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
672 Best ordering is then A B C.
674 This situation is created for example by:
681 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
683 && (e
->flags
& EDGE_CAN_FALLTHRU
)
684 && !(e
->flags
& EDGE_COMPLEX
)
685 && !e
->dest
->il
.rtl
->visited
686 && single_pred_p (e
->dest
)
687 && !(e
->flags
& EDGE_CROSSING
)
688 && single_succ_p (e
->dest
)
689 && (single_succ_edge (e
->dest
)->flags
691 && !(single_succ_edge (e
->dest
)->flags
& EDGE_COMPLEX
)
692 && single_succ (e
->dest
) == best_edge
->dest
693 && 2 * e
->dest
->frequency
>= EDGE_FREQUENCY (best_edge
))
697 fprintf (dump_file
, "Selecting BB %d\n",
698 best_edge
->dest
->index
);
702 bb
->aux
= best_edge
->dest
;
703 bbd
[best_edge
->dest
->index
].in_trace
= (*n_traces
) - 1;
704 bb
= best_edge
->dest
;
710 bbd
[trace
->first
->index
].start_of_trace
= *n_traces
- 1;
711 bbd
[trace
->last
->index
].end_of_trace
= *n_traces
- 1;
713 /* The trace is terminated so we have to recount the keys in heap
714 (some block can have a lower key because now one of its predecessors
715 is an end of the trace). */
716 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
718 if (e
->dest
== EXIT_BLOCK_PTR
719 || e
->dest
->il
.rtl
->visited
)
722 if (bbd
[e
->dest
->index
].heap
)
724 key
= bb_to_key (e
->dest
);
725 if (key
!= bbd
[e
->dest
->index
].node
->key
)
730 "Changing key for bb %d from %ld to %ld.\n",
732 (long) bbd
[e
->dest
->index
].node
->key
, key
);
734 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
735 bbd
[e
->dest
->index
].node
,
742 fibheap_delete (*heap
);
744 /* "Return" the new heap. */
748 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
749 it to trace after BB, mark OLD_BB visited and update pass' data structures
750 (TRACE is a number of trace which OLD_BB is duplicated to). */
753 copy_bb (basic_block old_bb
, edge e
, basic_block bb
, int trace
)
757 new_bb
= duplicate_block (old_bb
, e
, bb
);
758 BB_COPY_PARTITION (new_bb
, old_bb
);
760 gcc_assert (e
->dest
== new_bb
);
761 gcc_assert (!e
->dest
->il
.rtl
->visited
);
765 "Duplicated bb %d (created bb %d)\n",
766 old_bb
->index
, new_bb
->index
);
767 new_bb
->il
.rtl
->visited
= trace
;
768 new_bb
->aux
= bb
->aux
;
771 if (new_bb
->index
>= array_size
|| last_basic_block
> array_size
)
776 new_size
= MAX (last_basic_block
, new_bb
->index
+ 1);
777 new_size
= GET_ARRAY_SIZE (new_size
);
778 bbd
= XRESIZEVEC (bbro_basic_block_data
, bbd
, new_size
);
779 for (i
= array_size
; i
< new_size
; i
++)
781 bbd
[i
].start_of_trace
= -1;
782 bbd
[i
].in_trace
= -1;
783 bbd
[i
].end_of_trace
= -1;
787 array_size
= new_size
;
792 "Growing the dynamic array to %d elements.\n",
797 bbd
[new_bb
->index
].in_trace
= trace
;
802 /* Compute and return the key (for the heap) of the basic block BB. */
805 bb_to_key (basic_block bb
)
811 /* Do not start in probably never executed blocks. */
813 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
814 || probably_never_executed_bb_p (bb
))
817 /* Prefer blocks whose predecessor is an end of some trace
818 or whose predecessor edge is EDGE_DFS_BACK. */
819 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
821 if ((e
->src
!= ENTRY_BLOCK_PTR
&& bbd
[e
->src
->index
].end_of_trace
>= 0)
822 || (e
->flags
& EDGE_DFS_BACK
))
824 int edge_freq
= EDGE_FREQUENCY (e
);
826 if (edge_freq
> priority
)
827 priority
= edge_freq
;
832 /* The block with priority should have significantly lower key. */
833 return -(100 * BB_FREQ_MAX
+ 100 * priority
+ bb
->frequency
);
834 return -bb
->frequency
;
837 /* Return true when the edge E from basic block BB is better than the temporary
838 best edge (details are in function). The probability of edge E is PROB. The
839 frequency of the successor is FREQ. The current best probability is
840 BEST_PROB, the best frequency is BEST_FREQ.
841 The edge is considered to be equivalent when PROB does not differ much from
842 BEST_PROB; similarly for frequency. */
845 better_edge_p (const_basic_block bb
, const_edge e
, int prob
, int freq
, int best_prob
,
846 int best_freq
, const_edge cur_best_edge
)
850 /* The BEST_* values do not have to be best, but can be a bit smaller than
852 int diff_prob
= best_prob
/ 10;
853 int diff_freq
= best_freq
/ 10;
855 if (prob
> best_prob
+ diff_prob
)
856 /* The edge has higher probability than the temporary best edge. */
857 is_better_edge
= true;
858 else if (prob
< best_prob
- diff_prob
)
859 /* The edge has lower probability than the temporary best edge. */
860 is_better_edge
= false;
861 else if (freq
< best_freq
- diff_freq
)
862 /* The edge and the temporary best edge have almost equivalent
863 probabilities. The higher frequency of a successor now means
864 that there is another edge going into that successor.
865 This successor has lower frequency so it is better. */
866 is_better_edge
= true;
867 else if (freq
> best_freq
+ diff_freq
)
868 /* This successor has higher frequency so it is worse. */
869 is_better_edge
= false;
870 else if (e
->dest
->prev_bb
== bb
)
871 /* The edges have equivalent probabilities and the successors
872 have equivalent frequencies. Select the previous successor. */
873 is_better_edge
= true;
875 is_better_edge
= false;
877 /* If we are doing hot/cold partitioning, make sure that we always favor
878 non-crossing edges over crossing edges. */
881 && flag_reorder_blocks_and_partition
883 && (cur_best_edge
->flags
& EDGE_CROSSING
)
884 && !(e
->flags
& EDGE_CROSSING
))
885 is_better_edge
= true;
887 return is_better_edge
;
890 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
893 connect_traces (int n_traces
, struct trace
*traces
)
900 int current_partition
;
902 gcov_type count_threshold
;
904 freq_threshold
= max_entry_frequency
* DUPLICATION_THRESHOLD
/ 1000;
905 if (max_entry_count
< INT_MAX
/ 1000)
906 count_threshold
= max_entry_count
* DUPLICATION_THRESHOLD
/ 1000;
908 count_threshold
= max_entry_count
/ 1000 * DUPLICATION_THRESHOLD
;
910 connected
= XCNEWVEC (bool, n_traces
);
913 current_partition
= BB_PARTITION (traces
[0].first
);
916 if (flag_reorder_blocks_and_partition
)
917 for (i
= 0; i
< n_traces
&& !two_passes
; i
++)
918 if (BB_PARTITION (traces
[0].first
)
919 != BB_PARTITION (traces
[i
].first
))
922 for (i
= 0; i
< n_traces
|| (two_passes
&& current_pass
== 1) ; i
++)
931 gcc_assert (two_passes
&& current_pass
== 1);
935 if (current_partition
== BB_HOT_PARTITION
)
936 current_partition
= BB_COLD_PARTITION
;
938 current_partition
= BB_HOT_PARTITION
;
945 && BB_PARTITION (traces
[t
].first
) != current_partition
)
950 /* Find the predecessor traces. */
951 for (t2
= t
; t2
> 0;)
956 FOR_EACH_EDGE (e
, ei
, traces
[t2
].first
->preds
)
958 int si
= e
->src
->index
;
960 if (e
->src
!= ENTRY_BLOCK_PTR
961 && (e
->flags
& EDGE_CAN_FALLTHRU
)
962 && !(e
->flags
& EDGE_COMPLEX
)
963 && bbd
[si
].end_of_trace
>= 0
964 && !connected
[bbd
[si
].end_of_trace
]
965 && (BB_PARTITION (e
->src
) == current_partition
)
967 || e
->probability
> best
->probability
968 || (e
->probability
== best
->probability
969 && traces
[bbd
[si
].end_of_trace
].length
> best_len
)))
972 best_len
= traces
[bbd
[si
].end_of_trace
].length
;
977 best
->src
->aux
= best
->dest
;
978 t2
= bbd
[best
->src
->index
].end_of_trace
;
979 connected
[t2
] = true;
983 fprintf (dump_file
, "Connection: %d %d\n",
984 best
->src
->index
, best
->dest
->index
);
992 traces
[last_trace
].last
->aux
= traces
[t2
].first
;
995 /* Find the successor traces. */
998 /* Find the continuation of the chain. */
1002 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1004 int di
= e
->dest
->index
;
1006 if (e
->dest
!= EXIT_BLOCK_PTR
1007 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1008 && !(e
->flags
& EDGE_COMPLEX
)
1009 && bbd
[di
].start_of_trace
>= 0
1010 && !connected
[bbd
[di
].start_of_trace
]
1011 && (BB_PARTITION (e
->dest
) == current_partition
)
1013 || e
->probability
> best
->probability
1014 || (e
->probability
== best
->probability
1015 && traces
[bbd
[di
].start_of_trace
].length
> best_len
)))
1018 best_len
= traces
[bbd
[di
].start_of_trace
].length
;
1026 fprintf (dump_file
, "Connection: %d %d\n",
1027 best
->src
->index
, best
->dest
->index
);
1029 t
= bbd
[best
->dest
->index
].start_of_trace
;
1030 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1031 connected
[t
] = true;
1036 /* Try to connect the traces by duplication of 1 block. */
1038 basic_block next_bb
= NULL
;
1039 bool try_copy
= false;
1041 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1042 if (e
->dest
!= EXIT_BLOCK_PTR
1043 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1044 && !(e
->flags
& EDGE_COMPLEX
)
1045 && (!best
|| e
->probability
> best
->probability
))
1051 /* If the destination is a start of a trace which is only
1052 one block long, then no need to search the successor
1053 blocks of the trace. Accept it. */
1054 if (bbd
[e
->dest
->index
].start_of_trace
>= 0
1055 && traces
[bbd
[e
->dest
->index
].start_of_trace
].length
1063 FOR_EACH_EDGE (e2
, ei
, e
->dest
->succs
)
1065 int di
= e2
->dest
->index
;
1067 if (e2
->dest
== EXIT_BLOCK_PTR
1068 || ((e2
->flags
& EDGE_CAN_FALLTHRU
)
1069 && !(e2
->flags
& EDGE_COMPLEX
)
1070 && bbd
[di
].start_of_trace
>= 0
1071 && !connected
[bbd
[di
].start_of_trace
]
1072 && (BB_PARTITION (e2
->dest
) == current_partition
)
1073 && (EDGE_FREQUENCY (e2
) >= freq_threshold
)
1074 && (e2
->count
>= count_threshold
)
1076 || e2
->probability
> best2
->probability
1077 || (e2
->probability
== best2
->probability
1078 && traces
[bbd
[di
].start_of_trace
].length
1083 if (e2
->dest
!= EXIT_BLOCK_PTR
)
1084 best2_len
= traces
[bbd
[di
].start_of_trace
].length
;
1086 best2_len
= INT_MAX
;
1093 if (flag_reorder_blocks_and_partition
)
1096 /* Copy tiny blocks always; copy larger blocks only when the
1097 edge is traversed frequently enough. */
1099 && copy_bb_p (best
->dest
,
1100 optimize_edge_for_speed_p (best
)
1101 && EDGE_FREQUENCY (best
) >= freq_threshold
1102 && best
->count
>= count_threshold
))
1108 fprintf (dump_file
, "Connection: %d %d ",
1109 traces
[t
].last
->index
, best
->dest
->index
);
1111 fputc ('\n', dump_file
);
1112 else if (next_bb
== EXIT_BLOCK_PTR
)
1113 fprintf (dump_file
, "exit\n");
1115 fprintf (dump_file
, "%d\n", next_bb
->index
);
1118 new_bb
= copy_bb (best
->dest
, best
, traces
[t
].last
, t
);
1119 traces
[t
].last
= new_bb
;
1120 if (next_bb
&& next_bb
!= EXIT_BLOCK_PTR
)
1122 t
= bbd
[next_bb
->index
].start_of_trace
;
1123 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1124 connected
[t
] = true;
1128 break; /* Stop finding the successor traces. */
1131 break; /* Stop finding the successor traces. */
1140 fprintf (dump_file
, "Final order:\n");
1141 for (bb
= traces
[0].first
; bb
; bb
= (basic_block
) bb
->aux
)
1142 fprintf (dump_file
, "%d ", bb
->index
);
1143 fprintf (dump_file
, "\n");
1150 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1151 when code size is allowed to grow by duplication. */
1154 copy_bb_p (const_basic_block bb
, int code_may_grow
)
1157 int max_size
= uncond_jump_length
;
1162 if (EDGE_COUNT (bb
->preds
) < 2)
1164 if (!can_duplicate_block_p (bb
))
1167 /* Avoid duplicating blocks which have many successors (PR/13430). */
1168 if (EDGE_COUNT (bb
->succs
) > 8)
1171 if (code_may_grow
&& optimize_bb_for_speed_p (bb
))
1172 max_size
*= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS
);
1174 FOR_BB_INSNS (bb
, insn
)
1177 size
+= get_attr_min_length (insn
);
1180 if (size
<= max_size
)
1186 "Block %d can't be copied because its size = %d.\n",
1193 /* Return the length of unconditional jump instruction. */
1196 get_uncond_jump_length (void)
1201 label
= emit_label_before (gen_label_rtx (), get_insns ());
1202 jump
= emit_jump_insn (gen_jump (label
));
1204 length
= get_attr_min_length (jump
);
1207 delete_insn (label
);
1211 /* Find the basic blocks that are rarely executed and need to be moved to
1212 a separate section of the .o file (to cut down on paging and improve
1213 cache locality). Return a vector of all edges that cross. */
1215 static VEC(edge
, heap
) *
1216 find_rarely_executed_basic_blocks_and_crossing_edges (void)
1218 VEC(edge
, heap
) *crossing_edges
= NULL
;
1223 /* Mark which partition (hot/cold) each basic block belongs in. */
1227 if (probably_never_executed_bb_p (bb
))
1228 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
1230 BB_SET_PARTITION (bb
, BB_HOT_PARTITION
);
1233 /* Mark every edge that crosses between sections. */
1236 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1238 if (e
->src
!= ENTRY_BLOCK_PTR
1239 && e
->dest
!= EXIT_BLOCK_PTR
1240 && BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1242 e
->flags
|= EDGE_CROSSING
;
1243 VEC_safe_push (edge
, heap
, crossing_edges
, e
);
1246 e
->flags
&= ~EDGE_CROSSING
;
1249 return crossing_edges
;
1252 /* Emit a barrier into the footer of BB. */
1255 emit_barrier_after_bb (basic_block bb
)
1257 rtx barrier
= emit_barrier_after (BB_END (bb
));
1258 bb
->il
.rtl
->footer
= unlink_insn_chain (barrier
, barrier
);
1261 /* If any destination of a crossing edge does not have a label, add label;
1262 Convert any easy fall-through crossing edges to unconditional jumps. */
1265 add_labels_and_missing_jumps (VEC(edge
, heap
) *crossing_edges
)
1270 FOR_EACH_VEC_ELT (edge
, crossing_edges
, i
, e
)
1272 basic_block src
= e
->src
;
1273 basic_block dest
= e
->dest
;
1274 rtx label
, new_jump
;
1276 if (dest
== EXIT_BLOCK_PTR
)
1279 /* Make sure dest has a label. */
1280 label
= block_label (dest
);
1282 /* Nothing to do for non-fallthru edges. */
1283 if (src
== ENTRY_BLOCK_PTR
)
1285 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1288 /* If the block does not end with a control flow insn, then we
1289 can trivially add a jump to the end to fixup the crossing.
1290 Otherwise the jump will have to go in a new bb, which will
1291 be handled by fix_up_fall_thru_edges function. */
1292 if (control_flow_insn_p (BB_END (src
)))
1295 /* Make sure there's only one successor. */
1296 gcc_assert (single_succ_p (src
));
1298 new_jump
= emit_jump_insn_after (gen_jump (label
), BB_END (src
));
1299 BB_END (src
) = new_jump
;
1300 JUMP_LABEL (new_jump
) = label
;
1301 LABEL_NUSES (label
) += 1;
1303 emit_barrier_after_bb (src
);
1305 /* Mark edge as non-fallthru. */
1306 e
->flags
&= ~EDGE_FALLTHRU
;
1310 /* Find any bb's where the fall-through edge is a crossing edge (note that
1311 these bb's must also contain a conditional jump or end with a call
1312 instruction; we've already dealt with fall-through edges for blocks
1313 that didn't have a conditional jump or didn't end with call instruction
1314 in the call to add_labels_and_missing_jumps). Convert the fall-through
1315 edge to non-crossing edge by inserting a new bb to fall-through into.
1316 The new bb will contain an unconditional jump (crossing edge) to the
1317 original fall through destination. */
1320 fix_up_fall_thru_edges (void)
1327 edge cond_jump
= NULL
;
1329 bool cond_jump_crosses
;
1332 rtx fall_thru_label
;
1334 FOR_EACH_BB (cur_bb
)
1337 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1338 succ1
= EDGE_SUCC (cur_bb
, 0);
1342 if (EDGE_COUNT (cur_bb
->succs
) > 1)
1343 succ2
= EDGE_SUCC (cur_bb
, 1);
1347 /* Find the fall-through edge. */
1350 && (succ1
->flags
& EDGE_FALLTHRU
))
1356 && (succ2
->flags
& EDGE_FALLTHRU
))
1362 && (block_ends_with_call_p (cur_bb
)
1363 || can_throw_internal (BB_END (cur_bb
))))
1368 /* Find EDGE_CAN_FALLTHRU edge. */
1369 FOR_EACH_EDGE (e
, ei
, cur_bb
->succs
)
1370 if (e
->flags
& EDGE_CAN_FALLTHRU
)
1377 if (fall_thru
&& (fall_thru
->dest
!= EXIT_BLOCK_PTR
))
1379 /* Check to see if the fall-thru edge is a crossing edge. */
1381 if (fall_thru
->flags
& EDGE_CROSSING
)
1383 /* The fall_thru edge crosses; now check the cond jump edge, if
1386 cond_jump_crosses
= true;
1388 old_jump
= BB_END (cur_bb
);
1390 /* Find the jump instruction, if there is one. */
1394 if (!(cond_jump
->flags
& EDGE_CROSSING
))
1395 cond_jump_crosses
= false;
1397 /* We know the fall-thru edge crosses; if the cond
1398 jump edge does NOT cross, and its destination is the
1399 next block in the bb order, invert the jump
1400 (i.e. fix it so the fall thru does not cross and
1401 the cond jump does). */
1403 if (!cond_jump_crosses
1404 && cur_bb
->aux
== cond_jump
->dest
)
1406 /* Find label in fall_thru block. We've already added
1407 any missing labels, so there must be one. */
1409 fall_thru_label
= block_label (fall_thru
->dest
);
1411 if (old_jump
&& JUMP_P (old_jump
) && fall_thru_label
)
1412 invert_worked
= invert_jump (old_jump
,
1416 fall_thru
->flags
&= ~EDGE_FALLTHRU
;
1417 cond_jump
->flags
|= EDGE_FALLTHRU
;
1418 update_br_prob_note (cur_bb
);
1420 fall_thru
= cond_jump
;
1422 cond_jump
->flags
|= EDGE_CROSSING
;
1423 fall_thru
->flags
&= ~EDGE_CROSSING
;
1428 if (cond_jump_crosses
|| !invert_worked
)
1430 /* This is the case where both edges out of the basic
1431 block are crossing edges. Here we will fix up the
1432 fall through edge. The jump edge will be taken care
1433 of later. The EDGE_CROSSING flag of fall_thru edge
1434 is unset before the call to force_nonfallthru
1435 function because if a new basic-block is created
1436 this edge remains in the current section boundary
1437 while the edge between new_bb and the fall_thru->dest
1438 becomes EDGE_CROSSING. */
1440 fall_thru
->flags
&= ~EDGE_CROSSING
;
1441 new_bb
= force_nonfallthru (fall_thru
);
1445 new_bb
->aux
= cur_bb
->aux
;
1446 cur_bb
->aux
= new_bb
;
1448 /* Make sure new fall-through bb is in same
1449 partition as bb it's falling through from. */
1451 BB_COPY_PARTITION (new_bb
, cur_bb
);
1452 single_succ_edge (new_bb
)->flags
|= EDGE_CROSSING
;
1456 /* If a new basic-block was not created; restore
1457 the EDGE_CROSSING flag. */
1458 fall_thru
->flags
|= EDGE_CROSSING
;
1461 /* Add barrier after new jump */
1462 emit_barrier_after_bb (new_bb
? new_bb
: cur_bb
);
1469 /* This function checks the destination block of a "crossing jump" to
1470 see if it has any crossing predecessors that begin with a code label
1471 and end with an unconditional jump. If so, it returns that predecessor
1472 block. (This is to avoid creating lots of new basic blocks that all
1473 contain unconditional jumps to the same destination). */
1476 find_jump_block (basic_block jump_dest
)
1478 basic_block source_bb
= NULL
;
1483 FOR_EACH_EDGE (e
, ei
, jump_dest
->preds
)
1484 if (e
->flags
& EDGE_CROSSING
)
1486 basic_block src
= e
->src
;
1488 /* Check each predecessor to see if it has a label, and contains
1489 only one executable instruction, which is an unconditional jump.
1490 If so, we can use it. */
1492 if (LABEL_P (BB_HEAD (src
)))
1493 for (insn
= BB_HEAD (src
);
1494 !INSN_P (insn
) && insn
!= NEXT_INSN (BB_END (src
));
1495 insn
= NEXT_INSN (insn
))
1498 && insn
== BB_END (src
)
1500 && !any_condjump_p (insn
))
1514 /* Find all BB's with conditional jumps that are crossing edges;
1515 insert a new bb and make the conditional jump branch to the new
1516 bb instead (make the new bb same color so conditional branch won't
1517 be a 'crossing' edge). Insert an unconditional jump from the
1518 new bb to the original destination of the conditional jump. */
1521 fix_crossing_conditional_branches (void)
1532 rtx old_label
= NULL_RTX
;
1535 FOR_EACH_BB (cur_bb
)
1537 crossing_edge
= NULL
;
1538 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1539 succ1
= EDGE_SUCC (cur_bb
, 0);
1543 if (EDGE_COUNT (cur_bb
->succs
) > 1)
1544 succ2
= EDGE_SUCC (cur_bb
, 1);
1548 /* We already took care of fall-through edges, so only one successor
1549 can be a crossing edge. */
1551 if (succ1
&& (succ1
->flags
& EDGE_CROSSING
))
1552 crossing_edge
= succ1
;
1553 else if (succ2
&& (succ2
->flags
& EDGE_CROSSING
))
1554 crossing_edge
= succ2
;
1558 old_jump
= BB_END (cur_bb
);
1560 /* Check to make sure the jump instruction is a
1561 conditional jump. */
1565 if (any_condjump_p (old_jump
))
1567 if (GET_CODE (PATTERN (old_jump
)) == SET
)
1568 set_src
= SET_SRC (PATTERN (old_jump
));
1569 else if (GET_CODE (PATTERN (old_jump
)) == PARALLEL
)
1571 set_src
= XVECEXP (PATTERN (old_jump
), 0,0);
1572 if (GET_CODE (set_src
) == SET
)
1573 set_src
= SET_SRC (set_src
);
1579 if (set_src
&& (GET_CODE (set_src
) == IF_THEN_ELSE
))
1581 if (GET_CODE (XEXP (set_src
, 1)) == PC
)
1582 old_label
= XEXP (set_src
, 2);
1583 else if (GET_CODE (XEXP (set_src
, 2)) == PC
)
1584 old_label
= XEXP (set_src
, 1);
1586 /* Check to see if new bb for jumping to that dest has
1587 already been created; if so, use it; if not, create
1590 new_bb
= find_jump_block (crossing_edge
->dest
);
1593 new_label
= block_label (new_bb
);
1596 basic_block last_bb
;
1599 /* Create new basic block to be dest for
1600 conditional jump. */
1602 /* Put appropriate instructions in new bb. */
1604 new_label
= gen_label_rtx ();
1605 emit_label (new_label
);
1606 BB_HEAD (new_bb
) = new_label
;
1608 gcc_assert (GET_CODE (old_label
) == LABEL_REF
);
1609 old_label
= JUMP_LABEL (old_jump
);
1610 new_jump
= emit_jump_insn (gen_jump (old_label
));
1611 JUMP_LABEL (new_jump
) = old_label
;
1613 last_bb
= EXIT_BLOCK_PTR
->prev_bb
;
1614 new_bb
= create_basic_block (new_label
, new_jump
, last_bb
);
1615 new_bb
->aux
= last_bb
->aux
;
1616 last_bb
->aux
= new_bb
;
1618 emit_barrier_after_bb (new_bb
);
1620 /* Make sure new bb is in same partition as source
1621 of conditional branch. */
1622 BB_COPY_PARTITION (new_bb
, cur_bb
);
1625 /* Make old jump branch to new bb. */
1627 redirect_jump (old_jump
, new_label
, 0);
1629 /* Remove crossing_edge as predecessor of 'dest'. */
1631 dest
= crossing_edge
->dest
;
1633 redirect_edge_succ (crossing_edge
, new_bb
);
1635 /* Make a new edge from new_bb to old dest; new edge
1636 will be a successor for new_bb and a predecessor
1639 if (EDGE_COUNT (new_bb
->succs
) == 0)
1640 new_edge
= make_edge (new_bb
, dest
, 0);
1642 new_edge
= EDGE_SUCC (new_bb
, 0);
1644 crossing_edge
->flags
&= ~EDGE_CROSSING
;
1645 new_edge
->flags
|= EDGE_CROSSING
;
1651 /* Find any unconditional branches that cross between hot and cold
1652 sections. Convert them into indirect jumps instead. */
1655 fix_crossing_unconditional_branches (void)
1661 rtx indirect_jump_sequence
;
1662 rtx jump_insn
= NULL_RTX
;
1667 FOR_EACH_BB (cur_bb
)
1669 last_insn
= BB_END (cur_bb
);
1671 if (EDGE_COUNT (cur_bb
->succs
) < 1)
1674 succ
= EDGE_SUCC (cur_bb
, 0);
1676 /* Check to see if bb ends in a crossing (unconditional) jump. At
1677 this point, no crossing jumps should be conditional. */
1679 if (JUMP_P (last_insn
)
1680 && (succ
->flags
& EDGE_CROSSING
))
1684 gcc_assert (!any_condjump_p (last_insn
));
1686 /* Make sure the jump is not already an indirect or table jump. */
1688 if (!computed_jump_p (last_insn
)
1689 && !tablejump_p (last_insn
, &label2
, &table
))
1691 /* We have found a "crossing" unconditional branch. Now
1692 we must convert it to an indirect jump. First create
1693 reference of label, as target for jump. */
1695 label
= JUMP_LABEL (last_insn
);
1696 label_addr
= gen_rtx_LABEL_REF (Pmode
, label
);
1697 LABEL_NUSES (label
) += 1;
1699 /* Get a register to use for the indirect jump. */
1701 new_reg
= gen_reg_rtx (Pmode
);
1703 /* Generate indirect the jump sequence. */
1706 emit_move_insn (new_reg
, label_addr
);
1707 emit_indirect_jump (new_reg
);
1708 indirect_jump_sequence
= get_insns ();
1711 /* Make sure every instruction in the new jump sequence has
1712 its basic block set to be cur_bb. */
1714 for (cur_insn
= indirect_jump_sequence
; cur_insn
;
1715 cur_insn
= NEXT_INSN (cur_insn
))
1717 if (!BARRIER_P (cur_insn
))
1718 BLOCK_FOR_INSN (cur_insn
) = cur_bb
;
1719 if (JUMP_P (cur_insn
))
1720 jump_insn
= cur_insn
;
1723 /* Insert the new (indirect) jump sequence immediately before
1724 the unconditional jump, then delete the unconditional jump. */
1726 emit_insn_before (indirect_jump_sequence
, last_insn
);
1727 delete_insn (last_insn
);
1729 /* Make BB_END for cur_bb be the jump instruction (NOT the
1730 barrier instruction at the end of the sequence...). */
1732 BB_END (cur_bb
) = jump_insn
;
1738 /* Add REG_CROSSING_JUMP note to all crossing jump insns. */
1741 add_reg_crossing_jump_notes (void)
1748 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1749 if ((e
->flags
& EDGE_CROSSING
)
1750 && JUMP_P (BB_END (e
->src
)))
1751 add_reg_note (BB_END (e
->src
), REG_CROSSING_JUMP
, NULL_RTX
);
1754 /* Verify, in the basic block chain, that there is at most one switch
1755 between hot/cold partitions. This is modelled on
1756 rtl_verify_flow_info_1, but it cannot go inside that function
1757 because this condition will not be true until after
1758 reorder_basic_blocks is called. */
1761 verify_hot_cold_block_grouping (void)
1765 bool switched_sections
= false;
1766 int current_partition
= 0;
1770 if (!current_partition
)
1771 current_partition
= BB_PARTITION (bb
);
1772 if (BB_PARTITION (bb
) != current_partition
)
1774 if (switched_sections
)
1776 error ("multiple hot/cold transitions found (bb %i)",
1782 switched_sections
= true;
1783 current_partition
= BB_PARTITION (bb
);
1791 /* Reorder basic blocks. The main entry point to this file. FLAGS is
1792 the set of flags to pass to cfg_layout_initialize(). */
1795 reorder_basic_blocks (void)
1799 struct trace
*traces
;
1801 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
1803 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
1806 set_edge_can_fallthru_flag ();
1807 mark_dfs_back_edges ();
1809 /* We are estimating the length of uncond jump insn only once since the code
1810 for getting the insn length always returns the minimal length now. */
1811 if (uncond_jump_length
== 0)
1812 uncond_jump_length
= get_uncond_jump_length ();
1814 /* We need to know some information for each basic block. */
1815 array_size
= GET_ARRAY_SIZE (last_basic_block
);
1816 bbd
= XNEWVEC (bbro_basic_block_data
, array_size
);
1817 for (i
= 0; i
< array_size
; i
++)
1819 bbd
[i
].start_of_trace
= -1;
1820 bbd
[i
].in_trace
= -1;
1821 bbd
[i
].end_of_trace
= -1;
1826 traces
= XNEWVEC (struct trace
, n_basic_blocks
);
1828 find_traces (&n_traces
, traces
);
1829 connect_traces (n_traces
, traces
);
1833 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
1836 dump_flow_info (dump_file
, dump_flags
);
1838 if (flag_reorder_blocks_and_partition
)
1839 verify_hot_cold_block_grouping ();
1842 /* Determine which partition the first basic block in the function
1843 belongs to, then find the first basic block in the current function
1844 that belongs to a different section, and insert a
1845 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
1846 instruction stream. When writing out the assembly code,
1847 encountering this note will make the compiler switch between the
1848 hot and cold text sections. */
1851 insert_section_boundary_note (void)
1855 int first_partition
= 0;
1857 if (flag_reorder_blocks_and_partition
)
1860 if (!first_partition
)
1861 first_partition
= BB_PARTITION (bb
);
1862 if (BB_PARTITION (bb
) != first_partition
)
1864 new_note
= emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS
,
1866 /* ??? This kind of note always lives between basic blocks,
1867 but add_insn_before will set BLOCK_FOR_INSN anyway. */
1868 BLOCK_FOR_INSN (new_note
) = NULL
;
1874 /* Duplicate the blocks containing computed gotos. This basically unfactors
1875 computed gotos that were factored early on in the compilation process to
1876 speed up edge based data flow. We used to not unfactoring them again,
1877 which can seriously pessimize code with many computed jumps in the source
1878 code, such as interpreters. See e.g. PR15242. */
1881 gate_duplicate_computed_gotos (void)
1883 if (targetm
.cannot_modify_jumps_p ())
1885 return (optimize
> 0
1886 && flag_expensive_optimizations
1887 && ! optimize_function_for_size_p (cfun
));
1892 duplicate_computed_gotos (void)
1894 basic_block bb
, new_bb
;
1898 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
1901 cfg_layout_initialize (0);
1903 /* We are estimating the length of uncond jump insn only once
1904 since the code for getting the insn length always returns
1905 the minimal length now. */
1906 if (uncond_jump_length
== 0)
1907 uncond_jump_length
= get_uncond_jump_length ();
1909 max_size
= uncond_jump_length
* PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS
);
1910 candidates
= BITMAP_ALLOC (NULL
);
1912 /* Look for blocks that end in a computed jump, and see if such blocks
1913 are suitable for unfactoring. If a block is a candidate for unfactoring,
1914 mark it in the candidates. */
1920 int size
, all_flags
;
1922 /* Build the reorder chain for the original order of blocks. */
1923 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
1924 bb
->aux
= bb
->next_bb
;
1926 /* Obviously the block has to end in a computed jump. */
1927 if (!computed_jump_p (BB_END (bb
)))
1930 /* Only consider blocks that can be duplicated. */
1931 if (find_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
)
1932 || !can_duplicate_block_p (bb
))
1935 /* Make sure that the block is small enough. */
1937 FOR_BB_INSNS (bb
, insn
)
1940 size
+= get_attr_min_length (insn
);
1941 if (size
> max_size
)
1944 if (size
> max_size
)
1947 /* Final check: there must not be any incoming abnormal edges. */
1949 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1950 all_flags
|= e
->flags
;
1951 if (all_flags
& EDGE_COMPLEX
)
1954 bitmap_set_bit (candidates
, bb
->index
);
1957 /* Nothing to do if there is no computed jump here. */
1958 if (bitmap_empty_p (candidates
))
1961 /* Duplicate computed gotos. */
1964 if (bb
->il
.rtl
->visited
)
1967 bb
->il
.rtl
->visited
= 1;
1969 /* BB must have one outgoing edge. That edge must not lead to
1970 the exit block or the next block.
1971 The destination must have more than one predecessor. */
1972 if (!single_succ_p (bb
)
1973 || single_succ (bb
) == EXIT_BLOCK_PTR
1974 || single_succ (bb
) == bb
->next_bb
1975 || single_pred_p (single_succ (bb
)))
1978 /* The successor block has to be a duplication candidate. */
1979 if (!bitmap_bit_p (candidates
, single_succ (bb
)->index
))
1982 new_bb
= duplicate_block (single_succ (bb
), single_succ_edge (bb
), bb
);
1983 new_bb
->aux
= bb
->aux
;
1985 new_bb
->il
.rtl
->visited
= 1;
1989 cfg_layout_finalize ();
1991 BITMAP_FREE (candidates
);
1995 struct rtl_opt_pass pass_duplicate_computed_gotos
=
1999 "compgotos", /* name */
2000 gate_duplicate_computed_gotos
, /* gate */
2001 duplicate_computed_gotos
, /* execute */
2004 0, /* static_pass_number */
2005 TV_REORDER_BLOCKS
, /* tv_id */
2006 0, /* properties_required */
2007 0, /* properties_provided */
2008 0, /* properties_destroyed */
2009 0, /* todo_flags_start */
2010 TODO_verify_rtl_sharing
,/* todo_flags_finish */
2015 /* This function is the main 'entrance' for the optimization that
2016 partitions hot and cold basic blocks into separate sections of the
2017 .o file (to improve performance and cache locality). Ideally it
2018 would be called after all optimizations that rearrange the CFG have
2019 been called. However part of this optimization may introduce new
2020 register usage, so it must be called before register allocation has
2021 occurred. This means that this optimization is actually called
2022 well before the optimization that reorders basic blocks (see
2025 This optimization checks the feedback information to determine
2026 which basic blocks are hot/cold, updates flags on the basic blocks
2027 to indicate which section they belong in. This information is
2028 later used for writing out sections in the .o file. Because hot
2029 and cold sections can be arbitrarily large (within the bounds of
2030 memory), far beyond the size of a single function, it is necessary
2031 to fix up all edges that cross section boundaries, to make sure the
2032 instructions used can actually span the required distance. The
2033 fixes are described below.
2035 Fall-through edges must be changed into jumps; it is not safe or
2036 legal to fall through across a section boundary. Whenever a
2037 fall-through edge crossing a section boundary is encountered, a new
2038 basic block is inserted (in the same section as the fall-through
2039 source), and the fall through edge is redirected to the new basic
2040 block. The new basic block contains an unconditional jump to the
2041 original fall-through target. (If the unconditional jump is
2042 insufficient to cross section boundaries, that is dealt with a
2043 little later, see below).
2045 In order to deal with architectures that have short conditional
2046 branches (which cannot span all of memory) we take any conditional
2047 jump that attempts to cross a section boundary and add a level of
2048 indirection: it becomes a conditional jump to a new basic block, in
2049 the same section. The new basic block contains an unconditional
2050 jump to the original target, in the other section.
2052 For those architectures whose unconditional branch is also
2053 incapable of reaching all of memory, those unconditional jumps are
2054 converted into indirect jumps, through a register.
2056 IMPORTANT NOTE: This optimization causes some messy interactions
2057 with the cfg cleanup optimizations; those optimizations want to
2058 merge blocks wherever possible, and to collapse indirect jump
2059 sequences (change "A jumps to B jumps to C" directly into "A jumps
2060 to C"). Those optimizations can undo the jump fixes that
2061 partitioning is required to make (see above), in order to ensure
2062 that jumps attempting to cross section boundaries are really able
2063 to cover whatever distance the jump requires (on many architectures
2064 conditional or unconditional jumps are not able to reach all of
2065 memory). Therefore tests have to be inserted into each such
2066 optimization to make sure that it does not undo stuff necessary to
2067 cross partition boundaries. This would be much less of a problem
2068 if we could perform this optimization later in the compilation, but
2069 unfortunately the fact that we may need to create indirect jumps
2070 (through registers) requires that this optimization be performed
2071 before register allocation.
2073 Hot and cold basic blocks are partitioned and put in separate
2074 sections of the .o file, to reduce paging and improve cache
2075 performance (hopefully). This can result in bits of code from the
2076 same function being widely separated in the .o file. However this
2077 is not obvious to the current bb structure. Therefore we must take
2078 care to ensure that: 1). There are no fall_thru edges that cross
2079 between sections; 2). For those architectures which have "short"
2080 conditional branches, all conditional branches that attempt to
2081 cross between sections are converted to unconditional branches;
2082 and, 3). For those architectures which have "short" unconditional
2083 branches, all unconditional branches that attempt to cross between
2084 sections are converted to indirect jumps.
2086 The code for fixing up fall_thru edges that cross between hot and
2087 cold basic blocks does so by creating new basic blocks containing
2088 unconditional branches to the appropriate label in the "other"
2089 section. The new basic block is then put in the same (hot or cold)
2090 section as the original conditional branch, and the fall_thru edge
2091 is modified to fall into the new basic block instead. By adding
2092 this level of indirection we end up with only unconditional branches
2093 crossing between hot and cold sections.
2095 Conditional branches are dealt with by adding a level of indirection.
2096 A new basic block is added in the same (hot/cold) section as the
2097 conditional branch, and the conditional branch is retargeted to the
2098 new basic block. The new basic block contains an unconditional branch
2099 to the original target of the conditional branch (in the other section).
2101 Unconditional branches are dealt with by converting them into
2105 partition_hot_cold_basic_blocks (void)
2107 VEC(edge
, heap
) *crossing_edges
;
2109 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
2112 crossing_edges
= find_rarely_executed_basic_blocks_and_crossing_edges ();
2113 if (crossing_edges
== NULL
)
2116 /* Make sure the source of any crossing edge ends in a jump and the
2117 destination of any crossing edge has a label. */
2118 add_labels_and_missing_jumps (crossing_edges
);
2120 /* Convert all crossing fall_thru edges to non-crossing fall
2121 thrus to unconditional jumps (that jump to the original fall
2123 fix_up_fall_thru_edges ();
2125 /* If the architecture does not have conditional branches that can
2126 span all of memory, convert crossing conditional branches into
2127 crossing unconditional branches. */
2128 if (!HAS_LONG_COND_BRANCH
)
2129 fix_crossing_conditional_branches ();
2131 /* If the architecture does not have unconditional branches that
2132 can span all of memory, convert crossing unconditional branches
2133 into indirect jumps. Since adding an indirect jump also adds
2134 a new register usage, update the register usage information as
2136 if (!HAS_LONG_UNCOND_BRANCH
)
2137 fix_crossing_unconditional_branches ();
2139 add_reg_crossing_jump_notes ();
2141 VEC_free (edge
, heap
, crossing_edges
);
2143 return TODO_verify_flow
| TODO_verify_rtl_sharing
;
2147 gate_handle_reorder_blocks (void)
2149 if (targetm
.cannot_modify_jumps_p ())
2151 return (optimize
> 0);
2155 /* Reorder basic blocks. */
2157 rest_of_handle_reorder_blocks (void)
2161 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2162 splitting possibly introduced more crossjumping opportunities. */
2163 cfg_layout_initialize (CLEANUP_EXPENSIVE
);
2165 if ((flag_reorder_blocks
|| flag_reorder_blocks_and_partition
)
2166 /* Don't reorder blocks when optimizing for size because extra jump insns may
2167 be created; also barrier may create extra padding.
2169 More correctly we should have a block reordering mode that tried to
2170 minimize the combined size of all the jumps. This would more or less
2171 automatically remove extra jumps, but would also try to use more short
2172 jumps instead of long jumps. */
2173 && optimize_function_for_speed_p (cfun
))
2175 reorder_basic_blocks ();
2176 cleanup_cfg (CLEANUP_EXPENSIVE
);
2180 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2181 bb
->aux
= bb
->next_bb
;
2182 cfg_layout_finalize ();
2184 /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */
2185 insert_section_boundary_note ();
2189 struct rtl_opt_pass pass_reorder_blocks
=
2194 gate_handle_reorder_blocks
, /* gate */
2195 rest_of_handle_reorder_blocks
, /* execute */
2198 0, /* static_pass_number */
2199 TV_REORDER_BLOCKS
, /* tv_id */
2200 0, /* properties_required */
2201 0, /* properties_provided */
2202 0, /* properties_destroyed */
2203 0, /* todo_flags_start */
2204 TODO_verify_rtl_sharing
, /* todo_flags_finish */
2209 gate_handle_partition_blocks (void)
2211 /* The optimization to partition hot/cold basic blocks into separate
2212 sections of the .o file does not work well with linkonce or with
2213 user defined section attributes. Don't call it if either case
2215 return (flag_reorder_blocks_and_partition
2216 && !DECL_ONE_ONLY (current_function_decl
)
2217 && !user_defined_section_attribute
);
2220 struct rtl_opt_pass pass_partition_blocks
=
2224 "bbpart", /* name */
2225 gate_handle_partition_blocks
, /* gate */
2226 partition_hot_cold_basic_blocks
, /* execute */
2229 0, /* static_pass_number */
2230 TV_REORDER_BLOCKS
, /* tv_id */
2231 PROP_cfglayout
, /* properties_required */
2232 0, /* properties_provided */
2233 0, /* properties_destroyed */
2234 0, /* todo_flags_start */
2235 0 /* todo_flags_finish */