1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011,
3 2012 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
12 GCC is distributed in the hope that it will be useful, but WITHOUT
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* This (greedy) algorithm constructs traces in several rounds.
22 The construction starts from "seeds". The seed for the first round
23 is the entry point of function. When there are more than one seed
24 that one is selected first that has the lowest key in the heap
25 (see function bb_to_key). Then the algorithm repeatedly adds the most
26 probable successor to the end of a trace. Finally it connects the traces.
28 There are two parameters: Branch Threshold and Exec Threshold.
29 If the edge to a successor of the actual basic block is lower than
30 Branch Threshold or the frequency of the successor is lower than
31 Exec Threshold the successor will be the seed in one of the next rounds.
32 Each round has these parameters lower than the previous one.
33 The last round has to have these parameters set to zero
34 so that the remaining blocks are picked up.
36 The algorithm selects the most probable successor from all unvisited
37 successors and successors that have been added to this trace.
38 The other successors (that has not been "sent" to the next round) will be
39 other seeds for this round and the secondary traces will start in them.
40 If the successor has not been visited in this trace it is added to the trace
41 (however, there is some heuristic for simple branches).
42 If the successor has been visited in this trace the loop has been found.
43 If the loop has many iterations the loop is rotated so that the
44 source block of the most probable edge going out from the loop
45 is the last block of the trace.
46 If the loop has few iterations and there is no edge from the last block of
47 the loop going out from loop the loop header is duplicated.
48 Finally, the construction of the trace is terminated.
50 When connecting traces it first checks whether there is an edge from the
51 last block of one trace to the first block of another trace.
52 When there are still some unconnected traces it checks whether there exists
53 a basic block BB such that BB is a successor of the last bb of one trace
54 and BB is a predecessor of the first block of another trace. In this case,
55 BB is duplicated and the traces are connected through this duplicate.
56 The rest of traces are simply connected so there will be a jump to the
57 beginning of the rest of trace.
62 "Software Trace Cache"
63 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
64 http://citeseer.nj.nec.com/15361.html
70 #include "coretypes.h"
77 #include "cfglayout.h"
85 #include "diagnostic-core.h"
86 #include "toplev.h" /* user_defined_section_attribute */
87 #include "tree-pass.h"
89 #include "bb-reorder.h"
92 /* The number of rounds. In most cases there will only be 4 rounds, but
93 when partitioning hot and cold basic blocks into separate sections of
94 the .o file there will be an extra round.*/
97 /* Stubs in case we don't have a return insn.
98 We have to check at runtime too, not only compiletime. */
101 #define HAVE_return 0
102 #define gen_return() NULL_RTX
106 struct target_bb_reorder default_target_bb_reorder
;
107 #if SWITCHABLE_TARGET
108 struct target_bb_reorder
*this_target_bb_reorder
= &default_target_bb_reorder
;
111 #define uncond_jump_length \
112 (this_target_bb_reorder->x_uncond_jump_length)
114 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
115 static int branch_threshold
[N_ROUNDS
] = {400, 200, 100, 0, 0};
117 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
118 static int exec_threshold
[N_ROUNDS
] = {500, 200, 50, 0, 0};
120 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
121 block the edge destination is not duplicated while connecting traces. */
122 #define DUPLICATION_THRESHOLD 100
124 /* Structure to hold needed information for each basic block. */
125 typedef struct bbro_basic_block_data_def
127 /* Which trace is the bb start of (-1 means it is not a start of a trace). */
130 /* Which trace is the bb end of (-1 means it is not an end of a trace). */
133 /* Which trace is the bb in? */
136 /* Which trace was this bb visited in? */
139 /* Which heap is BB in (if any)? */
142 /* Which heap node is BB in (if any)? */
144 } bbro_basic_block_data
;
146 /* The current size of the following dynamic array. */
147 static int array_size
;
149 /* The array which holds needed information for basic blocks. */
150 static bbro_basic_block_data
*bbd
;
152 /* To avoid frequent reallocation the size of arrays is greater than needed,
153 the number of elements is (not less than) 1.25 * size_wanted. */
154 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
156 /* Free the memory and set the pointer to NULL. */
157 #define FREE(P) (gcc_assert (P), free (P), P = 0)
159 /* Structure for holding information about a trace. */
162 /* First and last basic block of the trace. */
163 basic_block first
, last
;
165 /* The round of the STC creation which this trace was found in. */
168 /* The length (i.e. the number of basic blocks) of the trace. */
172 /* Maximum frequency and count of one of the entry blocks. */
173 static int max_entry_frequency
;
174 static gcov_type max_entry_count
;
176 /* Local function prototypes. */
177 static void find_traces (int *, struct trace
*);
178 static basic_block
rotate_loop (edge
, struct trace
*, int);
179 static void mark_bb_visited (basic_block
, int);
180 static void find_traces_1_round (int, int, gcov_type
, struct trace
*, int *,
181 int, fibheap_t
*, int);
182 static basic_block
copy_bb (basic_block
, edge
, basic_block
, int);
183 static fibheapkey_t
bb_to_key (basic_block
);
184 static bool better_edge_p (const_basic_block
, const_edge
, int, int, int, int, const_edge
);
185 static void connect_traces (int, struct trace
*);
186 static bool copy_bb_p (const_basic_block
, int);
187 static bool push_to_next_round_p (const_basic_block
, int, int, int, gcov_type
);
189 /* Return the trace number in which BB was visited. */
192 bb_visited_trace (const_basic_block bb
)
194 gcc_assert (bb
->index
< array_size
);
195 return bbd
[bb
->index
].visited
;
198 /* This function marks BB that it was visited in trace number TRACE. */
201 mark_bb_visited (basic_block bb
, int trace
)
203 bbd
[bb
->index
].visited
= trace
;
204 if (bbd
[bb
->index
].heap
)
206 fibheap_delete_node (bbd
[bb
->index
].heap
, bbd
[bb
->index
].node
);
207 bbd
[bb
->index
].heap
= NULL
;
208 bbd
[bb
->index
].node
= NULL
;
212 /* Check to see if bb should be pushed into the next round of trace
213 collections or not. Reasons for pushing the block forward are 1).
214 If the block is cold, we are doing partitioning, and there will be
215 another round (cold partition blocks are not supposed to be
216 collected into traces until the very last round); or 2). There will
217 be another round, and the basic block is not "hot enough" for the
218 current round of trace collection. */
221 push_to_next_round_p (const_basic_block bb
, int round
, int number_of_rounds
,
222 int exec_th
, gcov_type count_th
)
224 bool there_exists_another_round
;
225 bool block_not_hot_enough
;
227 there_exists_another_round
= round
< number_of_rounds
- 1;
229 block_not_hot_enough
= (bb
->frequency
< exec_th
230 || bb
->count
< count_th
231 || probably_never_executed_bb_p (bb
));
233 if (there_exists_another_round
234 && block_not_hot_enough
)
240 /* Find the traces for Software Trace Cache. Chain each trace through
241 RBI()->next. Store the number of traces to N_TRACES and description of
245 find_traces (int *n_traces
, struct trace
*traces
)
248 int number_of_rounds
;
253 /* Add one extra round of trace collection when partitioning hot/cold
254 basic blocks into separate sections. The last round is for all the
255 cold blocks (and ONLY the cold blocks). */
257 number_of_rounds
= N_ROUNDS
- 1;
259 /* Insert entry points of function into heap. */
260 heap
= fibheap_new ();
261 max_entry_frequency
= 0;
263 FOR_EACH_EDGE (e
, ei
, ENTRY_BLOCK_PTR
->succs
)
265 bbd
[e
->dest
->index
].heap
= heap
;
266 bbd
[e
->dest
->index
].node
= fibheap_insert (heap
, bb_to_key (e
->dest
),
268 if (e
->dest
->frequency
> max_entry_frequency
)
269 max_entry_frequency
= e
->dest
->frequency
;
270 if (e
->dest
->count
> max_entry_count
)
271 max_entry_count
= e
->dest
->count
;
274 /* Find the traces. */
275 for (i
= 0; i
< number_of_rounds
; i
++)
277 gcov_type count_threshold
;
280 fprintf (dump_file
, "STC - round %d\n", i
+ 1);
282 if (max_entry_count
< INT_MAX
/ 1000)
283 count_threshold
= max_entry_count
* exec_threshold
[i
] / 1000;
285 count_threshold
= max_entry_count
/ 1000 * exec_threshold
[i
];
287 find_traces_1_round (REG_BR_PROB_BASE
* branch_threshold
[i
] / 1000,
288 max_entry_frequency
* exec_threshold
[i
] / 1000,
289 count_threshold
, traces
, n_traces
, i
, &heap
,
292 fibheap_delete (heap
);
296 for (i
= 0; i
< *n_traces
; i
++)
299 fprintf (dump_file
, "Trace %d (round %d): ", i
+ 1,
300 traces
[i
].round
+ 1);
301 for (bb
= traces
[i
].first
; bb
!= traces
[i
].last
; bb
= (basic_block
) bb
->aux
)
302 fprintf (dump_file
, "%d [%d] ", bb
->index
, bb
->frequency
);
303 fprintf (dump_file
, "%d [%d]\n", bb
->index
, bb
->frequency
);
309 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
310 (with sequential number TRACE_N). */
313 rotate_loop (edge back_edge
, struct trace
*trace
, int trace_n
)
317 /* Information about the best end (end after rotation) of the loop. */
318 basic_block best_bb
= NULL
;
319 edge best_edge
= NULL
;
321 gcov_type best_count
= -1;
322 /* The best edge is preferred when its destination is not visited yet
323 or is a start block of some trace. */
324 bool is_preferred
= false;
326 /* Find the most frequent edge that goes out from current trace. */
327 bb
= back_edge
->dest
;
333 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
334 if (e
->dest
!= EXIT_BLOCK_PTR
335 && bb_visited_trace (e
->dest
) != trace_n
336 && (e
->flags
& EDGE_CAN_FALLTHRU
)
337 && !(e
->flags
& EDGE_COMPLEX
))
341 /* The best edge is preferred. */
342 if (!bb_visited_trace (e
->dest
)
343 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
345 /* The current edge E is also preferred. */
346 int freq
= EDGE_FREQUENCY (e
);
347 if (freq
> best_freq
|| e
->count
> best_count
)
350 best_count
= e
->count
;
358 if (!bb_visited_trace (e
->dest
)
359 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
361 /* The current edge E is preferred. */
363 best_freq
= EDGE_FREQUENCY (e
);
364 best_count
= e
->count
;
370 int freq
= EDGE_FREQUENCY (e
);
371 if (!best_edge
|| freq
> best_freq
|| e
->count
> best_count
)
374 best_count
= e
->count
;
381 bb
= (basic_block
) bb
->aux
;
383 while (bb
!= back_edge
->dest
);
387 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
389 if (back_edge
->dest
== trace
->first
)
391 trace
->first
= (basic_block
) best_bb
->aux
;
397 for (prev_bb
= trace
->first
;
398 prev_bb
->aux
!= back_edge
->dest
;
399 prev_bb
= (basic_block
) prev_bb
->aux
)
401 prev_bb
->aux
= best_bb
->aux
;
403 /* Try to get rid of uncond jump to cond jump. */
404 if (single_succ_p (prev_bb
))
406 basic_block header
= single_succ (prev_bb
);
408 /* Duplicate HEADER if it is a small block containing cond jump
410 if (any_condjump_p (BB_END (header
)) && copy_bb_p (header
, 0)
411 && !find_reg_note (BB_END (header
), REG_CROSSING_JUMP
,
413 copy_bb (header
, single_succ_edge (prev_bb
), prev_bb
, trace_n
);
419 /* We have not found suitable loop tail so do no rotation. */
420 best_bb
= back_edge
->src
;
426 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
427 not include basic blocks their probability is lower than BRANCH_TH or their
428 frequency is lower than EXEC_TH into traces (or count is lower than
429 COUNT_TH). It stores the new traces into TRACES and modifies the number of
430 traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
431 expects that starting basic blocks are in *HEAP and at the end it deletes
432 *HEAP and stores starting points for the next round into new *HEAP. */
435 find_traces_1_round (int branch_th
, int exec_th
, gcov_type count_th
,
436 struct trace
*traces
, int *n_traces
, int round
,
437 fibheap_t
*heap
, int number_of_rounds
)
439 /* Heap for discarded basic blocks which are possible starting points for
441 fibheap_t new_heap
= fibheap_new ();
443 while (!fibheap_empty (*heap
))
451 bb
= (basic_block
) fibheap_extract_min (*heap
);
452 bbd
[bb
->index
].heap
= NULL
;
453 bbd
[bb
->index
].node
= NULL
;
456 fprintf (dump_file
, "Getting bb %d\n", bb
->index
);
458 /* If the BB's frequency is too low send BB to the next round. When
459 partitioning hot/cold blocks into separate sections, make sure all
460 the cold blocks (and ONLY the cold blocks) go into the (extra) final
463 if (push_to_next_round_p (bb
, round
, number_of_rounds
, exec_th
,
466 int key
= bb_to_key (bb
);
467 bbd
[bb
->index
].heap
= new_heap
;
468 bbd
[bb
->index
].node
= fibheap_insert (new_heap
, key
, bb
);
472 " Possible start point of next round: %d (key: %d)\n",
477 trace
= traces
+ *n_traces
;
479 trace
->round
= round
;
481 bbd
[bb
->index
].in_trace
= *n_traces
;
489 /* The probability and frequency of the best edge. */
490 int best_prob
= INT_MIN
/ 2;
491 int best_freq
= INT_MIN
/ 2;
494 mark_bb_visited (bb
, *n_traces
);
498 fprintf (dump_file
, "Basic block %d was visited in trace %d\n",
499 bb
->index
, *n_traces
- 1);
501 ends_in_call
= block_ends_with_call_p (bb
);
503 /* Select the successor that will be placed after BB. */
504 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
506 gcc_assert (!(e
->flags
& EDGE_FAKE
));
508 if (e
->dest
== EXIT_BLOCK_PTR
)
511 if (bb_visited_trace (e
->dest
)
512 && bb_visited_trace (e
->dest
) != *n_traces
)
515 if (BB_PARTITION (e
->dest
) != BB_PARTITION (bb
))
518 prob
= e
->probability
;
519 freq
= e
->dest
->frequency
;
521 /* The only sensible preference for a call instruction is the
522 fallthru edge. Don't bother selecting anything else. */
525 if (e
->flags
& EDGE_CAN_FALLTHRU
)
534 /* Edge that cannot be fallthru or improbable or infrequent
535 successor (i.e. it is unsuitable successor). */
536 if (!(e
->flags
& EDGE_CAN_FALLTHRU
) || (e
->flags
& EDGE_COMPLEX
)
537 || prob
< branch_th
|| EDGE_FREQUENCY (e
) < exec_th
538 || e
->count
< count_th
)
541 /* If partitioning hot/cold basic blocks, don't consider edges
542 that cross section boundaries. */
544 if (better_edge_p (bb
, e
, prob
, freq
, best_prob
, best_freq
,
553 /* If the best destination has multiple predecessors, and can be
554 duplicated cheaper than a jump, don't allow it to be added
555 to a trace. We'll duplicate it when connecting traces. */
556 if (best_edge
&& EDGE_COUNT (best_edge
->dest
->preds
) >= 2
557 && copy_bb_p (best_edge
->dest
, 0))
560 /* Add all non-selected successors to the heaps. */
561 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
564 || e
->dest
== EXIT_BLOCK_PTR
565 || bb_visited_trace (e
->dest
))
568 key
= bb_to_key (e
->dest
);
570 if (bbd
[e
->dest
->index
].heap
)
572 /* E->DEST is already in some heap. */
573 if (key
!= bbd
[e
->dest
->index
].node
->key
)
578 "Changing key for bb %d from %ld to %ld.\n",
580 (long) bbd
[e
->dest
->index
].node
->key
,
583 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
584 bbd
[e
->dest
->index
].node
, key
);
589 fibheap_t which_heap
= *heap
;
591 prob
= e
->probability
;
592 freq
= EDGE_FREQUENCY (e
);
594 if (!(e
->flags
& EDGE_CAN_FALLTHRU
)
595 || (e
->flags
& EDGE_COMPLEX
)
596 || prob
< branch_th
|| freq
< exec_th
597 || e
->count
< count_th
)
599 /* When partitioning hot/cold basic blocks, make sure
600 the cold blocks (and only the cold blocks) all get
601 pushed to the last round of trace collection. */
603 if (push_to_next_round_p (e
->dest
, round
,
606 which_heap
= new_heap
;
609 bbd
[e
->dest
->index
].heap
= which_heap
;
610 bbd
[e
->dest
->index
].node
= fibheap_insert (which_heap
,
616 " Possible start of %s round: %d (key: %ld)\n",
617 (which_heap
== new_heap
) ? "next" : "this",
618 e
->dest
->index
, (long) key
);
624 if (best_edge
) /* Suitable successor was found. */
626 if (bb_visited_trace (best_edge
->dest
) == *n_traces
)
628 /* We do nothing with one basic block loops. */
629 if (best_edge
->dest
!= bb
)
631 if (EDGE_FREQUENCY (best_edge
)
632 > 4 * best_edge
->dest
->frequency
/ 5)
634 /* The loop has at least 4 iterations. If the loop
635 header is not the first block of the function
636 we can rotate the loop. */
638 if (best_edge
->dest
!= ENTRY_BLOCK_PTR
->next_bb
)
643 "Rotating loop %d - %d\n",
644 best_edge
->dest
->index
, bb
->index
);
646 bb
->aux
= best_edge
->dest
;
647 bbd
[best_edge
->dest
->index
].in_trace
=
649 bb
= rotate_loop (best_edge
, trace
, *n_traces
);
654 /* The loop has less than 4 iterations. */
656 if (single_succ_p (bb
)
657 && copy_bb_p (best_edge
->dest
,
658 optimize_edge_for_speed_p (best_edge
)))
660 bb
= copy_bb (best_edge
->dest
, best_edge
, bb
,
667 /* Terminate the trace. */
672 /* Check for a situation
681 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
682 >= EDGE_FREQUENCY (AC).
683 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
684 Best ordering is then A B C.
686 This situation is created for example by:
693 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
695 && (e
->flags
& EDGE_CAN_FALLTHRU
)
696 && !(e
->flags
& EDGE_COMPLEX
)
697 && !bb_visited_trace (e
->dest
)
698 && single_pred_p (e
->dest
)
699 && !(e
->flags
& EDGE_CROSSING
)
700 && single_succ_p (e
->dest
)
701 && (single_succ_edge (e
->dest
)->flags
703 && !(single_succ_edge (e
->dest
)->flags
& EDGE_COMPLEX
)
704 && single_succ (e
->dest
) == best_edge
->dest
705 && 2 * e
->dest
->frequency
>= EDGE_FREQUENCY (best_edge
))
709 fprintf (dump_file
, "Selecting BB %d\n",
710 best_edge
->dest
->index
);
714 bb
->aux
= best_edge
->dest
;
715 bbd
[best_edge
->dest
->index
].in_trace
= (*n_traces
) - 1;
716 bb
= best_edge
->dest
;
722 bbd
[trace
->first
->index
].start_of_trace
= *n_traces
- 1;
723 bbd
[trace
->last
->index
].end_of_trace
= *n_traces
- 1;
725 /* The trace is terminated so we have to recount the keys in heap
726 (some block can have a lower key because now one of its predecessors
727 is an end of the trace). */
728 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
730 if (e
->dest
== EXIT_BLOCK_PTR
731 || bb_visited_trace (e
->dest
))
734 if (bbd
[e
->dest
->index
].heap
)
736 key
= bb_to_key (e
->dest
);
737 if (key
!= bbd
[e
->dest
->index
].node
->key
)
742 "Changing key for bb %d from %ld to %ld.\n",
744 (long) bbd
[e
->dest
->index
].node
->key
, key
);
746 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
747 bbd
[e
->dest
->index
].node
,
754 fibheap_delete (*heap
);
756 /* "Return" the new heap. */
760 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
761 it to trace after BB, mark OLD_BB visited and update pass' data structures
762 (TRACE is a number of trace which OLD_BB is duplicated to). */
765 copy_bb (basic_block old_bb
, edge e
, basic_block bb
, int trace
)
769 new_bb
= duplicate_block (old_bb
, e
, bb
);
770 BB_COPY_PARTITION (new_bb
, old_bb
);
772 gcc_assert (e
->dest
== new_bb
);
776 "Duplicated bb %d (created bb %d)\n",
777 old_bb
->index
, new_bb
->index
);
779 if (new_bb
->index
>= array_size
|| last_basic_block
> array_size
)
784 new_size
= MAX (last_basic_block
, new_bb
->index
+ 1);
785 new_size
= GET_ARRAY_SIZE (new_size
);
786 bbd
= XRESIZEVEC (bbro_basic_block_data
, bbd
, new_size
);
787 for (i
= array_size
; i
< new_size
; i
++)
789 bbd
[i
].start_of_trace
= -1;
790 bbd
[i
].end_of_trace
= -1;
791 bbd
[i
].in_trace
= -1;
796 array_size
= new_size
;
801 "Growing the dynamic array to %d elements.\n",
806 gcc_assert (!bb_visited_trace (e
->dest
));
807 mark_bb_visited (new_bb
, trace
);
808 new_bb
->aux
= bb
->aux
;
811 bbd
[new_bb
->index
].in_trace
= trace
;
816 /* Compute and return the key (for the heap) of the basic block BB. */
819 bb_to_key (basic_block bb
)
825 /* Do not start in probably never executed blocks. */
827 if (BB_PARTITION (bb
) == BB_COLD_PARTITION
828 || probably_never_executed_bb_p (bb
))
831 /* Prefer blocks whose predecessor is an end of some trace
832 or whose predecessor edge is EDGE_DFS_BACK. */
833 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
835 if ((e
->src
!= ENTRY_BLOCK_PTR
&& bbd
[e
->src
->index
].end_of_trace
>= 0)
836 || (e
->flags
& EDGE_DFS_BACK
))
838 int edge_freq
= EDGE_FREQUENCY (e
);
840 if (edge_freq
> priority
)
841 priority
= edge_freq
;
846 /* The block with priority should have significantly lower key. */
847 return -(100 * BB_FREQ_MAX
+ 100 * priority
+ bb
->frequency
);
848 return -bb
->frequency
;
851 /* Return true when the edge E from basic block BB is better than the temporary
852 best edge (details are in function). The probability of edge E is PROB. The
853 frequency of the successor is FREQ. The current best probability is
854 BEST_PROB, the best frequency is BEST_FREQ.
855 The edge is considered to be equivalent when PROB does not differ much from
856 BEST_PROB; similarly for frequency. */
859 better_edge_p (const_basic_block bb
, const_edge e
, int prob
, int freq
, int best_prob
,
860 int best_freq
, const_edge cur_best_edge
)
864 /* The BEST_* values do not have to be best, but can be a bit smaller than
866 int diff_prob
= best_prob
/ 10;
867 int diff_freq
= best_freq
/ 10;
869 if (prob
> best_prob
+ diff_prob
)
870 /* The edge has higher probability than the temporary best edge. */
871 is_better_edge
= true;
872 else if (prob
< best_prob
- diff_prob
)
873 /* The edge has lower probability than the temporary best edge. */
874 is_better_edge
= false;
875 else if (freq
< best_freq
- diff_freq
)
876 /* The edge and the temporary best edge have almost equivalent
877 probabilities. The higher frequency of a successor now means
878 that there is another edge going into that successor.
879 This successor has lower frequency so it is better. */
880 is_better_edge
= true;
881 else if (freq
> best_freq
+ diff_freq
)
882 /* This successor has higher frequency so it is worse. */
883 is_better_edge
= false;
884 else if (e
->dest
->prev_bb
== bb
)
885 /* The edges have equivalent probabilities and the successors
886 have equivalent frequencies. Select the previous successor. */
887 is_better_edge
= true;
889 is_better_edge
= false;
891 /* If we are doing hot/cold partitioning, make sure that we always favor
892 non-crossing edges over crossing edges. */
895 && flag_reorder_blocks_and_partition
897 && (cur_best_edge
->flags
& EDGE_CROSSING
)
898 && !(e
->flags
& EDGE_CROSSING
))
899 is_better_edge
= true;
901 return is_better_edge
;
904 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
907 connect_traces (int n_traces
, struct trace
*traces
)
914 int current_partition
;
916 gcov_type count_threshold
;
918 freq_threshold
= max_entry_frequency
* DUPLICATION_THRESHOLD
/ 1000;
919 if (max_entry_count
< INT_MAX
/ 1000)
920 count_threshold
= max_entry_count
* DUPLICATION_THRESHOLD
/ 1000;
922 count_threshold
= max_entry_count
/ 1000 * DUPLICATION_THRESHOLD
;
924 connected
= XCNEWVEC (bool, n_traces
);
927 current_partition
= BB_PARTITION (traces
[0].first
);
930 if (flag_reorder_blocks_and_partition
)
931 for (i
= 0; i
< n_traces
&& !two_passes
; i
++)
932 if (BB_PARTITION (traces
[0].first
)
933 != BB_PARTITION (traces
[i
].first
))
936 for (i
= 0; i
< n_traces
|| (two_passes
&& current_pass
== 1) ; i
++)
945 gcc_assert (two_passes
&& current_pass
== 1);
949 if (current_partition
== BB_HOT_PARTITION
)
950 current_partition
= BB_COLD_PARTITION
;
952 current_partition
= BB_HOT_PARTITION
;
959 && BB_PARTITION (traces
[t
].first
) != current_partition
)
964 /* Find the predecessor traces. */
965 for (t2
= t
; t2
> 0;)
970 FOR_EACH_EDGE (e
, ei
, traces
[t2
].first
->preds
)
972 int si
= e
->src
->index
;
974 if (e
->src
!= ENTRY_BLOCK_PTR
975 && (e
->flags
& EDGE_CAN_FALLTHRU
)
976 && !(e
->flags
& EDGE_COMPLEX
)
977 && bbd
[si
].end_of_trace
>= 0
978 && !connected
[bbd
[si
].end_of_trace
]
979 && (BB_PARTITION (e
->src
) == current_partition
)
981 || e
->probability
> best
->probability
982 || (e
->probability
== best
->probability
983 && traces
[bbd
[si
].end_of_trace
].length
> best_len
)))
986 best_len
= traces
[bbd
[si
].end_of_trace
].length
;
991 best
->src
->aux
= best
->dest
;
992 t2
= bbd
[best
->src
->index
].end_of_trace
;
993 connected
[t2
] = true;
997 fprintf (dump_file
, "Connection: %d %d\n",
998 best
->src
->index
, best
->dest
->index
);
1005 if (last_trace
>= 0)
1006 traces
[last_trace
].last
->aux
= traces
[t2
].first
;
1009 /* Find the successor traces. */
1012 /* Find the continuation of the chain. */
1016 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1018 int di
= e
->dest
->index
;
1020 if (e
->dest
!= EXIT_BLOCK_PTR
1021 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1022 && !(e
->flags
& EDGE_COMPLEX
)
1023 && bbd
[di
].start_of_trace
>= 0
1024 && !connected
[bbd
[di
].start_of_trace
]
1025 && (BB_PARTITION (e
->dest
) == current_partition
)
1027 || e
->probability
> best
->probability
1028 || (e
->probability
== best
->probability
1029 && traces
[bbd
[di
].start_of_trace
].length
> best_len
)))
1032 best_len
= traces
[bbd
[di
].start_of_trace
].length
;
1040 fprintf (dump_file
, "Connection: %d %d\n",
1041 best
->src
->index
, best
->dest
->index
);
1043 t
= bbd
[best
->dest
->index
].start_of_trace
;
1044 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1045 connected
[t
] = true;
1050 /* Try to connect the traces by duplication of 1 block. */
1052 basic_block next_bb
= NULL
;
1053 bool try_copy
= false;
1055 FOR_EACH_EDGE (e
, ei
, traces
[t
].last
->succs
)
1056 if (e
->dest
!= EXIT_BLOCK_PTR
1057 && (e
->flags
& EDGE_CAN_FALLTHRU
)
1058 && !(e
->flags
& EDGE_COMPLEX
)
1059 && (!best
|| e
->probability
> best
->probability
))
1065 /* If the destination is a start of a trace which is only
1066 one block long, then no need to search the successor
1067 blocks of the trace. Accept it. */
1068 if (bbd
[e
->dest
->index
].start_of_trace
>= 0
1069 && traces
[bbd
[e
->dest
->index
].start_of_trace
].length
1077 FOR_EACH_EDGE (e2
, ei
, e
->dest
->succs
)
1079 int di
= e2
->dest
->index
;
1081 if (e2
->dest
== EXIT_BLOCK_PTR
1082 || ((e2
->flags
& EDGE_CAN_FALLTHRU
)
1083 && !(e2
->flags
& EDGE_COMPLEX
)
1084 && bbd
[di
].start_of_trace
>= 0
1085 && !connected
[bbd
[di
].start_of_trace
]
1086 && (BB_PARTITION (e2
->dest
) == current_partition
)
1087 && (EDGE_FREQUENCY (e2
) >= freq_threshold
)
1088 && (e2
->count
>= count_threshold
)
1090 || e2
->probability
> best2
->probability
1091 || (e2
->probability
== best2
->probability
1092 && traces
[bbd
[di
].start_of_trace
].length
1097 if (e2
->dest
!= EXIT_BLOCK_PTR
)
1098 best2_len
= traces
[bbd
[di
].start_of_trace
].length
;
1100 best2_len
= INT_MAX
;
1107 if (flag_reorder_blocks_and_partition
)
1110 /* Copy tiny blocks always; copy larger blocks only when the
1111 edge is traversed frequently enough. */
1113 && copy_bb_p (best
->dest
,
1114 optimize_edge_for_speed_p (best
)
1115 && EDGE_FREQUENCY (best
) >= freq_threshold
1116 && best
->count
>= count_threshold
))
1122 fprintf (dump_file
, "Connection: %d %d ",
1123 traces
[t
].last
->index
, best
->dest
->index
);
1125 fputc ('\n', dump_file
);
1126 else if (next_bb
== EXIT_BLOCK_PTR
)
1127 fprintf (dump_file
, "exit\n");
1129 fprintf (dump_file
, "%d\n", next_bb
->index
);
1132 new_bb
= copy_bb (best
->dest
, best
, traces
[t
].last
, t
);
1133 traces
[t
].last
= new_bb
;
1134 if (next_bb
&& next_bb
!= EXIT_BLOCK_PTR
)
1136 t
= bbd
[next_bb
->index
].start_of_trace
;
1137 traces
[last_trace
].last
->aux
= traces
[t
].first
;
1138 connected
[t
] = true;
1142 break; /* Stop finding the successor traces. */
1145 break; /* Stop finding the successor traces. */
1154 fprintf (dump_file
, "Final order:\n");
1155 for (bb
= traces
[0].first
; bb
; bb
= (basic_block
) bb
->aux
)
1156 fprintf (dump_file
, "%d ", bb
->index
);
1157 fprintf (dump_file
, "\n");
1164 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1165 when code size is allowed to grow by duplication. */
1168 copy_bb_p (const_basic_block bb
, int code_may_grow
)
1171 int max_size
= uncond_jump_length
;
1176 if (EDGE_COUNT (bb
->preds
) < 2)
1178 if (!can_duplicate_block_p (bb
))
1181 /* Avoid duplicating blocks which have many successors (PR/13430). */
1182 if (EDGE_COUNT (bb
->succs
) > 8)
1185 if (code_may_grow
&& optimize_bb_for_speed_p (bb
))
1186 max_size
*= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS
);
1188 FOR_BB_INSNS (bb
, insn
)
1191 size
+= get_attr_min_length (insn
);
1194 if (size
<= max_size
)
1200 "Block %d can't be copied because its size = %d.\n",
1207 /* Return the length of unconditional jump instruction. */
1210 get_uncond_jump_length (void)
1215 label
= emit_label_before (gen_label_rtx (), get_insns ());
1216 jump
= emit_jump_insn (gen_jump (label
));
1218 length
= get_attr_min_length (jump
);
1221 delete_insn (label
);
1225 /* Emit a barrier into the footer of BB. */
1228 emit_barrier_after_bb (basic_block bb
)
1230 rtx barrier
= emit_barrier_after (BB_END (bb
));
1231 BB_FOOTER (bb
) = unlink_insn_chain (barrier
, barrier
);
1234 /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1235 Duplicate the landing pad and split the edges so that no EH edge
1236 crosses partitions. */
1239 fix_up_crossing_landing_pad (eh_landing_pad old_lp
, basic_block old_bb
)
1241 eh_landing_pad new_lp
;
1242 basic_block new_bb
, last_bb
, post_bb
;
1243 rtx new_label
, jump
, post_label
;
1244 unsigned new_partition
;
1248 /* Generate the new landing-pad structure. */
1249 new_lp
= gen_eh_landing_pad (old_lp
->region
);
1250 new_lp
->post_landing_pad
= old_lp
->post_landing_pad
;
1251 new_lp
->landing_pad
= gen_label_rtx ();
1252 LABEL_PRESERVE_P (new_lp
->landing_pad
) = 1;
1254 /* Put appropriate instructions in new bb. */
1255 new_label
= emit_label (new_lp
->landing_pad
);
1257 expand_dw2_landing_pad_for_region (old_lp
->region
);
1259 post_bb
= BLOCK_FOR_INSN (old_lp
->landing_pad
);
1260 post_bb
= single_succ (post_bb
);
1261 post_label
= block_label (post_bb
);
1262 jump
= emit_jump_insn (gen_jump (post_label
));
1263 JUMP_LABEL (jump
) = post_label
;
1265 /* Create new basic block to be dest for lp. */
1266 last_bb
= EXIT_BLOCK_PTR
->prev_bb
;
1267 new_bb
= create_basic_block (new_label
, jump
, last_bb
);
1268 new_bb
->aux
= last_bb
->aux
;
1269 last_bb
->aux
= new_bb
;
1271 emit_barrier_after_bb (new_bb
);
1273 make_edge (new_bb
, post_bb
, 0);
1275 /* Make sure new bb is in the other partition. */
1276 new_partition
= BB_PARTITION (old_bb
);
1277 new_partition
^= BB_HOT_PARTITION
| BB_COLD_PARTITION
;
1278 BB_SET_PARTITION (new_bb
, new_partition
);
1280 /* Fix up the edges. */
1281 for (ei
= ei_start (old_bb
->preds
); (e
= ei_safe_edge (ei
)) != NULL
; )
1282 if (BB_PARTITION (e
->src
) == new_partition
)
1284 rtx insn
= BB_END (e
->src
);
1285 rtx note
= find_reg_note (insn
, REG_EH_REGION
, NULL_RTX
);
1287 gcc_assert (note
!= NULL
);
1288 gcc_checking_assert (INTVAL (XEXP (note
, 0)) == old_lp
->index
);
1289 XEXP (note
, 0) = GEN_INT (new_lp
->index
);
1291 /* Adjust the edge to the new destination. */
1292 redirect_edge_succ (e
, new_bb
);
1298 /* Find the basic blocks that are rarely executed and need to be moved to
1299 a separate section of the .o file (to cut down on paging and improve
1300 cache locality). Return a vector of all edges that cross. */
1302 static VEC(edge
, heap
) *
1303 find_rarely_executed_basic_blocks_and_crossing_edges (void)
1305 VEC(edge
, heap
) *crossing_edges
= NULL
;
1310 /* Mark which partition (hot/cold) each basic block belongs in. */
1313 if (probably_never_executed_bb_p (bb
))
1314 BB_SET_PARTITION (bb
, BB_COLD_PARTITION
);
1316 BB_SET_PARTITION (bb
, BB_HOT_PARTITION
);
1319 /* The format of .gcc_except_table does not allow landing pads to
1320 be in a different partition as the throw. Fix this by either
1321 moving or duplicating the landing pads. */
1322 if (cfun
->eh
->lp_array
)
1327 FOR_EACH_VEC_ELT (eh_landing_pad
, cfun
->eh
->lp_array
, i
, lp
)
1329 bool all_same
, all_diff
;
1332 || lp
->landing_pad
== NULL_RTX
1333 || !LABEL_P (lp
->landing_pad
))
1336 all_same
= all_diff
= true;
1337 bb
= BLOCK_FOR_INSN (lp
->landing_pad
);
1338 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
1340 gcc_assert (e
->flags
& EDGE_EH
);
1341 if (BB_PARTITION (bb
) == BB_PARTITION (e
->src
))
1351 int which
= BB_PARTITION (bb
);
1352 which
^= BB_HOT_PARTITION
| BB_COLD_PARTITION
;
1353 BB_SET_PARTITION (bb
, which
);
1356 fix_up_crossing_landing_pad (lp
, bb
);
1360 /* Mark every edge that crosses between sections. */
1363 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1365 unsigned int flags
= e
->flags
;
1367 /* We should never have EDGE_CROSSING set yet. */
1368 gcc_checking_assert ((flags
& EDGE_CROSSING
) == 0);
1370 if (e
->src
!= ENTRY_BLOCK_PTR
1371 && e
->dest
!= EXIT_BLOCK_PTR
1372 && BB_PARTITION (e
->src
) != BB_PARTITION (e
->dest
))
1374 VEC_safe_push (edge
, heap
, crossing_edges
, e
);
1375 flags
|= EDGE_CROSSING
;
1378 /* Now that we've split eh edges as appropriate, allow landing pads
1379 to be merged with the post-landing pads. */
1380 flags
&= ~EDGE_PRESERVE
;
1385 return crossing_edges
;
1388 /* If any destination of a crossing edge does not have a label, add label;
1389 Convert any easy fall-through crossing edges to unconditional jumps. */
1392 add_labels_and_missing_jumps (VEC(edge
, heap
) *crossing_edges
)
1397 FOR_EACH_VEC_ELT (edge
, crossing_edges
, i
, e
)
1399 basic_block src
= e
->src
;
1400 basic_block dest
= e
->dest
;
1401 rtx label
, new_jump
;
1403 if (dest
== EXIT_BLOCK_PTR
)
1406 /* Make sure dest has a label. */
1407 label
= block_label (dest
);
1409 /* Nothing to do for non-fallthru edges. */
1410 if (src
== ENTRY_BLOCK_PTR
)
1412 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
1415 /* If the block does not end with a control flow insn, then we
1416 can trivially add a jump to the end to fixup the crossing.
1417 Otherwise the jump will have to go in a new bb, which will
1418 be handled by fix_up_fall_thru_edges function. */
1419 if (control_flow_insn_p (BB_END (src
)))
1422 /* Make sure there's only one successor. */
1423 gcc_assert (single_succ_p (src
));
1425 new_jump
= emit_jump_insn_after (gen_jump (label
), BB_END (src
));
1426 BB_END (src
) = new_jump
;
1427 JUMP_LABEL (new_jump
) = label
;
1428 LABEL_NUSES (label
) += 1;
1430 emit_barrier_after_bb (src
);
1432 /* Mark edge as non-fallthru. */
1433 e
->flags
&= ~EDGE_FALLTHRU
;
1437 /* Find any bb's where the fall-through edge is a crossing edge (note that
1438 these bb's must also contain a conditional jump or end with a call
1439 instruction; we've already dealt with fall-through edges for blocks
1440 that didn't have a conditional jump or didn't end with call instruction
1441 in the call to add_labels_and_missing_jumps). Convert the fall-through
1442 edge to non-crossing edge by inserting a new bb to fall-through into.
1443 The new bb will contain an unconditional jump (crossing edge) to the
1444 original fall through destination. */
1447 fix_up_fall_thru_edges (void)
1454 edge cond_jump
= NULL
;
1456 bool cond_jump_crosses
;
1459 rtx fall_thru_label
;
1461 FOR_EACH_BB (cur_bb
)
1464 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1465 succ1
= EDGE_SUCC (cur_bb
, 0);
1469 if (EDGE_COUNT (cur_bb
->succs
) > 1)
1470 succ2
= EDGE_SUCC (cur_bb
, 1);
1474 /* Find the fall-through edge. */
1477 && (succ1
->flags
& EDGE_FALLTHRU
))
1483 && (succ2
->flags
& EDGE_FALLTHRU
))
1489 && (block_ends_with_call_p (cur_bb
)
1490 || can_throw_internal (BB_END (cur_bb
))))
1495 /* Find EDGE_CAN_FALLTHRU edge. */
1496 FOR_EACH_EDGE (e
, ei
, cur_bb
->succs
)
1497 if (e
->flags
& EDGE_CAN_FALLTHRU
)
1504 if (fall_thru
&& (fall_thru
->dest
!= EXIT_BLOCK_PTR
))
1506 /* Check to see if the fall-thru edge is a crossing edge. */
1508 if (fall_thru
->flags
& EDGE_CROSSING
)
1510 /* The fall_thru edge crosses; now check the cond jump edge, if
1513 cond_jump_crosses
= true;
1515 old_jump
= BB_END (cur_bb
);
1517 /* Find the jump instruction, if there is one. */
1521 if (!(cond_jump
->flags
& EDGE_CROSSING
))
1522 cond_jump_crosses
= false;
1524 /* We know the fall-thru edge crosses; if the cond
1525 jump edge does NOT cross, and its destination is the
1526 next block in the bb order, invert the jump
1527 (i.e. fix it so the fall through does not cross and
1528 the cond jump does). */
1530 if (!cond_jump_crosses
1531 && cur_bb
->aux
== cond_jump
->dest
)
1533 /* Find label in fall_thru block. We've already added
1534 any missing labels, so there must be one. */
1536 fall_thru_label
= block_label (fall_thru
->dest
);
1538 if (old_jump
&& JUMP_P (old_jump
) && fall_thru_label
)
1539 invert_worked
= invert_jump (old_jump
,
1543 fall_thru
->flags
&= ~EDGE_FALLTHRU
;
1544 cond_jump
->flags
|= EDGE_FALLTHRU
;
1545 update_br_prob_note (cur_bb
);
1547 fall_thru
= cond_jump
;
1549 cond_jump
->flags
|= EDGE_CROSSING
;
1550 fall_thru
->flags
&= ~EDGE_CROSSING
;
1555 if (cond_jump_crosses
|| !invert_worked
)
1557 /* This is the case where both edges out of the basic
1558 block are crossing edges. Here we will fix up the
1559 fall through edge. The jump edge will be taken care
1560 of later. The EDGE_CROSSING flag of fall_thru edge
1561 is unset before the call to force_nonfallthru
1562 function because if a new basic-block is created
1563 this edge remains in the current section boundary
1564 while the edge between new_bb and the fall_thru->dest
1565 becomes EDGE_CROSSING. */
1567 fall_thru
->flags
&= ~EDGE_CROSSING
;
1568 new_bb
= force_nonfallthru (fall_thru
);
1572 new_bb
->aux
= cur_bb
->aux
;
1573 cur_bb
->aux
= new_bb
;
1575 /* Make sure new fall-through bb is in same
1576 partition as bb it's falling through from. */
1578 BB_COPY_PARTITION (new_bb
, cur_bb
);
1579 single_succ_edge (new_bb
)->flags
|= EDGE_CROSSING
;
1583 /* If a new basic-block was not created; restore
1584 the EDGE_CROSSING flag. */
1585 fall_thru
->flags
|= EDGE_CROSSING
;
1588 /* Add barrier after new jump */
1589 emit_barrier_after_bb (new_bb
? new_bb
: cur_bb
);
1596 /* This function checks the destination block of a "crossing jump" to
1597 see if it has any crossing predecessors that begin with a code label
1598 and end with an unconditional jump. If so, it returns that predecessor
1599 block. (This is to avoid creating lots of new basic blocks that all
1600 contain unconditional jumps to the same destination). */
1603 find_jump_block (basic_block jump_dest
)
1605 basic_block source_bb
= NULL
;
1610 FOR_EACH_EDGE (e
, ei
, jump_dest
->preds
)
1611 if (e
->flags
& EDGE_CROSSING
)
1613 basic_block src
= e
->src
;
1615 /* Check each predecessor to see if it has a label, and contains
1616 only one executable instruction, which is an unconditional jump.
1617 If so, we can use it. */
1619 if (LABEL_P (BB_HEAD (src
)))
1620 for (insn
= BB_HEAD (src
);
1621 !INSN_P (insn
) && insn
!= NEXT_INSN (BB_END (src
));
1622 insn
= NEXT_INSN (insn
))
1625 && insn
== BB_END (src
)
1627 && !any_condjump_p (insn
))
1641 /* Find all BB's with conditional jumps that are crossing edges;
1642 insert a new bb and make the conditional jump branch to the new
1643 bb instead (make the new bb same color so conditional branch won't
1644 be a 'crossing' edge). Insert an unconditional jump from the
1645 new bb to the original destination of the conditional jump. */
1648 fix_crossing_conditional_branches (void)
1659 rtx old_label
= NULL_RTX
;
1662 FOR_EACH_BB (cur_bb
)
1664 crossing_edge
= NULL
;
1665 if (EDGE_COUNT (cur_bb
->succs
) > 0)
1666 succ1
= EDGE_SUCC (cur_bb
, 0);
1670 if (EDGE_COUNT (cur_bb
->succs
) > 1)
1671 succ2
= EDGE_SUCC (cur_bb
, 1);
1675 /* We already took care of fall-through edges, so only one successor
1676 can be a crossing edge. */
1678 if (succ1
&& (succ1
->flags
& EDGE_CROSSING
))
1679 crossing_edge
= succ1
;
1680 else if (succ2
&& (succ2
->flags
& EDGE_CROSSING
))
1681 crossing_edge
= succ2
;
1685 old_jump
= BB_END (cur_bb
);
1687 /* Check to make sure the jump instruction is a
1688 conditional jump. */
1692 if (any_condjump_p (old_jump
))
1694 if (GET_CODE (PATTERN (old_jump
)) == SET
)
1695 set_src
= SET_SRC (PATTERN (old_jump
));
1696 else if (GET_CODE (PATTERN (old_jump
)) == PARALLEL
)
1698 set_src
= XVECEXP (PATTERN (old_jump
), 0,0);
1699 if (GET_CODE (set_src
) == SET
)
1700 set_src
= SET_SRC (set_src
);
1706 if (set_src
&& (GET_CODE (set_src
) == IF_THEN_ELSE
))
1708 if (GET_CODE (XEXP (set_src
, 1)) == PC
)
1709 old_label
= XEXP (set_src
, 2);
1710 else if (GET_CODE (XEXP (set_src
, 2)) == PC
)
1711 old_label
= XEXP (set_src
, 1);
1713 /* Check to see if new bb for jumping to that dest has
1714 already been created; if so, use it; if not, create
1717 new_bb
= find_jump_block (crossing_edge
->dest
);
1720 new_label
= block_label (new_bb
);
1723 basic_block last_bb
;
1726 /* Create new basic block to be dest for
1727 conditional jump. */
1729 /* Put appropriate instructions in new bb. */
1731 new_label
= gen_label_rtx ();
1732 emit_label (new_label
);
1734 gcc_assert (GET_CODE (old_label
) == LABEL_REF
);
1735 old_label
= JUMP_LABEL (old_jump
);
1736 new_jump
= emit_jump_insn (gen_jump (old_label
));
1737 JUMP_LABEL (new_jump
) = old_label
;
1739 last_bb
= EXIT_BLOCK_PTR
->prev_bb
;
1740 new_bb
= create_basic_block (new_label
, new_jump
, last_bb
);
1741 new_bb
->aux
= last_bb
->aux
;
1742 last_bb
->aux
= new_bb
;
1744 emit_barrier_after_bb (new_bb
);
1746 /* Make sure new bb is in same partition as source
1747 of conditional branch. */
1748 BB_COPY_PARTITION (new_bb
, cur_bb
);
1751 /* Make old jump branch to new bb. */
1753 redirect_jump (old_jump
, new_label
, 0);
1755 /* Remove crossing_edge as predecessor of 'dest'. */
1757 dest
= crossing_edge
->dest
;
1759 redirect_edge_succ (crossing_edge
, new_bb
);
1761 /* Make a new edge from new_bb to old dest; new edge
1762 will be a successor for new_bb and a predecessor
1765 if (EDGE_COUNT (new_bb
->succs
) == 0)
1766 new_edge
= make_edge (new_bb
, dest
, 0);
1768 new_edge
= EDGE_SUCC (new_bb
, 0);
1770 crossing_edge
->flags
&= ~EDGE_CROSSING
;
1771 new_edge
->flags
|= EDGE_CROSSING
;
1777 /* Find any unconditional branches that cross between hot and cold
1778 sections. Convert them into indirect jumps instead. */
1781 fix_crossing_unconditional_branches (void)
1787 rtx indirect_jump_sequence
;
1788 rtx jump_insn
= NULL_RTX
;
1793 FOR_EACH_BB (cur_bb
)
1795 last_insn
= BB_END (cur_bb
);
1797 if (EDGE_COUNT (cur_bb
->succs
) < 1)
1800 succ
= EDGE_SUCC (cur_bb
, 0);
1802 /* Check to see if bb ends in a crossing (unconditional) jump. At
1803 this point, no crossing jumps should be conditional. */
1805 if (JUMP_P (last_insn
)
1806 && (succ
->flags
& EDGE_CROSSING
))
1810 gcc_assert (!any_condjump_p (last_insn
));
1812 /* Make sure the jump is not already an indirect or table jump. */
1814 if (!computed_jump_p (last_insn
)
1815 && !tablejump_p (last_insn
, &label2
, &table
))
1817 /* We have found a "crossing" unconditional branch. Now
1818 we must convert it to an indirect jump. First create
1819 reference of label, as target for jump. */
1821 label
= JUMP_LABEL (last_insn
);
1822 label_addr
= gen_rtx_LABEL_REF (Pmode
, label
);
1823 LABEL_NUSES (label
) += 1;
1825 /* Get a register to use for the indirect jump. */
1827 new_reg
= gen_reg_rtx (Pmode
);
1829 /* Generate indirect the jump sequence. */
1832 emit_move_insn (new_reg
, label_addr
);
1833 emit_indirect_jump (new_reg
);
1834 indirect_jump_sequence
= get_insns ();
1837 /* Make sure every instruction in the new jump sequence has
1838 its basic block set to be cur_bb. */
1840 for (cur_insn
= indirect_jump_sequence
; cur_insn
;
1841 cur_insn
= NEXT_INSN (cur_insn
))
1843 if (!BARRIER_P (cur_insn
))
1844 BLOCK_FOR_INSN (cur_insn
) = cur_bb
;
1845 if (JUMP_P (cur_insn
))
1846 jump_insn
= cur_insn
;
1849 /* Insert the new (indirect) jump sequence immediately before
1850 the unconditional jump, then delete the unconditional jump. */
1852 emit_insn_before (indirect_jump_sequence
, last_insn
);
1853 delete_insn (last_insn
);
1855 /* Make BB_END for cur_bb be the jump instruction (NOT the
1856 barrier instruction at the end of the sequence...). */
1858 BB_END (cur_bb
) = jump_insn
;
1864 /* Add REG_CROSSING_JUMP note to all crossing jump insns. */
1867 add_reg_crossing_jump_notes (void)
1874 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1875 if ((e
->flags
& EDGE_CROSSING
)
1876 && JUMP_P (BB_END (e
->src
)))
1877 add_reg_note (BB_END (e
->src
), REG_CROSSING_JUMP
, NULL_RTX
);
1880 /* Verify, in the basic block chain, that there is at most one switch
1881 between hot/cold partitions. This is modelled on
1882 rtl_verify_flow_info_1, but it cannot go inside that function
1883 because this condition will not be true until after
1884 reorder_basic_blocks is called. */
1887 verify_hot_cold_block_grouping (void)
1891 bool switched_sections
= false;
1892 int current_partition
= 0;
1896 if (!current_partition
)
1897 current_partition
= BB_PARTITION (bb
);
1898 if (BB_PARTITION (bb
) != current_partition
)
1900 if (switched_sections
)
1902 error ("multiple hot/cold transitions found (bb %i)",
1908 switched_sections
= true;
1909 current_partition
= BB_PARTITION (bb
);
1917 /* Reorder basic blocks. The main entry point to this file. FLAGS is
1918 the set of flags to pass to cfg_layout_initialize(). */
1921 reorder_basic_blocks (void)
1925 struct trace
*traces
;
1927 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT
);
1929 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
1932 set_edge_can_fallthru_flag ();
1933 mark_dfs_back_edges ();
1935 /* We are estimating the length of uncond jump insn only once since the code
1936 for getting the insn length always returns the minimal length now. */
1937 if (uncond_jump_length
== 0)
1938 uncond_jump_length
= get_uncond_jump_length ();
1940 /* We need to know some information for each basic block. */
1941 array_size
= GET_ARRAY_SIZE (last_basic_block
);
1942 bbd
= XNEWVEC (bbro_basic_block_data
, array_size
);
1943 for (i
= 0; i
< array_size
; i
++)
1945 bbd
[i
].start_of_trace
= -1;
1946 bbd
[i
].end_of_trace
= -1;
1947 bbd
[i
].in_trace
= -1;
1953 traces
= XNEWVEC (struct trace
, n_basic_blocks
);
1955 find_traces (&n_traces
, traces
);
1956 connect_traces (n_traces
, traces
);
1960 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
1963 dump_flow_info (dump_file
, dump_flags
);
1965 if (flag_reorder_blocks_and_partition
)
1966 verify_hot_cold_block_grouping ();
1969 /* Determine which partition the first basic block in the function
1970 belongs to, then find the first basic block in the current function
1971 that belongs to a different section, and insert a
1972 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
1973 instruction stream. When writing out the assembly code,
1974 encountering this note will make the compiler switch between the
1975 hot and cold text sections. */
1978 insert_section_boundary_note (void)
1982 int first_partition
= 0;
1984 if (!flag_reorder_blocks_and_partition
)
1989 if (!first_partition
)
1990 first_partition
= BB_PARTITION (bb
);
1991 if (BB_PARTITION (bb
) != first_partition
)
1993 new_note
= emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS
,
1995 /* ??? This kind of note always lives between basic blocks,
1996 but add_insn_before will set BLOCK_FOR_INSN anyway. */
1997 BLOCK_FOR_INSN (new_note
) = NULL
;
2003 /* Duplicate the blocks containing computed gotos. This basically unfactors
2004 computed gotos that were factored early on in the compilation process to
2005 speed up edge based data flow. We used to not unfactoring them again,
2006 which can seriously pessimize code with many computed jumps in the source
2007 code, such as interpreters. See e.g. PR15242. */
2010 gate_duplicate_computed_gotos (void)
2012 if (targetm
.cannot_modify_jumps_p ())
2014 return (optimize
> 0
2015 && flag_expensive_optimizations
2016 && ! optimize_function_for_size_p (cfun
));
2021 duplicate_computed_gotos (void)
2023 basic_block bb
, new_bb
;
2027 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
2031 cfg_layout_initialize (0);
2033 /* We are estimating the length of uncond jump insn only once
2034 since the code for getting the insn length always returns
2035 the minimal length now. */
2036 if (uncond_jump_length
== 0)
2037 uncond_jump_length
= get_uncond_jump_length ();
2039 max_size
= uncond_jump_length
* PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS
);
2040 candidates
= BITMAP_ALLOC (NULL
);
2042 /* Look for blocks that end in a computed jump, and see if such blocks
2043 are suitable for unfactoring. If a block is a candidate for unfactoring,
2044 mark it in the candidates. */
2050 int size
, all_flags
;
2052 /* Build the reorder chain for the original order of blocks. */
2053 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2054 bb
->aux
= bb
->next_bb
;
2056 /* Obviously the block has to end in a computed jump. */
2057 if (!computed_jump_p (BB_END (bb
)))
2060 /* Only consider blocks that can be duplicated. */
2061 if (find_reg_note (BB_END (bb
), REG_CROSSING_JUMP
, NULL_RTX
)
2062 || !can_duplicate_block_p (bb
))
2065 /* Make sure that the block is small enough. */
2067 FOR_BB_INSNS (bb
, insn
)
2070 size
+= get_attr_min_length (insn
);
2071 if (size
> max_size
)
2074 if (size
> max_size
)
2077 /* Final check: there must not be any incoming abnormal edges. */
2079 FOR_EACH_EDGE (e
, ei
, bb
->preds
)
2080 all_flags
|= e
->flags
;
2081 if (all_flags
& EDGE_COMPLEX
)
2084 bitmap_set_bit (candidates
, bb
->index
);
2087 /* Nothing to do if there is no computed jump here. */
2088 if (bitmap_empty_p (candidates
))
2091 /* Duplicate computed gotos. */
2094 if (bb
->flags
& BB_VISITED
)
2097 bb
->flags
|= BB_VISITED
;
2099 /* BB must have one outgoing edge. That edge must not lead to
2100 the exit block or the next block.
2101 The destination must have more than one predecessor. */
2102 if (!single_succ_p (bb
)
2103 || single_succ (bb
) == EXIT_BLOCK_PTR
2104 || single_succ (bb
) == bb
->next_bb
2105 || single_pred_p (single_succ (bb
)))
2108 /* The successor block has to be a duplication candidate. */
2109 if (!bitmap_bit_p (candidates
, single_succ (bb
)->index
))
2112 new_bb
= duplicate_block (single_succ (bb
), single_succ_edge (bb
), bb
);
2113 new_bb
->aux
= bb
->aux
;
2115 new_bb
->flags
|= BB_VISITED
;
2119 cfg_layout_finalize ();
2121 BITMAP_FREE (candidates
);
2125 struct rtl_opt_pass pass_duplicate_computed_gotos
=
2129 "compgotos", /* name */
2130 gate_duplicate_computed_gotos
, /* gate */
2131 duplicate_computed_gotos
, /* execute */
2134 0, /* static_pass_number */
2135 TV_REORDER_BLOCKS
, /* tv_id */
2136 0, /* properties_required */
2137 0, /* properties_provided */
2138 0, /* properties_destroyed */
2139 0, /* todo_flags_start */
2140 TODO_verify_rtl_sharing
,/* todo_flags_finish */
2145 /* This function is the main 'entrance' for the optimization that
2146 partitions hot and cold basic blocks into separate sections of the
2147 .o file (to improve performance and cache locality). Ideally it
2148 would be called after all optimizations that rearrange the CFG have
2149 been called. However part of this optimization may introduce new
2150 register usage, so it must be called before register allocation has
2151 occurred. This means that this optimization is actually called
2152 well before the optimization that reorders basic blocks (see
2155 This optimization checks the feedback information to determine
2156 which basic blocks are hot/cold, updates flags on the basic blocks
2157 to indicate which section they belong in. This information is
2158 later used for writing out sections in the .o file. Because hot
2159 and cold sections can be arbitrarily large (within the bounds of
2160 memory), far beyond the size of a single function, it is necessary
2161 to fix up all edges that cross section boundaries, to make sure the
2162 instructions used can actually span the required distance. The
2163 fixes are described below.
2165 Fall-through edges must be changed into jumps; it is not safe or
2166 legal to fall through across a section boundary. Whenever a
2167 fall-through edge crossing a section boundary is encountered, a new
2168 basic block is inserted (in the same section as the fall-through
2169 source), and the fall through edge is redirected to the new basic
2170 block. The new basic block contains an unconditional jump to the
2171 original fall-through target. (If the unconditional jump is
2172 insufficient to cross section boundaries, that is dealt with a
2173 little later, see below).
2175 In order to deal with architectures that have short conditional
2176 branches (which cannot span all of memory) we take any conditional
2177 jump that attempts to cross a section boundary and add a level of
2178 indirection: it becomes a conditional jump to a new basic block, in
2179 the same section. The new basic block contains an unconditional
2180 jump to the original target, in the other section.
2182 For those architectures whose unconditional branch is also
2183 incapable of reaching all of memory, those unconditional jumps are
2184 converted into indirect jumps, through a register.
2186 IMPORTANT NOTE: This optimization causes some messy interactions
2187 with the cfg cleanup optimizations; those optimizations want to
2188 merge blocks wherever possible, and to collapse indirect jump
2189 sequences (change "A jumps to B jumps to C" directly into "A jumps
2190 to C"). Those optimizations can undo the jump fixes that
2191 partitioning is required to make (see above), in order to ensure
2192 that jumps attempting to cross section boundaries are really able
2193 to cover whatever distance the jump requires (on many architectures
2194 conditional or unconditional jumps are not able to reach all of
2195 memory). Therefore tests have to be inserted into each such
2196 optimization to make sure that it does not undo stuff necessary to
2197 cross partition boundaries. This would be much less of a problem
2198 if we could perform this optimization later in the compilation, but
2199 unfortunately the fact that we may need to create indirect jumps
2200 (through registers) requires that this optimization be performed
2201 before register allocation.
2203 Hot and cold basic blocks are partitioned and put in separate
2204 sections of the .o file, to reduce paging and improve cache
2205 performance (hopefully). This can result in bits of code from the
2206 same function being widely separated in the .o file. However this
2207 is not obvious to the current bb structure. Therefore we must take
2208 care to ensure that: 1). There are no fall_thru edges that cross
2209 between sections; 2). For those architectures which have "short"
2210 conditional branches, all conditional branches that attempt to
2211 cross between sections are converted to unconditional branches;
2212 and, 3). For those architectures which have "short" unconditional
2213 branches, all unconditional branches that attempt to cross between
2214 sections are converted to indirect jumps.
2216 The code for fixing up fall_thru edges that cross between hot and
2217 cold basic blocks does so by creating new basic blocks containing
2218 unconditional branches to the appropriate label in the "other"
2219 section. The new basic block is then put in the same (hot or cold)
2220 section as the original conditional branch, and the fall_thru edge
2221 is modified to fall into the new basic block instead. By adding
2222 this level of indirection we end up with only unconditional branches
2223 crossing between hot and cold sections.
2225 Conditional branches are dealt with by adding a level of indirection.
2226 A new basic block is added in the same (hot/cold) section as the
2227 conditional branch, and the conditional branch is retargeted to the
2228 new basic block. The new basic block contains an unconditional branch
2229 to the original target of the conditional branch (in the other section).
2231 Unconditional branches are dealt with by converting them into
2235 partition_hot_cold_basic_blocks (void)
2237 VEC(edge
, heap
) *crossing_edges
;
2239 if (n_basic_blocks
<= NUM_FIXED_BLOCKS
+ 1)
2242 df_set_flags (DF_DEFER_INSN_RESCAN
);
2244 crossing_edges
= find_rarely_executed_basic_blocks_and_crossing_edges ();
2245 if (crossing_edges
== NULL
)
2248 /* Make sure the source of any crossing edge ends in a jump and the
2249 destination of any crossing edge has a label. */
2250 add_labels_and_missing_jumps (crossing_edges
);
2252 /* Convert all crossing fall_thru edges to non-crossing fall
2253 thrus to unconditional jumps (that jump to the original fall
2255 fix_up_fall_thru_edges ();
2257 /* If the architecture does not have conditional branches that can
2258 span all of memory, convert crossing conditional branches into
2259 crossing unconditional branches. */
2260 if (!HAS_LONG_COND_BRANCH
)
2261 fix_crossing_conditional_branches ();
2263 /* If the architecture does not have unconditional branches that
2264 can span all of memory, convert crossing unconditional branches
2265 into indirect jumps. Since adding an indirect jump also adds
2266 a new register usage, update the register usage information as
2268 if (!HAS_LONG_UNCOND_BRANCH
)
2269 fix_crossing_unconditional_branches ();
2271 add_reg_crossing_jump_notes ();
2273 /* Clear bb->aux fields that the above routines were using. */
2274 clear_aux_for_blocks ();
2276 VEC_free (edge
, heap
, crossing_edges
);
2278 /* ??? FIXME: DF generates the bb info for a block immediately.
2279 And by immediately, I mean *during* creation of the block.
2281 #0 df_bb_refs_collect
2282 #1 in df_bb_refs_record
2283 #2 in create_basic_block_structure
2285 Which means that the bb_has_eh_pred test in df_bb_refs_collect
2286 will *always* fail, because no edges can have been added to the
2287 block yet. Which of course means we don't add the right
2288 artificial refs, which means we fail df_verify (much) later.
2290 Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
2291 that we also shouldn't grab data from the new blocks those new
2292 insns are in either. In this way one can create the block, link
2293 it up properly, and have everything Just Work later, when deferred
2294 insns are processed.
2296 In the meantime, we have no other option but to throw away all
2297 of the DF data and recompute it all. */
2298 if (cfun
->eh
->lp_array
)
2300 df_finish_pass (true);
2301 df_scan_alloc (NULL
);
2303 /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
2304 data. We blindly generated all of them when creating the new
2305 landing pad. Delete those assignments we don't use. */
2306 df_set_flags (DF_LR_RUN_DCE
);
2310 return TODO_verify_flow
| TODO_verify_rtl_sharing
;
2314 gate_handle_reorder_blocks (void)
2316 if (targetm
.cannot_modify_jumps_p ())
2318 /* Don't reorder blocks when optimizing for size because extra jump insns may
2319 be created; also barrier may create extra padding.
2321 More correctly we should have a block reordering mode that tried to
2322 minimize the combined size of all the jumps. This would more or less
2323 automatically remove extra jumps, but would also try to use more short
2324 jumps instead of long jumps. */
2325 if (!optimize_function_for_speed_p (cfun
))
2327 return (optimize
> 0
2328 && (flag_reorder_blocks
|| flag_reorder_blocks_and_partition
));
2332 /* Reorder basic blocks. */
2334 rest_of_handle_reorder_blocks (void)
2338 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2339 splitting possibly introduced more crossjumping opportunities. */
2340 cfg_layout_initialize (CLEANUP_EXPENSIVE
);
2342 reorder_basic_blocks ();
2343 cleanup_cfg (CLEANUP_EXPENSIVE
);
2346 if (bb
->next_bb
!= EXIT_BLOCK_PTR
)
2347 bb
->aux
= bb
->next_bb
;
2348 cfg_layout_finalize ();
2350 /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */
2351 insert_section_boundary_note ();
2355 struct rtl_opt_pass pass_reorder_blocks
=
2360 gate_handle_reorder_blocks
, /* gate */
2361 rest_of_handle_reorder_blocks
, /* execute */
2364 0, /* static_pass_number */
2365 TV_REORDER_BLOCKS
, /* tv_id */
2366 0, /* properties_required */
2367 0, /* properties_provided */
2368 0, /* properties_destroyed */
2369 0, /* todo_flags_start */
2370 TODO_verify_rtl_sharing
, /* todo_flags_finish */
2375 gate_handle_partition_blocks (void)
2377 /* The optimization to partition hot/cold basic blocks into separate
2378 sections of the .o file does not work well with linkonce or with
2379 user defined section attributes. Don't call it if either case
2381 return (flag_reorder_blocks_and_partition
2383 /* See gate_handle_reorder_blocks. We should not partition if
2384 we are going to omit the reordering. */
2385 && optimize_function_for_speed_p (cfun
)
2386 && !DECL_ONE_ONLY (current_function_decl
)
2387 && !user_defined_section_attribute
);
2390 struct rtl_opt_pass pass_partition_blocks
=
2394 "bbpart", /* name */
2395 gate_handle_partition_blocks
, /* gate */
2396 partition_hot_cold_basic_blocks
, /* execute */
2399 0, /* static_pass_number */
2400 TV_REORDER_BLOCKS
, /* tv_id */
2401 PROP_cfglayout
, /* properties_required */
2402 0, /* properties_provided */
2403 0, /* properties_destroyed */
2404 0, /* todo_flags_start */
2405 0 /* todo_flags_finish */