1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This (greedy) algorithm constructs traces in several rounds.
21 The construction starts from "seeds". The seed for the first round
22 is the entry point of the function. When there are more than one seed,
23 the one with the lowest key in the heap is selected first (see bb_to_key).
24 Then the algorithm repeatedly adds the most probable successor to the end
25 of a trace. Finally it connects the traces.
27 There are two parameters: Branch Threshold and Exec Threshold.
28 If the probability of an edge to a successor of the current basic block is
29 lower than Branch Threshold or its frequency is lower than Exec Threshold,
30 then the successor will be the seed in one of the next rounds.
31 Each round has these parameters lower than the previous one.
32 The last round has to have these parameters set to zero so that the
33 remaining blocks are picked up.
35 The algorithm selects the most probable successor from all unvisited
36 successors and successors that have been added to this trace.
37 The other successors (that has not been "sent" to the next round) will be
38 other seeds for this round and the secondary traces will start from them.
39 If the successor has not been visited in this trace, it is added to the
40 trace (however, there is some heuristic for simple branches).
41 If the successor has been visited in this trace, a loop has been found.
42 If the loop has many iterations, the loop is rotated so that the source
43 block of the most probable edge going out of the loop is the last block
45 If the loop has few iterations and there is no edge from the last block of
46 the loop going out of the loop, the loop header is duplicated.
48 When connecting traces, the algorithm first checks whether there is an edge
49 from the last block of a trace to the first block of another trace.
50 When there are still some unconnected traces it checks whether there exists
51 a basic block BB such that BB is a successor of the last block of a trace
52 and BB is a predecessor of the first block of another trace. In this case,
53 BB is duplicated, added at the end of the first trace and the traces are
55 The rest of traces are simply connected so there will be a jump to the
56 beginning of the rest of traces.
58 The above description is for the full algorithm, which is used when the
59 function is optimized for speed. When the function is optimized for size,
60 in order to reduce long jumps and connect more fallthru edges, the
61 algorithm is modified as follows:
62 (1) Break long traces to short ones. A trace is broken at a block that has
63 multiple predecessors/ successors during trace discovery. When connecting
64 traces, only connect Trace n with Trace n + 1. This change reduces most
65 long jumps compared with the above algorithm.
66 (2) Ignore the edge probability and frequency for fallthru edges.
67 (3) Keep the original order of blocks when there is no chance to fall
68 through. We rely on the results of cfg_cleanup.
70 To implement the change for code size optimization, block's index is
71 selected as the key and all traces are found in one round.
75 "Software Trace Cache"
76 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
77 http://citeseer.nj.nec.com/15361.html
83 #include "coretypes.h"
96 #include "insn-config.h"
101 #include "emit-rtl.h"
107 #include "diagnostic-core.h"
108 #include "toplev.h" /* user_defined_section_attribute */
109 #include "tree-pass.h"
112 #include "cfgbuild.h"
113 #include "cfgcleanup.h"
114 #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 typedef struct bbro_basic_block_data_def
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 /* Which heap is BB in (if any)? */
163 /* Which heap node is BB in (if any)? */
164 bb_heap_node_t
*node
;
165 } bbro_basic_block_data
;
167 /* The current size of the following dynamic array. */
168 static int array_size
;
170 /* The array which holds needed information for basic blocks. */
171 static bbro_basic_block_data
*bbd
;
173 /* To avoid frequent reallocation the size of arrays is greater than needed,
174 the number of elements is (not less than) 1.25 * size_wanted. */
175 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
177 /* Free the memory and set the pointer to NULL. */
178 #define FREE(P) (gcc_assert (P), free (P), P = 0)
180 /* Structure for holding information about a trace. */
183 /* First and last basic block of the trace. */
184 basic_block first
, last
;
186 /* The round of the STC creation which this trace was found in. */
189 /* The length (i.e. the number of basic blocks) of the trace. */
193 /* Maximum frequency and count of one of the entry blocks. */
194 static int max_entry_frequency
;
195 static gcov_type max_entry_count
;
197 /* Local function prototypes. */
198 static void find_traces (int *, struct trace
*);
199 static basic_block
rotate_loop (edge
, struct trace
*, int);
200 static void mark_bb_visited (basic_block
, int);
201 static void find_traces_1_round (int, int, gcov_type
, struct trace
*, int *,
202 int, bb_heap_t
**, int);
203 static basic_block
copy_bb (basic_block
, edge
, basic_block
, int);
204 static long bb_to_key (basic_block
);
205 static bool better_edge_p (const_basic_block
, const_edge
, int, int, int, int,
207 static bool connect_better_edge_p (const_edge
, bool, int, const_edge
,
209 static void connect_traces (int, struct trace
*);
210 static bool copy_bb_p (const_basic_block
, int);
211 static bool push_to_next_round_p (const_basic_block
, int, int, int, gcov_type
);
213 /* Return the trace number in which BB was visited. */
216 bb_visited_trace (const_basic_block bb
)
218 gcc_assert (bb
->index
< array_size
);
219 return bbd
[bb
->index
].visited
;
222 /* This function marks BB that it was visited in trace number TRACE. */
225 mark_bb_visited (basic_block bb
, int trace
)
227 bbd
[bb
->index
].visited
= trace
;
228 if (bbd
[bb
->index
].heap
)
230 bbd
[bb
->index
].heap
->delete_node (bbd
[bb
->index
].node
);
231 bbd
[bb
->index
].heap
= NULL
;
232 bbd
[bb
->index
].node
= NULL
;
236 /* Check to see if bb should be pushed into the next round of trace
237 collections or not. Reasons for pushing the block forward are 1).
238 If the block is cold, we are doing partitioning, and there will be
239 another round (cold partition blocks are not supposed to be
240 collected into traces until the very last round); or 2). There will
241 be another round, and the basic block is not "hot enough" for the
242 current round of trace collection. */
245 push_to_next_round_p (const_basic_block bb
, int round
, int number_of_rounds
,
246 int exec_th
, gcov_type count_th
)
248 bool there_exists_another_round
;
249 bool block_not_hot_enough
;
251 there_exists_another_round
= round
< number_of_rounds
- 1;
253 block_not_hot_enough
= (bb
->frequency
< exec_th
254 || bb
->count
< count_th
255 || probably_never_executed_bb_p (cfun
, bb
));
257 if (there_exists_another_round
258 && block_not_hot_enough
)
264 /* Find the traces for Software Trace Cache. Chain each trace through
265 RBI()->next. Store the number of traces to N_TRACES and description of
269 find_traces (int *n_traces
, struct trace
*traces
)
272 int number_of_rounds
;
275 bb_heap_t
*heap
= new bb_heap_t (LONG_MIN
);
277 /* Add one extra round of trace collection when partitioning hot/cold
278 basic blocks into separate sections. The last round is for all the
279 cold blocks (and ONLY the cold blocks). */
281 number_of_rounds
= N_ROUNDS
- 1;
283 /* Insert entry points of function into heap. */
284 max_entry_frequency
= 0;
286 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
288 bbd
[e
->dest
->index
].heap
= heap
;
289 bbd
[e
->dest
->index
].node
= heap
->insert (bb_to_key (e
->dest
), e
->dest
);
290 if (e
->dest
->frequency
> max_entry_frequency
)
291 max_entry_frequency
= e
->dest
->frequency
;
292 if (e
->dest
->count
> max_entry_count
)
293 max_entry_count
= e
->dest
->count
;
296 /* Find the traces. */
297 for (i
= 0; i
< number_of_rounds
; i
++)
299 gcov_type count_threshold
;
302 fprintf (dump_file
, "STC - round %d\n", i
+ 1);
304 if (max_entry_count
< INT_MAX
/ 1000)
305 count_threshold
= max_entry_count
* exec_threshold
[i
] / 1000;
307 count_threshold
= max_entry_count
/ 1000 * exec_threshold
[i
];
309 find_traces_1_round (REG_BR_PROB_BASE
* branch_threshold
[i
] / 1000,
310 max_entry_frequency
* exec_threshold
[i
] / 1000,
311 count_threshold
, traces
, n_traces
, i
, &heap
,
318 for (i
= 0; i
< *n_traces
; i
++)
321 fprintf (dump_file
, "Trace %d (round %d): ", i
+ 1,
322 traces
[i
].round
+ 1);
323 for (bb
= traces
[i
].first
;
324 bb
!= traces
[i
].last
;
325 bb
= (basic_block
) bb
->aux
)
326 fprintf (dump_file
, "%d [%d] ", bb
->index
, bb
->frequency
);
327 fprintf (dump_file
, "%d [%d]\n", bb
->index
, bb
->frequency
);
333 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
334 (with sequential number TRACE_N). */
337 rotate_loop (edge back_edge
, struct trace
*trace
, int trace_n
)
341 /* Information about the best end (end after rotation) of the loop. */
342 basic_block best_bb
= NULL
;
343 edge best_edge
= NULL
;
345 gcov_type best_count
= -1;
346 /* The best edge is preferred when its destination is not visited yet
347 or is a start block of some trace. */
348 bool is_preferred
= false;
350 /* Find the most frequent edge that goes out from current trace. */
351 bb
= back_edge
->dest
;
357 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
358 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
359 && bb_visited_trace (e
->dest
) != trace_n
360 && (e
->flags
& EDGE_CAN_FALLTHRU
)
361 && !(e
->flags
& EDGE_COMPLEX
))
365 /* The best edge is preferred. */
366 if (!bb_visited_trace (e
->dest
)
367 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
369 /* The current edge E is also preferred. */
370 int freq
= EDGE_FREQUENCY (e
);
371 if (freq
> best_freq
|| e
->count
> best_count
)
374 best_count
= e
->count
;
382 if (!bb_visited_trace (e
->dest
)
383 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
385 /* The current edge E is preferred. */
387 best_freq
= EDGE_FREQUENCY (e
);
388 best_count
= e
->count
;
394 int freq
= EDGE_FREQUENCY (e
);
395 if (!best_edge
|| freq
> best_freq
|| e
->count
> best_count
)
398 best_count
= e
->count
;
405 bb
= (basic_block
) bb
->aux
;
407 while (bb
!= back_edge
->dest
);
411 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
413 if (back_edge
->dest
== trace
->first
)
415 trace
->first
= (basic_block
) best_bb
->aux
;
421 for (prev_bb
= trace
->first
;
422 prev_bb
->aux
!= back_edge
->dest
;
423 prev_bb
= (basic_block
) prev_bb
->aux
)
425 prev_bb
->aux
= best_bb
->aux
;
427 /* Try to get rid of uncond jump to cond jump. */
428 if (single_succ_p (prev_bb
))
430 basic_block header
= single_succ (prev_bb
);
432 /* Duplicate HEADER if it is a small block containing cond jump
434 if (any_condjump_p (BB_END (header
)) && copy_bb_p (header
, 0)
435 && !CROSSING_JUMP_P (BB_END (header
)))
436 copy_bb (header
, single_succ_edge (prev_bb
), prev_bb
, trace_n
);
442 /* We have not found suitable loop tail so do no rotation. */
443 best_bb
= back_edge
->src
;
449 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
450 not include basic blocks whose probability is lower than BRANCH_TH or whose
451 frequency is lower than EXEC_TH into traces (or whose count is lower than
452 COUNT_TH). Store the new traces into TRACES and modify the number of
453 traces *N_TRACES. Set the round (which the trace belongs to) to ROUND.
454 The function expects starting basic blocks to be in *HEAP and will delete
455 *HEAP and store starting points for the next round into new *HEAP. */
458 find_traces_1_round (int branch_th
, int exec_th
, gcov_type count_th
,
459 struct trace
*traces
, int *n_traces
, int round
,
460 bb_heap_t
**heap
, int number_of_rounds
)
462 /* Heap for discarded basic blocks which are possible starting points for
464 bb_heap_t
*new_heap
= new bb_heap_t (LONG_MIN
);
465 bool for_size
= optimize_function_for_size_p (cfun
);
467 while (!(*heap
)->empty ())
475 bb
= (*heap
)->extract_min ();
476 bbd
[bb
->index
].heap
= NULL
;
477 bbd
[bb
->index
].node
= NULL
;
480 fprintf (dump_file
, "Getting bb %d\n", bb
->index
);
482 /* If the BB's frequency is too low, send BB to the next round. When
483 partitioning hot/cold blocks into separate sections, make sure all
484 the cold blocks (and ONLY the cold blocks) go into the (extra) final
485 round. When optimizing for size, do not push to next round. */
488 && push_to_next_round_p (bb
, round
, number_of_rounds
, exec_th
,
491 int key
= bb_to_key (bb
);
492 bbd
[bb
->index
].heap
= new_heap
;
493 bbd
[bb
->index
].node
= new_heap
->insert (key
, bb
);
497 " Possible start point of next round: %d (key: %d)\n",
502 trace
= traces
+ *n_traces
;
504 trace
->round
= round
;
506 bbd
[bb
->index
].in_trace
= *n_traces
;
514 /* The probability and frequency of the best edge. */
515 int best_prob
= INT_MIN
/ 2;
516 int best_freq
= INT_MIN
/ 2;
519 mark_bb_visited (bb
, *n_traces
);
523 fprintf (dump_file
, "Basic block %d was visited in trace %d\n",
524 bb
->index
, *n_traces
- 1);
526 ends_in_call
= block_ends_with_call_p (bb
);
528 /* Select the successor that will be placed after BB. */
529 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
531 gcc_assert (!(e
->flags
& EDGE_FAKE
));
533 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
536 if (bb_visited_trace (e
->dest
)
537 && bb_visited_trace (e
->dest
) != *n_traces
)
540 if (BB_PARTITION (e
->dest
) != BB_PARTITION (bb
))
543 prob
= e
->probability
;
544 freq
= e
->dest
->frequency
;
546 /* The only sensible preference for a call instruction is the
547 fallthru edge. Don't bother selecting anything else. */
550 if (e
->flags
& EDGE_CAN_FALLTHRU
)
559 /* Edge that cannot be fallthru or improbable or infrequent
560 successor (i.e. it is unsuitable successor). When optimizing
561 for size, ignore the probability and frequency. */
562 if (!(e
->flags
& EDGE_CAN_FALLTHRU
) || (e
->flags
& EDGE_COMPLEX
)
563 || ((prob
< branch_th
|| EDGE_FREQUENCY (e
) < exec_th
564 || e
->count
< count_th
) && (!for_size
)))
567 /* If partitioning hot/cold basic blocks, don't consider edges
568 that cross section boundaries. */
570 if (better_edge_p (bb
, e
, prob
, freq
, best_prob
, best_freq
,
579 /* If the best destination has multiple predecessors, and can be
580 duplicated cheaper than a jump, don't allow it to be added
581 to a trace. We'll duplicate it when connecting traces. */
582 if (best_edge
&& EDGE_COUNT (best_edge
->dest
->preds
) >= 2
583 && copy_bb_p (best_edge
->dest
, 0))
586 /* If the best destination has multiple successors or predecessors,
587 don't allow it to be added when optimizing for size. This makes
588 sure predecessors with smaller index are handled before the best
589 destinarion. It breaks long trace and reduces long jumps.
591 Take if-then-else as an example.
597 If we do not remove the best edge B->D/C->D, the final order might
598 be A B D ... C. C is at the end of the program. If D's successors
599 and D are complicated, might need long jumps for A->C and C->D.
600 Similar issue for order: A C D ... B.
602 After removing the best edge, the final result will be ABCD/ ACBD.
603 It does not add jump compared with the previous order. But it
604 reduces the possibility of long jumps. */
605 if (best_edge
&& for_size
606 && (EDGE_COUNT (best_edge
->dest
->succs
) > 1
607 || EDGE_COUNT (best_edge
->dest
->preds
) > 1))
610 /* Add all non-selected successors to the heaps. */
611 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
614 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
615 || bb_visited_trace (e
->dest
))
618 key
= bb_to_key (e
->dest
);
620 if (bbd
[e
->dest
->index
].heap
)
622 /* E->DEST is already in some heap. */
623 if (key
!= bbd
[e
->dest
->index
].node
->get_key ())
628 "Changing key for bb %d from %ld to %ld.\n",
630 (long) bbd
[e
->dest
->index
].node
->get_key (),
633 bbd
[e
->dest
->index
].heap
->replace_key
634 (bbd
[e
->dest
->index
].node
, key
);
639 bb_heap_t
*which_heap
= *heap
;
641 prob
= e
->probability
;
642 freq
= EDGE_FREQUENCY (e
);
644 if (!(e
->flags
& EDGE_CAN_FALLTHRU
)
645 || (e
->flags
& EDGE_COMPLEX
)
646 || prob
< branch_th
|| freq
< exec_th
647 || e
->count
< count_th
)
649 /* When partitioning hot/cold basic blocks, make sure
650 the cold blocks (and only the cold blocks) all get
651 pushed to the last round of trace collection. When
652 optimizing for size, do not push to next round. */
654 if (!for_size
&& push_to_next_round_p (e
->dest
, round
,
657 which_heap
= new_heap
;
660 bbd
[e
->dest
->index
].heap
= which_heap
;
661 bbd
[e
->dest
->index
].node
= which_heap
->insert (key
, e
->dest
);
666 " Possible start of %s round: %d (key: %ld)\n",
667 (which_heap
== new_heap
) ? "next" : "this",
668 e
->dest
->index
, (long) key
);
674 if (best_edge
) /* Suitable successor was found. */
676 if (bb_visited_trace (best_edge
->dest
) == *n_traces
)
678 /* We do nothing with one basic block loops. */
679 if (best_edge
->dest
!= bb
)
681 if (EDGE_FREQUENCY (best_edge
)
682 > 4 * best_edge
->dest
->frequency
/ 5)
684 /* The loop has at least 4 iterations. If the loop
685 header is not the first block of the function
686 we can rotate the loop. */
689 != ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
694 "Rotating loop %d - %d\n",
695 best_edge
->dest
->index
, bb
->index
);
697 bb
->aux
= best_edge
->dest
;
698 bbd
[best_edge
->dest
->index
].in_trace
=
700 bb
= rotate_loop (best_edge
, trace
, *n_traces
);
705 /* The loop has less than 4 iterations. */
707 if (single_succ_p (bb
)
708 && copy_bb_p (best_edge
->dest
,
709 optimize_edge_for_speed_p
712 bb
= copy_bb (best_edge
->dest
, best_edge
, bb
,
719 /* Terminate the trace. */
724 /* Check for a situation
733 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
734 >= EDGE_FREQUENCY (AC).
735 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
736 Best ordering is then A B C.
738 When optimizing for size, A B C is always the best order.
740 This situation is created for example by:
747 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
749 && (e
->flags
& EDGE_CAN_FALLTHRU
)
750 && !(e
->flags
& EDGE_COMPLEX
)
751 && !bb_visited_trace (e
->dest
)
752 && single_pred_p (e
->dest
)
753 && !(e
->flags
& EDGE_CROSSING
)
754 && single_succ_p (e
->dest
)
755 && (single_succ_edge (e
->dest
)->flags
757 && !(single_succ_edge (e
->dest
)->flags
& EDGE_COMPLEX
)
758 && single_succ (e
->dest
) == best_edge
->dest
759 && (2 * e
->dest
->frequency
>= EDGE_FREQUENCY (best_edge
)
764 fprintf (dump_file
, "Selecting BB %d\n",
765 best_edge
->dest
->index
);
769 bb
->aux
= best_edge
->dest
;
770 bbd
[best_edge
->dest
->index
].in_trace
= (*n_traces
) - 1;
771 bb
= best_edge
->dest
;
777 bbd
[trace
->first
->index
].start_of_trace
= *n_traces
- 1;
778 bbd
[trace
->last
->index
].end_of_trace
= *n_traces
- 1;
780 /* The trace is terminated so we have to recount the keys in heap
781 (some block can have a lower key because now one of its predecessors
782 is an end of the trace). */
783 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
785 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
786 || bb_visited_trace (e
->dest
))
789 if (bbd
[e
->dest
->index
].heap
)
791 key
= bb_to_key (e
->dest
);
792 if (key
!= bbd
[e
->dest
->index
].node
->get_key ())
797 "Changing key for bb %d from %ld to %ld.\n",
799 (long) bbd
[e
->dest
->index
].node
->get_key (), key
);
801 bbd
[e
->dest
->index
].heap
->replace_key
802 (bbd
[e
->dest
->index
].node
, key
);
810 /* "Return" the new heap. */
814 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
815 it to trace after BB, mark OLD_BB visited and update pass' data structures
816 (TRACE is a number of trace which OLD_BB is duplicated to). */
819 copy_bb (basic_block old_bb
, edge e
, basic_block bb
, int trace
)
823 new_bb
= duplicate_block (old_bb
, e
, bb
);
824 BB_COPY_PARTITION (new_bb
, old_bb
);
826 gcc_assert (e
->dest
== new_bb
);
830 "Duplicated bb %d (created bb %d)\n",
831 old_bb
->index
, new_bb
->index
);
833 if (new_bb
->index
>= array_size
834 || last_basic_block_for_fn (cfun
) > array_size
)
839 new_size
= MAX (last_basic_block_for_fn (cfun
), new_bb
->index
+ 1);
840 new_size
= GET_ARRAY_SIZE (new_size
);
841 bbd
= XRESIZEVEC (bbro_basic_block_data
, bbd
, new_size
);
842 for (i
= array_size
; i
< new_size
; i
++)
844 bbd
[i
].start_of_trace
= -1;
845 bbd
[i
].end_of_trace
= -1;
846 bbd
[i
].in_trace
= -1;
851 array_size
= new_size
;
856 "Growing the dynamic array to %d elements.\n",
861 gcc_assert (!bb_visited_trace (e
->dest
));
862 mark_bb_visited (new_bb
, trace
);
863 new_bb
->aux
= bb
->aux
;
866 bbd
[new_bb
->index
].in_trace
= trace
;
871 /* Compute and return the key (for the heap) of the basic block BB. */
874 bb_to_key (basic_block bb
)
880 /* Use index as key to align with its original order. */
881 if (optimize_function_for_size_p (cfun
))
884 /* Do not start in probably never executed blocks. */
886 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
887 || probably_never_executed_bb_p (cfun
, bb
))
890 /* Prefer blocks whose predecessor is an end of some trace
891 or whose predecessor edge is EDGE_DFS_BACK. */
892 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
894 if ((e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
895 && bbd
[e
->src
->index
].end_of_trace
>= 0)
896 || (e
->flags
& EDGE_DFS_BACK
))
898 int edge_freq
= EDGE_FREQUENCY (e
);
900 if (edge_freq
> priority
)
901 priority
= edge_freq
;
906 /* The block with priority should have significantly lower key. */
907 return -(100 * BB_FREQ_MAX
+ 100 * priority
+ bb
->frequency
);
909 return -bb
->frequency
;
912 /* Return true when the edge E from basic block BB is better than the temporary
913 best edge (details are in function). The probability of edge E is PROB. The
914 frequency of the successor is FREQ. The current best probability is
915 BEST_PROB, the best frequency is BEST_FREQ.
916 The edge is considered to be equivalent when PROB does not differ much from
917 BEST_PROB; similarly for frequency. */
920 better_edge_p (const_basic_block bb
, const_edge e
, int prob
, int freq
,
921 int best_prob
, int best_freq
, const_edge cur_best_edge
)
925 /* The BEST_* values do not have to be best, but can be a bit smaller than
927 int diff_prob
= best_prob
/ 10;
928 int diff_freq
= best_freq
/ 10;
930 /* The smaller one is better to keep the original order. */
931 if (optimize_function_for_size_p (cfun
))
932 return !cur_best_edge
933 || cur_best_edge
->dest
->index
> e
->dest
->index
;
935 if (prob
> best_prob
+ diff_prob
)
936 /* The edge has higher probability than the temporary best edge. */
937 is_better_edge
= true;
938 else if (prob
< best_prob
- diff_prob
)
939 /* The edge has lower probability than the temporary best edge. */
940 is_better_edge
= false;
941 else if (freq
< best_freq
- diff_freq
)
942 /* The edge and the temporary best edge have almost equivalent
943 probabilities. The higher frequency of a successor now means
944 that there is another edge going into that successor.
945 This successor has lower frequency so it is better. */
946 is_better_edge
= true;
947 else if (freq
> best_freq
+ diff_freq
)
948 /* This successor has higher frequency so it is worse. */
949 is_better_edge
= false;
950 else if (e
->dest
->prev_bb
== bb
)
951 /* The edges have equivalent probabilities and the successors
952 have equivalent frequencies. Select the previous successor. */
953 is_better_edge
= true;
955 is_better_edge
= false;
957 /* If we are doing hot/cold partitioning, make sure that we always favor
958 non-crossing edges over crossing edges. */
961 && flag_reorder_blocks_and_partition
963 && (cur_best_edge
->flags
& EDGE_CROSSING
)
964 && !(e
->flags
& EDGE_CROSSING
))
965 is_better_edge
= true;
967 return is_better_edge
;
970 /* Return true when the edge E is better than the temporary best edge
971 CUR_BEST_EDGE. If SRC_INDEX_P is true, the function compares the src bb of
972 E and CUR_BEST_EDGE; otherwise it will compare the dest bb.
973 BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE.
974 TRACES record the information about traces.
975 When optimizing for size, the edge with smaller index is better.
976 When optimizing for speed, the edge with bigger probability or longer trace
980 connect_better_edge_p (const_edge e
, bool src_index_p
, int best_len
,
981 const_edge cur_best_edge
, struct trace
*traces
)
990 if (optimize_function_for_size_p (cfun
))
992 e_index
= src_index_p
? e
->src
->index
: e
->dest
->index
;
993 b_index
= src_index_p
? cur_best_edge
->src
->index
994 : cur_best_edge
->dest
->index
;
995 /* The smaller one is better to keep the original order. */
996 return b_index
> e_index
;
1001 e_index
= e
->src
->index
;
1003 if (e
->probability
> cur_best_edge
->probability
)
1004 /* The edge has higher probability than the temporary best edge. */
1005 is_better_edge
= true;
1006 else if (e
->probability
< cur_best_edge
->probability
)
1007 /* The edge has lower probability than the temporary best edge. */
1008 is_better_edge
= false;
1009 else if (traces
[bbd
[e_index
].end_of_trace
].length
> best_len
)
1010 /* The edge and the temporary best edge have equivalent probabilities.
1011 The edge with longer trace is better. */
1012 is_better_edge
= true;
1014 is_better_edge
= false;
1018 e_index
= e
->dest
->index
;
1020 if (e
->probability
> cur_best_edge
->probability
)
1021 /* The edge has higher probability than the temporary best edge. */
1022 is_better_edge
= true;
1023 else if (e
->probability
< cur_best_edge
->probability
)
1024 /* The edge has lower probability than the temporary best edge. */
1025 is_better_edge
= false;
1026 else if (traces
[bbd
[e_index
].start_of_trace
].length
> best_len
)
1027 /* The edge and the temporary best edge have equivalent probabilities.
1028 The edge with longer trace is better. */
1029 is_better_edge
= true;
1031 is_better_edge
= false;
1034 return is_better_edge
;
1037 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
1040 connect_traces (int n_traces
, struct trace
*traces
)
1047 int current_partition
;
1049 gcov_type count_threshold
;
1050 bool for_size
= optimize_function_for_size_p (cfun
);
1052 freq_threshold
= max_entry_frequency
* DUPLICATION_THRESHOLD
/ 1000;
1053 if (max_entry_count
< INT_MAX
/ 1000)
1054 count_threshold
= max_entry_count
* DUPLICATION_THRESHOLD
/ 1000;
1056 count_threshold
= max_entry_count
/ 1000 * DUPLICATION_THRESHOLD
;
1058 connected
= XCNEWVEC (bool, n_traces
);
1061 current_partition
= BB_PARTITION (traces
[0].first
);
1064 if (crtl
->has_bb_partition
)
1065 for (i
= 0; i
< n_traces
&& !two_passes
; i
++)
1066 if (BB_PARTITION (traces
[0].first
)
1067 != BB_PARTITION (traces
[i
].first
))
1070 for (i
= 0; i
< n_traces
|| (two_passes
&& current_pass
== 1) ; i
++)
1079 gcc_assert (two_passes
&& current_pass
== 1);
1083 if (current_partition
== BB_HOT_PARTITION
)
1084 current_partition
= BB_COLD_PARTITION
;
1086 current_partition
= BB_HOT_PARTITION
;
1093 && BB_PARTITION (traces
[t
].first
) != current_partition
)
1096 connected
[t
] = true;
1098 /* Find the predecessor traces. */
1099 for (t2
= t
; t2
> 0;)
1104 FOR_EACH_EDGE (e
, ei
, traces
[t2
].first
->preds
)
1106 int si
= e
->src
->index
;
1108 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1109 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1110 && !(e
->flags
& EDGE_COMPLEX
)
1111 && bbd
[si
].end_of_trace
>= 0
1112 && !connected
[bbd
[si
].end_of_trace
]
1113 && (BB_PARTITION (e
->src
) == current_partition
)
1114 && connect_better_edge_p (e
, true, best_len
, best
, traces
))
1117 best_len
= traces
[bbd
[si
].end_of_trace
].length
;
1122 best
->src
->aux
= best
->dest
;
1123 t2
= bbd
[best
->src
->index
].end_of_trace
;
1124 connected
[t2
] = true;
1128 fprintf (dump_file
, "Connection: %d %d\n",
1129 best
->src
->index
, best
->dest
->index
);
1136 if (last_trace
>= 0)
1137 traces
[last_trace
].last
->aux
= traces
[t2
].first
;
1140 /* Find the successor traces. */
1143 /* Find the continuation of the chain. */
1147 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1149 int di
= e
->dest
->index
;
1151 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1152 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1153 && !(e
->flags
& EDGE_COMPLEX
)
1154 && bbd
[di
].start_of_trace
>= 0
1155 && !connected
[bbd
[di
].start_of_trace
]
1156 && (BB_PARTITION (e
->dest
) == current_partition
)
1157 && connect_better_edge_p (e
, false, best_len
, best
, traces
))
1160 best_len
= traces
[bbd
[di
].start_of_trace
].length
;
1167 /* Stop finding the successor traces. */
1170 /* It is OK to connect block n with block n + 1 or a block
1171 before n. For others, only connect to the loop header. */
1172 if (best
->dest
->index
> (traces
[t
].last
->index
+ 1))
1174 int count
= EDGE_COUNT (best
->dest
->preds
);
1176 FOR_EACH_EDGE (e
, ei
, best
->dest
->preds
)
1177 if (e
->flags
& EDGE_DFS_BACK
)
1180 /* If dest has multiple predecessors, skip it. We expect
1181 that one predecessor with smaller index connects with it
1187 /* Only connect Trace n with Trace n + 1. It is conservative
1188 to keep the order as close as possible to the original order.
1189 It also helps to reduce long jumps. */
1190 if (last_trace
!= bbd
[best
->dest
->index
].start_of_trace
- 1)
1194 fprintf (dump_file
, "Connection: %d %d\n",
1195 best
->src
->index
, best
->dest
->index
);
1197 t
= bbd
[best
->dest
->index
].start_of_trace
;
1198 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1199 connected
[t
] = true;
1206 fprintf (dump_file
, "Connection: %d %d\n",
1207 best
->src
->index
, best
->dest
->index
);
1209 t
= bbd
[best
->dest
->index
].start_of_trace
;
1210 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1211 connected
[t
] = true;
1216 /* Try to connect the traces by duplication of 1 block. */
1218 basic_block next_bb
= NULL
;
1219 bool try_copy
= false;
1221 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1222 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1223 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1224 && !(e
->flags
& EDGE_COMPLEX
)
1225 && (!best
|| e
->probability
> best
->probability
))
1231 /* If the destination is a start of a trace which is only
1232 one block long, then no need to search the successor
1233 blocks of the trace. Accept it. */
1234 if (bbd
[e
->dest
->index
].start_of_trace
>= 0
1235 && traces
[bbd
[e
->dest
->index
].start_of_trace
].length
1243 FOR_EACH_EDGE (e2
, ei
, e
->dest
->succs
)
1245 int di
= e2
->dest
->index
;
1247 if (e2
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
1248 || ((e2
->flags
& EDGE_CAN_FALLTHRU
)
1249 && !(e2
->flags
& EDGE_COMPLEX
)
1250 && bbd
[di
].start_of_trace
>= 0
1251 && !connected
[bbd
[di
].start_of_trace
]
1252 && BB_PARTITION (e2
->dest
) == current_partition
1253 && EDGE_FREQUENCY (e2
) >= freq_threshold
1254 && e2
->count
>= count_threshold
1256 || e2
->probability
> best2
->probability
1257 || (e2
->probability
== best2
->probability
1258 && traces
[bbd
[di
].start_of_trace
].length
1263 if (e2
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1264 best2_len
= traces
[bbd
[di
].start_of_trace
].length
;
1266 best2_len
= INT_MAX
;
1273 if (crtl
->has_bb_partition
)
1276 /* Copy tiny blocks always; copy larger blocks only when the
1277 edge is traversed frequently enough. */
1279 && copy_bb_p (best
->dest
,
1280 optimize_edge_for_speed_p (best
)
1281 && EDGE_FREQUENCY (best
) >= freq_threshold
1282 && best
->count
>= count_threshold
))
1288 fprintf (dump_file
, "Connection: %d %d ",
1289 traces
[t
].last
->index
, best
->dest
->index
);
1291 fputc ('\n', dump_file
);
1292 else if (next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1293 fprintf (dump_file
, "exit\n");
1295 fprintf (dump_file
, "%d\n", next_bb
->index
);
1298 new_bb
= copy_bb (best
->dest
, best
, traces
[t
].last
, t
);
1299 traces
[t
].last
= new_bb
;
1300 if (next_bb
&& next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1302 t
= bbd
[next_bb
->index
].start_of_trace
;
1303 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1304 connected
[t
] = true;
1308 break; /* Stop finding the successor traces. */
1311 break; /* Stop finding the successor traces. */
1320 fprintf (dump_file
, "Final order:\n");
1321 for (bb
= traces
[0].first
; bb
; bb
= (basic_block
) bb
->aux
)
1322 fprintf (dump_file
, "%d ", bb
->index
);
1323 fprintf (dump_file
, "\n");
1330 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1331 when code size is allowed to grow by duplication. */
1334 copy_bb_p (const_basic_block bb
, int code_may_grow
)
1337 int max_size
= uncond_jump_length
;
1342 if (EDGE_COUNT (bb
->preds
) < 2)
1344 if (!can_duplicate_block_p (bb
))
1347 /* Avoid duplicating blocks which have many successors (PR/13430). */
1348 if (EDGE_COUNT (bb
->succs
) > 8)
1351 if (code_may_grow
&& optimize_bb_for_speed_p (bb
))
1352 max_size
*= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS
);
1354 FOR_BB_INSNS (bb
, insn
)
1357 size
+= get_attr_min_length (insn
);
1360 if (size
<= max_size
)
1366 "Block %d can't be copied because its size = %d.\n",
1373 /* Return the length of unconditional jump instruction. */
1376 get_uncond_jump_length (void)
1381 rtx_code_label
*label
= emit_label (gen_label_rtx ());
1382 rtx_insn
*jump
= emit_jump_insn (targetm
.gen_jump (label
));
1383 length
= get_attr_min_length (jump
);
1389 /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1390 Duplicate the landing pad and split the edges so that no EH edge
1391 crosses partitions. */
1394 fix_up_crossing_landing_pad (eh_landing_pad old_lp
, basic_block old_bb
)
1396 eh_landing_pad new_lp
;
1397 basic_block new_bb
, last_bb
, post_bb
;
1399 unsigned new_partition
;
1403 /* Generate the new landing-pad structure. */
1404 new_lp
= gen_eh_landing_pad (old_lp
->region
);
1405 new_lp
->post_landing_pad
= old_lp
->post_landing_pad
;
1406 new_lp
->landing_pad
= gen_label_rtx ();
1407 LABEL_PRESERVE_P (new_lp
->landing_pad
) = 1;
1409 /* Put appropriate instructions in new bb. */
1410 rtx_code_label
*new_label
= emit_label (new_lp
->landing_pad
);
1412 expand_dw2_landing_pad_for_region (old_lp
->region
);
1414 post_bb
= BLOCK_FOR_INSN (old_lp
->landing_pad
);
1415 post_bb
= single_succ (post_bb
);
1416 rtx_code_label
*post_label
= block_label (post_bb
);
1417 jump
= emit_jump_insn (targetm
.gen_jump (post_label
));
1418 JUMP_LABEL (jump
) = post_label
;
1420 /* Create new basic block to be dest for lp. */
1421 last_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
1422 new_bb
= create_basic_block (new_label
, jump
, last_bb
);
1423 new_bb
->aux
= last_bb
->aux
;
1424 last_bb
->aux
= new_bb
;
1426 emit_barrier_after_bb (new_bb
);
1428 make_edge (new_bb
, post_bb
, 0);
1430 /* Make sure new bb is in the other partition. */
1431 new_partition
= BB_PARTITION (old_bb
);
1432 new_partition
^= BB_HOT_PARTITION
| BB_COLD_PARTITION
;
1433 BB_SET_PARTITION (new_bb
, new_partition
);
1435 /* Fix up the edges. */
1436 for (ei
= ei_start (old_bb
->preds
); (e
= ei_safe_edge (ei
)) != NULL
; )
1437 if (BB_PARTITION (e
->src
) == new_partition
)
1439 rtx_insn
*insn
= BB_END (e
->src
);
1440 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1442 gcc_assert (note
!= NULL
);
1443 gcc_checking_assert (INTVAL (XEXP (note
, 0)) == old_lp
->index
);
1444 XEXP (note
, 0) = GEN_INT (new_lp
->index
);
1446 /* Adjust the edge to the new destination. */
1447 redirect_edge_succ (e
, new_bb
);
1454 /* Ensure that all hot bbs are included in a hot path through the
1455 procedure. This is done by calling this function twice, once
1456 with WALK_UP true (to look for paths from the entry to hot bbs) and
1457 once with WALK_UP false (to look for paths from hot bbs to the exit).
1458 Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs
1459 to BBS_IN_HOT_PARTITION. */
1462 sanitize_hot_paths (bool walk_up
, unsigned int cold_bb_count
,
1463 vec
<basic_block
> *bbs_in_hot_partition
)
1465 /* Callers check this. */
1466 gcc_checking_assert (cold_bb_count
);
1468 /* Keep examining hot bbs while we still have some left to check
1469 and there are remaining cold bbs. */
1470 vec
<basic_block
> hot_bbs_to_check
= bbs_in_hot_partition
->copy ();
1471 while (! hot_bbs_to_check
.is_empty ()
1474 basic_block bb
= hot_bbs_to_check
.pop ();
1475 vec
<edge
, va_gc
> *edges
= walk_up
? bb
->preds
: bb
->succs
;
1478 int highest_probability
= 0;
1479 int highest_freq
= 0;
1480 gcov_type highest_count
= 0;
1483 /* Walk the preds/succs and check if there is at least one already
1484 marked hot. Keep track of the most frequent pred/succ so that we
1485 can mark it hot if we don't find one. */
1486 FOR_EACH_EDGE (e
, ei
, edges
)
1488 basic_block reach_bb
= walk_up
? e
->src
: e
->dest
;
1490 if (e
->flags
& EDGE_DFS_BACK
)
1493 if (BB_PARTITION (reach_bb
) != BB_COLD_PARTITION
)
1498 /* The following loop will look for the hottest edge via
1499 the edge count, if it is non-zero, then fallback to the edge
1500 frequency and finally the edge probability. */
1501 if (e
->count
> highest_count
)
1502 highest_count
= e
->count
;
1503 int edge_freq
= EDGE_FREQUENCY (e
);
1504 if (edge_freq
> highest_freq
)
1505 highest_freq
= edge_freq
;
1506 if (e
->probability
> highest_probability
)
1507 highest_probability
= e
->probability
;
1510 /* If bb is reached by (or reaches, in the case of !WALK_UP) another hot
1511 block (or unpartitioned, e.g. the entry block) then it is ok. If not,
1512 then the most frequent pred (or succ) needs to be adjusted. In the
1513 case where multiple preds/succs have the same frequency (e.g. a
1514 50-50 branch), then both will be adjusted. */
1518 FOR_EACH_EDGE (e
, ei
, edges
)
1520 if (e
->flags
& EDGE_DFS_BACK
)
1522 /* Select the hottest edge using the edge count, if it is non-zero,
1523 then fallback to the edge frequency and finally the edge
1527 if (e
->count
< highest_count
)
1530 else if (highest_freq
)
1532 if (EDGE_FREQUENCY (e
) < highest_freq
)
1535 else if (e
->probability
< highest_probability
)
1538 basic_block reach_bb
= walk_up
? e
->src
: e
->dest
;
1540 /* We have a hot bb with an immediate dominator that is cold.
1541 The dominator needs to be re-marked hot. */
1542 BB_SET_PARTITION (reach_bb
, BB_HOT_PARTITION
);
1545 /* Now we need to examine newly-hot reach_bb to see if it is also
1546 dominated by a cold bb. */
1547 bbs_in_hot_partition
->safe_push (reach_bb
);
1548 hot_bbs_to_check
.safe_push (reach_bb
);
1552 return cold_bb_count
;
1556 /* Find the basic blocks that are rarely executed and need to be moved to
1557 a separate section of the .o file (to cut down on paging and improve
1558 cache locality). Return a vector of all edges that cross. */
1561 find_rarely_executed_basic_blocks_and_crossing_edges (void)
1563 vec
<edge
> crossing_edges
= vNULL
;
1567 unsigned int cold_bb_count
= 0;
1568 auto_vec
<basic_block
> bbs_in_hot_partition
;
1570 /* Mark which partition (hot/cold) each basic block belongs in. */
1571 FOR_EACH_BB_FN (bb
, cfun
)
1573 bool cold_bb
= false;
1575 if (probably_never_executed_bb_p (cfun
, bb
))
1577 /* Handle profile insanities created by upstream optimizations
1578 by also checking the incoming edge weights. If there is a non-cold
1579 incoming edge, conservatively prevent this block from being split
1580 into the cold section. */
1582 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1583 if (!probably_never_executed_edge_p (cfun
, e
))
1591 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
1596 BB_SET_PARTITION (bb
, BB_HOT_PARTITION
);
1597 bbs_in_hot_partition
.safe_push (bb
);
1601 /* Ensure that hot bbs are included along a hot path from the entry to exit.
1602 Several different possibilities may include cold bbs along all paths
1603 to/from a hot bb. One is that there are edge weight insanities
1604 due to optimization phases that do not properly update basic block profile
1605 counts. The second is that the entry of the function may not be hot, because
1606 it is entered fewer times than the number of profile training runs, but there
1607 is a loop inside the function that causes blocks within the function to be
1608 above the threshold for hotness. This is fixed by walking up from hot bbs
1609 to the entry block, and then down from hot bbs to the exit, performing
1610 partitioning fixups as necessary. */
1613 mark_dfs_back_edges ();
1614 cold_bb_count
= sanitize_hot_paths (true, cold_bb_count
,
1615 &bbs_in_hot_partition
);
1617 sanitize_hot_paths (false, cold_bb_count
, &bbs_in_hot_partition
);
1620 /* The format of .gcc_except_table does not allow landing pads to
1621 be in a different partition as the throw. Fix this by either
1622 moving or duplicating the landing pads. */
1623 if (cfun
->eh
->lp_array
)
1628 FOR_EACH_VEC_ELT (*cfun
->eh
->lp_array
, i
, lp
)
1630 bool all_same
, all_diff
;
1633 || lp
->landing_pad
== NULL_RTX
1634 || !LABEL_P (lp
->landing_pad
))
1637 all_same
= all_diff
= true;
1638 bb
= BLOCK_FOR_INSN (lp
->landing_pad
);
1639 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1641 gcc_assert (e
->flags
& EDGE_EH
);
1642 if (BB_PARTITION (bb
) == BB_PARTITION (e
->src
))
1652 int which
= BB_PARTITION (bb
);
1653 which
^= BB_HOT_PARTITION
| BB_COLD_PARTITION
;
1654 BB_SET_PARTITION (bb
, which
);
1657 fix_up_crossing_landing_pad (lp
, bb
);
1661 /* Mark every edge that crosses between sections. */
1663 FOR_EACH_BB_FN (bb
, cfun
)
1664 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1666 unsigned int flags
= e
->flags
;
1668 /* We should never have EDGE_CROSSING set yet. */
1669 gcc_checking_assert ((flags
& EDGE_CROSSING
) == 0);
1671 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1672 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1673 && BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1675 crossing_edges
.safe_push (e
);
1676 flags
|= EDGE_CROSSING
;
1679 /* Now that we've split eh edges as appropriate, allow landing pads
1680 to be merged with the post-landing pads. */
1681 flags
&= ~EDGE_PRESERVE
;
1686 return crossing_edges
;
1689 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
1692 set_edge_can_fallthru_flag (void)
1696 FOR_EACH_BB_FN (bb
, cfun
)
1701 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1703 e
->flags
&= ~EDGE_CAN_FALLTHRU
;
1705 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
1706 if (e
->flags
& EDGE_FALLTHRU
)
1707 e
->flags
|= EDGE_CAN_FALLTHRU
;
1710 /* If the BB ends with an invertible condjump all (2) edges are
1711 CAN_FALLTHRU edges. */
1712 if (EDGE_COUNT (bb
->succs
) != 2)
1714 if (!any_condjump_p (BB_END (bb
)))
1717 rtx_jump_insn
*bb_end_jump
= as_a
<rtx_jump_insn
*> (BB_END (bb
));
1718 if (!invert_jump (bb_end_jump
, JUMP_LABEL (bb_end_jump
), 0))
1720 invert_jump (bb_end_jump
, JUMP_LABEL (bb_end_jump
), 0);
1721 EDGE_SUCC (bb
, 0)->flags
|= EDGE_CAN_FALLTHRU
;
1722 EDGE_SUCC (bb
, 1)->flags
|= EDGE_CAN_FALLTHRU
;
1726 /* If any destination of a crossing edge does not have a label, add label;
1727 Convert any easy fall-through crossing edges to unconditional jumps. */
1730 add_labels_and_missing_jumps (vec
<edge
> crossing_edges
)
1735 FOR_EACH_VEC_ELT (crossing_edges
, i
, e
)
1737 basic_block src
= e
->src
;
1738 basic_block dest
= e
->dest
;
1739 rtx_jump_insn
*new_jump
;
1741 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1744 /* Make sure dest has a label. */
1745 rtx_code_label
*label
= block_label (dest
);
1747 /* Nothing to do for non-fallthru edges. */
1748 if (src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1750 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1753 /* If the block does not end with a control flow insn, then we
1754 can trivially add a jump to the end to fixup the crossing.
1755 Otherwise the jump will have to go in a new bb, which will
1756 be handled by fix_up_fall_thru_edges function. */
1757 if (control_flow_insn_p (BB_END (src
)))
1760 /* Make sure there's only one successor. */
1761 gcc_assert (single_succ_p (src
));
1763 new_jump
= emit_jump_insn_after (targetm
.gen_jump (label
), BB_END (src
));
1764 BB_END (src
) = new_jump
;
1765 JUMP_LABEL (new_jump
) = label
;
1766 LABEL_NUSES (label
) += 1;
1768 emit_barrier_after_bb (src
);
1770 /* Mark edge as non-fallthru. */
1771 e
->flags
&= ~EDGE_FALLTHRU
;
1775 /* Find any bb's where the fall-through edge is a crossing edge (note that
1776 these bb's must also contain a conditional jump or end with a call
1777 instruction; we've already dealt with fall-through edges for blocks
1778 that didn't have a conditional jump or didn't end with call instruction
1779 in the call to add_labels_and_missing_jumps). Convert the fall-through
1780 edge to non-crossing edge by inserting a new bb to fall-through into.
1781 The new bb will contain an unconditional jump (crossing edge) to the
1782 original fall through destination. */
1785 fix_up_fall_thru_edges (void)
1792 edge cond_jump
= NULL
;
1793 bool cond_jump_crosses
;
1796 rtx_code_label
*fall_thru_label
;
1798 FOR_EACH_BB_FN (cur_bb
, cfun
)
1801 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1802 succ1
= EDGE_SUCC (cur_bb
, 0);
1806 if (EDGE_COUNT (cur_bb
->succs
) > 1)
1807 succ2
= EDGE_SUCC (cur_bb
, 1);
1811 /* Find the fall-through edge. */
1814 && (succ1
->flags
& EDGE_FALLTHRU
))
1820 && (succ2
->flags
& EDGE_FALLTHRU
))
1826 && (block_ends_with_call_p (cur_bb
)
1827 || can_throw_internal (BB_END (cur_bb
))))
1832 FOR_EACH_EDGE (e
, ei
, cur_bb
->succs
)
1833 if (e
->flags
& EDGE_FALLTHRU
)
1840 if (fall_thru
&& (fall_thru
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
1842 /* Check to see if the fall-thru edge is a crossing edge. */
1844 if (fall_thru
->flags
& EDGE_CROSSING
)
1846 /* The fall_thru edge crosses; now check the cond jump edge, if
1849 cond_jump_crosses
= true;
1851 old_jump
= BB_END (cur_bb
);
1853 /* Find the jump instruction, if there is one. */
1857 if (!(cond_jump
->flags
& EDGE_CROSSING
))
1858 cond_jump_crosses
= false;
1860 /* We know the fall-thru edge crosses; if the cond
1861 jump edge does NOT cross, and its destination is the
1862 next block in the bb order, invert the jump
1863 (i.e. fix it so the fall through does not cross and
1864 the cond jump does). */
1866 if (!cond_jump_crosses
)
1868 /* Find label in fall_thru block. We've already added
1869 any missing labels, so there must be one. */
1871 fall_thru_label
= block_label (fall_thru
->dest
);
1873 if (old_jump
&& fall_thru_label
)
1875 rtx_jump_insn
*old_jump_insn
=
1876 dyn_cast
<rtx_jump_insn
*> (old_jump
);
1878 invert_worked
= invert_jump (old_jump_insn
,
1879 fall_thru_label
, 0);
1884 fall_thru
->flags
&= ~EDGE_FALLTHRU
;
1885 cond_jump
->flags
|= EDGE_FALLTHRU
;
1886 update_br_prob_note (cur_bb
);
1887 std::swap (fall_thru
, cond_jump
);
1888 cond_jump
->flags
|= EDGE_CROSSING
;
1889 fall_thru
->flags
&= ~EDGE_CROSSING
;
1894 if (cond_jump_crosses
|| !invert_worked
)
1896 /* This is the case where both edges out of the basic
1897 block are crossing edges. Here we will fix up the
1898 fall through edge. The jump edge will be taken care
1899 of later. The EDGE_CROSSING flag of fall_thru edge
1900 is unset before the call to force_nonfallthru
1901 function because if a new basic-block is created
1902 this edge remains in the current section boundary
1903 while the edge between new_bb and the fall_thru->dest
1904 becomes EDGE_CROSSING. */
1906 fall_thru
->flags
&= ~EDGE_CROSSING
;
1907 new_bb
= force_nonfallthru (fall_thru
);
1911 new_bb
->aux
= cur_bb
->aux
;
1912 cur_bb
->aux
= new_bb
;
1914 /* This is done by force_nonfallthru_and_redirect. */
1915 gcc_assert (BB_PARTITION (new_bb
)
1916 == BB_PARTITION (cur_bb
));
1918 single_succ_edge (new_bb
)->flags
|= EDGE_CROSSING
;
1922 /* If a new basic-block was not created; restore
1923 the EDGE_CROSSING flag. */
1924 fall_thru
->flags
|= EDGE_CROSSING
;
1927 /* Add barrier after new jump */
1928 emit_barrier_after_bb (new_bb
? new_bb
: cur_bb
);
1935 /* This function checks the destination block of a "crossing jump" to
1936 see if it has any crossing predecessors that begin with a code label
1937 and end with an unconditional jump. If so, it returns that predecessor
1938 block. (This is to avoid creating lots of new basic blocks that all
1939 contain unconditional jumps to the same destination). */
1942 find_jump_block (basic_block jump_dest
)
1944 basic_block source_bb
= NULL
;
1949 FOR_EACH_EDGE (e
, ei
, jump_dest
->preds
)
1950 if (e
->flags
& EDGE_CROSSING
)
1952 basic_block src
= e
->src
;
1954 /* Check each predecessor to see if it has a label, and contains
1955 only one executable instruction, which is an unconditional jump.
1956 If so, we can use it. */
1958 if (LABEL_P (BB_HEAD (src
)))
1959 for (insn
= BB_HEAD (src
);
1960 !INSN_P (insn
) && insn
!= NEXT_INSN (BB_END (src
));
1961 insn
= NEXT_INSN (insn
))
1964 && insn
== BB_END (src
)
1966 && !any_condjump_p (insn
))
1980 /* Find all BB's with conditional jumps that are crossing edges;
1981 insert a new bb and make the conditional jump branch to the new
1982 bb instead (make the new bb same color so conditional branch won't
1983 be a 'crossing' edge). Insert an unconditional jump from the
1984 new bb to the original destination of the conditional jump. */
1987 fix_crossing_conditional_branches (void)
1997 rtx old_label
= NULL_RTX
;
1998 rtx_code_label
*new_label
;
2000 FOR_EACH_BB_FN (cur_bb
, cfun
)
2002 crossing_edge
= NULL
;
2003 if (EDGE_COUNT (cur_bb
->succs
) > 0)
2004 succ1
= EDGE_SUCC (cur_bb
, 0);
2008 if (EDGE_COUNT (cur_bb
->succs
) > 1)
2009 succ2
= EDGE_SUCC (cur_bb
, 1);
2013 /* We already took care of fall-through edges, so only one successor
2014 can be a crossing edge. */
2016 if (succ1
&& (succ1
->flags
& EDGE_CROSSING
))
2017 crossing_edge
= succ1
;
2018 else if (succ2
&& (succ2
->flags
& EDGE_CROSSING
))
2019 crossing_edge
= succ2
;
2023 rtx_insn
*old_jump
= BB_END (cur_bb
);
2025 /* Check to make sure the jump instruction is a
2026 conditional jump. */
2030 if (any_condjump_p (old_jump
))
2032 if (GET_CODE (PATTERN (old_jump
)) == SET
)
2033 set_src
= SET_SRC (PATTERN (old_jump
));
2034 else if (GET_CODE (PATTERN (old_jump
)) == PARALLEL
)
2036 set_src
= XVECEXP (PATTERN (old_jump
), 0,0);
2037 if (GET_CODE (set_src
) == SET
)
2038 set_src
= SET_SRC (set_src
);
2044 if (set_src
&& (GET_CODE (set_src
) == IF_THEN_ELSE
))
2046 rtx_jump_insn
*old_jump_insn
=
2047 as_a
<rtx_jump_insn
*> (old_jump
);
2049 if (GET_CODE (XEXP (set_src
, 1)) == PC
)
2050 old_label
= XEXP (set_src
, 2);
2051 else if (GET_CODE (XEXP (set_src
, 2)) == PC
)
2052 old_label
= XEXP (set_src
, 1);
2054 /* Check to see if new bb for jumping to that dest has
2055 already been created; if so, use it; if not, create
2058 new_bb
= find_jump_block (crossing_edge
->dest
);
2061 new_label
= block_label (new_bb
);
2064 basic_block last_bb
;
2065 rtx_code_label
*old_jump_target
;
2066 rtx_jump_insn
*new_jump
;
2068 /* Create new basic block to be dest for
2069 conditional jump. */
2071 /* Put appropriate instructions in new bb. */
2073 new_label
= gen_label_rtx ();
2074 emit_label (new_label
);
2076 gcc_assert (GET_CODE (old_label
) == LABEL_REF
);
2077 old_jump_target
= old_jump_insn
->jump_target ();
2078 new_jump
= as_a
<rtx_jump_insn
*>
2079 (emit_jump_insn (targetm
.gen_jump (old_jump_target
)));
2080 new_jump
->set_jump_target (old_jump_target
);
2082 last_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
2083 new_bb
= create_basic_block (new_label
, new_jump
, last_bb
);
2084 new_bb
->aux
= last_bb
->aux
;
2085 last_bb
->aux
= new_bb
;
2087 emit_barrier_after_bb (new_bb
);
2089 /* Make sure new bb is in same partition as source
2090 of conditional branch. */
2091 BB_COPY_PARTITION (new_bb
, cur_bb
);
2094 /* Make old jump branch to new bb. */
2096 redirect_jump (old_jump_insn
, new_label
, 0);
2098 /* Remove crossing_edge as predecessor of 'dest'. */
2100 dest
= crossing_edge
->dest
;
2102 redirect_edge_succ (crossing_edge
, new_bb
);
2104 /* Make a new edge from new_bb to old dest; new edge
2105 will be a successor for new_bb and a predecessor
2108 if (EDGE_COUNT (new_bb
->succs
) == 0)
2109 new_edge
= make_edge (new_bb
, dest
, 0);
2111 new_edge
= EDGE_SUCC (new_bb
, 0);
2113 crossing_edge
->flags
&= ~EDGE_CROSSING
;
2114 new_edge
->flags
|= EDGE_CROSSING
;
2120 /* Find any unconditional branches that cross between hot and cold
2121 sections. Convert them into indirect jumps instead. */
2124 fix_crossing_unconditional_branches (void)
2127 rtx_insn
*last_insn
;
2130 rtx_insn
*indirect_jump_sequence
;
2131 rtx_insn
*jump_insn
= NULL
;
2136 FOR_EACH_BB_FN (cur_bb
, cfun
)
2138 last_insn
= BB_END (cur_bb
);
2140 if (EDGE_COUNT (cur_bb
->succs
) < 1)
2143 succ
= EDGE_SUCC (cur_bb
, 0);
2145 /* Check to see if bb ends in a crossing (unconditional) jump. At
2146 this point, no crossing jumps should be conditional. */
2148 if (JUMP_P (last_insn
)
2149 && (succ
->flags
& EDGE_CROSSING
))
2151 gcc_assert (!any_condjump_p (last_insn
));
2153 /* Make sure the jump is not already an indirect or table jump. */
2155 if (!computed_jump_p (last_insn
)
2156 && !tablejump_p (last_insn
, NULL
, NULL
))
2158 /* We have found a "crossing" unconditional branch. Now
2159 we must convert it to an indirect jump. First create
2160 reference of label, as target for jump. */
2162 label
= JUMP_LABEL (last_insn
);
2163 label_addr
= gen_rtx_LABEL_REF (Pmode
, label
);
2164 LABEL_NUSES (label
) += 1;
2166 /* Get a register to use for the indirect jump. */
2168 new_reg
= gen_reg_rtx (Pmode
);
2170 /* Generate indirect the jump sequence. */
2173 emit_move_insn (new_reg
, label_addr
);
2174 emit_indirect_jump (new_reg
);
2175 indirect_jump_sequence
= get_insns ();
2178 /* Make sure every instruction in the new jump sequence has
2179 its basic block set to be cur_bb. */
2181 for (cur_insn
= indirect_jump_sequence
; cur_insn
;
2182 cur_insn
= NEXT_INSN (cur_insn
))
2184 if (!BARRIER_P (cur_insn
))
2185 BLOCK_FOR_INSN (cur_insn
) = cur_bb
;
2186 if (JUMP_P (cur_insn
))
2187 jump_insn
= cur_insn
;
2190 /* Insert the new (indirect) jump sequence immediately before
2191 the unconditional jump, then delete the unconditional jump. */
2193 emit_insn_before (indirect_jump_sequence
, last_insn
);
2194 delete_insn (last_insn
);
2196 JUMP_LABEL (jump_insn
) = label
;
2197 LABEL_NUSES (label
)++;
2199 /* Make BB_END for cur_bb be the jump instruction (NOT the
2200 barrier instruction at the end of the sequence...). */
2202 BB_END (cur_bb
) = jump_insn
;
2208 /* Update CROSSING_JUMP_P flags on all jump insns. */
2211 update_crossing_jump_flags (void)
2217 FOR_EACH_BB_FN (bb
, cfun
)
2218 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2219 if (e
->flags
& EDGE_CROSSING
)
2221 if (JUMP_P (BB_END (bb
))
2222 /* Some flags were added during fix_up_fall_thru_edges, via
2223 force_nonfallthru_and_redirect. */
2224 && !CROSSING_JUMP_P (BB_END (bb
)))
2225 CROSSING_JUMP_P (BB_END (bb
)) = 1;
2230 /* Reorder basic blocks. The main entry point to this file. FLAGS is
2231 the set of flags to pass to cfg_layout_initialize(). */
2234 reorder_basic_blocks (void)
2238 struct trace
*traces
;
2240 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
2242 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1)
2245 set_edge_can_fallthru_flag ();
2246 mark_dfs_back_edges ();
2248 /* We are estimating the length of uncond jump insn only once since the code
2249 for getting the insn length always returns the minimal length now. */
2250 if (uncond_jump_length
== 0)
2251 uncond_jump_length
= get_uncond_jump_length ();
2253 /* We need to know some information for each basic block. */
2254 array_size
= GET_ARRAY_SIZE (last_basic_block_for_fn (cfun
));
2255 bbd
= XNEWVEC (bbro_basic_block_data
, array_size
);
2256 for (i
= 0; i
< array_size
; i
++)
2258 bbd
[i
].start_of_trace
= -1;
2259 bbd
[i
].end_of_trace
= -1;
2260 bbd
[i
].in_trace
= -1;
2266 traces
= XNEWVEC (struct trace
, n_basic_blocks_for_fn (cfun
));
2268 find_traces (&n_traces
, traces
);
2269 connect_traces (n_traces
, traces
);
2273 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
2277 if (dump_flags
& TDF_DETAILS
)
2278 dump_reg_info (dump_file
);
2279 dump_flow_info (dump_file
, dump_flags
);
2282 /* Signal that rtl_verify_flow_info_1 can now verify that there
2283 is at most one switch between hot/cold sections. */
2284 crtl
->bb_reorder_complete
= true;
2287 /* Determine which partition the first basic block in the function
2288 belongs to, then find the first basic block in the current function
2289 that belongs to a different section, and insert a
2290 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
2291 instruction stream. When writing out the assembly code,
2292 encountering this note will make the compiler switch between the
2293 hot and cold text sections. */
2296 insert_section_boundary_note (void)
2299 bool switched_sections
= false;
2300 int current_partition
= 0;
2302 if (!crtl
->has_bb_partition
)
2305 FOR_EACH_BB_FN (bb
, cfun
)
2307 if (!current_partition
)
2308 current_partition
= BB_PARTITION (bb
);
2309 if (BB_PARTITION (bb
) != current_partition
)
2311 gcc_assert (!switched_sections
);
2312 switched_sections
= true;
2313 emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS
, BB_HEAD (bb
));
2314 current_partition
= BB_PARTITION (bb
);
2321 const pass_data pass_data_reorder_blocks
=
2323 RTL_PASS
, /* type */
2325 OPTGROUP_NONE
, /* optinfo_flags */
2326 TV_REORDER_BLOCKS
, /* tv_id */
2327 0, /* properties_required */
2328 0, /* properties_provided */
2329 0, /* properties_destroyed */
2330 0, /* todo_flags_start */
2331 0, /* todo_flags_finish */
2334 class pass_reorder_blocks
: public rtl_opt_pass
2337 pass_reorder_blocks (gcc::context
*ctxt
)
2338 : rtl_opt_pass (pass_data_reorder_blocks
, ctxt
)
2341 /* opt_pass methods: */
2342 virtual bool gate (function
*)
2344 if (targetm
.cannot_modify_jumps_p ())
2346 return (optimize
> 0
2347 && (flag_reorder_blocks
|| flag_reorder_blocks_and_partition
));
2350 virtual unsigned int execute (function
*);
2352 }; // class pass_reorder_blocks
2355 pass_reorder_blocks::execute (function
*fun
)
2359 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2360 splitting possibly introduced more crossjumping opportunities. */
2361 cfg_layout_initialize (CLEANUP_EXPENSIVE
);
2363 reorder_basic_blocks ();
2364 cleanup_cfg (CLEANUP_EXPENSIVE
);
2366 FOR_EACH_BB_FN (bb
, fun
)
2367 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
2368 bb
->aux
= bb
->next_bb
;
2369 cfg_layout_finalize ();
2377 make_pass_reorder_blocks (gcc::context
*ctxt
)
2379 return new pass_reorder_blocks (ctxt
);
2382 /* Duplicate the blocks containing computed gotos. This basically unfactors
2383 computed gotos that were factored early on in the compilation process to
2384 speed up edge based data flow. We used to not unfactoring them again,
2385 which can seriously pessimize code with many computed jumps in the source
2386 code, such as interpreters. See e.g. PR15242. */
2390 const pass_data pass_data_duplicate_computed_gotos
=
2392 RTL_PASS
, /* type */
2393 "compgotos", /* name */
2394 OPTGROUP_NONE
, /* optinfo_flags */
2395 TV_REORDER_BLOCKS
, /* tv_id */
2396 0, /* properties_required */
2397 0, /* properties_provided */
2398 0, /* properties_destroyed */
2399 0, /* todo_flags_start */
2400 0, /* todo_flags_finish */
2403 class pass_duplicate_computed_gotos
: public rtl_opt_pass
2406 pass_duplicate_computed_gotos (gcc::context
*ctxt
)
2407 : rtl_opt_pass (pass_data_duplicate_computed_gotos
, ctxt
)
2410 /* opt_pass methods: */
2411 virtual bool gate (function
*);
2412 virtual unsigned int execute (function
*);
2414 }; // class pass_duplicate_computed_gotos
2417 pass_duplicate_computed_gotos::gate (function
*fun
)
2419 if (targetm
.cannot_modify_jumps_p ())
2421 return (optimize
> 0
2422 && flag_expensive_optimizations
2423 && ! optimize_function_for_size_p (fun
));
2427 pass_duplicate_computed_gotos::execute (function
*fun
)
2429 basic_block bb
, new_bb
;
2432 bool changed
= false;
2434 if (n_basic_blocks_for_fn (fun
) <= NUM_FIXED_BLOCKS
+ 1)
2438 cfg_layout_initialize (0);
2440 /* We are estimating the length of uncond jump insn only once
2441 since the code for getting the insn length always returns
2442 the minimal length now. */
2443 if (uncond_jump_length
== 0)
2444 uncond_jump_length
= get_uncond_jump_length ();
2447 = uncond_jump_length
* PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS
);
2448 candidates
= BITMAP_ALLOC (NULL
);
2450 /* Look for blocks that end in a computed jump, and see if such blocks
2451 are suitable for unfactoring. If a block is a candidate for unfactoring,
2452 mark it in the candidates. */
2453 FOR_EACH_BB_FN (bb
, fun
)
2458 int size
, all_flags
;
2460 /* Build the reorder chain for the original order of blocks. */
2461 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
2462 bb
->aux
= bb
->next_bb
;
2464 /* Obviously the block has to end in a computed jump. */
2465 if (!computed_jump_p (BB_END (bb
)))
2468 /* Only consider blocks that can be duplicated. */
2469 if (CROSSING_JUMP_P (BB_END (bb
))
2470 || !can_duplicate_block_p (bb
))
2473 /* Make sure that the block is small enough. */
2475 FOR_BB_INSNS (bb
, insn
)
2478 size
+= get_attr_min_length (insn
);
2479 if (size
> max_size
)
2482 if (size
> max_size
)
2485 /* Final check: there must not be any incoming abnormal edges. */
2487 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2488 all_flags
|= e
->flags
;
2489 if (all_flags
& EDGE_COMPLEX
)
2492 bitmap_set_bit (candidates
, bb
->index
);
2495 /* Nothing to do if there is no computed jump here. */
2496 if (bitmap_empty_p (candidates
))
2499 /* Duplicate computed gotos. */
2500 FOR_EACH_BB_FN (bb
, fun
)
2502 if (bb
->flags
& BB_VISITED
)
2505 bb
->flags
|= BB_VISITED
;
2507 /* BB must have one outgoing edge. That edge must not lead to
2508 the exit block or the next block.
2509 The destination must have more than one predecessor. */
2510 if (!single_succ_p (bb
)
2511 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (fun
)
2512 || single_succ (bb
) == bb
->next_bb
2513 || single_pred_p (single_succ (bb
)))
2516 /* The successor block has to be a duplication candidate. */
2517 if (!bitmap_bit_p (candidates
, single_succ (bb
)->index
))
2520 /* Don't duplicate a partition crossing edge, which requires difficult
2522 if (JUMP_P (BB_END (bb
)) && CROSSING_JUMP_P (BB_END (bb
)))
2525 new_bb
= duplicate_block (single_succ (bb
), single_succ_edge (bb
), bb
);
2526 new_bb
->aux
= bb
->aux
;
2528 new_bb
->flags
|= BB_VISITED
;
2535 /* Duplicating blocks above will redirect edges and may cause hot
2536 blocks previously reached by both hot and cold blocks to become
2537 dominated only by cold blocks. */
2538 fixup_partitions ();
2540 /* Merge the duplicated blocks into predecessors, when possible. */
2541 cfg_layout_finalize ();
2545 cfg_layout_finalize ();
2547 BITMAP_FREE (candidates
);
2554 make_pass_duplicate_computed_gotos (gcc::context
*ctxt
)
2556 return new pass_duplicate_computed_gotos (ctxt
);
2559 /* This function is the main 'entrance' for the optimization that
2560 partitions hot and cold basic blocks into separate sections of the
2561 .o file (to improve performance and cache locality). Ideally it
2562 would be called after all optimizations that rearrange the CFG have
2563 been called. However part of this optimization may introduce new
2564 register usage, so it must be called before register allocation has
2565 occurred. This means that this optimization is actually called
2566 well before the optimization that reorders basic blocks (see
2569 This optimization checks the feedback information to determine
2570 which basic blocks are hot/cold, updates flags on the basic blocks
2571 to indicate which section they belong in. This information is
2572 later used for writing out sections in the .o file. Because hot
2573 and cold sections can be arbitrarily large (within the bounds of
2574 memory), far beyond the size of a single function, it is necessary
2575 to fix up all edges that cross section boundaries, to make sure the
2576 instructions used can actually span the required distance. The
2577 fixes are described below.
2579 Fall-through edges must be changed into jumps; it is not safe or
2580 legal to fall through across a section boundary. Whenever a
2581 fall-through edge crossing a section boundary is encountered, a new
2582 basic block is inserted (in the same section as the fall-through
2583 source), and the fall through edge is redirected to the new basic
2584 block. The new basic block contains an unconditional jump to the
2585 original fall-through target. (If the unconditional jump is
2586 insufficient to cross section boundaries, that is dealt with a
2587 little later, see below).
2589 In order to deal with architectures that have short conditional
2590 branches (which cannot span all of memory) we take any conditional
2591 jump that attempts to cross a section boundary and add a level of
2592 indirection: it becomes a conditional jump to a new basic block, in
2593 the same section. The new basic block contains an unconditional
2594 jump to the original target, in the other section.
2596 For those architectures whose unconditional branch is also
2597 incapable of reaching all of memory, those unconditional jumps are
2598 converted into indirect jumps, through a register.
2600 IMPORTANT NOTE: This optimization causes some messy interactions
2601 with the cfg cleanup optimizations; those optimizations want to
2602 merge blocks wherever possible, and to collapse indirect jump
2603 sequences (change "A jumps to B jumps to C" directly into "A jumps
2604 to C"). Those optimizations can undo the jump fixes that
2605 partitioning is required to make (see above), in order to ensure
2606 that jumps attempting to cross section boundaries are really able
2607 to cover whatever distance the jump requires (on many architectures
2608 conditional or unconditional jumps are not able to reach all of
2609 memory). Therefore tests have to be inserted into each such
2610 optimization to make sure that it does not undo stuff necessary to
2611 cross partition boundaries. This would be much less of a problem
2612 if we could perform this optimization later in the compilation, but
2613 unfortunately the fact that we may need to create indirect jumps
2614 (through registers) requires that this optimization be performed
2615 before register allocation.
2617 Hot and cold basic blocks are partitioned and put in separate
2618 sections of the .o file, to reduce paging and improve cache
2619 performance (hopefully). This can result in bits of code from the
2620 same function being widely separated in the .o file. However this
2621 is not obvious to the current bb structure. Therefore we must take
2622 care to ensure that: 1). There are no fall_thru edges that cross
2623 between sections; 2). For those architectures which have "short"
2624 conditional branches, all conditional branches that attempt to
2625 cross between sections are converted to unconditional branches;
2626 and, 3). For those architectures which have "short" unconditional
2627 branches, all unconditional branches that attempt to cross between
2628 sections are converted to indirect jumps.
2630 The code for fixing up fall_thru edges that cross between hot and
2631 cold basic blocks does so by creating new basic blocks containing
2632 unconditional branches to the appropriate label in the "other"
2633 section. The new basic block is then put in the same (hot or cold)
2634 section as the original conditional branch, and the fall_thru edge
2635 is modified to fall into the new basic block instead. By adding
2636 this level of indirection we end up with only unconditional branches
2637 crossing between hot and cold sections.
2639 Conditional branches are dealt with by adding a level of indirection.
2640 A new basic block is added in the same (hot/cold) section as the
2641 conditional branch, and the conditional branch is retargeted to the
2642 new basic block. The new basic block contains an unconditional branch
2643 to the original target of the conditional branch (in the other section).
2645 Unconditional branches are dealt with by converting them into
2650 const pass_data pass_data_partition_blocks
=
2652 RTL_PASS
, /* type */
2653 "bbpart", /* name */
2654 OPTGROUP_NONE
, /* optinfo_flags */
2655 TV_REORDER_BLOCKS
, /* tv_id */
2656 PROP_cfglayout
, /* properties_required */
2657 0, /* properties_provided */
2658 0, /* properties_destroyed */
2659 0, /* todo_flags_start */
2660 0, /* todo_flags_finish */
2663 class pass_partition_blocks
: public rtl_opt_pass
2666 pass_partition_blocks (gcc::context
*ctxt
)
2667 : rtl_opt_pass (pass_data_partition_blocks
, ctxt
)
2670 /* opt_pass methods: */
2671 virtual bool gate (function
*);
2672 virtual unsigned int execute (function
*);
2674 }; // class pass_partition_blocks
2677 pass_partition_blocks::gate (function
*fun
)
2679 /* The optimization to partition hot/cold basic blocks into separate
2680 sections of the .o file does not work well with linkonce or with
2681 user defined section attributes. Don't call it if either case
2683 return (flag_reorder_blocks_and_partition
2685 /* See gate_handle_reorder_blocks. We should not partition if
2686 we are going to omit the reordering. */
2687 && optimize_function_for_speed_p (fun
)
2688 && !DECL_COMDAT_GROUP (current_function_decl
)
2689 && !user_defined_section_attribute
);
2693 pass_partition_blocks::execute (function
*fun
)
2695 vec
<edge
> crossing_edges
;
2697 if (n_basic_blocks_for_fn (fun
) <= NUM_FIXED_BLOCKS
+ 1)
2700 df_set_flags (DF_DEFER_INSN_RESCAN
);
2702 crossing_edges
= find_rarely_executed_basic_blocks_and_crossing_edges ();
2703 if (!crossing_edges
.exists ())
2706 crtl
->has_bb_partition
= true;
2708 /* Make sure the source of any crossing edge ends in a jump and the
2709 destination of any crossing edge has a label. */
2710 add_labels_and_missing_jumps (crossing_edges
);
2712 /* Convert all crossing fall_thru edges to non-crossing fall
2713 thrus to unconditional jumps (that jump to the original fall
2715 fix_up_fall_thru_edges ();
2717 /* If the architecture does not have conditional branches that can
2718 span all of memory, convert crossing conditional branches into
2719 crossing unconditional branches. */
2720 if (!HAS_LONG_COND_BRANCH
)
2721 fix_crossing_conditional_branches ();
2723 /* If the architecture does not have unconditional branches that
2724 can span all of memory, convert crossing unconditional branches
2725 into indirect jumps. Since adding an indirect jump also adds
2726 a new register usage, update the register usage information as
2728 if (!HAS_LONG_UNCOND_BRANCH
)
2729 fix_crossing_unconditional_branches ();
2731 update_crossing_jump_flags ();
2733 /* Clear bb->aux fields that the above routines were using. */
2734 clear_aux_for_blocks ();
2736 crossing_edges
.release ();
2738 /* ??? FIXME: DF generates the bb info for a block immediately.
2739 And by immediately, I mean *during* creation of the block.
2741 #0 df_bb_refs_collect
2742 #1 in df_bb_refs_record
2743 #2 in create_basic_block_structure
2745 Which means that the bb_has_eh_pred test in df_bb_refs_collect
2746 will *always* fail, because no edges can have been added to the
2747 block yet. Which of course means we don't add the right
2748 artificial refs, which means we fail df_verify (much) later.
2750 Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
2751 that we also shouldn't grab data from the new blocks those new
2752 insns are in either. In this way one can create the block, link
2753 it up properly, and have everything Just Work later, when deferred
2754 insns are processed.
2756 In the meantime, we have no other option but to throw away all
2757 of the DF data and recompute it all. */
2758 if (fun
->eh
->lp_array
)
2760 df_finish_pass (true);
2761 df_scan_alloc (NULL
);
2763 /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
2764 data. We blindly generated all of them when creating the new
2765 landing pad. Delete those assignments we don't use. */
2766 df_set_flags (DF_LR_RUN_DCE
);
2776 make_pass_partition_blocks (gcc::context
*ctxt
)
2778 return new pass_partition_blocks (ctxt
);