1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000-2017 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 file contains the "reorder blocks" pass, which changes the control
21 flow of a function to encounter fewer branches; the "partition blocks"
22 pass, which divides the basic blocks into "hot" and "cold" partitions,
23 which are kept separate; and the "duplicate computed gotos" pass, which
24 duplicates blocks ending in an indirect jump.
26 There are two algorithms for "reorder blocks": the "simple" algorithm,
27 which just rearranges blocks, trying to minimize the number of executed
28 unconditional branches; and the "software trace cache" algorithm, which
29 also copies code, and in general tries a lot harder to have long linear
30 pieces of machine code executed. This algorithm is described next. */
32 /* This (greedy) algorithm constructs traces in several rounds.
33 The construction starts from "seeds". The seed for the first round
34 is the entry point of the function. When there are more than one seed,
35 the one with the lowest key in the heap is selected first (see bb_to_key).
36 Then the algorithm repeatedly adds the most probable successor to the end
37 of a trace. Finally it connects the traces.
39 There are two parameters: Branch Threshold and Exec Threshold.
40 If the probability of an edge to a successor of the current basic block is
41 lower than Branch Threshold or its frequency is lower than Exec Threshold,
42 then the successor will be the seed in one of the next rounds.
43 Each round has these parameters lower than the previous one.
44 The last round has to have these parameters set to zero so that the
45 remaining blocks are picked up.
47 The algorithm selects the most probable successor from all unvisited
48 successors and successors that have been added to this trace.
49 The other successors (that has not been "sent" to the next round) will be
50 other seeds for this round and the secondary traces will start from them.
51 If the successor has not been visited in this trace, it is added to the
52 trace (however, there is some heuristic for simple branches).
53 If the successor has been visited in this trace, a loop has been found.
54 If the loop has many iterations, the loop is rotated so that the source
55 block of the most probable edge going out of the loop is the last block
57 If the loop has few iterations and there is no edge from the last block of
58 the loop going out of the loop, the loop header is duplicated.
60 When connecting traces, the algorithm first checks whether there is an edge
61 from the last block of a trace to the first block of another trace.
62 When there are still some unconnected traces it checks whether there exists
63 a basic block BB such that BB is a successor of the last block of a trace
64 and BB is a predecessor of the first block of another trace. In this case,
65 BB is duplicated, added at the end of the first trace and the traces are
67 The rest of traces are simply connected so there will be a jump to the
68 beginning of the rest of traces.
70 The above description is for the full algorithm, which is used when the
71 function is optimized for speed. When the function is optimized for size,
72 in order to reduce long jumps and connect more fallthru edges, the
73 algorithm is modified as follows:
74 (1) Break long traces to short ones. A trace is broken at a block that has
75 multiple predecessors/ successors during trace discovery. When connecting
76 traces, only connect Trace n with Trace n + 1. This change reduces most
77 long jumps compared with the above algorithm.
78 (2) Ignore the edge probability and frequency for fallthru edges.
79 (3) Keep the original order of blocks when there is no chance to fall
80 through. We rely on the results of cfg_cleanup.
82 To implement the change for code size optimization, block's index is
83 selected as the key and all traces are found in one round.
87 "Software Trace Cache"
88 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
89 http://citeseer.nj.nec.com/15361.html
94 #define INCLUDE_ALGORITHM /* stable_sort */
96 #include "coretypes.h"
101 #include "cfghooks.h"
103 #include "memmodel.h"
106 #include "emit-rtl.h"
110 #include "tree-pass.h"
113 #include "cfgbuild.h"
114 #include "cfgcleanup.h"
115 #include "bb-reorder.h"
117 #include "fibonacci_heap.h"
119 /* The number of rounds. In most cases there will only be 4 rounds, but
120 when partitioning hot and cold basic blocks into separate sections of
121 the object file there will be an extra round. */
124 struct target_bb_reorder default_target_bb_reorder
;
125 #if SWITCHABLE_TARGET
126 struct target_bb_reorder
*this_target_bb_reorder
= &default_target_bb_reorder
;
129 #define uncond_jump_length \
130 (this_target_bb_reorder->x_uncond_jump_length)
132 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
133 static const int branch_threshold
[N_ROUNDS
] = {400, 200, 100, 0, 0};
135 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
136 static const int exec_threshold
[N_ROUNDS
] = {500, 200, 50, 0, 0};
138 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
139 block the edge destination is not duplicated while connecting traces. */
140 #define DUPLICATION_THRESHOLD 100
142 typedef fibonacci_heap
<long, basic_block_def
> bb_heap_t
;
143 typedef fibonacci_node
<long, basic_block_def
> bb_heap_node_t
;
145 /* Structure to hold needed information for each basic block. */
146 struct bbro_basic_block_data
148 /* Which trace is the bb start of (-1 means it is not a start of any). */
151 /* Which trace is the bb end of (-1 means it is not an end of any). */
154 /* Which trace is the bb in? */
157 /* Which trace was this bb visited in? */
160 /* Cached maximum frequency of interesting incoming edges.
161 Minus one means not yet computed. */
164 /* Which heap is BB in (if any)? */
167 /* Which heap node is BB in (if any)? */
168 bb_heap_node_t
*node
;
171 /* The current size of the following dynamic array. */
172 static int array_size
;
174 /* The array which holds needed information for basic blocks. */
175 static bbro_basic_block_data
*bbd
;
177 /* To avoid frequent reallocation the size of arrays is greater than needed,
178 the number of elements is (not less than) 1.25 * size_wanted. */
179 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
181 /* Free the memory and set the pointer to NULL. */
182 #define FREE(P) (gcc_assert (P), free (P), P = 0)
184 /* Structure for holding information about a trace. */
187 /* First and last basic block of the trace. */
188 basic_block first
, last
;
190 /* The round of the STC creation which this trace was found in. */
193 /* The length (i.e. the number of basic blocks) of the trace. */
197 /* Maximum frequency and count of one of the entry blocks. */
198 static int max_entry_frequency
;
199 static profile_count max_entry_count
;
201 /* Local function prototypes. */
202 static void find_traces (int *, struct trace
*);
203 static basic_block
rotate_loop (edge
, struct trace
*, int);
204 static void mark_bb_visited (basic_block
, int);
205 static void find_traces_1_round (int, int, gcov_type
, struct trace
*, int *,
206 int, bb_heap_t
**, int);
207 static basic_block
copy_bb (basic_block
, edge
, basic_block
, int);
208 static long bb_to_key (basic_block
);
209 static bool better_edge_p (const_basic_block
, const_edge
, profile_probability
,
210 int, profile_probability
, int, const_edge
);
211 static bool connect_better_edge_p (const_edge
, bool, int, const_edge
,
213 static void connect_traces (int, struct trace
*);
214 static bool copy_bb_p (const_basic_block
, int);
215 static bool push_to_next_round_p (const_basic_block
, int, int, int, gcov_type
);
217 /* Return the trace number in which BB was visited. */
220 bb_visited_trace (const_basic_block bb
)
222 gcc_assert (bb
->index
< array_size
);
223 return bbd
[bb
->index
].visited
;
226 /* This function marks BB that it was visited in trace number TRACE. */
229 mark_bb_visited (basic_block bb
, int trace
)
231 bbd
[bb
->index
].visited
= trace
;
232 if (bbd
[bb
->index
].heap
)
234 bbd
[bb
->index
].heap
->delete_node (bbd
[bb
->index
].node
);
235 bbd
[bb
->index
].heap
= NULL
;
236 bbd
[bb
->index
].node
= NULL
;
240 /* Check to see if bb should be pushed into the next round of trace
241 collections or not. Reasons for pushing the block forward are 1).
242 If the block is cold, we are doing partitioning, and there will be
243 another round (cold partition blocks are not supposed to be
244 collected into traces until the very last round); or 2). There will
245 be another round, and the basic block is not "hot enough" for the
246 current round of trace collection. */
249 push_to_next_round_p (const_basic_block bb
, int round
, int number_of_rounds
,
250 int exec_th
, gcov_type count_th
)
252 bool there_exists_another_round
;
253 bool block_not_hot_enough
;
255 there_exists_another_round
= round
< number_of_rounds
- 1;
257 block_not_hot_enough
= (bb
->frequency
< exec_th
258 || bb
->count
< count_th
259 || probably_never_executed_bb_p (cfun
, bb
));
261 if (there_exists_another_round
262 && block_not_hot_enough
)
268 /* Find the traces for Software Trace Cache. Chain each trace through
269 RBI()->next. Store the number of traces to N_TRACES and description of
273 find_traces (int *n_traces
, struct trace
*traces
)
276 int number_of_rounds
;
279 bb_heap_t
*heap
= new bb_heap_t (LONG_MIN
);
281 /* Add one extra round of trace collection when partitioning hot/cold
282 basic blocks into separate sections. The last round is for all the
283 cold blocks (and ONLY the cold blocks). */
285 number_of_rounds
= N_ROUNDS
- 1;
287 /* Insert entry points of function into heap. */
288 max_entry_frequency
= 0;
289 max_entry_count
= profile_count::zero ();
290 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
292 bbd
[e
->dest
->index
].heap
= heap
;
293 bbd
[e
->dest
->index
].node
= heap
->insert (bb_to_key (e
->dest
), e
->dest
);
294 if (e
->dest
->frequency
> max_entry_frequency
)
295 max_entry_frequency
= e
->dest
->frequency
;
296 if (e
->dest
->count
.initialized_p () && e
->dest
->count
> max_entry_count
)
297 max_entry_count
= e
->dest
->count
;
300 /* Find the traces. */
301 for (i
= 0; i
< number_of_rounds
; i
++)
303 gcov_type count_threshold
;
306 fprintf (dump_file
, "STC - round %d\n", i
+ 1);
308 if (max_entry_count
< INT_MAX
/ 1000)
309 count_threshold
= max_entry_count
.to_gcov_type () * exec_threshold
[i
] / 1000;
311 count_threshold
= max_entry_count
.to_gcov_type () / 1000 * exec_threshold
[i
];
313 find_traces_1_round (REG_BR_PROB_BASE
* branch_threshold
[i
] / 1000,
314 max_entry_frequency
* exec_threshold
[i
] / 1000,
315 count_threshold
, traces
, n_traces
, i
, &heap
,
322 for (i
= 0; i
< *n_traces
; i
++)
325 fprintf (dump_file
, "Trace %d (round %d): ", i
+ 1,
326 traces
[i
].round
+ 1);
327 for (bb
= traces
[i
].first
;
328 bb
!= traces
[i
].last
;
329 bb
= (basic_block
) bb
->aux
)
330 fprintf (dump_file
, "%d [%d] ", bb
->index
, bb
->frequency
);
331 fprintf (dump_file
, "%d [%d]\n", bb
->index
, bb
->frequency
);
337 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
338 (with sequential number TRACE_N). */
341 rotate_loop (edge back_edge
, struct trace
*trace
, int trace_n
)
345 /* Information about the best end (end after rotation) of the loop. */
346 basic_block best_bb
= NULL
;
347 edge best_edge
= NULL
;
349 profile_count best_count
= profile_count::uninitialized ();
350 /* The best edge is preferred when its destination is not visited yet
351 or is a start block of some trace. */
352 bool is_preferred
= false;
354 /* Find the most frequent edge that goes out from current trace. */
355 bb
= back_edge
->dest
;
361 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
362 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
363 && bb_visited_trace (e
->dest
) != trace_n
364 && (e
->flags
& EDGE_CAN_FALLTHRU
)
365 && !(e
->flags
& EDGE_COMPLEX
))
369 /* The best edge is preferred. */
370 if (!bb_visited_trace (e
->dest
)
371 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
373 /* The current edge E is also preferred. */
374 int freq
= EDGE_FREQUENCY (e
);
375 if (freq
> best_freq
|| e
->count
> best_count
)
378 if (e
->count
.initialized_p ())
379 best_count
= e
->count
;
387 if (!bb_visited_trace (e
->dest
)
388 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
390 /* The current edge E is preferred. */
392 best_freq
= EDGE_FREQUENCY (e
);
393 best_count
= e
->count
;
399 int freq
= EDGE_FREQUENCY (e
);
400 if (!best_edge
|| freq
> best_freq
|| e
->count
> best_count
)
403 best_count
= e
->count
;
410 bb
= (basic_block
) bb
->aux
;
412 while (bb
!= back_edge
->dest
);
416 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
418 if (back_edge
->dest
== trace
->first
)
420 trace
->first
= (basic_block
) best_bb
->aux
;
426 for (prev_bb
= trace
->first
;
427 prev_bb
->aux
!= back_edge
->dest
;
428 prev_bb
= (basic_block
) prev_bb
->aux
)
430 prev_bb
->aux
= best_bb
->aux
;
432 /* Try to get rid of uncond jump to cond jump. */
433 if (single_succ_p (prev_bb
))
435 basic_block header
= single_succ (prev_bb
);
437 /* Duplicate HEADER if it is a small block containing cond jump
439 if (any_condjump_p (BB_END (header
)) && copy_bb_p (header
, 0)
440 && !CROSSING_JUMP_P (BB_END (header
)))
441 copy_bb (header
, single_succ_edge (prev_bb
), prev_bb
, trace_n
);
447 /* We have not found suitable loop tail so do no rotation. */
448 best_bb
= back_edge
->src
;
454 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
455 not include basic blocks whose probability is lower than BRANCH_TH or whose
456 frequency is lower than EXEC_TH into traces (or whose count is lower than
457 COUNT_TH). Store the new traces into TRACES and modify the number of
458 traces *N_TRACES. Set the round (which the trace belongs to) to ROUND.
459 The function expects starting basic blocks to be in *HEAP and will delete
460 *HEAP and store starting points for the next round into new *HEAP. */
463 find_traces_1_round (int branch_th
, int exec_th
, gcov_type count_th
,
464 struct trace
*traces
, int *n_traces
, int round
,
465 bb_heap_t
**heap
, int number_of_rounds
)
467 /* Heap for discarded basic blocks which are possible starting points for
469 bb_heap_t
*new_heap
= new bb_heap_t (LONG_MIN
);
470 bool for_size
= optimize_function_for_size_p (cfun
);
472 while (!(*heap
)->empty ())
480 bb
= (*heap
)->extract_min ();
481 bbd
[bb
->index
].heap
= NULL
;
482 bbd
[bb
->index
].node
= NULL
;
485 fprintf (dump_file
, "Getting bb %d\n", bb
->index
);
487 /* If the BB's frequency is too low, send BB to the next round. When
488 partitioning hot/cold blocks into separate sections, make sure all
489 the cold blocks (and ONLY the cold blocks) go into the (extra) final
490 round. When optimizing for size, do not push to next round. */
493 && push_to_next_round_p (bb
, round
, number_of_rounds
, exec_th
,
496 int key
= bb_to_key (bb
);
497 bbd
[bb
->index
].heap
= new_heap
;
498 bbd
[bb
->index
].node
= new_heap
->insert (key
, bb
);
502 " Possible start point of next round: %d (key: %d)\n",
507 trace
= traces
+ *n_traces
;
509 trace
->round
= round
;
511 bbd
[bb
->index
].in_trace
= *n_traces
;
516 profile_probability prob
;
520 /* The probability and frequency of the best edge. */
521 profile_probability best_prob
= profile_probability::uninitialized ();
522 int best_freq
= INT_MIN
/ 2;
525 mark_bb_visited (bb
, *n_traces
);
529 fprintf (dump_file
, "Basic block %d was visited in trace %d\n",
530 bb
->index
, *n_traces
- 1);
532 ends_in_call
= block_ends_with_call_p (bb
);
534 /* Select the successor that will be placed after BB. */
535 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
537 gcc_assert (!(e
->flags
& EDGE_FAKE
));
539 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
542 if (bb_visited_trace (e
->dest
)
543 && bb_visited_trace (e
->dest
) != *n_traces
)
546 if (BB_PARTITION (e
->dest
) != BB_PARTITION (bb
))
549 prob
= e
->probability
;
550 freq
= e
->dest
->frequency
;
552 /* The only sensible preference for a call instruction is the
553 fallthru edge. Don't bother selecting anything else. */
556 if (e
->flags
& EDGE_CAN_FALLTHRU
)
565 /* Edge that cannot be fallthru or improbable or infrequent
566 successor (i.e. it is unsuitable successor). When optimizing
567 for size, ignore the probability and frequency. */
568 if (!(e
->flags
& EDGE_CAN_FALLTHRU
) || (e
->flags
& EDGE_COMPLEX
)
569 || !prob
.initialized_p ()
570 || ((prob
.to_reg_br_prob_base () < branch_th
571 || EDGE_FREQUENCY (e
) < exec_th
572 || e
->count
< count_th
) && (!for_size
)))
575 /* If partitioning hot/cold basic blocks, don't consider edges
576 that cross section boundaries. */
578 if (better_edge_p (bb
, e
, prob
, freq
, best_prob
, best_freq
,
587 /* If the best destination has multiple predecessors, and can be
588 duplicated cheaper than a jump, don't allow it to be added
589 to a trace. We'll duplicate it when connecting traces. */
590 if (best_edge
&& EDGE_COUNT (best_edge
->dest
->preds
) >= 2
591 && copy_bb_p (best_edge
->dest
, 0))
594 /* If the best destination has multiple successors or predecessors,
595 don't allow it to be added when optimizing for size. This makes
596 sure predecessors with smaller index are handled before the best
597 destinarion. It breaks long trace and reduces long jumps.
599 Take if-then-else as an example.
605 If we do not remove the best edge B->D/C->D, the final order might
606 be A B D ... C. C is at the end of the program. If D's successors
607 and D are complicated, might need long jumps for A->C and C->D.
608 Similar issue for order: A C D ... B.
610 After removing the best edge, the final result will be ABCD/ ACBD.
611 It does not add jump compared with the previous order. But it
612 reduces the possibility of long jumps. */
613 if (best_edge
&& for_size
614 && (EDGE_COUNT (best_edge
->dest
->succs
) > 1
615 || EDGE_COUNT (best_edge
->dest
->preds
) > 1))
618 /* Add all non-selected successors to the heaps. */
619 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
622 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
623 || bb_visited_trace (e
->dest
))
626 key
= bb_to_key (e
->dest
);
628 if (bbd
[e
->dest
->index
].heap
)
630 /* E->DEST is already in some heap. */
631 if (key
!= bbd
[e
->dest
->index
].node
->get_key ())
636 "Changing key for bb %d from %ld to %ld.\n",
638 (long) bbd
[e
->dest
->index
].node
->get_key (),
641 bbd
[e
->dest
->index
].heap
->replace_key
642 (bbd
[e
->dest
->index
].node
, key
);
647 bb_heap_t
*which_heap
= *heap
;
649 prob
= e
->probability
;
650 freq
= EDGE_FREQUENCY (e
);
652 if (!(e
->flags
& EDGE_CAN_FALLTHRU
)
653 || (e
->flags
& EDGE_COMPLEX
)
654 || !prob
.initialized_p ()
655 || prob
.to_reg_br_prob_base () < branch_th
657 || e
->count
< count_th
)
659 /* When partitioning hot/cold basic blocks, make sure
660 the cold blocks (and only the cold blocks) all get
661 pushed to the last round of trace collection. When
662 optimizing for size, do not push to next round. */
664 if (!for_size
&& push_to_next_round_p (e
->dest
, round
,
667 which_heap
= new_heap
;
670 bbd
[e
->dest
->index
].heap
= which_heap
;
671 bbd
[e
->dest
->index
].node
= which_heap
->insert (key
, e
->dest
);
676 " Possible start of %s round: %d (key: %ld)\n",
677 (which_heap
== new_heap
) ? "next" : "this",
678 e
->dest
->index
, (long) key
);
684 if (best_edge
) /* Suitable successor was found. */
686 if (bb_visited_trace (best_edge
->dest
) == *n_traces
)
688 /* We do nothing with one basic block loops. */
689 if (best_edge
->dest
!= bb
)
691 if (EDGE_FREQUENCY (best_edge
)
692 > 4 * best_edge
->dest
->frequency
/ 5)
694 /* The loop has at least 4 iterations. If the loop
695 header is not the first block of the function
696 we can rotate the loop. */
699 != ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
704 "Rotating loop %d - %d\n",
705 best_edge
->dest
->index
, bb
->index
);
707 bb
->aux
= best_edge
->dest
;
708 bbd
[best_edge
->dest
->index
].in_trace
=
710 bb
= rotate_loop (best_edge
, trace
, *n_traces
);
715 /* The loop has less than 4 iterations. */
717 if (single_succ_p (bb
)
718 && copy_bb_p (best_edge
->dest
,
719 optimize_edge_for_speed_p
722 bb
= copy_bb (best_edge
->dest
, best_edge
, bb
,
729 /* Terminate the trace. */
734 /* Check for a situation
743 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
744 >= EDGE_FREQUENCY (AC).
745 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
746 Best ordering is then A B C.
748 When optimizing for size, A B C is always the best order.
750 This situation is created for example by:
757 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
759 && (e
->flags
& EDGE_CAN_FALLTHRU
)
760 && !(e
->flags
& EDGE_COMPLEX
)
761 && !bb_visited_trace (e
->dest
)
762 && single_pred_p (e
->dest
)
763 && !(e
->flags
& EDGE_CROSSING
)
764 && single_succ_p (e
->dest
)
765 && (single_succ_edge (e
->dest
)->flags
767 && !(single_succ_edge (e
->dest
)->flags
& EDGE_COMPLEX
)
768 && single_succ (e
->dest
) == best_edge
->dest
769 && (2 * e
->dest
->frequency
>= EDGE_FREQUENCY (best_edge
)
774 fprintf (dump_file
, "Selecting BB %d\n",
775 best_edge
->dest
->index
);
779 bb
->aux
= best_edge
->dest
;
780 bbd
[best_edge
->dest
->index
].in_trace
= (*n_traces
) - 1;
781 bb
= best_edge
->dest
;
787 bbd
[trace
->first
->index
].start_of_trace
= *n_traces
- 1;
788 if (bbd
[trace
->last
->index
].end_of_trace
!= *n_traces
- 1)
790 bbd
[trace
->last
->index
].end_of_trace
= *n_traces
- 1;
791 /* Update the cached maximum frequency for interesting predecessor
792 edges for successors of the new trace end. */
793 FOR_EACH_EDGE (e
, ei
, trace
->last
->succs
)
794 if (EDGE_FREQUENCY (e
) > bbd
[e
->dest
->index
].priority
)
795 bbd
[e
->dest
->index
].priority
= EDGE_FREQUENCY (e
);
798 /* The trace is terminated so we have to recount the keys in heap
799 (some block can have a lower key because now one of its predecessors
800 is an end of the trace). */
801 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
803 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
804 || bb_visited_trace (e
->dest
))
807 if (bbd
[e
->dest
->index
].heap
)
809 key
= bb_to_key (e
->dest
);
810 if (key
!= bbd
[e
->dest
->index
].node
->get_key ())
815 "Changing key for bb %d from %ld to %ld.\n",
817 (long) bbd
[e
->dest
->index
].node
->get_key (), key
);
819 bbd
[e
->dest
->index
].heap
->replace_key
820 (bbd
[e
->dest
->index
].node
, key
);
828 /* "Return" the new heap. */
832 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
833 it to trace after BB, mark OLD_BB visited and update pass' data structures
834 (TRACE is a number of trace which OLD_BB is duplicated to). */
837 copy_bb (basic_block old_bb
, edge e
, basic_block bb
, int trace
)
841 new_bb
= duplicate_block (old_bb
, e
, bb
);
842 BB_COPY_PARTITION (new_bb
, old_bb
);
844 gcc_assert (e
->dest
== new_bb
);
848 "Duplicated bb %d (created bb %d)\n",
849 old_bb
->index
, new_bb
->index
);
851 if (new_bb
->index
>= array_size
852 || last_basic_block_for_fn (cfun
) > array_size
)
857 new_size
= MAX (last_basic_block_for_fn (cfun
), new_bb
->index
+ 1);
858 new_size
= GET_ARRAY_SIZE (new_size
);
859 bbd
= XRESIZEVEC (bbro_basic_block_data
, bbd
, new_size
);
860 for (i
= array_size
; i
< new_size
; i
++)
862 bbd
[i
].start_of_trace
= -1;
863 bbd
[i
].end_of_trace
= -1;
864 bbd
[i
].in_trace
= -1;
866 bbd
[i
].priority
= -1;
870 array_size
= new_size
;
875 "Growing the dynamic array to %d elements.\n",
880 gcc_assert (!bb_visited_trace (e
->dest
));
881 mark_bb_visited (new_bb
, trace
);
882 new_bb
->aux
= bb
->aux
;
885 bbd
[new_bb
->index
].in_trace
= trace
;
890 /* Compute and return the key (for the heap) of the basic block BB. */
893 bb_to_key (basic_block bb
)
898 /* Use index as key to align with its original order. */
899 if (optimize_function_for_size_p (cfun
))
902 /* Do not start in probably never executed blocks. */
904 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
905 || probably_never_executed_bb_p (cfun
, bb
))
908 /* Prefer blocks whose predecessor is an end of some trace
909 or whose predecessor edge is EDGE_DFS_BACK. */
910 int priority
= bbd
[bb
->index
].priority
;
914 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
916 if ((e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
917 && bbd
[e
->src
->index
].end_of_trace
>= 0)
918 || (e
->flags
& EDGE_DFS_BACK
))
920 int edge_freq
= EDGE_FREQUENCY (e
);
922 if (edge_freq
> priority
)
923 priority
= edge_freq
;
926 bbd
[bb
->index
].priority
= priority
;
930 /* The block with priority should have significantly lower key. */
931 return -(100 * BB_FREQ_MAX
+ 100 * priority
+ bb
->frequency
);
933 return -bb
->frequency
;
936 /* Return true when the edge E from basic block BB is better than the temporary
937 best edge (details are in function). The probability of edge E is PROB. The
938 frequency of the successor is FREQ. The current best probability is
939 BEST_PROB, the best frequency is BEST_FREQ.
940 The edge is considered to be equivalent when PROB does not differ much from
941 BEST_PROB; similarly for frequency. */
944 better_edge_p (const_basic_block bb
, const_edge e
, profile_probability prob
,
945 int freq
, profile_probability best_prob
, int best_freq
,
946 const_edge cur_best_edge
)
950 /* The BEST_* values do not have to be best, but can be a bit smaller than
952 profile_probability diff_prob
= best_prob
.apply_scale (1, 10);
953 int diff_freq
= best_freq
/ 10;
955 /* The smaller one is better to keep the original order. */
956 if (optimize_function_for_size_p (cfun
))
957 return !cur_best_edge
958 || cur_best_edge
->dest
->index
> e
->dest
->index
;
960 if (prob
> best_prob
+ diff_prob
|| !best_prob
.initialized_p ())
961 /* The edge has higher probability than the temporary best edge. */
962 is_better_edge
= true;
963 else if (prob
< best_prob
- diff_prob
)
964 /* The edge has lower probability than the temporary best edge. */
965 is_better_edge
= false;
966 else if (freq
< best_freq
- diff_freq
)
967 /* The edge and the temporary best edge have almost equivalent
968 probabilities. The higher frequency of a successor now means
969 that there is another edge going into that successor.
970 This successor has lower frequency so it is better. */
971 is_better_edge
= true;
972 else if (freq
> best_freq
+ diff_freq
)
973 /* This successor has higher frequency so it is worse. */
974 is_better_edge
= false;
975 else if (e
->dest
->prev_bb
== bb
)
976 /* The edges have equivalent probabilities and the successors
977 have equivalent frequencies. Select the previous successor. */
978 is_better_edge
= true;
980 is_better_edge
= false;
982 /* If we are doing hot/cold partitioning, make sure that we always favor
983 non-crossing edges over crossing edges. */
986 && flag_reorder_blocks_and_partition
988 && (cur_best_edge
->flags
& EDGE_CROSSING
)
989 && !(e
->flags
& EDGE_CROSSING
))
990 is_better_edge
= true;
992 return is_better_edge
;
995 /* Return true when the edge E is better than the temporary best edge
996 CUR_BEST_EDGE. If SRC_INDEX_P is true, the function compares the src bb of
997 E and CUR_BEST_EDGE; otherwise it will compare the dest bb.
998 BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE.
999 TRACES record the information about traces.
1000 When optimizing for size, the edge with smaller index is better.
1001 When optimizing for speed, the edge with bigger probability or longer trace
1005 connect_better_edge_p (const_edge e
, bool src_index_p
, int best_len
,
1006 const_edge cur_best_edge
, struct trace
*traces
)
1010 bool is_better_edge
;
1015 if (optimize_function_for_size_p (cfun
))
1017 e_index
= src_index_p
? e
->src
->index
: e
->dest
->index
;
1018 b_index
= src_index_p
? cur_best_edge
->src
->index
1019 : cur_best_edge
->dest
->index
;
1020 /* The smaller one is better to keep the original order. */
1021 return b_index
> e_index
;
1026 e_index
= e
->src
->index
;
1028 if (e
->probability
> cur_best_edge
->probability
)
1029 /* The edge has higher probability than the temporary best edge. */
1030 is_better_edge
= true;
1031 else if (e
->probability
< cur_best_edge
->probability
)
1032 /* The edge has lower probability than the temporary best edge. */
1033 is_better_edge
= false;
1034 else if (traces
[bbd
[e_index
].end_of_trace
].length
> best_len
)
1035 /* The edge and the temporary best edge have equivalent probabilities.
1036 The edge with longer trace is better. */
1037 is_better_edge
= true;
1039 is_better_edge
= false;
1043 e_index
= e
->dest
->index
;
1045 if (e
->probability
> cur_best_edge
->probability
)
1046 /* The edge has higher probability than the temporary best edge. */
1047 is_better_edge
= true;
1048 else if (e
->probability
< cur_best_edge
->probability
)
1049 /* The edge has lower probability than the temporary best edge. */
1050 is_better_edge
= false;
1051 else if (traces
[bbd
[e_index
].start_of_trace
].length
> best_len
)
1052 /* The edge and the temporary best edge have equivalent probabilities.
1053 The edge with longer trace is better. */
1054 is_better_edge
= true;
1056 is_better_edge
= false;
1059 return is_better_edge
;
1062 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
1065 connect_traces (int n_traces
, struct trace
*traces
)
1072 int current_partition
;
1074 gcov_type count_threshold
;
1075 bool for_size
= optimize_function_for_size_p (cfun
);
1077 freq_threshold
= max_entry_frequency
* DUPLICATION_THRESHOLD
/ 1000;
1078 if (max_entry_count
.to_gcov_type () < INT_MAX
/ 1000)
1079 count_threshold
= max_entry_count
.to_gcov_type () * DUPLICATION_THRESHOLD
/ 1000;
1081 count_threshold
= max_entry_count
.to_gcov_type () / 1000 * DUPLICATION_THRESHOLD
;
1083 connected
= XCNEWVEC (bool, n_traces
);
1086 current_partition
= BB_PARTITION (traces
[0].first
);
1089 if (crtl
->has_bb_partition
)
1090 for (i
= 0; i
< n_traces
&& !two_passes
; i
++)
1091 if (BB_PARTITION (traces
[0].first
)
1092 != BB_PARTITION (traces
[i
].first
))
1095 for (i
= 0; i
< n_traces
|| (two_passes
&& current_pass
== 1) ; i
++)
1104 gcc_assert (two_passes
&& current_pass
== 1);
1108 if (current_partition
== BB_HOT_PARTITION
)
1109 current_partition
= BB_COLD_PARTITION
;
1111 current_partition
= BB_HOT_PARTITION
;
1118 && BB_PARTITION (traces
[t
].first
) != current_partition
)
1121 connected
[t
] = true;
1123 /* Find the predecessor traces. */
1124 for (t2
= t
; t2
> 0;)
1129 FOR_EACH_EDGE (e
, ei
, traces
[t2
].first
->preds
)
1131 int si
= e
->src
->index
;
1133 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1134 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1135 && !(e
->flags
& EDGE_COMPLEX
)
1136 && bbd
[si
].end_of_trace
>= 0
1137 && !connected
[bbd
[si
].end_of_trace
]
1138 && (BB_PARTITION (e
->src
) == current_partition
)
1139 && connect_better_edge_p (e
, true, best_len
, best
, traces
))
1142 best_len
= traces
[bbd
[si
].end_of_trace
].length
;
1147 best
->src
->aux
= best
->dest
;
1148 t2
= bbd
[best
->src
->index
].end_of_trace
;
1149 connected
[t2
] = true;
1153 fprintf (dump_file
, "Connection: %d %d\n",
1154 best
->src
->index
, best
->dest
->index
);
1161 if (last_trace
>= 0)
1162 traces
[last_trace
].last
->aux
= traces
[t2
].first
;
1165 /* Find the successor traces. */
1168 /* Find the continuation of the chain. */
1172 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1174 int di
= e
->dest
->index
;
1176 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1177 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1178 && !(e
->flags
& EDGE_COMPLEX
)
1179 && bbd
[di
].start_of_trace
>= 0
1180 && !connected
[bbd
[di
].start_of_trace
]
1181 && (BB_PARTITION (e
->dest
) == current_partition
)
1182 && connect_better_edge_p (e
, false, best_len
, best
, traces
))
1185 best_len
= traces
[bbd
[di
].start_of_trace
].length
;
1192 /* Stop finding the successor traces. */
1195 /* It is OK to connect block n with block n + 1 or a block
1196 before n. For others, only connect to the loop header. */
1197 if (best
->dest
->index
> (traces
[t
].last
->index
+ 1))
1199 int count
= EDGE_COUNT (best
->dest
->preds
);
1201 FOR_EACH_EDGE (e
, ei
, best
->dest
->preds
)
1202 if (e
->flags
& EDGE_DFS_BACK
)
1205 /* If dest has multiple predecessors, skip it. We expect
1206 that one predecessor with smaller index connects with it
1212 /* Only connect Trace n with Trace n + 1. It is conservative
1213 to keep the order as close as possible to the original order.
1214 It also helps to reduce long jumps. */
1215 if (last_trace
!= bbd
[best
->dest
->index
].start_of_trace
- 1)
1219 fprintf (dump_file
, "Connection: %d %d\n",
1220 best
->src
->index
, best
->dest
->index
);
1222 t
= bbd
[best
->dest
->index
].start_of_trace
;
1223 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1224 connected
[t
] = true;
1231 fprintf (dump_file
, "Connection: %d %d\n",
1232 best
->src
->index
, best
->dest
->index
);
1234 t
= bbd
[best
->dest
->index
].start_of_trace
;
1235 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1236 connected
[t
] = true;
1241 /* Try to connect the traces by duplication of 1 block. */
1243 basic_block next_bb
= NULL
;
1244 bool try_copy
= false;
1246 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1247 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1248 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1249 && !(e
->flags
& EDGE_COMPLEX
)
1250 && (!best
|| e
->probability
> best
->probability
))
1256 /* If the destination is a start of a trace which is only
1257 one block long, then no need to search the successor
1258 blocks of the trace. Accept it. */
1259 if (bbd
[e
->dest
->index
].start_of_trace
>= 0
1260 && traces
[bbd
[e
->dest
->index
].start_of_trace
].length
1268 FOR_EACH_EDGE (e2
, ei
, e
->dest
->succs
)
1270 int di
= e2
->dest
->index
;
1272 if (e2
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
1273 || ((e2
->flags
& EDGE_CAN_FALLTHRU
)
1274 && !(e2
->flags
& EDGE_COMPLEX
)
1275 && bbd
[di
].start_of_trace
>= 0
1276 && !connected
[bbd
[di
].start_of_trace
]
1277 && BB_PARTITION (e2
->dest
) == current_partition
1278 && EDGE_FREQUENCY (e2
) >= freq_threshold
1279 && e2
->count
>= count_threshold
1281 || e2
->probability
> best2
->probability
1282 || (e2
->probability
== best2
->probability
1283 && traces
[bbd
[di
].start_of_trace
].length
1288 if (e2
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1289 best2_len
= traces
[bbd
[di
].start_of_trace
].length
;
1291 best2_len
= INT_MAX
;
1298 if (crtl
->has_bb_partition
)
1301 /* Copy tiny blocks always; copy larger blocks only when the
1302 edge is traversed frequently enough. */
1304 && copy_bb_p (best
->dest
,
1305 optimize_edge_for_speed_p (best
)
1306 && EDGE_FREQUENCY (best
) >= freq_threshold
1307 && best
->count
>= count_threshold
))
1313 fprintf (dump_file
, "Connection: %d %d ",
1314 traces
[t
].last
->index
, best
->dest
->index
);
1316 fputc ('\n', dump_file
);
1317 else if (next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1318 fprintf (dump_file
, "exit\n");
1320 fprintf (dump_file
, "%d\n", next_bb
->index
);
1323 new_bb
= copy_bb (best
->dest
, best
, traces
[t
].last
, t
);
1324 traces
[t
].last
= new_bb
;
1325 if (next_bb
&& next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1327 t
= bbd
[next_bb
->index
].start_of_trace
;
1328 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1329 connected
[t
] = true;
1333 break; /* Stop finding the successor traces. */
1336 break; /* Stop finding the successor traces. */
1345 fprintf (dump_file
, "Final order:\n");
1346 for (bb
= traces
[0].first
; bb
; bb
= (basic_block
) bb
->aux
)
1347 fprintf (dump_file
, "%d ", bb
->index
);
1348 fprintf (dump_file
, "\n");
1355 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1356 when code size is allowed to grow by duplication. */
1359 copy_bb_p (const_basic_block bb
, int code_may_grow
)
1362 int max_size
= uncond_jump_length
;
1367 if (EDGE_COUNT (bb
->preds
) < 2)
1369 if (!can_duplicate_block_p (bb
))
1372 /* Avoid duplicating blocks which have many successors (PR/13430). */
1373 if (EDGE_COUNT (bb
->succs
) > 8)
1376 if (code_may_grow
&& optimize_bb_for_speed_p (bb
))
1377 max_size
*= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS
);
1379 FOR_BB_INSNS (bb
, insn
)
1382 size
+= get_attr_min_length (insn
);
1385 if (size
<= max_size
)
1391 "Block %d can't be copied because its size = %d.\n",
1398 /* Return the length of unconditional jump instruction. */
1401 get_uncond_jump_length (void)
1406 rtx_code_label
*label
= emit_label (gen_label_rtx ());
1407 rtx_insn
*jump
= emit_jump_insn (targetm
.gen_jump (label
));
1408 length
= get_attr_min_length (jump
);
1414 /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1415 Duplicate the landing pad and split the edges so that no EH edge
1416 crosses partitions. */
1419 fix_up_crossing_landing_pad (eh_landing_pad old_lp
, basic_block old_bb
)
1421 eh_landing_pad new_lp
;
1422 basic_block new_bb
, last_bb
, post_bb
;
1424 unsigned new_partition
;
1428 /* Generate the new landing-pad structure. */
1429 new_lp
= gen_eh_landing_pad (old_lp
->region
);
1430 new_lp
->post_landing_pad
= old_lp
->post_landing_pad
;
1431 new_lp
->landing_pad
= gen_label_rtx ();
1432 LABEL_PRESERVE_P (new_lp
->landing_pad
) = 1;
1434 /* Put appropriate instructions in new bb. */
1435 rtx_code_label
*new_label
= emit_label (new_lp
->landing_pad
);
1437 expand_dw2_landing_pad_for_region (old_lp
->region
);
1439 post_bb
= BLOCK_FOR_INSN (old_lp
->landing_pad
);
1440 post_bb
= single_succ (post_bb
);
1441 rtx_code_label
*post_label
= block_label (post_bb
);
1442 jump
= emit_jump_insn (targetm
.gen_jump (post_label
));
1443 JUMP_LABEL (jump
) = post_label
;
1445 /* Create new basic block to be dest for lp. */
1446 last_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
1447 new_bb
= create_basic_block (new_label
, jump
, last_bb
);
1448 new_bb
->aux
= last_bb
->aux
;
1449 new_bb
->frequency
= post_bb
->frequency
;
1450 new_bb
->count
= post_bb
->count
;
1451 last_bb
->aux
= new_bb
;
1453 emit_barrier_after_bb (new_bb
);
1455 make_single_succ_edge (new_bb
, post_bb
, 0);
1457 /* Make sure new bb is in the other partition. */
1458 new_partition
= BB_PARTITION (old_bb
);
1459 new_partition
^= BB_HOT_PARTITION
| BB_COLD_PARTITION
;
1460 BB_SET_PARTITION (new_bb
, new_partition
);
1462 /* Fix up the edges. */
1463 for (ei
= ei_start (old_bb
->preds
); (e
= ei_safe_edge (ei
)) != NULL
; )
1464 if (BB_PARTITION (e
->src
) == new_partition
)
1466 rtx_insn
*insn
= BB_END (e
->src
);
1467 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1469 gcc_assert (note
!= NULL
);
1470 gcc_checking_assert (INTVAL (XEXP (note
, 0)) == old_lp
->index
);
1471 XEXP (note
, 0) = GEN_INT (new_lp
->index
);
1473 /* Adjust the edge to the new destination. */
1474 redirect_edge_succ (e
, new_bb
);
1481 /* Ensure that all hot bbs are included in a hot path through the
1482 procedure. This is done by calling this function twice, once
1483 with WALK_UP true (to look for paths from the entry to hot bbs) and
1484 once with WALK_UP false (to look for paths from hot bbs to the exit).
1485 Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs
1486 to BBS_IN_HOT_PARTITION. */
1489 sanitize_hot_paths (bool walk_up
, unsigned int cold_bb_count
,
1490 vec
<basic_block
> *bbs_in_hot_partition
)
1492 /* Callers check this. */
1493 gcc_checking_assert (cold_bb_count
);
1495 /* Keep examining hot bbs while we still have some left to check
1496 and there are remaining cold bbs. */
1497 vec
<basic_block
> hot_bbs_to_check
= bbs_in_hot_partition
->copy ();
1498 while (! hot_bbs_to_check
.is_empty ()
1501 basic_block bb
= hot_bbs_to_check
.pop ();
1502 vec
<edge
, va_gc
> *edges
= walk_up
? bb
->preds
: bb
->succs
;
1505 profile_probability highest_probability
1506 = profile_probability::uninitialized ();
1507 int highest_freq
= 0;
1508 profile_count highest_count
= profile_count::uninitialized ();
1511 /* Walk the preds/succs and check if there is at least one already
1512 marked hot. Keep track of the most frequent pred/succ so that we
1513 can mark it hot if we don't find one. */
1514 FOR_EACH_EDGE (e
, ei
, edges
)
1516 basic_block reach_bb
= walk_up
? e
->src
: e
->dest
;
1518 if (e
->flags
& EDGE_DFS_BACK
)
1521 if (BB_PARTITION (reach_bb
) != BB_COLD_PARTITION
)
1526 /* The following loop will look for the hottest edge via
1527 the edge count, if it is non-zero, then fallback to the edge
1528 frequency and finally the edge probability. */
1529 if (!highest_count
.initialized_p () || e
->count
> highest_count
)
1530 highest_count
= e
->count
;
1531 int edge_freq
= EDGE_FREQUENCY (e
);
1532 if (edge_freq
> highest_freq
)
1533 highest_freq
= edge_freq
;
1534 if (!highest_probability
.initialized_p ()
1535 || e
->probability
> highest_probability
)
1536 highest_probability
= e
->probability
;
1539 /* If bb is reached by (or reaches, in the case of !WALK_UP) another hot
1540 block (or unpartitioned, e.g. the entry block) then it is ok. If not,
1541 then the most frequent pred (or succ) needs to be adjusted. In the
1542 case where multiple preds/succs have the same frequency (e.g. a
1543 50-50 branch), then both will be adjusted. */
1547 FOR_EACH_EDGE (e
, ei
, edges
)
1549 if (e
->flags
& EDGE_DFS_BACK
)
1551 /* Select the hottest edge using the edge count, if it is non-zero,
1552 then fallback to the edge frequency and finally the edge
1554 if (highest_count
> 0)
1556 if (e
->count
< highest_count
)
1559 else if (highest_freq
)
1561 if (EDGE_FREQUENCY (e
) < highest_freq
)
1564 else if (e
->probability
< highest_probability
)
1567 basic_block reach_bb
= walk_up
? e
->src
: e
->dest
;
1569 /* We have a hot bb with an immediate dominator that is cold.
1570 The dominator needs to be re-marked hot. */
1571 BB_SET_PARTITION (reach_bb
, BB_HOT_PARTITION
);
1574 /* Now we need to examine newly-hot reach_bb to see if it is also
1575 dominated by a cold bb. */
1576 bbs_in_hot_partition
->safe_push (reach_bb
);
1577 hot_bbs_to_check
.safe_push (reach_bb
);
1581 return cold_bb_count
;
1585 /* Find the basic blocks that are rarely executed and need to be moved to
1586 a separate section of the .o file (to cut down on paging and improve
1587 cache locality). Return a vector of all edges that cross. */
1590 find_rarely_executed_basic_blocks_and_crossing_edges (void)
1592 vec
<edge
> crossing_edges
= vNULL
;
1596 unsigned int cold_bb_count
= 0;
1597 auto_vec
<basic_block
> bbs_in_hot_partition
;
1599 /* Mark which partition (hot/cold) each basic block belongs in. */
1600 FOR_EACH_BB_FN (bb
, cfun
)
1602 bool cold_bb
= false;
1604 if (probably_never_executed_bb_p (cfun
, bb
))
1606 /* Handle profile insanities created by upstream optimizations
1607 by also checking the incoming edge weights. If there is a non-cold
1608 incoming edge, conservatively prevent this block from being split
1609 into the cold section. */
1611 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1612 if (!probably_never_executed_edge_p (cfun
, e
))
1620 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
1625 BB_SET_PARTITION (bb
, BB_HOT_PARTITION
);
1626 bbs_in_hot_partition
.safe_push (bb
);
1630 /* Ensure that hot bbs are included along a hot path from the entry to exit.
1631 Several different possibilities may include cold bbs along all paths
1632 to/from a hot bb. One is that there are edge weight insanities
1633 due to optimization phases that do not properly update basic block profile
1634 counts. The second is that the entry of the function may not be hot, because
1635 it is entered fewer times than the number of profile training runs, but there
1636 is a loop inside the function that causes blocks within the function to be
1637 above the threshold for hotness. This is fixed by walking up from hot bbs
1638 to the entry block, and then down from hot bbs to the exit, performing
1639 partitioning fixups as necessary. */
1642 mark_dfs_back_edges ();
1643 cold_bb_count
= sanitize_hot_paths (true, cold_bb_count
,
1644 &bbs_in_hot_partition
);
1646 sanitize_hot_paths (false, cold_bb_count
, &bbs_in_hot_partition
);
1649 /* The format of .gcc_except_table does not allow landing pads to
1650 be in a different partition as the throw. Fix this by either
1651 moving or duplicating the landing pads. */
1652 if (cfun
->eh
->lp_array
)
1657 FOR_EACH_VEC_ELT (*cfun
->eh
->lp_array
, i
, lp
)
1659 bool all_same
, all_diff
;
1662 || lp
->landing_pad
== NULL_RTX
1663 || !LABEL_P (lp
->landing_pad
))
1666 all_same
= all_diff
= true;
1667 bb
= BLOCK_FOR_INSN (lp
->landing_pad
);
1668 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1670 gcc_assert (e
->flags
& EDGE_EH
);
1671 if (BB_PARTITION (bb
) == BB_PARTITION (e
->src
))
1681 int which
= BB_PARTITION (bb
);
1682 which
^= BB_HOT_PARTITION
| BB_COLD_PARTITION
;
1683 BB_SET_PARTITION (bb
, which
);
1686 fix_up_crossing_landing_pad (lp
, bb
);
1690 /* Mark every edge that crosses between sections. */
1692 FOR_EACH_BB_FN (bb
, cfun
)
1693 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1695 unsigned int flags
= e
->flags
;
1697 /* We should never have EDGE_CROSSING set yet. */
1698 gcc_checking_assert ((flags
& EDGE_CROSSING
) == 0);
1700 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1701 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1702 && BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1704 crossing_edges
.safe_push (e
);
1705 flags
|= EDGE_CROSSING
;
1708 /* Now that we've split eh edges as appropriate, allow landing pads
1709 to be merged with the post-landing pads. */
1710 flags
&= ~EDGE_PRESERVE
;
1715 return crossing_edges
;
1718 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
1721 set_edge_can_fallthru_flag (void)
1725 FOR_EACH_BB_FN (bb
, cfun
)
1730 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1732 e
->flags
&= ~EDGE_CAN_FALLTHRU
;
1734 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
1735 if (e
->flags
& EDGE_FALLTHRU
)
1736 e
->flags
|= EDGE_CAN_FALLTHRU
;
1739 /* If the BB ends with an invertible condjump all (2) edges are
1740 CAN_FALLTHRU edges. */
1741 if (EDGE_COUNT (bb
->succs
) != 2)
1743 if (!any_condjump_p (BB_END (bb
)))
1746 rtx_jump_insn
*bb_end_jump
= as_a
<rtx_jump_insn
*> (BB_END (bb
));
1747 if (!invert_jump (bb_end_jump
, JUMP_LABEL (bb_end_jump
), 0))
1749 invert_jump (bb_end_jump
, JUMP_LABEL (bb_end_jump
), 0);
1750 EDGE_SUCC (bb
, 0)->flags
|= EDGE_CAN_FALLTHRU
;
1751 EDGE_SUCC (bb
, 1)->flags
|= EDGE_CAN_FALLTHRU
;
1755 /* If any destination of a crossing edge does not have a label, add label;
1756 Convert any easy fall-through crossing edges to unconditional jumps. */
1759 add_labels_and_missing_jumps (vec
<edge
> crossing_edges
)
1764 FOR_EACH_VEC_ELT (crossing_edges
, i
, e
)
1766 basic_block src
= e
->src
;
1767 basic_block dest
= e
->dest
;
1768 rtx_jump_insn
*new_jump
;
1770 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1773 /* Make sure dest has a label. */
1774 rtx_code_label
*label
= block_label (dest
);
1776 /* Nothing to do for non-fallthru edges. */
1777 if (src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1779 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1782 /* If the block does not end with a control flow insn, then we
1783 can trivially add a jump to the end to fixup the crossing.
1784 Otherwise the jump will have to go in a new bb, which will
1785 be handled by fix_up_fall_thru_edges function. */
1786 if (control_flow_insn_p (BB_END (src
)))
1789 /* Make sure there's only one successor. */
1790 gcc_assert (single_succ_p (src
));
1792 new_jump
= emit_jump_insn_after (targetm
.gen_jump (label
), BB_END (src
));
1793 BB_END (src
) = new_jump
;
1794 JUMP_LABEL (new_jump
) = label
;
1795 LABEL_NUSES (label
) += 1;
1797 emit_barrier_after_bb (src
);
1799 /* Mark edge as non-fallthru. */
1800 e
->flags
&= ~EDGE_FALLTHRU
;
1804 /* Find any bb's where the fall-through edge is a crossing edge (note that
1805 these bb's must also contain a conditional jump or end with a call
1806 instruction; we've already dealt with fall-through edges for blocks
1807 that didn't have a conditional jump or didn't end with call instruction
1808 in the call to add_labels_and_missing_jumps). Convert the fall-through
1809 edge to non-crossing edge by inserting a new bb to fall-through into.
1810 The new bb will contain an unconditional jump (crossing edge) to the
1811 original fall through destination. */
1814 fix_up_fall_thru_edges (void)
1818 FOR_EACH_BB_FN (cur_bb
, cfun
)
1822 edge fall_thru
= NULL
;
1823 edge cond_jump
= NULL
;
1826 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1827 succ1
= EDGE_SUCC (cur_bb
, 0);
1831 if (EDGE_COUNT (cur_bb
->succs
) > 1)
1832 succ2
= EDGE_SUCC (cur_bb
, 1);
1836 /* Find the fall-through edge. */
1839 && (succ1
->flags
& EDGE_FALLTHRU
))
1845 && (succ2
->flags
& EDGE_FALLTHRU
))
1850 else if (succ2
&& EDGE_COUNT (cur_bb
->succs
) > 2)
1851 fall_thru
= find_fallthru_edge (cur_bb
->succs
);
1853 if (fall_thru
&& (fall_thru
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
1855 /* Check to see if the fall-thru edge is a crossing edge. */
1857 if (fall_thru
->flags
& EDGE_CROSSING
)
1859 /* The fall_thru edge crosses; now check the cond jump edge, if
1862 bool cond_jump_crosses
= true;
1863 int invert_worked
= 0;
1864 rtx_insn
*old_jump
= BB_END (cur_bb
);
1866 /* Find the jump instruction, if there is one. */
1870 if (!(cond_jump
->flags
& EDGE_CROSSING
))
1871 cond_jump_crosses
= false;
1873 /* We know the fall-thru edge crosses; if the cond
1874 jump edge does NOT cross, and its destination is the
1875 next block in the bb order, invert the jump
1876 (i.e. fix it so the fall through does not cross and
1877 the cond jump does). */
1879 if (!cond_jump_crosses
)
1881 /* Find label in fall_thru block. We've already added
1882 any missing labels, so there must be one. */
1884 rtx_code_label
*fall_thru_label
1885 = block_label (fall_thru
->dest
);
1887 if (old_jump
&& fall_thru_label
)
1889 rtx_jump_insn
*old_jump_insn
1890 = dyn_cast
<rtx_jump_insn
*> (old_jump
);
1892 invert_worked
= invert_jump (old_jump_insn
,
1893 fall_thru_label
, 0);
1898 fall_thru
->flags
&= ~EDGE_FALLTHRU
;
1899 cond_jump
->flags
|= EDGE_FALLTHRU
;
1900 update_br_prob_note (cur_bb
);
1901 std::swap (fall_thru
, cond_jump
);
1902 cond_jump
->flags
|= EDGE_CROSSING
;
1903 fall_thru
->flags
&= ~EDGE_CROSSING
;
1908 if (cond_jump_crosses
|| !invert_worked
)
1910 /* This is the case where both edges out of the basic
1911 block are crossing edges. Here we will fix up the
1912 fall through edge. The jump edge will be taken care
1913 of later. The EDGE_CROSSING flag of fall_thru edge
1914 is unset before the call to force_nonfallthru
1915 function because if a new basic-block is created
1916 this edge remains in the current section boundary
1917 while the edge between new_bb and the fall_thru->dest
1918 becomes EDGE_CROSSING. */
1920 fall_thru
->flags
&= ~EDGE_CROSSING
;
1921 basic_block new_bb
= force_nonfallthru (fall_thru
);
1925 new_bb
->aux
= cur_bb
->aux
;
1926 cur_bb
->aux
= new_bb
;
1928 /* This is done by force_nonfallthru_and_redirect. */
1929 gcc_assert (BB_PARTITION (new_bb
)
1930 == BB_PARTITION (cur_bb
));
1932 single_succ_edge (new_bb
)->flags
|= EDGE_CROSSING
;
1936 /* If a new basic-block was not created; restore
1937 the EDGE_CROSSING flag. */
1938 fall_thru
->flags
|= EDGE_CROSSING
;
1941 /* Add barrier after new jump */
1942 emit_barrier_after_bb (new_bb
? new_bb
: cur_bb
);
1949 /* This function checks the destination block of a "crossing jump" to
1950 see if it has any crossing predecessors that begin with a code label
1951 and end with an unconditional jump. If so, it returns that predecessor
1952 block. (This is to avoid creating lots of new basic blocks that all
1953 contain unconditional jumps to the same destination). */
1956 find_jump_block (basic_block jump_dest
)
1958 basic_block source_bb
= NULL
;
1963 FOR_EACH_EDGE (e
, ei
, jump_dest
->preds
)
1964 if (e
->flags
& EDGE_CROSSING
)
1966 basic_block src
= e
->src
;
1968 /* Check each predecessor to see if it has a label, and contains
1969 only one executable instruction, which is an unconditional jump.
1970 If so, we can use it. */
1972 if (LABEL_P (BB_HEAD (src
)))
1973 for (insn
= BB_HEAD (src
);
1974 !INSN_P (insn
) && insn
!= NEXT_INSN (BB_END (src
));
1975 insn
= NEXT_INSN (insn
))
1978 && insn
== BB_END (src
)
1980 && !any_condjump_p (insn
))
1994 /* Find all BB's with conditional jumps that are crossing edges;
1995 insert a new bb and make the conditional jump branch to the new
1996 bb instead (make the new bb same color so conditional branch won't
1997 be a 'crossing' edge). Insert an unconditional jump from the
1998 new bb to the original destination of the conditional jump. */
2001 fix_crossing_conditional_branches (void)
2011 rtx old_label
= NULL_RTX
;
2012 rtx_code_label
*new_label
;
2014 FOR_EACH_BB_FN (cur_bb
, cfun
)
2016 crossing_edge
= NULL
;
2017 if (EDGE_COUNT (cur_bb
->succs
) > 0)
2018 succ1
= EDGE_SUCC (cur_bb
, 0);
2022 if (EDGE_COUNT (cur_bb
->succs
) > 1)
2023 succ2
= EDGE_SUCC (cur_bb
, 1);
2027 /* We already took care of fall-through edges, so only one successor
2028 can be a crossing edge. */
2030 if (succ1
&& (succ1
->flags
& EDGE_CROSSING
))
2031 crossing_edge
= succ1
;
2032 else if (succ2
&& (succ2
->flags
& EDGE_CROSSING
))
2033 crossing_edge
= succ2
;
2037 rtx_insn
*old_jump
= BB_END (cur_bb
);
2039 /* Check to make sure the jump instruction is a
2040 conditional jump. */
2044 if (any_condjump_p (old_jump
))
2046 if (GET_CODE (PATTERN (old_jump
)) == SET
)
2047 set_src
= SET_SRC (PATTERN (old_jump
));
2048 else if (GET_CODE (PATTERN (old_jump
)) == PARALLEL
)
2050 set_src
= XVECEXP (PATTERN (old_jump
), 0,0);
2051 if (GET_CODE (set_src
) == SET
)
2052 set_src
= SET_SRC (set_src
);
2058 if (set_src
&& (GET_CODE (set_src
) == IF_THEN_ELSE
))
2060 rtx_jump_insn
*old_jump_insn
=
2061 as_a
<rtx_jump_insn
*> (old_jump
);
2063 if (GET_CODE (XEXP (set_src
, 1)) == PC
)
2064 old_label
= XEXP (set_src
, 2);
2065 else if (GET_CODE (XEXP (set_src
, 2)) == PC
)
2066 old_label
= XEXP (set_src
, 1);
2068 /* Check to see if new bb for jumping to that dest has
2069 already been created; if so, use it; if not, create
2072 new_bb
= find_jump_block (crossing_edge
->dest
);
2075 new_label
= block_label (new_bb
);
2078 basic_block last_bb
;
2079 rtx_code_label
*old_jump_target
;
2080 rtx_jump_insn
*new_jump
;
2082 /* Create new basic block to be dest for
2083 conditional jump. */
2085 /* Put appropriate instructions in new bb. */
2087 new_label
= gen_label_rtx ();
2088 emit_label (new_label
);
2090 gcc_assert (GET_CODE (old_label
) == LABEL_REF
);
2091 old_jump_target
= old_jump_insn
->jump_target ();
2092 new_jump
= as_a
<rtx_jump_insn
*>
2093 (emit_jump_insn (targetm
.gen_jump (old_jump_target
)));
2094 new_jump
->set_jump_target (old_jump_target
);
2096 last_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
2097 new_bb
= create_basic_block (new_label
, new_jump
, last_bb
);
2098 new_bb
->aux
= last_bb
->aux
;
2099 last_bb
->aux
= new_bb
;
2101 emit_barrier_after_bb (new_bb
);
2103 /* Make sure new bb is in same partition as source
2104 of conditional branch. */
2105 BB_COPY_PARTITION (new_bb
, cur_bb
);
2108 /* Make old jump branch to new bb. */
2110 redirect_jump (old_jump_insn
, new_label
, 0);
2112 /* Remove crossing_edge as predecessor of 'dest'. */
2114 dest
= crossing_edge
->dest
;
2116 redirect_edge_succ (crossing_edge
, new_bb
);
2118 /* Make a new edge from new_bb to old dest; new edge
2119 will be a successor for new_bb and a predecessor
2122 if (EDGE_COUNT (new_bb
->succs
) == 0)
2123 new_edge
= make_single_succ_edge (new_bb
, dest
, 0);
2125 new_edge
= EDGE_SUCC (new_bb
, 0);
2127 crossing_edge
->flags
&= ~EDGE_CROSSING
;
2128 new_edge
->flags
|= EDGE_CROSSING
;
2134 /* Find any unconditional branches that cross between hot and cold
2135 sections. Convert them into indirect jumps instead. */
2138 fix_crossing_unconditional_branches (void)
2141 rtx_insn
*last_insn
;
2144 rtx_insn
*indirect_jump_sequence
;
2145 rtx_insn
*jump_insn
= NULL
;
2150 FOR_EACH_BB_FN (cur_bb
, cfun
)
2152 last_insn
= BB_END (cur_bb
);
2154 if (EDGE_COUNT (cur_bb
->succs
) < 1)
2157 succ
= EDGE_SUCC (cur_bb
, 0);
2159 /* Check to see if bb ends in a crossing (unconditional) jump. At
2160 this point, no crossing jumps should be conditional. */
2162 if (JUMP_P (last_insn
)
2163 && (succ
->flags
& EDGE_CROSSING
))
2165 gcc_assert (!any_condjump_p (last_insn
));
2167 /* Make sure the jump is not already an indirect or table jump. */
2169 if (!computed_jump_p (last_insn
)
2170 && !tablejump_p (last_insn
, NULL
, NULL
))
2172 /* We have found a "crossing" unconditional branch. Now
2173 we must convert it to an indirect jump. First create
2174 reference of label, as target for jump. */
2176 label
= JUMP_LABEL (last_insn
);
2177 label_addr
= gen_rtx_LABEL_REF (Pmode
, label
);
2178 LABEL_NUSES (label
) += 1;
2180 /* Get a register to use for the indirect jump. */
2182 new_reg
= gen_reg_rtx (Pmode
);
2184 /* Generate indirect the jump sequence. */
2187 emit_move_insn (new_reg
, label_addr
);
2188 emit_indirect_jump (new_reg
);
2189 indirect_jump_sequence
= get_insns ();
2192 /* Make sure every instruction in the new jump sequence has
2193 its basic block set to be cur_bb. */
2195 for (cur_insn
= indirect_jump_sequence
; cur_insn
;
2196 cur_insn
= NEXT_INSN (cur_insn
))
2198 if (!BARRIER_P (cur_insn
))
2199 BLOCK_FOR_INSN (cur_insn
) = cur_bb
;
2200 if (JUMP_P (cur_insn
))
2201 jump_insn
= cur_insn
;
2204 /* Insert the new (indirect) jump sequence immediately before
2205 the unconditional jump, then delete the unconditional jump. */
2207 emit_insn_before (indirect_jump_sequence
, last_insn
);
2208 delete_insn (last_insn
);
2210 JUMP_LABEL (jump_insn
) = label
;
2211 LABEL_NUSES (label
)++;
2213 /* Make BB_END for cur_bb be the jump instruction (NOT the
2214 barrier instruction at the end of the sequence...). */
2216 BB_END (cur_bb
) = jump_insn
;
2222 /* Update CROSSING_JUMP_P flags on all jump insns. */
2225 update_crossing_jump_flags (void)
2231 FOR_EACH_BB_FN (bb
, cfun
)
2232 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2233 if (e
->flags
& EDGE_CROSSING
)
2235 if (JUMP_P (BB_END (bb
))
2236 /* Some flags were added during fix_up_fall_thru_edges, via
2237 force_nonfallthru_and_redirect. */
2238 && !CROSSING_JUMP_P (BB_END (bb
)))
2239 CROSSING_JUMP_P (BB_END (bb
)) = 1;
2244 /* Reorder basic blocks using the software trace cache (STC) algorithm. */
2247 reorder_basic_blocks_software_trace_cache (void)
2250 fprintf (dump_file
, "\nReordering with the STC algorithm.\n\n");
2254 struct trace
*traces
;
2256 /* We are estimating the length of uncond jump insn only once since the code
2257 for getting the insn length always returns the minimal length now. */
2258 if (uncond_jump_length
== 0)
2259 uncond_jump_length
= get_uncond_jump_length ();
2261 /* We need to know some information for each basic block. */
2262 array_size
= GET_ARRAY_SIZE (last_basic_block_for_fn (cfun
));
2263 bbd
= XNEWVEC (bbro_basic_block_data
, array_size
);
2264 for (i
= 0; i
< array_size
; i
++)
2266 bbd
[i
].start_of_trace
= -1;
2267 bbd
[i
].end_of_trace
= -1;
2268 bbd
[i
].in_trace
= -1;
2270 bbd
[i
].priority
= -1;
2275 traces
= XNEWVEC (struct trace
, n_basic_blocks_for_fn (cfun
));
2277 find_traces (&n_traces
, traces
);
2278 connect_traces (n_traces
, traces
);
2283 /* Return true if edge E1 is more desirable as a fallthrough edge than
2287 edge_order (edge e1
, edge e2
)
2289 return EDGE_FREQUENCY (e1
) > EDGE_FREQUENCY (e2
);
2292 /* Reorder basic blocks using the "simple" algorithm. This tries to
2293 maximize the dynamic number of branches that are fallthrough, without
2294 copying instructions. The algorithm is greedy, looking at the most
2295 frequently executed branch first. */
2298 reorder_basic_blocks_simple (void)
2301 fprintf (dump_file
, "\nReordering with the \"simple\" algorithm.\n\n");
2303 edge
*edges
= new edge
[2 * n_basic_blocks_for_fn (cfun
)];
2305 /* First, collect all edges that can be optimized by reordering blocks:
2306 simple jumps and conditional jumps, as well as the function entry edge. */
2309 edges
[n
++] = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun
), 0);
2312 FOR_EACH_BB_FN (bb
, cfun
)
2314 rtx_insn
*end
= BB_END (bb
);
2316 if (computed_jump_p (end
) || tablejump_p (end
, NULL
, NULL
))
2319 /* We cannot optimize asm goto. */
2320 if (JUMP_P (end
) && extract_asm_operands (end
))
2323 if (single_succ_p (bb
))
2324 edges
[n
++] = EDGE_SUCC (bb
, 0);
2325 else if (any_condjump_p (end
))
2327 edge e0
= EDGE_SUCC (bb
, 0);
2328 edge e1
= EDGE_SUCC (bb
, 1);
2329 /* When optimizing for size it is best to keep the original
2330 fallthrough edges. */
2331 if (e1
->flags
& EDGE_FALLTHRU
)
2338 /* Sort the edges, the most desirable first. When optimizing for size
2339 all edges are equally desirable. */
2341 if (optimize_function_for_speed_p (cfun
))
2342 std::stable_sort (edges
, edges
+ n
, edge_order
);
2344 /* Now decide which of those edges to make fallthrough edges. We set
2345 BB_VISITED if a block already has a fallthrough successor assigned
2346 to it. We make ->AUX of an endpoint point to the opposite endpoint
2347 of a sequence of blocks that fall through, and ->AUX will be NULL
2348 for a block that is in such a sequence but not an endpoint anymore.
2350 To start with, everything points to itself, nothing is assigned yet. */
2352 FOR_ALL_BB_FN (bb
, cfun
)
2355 bb
->flags
&= ~BB_VISITED
;
2358 EXIT_BLOCK_PTR_FOR_FN (cfun
)->aux
= 0;
2360 /* Now for all edges, the most desirable first, see if that edge can
2361 connect two sequences. If it can, update AUX and BB_VISITED; if it
2362 cannot, zero out the edge in the table. */
2364 for (int j
= 0; j
< n
; j
++)
2368 basic_block tail_a
= e
->src
;
2369 basic_block head_b
= e
->dest
;
2370 basic_block head_a
= (basic_block
) tail_a
->aux
;
2371 basic_block tail_b
= (basic_block
) head_b
->aux
;
2373 /* An edge cannot connect two sequences if:
2374 - it crosses partitions;
2375 - its src is not a current endpoint;
2376 - its dest is not a current endpoint;
2377 - or, it would create a loop. */
2379 if (e
->flags
& EDGE_CROSSING
2380 || tail_a
->flags
& BB_VISITED
2382 || (!(head_b
->flags
& BB_VISITED
) && head_b
!= tail_b
)
2383 || tail_a
== tail_b
)
2391 head_a
->aux
= tail_b
;
2392 tail_b
->aux
= head_a
;
2393 tail_a
->flags
|= BB_VISITED
;
2396 /* Put the pieces together, in the same order that the start blocks of
2397 the sequences already had. The hot/cold partitioning gives a little
2398 complication: as a first pass only do this for blocks in the same
2399 partition as the start block, and (if there is anything left to do)
2400 in a second pass handle the other partition. */
2402 basic_block last_tail
= (basic_block
) ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
;
2404 int current_partition
= BB_PARTITION (last_tail
);
2405 bool need_another_pass
= true;
2407 for (int pass
= 0; pass
< 2 && need_another_pass
; pass
++)
2409 need_another_pass
= false;
2411 FOR_EACH_BB_FN (bb
, cfun
)
2412 if ((bb
->flags
& BB_VISITED
&& bb
->aux
) || bb
->aux
== bb
)
2414 if (BB_PARTITION (bb
) != current_partition
)
2416 need_another_pass
= true;
2420 last_tail
->aux
= bb
;
2421 last_tail
= (basic_block
) bb
->aux
;
2424 current_partition
^= BB_HOT_PARTITION
| BB_COLD_PARTITION
;
2429 /* Finally, link all the chosen fallthrough edges. */
2431 for (int j
= 0; j
< n
; j
++)
2433 edges
[j
]->src
->aux
= edges
[j
]->dest
;
2437 /* If the entry edge no longer falls through we have to make a new
2438 block so it can do so again. */
2440 edge e
= EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun
), 0);
2441 if (e
->dest
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
)
2443 force_nonfallthru (e
);
2444 e
->src
->aux
= ENTRY_BLOCK_PTR_FOR_FN (cfun
)->aux
;
2445 BB_COPY_PARTITION (e
->src
, e
->dest
);
2449 /* Reorder basic blocks. The main entry point to this file. */
2452 reorder_basic_blocks (void)
2454 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
2456 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1)
2459 set_edge_can_fallthru_flag ();
2460 mark_dfs_back_edges ();
2462 switch (flag_reorder_blocks_algorithm
)
2464 case REORDER_BLOCKS_ALGORITHM_SIMPLE
:
2465 reorder_basic_blocks_simple ();
2468 case REORDER_BLOCKS_ALGORITHM_STC
:
2469 reorder_basic_blocks_software_trace_cache ();
2476 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
2480 if (dump_flags
& TDF_DETAILS
)
2481 dump_reg_info (dump_file
);
2482 dump_flow_info (dump_file
, dump_flags
);
2485 /* Signal that rtl_verify_flow_info_1 can now verify that there
2486 is at most one switch between hot/cold sections. */
2487 crtl
->bb_reorder_complete
= true;
2490 /* Determine which partition the first basic block in the function
2491 belongs to, then find the first basic block in the current function
2492 that belongs to a different section, and insert a
2493 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
2494 instruction stream. When writing out the assembly code,
2495 encountering this note will make the compiler switch between the
2496 hot and cold text sections. */
2499 insert_section_boundary_note (void)
2502 bool switched_sections
= false;
2503 int current_partition
= 0;
2505 if (!crtl
->has_bb_partition
)
2508 FOR_EACH_BB_FN (bb
, cfun
)
2510 if (!current_partition
)
2511 current_partition
= BB_PARTITION (bb
);
2512 if (BB_PARTITION (bb
) != current_partition
)
2514 gcc_assert (!switched_sections
);
2515 switched_sections
= true;
2516 emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS
, BB_HEAD (bb
));
2517 current_partition
= BB_PARTITION (bb
);
2524 const pass_data pass_data_reorder_blocks
=
2526 RTL_PASS
, /* type */
2528 OPTGROUP_NONE
, /* optinfo_flags */
2529 TV_REORDER_BLOCKS
, /* tv_id */
2530 0, /* properties_required */
2531 0, /* properties_provided */
2532 0, /* properties_destroyed */
2533 0, /* todo_flags_start */
2534 0, /* todo_flags_finish */
2537 class pass_reorder_blocks
: public rtl_opt_pass
2540 pass_reorder_blocks (gcc::context
*ctxt
)
2541 : rtl_opt_pass (pass_data_reorder_blocks
, ctxt
)
2544 /* opt_pass methods: */
2545 virtual bool gate (function
*)
2547 if (targetm
.cannot_modify_jumps_p ())
2549 return (optimize
> 0
2550 && (flag_reorder_blocks
|| flag_reorder_blocks_and_partition
));
2553 virtual unsigned int execute (function
*);
2555 }; // class pass_reorder_blocks
2558 pass_reorder_blocks::execute (function
*fun
)
2562 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2563 splitting possibly introduced more crossjumping opportunities. */
2564 cfg_layout_initialize (CLEANUP_EXPENSIVE
);
2566 reorder_basic_blocks ();
2567 cleanup_cfg (CLEANUP_EXPENSIVE
);
2569 FOR_EACH_BB_FN (bb
, fun
)
2570 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
2571 bb
->aux
= bb
->next_bb
;
2572 cfg_layout_finalize ();
2580 make_pass_reorder_blocks (gcc::context
*ctxt
)
2582 return new pass_reorder_blocks (ctxt
);
2585 /* Duplicate a block (that we already know ends in a computed jump) into its
2586 predecessors, where possible. Return whether anything is changed. */
2588 maybe_duplicate_computed_goto (basic_block bb
, int max_size
)
2590 if (single_pred_p (bb
))
2593 /* Make sure that the block is small enough. */
2595 FOR_BB_INSNS (bb
, insn
)
2598 max_size
-= get_attr_min_length (insn
);
2603 bool changed
= false;
2606 for (ei
= ei_start (bb
->preds
); (e
= ei_safe_edge (ei
)); )
2608 basic_block pred
= e
->src
;
2610 /* Do not duplicate BB into PRED if that is the last predecessor, or if
2611 we cannot merge a copy of BB with PRED. */
2612 if (single_pred_p (bb
)
2613 || !single_succ_p (pred
)
2614 || e
->flags
& EDGE_COMPLEX
2615 || pred
->index
< NUM_FIXED_BLOCKS
2616 || (JUMP_P (BB_END (pred
)) && !simplejump_p (BB_END (pred
)))
2617 || (JUMP_P (BB_END (pred
)) && CROSSING_JUMP_P (BB_END (pred
))))
2624 fprintf (dump_file
, "Duplicating computed goto bb %d into bb %d\n",
2625 bb
->index
, e
->src
->index
);
2627 /* Remember if PRED can be duplicated; if so, the copy of BB merged
2628 with PRED can be duplicated as well. */
2629 bool can_dup_more
= can_duplicate_block_p (pred
);
2631 /* Make a copy of BB, merge it into PRED. */
2632 basic_block copy
= duplicate_block (bb
, e
, NULL
);
2633 emit_barrier_after_bb (copy
);
2634 reorder_insns_nobb (BB_HEAD (copy
), BB_END (copy
), BB_END (pred
));
2635 merge_blocks (pred
, copy
);
2639 /* Try to merge the resulting merged PRED into further predecessors. */
2641 maybe_duplicate_computed_goto (pred
, max_size
);
2647 /* Duplicate the blocks containing computed gotos. This basically unfactors
2648 computed gotos that were factored early on in the compilation process to
2649 speed up edge based data flow. We used to not unfactor them again, which
2650 can seriously pessimize code with many computed jumps in the source code,
2651 such as interpreters. See e.g. PR15242. */
2653 duplicate_computed_gotos (function
*fun
)
2655 /* We are estimating the length of uncond jump insn only once
2656 since the code for getting the insn length always returns
2657 the minimal length now. */
2658 if (uncond_jump_length
== 0)
2659 uncond_jump_length
= get_uncond_jump_length ();
2661 /* Never copy a block larger than this. */
2663 = uncond_jump_length
* PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS
);
2665 bool changed
= false;
2667 /* Try to duplicate all blocks that end in a computed jump and that
2668 can be duplicated at all. */
2670 FOR_EACH_BB_FN (bb
, fun
)
2671 if (computed_jump_p (BB_END (bb
)) && can_duplicate_block_p (bb
))
2672 changed
|= maybe_duplicate_computed_goto (bb
, max_size
);
2674 /* Duplicating blocks will redirect edges and may cause hot blocks
2675 previously reached by both hot and cold blocks to become dominated
2676 only by cold blocks. */
2678 fixup_partitions ();
2683 const pass_data pass_data_duplicate_computed_gotos
=
2685 RTL_PASS
, /* type */
2686 "compgotos", /* name */
2687 OPTGROUP_NONE
, /* optinfo_flags */
2688 TV_REORDER_BLOCKS
, /* tv_id */
2689 0, /* properties_required */
2690 0, /* properties_provided */
2691 0, /* properties_destroyed */
2692 0, /* todo_flags_start */
2693 0, /* todo_flags_finish */
2696 class pass_duplicate_computed_gotos
: public rtl_opt_pass
2699 pass_duplicate_computed_gotos (gcc::context
*ctxt
)
2700 : rtl_opt_pass (pass_data_duplicate_computed_gotos
, ctxt
)
2703 /* opt_pass methods: */
2704 virtual bool gate (function
*);
2705 virtual unsigned int execute (function
*);
2707 }; // class pass_duplicate_computed_gotos
2710 pass_duplicate_computed_gotos::gate (function
*fun
)
2712 if (targetm
.cannot_modify_jumps_p ())
2714 return (optimize
> 0
2715 && flag_expensive_optimizations
2716 && ! optimize_function_for_size_p (fun
));
2720 pass_duplicate_computed_gotos::execute (function
*fun
)
2722 duplicate_computed_gotos (fun
);
2730 make_pass_duplicate_computed_gotos (gcc::context
*ctxt
)
2732 return new pass_duplicate_computed_gotos (ctxt
);
2735 /* This function is the main 'entrance' for the optimization that
2736 partitions hot and cold basic blocks into separate sections of the
2737 .o file (to improve performance and cache locality). Ideally it
2738 would be called after all optimizations that rearrange the CFG have
2739 been called. However part of this optimization may introduce new
2740 register usage, so it must be called before register allocation has
2741 occurred. This means that this optimization is actually called
2742 well before the optimization that reorders basic blocks (see
2745 This optimization checks the feedback information to determine
2746 which basic blocks are hot/cold, updates flags on the basic blocks
2747 to indicate which section they belong in. This information is
2748 later used for writing out sections in the .o file. Because hot
2749 and cold sections can be arbitrarily large (within the bounds of
2750 memory), far beyond the size of a single function, it is necessary
2751 to fix up all edges that cross section boundaries, to make sure the
2752 instructions used can actually span the required distance. The
2753 fixes are described below.
2755 Fall-through edges must be changed into jumps; it is not safe or
2756 legal to fall through across a section boundary. Whenever a
2757 fall-through edge crossing a section boundary is encountered, a new
2758 basic block is inserted (in the same section as the fall-through
2759 source), and the fall through edge is redirected to the new basic
2760 block. The new basic block contains an unconditional jump to the
2761 original fall-through target. (If the unconditional jump is
2762 insufficient to cross section boundaries, that is dealt with a
2763 little later, see below).
2765 In order to deal with architectures that have short conditional
2766 branches (which cannot span all of memory) we take any conditional
2767 jump that attempts to cross a section boundary and add a level of
2768 indirection: it becomes a conditional jump to a new basic block, in
2769 the same section. The new basic block contains an unconditional
2770 jump to the original target, in the other section.
2772 For those architectures whose unconditional branch is also
2773 incapable of reaching all of memory, those unconditional jumps are
2774 converted into indirect jumps, through a register.
2776 IMPORTANT NOTE: This optimization causes some messy interactions
2777 with the cfg cleanup optimizations; those optimizations want to
2778 merge blocks wherever possible, and to collapse indirect jump
2779 sequences (change "A jumps to B jumps to C" directly into "A jumps
2780 to C"). Those optimizations can undo the jump fixes that
2781 partitioning is required to make (see above), in order to ensure
2782 that jumps attempting to cross section boundaries are really able
2783 to cover whatever distance the jump requires (on many architectures
2784 conditional or unconditional jumps are not able to reach all of
2785 memory). Therefore tests have to be inserted into each such
2786 optimization to make sure that it does not undo stuff necessary to
2787 cross partition boundaries. This would be much less of a problem
2788 if we could perform this optimization later in the compilation, but
2789 unfortunately the fact that we may need to create indirect jumps
2790 (through registers) requires that this optimization be performed
2791 before register allocation.
2793 Hot and cold basic blocks are partitioned and put in separate
2794 sections of the .o file, to reduce paging and improve cache
2795 performance (hopefully). This can result in bits of code from the
2796 same function being widely separated in the .o file. However this
2797 is not obvious to the current bb structure. Therefore we must take
2798 care to ensure that: 1). There are no fall_thru edges that cross
2799 between sections; 2). For those architectures which have "short"
2800 conditional branches, all conditional branches that attempt to
2801 cross between sections are converted to unconditional branches;
2802 and, 3). For those architectures which have "short" unconditional
2803 branches, all unconditional branches that attempt to cross between
2804 sections are converted to indirect jumps.
2806 The code for fixing up fall_thru edges that cross between hot and
2807 cold basic blocks does so by creating new basic blocks containing
2808 unconditional branches to the appropriate label in the "other"
2809 section. The new basic block is then put in the same (hot or cold)
2810 section as the original conditional branch, and the fall_thru edge
2811 is modified to fall into the new basic block instead. By adding
2812 this level of indirection we end up with only unconditional branches
2813 crossing between hot and cold sections.
2815 Conditional branches are dealt with by adding a level of indirection.
2816 A new basic block is added in the same (hot/cold) section as the
2817 conditional branch, and the conditional branch is retargeted to the
2818 new basic block. The new basic block contains an unconditional branch
2819 to the original target of the conditional branch (in the other section).
2821 Unconditional branches are dealt with by converting them into
2826 const pass_data pass_data_partition_blocks
=
2828 RTL_PASS
, /* type */
2829 "bbpart", /* name */
2830 OPTGROUP_NONE
, /* optinfo_flags */
2831 TV_REORDER_BLOCKS
, /* tv_id */
2832 PROP_cfglayout
, /* properties_required */
2833 0, /* properties_provided */
2834 0, /* properties_destroyed */
2835 0, /* todo_flags_start */
2836 0, /* todo_flags_finish */
2839 class pass_partition_blocks
: public rtl_opt_pass
2842 pass_partition_blocks (gcc::context
*ctxt
)
2843 : rtl_opt_pass (pass_data_partition_blocks
, ctxt
)
2846 /* opt_pass methods: */
2847 virtual bool gate (function
*);
2848 virtual unsigned int execute (function
*);
2850 }; // class pass_partition_blocks
2853 pass_partition_blocks::gate (function
*fun
)
2855 /* The optimization to partition hot/cold basic blocks into separate
2856 sections of the .o file does not work well with linkonce or with
2857 user defined section attributes. Don't call it if either case
2859 return (flag_reorder_blocks_and_partition
2861 /* See pass_reorder_blocks::gate. We should not partition if
2862 we are going to omit the reordering. */
2863 && optimize_function_for_speed_p (fun
)
2864 && !DECL_COMDAT_GROUP (current_function_decl
)
2865 && !lookup_attribute ("section", DECL_ATTRIBUTES (fun
->decl
)));
2869 pass_partition_blocks::execute (function
*fun
)
2871 vec
<edge
> crossing_edges
;
2873 if (n_basic_blocks_for_fn (fun
) <= NUM_FIXED_BLOCKS
+ 1)
2876 df_set_flags (DF_DEFER_INSN_RESCAN
);
2878 crossing_edges
= find_rarely_executed_basic_blocks_and_crossing_edges ();
2879 if (!crossing_edges
.exists ())
2882 crtl
->has_bb_partition
= true;
2884 /* Make sure the source of any crossing edge ends in a jump and the
2885 destination of any crossing edge has a label. */
2886 add_labels_and_missing_jumps (crossing_edges
);
2888 /* Convert all crossing fall_thru edges to non-crossing fall
2889 thrus to unconditional jumps (that jump to the original fall
2891 fix_up_fall_thru_edges ();
2893 /* If the architecture does not have conditional branches that can
2894 span all of memory, convert crossing conditional branches into
2895 crossing unconditional branches. */
2896 if (!HAS_LONG_COND_BRANCH
)
2897 fix_crossing_conditional_branches ();
2899 /* If the architecture does not have unconditional branches that
2900 can span all of memory, convert crossing unconditional branches
2901 into indirect jumps. Since adding an indirect jump also adds
2902 a new register usage, update the register usage information as
2904 if (!HAS_LONG_UNCOND_BRANCH
)
2905 fix_crossing_unconditional_branches ();
2907 update_crossing_jump_flags ();
2909 /* Clear bb->aux fields that the above routines were using. */
2910 clear_aux_for_blocks ();
2912 crossing_edges
.release ();
2914 /* ??? FIXME: DF generates the bb info for a block immediately.
2915 And by immediately, I mean *during* creation of the block.
2917 #0 df_bb_refs_collect
2918 #1 in df_bb_refs_record
2919 #2 in create_basic_block_structure
2921 Which means that the bb_has_eh_pred test in df_bb_refs_collect
2922 will *always* fail, because no edges can have been added to the
2923 block yet. Which of course means we don't add the right
2924 artificial refs, which means we fail df_verify (much) later.
2926 Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
2927 that we also shouldn't grab data from the new blocks those new
2928 insns are in either. In this way one can create the block, link
2929 it up properly, and have everything Just Work later, when deferred
2930 insns are processed.
2932 In the meantime, we have no other option but to throw away all
2933 of the DF data and recompute it all. */
2934 if (fun
->eh
->lp_array
)
2936 df_finish_pass (true);
2937 df_scan_alloc (NULL
);
2939 /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
2940 data. We blindly generated all of them when creating the new
2941 landing pad. Delete those assignments we don't use. */
2942 df_set_flags (DF_LR_RUN_DCE
);
2952 make_pass_partition_blocks (gcc::context
*ctxt
)
2954 return new pass_partition_blocks (ctxt
);