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 (round
< N_ROUNDS
- 1
378 && (bb
->frequency
< exec_th
|| bb
->count
< count_th
379 || probably_never_executed_bb_p (bb
)))
381 int key
= bb_to_key (bb
);
382 bbd
[bb
->index
].heap
= new_heap
;
383 bbd
[bb
->index
].node
= fibheap_insert (new_heap
, key
, bb
);
386 fprintf (rtl_dump_file
,
387 " Possible start point of next round: %d (key: %d)\n",
392 trace
= traces
+ *n_traces
;
394 trace
->round
= round
;
402 /* The probability and frequency of the best edge. */
403 int best_prob
= INT_MIN
/ 2;
404 int best_freq
= INT_MIN
/ 2;
407 mark_bb_visited (bb
, *n_traces
);
411 fprintf (rtl_dump_file
, "Basic block %d was visited in trace %d\n",
412 bb
->index
, *n_traces
- 1);
414 /* Select the successor that will be placed after BB. */
415 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
417 if (e
->flags
& EDGE_FAKE
)
420 if (e
->dest
== EXIT_BLOCK_PTR
)
423 if (RBI (e
->dest
)->visited
424 && RBI (e
->dest
)->visited
!= *n_traces
)
427 prob
= e
->probability
;
428 freq
= EDGE_FREQUENCY (e
);
430 /* Edge that cannot be fallthru or improbable or infrequent
431 successor (ie. it is unsuitable successor). */
432 if (!(e
->flags
& EDGE_CAN_FALLTHRU
) || (e
->flags
& EDGE_COMPLEX
)
433 || prob
< branch_th
|| freq
< exec_th
|| e
->count
< count_th
)
436 if (better_edge_p (bb
, e
, prob
, freq
, best_prob
, best_freq
))
444 /* If the best destination has multiple predecessors, and can be
445 duplicated cheaper than a jump, don't allow it to be added
446 to a trace. We'll duplicate it when connecting traces. */
447 if (best_edge
&& best_edge
->dest
->pred
->pred_next
448 && copy_bb_p (best_edge
->dest
, 0))
451 /* Add all non-selected successors to the heaps. */
452 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
455 || e
->dest
== EXIT_BLOCK_PTR
456 || RBI (e
->dest
)->visited
)
459 key
= bb_to_key (e
->dest
);
461 if (bbd
[e
->dest
->index
].heap
)
463 /* E->DEST is already in some heap. */
464 if (key
!= bbd
[e
->dest
->index
].node
->key
)
468 fprintf (rtl_dump_file
,
469 "Changing key for bb %d from %ld to %ld.\n",
471 (long) bbd
[e
->dest
->index
].node
->key
,
474 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
475 bbd
[e
->dest
->index
].node
, key
);
480 fibheap_t which_heap
= *heap
;
482 prob
= e
->probability
;
483 freq
= EDGE_FREQUENCY (e
);
485 if (!(e
->flags
& EDGE_CAN_FALLTHRU
)
486 || (e
->flags
& EDGE_COMPLEX
)
487 || prob
< branch_th
|| freq
< exec_th
488 || e
->count
< count_th
)
490 if (round
< N_ROUNDS
- 1)
491 which_heap
= new_heap
;
494 bbd
[e
->dest
->index
].heap
= which_heap
;
495 bbd
[e
->dest
->index
].node
= fibheap_insert (which_heap
,
500 fprintf (rtl_dump_file
,
501 " Possible start of %s round: %d (key: %ld)\n",
502 (which_heap
== new_heap
) ? "next" : "this",
503 e
->dest
->index
, (long) key
);
509 if (best_edge
) /* Suitable successor was found. */
511 if (RBI (best_edge
->dest
)->visited
== *n_traces
)
513 /* We do nothing with one basic block loops. */
514 if (best_edge
->dest
!= bb
)
516 if (EDGE_FREQUENCY (best_edge
)
517 > 4 * best_edge
->dest
->frequency
/ 5)
519 /* The loop has at least 4 iterations. If the loop
520 header is not the first block of the function
521 we can rotate the loop. */
523 if (best_edge
->dest
!= ENTRY_BLOCK_PTR
->next_bb
)
527 fprintf (rtl_dump_file
,
528 "Rotating loop %d - %d\n",
529 best_edge
->dest
->index
, bb
->index
);
531 RBI (bb
)->next
= best_edge
->dest
;
532 bb
= rotate_loop (best_edge
, trace
, *n_traces
);
537 /* The loop has less than 4 iterations. */
539 /* Check whether there is another edge from BB. */
541 for (another_edge
= bb
->succ
;
543 another_edge
= another_edge
->succ_next
)
544 if (another_edge
!= best_edge
)
547 if (!another_edge
&& copy_bb_p (best_edge
->dest
,
550 bb
= copy_bb (best_edge
->dest
, best_edge
, bb
,
556 /* Terminate the trace. */
561 /* Check for a situation
570 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
571 >= EDGE_FREQUENCY (AC).
572 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
573 Best ordering is then A B C.
575 This situation is created for example by:
582 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
584 && (e
->flags
& EDGE_CAN_FALLTHRU
)
585 && !(e
->flags
& EDGE_COMPLEX
)
586 && !RBI (e
->dest
)->visited
587 && !e
->dest
->pred
->pred_next
589 && (e
->dest
->succ
->flags
& EDGE_CAN_FALLTHRU
)
590 && !(e
->dest
->succ
->flags
& EDGE_COMPLEX
)
591 && !e
->dest
->succ
->succ_next
592 && e
->dest
->succ
->dest
== best_edge
->dest
593 && 2 * e
->dest
->frequency
>= EDGE_FREQUENCY (best_edge
))
597 fprintf (rtl_dump_file
, "Selecting BB %d\n",
598 best_edge
->dest
->index
);
602 RBI (bb
)->next
= best_edge
->dest
;
603 bb
= best_edge
->dest
;
609 bbd
[trace
->first
->index
].start_of_trace
= *n_traces
- 1;
610 bbd
[trace
->last
->index
].end_of_trace
= *n_traces
- 1;
612 /* The trace is terminated so we have to recount the keys in heap
613 (some block can have a lower key because now one of its predecessors
614 is an end of the trace). */
615 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
617 if (e
->dest
== EXIT_BLOCK_PTR
618 || RBI (e
->dest
)->visited
)
621 if (bbd
[e
->dest
->index
].heap
)
623 key
= bb_to_key (e
->dest
);
624 if (key
!= bbd
[e
->dest
->index
].node
->key
)
628 fprintf (rtl_dump_file
,
629 "Changing key for bb %d from %ld to %ld.\n",
631 (long) bbd
[e
->dest
->index
].node
->key
, key
);
633 fibheap_replace_key (bbd
[e
->dest
->index
].heap
,
634 bbd
[e
->dest
->index
].node
,
641 fibheap_delete (*heap
);
643 /* "Return" the new heap. */
647 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
648 it to trace after BB, mark OLD_BB visited and update pass' data structures
649 (TRACE is a number of trace which OLD_BB is duplicated to). */
652 copy_bb (basic_block old_bb
, edge e
, basic_block bb
, int trace
)
656 new_bb
= cfg_layout_duplicate_bb (old_bb
, e
);
657 if (e
->dest
!= new_bb
)
659 if (RBI (e
->dest
)->visited
)
662 fprintf (rtl_dump_file
,
663 "Duplicated bb %d (created bb %d)\n",
664 old_bb
->index
, new_bb
->index
);
665 RBI (new_bb
)->visited
= trace
;
666 RBI (new_bb
)->next
= RBI (bb
)->next
;
667 RBI (bb
)->next
= new_bb
;
669 if (new_bb
->index
>= array_size
|| last_basic_block
> array_size
)
674 new_size
= MAX (last_basic_block
, new_bb
->index
+ 1);
675 new_size
= GET_ARRAY_SIZE (new_size
);
676 bbd
= xrealloc (bbd
, new_size
* sizeof (bbro_basic_block_data
));
677 for (i
= array_size
; i
< new_size
; i
++)
679 bbd
[i
].start_of_trace
= -1;
680 bbd
[i
].end_of_trace
= -1;
684 array_size
= new_size
;
688 fprintf (rtl_dump_file
,
689 "Growing the dynamic array to %d elements.\n",
697 /* Compute and return the key (for the heap) of the basic block BB. */
700 bb_to_key (basic_block bb
)
706 /* Do not start in probably never executed blocks. */
707 if (probably_never_executed_bb_p (bb
))
710 /* Prefer blocks whose predecessor is an end of some trace
711 or whose predecessor edge is EDGE_DFS_BACK. */
712 for (e
= bb
->pred
; e
; e
= e
->pred_next
)
714 if ((e
->src
!= ENTRY_BLOCK_PTR
&& bbd
[e
->src
->index
].end_of_trace
>= 0)
715 || (e
->flags
& EDGE_DFS_BACK
))
717 int edge_freq
= EDGE_FREQUENCY (e
);
719 if (edge_freq
> priority
)
720 priority
= edge_freq
;
725 /* The block with priority should have significantly lower key. */
726 return -(100 * BB_FREQ_MAX
+ 100 * priority
+ bb
->frequency
);
727 return -bb
->frequency
;
730 /* Return true when the edge E from basic block BB is better than the temporary
731 best edge (details are in function). The probability of edge E is PROB. The
732 frequency of the successor is FREQ. The current best probability is
733 BEST_PROB, the best frequency is BEST_FREQ.
734 The edge is considered to be equivalent when PROB does not differ much from
735 BEST_PROB; similarly for frequency. */
738 better_edge_p (basic_block bb
, edge e
, int prob
, int freq
, int best_prob
,
743 /* The BEST_* values do not have to be best, but can be a bit smaller than
745 int diff_prob
= best_prob
/ 10;
746 int diff_freq
= best_freq
/ 10;
748 if (prob
> best_prob
+ diff_prob
)
749 /* The edge has higher probability than the temporary best edge. */
750 is_better_edge
= true;
751 else if (prob
< best_prob
- diff_prob
)
752 /* The edge has lower probability than the temporary best edge. */
753 is_better_edge
= false;
754 else if (freq
< best_freq
- diff_freq
)
755 /* The edge and the temporary best edge have almost equivalent
756 probabilities. The higher frequency of a successor now means
757 that there is another edge going into that successor.
758 This successor has lower frequency so it is better. */
759 is_better_edge
= true;
760 else if (freq
> best_freq
+ diff_freq
)
761 /* This successor has higher frequency so it is worse. */
762 is_better_edge
= false;
763 else if (e
->dest
->prev_bb
== bb
)
764 /* The edges have equivalent probabilities and the successors
765 have equivalent frequencies. Select the previous successor. */
766 is_better_edge
= true;
768 is_better_edge
= false;
770 return is_better_edge
;
773 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
776 connect_traces (int n_traces
, struct trace
*traces
)
782 gcov_type count_threshold
;
784 freq_threshold
= max_entry_frequency
* DUPLICATION_THRESHOLD
/ 1000;
785 if (max_entry_count
< INT_MAX
/ 1000)
786 count_threshold
= max_entry_count
* DUPLICATION_THRESHOLD
/ 1000;
788 count_threshold
= max_entry_count
/ 1000 * DUPLICATION_THRESHOLD
;
790 connected
= xcalloc (n_traces
, sizeof (bool));
792 for (i
= 0; i
< n_traces
; i
++)
804 /* Find the predecessor traces. */
805 for (t2
= t
; t2
> 0;)
809 for (e
= traces
[t2
].first
->pred
; e
; e
= e
->pred_next
)
811 int si
= e
->src
->index
;
813 if (e
->src
!= ENTRY_BLOCK_PTR
814 && (e
->flags
& EDGE_CAN_FALLTHRU
)
815 && !(e
->flags
& EDGE_COMPLEX
)
816 && bbd
[si
].end_of_trace
>= 0
817 && !connected
[bbd
[si
].end_of_trace
]
819 || e
->probability
> best
->probability
820 || (e
->probability
== best
->probability
821 && traces
[bbd
[si
].end_of_trace
].length
> best_len
)))
824 best_len
= traces
[bbd
[si
].end_of_trace
].length
;
829 RBI (best
->src
)->next
= best
->dest
;
830 t2
= bbd
[best
->src
->index
].end_of_trace
;
831 connected
[t2
] = true;
834 fprintf (rtl_dump_file
, "Connection: %d %d\n",
835 best
->src
->index
, best
->dest
->index
);
843 RBI (traces
[last_trace
].last
)->next
= traces
[t2
].first
;
846 /* Find the successor traces. */
849 /* Find the continuation of the chain. */
852 for (e
= traces
[t
].last
->succ
; e
; e
= e
->succ_next
)
854 int di
= e
->dest
->index
;
856 if (e
->dest
!= EXIT_BLOCK_PTR
857 && (e
->flags
& EDGE_CAN_FALLTHRU
)
858 && !(e
->flags
& EDGE_COMPLEX
)
859 && bbd
[di
].start_of_trace
>= 0
860 && !connected
[bbd
[di
].start_of_trace
]
862 || e
->probability
> best
->probability
863 || (e
->probability
== best
->probability
864 && traces
[bbd
[di
].start_of_trace
].length
> best_len
)))
867 best_len
= traces
[bbd
[di
].start_of_trace
].length
;
875 fprintf (rtl_dump_file
, "Connection: %d %d\n",
876 best
->src
->index
, best
->dest
->index
);
878 t
= bbd
[best
->dest
->index
].start_of_trace
;
879 RBI (traces
[last_trace
].last
)->next
= traces
[t
].first
;
885 /* Try to connect the traces by duplication of 1 block. */
887 basic_block next_bb
= NULL
;
888 bool try_copy
= false;
890 for (e
= traces
[t
].last
->succ
; e
; e
= e
->succ_next
)
891 if (e
->dest
!= EXIT_BLOCK_PTR
892 && (e
->flags
& EDGE_CAN_FALLTHRU
)
893 && !(e
->flags
& EDGE_COMPLEX
)
894 && (!best
|| e
->probability
> best
->probability
))
899 /* If the destination is a start of a trace which is only
900 one block long, then no need to search the successor
901 blocks of the trace. Accept it. */
902 if (bbd
[e
->dest
->index
].start_of_trace
>= 0
903 && traces
[bbd
[e
->dest
->index
].start_of_trace
].length
911 for (e2
= e
->dest
->succ
; e2
; e2
= e2
->succ_next
)
913 int di
= e2
->dest
->index
;
915 if (e2
->dest
== EXIT_BLOCK_PTR
916 || ((e2
->flags
& EDGE_CAN_FALLTHRU
)
917 && !(e2
->flags
& EDGE_COMPLEX
)
918 && bbd
[di
].start_of_trace
>= 0
919 && !connected
[bbd
[di
].start_of_trace
]
920 && (EDGE_FREQUENCY (e2
) >= freq_threshold
)
921 && (e2
->count
>= count_threshold
)
923 || e2
->probability
> best2
->probability
924 || (e2
->probability
== best2
->probability
925 && traces
[bbd
[di
].start_of_trace
].length
930 if (e2
->dest
!= EXIT_BLOCK_PTR
)
931 best2_len
= traces
[bbd
[di
].start_of_trace
].length
;
940 /* Copy tiny blocks always; copy larger blocks only when the
941 edge is traversed frequently enough. */
943 && copy_bb_p (best
->dest
,
945 && EDGE_FREQUENCY (best
) >= freq_threshold
946 && best
->count
>= count_threshold
))
952 fprintf (rtl_dump_file
, "Connection: %d %d ",
953 traces
[t
].last
->index
, best
->dest
->index
);
955 fputc ('\n', rtl_dump_file
);
956 else if (next_bb
== EXIT_BLOCK_PTR
)
957 fprintf (rtl_dump_file
, "exit\n");
959 fprintf (rtl_dump_file
, "%d\n", next_bb
->index
);
962 new_bb
= copy_bb (best
->dest
, best
, traces
[t
].last
, t
);
963 traces
[t
].last
= new_bb
;
964 if (next_bb
&& next_bb
!= EXIT_BLOCK_PTR
)
966 t
= bbd
[next_bb
->index
].start_of_trace
;
967 RBI (traces
[last_trace
].last
)->next
= traces
[t
].first
;
972 break; /* Stop finding the successor traces. */
975 break; /* Stop finding the successor traces. */
984 fprintf (rtl_dump_file
, "Final order:\n");
985 for (bb
= traces
[0].first
; bb
; bb
= RBI (bb
)->next
)
986 fprintf (rtl_dump_file
, "%d ", bb
->index
);
987 fprintf (rtl_dump_file
, "\n");
988 fflush (rtl_dump_file
);
994 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
995 when code size is allowed to grow by duplication. */
998 copy_bb_p (basic_block bb
, int code_may_grow
)
1001 int max_size
= uncond_jump_length
;
1006 if (!bb
->pred
|| !bb
->pred
->pred_next
)
1008 if (!cfg_layout_can_duplicate_bb_p (bb
))
1011 if (code_may_grow
&& maybe_hot_bb_p (bb
))
1014 for (insn
= bb
->head
; insn
!= NEXT_INSN (bb
->end
);
1015 insn
= NEXT_INSN (insn
))
1018 size
+= get_attr_length (insn
);
1021 if (size
<= max_size
)
1026 fprintf (rtl_dump_file
,
1027 "Block %d can't be copied because its size = %d.\n",
1034 /* Return the length of unconditional jump instruction. */
1037 get_uncond_jump_length (void)
1042 label
= emit_label_before (gen_label_rtx (), get_insns ());
1043 jump
= emit_jump_insn (gen_jump (label
));
1045 length
= get_attr_length (jump
);
1048 delete_insn (label
);
1052 /* Reorder basic blocks. The main entry point to this file. */
1055 reorder_basic_blocks (void)
1059 struct trace
*traces
;
1061 if (n_basic_blocks
<= 1)
1064 if ((* targetm
.cannot_modify_jumps_p
) ())
1067 cfg_layout_initialize (NULL
);
1069 set_edge_can_fallthru_flag ();
1070 mark_dfs_back_edges ();
1072 /* We are estimating the lenght of uncond jump insn only once since the code
1073 for getting the insn lenght always returns the minimal length now. */
1074 if (uncond_jump_length
== 0)
1075 uncond_jump_length
= get_uncond_jump_length ();
1077 /* We need to know some information for each basic block. */
1078 array_size
= GET_ARRAY_SIZE (last_basic_block
);
1079 bbd
= xmalloc (array_size
* sizeof (bbro_basic_block_data
));
1080 for (i
= 0; i
< array_size
; i
++)
1082 bbd
[i
].start_of_trace
= -1;
1083 bbd
[i
].end_of_trace
= -1;
1088 traces
= xmalloc (n_basic_blocks
* sizeof (struct trace
));
1090 find_traces (&n_traces
, traces
);
1091 connect_traces (n_traces
, traces
);
1096 dump_flow_info (rtl_dump_file
);
1098 cfg_layout_finalize ();