1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000-2014 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"
97 #include "diagnostic-core.h"
98 #include "toplev.h" /* user_defined_section_attribute */
99 #include "tree-pass.h"
101 #include "bb-reorder.h"
104 /* The number of rounds. In most cases there will only be 4 rounds, but
105 when partitioning hot and cold basic blocks into separate sections of
106 the object file there will be an extra round. */
109 /* Stubs in case we don't have a return insn.
110 We have to check at run time too, not only compile time. */
113 #define HAVE_return 0
114 #define gen_return() NULL_RTX
118 struct target_bb_reorder default_target_bb_reorder
;
119 #if SWITCHABLE_TARGET
120 struct target_bb_reorder
*this_target_bb_reorder
= &default_target_bb_reorder
;
123 #define uncond_jump_length \
124 (this_target_bb_reorder->x_uncond_jump_length)
126 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
127 static const int branch_threshold
[N_ROUNDS
] = {400, 200, 100, 0, 0};
129 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
130 static const int exec_threshold
[N_ROUNDS
] = {500, 200, 50, 0, 0};
132 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
133 block the edge destination is not duplicated while connecting traces. */
134 #define DUPLICATION_THRESHOLD 100
136 /* Structure to hold needed information for each basic block. */
137 typedef struct bbro_basic_block_data_def
139 /* Which trace is the bb start of (-1 means it is not a start of any). */
142 /* Which trace is the bb end of (-1 means it is not an end of any). */
145 /* Which trace is the bb in? */
148 /* Which trace was this bb visited in? */
151 /* Which heap is BB in (if any)? */
154 /* Which heap node is BB in (if any)? */
156 } bbro_basic_block_data
;
158 /* The current size of the following dynamic array. */
159 static int array_size
;
161 /* The array which holds needed information for basic blocks. */
162 static bbro_basic_block_data
*bbd
;
164 /* To avoid frequent reallocation the size of arrays is greater than needed,
165 the number of elements is (not less than) 1.25 * size_wanted. */
166 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
168 /* Free the memory and set the pointer to NULL. */
169 #define FREE(P) (gcc_assert (P), free (P), P = 0)
171 /* Structure for holding information about a trace. */
174 /* First and last basic block of the trace. */
175 basic_block first
, last
;
177 /* The round of the STC creation which this trace was found in. */
180 /* The length (i.e. the number of basic blocks) of the trace. */
184 /* Maximum frequency and count of one of the entry blocks. */
185 static int max_entry_frequency
;
186 static gcov_type max_entry_count
;
188 /* Local function prototypes. */
189 static void find_traces (int *, struct trace
*);
190 static basic_block
rotate_loop (edge
, struct trace
*, int);
191 static void mark_bb_visited (basic_block
, int);
192 static void find_traces_1_round (int, int, gcov_type
, struct trace
*, int *,
193 int, fibheap_t
*, int);
194 static basic_block
copy_bb (basic_block
, edge
, basic_block
, int);
195 static fibheapkey_t
bb_to_key (basic_block
);
196 static bool better_edge_p (const_basic_block
, const_edge
, int, int, int, int,
198 static bool connect_better_edge_p (const_edge
, bool, int, const_edge
,
200 static void connect_traces (int, struct trace
*);
201 static bool copy_bb_p (const_basic_block
, int);
202 static bool push_to_next_round_p (const_basic_block
, int, int, int, gcov_type
);
204 /* Return the trace number in which BB was visited. */
207 bb_visited_trace (const_basic_block bb
)
209 gcc_assert (bb
->index
< array_size
);
210 return bbd
[bb
->index
].visited
;
213 /* This function marks BB that it was visited in trace number TRACE. */
216 mark_bb_visited (basic_block bb
, int trace
)
218 bbd
[bb
->index
].visited
= trace
;
219 if (bbd
[bb
->index
].heap
)
221 fibheap_delete_node (bbd
[bb
->index
].heap
, bbd
[bb
->index
].node
);
222 bbd
[bb
->index
].heap
= NULL
;
223 bbd
[bb
->index
].node
= NULL
;
227 /* Check to see if bb should be pushed into the next round of trace
228 collections or not. Reasons for pushing the block forward are 1).
229 If the block is cold, we are doing partitioning, and there will be
230 another round (cold partition blocks are not supposed to be
231 collected into traces until the very last round); or 2). There will
232 be another round, and the basic block is not "hot enough" for the
233 current round of trace collection. */
236 push_to_next_round_p (const_basic_block bb
, int round
, int number_of_rounds
,
237 int exec_th
, gcov_type count_th
)
239 bool there_exists_another_round
;
240 bool block_not_hot_enough
;
242 there_exists_another_round
= round
< number_of_rounds
- 1;
244 block_not_hot_enough
= (bb
->frequency
< exec_th
245 || bb
->count
< count_th
246 || probably_never_executed_bb_p (cfun
, bb
));
248 if (there_exists_another_round
249 && block_not_hot_enough
)
255 /* Find the traces for Software Trace Cache. Chain each trace through
256 RBI()->next. Store the number of traces to N_TRACES and description of
260 find_traces (int *n_traces
, struct trace
*traces
)
263 int number_of_rounds
;
268 /* Add one extra round of trace collection when partitioning hot/cold
269 basic blocks into separate sections. The last round is for all the
270 cold blocks (and ONLY the cold blocks). */
272 number_of_rounds
= N_ROUNDS
- 1;
274 /* Insert entry points of function into heap. */
275 heap
= fibheap_new ();
276 max_entry_frequency
= 0;
278 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR_FOR_FN (cfun
)->succs
)
280 bbd
[e
->dest
->index
].heap
= heap
;
281 bbd
[e
->dest
->index
].node
= fibheap_insert (heap
, bb_to_key (e
->dest
),
283 if (e
->dest
->frequency
> max_entry_frequency
)
284 max_entry_frequency
= e
->dest
->frequency
;
285 if (e
->dest
->count
> max_entry_count
)
286 max_entry_count
= e
->dest
->count
;
289 /* Find the traces. */
290 for (i
= 0; i
< number_of_rounds
; i
++)
292 gcov_type count_threshold
;
295 fprintf (dump_file
, "STC - round %d\n", i
+ 1);
297 if (max_entry_count
< INT_MAX
/ 1000)
298 count_threshold
= max_entry_count
* exec_threshold
[i
] / 1000;
300 count_threshold
= max_entry_count
/ 1000 * exec_threshold
[i
];
302 find_traces_1_round (REG_BR_PROB_BASE
* branch_threshold
[i
] / 1000,
303 max_entry_frequency
* exec_threshold
[i
] / 1000,
304 count_threshold
, traces
, n_traces
, i
, &heap
,
307 fibheap_delete (heap
);
311 for (i
= 0; i
< *n_traces
; i
++)
314 fprintf (dump_file
, "Trace %d (round %d): ", i
+ 1,
315 traces
[i
].round
+ 1);
316 for (bb
= traces
[i
].first
;
317 bb
!= traces
[i
].last
;
318 bb
= (basic_block
) bb
->aux
)
319 fprintf (dump_file
, "%d [%d] ", bb
->index
, bb
->frequency
);
320 fprintf (dump_file
, "%d [%d]\n", bb
->index
, bb
->frequency
);
326 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
327 (with sequential number TRACE_N). */
330 rotate_loop (edge back_edge
, struct trace
*trace
, int trace_n
)
334 /* Information about the best end (end after rotation) of the loop. */
335 basic_block best_bb
= NULL
;
336 edge best_edge
= NULL
;
338 gcov_type best_count
= -1;
339 /* The best edge is preferred when its destination is not visited yet
340 or is a start block of some trace. */
341 bool is_preferred
= false;
343 /* Find the most frequent edge that goes out from current trace. */
344 bb
= back_edge
->dest
;
350 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
351 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
352 && bb_visited_trace (e
->dest
) != trace_n
353 && (e
->flags
& EDGE_CAN_FALLTHRU
)
354 && !(e
->flags
& EDGE_COMPLEX
))
358 /* The best edge is preferred. */
359 if (!bb_visited_trace (e
->dest
)
360 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
362 /* The current edge E is also preferred. */
363 int freq
= EDGE_FREQUENCY (e
);
364 if (freq
> best_freq
|| e
->count
> best_count
)
367 best_count
= e
->count
;
375 if (!bb_visited_trace (e
->dest
)
376 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
378 /* The current edge E is preferred. */
380 best_freq
= EDGE_FREQUENCY (e
);
381 best_count
= e
->count
;
387 int freq
= EDGE_FREQUENCY (e
);
388 if (!best_edge
|| freq
> best_freq
|| e
->count
> best_count
)
391 best_count
= e
->count
;
398 bb
= (basic_block
) bb
->aux
;
400 while (bb
!= back_edge
->dest
);
404 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
406 if (back_edge
->dest
== trace
->first
)
408 trace
->first
= (basic_block
) best_bb
->aux
;
414 for (prev_bb
= trace
->first
;
415 prev_bb
->aux
!= back_edge
->dest
;
416 prev_bb
= (basic_block
) prev_bb
->aux
)
418 prev_bb
->aux
= best_bb
->aux
;
420 /* Try to get rid of uncond jump to cond jump. */
421 if (single_succ_p (prev_bb
))
423 basic_block header
= single_succ (prev_bb
);
425 /* Duplicate HEADER if it is a small block containing cond jump
427 if (any_condjump_p (BB_END (header
)) && copy_bb_p (header
, 0)
428 && !CROSSING_JUMP_P (BB_END (header
)))
429 copy_bb (header
, single_succ_edge (prev_bb
), prev_bb
, trace_n
);
435 /* We have not found suitable loop tail so do no rotation. */
436 best_bb
= back_edge
->src
;
442 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
443 not include basic blocks whose probability is lower than BRANCH_TH or whose
444 frequency is lower than EXEC_TH into traces (or whose count is lower than
445 COUNT_TH). Store the new traces into TRACES and modify the number of
446 traces *N_TRACES. Set the round (which the trace belongs to) to ROUND.
447 The function expects starting basic blocks to be in *HEAP and will delete
448 *HEAP and store starting points for the next round into new *HEAP. */
451 find_traces_1_round (int branch_th
, int exec_th
, gcov_type count_th
,
452 struct trace
*traces
, int *n_traces
, int round
,
453 fibheap_t
*heap
, int number_of_rounds
)
455 /* Heap for discarded basic blocks which are possible starting points for
457 fibheap_t new_heap
= fibheap_new ();
458 bool for_size
= optimize_function_for_size_p (cfun
);
460 while (!fibheap_empty (*heap
))
468 bb
= (basic_block
) fibheap_extract_min (*heap
);
469 bbd
[bb
->index
].heap
= NULL
;
470 bbd
[bb
->index
].node
= NULL
;
473 fprintf (dump_file
, "Getting bb %d\n", bb
->index
);
475 /* If the BB's frequency is too low, send BB to the next round. When
476 partitioning hot/cold blocks into separate sections, make sure all
477 the cold blocks (and ONLY the cold blocks) go into the (extra) final
478 round. When optimizing for size, do not push to next round. */
481 && push_to_next_round_p (bb
, round
, number_of_rounds
, exec_th
,
484 int key
= bb_to_key (bb
);
485 bbd
[bb
->index
].heap
= new_heap
;
486 bbd
[bb
->index
].node
= fibheap_insert (new_heap
, key
, bb
);
490 " Possible start point of next round: %d (key: %d)\n",
495 trace
= traces
+ *n_traces
;
497 trace
->round
= round
;
499 bbd
[bb
->index
].in_trace
= *n_traces
;
507 /* The probability and frequency of the best edge. */
508 int best_prob
= INT_MIN
/ 2;
509 int best_freq
= INT_MIN
/ 2;
512 mark_bb_visited (bb
, *n_traces
);
516 fprintf (dump_file
, "Basic block %d was visited in trace %d\n",
517 bb
->index
, *n_traces
- 1);
519 ends_in_call
= block_ends_with_call_p (bb
);
521 /* Select the successor that will be placed after BB. */
522 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
524 gcc_assert (!(e
->flags
& EDGE_FAKE
));
526 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
529 if (bb_visited_trace (e
->dest
)
530 && bb_visited_trace (e
->dest
) != *n_traces
)
533 if (BB_PARTITION (e
->dest
) != BB_PARTITION (bb
))
536 prob
= e
->probability
;
537 freq
= e
->dest
->frequency
;
539 /* The only sensible preference for a call instruction is the
540 fallthru edge. Don't bother selecting anything else. */
543 if (e
->flags
& EDGE_CAN_FALLTHRU
)
552 /* Edge that cannot be fallthru or improbable or infrequent
553 successor (i.e. it is unsuitable successor). When optimizing
554 for size, ignore the probability and frequency. */
555 if (!(e
->flags
& EDGE_CAN_FALLTHRU
) || (e
->flags
& EDGE_COMPLEX
)
556 || ((prob
< branch_th
|| EDGE_FREQUENCY (e
) < exec_th
557 || e
->count
< count_th
) && (!for_size
)))
560 /* If partitioning hot/cold basic blocks, don't consider edges
561 that cross section boundaries. */
563 if (better_edge_p (bb
, e
, prob
, freq
, best_prob
, best_freq
,
572 /* If the best destination has multiple predecessors, and can be
573 duplicated cheaper than a jump, don't allow it to be added
574 to a trace. We'll duplicate it when connecting traces. */
575 if (best_edge
&& EDGE_COUNT (best_edge
->dest
->preds
) >= 2
576 && copy_bb_p (best_edge
->dest
, 0))
579 /* If the best destination has multiple successors or predecessors,
580 don't allow it to be added when optimizing for size. This makes
581 sure predecessors with smaller index are handled before the best
582 destinarion. It breaks long trace and reduces long jumps.
584 Take if-then-else as an example.
590 If we do not remove the best edge B->D/C->D, the final order might
591 be A B D ... C. C is at the end of the program. If D's successors
592 and D are complicated, might need long jumps for A->C and C->D.
593 Similar issue for order: A C D ... B.
595 After removing the best edge, the final result will be ABCD/ ACBD.
596 It does not add jump compared with the previous order. But it
597 reduces the possibility of long jumps. */
598 if (best_edge
&& for_size
599 && (EDGE_COUNT (best_edge
->dest
->succs
) > 1
600 || EDGE_COUNT (best_edge
->dest
->preds
) > 1))
603 /* Add all non-selected successors to the heaps. */
604 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
607 || e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
608 || bb_visited_trace (e
->dest
))
611 key
= bb_to_key (e
->dest
);
613 if (bbd
[e
->dest
->index
].heap
)
615 /* E->DEST is already in some heap. */
616 if (key
!= bbd
[e
->dest
->index
].node
->key
)
621 "Changing key for bb %d from %ld to %ld.\n",
623 (long) bbd
[e
->dest
->index
].node
->key
,
626 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
627 bbd
[e
->dest
->index
].node
, key
);
632 fibheap_t which_heap
= *heap
;
634 prob
= e
->probability
;
635 freq
= EDGE_FREQUENCY (e
);
637 if (!(e
->flags
& EDGE_CAN_FALLTHRU
)
638 || (e
->flags
& EDGE_COMPLEX
)
639 || prob
< branch_th
|| freq
< exec_th
640 || e
->count
< count_th
)
642 /* When partitioning hot/cold basic blocks, make sure
643 the cold blocks (and only the cold blocks) all get
644 pushed to the last round of trace collection. When
645 optimizing for size, do not push to next round. */
647 if (!for_size
&& push_to_next_round_p (e
->dest
, round
,
650 which_heap
= new_heap
;
653 bbd
[e
->dest
->index
].heap
= which_heap
;
654 bbd
[e
->dest
->index
].node
= fibheap_insert (which_heap
,
660 " Possible start of %s round: %d (key: %ld)\n",
661 (which_heap
== new_heap
) ? "next" : "this",
662 e
->dest
->index
, (long) key
);
668 if (best_edge
) /* Suitable successor was found. */
670 if (bb_visited_trace (best_edge
->dest
) == *n_traces
)
672 /* We do nothing with one basic block loops. */
673 if (best_edge
->dest
!= bb
)
675 if (EDGE_FREQUENCY (best_edge
)
676 > 4 * best_edge
->dest
->frequency
/ 5)
678 /* The loop has at least 4 iterations. If the loop
679 header is not the first block of the function
680 we can rotate the loop. */
683 != ENTRY_BLOCK_PTR_FOR_FN (cfun
)->next_bb
)
688 "Rotating loop %d - %d\n",
689 best_edge
->dest
->index
, bb
->index
);
691 bb
->aux
= best_edge
->dest
;
692 bbd
[best_edge
->dest
->index
].in_trace
=
694 bb
= rotate_loop (best_edge
, trace
, *n_traces
);
699 /* The loop has less than 4 iterations. */
701 if (single_succ_p (bb
)
702 && copy_bb_p (best_edge
->dest
,
703 optimize_edge_for_speed_p
706 bb
= copy_bb (best_edge
->dest
, best_edge
, bb
,
713 /* Terminate the trace. */
718 /* Check for a situation
727 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
728 >= EDGE_FREQUENCY (AC).
729 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
730 Best ordering is then A B C.
732 When optimizing for size, A B C is always the best order.
734 This situation is created for example by:
741 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
743 && (e
->flags
& EDGE_CAN_FALLTHRU
)
744 && !(e
->flags
& EDGE_COMPLEX
)
745 && !bb_visited_trace (e
->dest
)
746 && single_pred_p (e
->dest
)
747 && !(e
->flags
& EDGE_CROSSING
)
748 && single_succ_p (e
->dest
)
749 && (single_succ_edge (e
->dest
)->flags
751 && !(single_succ_edge (e
->dest
)->flags
& EDGE_COMPLEX
)
752 && single_succ (e
->dest
) == best_edge
->dest
753 && (2 * e
->dest
->frequency
>= EDGE_FREQUENCY (best_edge
)
758 fprintf (dump_file
, "Selecting BB %d\n",
759 best_edge
->dest
->index
);
763 bb
->aux
= best_edge
->dest
;
764 bbd
[best_edge
->dest
->index
].in_trace
= (*n_traces
) - 1;
765 bb
= best_edge
->dest
;
771 bbd
[trace
->first
->index
].start_of_trace
= *n_traces
- 1;
772 bbd
[trace
->last
->index
].end_of_trace
= *n_traces
- 1;
774 /* The trace is terminated so we have to recount the keys in heap
775 (some block can have a lower key because now one of its predecessors
776 is an end of the trace). */
777 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
779 if (e
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
780 || bb_visited_trace (e
->dest
))
783 if (bbd
[e
->dest
->index
].heap
)
785 key
= bb_to_key (e
->dest
);
786 if (key
!= bbd
[e
->dest
->index
].node
->key
)
791 "Changing key for bb %d from %ld to %ld.\n",
793 (long) bbd
[e
->dest
->index
].node
->key
, key
);
795 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
796 bbd
[e
->dest
->index
].node
,
803 fibheap_delete (*heap
);
805 /* "Return" the new heap. */
809 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
810 it to trace after BB, mark OLD_BB visited and update pass' data structures
811 (TRACE is a number of trace which OLD_BB is duplicated to). */
814 copy_bb (basic_block old_bb
, edge e
, basic_block bb
, int trace
)
818 new_bb
= duplicate_block (old_bb
, e
, bb
);
819 BB_COPY_PARTITION (new_bb
, old_bb
);
821 gcc_assert (e
->dest
== new_bb
);
825 "Duplicated bb %d (created bb %d)\n",
826 old_bb
->index
, new_bb
->index
);
828 if (new_bb
->index
>= array_size
829 || last_basic_block_for_fn (cfun
) > array_size
)
834 new_size
= MAX (last_basic_block_for_fn (cfun
), new_bb
->index
+ 1);
835 new_size
= GET_ARRAY_SIZE (new_size
);
836 bbd
= XRESIZEVEC (bbro_basic_block_data
, bbd
, new_size
);
837 for (i
= array_size
; i
< new_size
; i
++)
839 bbd
[i
].start_of_trace
= -1;
840 bbd
[i
].end_of_trace
= -1;
841 bbd
[i
].in_trace
= -1;
846 array_size
= new_size
;
851 "Growing the dynamic array to %d elements.\n",
856 gcc_assert (!bb_visited_trace (e
->dest
));
857 mark_bb_visited (new_bb
, trace
);
858 new_bb
->aux
= bb
->aux
;
861 bbd
[new_bb
->index
].in_trace
= trace
;
866 /* Compute and return the key (for the heap) of the basic block BB. */
869 bb_to_key (basic_block bb
)
875 /* Use index as key to align with its original order. */
876 if (optimize_function_for_size_p (cfun
))
879 /* Do not start in probably never executed blocks. */
881 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
882 || probably_never_executed_bb_p (cfun
, bb
))
885 /* Prefer blocks whose predecessor is an end of some trace
886 or whose predecessor edge is EDGE_DFS_BACK. */
887 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
889 if ((e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
890 && bbd
[e
->src
->index
].end_of_trace
>= 0)
891 || (e
->flags
& EDGE_DFS_BACK
))
893 int edge_freq
= EDGE_FREQUENCY (e
);
895 if (edge_freq
> priority
)
896 priority
= edge_freq
;
901 /* The block with priority should have significantly lower key. */
902 return -(100 * BB_FREQ_MAX
+ 100 * priority
+ bb
->frequency
);
904 return -bb
->frequency
;
907 /* Return true when the edge E from basic block BB is better than the temporary
908 best edge (details are in function). The probability of edge E is PROB. The
909 frequency of the successor is FREQ. The current best probability is
910 BEST_PROB, the best frequency is BEST_FREQ.
911 The edge is considered to be equivalent when PROB does not differ much from
912 BEST_PROB; similarly for frequency. */
915 better_edge_p (const_basic_block bb
, const_edge e
, int prob
, int freq
,
916 int best_prob
, int best_freq
, const_edge cur_best_edge
)
920 /* The BEST_* values do not have to be best, but can be a bit smaller than
922 int diff_prob
= best_prob
/ 10;
923 int diff_freq
= best_freq
/ 10;
925 /* The smaller one is better to keep the original order. */
926 if (optimize_function_for_size_p (cfun
))
927 return !cur_best_edge
928 || cur_best_edge
->dest
->index
> e
->dest
->index
;
930 if (prob
> best_prob
+ diff_prob
)
931 /* The edge has higher probability than the temporary best edge. */
932 is_better_edge
= true;
933 else if (prob
< best_prob
- diff_prob
)
934 /* The edge has lower probability than the temporary best edge. */
935 is_better_edge
= false;
936 else if (freq
< best_freq
- diff_freq
)
937 /* The edge and the temporary best edge have almost equivalent
938 probabilities. The higher frequency of a successor now means
939 that there is another edge going into that successor.
940 This successor has lower frequency so it is better. */
941 is_better_edge
= true;
942 else if (freq
> best_freq
+ diff_freq
)
943 /* This successor has higher frequency so it is worse. */
944 is_better_edge
= false;
945 else if (e
->dest
->prev_bb
== bb
)
946 /* The edges have equivalent probabilities and the successors
947 have equivalent frequencies. Select the previous successor. */
948 is_better_edge
= true;
950 is_better_edge
= false;
952 /* If we are doing hot/cold partitioning, make sure that we always favor
953 non-crossing edges over crossing edges. */
956 && flag_reorder_blocks_and_partition
958 && (cur_best_edge
->flags
& EDGE_CROSSING
)
959 && !(e
->flags
& EDGE_CROSSING
))
960 is_better_edge
= true;
962 return is_better_edge
;
965 /* Return true when the edge E is better than the temporary best edge
966 CUR_BEST_EDGE. If SRC_INDEX_P is true, the function compares the src bb of
967 E and CUR_BEST_EDGE; otherwise it will compare the dest bb.
968 BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE.
969 TRACES record the information about traces.
970 When optimizing for size, the edge with smaller index is better.
971 When optimizing for speed, the edge with bigger probability or longer trace
975 connect_better_edge_p (const_edge e
, bool src_index_p
, int best_len
,
976 const_edge cur_best_edge
, struct trace
*traces
)
985 if (optimize_function_for_size_p (cfun
))
987 e_index
= src_index_p
? e
->src
->index
: e
->dest
->index
;
988 b_index
= src_index_p
? cur_best_edge
->src
->index
989 : cur_best_edge
->dest
->index
;
990 /* The smaller one is better to keep the original order. */
991 return b_index
> e_index
;
996 e_index
= e
->src
->index
;
998 if (e
->probability
> cur_best_edge
->probability
)
999 /* The edge has higher probability than the temporary best edge. */
1000 is_better_edge
= true;
1001 else if (e
->probability
< cur_best_edge
->probability
)
1002 /* The edge has lower probability than the temporary best edge. */
1003 is_better_edge
= false;
1004 else if (traces
[bbd
[e_index
].end_of_trace
].length
> best_len
)
1005 /* The edge and the temporary best edge have equivalent probabilities.
1006 The edge with longer trace is better. */
1007 is_better_edge
= true;
1009 is_better_edge
= false;
1013 e_index
= e
->dest
->index
;
1015 if (e
->probability
> cur_best_edge
->probability
)
1016 /* The edge has higher probability than the temporary best edge. */
1017 is_better_edge
= true;
1018 else if (e
->probability
< cur_best_edge
->probability
)
1019 /* The edge has lower probability than the temporary best edge. */
1020 is_better_edge
= false;
1021 else if (traces
[bbd
[e_index
].start_of_trace
].length
> best_len
)
1022 /* The edge and the temporary best edge have equivalent probabilities.
1023 The edge with longer trace is better. */
1024 is_better_edge
= true;
1026 is_better_edge
= false;
1029 return is_better_edge
;
1032 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
1035 connect_traces (int n_traces
, struct trace
*traces
)
1042 int current_partition
;
1044 gcov_type count_threshold
;
1045 bool for_size
= optimize_function_for_size_p (cfun
);
1047 freq_threshold
= max_entry_frequency
* DUPLICATION_THRESHOLD
/ 1000;
1048 if (max_entry_count
< INT_MAX
/ 1000)
1049 count_threshold
= max_entry_count
* DUPLICATION_THRESHOLD
/ 1000;
1051 count_threshold
= max_entry_count
/ 1000 * DUPLICATION_THRESHOLD
;
1053 connected
= XCNEWVEC (bool, n_traces
);
1056 current_partition
= BB_PARTITION (traces
[0].first
);
1059 if (crtl
->has_bb_partition
)
1060 for (i
= 0; i
< n_traces
&& !two_passes
; i
++)
1061 if (BB_PARTITION (traces
[0].first
)
1062 != BB_PARTITION (traces
[i
].first
))
1065 for (i
= 0; i
< n_traces
|| (two_passes
&& current_pass
== 1) ; i
++)
1074 gcc_assert (two_passes
&& current_pass
== 1);
1078 if (current_partition
== BB_HOT_PARTITION
)
1079 current_partition
= BB_COLD_PARTITION
;
1081 current_partition
= BB_HOT_PARTITION
;
1088 && BB_PARTITION (traces
[t
].first
) != current_partition
)
1091 connected
[t
] = true;
1093 /* Find the predecessor traces. */
1094 for (t2
= t
; t2
> 0;)
1099 FOR_EACH_EDGE (e
, ei
, traces
[t2
].first
->preds
)
1101 int si
= e
->src
->index
;
1103 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1104 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1105 && !(e
->flags
& EDGE_COMPLEX
)
1106 && bbd
[si
].end_of_trace
>= 0
1107 && !connected
[bbd
[si
].end_of_trace
]
1108 && (BB_PARTITION (e
->src
) == current_partition
)
1109 && connect_better_edge_p (e
, true, best_len
, best
, traces
))
1112 best_len
= traces
[bbd
[si
].end_of_trace
].length
;
1117 best
->src
->aux
= best
->dest
;
1118 t2
= bbd
[best
->src
->index
].end_of_trace
;
1119 connected
[t2
] = true;
1123 fprintf (dump_file
, "Connection: %d %d\n",
1124 best
->src
->index
, best
->dest
->index
);
1131 if (last_trace
>= 0)
1132 traces
[last_trace
].last
->aux
= traces
[t2
].first
;
1135 /* Find the successor traces. */
1138 /* Find the continuation of the chain. */
1142 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1144 int di
= e
->dest
->index
;
1146 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1147 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1148 && !(e
->flags
& EDGE_COMPLEX
)
1149 && bbd
[di
].start_of_trace
>= 0
1150 && !connected
[bbd
[di
].start_of_trace
]
1151 && (BB_PARTITION (e
->dest
) == current_partition
)
1152 && connect_better_edge_p (e
, false, best_len
, best
, traces
))
1155 best_len
= traces
[bbd
[di
].start_of_trace
].length
;
1162 /* Stop finding the successor traces. */
1165 /* It is OK to connect block n with block n + 1 or a block
1166 before n. For others, only connect to the loop header. */
1167 if (best
->dest
->index
> (traces
[t
].last
->index
+ 1))
1169 int count
= EDGE_COUNT (best
->dest
->preds
);
1171 FOR_EACH_EDGE (e
, ei
, best
->dest
->preds
)
1172 if (e
->flags
& EDGE_DFS_BACK
)
1175 /* If dest has multiple predecessors, skip it. We expect
1176 that one predecessor with smaller index connects with it
1182 /* Only connect Trace n with Trace n + 1. It is conservative
1183 to keep the order as close as possible to the original order.
1184 It also helps to reduce long jumps. */
1185 if (last_trace
!= bbd
[best
->dest
->index
].start_of_trace
- 1)
1189 fprintf (dump_file
, "Connection: %d %d\n",
1190 best
->src
->index
, best
->dest
->index
);
1192 t
= bbd
[best
->dest
->index
].start_of_trace
;
1193 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1194 connected
[t
] = true;
1201 fprintf (dump_file
, "Connection: %d %d\n",
1202 best
->src
->index
, best
->dest
->index
);
1204 t
= bbd
[best
->dest
->index
].start_of_trace
;
1205 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1206 connected
[t
] = true;
1211 /* Try to connect the traces by duplication of 1 block. */
1213 basic_block next_bb
= NULL
;
1214 bool try_copy
= false;
1216 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1217 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1218 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1219 && !(e
->flags
& EDGE_COMPLEX
)
1220 && (!best
|| e
->probability
> best
->probability
))
1226 /* If the destination is a start of a trace which is only
1227 one block long, then no need to search the successor
1228 blocks of the trace. Accept it. */
1229 if (bbd
[e
->dest
->index
].start_of_trace
>= 0
1230 && traces
[bbd
[e
->dest
->index
].start_of_trace
].length
1238 FOR_EACH_EDGE (e2
, ei
, e
->dest
->succs
)
1240 int di
= e2
->dest
->index
;
1242 if (e2
->dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
)
1243 || ((e2
->flags
& EDGE_CAN_FALLTHRU
)
1244 && !(e2
->flags
& EDGE_COMPLEX
)
1245 && bbd
[di
].start_of_trace
>= 0
1246 && !connected
[bbd
[di
].start_of_trace
]
1247 && BB_PARTITION (e2
->dest
) == current_partition
1248 && EDGE_FREQUENCY (e2
) >= freq_threshold
1249 && e2
->count
>= count_threshold
1251 || e2
->probability
> best2
->probability
1252 || (e2
->probability
== best2
->probability
1253 && traces
[bbd
[di
].start_of_trace
].length
1258 if (e2
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1259 best2_len
= traces
[bbd
[di
].start_of_trace
].length
;
1261 best2_len
= INT_MAX
;
1268 if (crtl
->has_bb_partition
)
1271 /* Copy tiny blocks always; copy larger blocks only when the
1272 edge is traversed frequently enough. */
1274 && copy_bb_p (best
->dest
,
1275 optimize_edge_for_speed_p (best
)
1276 && EDGE_FREQUENCY (best
) >= freq_threshold
1277 && best
->count
>= count_threshold
))
1283 fprintf (dump_file
, "Connection: %d %d ",
1284 traces
[t
].last
->index
, best
->dest
->index
);
1286 fputc ('\n', dump_file
);
1287 else if (next_bb
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1288 fprintf (dump_file
, "exit\n");
1290 fprintf (dump_file
, "%d\n", next_bb
->index
);
1293 new_bb
= copy_bb (best
->dest
, best
, traces
[t
].last
, t
);
1294 traces
[t
].last
= new_bb
;
1295 if (next_bb
&& next_bb
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1297 t
= bbd
[next_bb
->index
].start_of_trace
;
1298 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1299 connected
[t
] = true;
1303 break; /* Stop finding the successor traces. */
1306 break; /* Stop finding the successor traces. */
1315 fprintf (dump_file
, "Final order:\n");
1316 for (bb
= traces
[0].first
; bb
; bb
= (basic_block
) bb
->aux
)
1317 fprintf (dump_file
, "%d ", bb
->index
);
1318 fprintf (dump_file
, "\n");
1325 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1326 when code size is allowed to grow by duplication. */
1329 copy_bb_p (const_basic_block bb
, int code_may_grow
)
1332 int max_size
= uncond_jump_length
;
1337 if (EDGE_COUNT (bb
->preds
) < 2)
1339 if (!can_duplicate_block_p (bb
))
1342 /* Avoid duplicating blocks which have many successors (PR/13430). */
1343 if (EDGE_COUNT (bb
->succs
) > 8)
1346 if (code_may_grow
&& optimize_bb_for_speed_p (bb
))
1347 max_size
*= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS
);
1349 FOR_BB_INSNS (bb
, insn
)
1352 size
+= get_attr_min_length (insn
);
1355 if (size
<= max_size
)
1361 "Block %d can't be copied because its size = %d.\n",
1368 /* Return the length of unconditional jump instruction. */
1371 get_uncond_jump_length (void)
1376 label
= emit_label_before (gen_label_rtx (), get_insns ());
1377 jump
= emit_jump_insn (gen_jump (label
));
1379 length
= get_attr_min_length (jump
);
1382 delete_insn (label
);
1386 /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1387 Duplicate the landing pad and split the edges so that no EH edge
1388 crosses partitions. */
1391 fix_up_crossing_landing_pad (eh_landing_pad old_lp
, basic_block old_bb
)
1393 eh_landing_pad new_lp
;
1394 basic_block new_bb
, last_bb
, post_bb
;
1395 rtx new_label
, jump
, post_label
;
1396 unsigned new_partition
;
1400 /* Generate the new landing-pad structure. */
1401 new_lp
= gen_eh_landing_pad (old_lp
->region
);
1402 new_lp
->post_landing_pad
= old_lp
->post_landing_pad
;
1403 new_lp
->landing_pad
= gen_label_rtx ();
1404 LABEL_PRESERVE_P (new_lp
->landing_pad
) = 1;
1406 /* Put appropriate instructions in new bb. */
1407 new_label
= emit_label (new_lp
->landing_pad
);
1409 expand_dw2_landing_pad_for_region (old_lp
->region
);
1411 post_bb
= BLOCK_FOR_INSN (old_lp
->landing_pad
);
1412 post_bb
= single_succ (post_bb
);
1413 post_label
= block_label (post_bb
);
1414 jump
= emit_jump_insn (gen_jump (post_label
));
1415 JUMP_LABEL (jump
) = post_label
;
1417 /* Create new basic block to be dest for lp. */
1418 last_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
1419 new_bb
= create_basic_block (new_label
, jump
, last_bb
);
1420 new_bb
->aux
= last_bb
->aux
;
1421 last_bb
->aux
= new_bb
;
1423 emit_barrier_after_bb (new_bb
);
1425 make_edge (new_bb
, post_bb
, 0);
1427 /* Make sure new bb is in the other partition. */
1428 new_partition
= BB_PARTITION (old_bb
);
1429 new_partition
^= BB_HOT_PARTITION
| BB_COLD_PARTITION
;
1430 BB_SET_PARTITION (new_bb
, new_partition
);
1432 /* Fix up the edges. */
1433 for (ei
= ei_start (old_bb
->preds
); (e
= ei_safe_edge (ei
)) != NULL
; )
1434 if (BB_PARTITION (e
->src
) == new_partition
)
1436 rtx insn
= BB_END (e
->src
);
1437 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1439 gcc_assert (note
!= NULL
);
1440 gcc_checking_assert (INTVAL (XEXP (note
, 0)) == old_lp
->index
);
1441 XEXP (note
, 0) = GEN_INT (new_lp
->index
);
1443 /* Adjust the edge to the new destination. */
1444 redirect_edge_succ (e
, new_bb
);
1451 /* Ensure that all hot bbs are included in a hot path through the
1452 procedure. This is done by calling this function twice, once
1453 with WALK_UP true (to look for paths from the entry to hot bbs) and
1454 once with WALK_UP false (to look for paths from hot bbs to the exit).
1455 Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs
1456 to BBS_IN_HOT_PARTITION. */
1459 sanitize_hot_paths (bool walk_up
, unsigned int cold_bb_count
,
1460 vec
<basic_block
> *bbs_in_hot_partition
)
1462 /* Callers check this. */
1463 gcc_checking_assert (cold_bb_count
);
1465 /* Keep examining hot bbs while we still have some left to check
1466 and there are remaining cold bbs. */
1467 vec
<basic_block
> hot_bbs_to_check
= bbs_in_hot_partition
->copy ();
1468 while (! hot_bbs_to_check
.is_empty ()
1471 basic_block bb
= hot_bbs_to_check
.pop ();
1472 vec
<edge
, va_gc
> *edges
= walk_up
? bb
->preds
: bb
->succs
;
1475 int highest_probability
= 0;
1476 int highest_freq
= 0;
1477 gcov_type highest_count
= 0;
1480 /* Walk the preds/succs and check if there is at least one already
1481 marked hot. Keep track of the most frequent pred/succ so that we
1482 can mark it hot if we don't find one. */
1483 FOR_EACH_EDGE (e
, ei
, edges
)
1485 basic_block reach_bb
= walk_up
? e
->src
: e
->dest
;
1487 if (e
->flags
& EDGE_DFS_BACK
)
1490 if (BB_PARTITION (reach_bb
) != BB_COLD_PARTITION
)
1495 /* The following loop will look for the hottest edge via
1496 the edge count, if it is non-zero, then fallback to the edge
1497 frequency and finally the edge probability. */
1498 if (e
->count
> highest_count
)
1499 highest_count
= e
->count
;
1500 int edge_freq
= EDGE_FREQUENCY (e
);
1501 if (edge_freq
> highest_freq
)
1502 highest_freq
= edge_freq
;
1503 if (e
->probability
> highest_probability
)
1504 highest_probability
= e
->probability
;
1507 /* If bb is reached by (or reaches, in the case of !WALK_UP) another hot
1508 block (or unpartitioned, e.g. the entry block) then it is ok. If not,
1509 then the most frequent pred (or succ) needs to be adjusted. In the
1510 case where multiple preds/succs have the same frequency (e.g. a
1511 50-50 branch), then both will be adjusted. */
1515 FOR_EACH_EDGE (e
, ei
, edges
)
1517 if (e
->flags
& EDGE_DFS_BACK
)
1519 /* Select the hottest edge using the edge count, if it is non-zero,
1520 then fallback to the edge frequency and finally the edge
1524 if (e
->count
< highest_count
)
1527 else if (highest_freq
)
1529 if (EDGE_FREQUENCY (e
) < highest_freq
)
1532 else if (e
->probability
< highest_probability
)
1535 basic_block reach_bb
= walk_up
? e
->src
: e
->dest
;
1537 /* We have a hot bb with an immediate dominator that is cold.
1538 The dominator needs to be re-marked hot. */
1539 BB_SET_PARTITION (reach_bb
, BB_HOT_PARTITION
);
1542 /* Now we need to examine newly-hot reach_bb to see if it is also
1543 dominated by a cold bb. */
1544 bbs_in_hot_partition
->safe_push (reach_bb
);
1545 hot_bbs_to_check
.safe_push (reach_bb
);
1549 return cold_bb_count
;
1553 /* Find the basic blocks that are rarely executed and need to be moved to
1554 a separate section of the .o file (to cut down on paging and improve
1555 cache locality). Return a vector of all edges that cross. */
1558 find_rarely_executed_basic_blocks_and_crossing_edges (void)
1560 vec
<edge
> crossing_edges
= vNULL
;
1564 unsigned int cold_bb_count
= 0;
1565 vec
<basic_block
> bbs_in_hot_partition
= vNULL
;
1567 /* Mark which partition (hot/cold) each basic block belongs in. */
1568 FOR_EACH_BB_FN (bb
, cfun
)
1570 bool cold_bb
= false;
1572 if (probably_never_executed_bb_p (cfun
, bb
))
1574 /* Handle profile insanities created by upstream optimizations
1575 by also checking the incoming edge weights. If there is a non-cold
1576 incoming edge, conservatively prevent this block from being split
1577 into the cold section. */
1579 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1580 if (!probably_never_executed_edge_p (cfun
, e
))
1588 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
1593 BB_SET_PARTITION (bb
, BB_HOT_PARTITION
);
1594 bbs_in_hot_partition
.safe_push (bb
);
1598 /* Ensure that hot bbs are included along a hot path from the entry to exit.
1599 Several different possibilities may include cold bbs along all paths
1600 to/from a hot bb. One is that there are edge weight insanities
1601 due to optimization phases that do not properly update basic block profile
1602 counts. The second is that the entry of the function may not be hot, because
1603 it is entered fewer times than the number of profile training runs, but there
1604 is a loop inside the function that causes blocks within the function to be
1605 above the threshold for hotness. This is fixed by walking up from hot bbs
1606 to the entry block, and then down from hot bbs to the exit, performing
1607 partitioning fixups as necessary. */
1610 mark_dfs_back_edges ();
1611 cold_bb_count
= sanitize_hot_paths (true, cold_bb_count
,
1612 &bbs_in_hot_partition
);
1614 sanitize_hot_paths (false, cold_bb_count
, &bbs_in_hot_partition
);
1617 /* The format of .gcc_except_table does not allow landing pads to
1618 be in a different partition as the throw. Fix this by either
1619 moving or duplicating the landing pads. */
1620 if (cfun
->eh
->lp_array
)
1625 FOR_EACH_VEC_ELT (*cfun
->eh
->lp_array
, i
, lp
)
1627 bool all_same
, all_diff
;
1630 || lp
->landing_pad
== NULL_RTX
1631 || !LABEL_P (lp
->landing_pad
))
1634 all_same
= all_diff
= true;
1635 bb
= BLOCK_FOR_INSN (lp
->landing_pad
);
1636 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1638 gcc_assert (e
->flags
& EDGE_EH
);
1639 if (BB_PARTITION (bb
) == BB_PARTITION (e
->src
))
1649 int which
= BB_PARTITION (bb
);
1650 which
^= BB_HOT_PARTITION
| BB_COLD_PARTITION
;
1651 BB_SET_PARTITION (bb
, which
);
1654 fix_up_crossing_landing_pad (lp
, bb
);
1658 /* Mark every edge that crosses between sections. */
1660 FOR_EACH_BB_FN (bb
, cfun
)
1661 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1663 unsigned int flags
= e
->flags
;
1665 /* We should never have EDGE_CROSSING set yet. */
1666 gcc_checking_assert ((flags
& EDGE_CROSSING
) == 0);
1668 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
1669 && e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)
1670 && BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1672 crossing_edges
.safe_push (e
);
1673 flags
|= EDGE_CROSSING
;
1676 /* Now that we've split eh edges as appropriate, allow landing pads
1677 to be merged with the post-landing pads. */
1678 flags
&= ~EDGE_PRESERVE
;
1683 return crossing_edges
;
1686 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
1689 set_edge_can_fallthru_flag (void)
1693 FOR_EACH_BB_FN (bb
, cfun
)
1698 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1700 e
->flags
&= ~EDGE_CAN_FALLTHRU
;
1702 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
1703 if (e
->flags
& EDGE_FALLTHRU
)
1704 e
->flags
|= EDGE_CAN_FALLTHRU
;
1707 /* If the BB ends with an invertible condjump all (2) edges are
1708 CAN_FALLTHRU edges. */
1709 if (EDGE_COUNT (bb
->succs
) != 2)
1711 if (!any_condjump_p (BB_END (bb
)))
1713 if (!invert_jump (BB_END (bb
), JUMP_LABEL (BB_END (bb
)), 0))
1715 invert_jump (BB_END (bb
), JUMP_LABEL (BB_END (bb
)), 0);
1716 EDGE_SUCC (bb
, 0)->flags
|= EDGE_CAN_FALLTHRU
;
1717 EDGE_SUCC (bb
, 1)->flags
|= EDGE_CAN_FALLTHRU
;
1721 /* If any destination of a crossing edge does not have a label, add label;
1722 Convert any easy fall-through crossing edges to unconditional jumps. */
1725 add_labels_and_missing_jumps (vec
<edge
> crossing_edges
)
1730 FOR_EACH_VEC_ELT (crossing_edges
, i
, e
)
1732 basic_block src
= e
->src
;
1733 basic_block dest
= e
->dest
;
1734 rtx label
, new_jump
;
1736 if (dest
== EXIT_BLOCK_PTR_FOR_FN (cfun
))
1739 /* Make sure dest has a label. */
1740 label
= block_label (dest
);
1742 /* Nothing to do for non-fallthru edges. */
1743 if (src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1745 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1748 /* If the block does not end with a control flow insn, then we
1749 can trivially add a jump to the end to fixup the crossing.
1750 Otherwise the jump will have to go in a new bb, which will
1751 be handled by fix_up_fall_thru_edges function. */
1752 if (control_flow_insn_p (BB_END (src
)))
1755 /* Make sure there's only one successor. */
1756 gcc_assert (single_succ_p (src
));
1758 new_jump
= emit_jump_insn_after (gen_jump (label
), BB_END (src
));
1759 BB_END (src
) = new_jump
;
1760 JUMP_LABEL (new_jump
) = label
;
1761 LABEL_NUSES (label
) += 1;
1763 emit_barrier_after_bb (src
);
1765 /* Mark edge as non-fallthru. */
1766 e
->flags
&= ~EDGE_FALLTHRU
;
1770 /* Find any bb's where the fall-through edge is a crossing edge (note that
1771 these bb's must also contain a conditional jump or end with a call
1772 instruction; we've already dealt with fall-through edges for blocks
1773 that didn't have a conditional jump or didn't end with call instruction
1774 in the call to add_labels_and_missing_jumps). Convert the fall-through
1775 edge to non-crossing edge by inserting a new bb to fall-through into.
1776 The new bb will contain an unconditional jump (crossing edge) to the
1777 original fall through destination. */
1780 fix_up_fall_thru_edges (void)
1787 edge cond_jump
= NULL
;
1789 bool cond_jump_crosses
;
1792 rtx fall_thru_label
;
1794 FOR_EACH_BB_FN (cur_bb
, cfun
)
1797 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1798 succ1
= EDGE_SUCC (cur_bb
, 0);
1802 if (EDGE_COUNT (cur_bb
->succs
) > 1)
1803 succ2
= EDGE_SUCC (cur_bb
, 1);
1807 /* Find the fall-through edge. */
1810 && (succ1
->flags
& EDGE_FALLTHRU
))
1816 && (succ2
->flags
& EDGE_FALLTHRU
))
1822 && (block_ends_with_call_p (cur_bb
)
1823 || can_throw_internal (BB_END (cur_bb
))))
1828 FOR_EACH_EDGE (e
, ei
, cur_bb
->succs
)
1829 if (e
->flags
& EDGE_FALLTHRU
)
1836 if (fall_thru
&& (fall_thru
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
)))
1838 /* Check to see if the fall-thru edge is a crossing edge. */
1840 if (fall_thru
->flags
& EDGE_CROSSING
)
1842 /* The fall_thru edge crosses; now check the cond jump edge, if
1845 cond_jump_crosses
= true;
1847 old_jump
= BB_END (cur_bb
);
1849 /* Find the jump instruction, if there is one. */
1853 if (!(cond_jump
->flags
& EDGE_CROSSING
))
1854 cond_jump_crosses
= false;
1856 /* We know the fall-thru edge crosses; if the cond
1857 jump edge does NOT cross, and its destination is the
1858 next block in the bb order, invert the jump
1859 (i.e. fix it so the fall through does not cross and
1860 the cond jump does). */
1862 if (!cond_jump_crosses
)
1864 /* Find label in fall_thru block. We've already added
1865 any missing labels, so there must be one. */
1867 fall_thru_label
= block_label (fall_thru
->dest
);
1869 if (old_jump
&& JUMP_P (old_jump
) && fall_thru_label
)
1870 invert_worked
= invert_jump (old_jump
,
1874 fall_thru
->flags
&= ~EDGE_FALLTHRU
;
1875 cond_jump
->flags
|= EDGE_FALLTHRU
;
1876 update_br_prob_note (cur_bb
);
1878 fall_thru
= cond_jump
;
1880 cond_jump
->flags
|= EDGE_CROSSING
;
1881 fall_thru
->flags
&= ~EDGE_CROSSING
;
1886 if (cond_jump_crosses
|| !invert_worked
)
1888 /* This is the case where both edges out of the basic
1889 block are crossing edges. Here we will fix up the
1890 fall through edge. The jump edge will be taken care
1891 of later. The EDGE_CROSSING flag of fall_thru edge
1892 is unset before the call to force_nonfallthru
1893 function because if a new basic-block is created
1894 this edge remains in the current section boundary
1895 while the edge between new_bb and the fall_thru->dest
1896 becomes EDGE_CROSSING. */
1898 fall_thru
->flags
&= ~EDGE_CROSSING
;
1899 new_bb
= force_nonfallthru (fall_thru
);
1903 new_bb
->aux
= cur_bb
->aux
;
1904 cur_bb
->aux
= new_bb
;
1906 /* This is done by force_nonfallthru_and_redirect. */
1907 gcc_assert (BB_PARTITION (new_bb
)
1908 == BB_PARTITION (cur_bb
));
1910 single_succ_edge (new_bb
)->flags
|= EDGE_CROSSING
;
1914 /* If a new basic-block was not created; restore
1915 the EDGE_CROSSING flag. */
1916 fall_thru
->flags
|= EDGE_CROSSING
;
1919 /* Add barrier after new jump */
1920 emit_barrier_after_bb (new_bb
? new_bb
: cur_bb
);
1927 /* This function checks the destination block of a "crossing jump" to
1928 see if it has any crossing predecessors that begin with a code label
1929 and end with an unconditional jump. If so, it returns that predecessor
1930 block. (This is to avoid creating lots of new basic blocks that all
1931 contain unconditional jumps to the same destination). */
1934 find_jump_block (basic_block jump_dest
)
1936 basic_block source_bb
= NULL
;
1941 FOR_EACH_EDGE (e
, ei
, jump_dest
->preds
)
1942 if (e
->flags
& EDGE_CROSSING
)
1944 basic_block src
= e
->src
;
1946 /* Check each predecessor to see if it has a label, and contains
1947 only one executable instruction, which is an unconditional jump.
1948 If so, we can use it. */
1950 if (LABEL_P (BB_HEAD (src
)))
1951 for (insn
= BB_HEAD (src
);
1952 !INSN_P (insn
) && insn
!= NEXT_INSN (BB_END (src
));
1953 insn
= NEXT_INSN (insn
))
1956 && insn
== BB_END (src
)
1958 && !any_condjump_p (insn
))
1972 /* Find all BB's with conditional jumps that are crossing edges;
1973 insert a new bb and make the conditional jump branch to the new
1974 bb instead (make the new bb same color so conditional branch won't
1975 be a 'crossing' edge). Insert an unconditional jump from the
1976 new bb to the original destination of the conditional jump. */
1979 fix_crossing_conditional_branches (void)
1990 rtx old_label
= NULL_RTX
;
1993 FOR_EACH_BB_FN (cur_bb
, cfun
)
1995 crossing_edge
= NULL
;
1996 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1997 succ1
= EDGE_SUCC (cur_bb
, 0);
2001 if (EDGE_COUNT (cur_bb
->succs
) > 1)
2002 succ2
= EDGE_SUCC (cur_bb
, 1);
2006 /* We already took care of fall-through edges, so only one successor
2007 can be a crossing edge. */
2009 if (succ1
&& (succ1
->flags
& EDGE_CROSSING
))
2010 crossing_edge
= succ1
;
2011 else if (succ2
&& (succ2
->flags
& EDGE_CROSSING
))
2012 crossing_edge
= succ2
;
2016 old_jump
= BB_END (cur_bb
);
2018 /* Check to make sure the jump instruction is a
2019 conditional jump. */
2023 if (any_condjump_p (old_jump
))
2025 if (GET_CODE (PATTERN (old_jump
)) == SET
)
2026 set_src
= SET_SRC (PATTERN (old_jump
));
2027 else if (GET_CODE (PATTERN (old_jump
)) == PARALLEL
)
2029 set_src
= XVECEXP (PATTERN (old_jump
), 0,0);
2030 if (GET_CODE (set_src
) == SET
)
2031 set_src
= SET_SRC (set_src
);
2037 if (set_src
&& (GET_CODE (set_src
) == IF_THEN_ELSE
))
2039 if (GET_CODE (XEXP (set_src
, 1)) == PC
)
2040 old_label
= XEXP (set_src
, 2);
2041 else if (GET_CODE (XEXP (set_src
, 2)) == PC
)
2042 old_label
= XEXP (set_src
, 1);
2044 /* Check to see if new bb for jumping to that dest has
2045 already been created; if so, use it; if not, create
2048 new_bb
= find_jump_block (crossing_edge
->dest
);
2051 new_label
= block_label (new_bb
);
2054 basic_block last_bb
;
2057 /* Create new basic block to be dest for
2058 conditional jump. */
2060 /* Put appropriate instructions in new bb. */
2062 new_label
= gen_label_rtx ();
2063 emit_label (new_label
);
2065 gcc_assert (GET_CODE (old_label
) == LABEL_REF
);
2066 old_label
= JUMP_LABEL (old_jump
);
2067 new_jump
= emit_jump_insn (gen_jump (old_label
));
2068 JUMP_LABEL (new_jump
) = old_label
;
2070 last_bb
= EXIT_BLOCK_PTR_FOR_FN (cfun
)->prev_bb
;
2071 new_bb
= create_basic_block (new_label
, new_jump
, last_bb
);
2072 new_bb
->aux
= last_bb
->aux
;
2073 last_bb
->aux
= new_bb
;
2075 emit_barrier_after_bb (new_bb
);
2077 /* Make sure new bb is in same partition as source
2078 of conditional branch. */
2079 BB_COPY_PARTITION (new_bb
, cur_bb
);
2082 /* Make old jump branch to new bb. */
2084 redirect_jump (old_jump
, new_label
, 0);
2086 /* Remove crossing_edge as predecessor of 'dest'. */
2088 dest
= crossing_edge
->dest
;
2090 redirect_edge_succ (crossing_edge
, new_bb
);
2092 /* Make a new edge from new_bb to old dest; new edge
2093 will be a successor for new_bb and a predecessor
2096 if (EDGE_COUNT (new_bb
->succs
) == 0)
2097 new_edge
= make_edge (new_bb
, dest
, 0);
2099 new_edge
= EDGE_SUCC (new_bb
, 0);
2101 crossing_edge
->flags
&= ~EDGE_CROSSING
;
2102 new_edge
->flags
|= EDGE_CROSSING
;
2108 /* Find any unconditional branches that cross between hot and cold
2109 sections. Convert them into indirect jumps instead. */
2112 fix_crossing_unconditional_branches (void)
2118 rtx indirect_jump_sequence
;
2119 rtx jump_insn
= NULL_RTX
;
2124 FOR_EACH_BB_FN (cur_bb
, cfun
)
2126 last_insn
= BB_END (cur_bb
);
2128 if (EDGE_COUNT (cur_bb
->succs
) < 1)
2131 succ
= EDGE_SUCC (cur_bb
, 0);
2133 /* Check to see if bb ends in a crossing (unconditional) jump. At
2134 this point, no crossing jumps should be conditional. */
2136 if (JUMP_P (last_insn
)
2137 && (succ
->flags
& EDGE_CROSSING
))
2139 gcc_assert (!any_condjump_p (last_insn
));
2141 /* Make sure the jump is not already an indirect or table jump. */
2143 if (!computed_jump_p (last_insn
)
2144 && !tablejump_p (last_insn
, NULL
, NULL
))
2146 /* We have found a "crossing" unconditional branch. Now
2147 we must convert it to an indirect jump. First create
2148 reference of label, as target for jump. */
2150 label
= JUMP_LABEL (last_insn
);
2151 label_addr
= gen_rtx_LABEL_REF (Pmode
, label
);
2152 LABEL_NUSES (label
) += 1;
2154 /* Get a register to use for the indirect jump. */
2156 new_reg
= gen_reg_rtx (Pmode
);
2158 /* Generate indirect the jump sequence. */
2161 emit_move_insn (new_reg
, label_addr
);
2162 emit_indirect_jump (new_reg
);
2163 indirect_jump_sequence
= get_insns ();
2166 /* Make sure every instruction in the new jump sequence has
2167 its basic block set to be cur_bb. */
2169 for (cur_insn
= indirect_jump_sequence
; cur_insn
;
2170 cur_insn
= NEXT_INSN (cur_insn
))
2172 if (!BARRIER_P (cur_insn
))
2173 BLOCK_FOR_INSN (cur_insn
) = cur_bb
;
2174 if (JUMP_P (cur_insn
))
2175 jump_insn
= cur_insn
;
2178 /* Insert the new (indirect) jump sequence immediately before
2179 the unconditional jump, then delete the unconditional jump. */
2181 emit_insn_before (indirect_jump_sequence
, last_insn
);
2182 delete_insn (last_insn
);
2184 JUMP_LABEL (jump_insn
) = label
;
2185 LABEL_NUSES (label
)++;
2187 /* Make BB_END for cur_bb be the jump instruction (NOT the
2188 barrier instruction at the end of the sequence...). */
2190 BB_END (cur_bb
) = jump_insn
;
2196 /* Update CROSSING_JUMP_P flags on all jump insns. */
2199 update_crossing_jump_flags (void)
2205 FOR_EACH_BB_FN (bb
, cfun
)
2206 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
2207 if (e
->flags
& EDGE_CROSSING
)
2209 if (JUMP_P (BB_END (bb
))
2210 /* Some flags were added during fix_up_fall_thru_edges, via
2211 force_nonfallthru_and_redirect. */
2212 && !CROSSING_JUMP_P (BB_END (bb
)))
2213 CROSSING_JUMP_P (BB_END (bb
)) = 1;
2218 /* Reorder basic blocks. The main entry point to this file. FLAGS is
2219 the set of flags to pass to cfg_layout_initialize(). */
2222 reorder_basic_blocks (void)
2226 struct trace
*traces
;
2228 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
2230 if (n_basic_blocks_for_fn (cfun
) <= NUM_FIXED_BLOCKS
+ 1)
2233 set_edge_can_fallthru_flag ();
2234 mark_dfs_back_edges ();
2236 /* We are estimating the length of uncond jump insn only once since the code
2237 for getting the insn length always returns the minimal length now. */
2238 if (uncond_jump_length
== 0)
2239 uncond_jump_length
= get_uncond_jump_length ();
2241 /* We need to know some information for each basic block. */
2242 array_size
= GET_ARRAY_SIZE (last_basic_block_for_fn (cfun
));
2243 bbd
= XNEWVEC (bbro_basic_block_data
, array_size
);
2244 for (i
= 0; i
< array_size
; i
++)
2246 bbd
[i
].start_of_trace
= -1;
2247 bbd
[i
].end_of_trace
= -1;
2248 bbd
[i
].in_trace
= -1;
2254 traces
= XNEWVEC (struct trace
, n_basic_blocks_for_fn (cfun
));
2256 find_traces (&n_traces
, traces
);
2257 connect_traces (n_traces
, traces
);
2261 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
2265 if (dump_flags
& TDF_DETAILS
)
2266 dump_reg_info (dump_file
);
2267 dump_flow_info (dump_file
, dump_flags
);
2270 /* Signal that rtl_verify_flow_info_1 can now verify that there
2271 is at most one switch between hot/cold sections. */
2272 crtl
->bb_reorder_complete
= true;
2275 /* Determine which partition the first basic block in the function
2276 belongs to, then find the first basic block in the current function
2277 that belongs to a different section, and insert a
2278 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
2279 instruction stream. When writing out the assembly code,
2280 encountering this note will make the compiler switch between the
2281 hot and cold text sections. */
2284 insert_section_boundary_note (void)
2287 bool switched_sections
= false;
2288 int current_partition
= 0;
2290 if (!crtl
->has_bb_partition
)
2293 FOR_EACH_BB_FN (bb
, cfun
)
2295 if (!current_partition
)
2296 current_partition
= BB_PARTITION (bb
);
2297 if (BB_PARTITION (bb
) != current_partition
)
2299 gcc_assert (!switched_sections
);
2300 switched_sections
= true;
2301 emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS
, BB_HEAD (bb
));
2302 current_partition
= BB_PARTITION (bb
);
2309 const pass_data pass_data_reorder_blocks
=
2311 RTL_PASS
, /* type */
2313 OPTGROUP_NONE
, /* optinfo_flags */
2314 true, /* has_execute */
2315 TV_REORDER_BLOCKS
, /* tv_id */
2316 0, /* properties_required */
2317 0, /* properties_provided */
2318 0, /* properties_destroyed */
2319 0, /* todo_flags_start */
2320 0, /* todo_flags_finish */
2323 class pass_reorder_blocks
: public rtl_opt_pass
2326 pass_reorder_blocks (gcc::context
*ctxt
)
2327 : rtl_opt_pass (pass_data_reorder_blocks
, ctxt
)
2330 /* opt_pass methods: */
2331 virtual bool gate (function
*)
2333 if (targetm
.cannot_modify_jumps_p ())
2335 return (optimize
> 0
2336 && (flag_reorder_blocks
|| flag_reorder_blocks_and_partition
));
2339 virtual unsigned int execute (function
*);
2341 }; // class pass_reorder_blocks
2344 pass_reorder_blocks::execute (function
*fun
)
2348 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2349 splitting possibly introduced more crossjumping opportunities. */
2350 cfg_layout_initialize (CLEANUP_EXPENSIVE
);
2352 reorder_basic_blocks ();
2353 cleanup_cfg (CLEANUP_EXPENSIVE
);
2355 FOR_EACH_BB_FN (bb
, fun
)
2356 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
2357 bb
->aux
= bb
->next_bb
;
2358 cfg_layout_finalize ();
2366 make_pass_reorder_blocks (gcc::context
*ctxt
)
2368 return new pass_reorder_blocks (ctxt
);
2371 /* Duplicate the blocks containing computed gotos. This basically unfactors
2372 computed gotos that were factored early on in the compilation process to
2373 speed up edge based data flow. We used to not unfactoring them again,
2374 which can seriously pessimize code with many computed jumps in the source
2375 code, such as interpreters. See e.g. PR15242. */
2379 const pass_data pass_data_duplicate_computed_gotos
=
2381 RTL_PASS
, /* type */
2382 "compgotos", /* name */
2383 OPTGROUP_NONE
, /* optinfo_flags */
2384 true, /* has_execute */
2385 TV_REORDER_BLOCKS
, /* tv_id */
2386 0, /* properties_required */
2387 0, /* properties_provided */
2388 0, /* properties_destroyed */
2389 0, /* todo_flags_start */
2390 0, /* todo_flags_finish */
2393 class pass_duplicate_computed_gotos
: public rtl_opt_pass
2396 pass_duplicate_computed_gotos (gcc::context
*ctxt
)
2397 : rtl_opt_pass (pass_data_duplicate_computed_gotos
, ctxt
)
2400 /* opt_pass methods: */
2401 virtual bool gate (function
*);
2402 virtual unsigned int execute (function
*);
2404 }; // class pass_duplicate_computed_gotos
2407 pass_duplicate_computed_gotos::gate (function
*fun
)
2409 if (targetm
.cannot_modify_jumps_p ())
2411 return (optimize
> 0
2412 && flag_expensive_optimizations
2413 && ! optimize_function_for_size_p (fun
));
2417 pass_duplicate_computed_gotos::execute (function
*fun
)
2419 basic_block bb
, new_bb
;
2422 bool changed
= false;
2424 if (n_basic_blocks_for_fn (fun
) <= NUM_FIXED_BLOCKS
+ 1)
2428 cfg_layout_initialize (0);
2430 /* We are estimating the length of uncond jump insn only once
2431 since the code for getting the insn length always returns
2432 the minimal length now. */
2433 if (uncond_jump_length
== 0)
2434 uncond_jump_length
= get_uncond_jump_length ();
2437 = uncond_jump_length
* PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS
);
2438 candidates
= BITMAP_ALLOC (NULL
);
2440 /* Look for blocks that end in a computed jump, and see if such blocks
2441 are suitable for unfactoring. If a block is a candidate for unfactoring,
2442 mark it in the candidates. */
2443 FOR_EACH_BB_FN (bb
, fun
)
2448 int size
, all_flags
;
2450 /* Build the reorder chain for the original order of blocks. */
2451 if (bb
->next_bb
!= EXIT_BLOCK_PTR_FOR_FN (fun
))
2452 bb
->aux
= bb
->next_bb
;
2454 /* Obviously the block has to end in a computed jump. */
2455 if (!computed_jump_p (BB_END (bb
)))
2458 /* Only consider blocks that can be duplicated. */
2459 if (CROSSING_JUMP_P (BB_END (bb
))
2460 || !can_duplicate_block_p (bb
))
2463 /* Make sure that the block is small enough. */
2465 FOR_BB_INSNS (bb
, insn
)
2468 size
+= get_attr_min_length (insn
);
2469 if (size
> max_size
)
2472 if (size
> max_size
)
2475 /* Final check: there must not be any incoming abnormal edges. */
2477 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2478 all_flags
|= e
->flags
;
2479 if (all_flags
& EDGE_COMPLEX
)
2482 bitmap_set_bit (candidates
, bb
->index
);
2485 /* Nothing to do if there is no computed jump here. */
2486 if (bitmap_empty_p (candidates
))
2489 /* Duplicate computed gotos. */
2490 FOR_EACH_BB_FN (bb
, fun
)
2492 if (bb
->flags
& BB_VISITED
)
2495 bb
->flags
|= BB_VISITED
;
2497 /* BB must have one outgoing edge. That edge must not lead to
2498 the exit block or the next block.
2499 The destination must have more than one predecessor. */
2500 if (!single_succ_p (bb
)
2501 || single_succ (bb
) == EXIT_BLOCK_PTR_FOR_FN (fun
)
2502 || single_succ (bb
) == bb
->next_bb
2503 || single_pred_p (single_succ (bb
)))
2506 /* The successor block has to be a duplication candidate. */
2507 if (!bitmap_bit_p (candidates
, single_succ (bb
)->index
))
2510 /* Don't duplicate a partition crossing edge, which requires difficult
2512 if (JUMP_P (BB_END (bb
)) && CROSSING_JUMP_P (BB_END (bb
)))
2515 new_bb
= duplicate_block (single_succ (bb
), single_succ_edge (bb
), bb
);
2516 new_bb
->aux
= bb
->aux
;
2518 new_bb
->flags
|= BB_VISITED
;
2523 /* Duplicating blocks above will redirect edges and may cause hot blocks
2524 previously reached by both hot and cold blocks to become dominated only
2527 fixup_partitions ();
2528 cfg_layout_finalize ();
2530 BITMAP_FREE (candidates
);
2537 make_pass_duplicate_computed_gotos (gcc::context
*ctxt
)
2539 return new pass_duplicate_computed_gotos (ctxt
);
2542 /* This function is the main 'entrance' for the optimization that
2543 partitions hot and cold basic blocks into separate sections of the
2544 .o file (to improve performance and cache locality). Ideally it
2545 would be called after all optimizations that rearrange the CFG have
2546 been called. However part of this optimization may introduce new
2547 register usage, so it must be called before register allocation has
2548 occurred. This means that this optimization is actually called
2549 well before the optimization that reorders basic blocks (see
2552 This optimization checks the feedback information to determine
2553 which basic blocks are hot/cold, updates flags on the basic blocks
2554 to indicate which section they belong in. This information is
2555 later used for writing out sections in the .o file. Because hot
2556 and cold sections can be arbitrarily large (within the bounds of
2557 memory), far beyond the size of a single function, it is necessary
2558 to fix up all edges that cross section boundaries, to make sure the
2559 instructions used can actually span the required distance. The
2560 fixes are described below.
2562 Fall-through edges must be changed into jumps; it is not safe or
2563 legal to fall through across a section boundary. Whenever a
2564 fall-through edge crossing a section boundary is encountered, a new
2565 basic block is inserted (in the same section as the fall-through
2566 source), and the fall through edge is redirected to the new basic
2567 block. The new basic block contains an unconditional jump to the
2568 original fall-through target. (If the unconditional jump is
2569 insufficient to cross section boundaries, that is dealt with a
2570 little later, see below).
2572 In order to deal with architectures that have short conditional
2573 branches (which cannot span all of memory) we take any conditional
2574 jump that attempts to cross a section boundary and add a level of
2575 indirection: it becomes a conditional jump to a new basic block, in
2576 the same section. The new basic block contains an unconditional
2577 jump to the original target, in the other section.
2579 For those architectures whose unconditional branch is also
2580 incapable of reaching all of memory, those unconditional jumps are
2581 converted into indirect jumps, through a register.
2583 IMPORTANT NOTE: This optimization causes some messy interactions
2584 with the cfg cleanup optimizations; those optimizations want to
2585 merge blocks wherever possible, and to collapse indirect jump
2586 sequences (change "A jumps to B jumps to C" directly into "A jumps
2587 to C"). Those optimizations can undo the jump fixes that
2588 partitioning is required to make (see above), in order to ensure
2589 that jumps attempting to cross section boundaries are really able
2590 to cover whatever distance the jump requires (on many architectures
2591 conditional or unconditional jumps are not able to reach all of
2592 memory). Therefore tests have to be inserted into each such
2593 optimization to make sure that it does not undo stuff necessary to
2594 cross partition boundaries. This would be much less of a problem
2595 if we could perform this optimization later in the compilation, but
2596 unfortunately the fact that we may need to create indirect jumps
2597 (through registers) requires that this optimization be performed
2598 before register allocation.
2600 Hot and cold basic blocks are partitioned and put in separate
2601 sections of the .o file, to reduce paging and improve cache
2602 performance (hopefully). This can result in bits of code from the
2603 same function being widely separated in the .o file. However this
2604 is not obvious to the current bb structure. Therefore we must take
2605 care to ensure that: 1). There are no fall_thru edges that cross
2606 between sections; 2). For those architectures which have "short"
2607 conditional branches, all conditional branches that attempt to
2608 cross between sections are converted to unconditional branches;
2609 and, 3). For those architectures which have "short" unconditional
2610 branches, all unconditional branches that attempt to cross between
2611 sections are converted to indirect jumps.
2613 The code for fixing up fall_thru edges that cross between hot and
2614 cold basic blocks does so by creating new basic blocks containing
2615 unconditional branches to the appropriate label in the "other"
2616 section. The new basic block is then put in the same (hot or cold)
2617 section as the original conditional branch, and the fall_thru edge
2618 is modified to fall into the new basic block instead. By adding
2619 this level of indirection we end up with only unconditional branches
2620 crossing between hot and cold sections.
2622 Conditional branches are dealt with by adding a level of indirection.
2623 A new basic block is added in the same (hot/cold) section as the
2624 conditional branch, and the conditional branch is retargeted to the
2625 new basic block. The new basic block contains an unconditional branch
2626 to the original target of the conditional branch (in the other section).
2628 Unconditional branches are dealt with by converting them into
2633 const pass_data pass_data_partition_blocks
=
2635 RTL_PASS
, /* type */
2636 "bbpart", /* name */
2637 OPTGROUP_NONE
, /* optinfo_flags */
2638 true, /* has_execute */
2639 TV_REORDER_BLOCKS
, /* tv_id */
2640 PROP_cfglayout
, /* properties_required */
2641 0, /* properties_provided */
2642 0, /* properties_destroyed */
2643 0, /* todo_flags_start */
2644 0, /* todo_flags_finish */
2647 class pass_partition_blocks
: public rtl_opt_pass
2650 pass_partition_blocks (gcc::context
*ctxt
)
2651 : rtl_opt_pass (pass_data_partition_blocks
, ctxt
)
2654 /* opt_pass methods: */
2655 virtual bool gate (function
*);
2656 virtual unsigned int execute (function
*);
2658 }; // class pass_partition_blocks
2661 pass_partition_blocks::gate (function
*fun
)
2663 /* The optimization to partition hot/cold basic blocks into separate
2664 sections of the .o file does not work well with linkonce or with
2665 user defined section attributes. Don't call it if either case
2667 return (flag_reorder_blocks_and_partition
2669 /* See gate_handle_reorder_blocks. We should not partition if
2670 we are going to omit the reordering. */
2671 && optimize_function_for_speed_p (fun
)
2672 && !DECL_COMDAT_GROUP (current_function_decl
)
2673 && !user_defined_section_attribute
);
2677 pass_partition_blocks::execute (function
*fun
)
2679 vec
<edge
> crossing_edges
;
2681 if (n_basic_blocks_for_fn (fun
) <= NUM_FIXED_BLOCKS
+ 1)
2684 df_set_flags (DF_DEFER_INSN_RESCAN
);
2686 crossing_edges
= find_rarely_executed_basic_blocks_and_crossing_edges ();
2687 if (!crossing_edges
.exists ())
2690 crtl
->has_bb_partition
= true;
2692 /* Make sure the source of any crossing edge ends in a jump and the
2693 destination of any crossing edge has a label. */
2694 add_labels_and_missing_jumps (crossing_edges
);
2696 /* Convert all crossing fall_thru edges to non-crossing fall
2697 thrus to unconditional jumps (that jump to the original fall
2699 fix_up_fall_thru_edges ();
2701 /* If the architecture does not have conditional branches that can
2702 span all of memory, convert crossing conditional branches into
2703 crossing unconditional branches. */
2704 if (!HAS_LONG_COND_BRANCH
)
2705 fix_crossing_conditional_branches ();
2707 /* If the architecture does not have unconditional branches that
2708 can span all of memory, convert crossing unconditional branches
2709 into indirect jumps. Since adding an indirect jump also adds
2710 a new register usage, update the register usage information as
2712 if (!HAS_LONG_UNCOND_BRANCH
)
2713 fix_crossing_unconditional_branches ();
2715 update_crossing_jump_flags ();
2717 /* Clear bb->aux fields that the above routines were using. */
2718 clear_aux_for_blocks ();
2720 crossing_edges
.release ();
2722 /* ??? FIXME: DF generates the bb info for a block immediately.
2723 And by immediately, I mean *during* creation of the block.
2725 #0 df_bb_refs_collect
2726 #1 in df_bb_refs_record
2727 #2 in create_basic_block_structure
2729 Which means that the bb_has_eh_pred test in df_bb_refs_collect
2730 will *always* fail, because no edges can have been added to the
2731 block yet. Which of course means we don't add the right
2732 artificial refs, which means we fail df_verify (much) later.
2734 Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
2735 that we also shouldn't grab data from the new blocks those new
2736 insns are in either. In this way one can create the block, link
2737 it up properly, and have everything Just Work later, when deferred
2738 insns are processed.
2740 In the meantime, we have no other option but to throw away all
2741 of the DF data and recompute it all. */
2742 if (fun
->eh
->lp_array
)
2744 df_finish_pass (true);
2745 df_scan_alloc (NULL
);
2747 /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
2748 data. We blindly generated all of them when creating the new
2749 landing pad. Delete those assignments we don't use. */
2750 df_set_flags (DF_LR_RUN_DCE
);
2760 make_pass_partition_blocks (gcc::context
*ctxt
)
2762 return new pass_partition_blocks (ctxt
);