1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2002, 2003 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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"
73 #include "basic-block.h"
76 #include "cfglayout.h"
80 /* The number of rounds. */
83 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
84 static int branch_threshold
[N_ROUNDS
] = {400, 200, 100, 0};
86 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
87 static int exec_threshold
[N_ROUNDS
] = {500, 200, 50, 0};
89 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
90 block the edge destination is not duplicated while connecting traces. */
91 #define DUPLICATION_THRESHOLD 100
93 /* Length of unconditional jump instruction. */
94 static int uncond_jump_length
;
96 /* Structure to hold needed information for each basic block. */
97 typedef struct bbro_basic_block_data_def
99 /* Which trace is the bb start of (-1 means it is not a start of a trace). */
102 /* Which trace is the bb end of (-1 means it is not an end of a trace). */
105 /* Which heap is BB in (if any)? */
108 /* Which heap node is BB in (if any)? */
110 } bbro_basic_block_data
;
112 /* The current size of the following dynamic array. */
113 static int array_size
;
115 /* The array which holds needed information for basic blocks. */
116 static bbro_basic_block_data
*bbd
;
118 /* To avoid frequent reallocation the size of arrays is greater than needed,
119 the number of elements is (not less than) 1.25 * size_wanted. */
120 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
122 /* Free the memory and set the pointer to NULL. */
124 do { if (P) { free (P); P = 0; } else { abort (); } } while (0)
126 /* Structure for holding information about a trace. */
129 /* First and last basic block of the trace. */
130 basic_block first
, last
;
132 /* The round of the STC creation which this trace was found in. */
135 /* The length (i.e. the number of basic blocks) of the trace. */
139 /* Maximum frequency and count of one of the entry blocks. */
140 int max_entry_frequency
;
141 gcov_type max_entry_count
;
143 /* Local function prototypes. */
144 static void find_traces (int *, struct trace
*);
145 static basic_block
rotate_loop (edge
, struct trace
*, int);
146 static void mark_bb_visited (basic_block
, int);
147 static void find_traces_1_round (int, int, gcov_type
, struct trace
*, int *,
149 static basic_block
copy_bb (basic_block
, edge
, basic_block
, int);
150 static fibheapkey_t
bb_to_key (basic_block
);
151 static bool better_edge_p (basic_block
, edge
, int, int, int, int);
152 static void connect_traces (int, struct trace
*);
153 static bool copy_bb_p (basic_block
, int);
154 static int get_uncond_jump_length (void);
156 /* Find the traces for Software Trace Cache. Chain each trace through
157 RBI()->next. Store the number of traces to N_TRACES and description of
161 find_traces (int *n_traces
, struct trace
*traces
)
167 /* Insert entry points of function into heap. */
168 heap
= fibheap_new ();
169 max_entry_frequency
= 0;
171 for (e
= ENTRY_BLOCK_PTR
->succ
; e
; e
= e
->succ_next
)
173 bbd
[e
->dest
->index
].heap
= heap
;
174 bbd
[e
->dest
->index
].node
= fibheap_insert (heap
, bb_to_key (e
->dest
),
176 if (e
->dest
->frequency
> max_entry_frequency
)
177 max_entry_frequency
= e
->dest
->frequency
;
178 if (e
->dest
->count
> max_entry_count
)
179 max_entry_count
= e
->dest
->count
;
182 /* Find the traces. */
183 for (i
= 0; i
< N_ROUNDS
; i
++)
185 gcov_type count_threshold
;
188 fprintf (rtl_dump_file
, "STC - round %d\n", i
+ 1);
190 if (max_entry_count
< INT_MAX
/ 1000)
191 count_threshold
= max_entry_count
* exec_threshold
[i
] / 1000;
193 count_threshold
= max_entry_count
/ 1000 * exec_threshold
[i
];
195 find_traces_1_round (REG_BR_PROB_BASE
* branch_threshold
[i
] / 1000,
196 max_entry_frequency
* exec_threshold
[i
] / 1000,
197 count_threshold
, traces
, n_traces
, i
, &heap
);
199 fibheap_delete (heap
);
203 for (i
= 0; i
< *n_traces
; i
++)
206 fprintf (rtl_dump_file
, "Trace %d (round %d): ", i
+ 1,
207 traces
[i
].round
+ 1);
208 for (bb
= traces
[i
].first
; bb
!= traces
[i
].last
; bb
= RBI (bb
)->next
)
209 fprintf (rtl_dump_file
, "%d [%d] ", bb
->index
, bb
->frequency
);
210 fprintf (rtl_dump_file
, "%d [%d]\n", bb
->index
, bb
->frequency
);
212 fflush (rtl_dump_file
);
216 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
217 (with sequential number TRACE_N). */
220 rotate_loop (edge back_edge
, struct trace
*trace
, int trace_n
)
224 /* Information about the best end (end after rotation) of the loop. */
225 basic_block best_bb
= NULL
;
226 edge best_edge
= NULL
;
228 gcov_type best_count
= -1;
229 /* The best edge is preferred when its destination is not visited yet
230 or is a start block of some trace. */
231 bool is_preferred
= false;
233 /* Find the most frequent edge that goes out from current trace. */
234 bb
= back_edge
->dest
;
238 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
239 if (e
->dest
!= EXIT_BLOCK_PTR
240 && RBI (e
->dest
)->visited
!= trace_n
241 && (e
->flags
& EDGE_CAN_FALLTHRU
)
242 && !(e
->flags
& EDGE_COMPLEX
))
246 /* The best edge is preferred. */
247 if (!RBI (e
->dest
)->visited
248 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
250 /* The current edge E is also preferred. */
251 int freq
= EDGE_FREQUENCY (e
);
252 if (freq
> best_freq
|| e
->count
> best_count
)
255 best_count
= e
->count
;
263 if (!RBI (e
->dest
)->visited
264 || bbd
[e
->dest
->index
].start_of_trace
>= 0)
266 /* The current edge E is preferred. */
268 best_freq
= EDGE_FREQUENCY (e
);
269 best_count
= e
->count
;
275 int freq
= EDGE_FREQUENCY (e
);
276 if (!best_edge
|| freq
> best_freq
|| e
->count
> best_count
)
279 best_count
= e
->count
;
288 while (bb
!= back_edge
->dest
);
292 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
294 if (back_edge
->dest
== trace
->first
)
296 trace
->first
= RBI (best_bb
)->next
;
302 for (prev_bb
= trace
->first
;
303 RBI (prev_bb
)->next
!= back_edge
->dest
;
304 prev_bb
= RBI (prev_bb
)->next
)
306 RBI (prev_bb
)->next
= RBI (best_bb
)->next
;
308 /* Try to get rid of uncond jump to cond jump. */
309 if (prev_bb
->succ
&& !prev_bb
->succ
->succ_next
)
311 basic_block header
= prev_bb
->succ
->dest
;
313 /* Duplicate HEADER if it is a small block containing cond jump
315 if (any_condjump_p (header
->end
) && copy_bb_p (header
, 0))
317 copy_bb (header
, prev_bb
->succ
, prev_bb
, trace_n
);
324 /* We have not found suitable loop tail so do no rotation. */
325 best_bb
= back_edge
->src
;
327 RBI (best_bb
)->next
= NULL
;
331 /* This function marks BB that it was visited in trace number TRACE. */
334 mark_bb_visited (basic_block bb
, int trace
)
336 RBI (bb
)->visited
= trace
;
337 if (bbd
[bb
->index
].heap
)
339 fibheap_delete_node (bbd
[bb
->index
].heap
, bbd
[bb
->index
].node
);
340 bbd
[bb
->index
].heap
= NULL
;
341 bbd
[bb
->index
].node
= NULL
;
345 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
346 not include basic blocks their probability is lower than BRANCH_TH or their
347 frequency is lower than EXEC_TH into traces (or count is lower than
348 COUNT_TH). It stores the new traces into TRACES and modifies the number of
349 traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
350 expects that starting basic blocks are in *HEAP and at the end it deletes
351 *HEAP and stores starting points for the next round into new *HEAP. */
354 find_traces_1_round (int branch_th
, int exec_th
, gcov_type count_th
,
355 struct trace
*traces
, int *n_traces
, int round
,
358 /* Heap for discarded basic blocks which are possible starting points for
360 fibheap_t new_heap
= fibheap_new ();
362 while (!fibheap_empty (*heap
))
369 bb
= fibheap_extract_min (*heap
);
370 bbd
[bb
->index
].heap
= NULL
;
371 bbd
[bb
->index
].node
= NULL
;
374 fprintf (rtl_dump_file
, "Getting bb %d\n", bb
->index
);
376 /* If the BB's frequency is too low send BB to the next round. */
377 if (bb
->frequency
< exec_th
|| bb
->count
< count_th
378 || ((round
< N_ROUNDS
- 1) && probably_never_executed_bb_p (bb
)))
380 int key
= bb_to_key (bb
);
381 bbd
[bb
->index
].heap
= new_heap
;
382 bbd
[bb
->index
].node
= fibheap_insert (new_heap
, key
, bb
);
385 fprintf (rtl_dump_file
,
386 " Possible start point of next round: %d (key: %d)\n",
391 trace
= traces
+ *n_traces
;
393 trace
->round
= round
;
401 /* The probability and frequency of the best edge. */
402 int best_prob
= INT_MIN
/ 2;
403 int best_freq
= INT_MIN
/ 2;
406 mark_bb_visited (bb
, *n_traces
);
410 fprintf (rtl_dump_file
, "Basic block %d was visited in trace %d\n",
411 bb
->index
, *n_traces
- 1);
413 /* Select the successor that will be placed after BB. */
414 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
416 if (e
->flags
& EDGE_FAKE
)
419 if (e
->dest
== EXIT_BLOCK_PTR
)
422 if (RBI (e
->dest
)->visited
423 && RBI (e
->dest
)->visited
!= *n_traces
)
426 prob
= e
->probability
;
427 freq
= EDGE_FREQUENCY (e
);
429 /* Edge that cannot be fallthru or improbable or infrequent
430 successor (ie. it is unsuitable successor). */
431 if (!(e
->flags
& EDGE_CAN_FALLTHRU
) || (e
->flags
& EDGE_COMPLEX
)
432 || prob
< branch_th
|| freq
< exec_th
|| e
->count
< count_th
)
435 if (better_edge_p (bb
, e
, prob
, freq
, best_prob
, best_freq
))
443 /* If the best destination has multiple predecessors, and can be
444 duplicated cheaper than a jump, don't allow it to be added
445 to a trace. We'll duplicate it when connecting traces. */
446 if (best_edge
&& best_edge
->dest
->pred
->pred_next
447 && copy_bb_p (best_edge
->dest
, 0))
450 /* Add all non-selected successors to the heaps. */
451 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
454 || e
->dest
== EXIT_BLOCK_PTR
455 || RBI (e
->dest
)->visited
)
458 key
= bb_to_key (e
->dest
);
460 if (bbd
[e
->dest
->index
].heap
)
462 /* E->DEST is already in some heap. */
463 if (key
!= bbd
[e
->dest
->index
].node
->key
)
467 fprintf (rtl_dump_file
,
468 "Changing key for bb %d from %ld to %ld.\n",
470 (long) bbd
[e
->dest
->index
].node
->key
,
473 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
474 bbd
[e
->dest
->index
].node
, key
);
479 fibheap_t which_heap
= *heap
;
481 prob
= e
->probability
;
482 freq
= EDGE_FREQUENCY (e
);
484 if (!(e
->flags
& EDGE_CAN_FALLTHRU
)
485 || (e
->flags
& EDGE_COMPLEX
)
486 || prob
< branch_th
|| freq
< exec_th
487 || e
->count
< count_th
)
489 if (round
< N_ROUNDS
- 1)
490 which_heap
= new_heap
;
493 bbd
[e
->dest
->index
].heap
= which_heap
;
494 bbd
[e
->dest
->index
].node
= fibheap_insert (which_heap
,
499 fprintf (rtl_dump_file
,
500 " Possible start of %s round: %d (key: %ld)\n",
501 (which_heap
== new_heap
) ? "next" : "this",
502 e
->dest
->index
, (long) key
);
508 if (best_edge
) /* Suitable successor was found. */
510 if (RBI (best_edge
->dest
)->visited
== *n_traces
)
512 /* We do nothing with one basic block loops. */
513 if (best_edge
->dest
!= bb
)
515 if (EDGE_FREQUENCY (best_edge
)
516 > 4 * best_edge
->dest
->frequency
/ 5)
518 /* The loop has at least 4 iterations. If the loop
519 header is not the first block of the function
520 we can rotate the loop. */
522 if (best_edge
->dest
!= ENTRY_BLOCK_PTR
->next_bb
)
526 fprintf (rtl_dump_file
,
527 "Rotating loop %d - %d\n",
528 best_edge
->dest
->index
, bb
->index
);
530 RBI (bb
)->next
= best_edge
->dest
;
531 bb
= rotate_loop (best_edge
, trace
, *n_traces
);
536 /* The loop has less than 4 iterations. */
538 /* Check whether there is another edge from BB. */
540 for (another_edge
= bb
->succ
;
542 another_edge
= another_edge
->succ_next
)
543 if (another_edge
!= best_edge
)
546 if (!another_edge
&& copy_bb_p (best_edge
->dest
,
549 bb
= copy_bb (best_edge
->dest
, best_edge
, bb
,
555 /* Terminate the trace. */
560 /* Check for a situation
569 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
570 >= EDGE_FREQUENCY (AC).
571 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
572 Best ordering is then A B C.
574 This situation is created for example by:
581 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
583 && (e
->flags
& EDGE_CAN_FALLTHRU
)
584 && !(e
->flags
& EDGE_COMPLEX
)
585 && !RBI (e
->dest
)->visited
586 && !e
->dest
->pred
->pred_next
588 && (e
->dest
->succ
->flags
& EDGE_CAN_FALLTHRU
)
589 && !(e
->dest
->succ
->flags
& EDGE_COMPLEX
)
590 && !e
->dest
->succ
->succ_next
591 && e
->dest
->succ
->dest
== best_edge
->dest
592 && 2 * e
->dest
->frequency
>= EDGE_FREQUENCY (best_edge
))
596 fprintf (rtl_dump_file
, "Selecting BB %d\n",
597 best_edge
->dest
->index
);
601 RBI (bb
)->next
= best_edge
->dest
;
602 bb
= best_edge
->dest
;
608 bbd
[trace
->first
->index
].start_of_trace
= *n_traces
- 1;
609 bbd
[trace
->last
->index
].end_of_trace
= *n_traces
- 1;
611 /* The trace is terminated so we have to recount the keys in heap
612 (some block can have a lower key because now one of its predecessors
613 is an end of the trace). */
614 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
616 if (e
->dest
== EXIT_BLOCK_PTR
617 || RBI (e
->dest
)->visited
)
620 if (bbd
[e
->dest
->index
].heap
)
622 key
= bb_to_key (e
->dest
);
623 if (key
!= bbd
[e
->dest
->index
].node
->key
)
627 fprintf (rtl_dump_file
,
628 "Changing key for bb %d from %ld to %ld.\n",
630 (long) bbd
[e
->dest
->index
].node
->key
, key
);
632 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
633 bbd
[e
->dest
->index
].node
,
640 fibheap_delete (*heap
);
642 /* "Return" the new heap. */
646 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
647 it to trace after BB, mark OLD_BB visited and update pass' data structures
648 (TRACE is a number of trace which OLD_BB is duplicated to). */
651 copy_bb (basic_block old_bb
, edge e
, basic_block bb
, int trace
)
655 new_bb
= cfg_layout_duplicate_bb (old_bb
, e
);
656 if (e
->dest
!= new_bb
)
658 if (RBI (e
->dest
)->visited
)
661 fprintf (rtl_dump_file
,
662 "Duplicated bb %d (created bb %d)\n",
663 old_bb
->index
, new_bb
->index
);
664 RBI (new_bb
)->visited
= trace
;
665 RBI (new_bb
)->next
= RBI (bb
)->next
;
666 RBI (bb
)->next
= new_bb
;
668 if (new_bb
->index
>= array_size
|| last_basic_block
> array_size
)
673 new_size
= MAX (last_basic_block
, new_bb
->index
+ 1);
674 new_size
= GET_ARRAY_SIZE (new_size
);
675 bbd
= xrealloc (bbd
, new_size
* sizeof (bbro_basic_block_data
));
676 for (i
= array_size
; i
< new_size
; i
++)
678 bbd
[i
].start_of_trace
= -1;
679 bbd
[i
].end_of_trace
= -1;
683 array_size
= new_size
;
687 fprintf (rtl_dump_file
,
688 "Growing the dynamic array to %d elements.\n",
696 /* Compute and return the key (for the heap) of the basic block BB. */
699 bb_to_key (basic_block bb
)
705 /* Do not start in probably never executed blocks. */
706 if (probably_never_executed_bb_p (bb
))
709 /* Prefer blocks whose predecessor is an end of some trace
710 or whose predecessor edge is EDGE_DFS_BACK. */
711 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
713 if ((e
->src
!= ENTRY_BLOCK_PTR
&& bbd
[e
->src
->index
].end_of_trace
>= 0)
714 || (e
->flags
& EDGE_DFS_BACK
))
716 int edge_freq
= EDGE_FREQUENCY (e
);
718 if (edge_freq
> priority
)
719 priority
= edge_freq
;
724 /* The block with priority should have significantly lower key. */
725 return -(100 * BB_FREQ_MAX
+ 100 * priority
+ bb
->frequency
);
726 return -bb
->frequency
;
729 /* Return true when the edge E from basic block BB is better than the temporary
730 best edge (details are in function). The probability of edge E is PROB. The
731 frequency of the successor is FREQ. The current best probability is
732 BEST_PROB, the best frequency is BEST_FREQ.
733 The edge is considered to be equivalent when PROB does not differ much from
734 BEST_PROB; similarly for frequency. */
737 better_edge_p (basic_block bb
, edge e
, int prob
, int freq
, int best_prob
,
742 /* The BEST_* values do not have to be best, but can be a bit smaller than
744 int diff_prob
= best_prob
/ 10;
745 int diff_freq
= best_freq
/ 10;
747 if (prob
> best_prob
+ diff_prob
)
748 /* The edge has higher probability than the temporary best edge. */
749 is_better_edge
= true;
750 else if (prob
< best_prob
- diff_prob
)
751 /* The edge has lower probability than the temporary best edge. */
752 is_better_edge
= false;
753 else if (freq
< best_freq
- diff_freq
)
754 /* The edge and the temporary best edge have almost equivalent
755 probabilities. The higher frequency of a successor now means
756 that there is another edge going into that successor.
757 This successor has lower frequency so it is better. */
758 is_better_edge
= true;
759 else if (freq
> best_freq
+ diff_freq
)
760 /* This successor has higher frequency so it is worse. */
761 is_better_edge
= false;
762 else if (e
->dest
->prev_bb
== bb
)
763 /* The edges have equivalent probabilities and the successors
764 have equivalent frequencies. Select the previous successor. */
765 is_better_edge
= true;
767 is_better_edge
= false;
769 return is_better_edge
;
772 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
775 connect_traces (int n_traces
, struct trace
*traces
)
781 gcov_type count_threshold
;
783 freq_threshold
= max_entry_frequency
* DUPLICATION_THRESHOLD
/ 1000;
784 if (max_entry_count
< INT_MAX
/ 1000)
785 count_threshold
= max_entry_count
* DUPLICATION_THRESHOLD
/ 1000;
787 count_threshold
= max_entry_count
/ 1000 * DUPLICATION_THRESHOLD
;
789 connected
= xcalloc (n_traces
, sizeof (bool));
791 for (i
= 0; i
< n_traces
; i
++)
803 /* Find the predecessor traces. */
804 for (t2
= t
; t2
> 0;)
808 for (e
= traces
[t2
].first
->pred
; e
; e
= e
->pred_next
)
810 int si
= e
->src
->index
;
812 if (e
->src
!= ENTRY_BLOCK_PTR
813 && (e
->flags
& EDGE_CAN_FALLTHRU
)
814 && !(e
->flags
& EDGE_COMPLEX
)
815 && bbd
[si
].end_of_trace
>= 0
816 && !connected
[bbd
[si
].end_of_trace
]
818 || e
->probability
> best
->probability
819 || (e
->probability
== best
->probability
820 && traces
[bbd
[si
].end_of_trace
].length
> best_len
)))
823 best_len
= traces
[bbd
[si
].end_of_trace
].length
;
828 RBI (best
->src
)->next
= best
->dest
;
829 t2
= bbd
[best
->src
->index
].end_of_trace
;
830 connected
[t2
] = true;
833 fprintf (rtl_dump_file
, "Connection: %d %d\n",
834 best
->src
->index
, best
->dest
->index
);
842 RBI (traces
[last_trace
].last
)->next
= traces
[t2
].first
;
845 /* Find the successor traces. */
848 /* Find the continuation of the chain. */
851 for (e
= traces
[t
].last
->succ
; e
; e
= e
->succ_next
)
853 int di
= e
->dest
->index
;
855 if (e
->dest
!= EXIT_BLOCK_PTR
856 && (e
->flags
& EDGE_CAN_FALLTHRU
)
857 && !(e
->flags
& EDGE_COMPLEX
)
858 && bbd
[di
].start_of_trace
>= 0
859 && !connected
[bbd
[di
].start_of_trace
]
861 || e
->probability
> best
->probability
862 || (e
->probability
== best
->probability
863 && traces
[bbd
[di
].start_of_trace
].length
> best_len
)))
866 best_len
= traces
[bbd
[di
].start_of_trace
].length
;
874 fprintf (rtl_dump_file
, "Connection: %d %d\n",
875 best
->src
->index
, best
->dest
->index
);
877 t
= bbd
[best
->dest
->index
].start_of_trace
;
878 RBI (traces
[last_trace
].last
)->next
= traces
[t
].first
;
884 /* Try to connect the traces by duplication of 1 block. */
886 basic_block next_bb
= NULL
;
887 bool try_copy
= false;
889 for (e
= traces
[t
].last
->succ
; e
; e
= e
->succ_next
)
890 if (e
->dest
!= EXIT_BLOCK_PTR
891 && (e
->flags
& EDGE_CAN_FALLTHRU
)
892 && !(e
->flags
& EDGE_COMPLEX
)
893 && (!best
|| e
->probability
> best
->probability
))
898 /* If the destination is a start of a trace which is only
899 one block long, then no need to search the successor
900 blocks of the trace. Accept it. */
901 if (bbd
[e
->dest
->index
].start_of_trace
>= 0
902 && traces
[bbd
[e
->dest
->index
].start_of_trace
].length
910 for (e2
= e
->dest
->succ
; e2
; e2
= e2
->succ_next
)
912 int di
= e2
->dest
->index
;
914 if (e2
->dest
== EXIT_BLOCK_PTR
915 || ((e2
->flags
& EDGE_CAN_FALLTHRU
)
916 && !(e2
->flags
& EDGE_COMPLEX
)
917 && bbd
[di
].start_of_trace
>= 0
918 && !connected
[bbd
[di
].start_of_trace
]
919 && (EDGE_FREQUENCY (e2
) >= freq_threshold
)
920 && (e2
->count
>= count_threshold
)
922 || e2
->probability
> best2
->probability
923 || (e2
->probability
== best2
->probability
924 && traces
[bbd
[di
].start_of_trace
].length
929 if (e2
->dest
!= EXIT_BLOCK_PTR
)
930 best2_len
= traces
[bbd
[di
].start_of_trace
].length
;
939 /* Copy tiny blocks always; copy larger blocks only when the
940 edge is traversed frequently enough. */
942 && copy_bb_p (best
->dest
,
944 && EDGE_FREQUENCY (best
) >= freq_threshold
945 && best
->count
>= count_threshold
))
951 fprintf (rtl_dump_file
, "Connection: %d %d ",
952 traces
[t
].last
->index
, best
->dest
->index
);
954 fputc ('\n', rtl_dump_file
);
955 else if (next_bb
== EXIT_BLOCK_PTR
)
956 fprintf (rtl_dump_file
, "exit\n");
958 fprintf (rtl_dump_file
, "%d\n", next_bb
->index
);
961 new_bb
= copy_bb (best
->dest
, best
, traces
[t
].last
, t
);
962 traces
[t
].last
= new_bb
;
963 if (next_bb
&& next_bb
!= EXIT_BLOCK_PTR
)
965 t
= bbd
[next_bb
->index
].start_of_trace
;
966 RBI (traces
[last_trace
].last
)->next
= traces
[t
].first
;
971 break; /* Stop finding the successor traces. */
974 break; /* Stop finding the successor traces. */
983 fprintf (rtl_dump_file
, "Final order:\n");
984 for (bb
= traces
[0].first
; bb
; bb
= RBI (bb
)->next
)
985 fprintf (rtl_dump_file
, "%d ", bb
->index
);
986 fprintf (rtl_dump_file
, "\n");
987 fflush (rtl_dump_file
);
993 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
994 when code size is allowed to grow by duplication. */
997 copy_bb_p (basic_block bb
, int code_may_grow
)
1000 int max_size
= uncond_jump_length
;
1005 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1007 if (!cfg_layout_can_duplicate_bb_p (bb
))
1010 if (code_may_grow
&& maybe_hot_bb_p (bb
))
1013 for (insn
= bb
->head
; insn
!= NEXT_INSN (bb
->end
);
1014 insn
= NEXT_INSN (insn
))
1017 size
+= get_attr_length (insn
);
1020 if (size
<= max_size
)
1025 fprintf (rtl_dump_file
,
1026 "Block %d can't be copied because its size = %d.\n",
1033 /* Return the length of unconditional jump instruction. */
1036 get_uncond_jump_length (void)
1041 label
= emit_label_before (gen_label_rtx (), get_insns ());
1042 jump
= emit_jump_insn (gen_jump (label
));
1044 length
= get_attr_length (jump
);
1047 delete_insn (label
);
1051 /* Reorder basic blocks. The main entry point to this file. */
1054 reorder_basic_blocks (void)
1058 struct trace
*traces
;
1060 if (n_basic_blocks
<= 1)
1063 if ((* targetm
.cannot_modify_jumps_p
) ())
1066 cfg_layout_initialize (NULL
);
1068 set_edge_can_fallthru_flag ();
1069 mark_dfs_back_edges ();
1071 /* We are estimating the lenght of uncond jump insn only once since the code
1072 for getting the insn lenght always returns the minimal length now. */
1073 if (uncond_jump_length
== 0)
1074 uncond_jump_length
= get_uncond_jump_length ();
1076 /* We need to know some information for each basic block. */
1077 array_size
= GET_ARRAY_SIZE (last_basic_block
);
1078 bbd
= xmalloc (array_size
* sizeof (bbro_basic_block_data
));
1079 for (i
= 0; i
< array_size
; i
++)
1081 bbd
[i
].start_of_trace
= -1;
1082 bbd
[i
].end_of_trace
= -1;
1087 traces
= xmalloc (n_basic_blocks
* sizeof (struct trace
));
1089 find_traces (&n_traces
, traces
);
1090 connect_traces (n_traces
, traces
);
1095 dump_flow_info (rtl_dump_file
);
1097 cfg_layout_finalize ();