Daily bump.
[official-gcc.git] / gcc / bb-reorder.c
blob9428ef3b92302abf0f8e994a1489161693503a68
1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007
3 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 2, or (at your option)
10 any later version.
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 COPYING. If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
22 /* This (greedy) algorithm constructs traces in several rounds.
23 The construction starts from "seeds". The seed for the first round
24 is the entry point of function. When there are more than one seed
25 that one is selected first that has the lowest key in the heap
26 (see function bb_to_key). Then the algorithm repeatedly adds the most
27 probable successor to the end of a trace. Finally it connects the traces.
29 There are two parameters: Branch Threshold and Exec Threshold.
30 If the edge to a successor of the actual basic block is lower than
31 Branch Threshold or the frequency of the successor is lower than
32 Exec Threshold the successor will be the seed in one of the next rounds.
33 Each round has these parameters lower than the previous one.
34 The last round has to have these parameters set to zero
35 so that the remaining blocks are picked up.
37 The algorithm selects the most probable successor from all unvisited
38 successors and successors that have been added to this trace.
39 The other successors (that has not been "sent" to the next round) will be
40 other seeds for this round and the secondary traces will start in them.
41 If the successor has not been visited in this trace it is added to the trace
42 (however, there is some heuristic for simple branches).
43 If the successor has been visited in this trace the loop has been found.
44 If the loop has many iterations the loop is rotated so that the
45 source block of the most probable edge going out from the loop
46 is the last block of the trace.
47 If the loop has few iterations and there is no edge from the last block of
48 the loop going out from loop the loop header is duplicated.
49 Finally, the construction of the trace is terminated.
51 When connecting traces it first checks whether there is an edge from the
52 last block of one trace to the first block of another trace.
53 When there are still some unconnected traces it checks whether there exists
54 a basic block BB such that BB is a successor of the last bb of one trace
55 and BB is a predecessor of the first block of another trace. In this case,
56 BB is duplicated and the traces are connected through this duplicate.
57 The rest of traces are simply connected so there will be a jump to the
58 beginning of the rest of trace.
61 References:
63 "Software Trace Cache"
64 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
65 http://citeseer.nj.nec.com/15361.html
69 #include "config.h"
70 #include "system.h"
71 #include "coretypes.h"
72 #include "tm.h"
73 #include "rtl.h"
74 #include "regs.h"
75 #include "flags.h"
76 #include "timevar.h"
77 #include "output.h"
78 #include "cfglayout.h"
79 #include "fibheap.h"
80 #include "target.h"
81 #include "function.h"
82 #include "tm_p.h"
83 #include "obstack.h"
84 #include "expr.h"
85 #include "params.h"
86 #include "toplev.h"
87 #include "tree-pass.h"
89 #ifndef HAVE_conditional_execution
90 #define HAVE_conditional_execution 0
91 #endif
93 /* The number of rounds. In most cases there will only be 4 rounds, but
94 when partitioning hot and cold basic blocks into separate sections of
95 the .o file there will be an extra round.*/
96 #define N_ROUNDS 5
98 /* Stubs in case we don't have a return insn.
99 We have to check at runtime too, not only compiletime. */
101 #ifndef HAVE_return
102 #define HAVE_return 0
103 #define gen_return() NULL_RTX
104 #endif
107 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
108 static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
110 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
111 static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
113 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
114 block the edge destination is not duplicated while connecting traces. */
115 #define DUPLICATION_THRESHOLD 100
117 /* Length of unconditional jump instruction. */
118 static int uncond_jump_length;
120 /* Structure to hold needed information for each basic block. */
121 typedef struct bbro_basic_block_data_def
123 /* Which trace is the bb start of (-1 means it is not a start of a trace). */
124 int start_of_trace;
126 /* Which trace is the bb end of (-1 means it is not an end of a trace). */
127 int end_of_trace;
129 /* Which trace is the bb in? */
130 int in_trace;
132 /* Which heap is BB in (if any)? */
133 fibheap_t heap;
135 /* Which heap node is BB in (if any)? */
136 fibnode_t node;
137 } bbro_basic_block_data;
139 /* The current size of the following dynamic array. */
140 static int array_size;
142 /* The array which holds needed information for basic blocks. */
143 static bbro_basic_block_data *bbd;
145 /* To avoid frequent reallocation the size of arrays is greater than needed,
146 the number of elements is (not less than) 1.25 * size_wanted. */
147 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
149 /* Free the memory and set the pointer to NULL. */
150 #define FREE(P) (gcc_assert (P), free (P), P = 0)
152 /* Structure for holding information about a trace. */
153 struct trace
155 /* First and last basic block of the trace. */
156 basic_block first, last;
158 /* The round of the STC creation which this trace was found in. */
159 int round;
161 /* The length (i.e. the number of basic blocks) of the trace. */
162 int length;
165 /* Maximum frequency and count of one of the entry blocks. */
166 static int max_entry_frequency;
167 static gcov_type max_entry_count;
169 /* Local function prototypes. */
170 static void find_traces (int *, struct trace *);
171 static basic_block rotate_loop (edge, struct trace *, int);
172 static void mark_bb_visited (basic_block, int);
173 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
174 int, fibheap_t *, int);
175 static basic_block copy_bb (basic_block, edge, basic_block, int);
176 static fibheapkey_t bb_to_key (basic_block);
177 static bool better_edge_p (basic_block, edge, int, int, int, int, edge);
178 static void connect_traces (int, struct trace *);
179 static bool copy_bb_p (basic_block, int);
180 static int get_uncond_jump_length (void);
181 static bool push_to_next_round_p (basic_block, int, int, int, gcov_type);
182 static void find_rarely_executed_basic_blocks_and_crossing_edges (edge *,
183 int *,
184 int *);
185 static void add_labels_and_missing_jumps (edge *, int);
186 static void add_reg_crossing_jump_notes (void);
187 static void fix_up_fall_thru_edges (void);
188 static void fix_edges_for_rarely_executed_code (edge *, int);
189 static void fix_crossing_conditional_branches (void);
190 static void fix_crossing_unconditional_branches (void);
192 /* Check to see if bb should be pushed into the next round of trace
193 collections or not. Reasons for pushing the block forward are 1).
194 If the block is cold, we are doing partitioning, and there will be
195 another round (cold partition blocks are not supposed to be
196 collected into traces until the very last round); or 2). There will
197 be another round, and the basic block is not "hot enough" for the
198 current round of trace collection. */
200 static bool
201 push_to_next_round_p (basic_block bb, int round, int number_of_rounds,
202 int exec_th, gcov_type count_th)
204 bool there_exists_another_round;
205 bool block_not_hot_enough;
207 there_exists_another_round = round < number_of_rounds - 1;
209 block_not_hot_enough = (bb->frequency < exec_th
210 || bb->count < count_th
211 || probably_never_executed_bb_p (bb));
213 if (there_exists_another_round
214 && block_not_hot_enough)
215 return true;
216 else
217 return false;
220 /* Find the traces for Software Trace Cache. Chain each trace through
221 RBI()->next. Store the number of traces to N_TRACES and description of
222 traces to TRACES. */
224 static void
225 find_traces (int *n_traces, struct trace *traces)
227 int i;
228 int number_of_rounds;
229 edge e;
230 edge_iterator ei;
231 fibheap_t heap;
233 /* Add one extra round of trace collection when partitioning hot/cold
234 basic blocks into separate sections. The last round is for all the
235 cold blocks (and ONLY the cold blocks). */
237 number_of_rounds = N_ROUNDS - 1;
239 /* Insert entry points of function into heap. */
240 heap = fibheap_new ();
241 max_entry_frequency = 0;
242 max_entry_count = 0;
243 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
245 bbd[e->dest->index].heap = heap;
246 bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
247 e->dest);
248 if (e->dest->frequency > max_entry_frequency)
249 max_entry_frequency = e->dest->frequency;
250 if (e->dest->count > max_entry_count)
251 max_entry_count = e->dest->count;
254 /* Find the traces. */
255 for (i = 0; i < number_of_rounds; i++)
257 gcov_type count_threshold;
259 if (dump_file)
260 fprintf (dump_file, "STC - round %d\n", i + 1);
262 if (max_entry_count < INT_MAX / 1000)
263 count_threshold = max_entry_count * exec_threshold[i] / 1000;
264 else
265 count_threshold = max_entry_count / 1000 * exec_threshold[i];
267 find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
268 max_entry_frequency * exec_threshold[i] / 1000,
269 count_threshold, traces, n_traces, i, &heap,
270 number_of_rounds);
272 fibheap_delete (heap);
274 if (dump_file)
276 for (i = 0; i < *n_traces; i++)
278 basic_block bb;
279 fprintf (dump_file, "Trace %d (round %d): ", i + 1,
280 traces[i].round + 1);
281 for (bb = traces[i].first; bb != traces[i].last; bb = bb->aux)
282 fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
283 fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
285 fflush (dump_file);
289 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
290 (with sequential number TRACE_N). */
292 static basic_block
293 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
295 basic_block bb;
297 /* Information about the best end (end after rotation) of the loop. */
298 basic_block best_bb = NULL;
299 edge best_edge = NULL;
300 int best_freq = -1;
301 gcov_type best_count = -1;
302 /* The best edge is preferred when its destination is not visited yet
303 or is a start block of some trace. */
304 bool is_preferred = false;
306 /* Find the most frequent edge that goes out from current trace. */
307 bb = back_edge->dest;
310 edge e;
311 edge_iterator ei;
313 FOR_EACH_EDGE (e, ei, bb->succs)
314 if (e->dest != EXIT_BLOCK_PTR
315 && e->dest->il.rtl->visited != trace_n
316 && (e->flags & EDGE_CAN_FALLTHRU)
317 && !(e->flags & EDGE_COMPLEX))
319 if (is_preferred)
321 /* The best edge is preferred. */
322 if (!e->dest->il.rtl->visited
323 || bbd[e->dest->index].start_of_trace >= 0)
325 /* The current edge E is also preferred. */
326 int freq = EDGE_FREQUENCY (e);
327 if (freq > best_freq || e->count > best_count)
329 best_freq = freq;
330 best_count = e->count;
331 best_edge = e;
332 best_bb = bb;
336 else
338 if (!e->dest->il.rtl->visited
339 || bbd[e->dest->index].start_of_trace >= 0)
341 /* The current edge E is preferred. */
342 is_preferred = true;
343 best_freq = EDGE_FREQUENCY (e);
344 best_count = e->count;
345 best_edge = e;
346 best_bb = bb;
348 else
350 int freq = EDGE_FREQUENCY (e);
351 if (!best_edge || freq > best_freq || e->count > best_count)
353 best_freq = freq;
354 best_count = e->count;
355 best_edge = e;
356 best_bb = bb;
361 bb = bb->aux;
363 while (bb != back_edge->dest);
365 if (best_bb)
367 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
368 the trace. */
369 if (back_edge->dest == trace->first)
371 trace->first = best_bb->aux;
373 else
375 basic_block prev_bb;
377 for (prev_bb = trace->first;
378 prev_bb->aux != back_edge->dest;
379 prev_bb = prev_bb->aux)
381 prev_bb->aux = best_bb->aux;
383 /* Try to get rid of uncond jump to cond jump. */
384 if (single_succ_p (prev_bb))
386 basic_block header = single_succ (prev_bb);
388 /* Duplicate HEADER if it is a small block containing cond jump
389 in the end. */
390 if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
391 && !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
392 NULL_RTX))
393 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
397 else
399 /* We have not found suitable loop tail so do no rotation. */
400 best_bb = back_edge->src;
402 best_bb->aux = NULL;
403 return best_bb;
406 /* This function marks BB that it was visited in trace number TRACE. */
408 static void
409 mark_bb_visited (basic_block bb, int trace)
411 bb->il.rtl->visited = trace;
412 if (bbd[bb->index].heap)
414 fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
415 bbd[bb->index].heap = NULL;
416 bbd[bb->index].node = NULL;
420 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
421 not include basic blocks their probability is lower than BRANCH_TH or their
422 frequency is lower than EXEC_TH into traces (or count is lower than
423 COUNT_TH). It stores the new traces into TRACES and modifies the number of
424 traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
425 expects that starting basic blocks are in *HEAP and at the end it deletes
426 *HEAP and stores starting points for the next round into new *HEAP. */
428 static void
429 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
430 struct trace *traces, int *n_traces, int round,
431 fibheap_t *heap, int number_of_rounds)
433 /* Heap for discarded basic blocks which are possible starting points for
434 the next round. */
435 fibheap_t new_heap = fibheap_new ();
437 while (!fibheap_empty (*heap))
439 basic_block bb;
440 struct trace *trace;
441 edge best_edge, e;
442 fibheapkey_t key;
443 edge_iterator ei;
445 bb = fibheap_extract_min (*heap);
446 bbd[bb->index].heap = NULL;
447 bbd[bb->index].node = NULL;
449 if (dump_file)
450 fprintf (dump_file, "Getting bb %d\n", bb->index);
452 /* If the BB's frequency is too low send BB to the next round. When
453 partitioning hot/cold blocks into separate sections, make sure all
454 the cold blocks (and ONLY the cold blocks) go into the (extra) final
455 round. */
457 if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
458 count_th))
460 int key = bb_to_key (bb);
461 bbd[bb->index].heap = new_heap;
462 bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
464 if (dump_file)
465 fprintf (dump_file,
466 " Possible start point of next round: %d (key: %d)\n",
467 bb->index, key);
468 continue;
471 trace = traces + *n_traces;
472 trace->first = bb;
473 trace->round = round;
474 trace->length = 0;
475 bbd[bb->index].in_trace = *n_traces;
476 (*n_traces)++;
480 int prob, freq;
481 bool ends_in_call;
483 /* The probability and frequency of the best edge. */
484 int best_prob = INT_MIN / 2;
485 int best_freq = INT_MIN / 2;
487 best_edge = NULL;
488 mark_bb_visited (bb, *n_traces);
489 trace->length++;
491 if (dump_file)
492 fprintf (dump_file, "Basic block %d was visited in trace %d\n",
493 bb->index, *n_traces - 1);
495 ends_in_call = block_ends_with_call_p (bb);
497 /* Select the successor that will be placed after BB. */
498 FOR_EACH_EDGE (e, ei, bb->succs)
500 gcc_assert (!(e->flags & EDGE_FAKE));
502 if (e->dest == EXIT_BLOCK_PTR)
503 continue;
505 if (e->dest->il.rtl->visited
506 && e->dest->il.rtl->visited != *n_traces)
507 continue;
509 if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
510 continue;
512 prob = e->probability;
513 freq = e->dest->frequency;
515 /* The only sensible preference for a call instruction is the
516 fallthru edge. Don't bother selecting anything else. */
517 if (ends_in_call)
519 if (e->flags & EDGE_CAN_FALLTHRU)
521 best_edge = e;
522 best_prob = prob;
523 best_freq = freq;
525 continue;
528 /* Edge that cannot be fallthru or improbable or infrequent
529 successor (i.e. it is unsuitable successor). */
530 if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
531 || prob < branch_th || EDGE_FREQUENCY (e) < exec_th
532 || e->count < count_th)
533 continue;
535 /* If partitioning hot/cold basic blocks, don't consider edges
536 that cross section boundaries. */
538 if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
539 best_edge))
541 best_edge = e;
542 best_prob = prob;
543 best_freq = freq;
547 /* If the best destination has multiple predecessors, and can be
548 duplicated cheaper than a jump, don't allow it to be added
549 to a trace. We'll duplicate it when connecting traces. */
550 if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2
551 && copy_bb_p (best_edge->dest, 0))
552 best_edge = NULL;
554 /* Add all non-selected successors to the heaps. */
555 FOR_EACH_EDGE (e, ei, bb->succs)
557 if (e == best_edge
558 || e->dest == EXIT_BLOCK_PTR
559 || e->dest->il.rtl->visited)
560 continue;
562 key = bb_to_key (e->dest);
564 if (bbd[e->dest->index].heap)
566 /* E->DEST is already in some heap. */
567 if (key != bbd[e->dest->index].node->key)
569 if (dump_file)
571 fprintf (dump_file,
572 "Changing key for bb %d from %ld to %ld.\n",
573 e->dest->index,
574 (long) bbd[e->dest->index].node->key,
575 key);
577 fibheap_replace_key (bbd[e->dest->index].heap,
578 bbd[e->dest->index].node, key);
581 else
583 fibheap_t which_heap = *heap;
585 prob = e->probability;
586 freq = EDGE_FREQUENCY (e);
588 if (!(e->flags & EDGE_CAN_FALLTHRU)
589 || (e->flags & EDGE_COMPLEX)
590 || prob < branch_th || freq < exec_th
591 || e->count < count_th)
593 /* When partitioning hot/cold basic blocks, make sure
594 the cold blocks (and only the cold blocks) all get
595 pushed to the last round of trace collection. */
597 if (push_to_next_round_p (e->dest, round,
598 number_of_rounds,
599 exec_th, count_th))
600 which_heap = new_heap;
603 bbd[e->dest->index].heap = which_heap;
604 bbd[e->dest->index].node = fibheap_insert (which_heap,
605 key, e->dest);
607 if (dump_file)
609 fprintf (dump_file,
610 " Possible start of %s round: %d (key: %ld)\n",
611 (which_heap == new_heap) ? "next" : "this",
612 e->dest->index, (long) key);
618 if (best_edge) /* Suitable successor was found. */
620 if (best_edge->dest->il.rtl->visited == *n_traces)
622 /* We do nothing with one basic block loops. */
623 if (best_edge->dest != bb)
625 if (EDGE_FREQUENCY (best_edge)
626 > 4 * best_edge->dest->frequency / 5)
628 /* The loop has at least 4 iterations. If the loop
629 header is not the first block of the function
630 we can rotate the loop. */
632 if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
634 if (dump_file)
636 fprintf (dump_file,
637 "Rotating loop %d - %d\n",
638 best_edge->dest->index, bb->index);
640 bb->aux = best_edge->dest;
641 bbd[best_edge->dest->index].in_trace =
642 (*n_traces) - 1;
643 bb = rotate_loop (best_edge, trace, *n_traces);
646 else
648 /* The loop has less than 4 iterations. */
650 if (single_succ_p (bb)
651 && copy_bb_p (best_edge->dest, !optimize_size))
653 bb = copy_bb (best_edge->dest, best_edge, bb,
654 *n_traces);
655 trace->length++;
660 /* Terminate the trace. */
661 break;
663 else
665 /* Check for a situation
673 where
674 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
675 >= EDGE_FREQUENCY (AC).
676 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
677 Best ordering is then A B C.
679 This situation is created for example by:
681 if (A) B;
686 FOR_EACH_EDGE (e, ei, bb->succs)
687 if (e != best_edge
688 && (e->flags & EDGE_CAN_FALLTHRU)
689 && !(e->flags & EDGE_COMPLEX)
690 && !e->dest->il.rtl->visited
691 && single_pred_p (e->dest)
692 && !(e->flags & EDGE_CROSSING)
693 && single_succ_p (e->dest)
694 && (single_succ_edge (e->dest)->flags
695 & EDGE_CAN_FALLTHRU)
696 && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
697 && single_succ (e->dest) == best_edge->dest
698 && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
700 best_edge = e;
701 if (dump_file)
702 fprintf (dump_file, "Selecting BB %d\n",
703 best_edge->dest->index);
704 break;
707 bb->aux = best_edge->dest;
708 bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
709 bb = best_edge->dest;
713 while (best_edge);
714 trace->last = bb;
715 bbd[trace->first->index].start_of_trace = *n_traces - 1;
716 bbd[trace->last->index].end_of_trace = *n_traces - 1;
718 /* The trace is terminated so we have to recount the keys in heap
719 (some block can have a lower key because now one of its predecessors
720 is an end of the trace). */
721 FOR_EACH_EDGE (e, ei, bb->succs)
723 if (e->dest == EXIT_BLOCK_PTR
724 || e->dest->il.rtl->visited)
725 continue;
727 if (bbd[e->dest->index].heap)
729 key = bb_to_key (e->dest);
730 if (key != bbd[e->dest->index].node->key)
732 if (dump_file)
734 fprintf (dump_file,
735 "Changing key for bb %d from %ld to %ld.\n",
736 e->dest->index,
737 (long) bbd[e->dest->index].node->key, key);
739 fibheap_replace_key (bbd[e->dest->index].heap,
740 bbd[e->dest->index].node,
741 key);
747 fibheap_delete (*heap);
749 /* "Return" the new heap. */
750 *heap = new_heap;
753 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
754 it to trace after BB, mark OLD_BB visited and update pass' data structures
755 (TRACE is a number of trace which OLD_BB is duplicated to). */
757 static basic_block
758 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
760 basic_block new_bb;
762 new_bb = duplicate_block (old_bb, e, bb);
763 BB_COPY_PARTITION (new_bb, old_bb);
765 gcc_assert (e->dest == new_bb);
766 gcc_assert (!e->dest->il.rtl->visited);
768 if (dump_file)
769 fprintf (dump_file,
770 "Duplicated bb %d (created bb %d)\n",
771 old_bb->index, new_bb->index);
772 new_bb->il.rtl->visited = trace;
773 new_bb->aux = bb->aux;
774 bb->aux = new_bb;
776 if (new_bb->index >= array_size || last_basic_block > array_size)
778 int i;
779 int new_size;
781 new_size = MAX (last_basic_block, new_bb->index + 1);
782 new_size = GET_ARRAY_SIZE (new_size);
783 bbd = xrealloc (bbd, new_size * sizeof (bbro_basic_block_data));
784 for (i = array_size; i < new_size; i++)
786 bbd[i].start_of_trace = -1;
787 bbd[i].in_trace = -1;
788 bbd[i].end_of_trace = -1;
789 bbd[i].heap = NULL;
790 bbd[i].node = NULL;
792 array_size = new_size;
794 if (dump_file)
796 fprintf (dump_file,
797 "Growing the dynamic array to %d elements.\n",
798 array_size);
802 bbd[new_bb->index].in_trace = trace;
804 return new_bb;
807 /* Compute and return the key (for the heap) of the basic block BB. */
809 static fibheapkey_t
810 bb_to_key (basic_block bb)
812 edge e;
813 edge_iterator ei;
814 int priority = 0;
816 /* Do not start in probably never executed blocks. */
818 if (BB_PARTITION (bb) == BB_COLD_PARTITION
819 || probably_never_executed_bb_p (bb))
820 return BB_FREQ_MAX;
822 /* Prefer blocks whose predecessor is an end of some trace
823 or whose predecessor edge is EDGE_DFS_BACK. */
824 FOR_EACH_EDGE (e, ei, bb->preds)
826 if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
827 || (e->flags & EDGE_DFS_BACK))
829 int edge_freq = EDGE_FREQUENCY (e);
831 if (edge_freq > priority)
832 priority = edge_freq;
836 if (priority)
837 /* The block with priority should have significantly lower key. */
838 return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
839 return -bb->frequency;
842 /* Return true when the edge E from basic block BB is better than the temporary
843 best edge (details are in function). The probability of edge E is PROB. The
844 frequency of the successor is FREQ. The current best probability is
845 BEST_PROB, the best frequency is BEST_FREQ.
846 The edge is considered to be equivalent when PROB does not differ much from
847 BEST_PROB; similarly for frequency. */
849 static bool
850 better_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob,
851 int best_freq, edge cur_best_edge)
853 bool is_better_edge;
855 /* The BEST_* values do not have to be best, but can be a bit smaller than
856 maximum values. */
857 int diff_prob = best_prob / 10;
858 int diff_freq = best_freq / 10;
860 if (prob > best_prob + diff_prob)
861 /* The edge has higher probability than the temporary best edge. */
862 is_better_edge = true;
863 else if (prob < best_prob - diff_prob)
864 /* The edge has lower probability than the temporary best edge. */
865 is_better_edge = false;
866 else if (freq < best_freq - diff_freq)
867 /* The edge and the temporary best edge have almost equivalent
868 probabilities. The higher frequency of a successor now means
869 that there is another edge going into that successor.
870 This successor has lower frequency so it is better. */
871 is_better_edge = true;
872 else if (freq > best_freq + diff_freq)
873 /* This successor has higher frequency so it is worse. */
874 is_better_edge = false;
875 else if (e->dest->prev_bb == bb)
876 /* The edges have equivalent probabilities and the successors
877 have equivalent frequencies. Select the previous successor. */
878 is_better_edge = true;
879 else
880 is_better_edge = false;
882 /* If we are doing hot/cold partitioning, make sure that we always favor
883 non-crossing edges over crossing edges. */
885 if (!is_better_edge
886 && flag_reorder_blocks_and_partition
887 && cur_best_edge
888 && (cur_best_edge->flags & EDGE_CROSSING)
889 && !(e->flags & EDGE_CROSSING))
890 is_better_edge = true;
892 return is_better_edge;
895 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
897 static void
898 connect_traces (int n_traces, struct trace *traces)
900 int i;
901 bool *connected;
902 bool two_passes;
903 int last_trace;
904 int current_pass;
905 int current_partition;
906 int freq_threshold;
907 gcov_type count_threshold;
909 freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
910 if (max_entry_count < INT_MAX / 1000)
911 count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
912 else
913 count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
915 connected = XCNEWVEC (bool, n_traces);
916 last_trace = -1;
917 current_pass = 1;
918 current_partition = BB_PARTITION (traces[0].first);
919 two_passes = false;
921 if (flag_reorder_blocks_and_partition)
922 for (i = 0; i < n_traces && !two_passes; i++)
923 if (BB_PARTITION (traces[0].first)
924 != BB_PARTITION (traces[i].first))
925 two_passes = true;
927 for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
929 int t = i;
930 int t2;
931 edge e, best;
932 int best_len;
934 if (i >= n_traces)
936 gcc_assert (two_passes && current_pass == 1);
937 i = 0;
938 t = i;
939 current_pass = 2;
940 if (current_partition == BB_HOT_PARTITION)
941 current_partition = BB_COLD_PARTITION;
942 else
943 current_partition = BB_HOT_PARTITION;
946 if (connected[t])
947 continue;
949 if (two_passes
950 && BB_PARTITION (traces[t].first) != current_partition)
951 continue;
953 connected[t] = true;
955 /* Find the predecessor traces. */
956 for (t2 = t; t2 > 0;)
958 edge_iterator ei;
959 best = NULL;
960 best_len = 0;
961 FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
963 int si = e->src->index;
965 if (e->src != ENTRY_BLOCK_PTR
966 && (e->flags & EDGE_CAN_FALLTHRU)
967 && !(e->flags & EDGE_COMPLEX)
968 && bbd[si].end_of_trace >= 0
969 && !connected[bbd[si].end_of_trace]
970 && (BB_PARTITION (e->src) == current_partition)
971 && (!best
972 || e->probability > best->probability
973 || (e->probability == best->probability
974 && traces[bbd[si].end_of_trace].length > best_len)))
976 best = e;
977 best_len = traces[bbd[si].end_of_trace].length;
980 if (best)
982 best->src->aux = best->dest;
983 t2 = bbd[best->src->index].end_of_trace;
984 connected[t2] = true;
986 if (dump_file)
988 fprintf (dump_file, "Connection: %d %d\n",
989 best->src->index, best->dest->index);
992 else
993 break;
996 if (last_trace >= 0)
997 traces[last_trace].last->aux = traces[t2].first;
998 last_trace = t;
1000 /* Find the successor traces. */
1001 while (1)
1003 /* Find the continuation of the chain. */
1004 edge_iterator ei;
1005 best = NULL;
1006 best_len = 0;
1007 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1009 int di = e->dest->index;
1011 if (e->dest != EXIT_BLOCK_PTR
1012 && (e->flags & EDGE_CAN_FALLTHRU)
1013 && !(e->flags & EDGE_COMPLEX)
1014 && bbd[di].start_of_trace >= 0
1015 && !connected[bbd[di].start_of_trace]
1016 && (BB_PARTITION (e->dest) == current_partition)
1017 && (!best
1018 || e->probability > best->probability
1019 || (e->probability == best->probability
1020 && traces[bbd[di].start_of_trace].length > best_len)))
1022 best = e;
1023 best_len = traces[bbd[di].start_of_trace].length;
1027 if (best)
1029 if (dump_file)
1031 fprintf (dump_file, "Connection: %d %d\n",
1032 best->src->index, best->dest->index);
1034 t = bbd[best->dest->index].start_of_trace;
1035 traces[last_trace].last->aux = traces[t].first;
1036 connected[t] = true;
1037 last_trace = t;
1039 else
1041 /* Try to connect the traces by duplication of 1 block. */
1042 edge e2;
1043 basic_block next_bb = NULL;
1044 bool try_copy = false;
1046 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1047 if (e->dest != EXIT_BLOCK_PTR
1048 && (e->flags & EDGE_CAN_FALLTHRU)
1049 && !(e->flags & EDGE_COMPLEX)
1050 && (!best || e->probability > best->probability))
1052 edge_iterator ei;
1053 edge best2 = NULL;
1054 int best2_len = 0;
1056 /* If the destination is a start of a trace which is only
1057 one block long, then no need to search the successor
1058 blocks of the trace. Accept it. */
1059 if (bbd[e->dest->index].start_of_trace >= 0
1060 && traces[bbd[e->dest->index].start_of_trace].length
1061 == 1)
1063 best = e;
1064 try_copy = true;
1065 continue;
1068 FOR_EACH_EDGE (e2, ei, e->dest->succs)
1070 int di = e2->dest->index;
1072 if (e2->dest == EXIT_BLOCK_PTR
1073 || ((e2->flags & EDGE_CAN_FALLTHRU)
1074 && !(e2->flags & EDGE_COMPLEX)
1075 && bbd[di].start_of_trace >= 0
1076 && !connected[bbd[di].start_of_trace]
1077 && (BB_PARTITION (e2->dest) == current_partition)
1078 && (EDGE_FREQUENCY (e2) >= freq_threshold)
1079 && (e2->count >= count_threshold)
1080 && (!best2
1081 || e2->probability > best2->probability
1082 || (e2->probability == best2->probability
1083 && traces[bbd[di].start_of_trace].length
1084 > best2_len))))
1086 best = e;
1087 best2 = e2;
1088 if (e2->dest != EXIT_BLOCK_PTR)
1089 best2_len = traces[bbd[di].start_of_trace].length;
1090 else
1091 best2_len = INT_MAX;
1092 next_bb = e2->dest;
1093 try_copy = true;
1098 if (flag_reorder_blocks_and_partition)
1099 try_copy = false;
1101 /* Copy tiny blocks always; copy larger blocks only when the
1102 edge is traversed frequently enough. */
1103 if (try_copy
1104 && copy_bb_p (best->dest,
1105 !optimize_size
1106 && EDGE_FREQUENCY (best) >= freq_threshold
1107 && best->count >= count_threshold))
1109 basic_block new_bb;
1111 if (dump_file)
1113 fprintf (dump_file, "Connection: %d %d ",
1114 traces[t].last->index, best->dest->index);
1115 if (!next_bb)
1116 fputc ('\n', dump_file);
1117 else if (next_bb == EXIT_BLOCK_PTR)
1118 fprintf (dump_file, "exit\n");
1119 else
1120 fprintf (dump_file, "%d\n", next_bb->index);
1123 new_bb = copy_bb (best->dest, best, traces[t].last, t);
1124 traces[t].last = new_bb;
1125 if (next_bb && next_bb != EXIT_BLOCK_PTR)
1127 t = bbd[next_bb->index].start_of_trace;
1128 traces[last_trace].last->aux = traces[t].first;
1129 connected[t] = true;
1130 last_trace = t;
1132 else
1133 break; /* Stop finding the successor traces. */
1135 else
1136 break; /* Stop finding the successor traces. */
1141 if (dump_file)
1143 basic_block bb;
1145 fprintf (dump_file, "Final order:\n");
1146 for (bb = traces[0].first; bb; bb = bb->aux)
1147 fprintf (dump_file, "%d ", bb->index);
1148 fprintf (dump_file, "\n");
1149 fflush (dump_file);
1152 FREE (connected);
1155 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1156 when code size is allowed to grow by duplication. */
1158 static bool
1159 copy_bb_p (basic_block bb, int code_may_grow)
1161 int size = 0;
1162 int max_size = uncond_jump_length;
1163 rtx insn;
1165 if (!bb->frequency)
1166 return false;
1167 if (EDGE_COUNT (bb->preds) < 2)
1168 return false;
1169 if (!can_duplicate_block_p (bb))
1170 return false;
1172 /* Avoid duplicating blocks which have many successors (PR/13430). */
1173 if (EDGE_COUNT (bb->succs) > 8)
1174 return false;
1176 if (code_may_grow && maybe_hot_bb_p (bb))
1177 max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
1179 FOR_BB_INSNS (bb, insn)
1181 if (INSN_P (insn))
1182 size += get_attr_min_length (insn);
1185 if (size <= max_size)
1186 return true;
1188 if (dump_file)
1190 fprintf (dump_file,
1191 "Block %d can't be copied because its size = %d.\n",
1192 bb->index, size);
1195 return false;
1198 /* Return the length of unconditional jump instruction. */
1200 static int
1201 get_uncond_jump_length (void)
1203 rtx label, jump;
1204 int length;
1206 label = emit_label_before (gen_label_rtx (), get_insns ());
1207 jump = emit_jump_insn (gen_jump (label));
1209 length = get_attr_min_length (jump);
1211 delete_insn (jump);
1212 delete_insn (label);
1213 return length;
1216 /* Find the basic blocks that are rarely executed and need to be moved to
1217 a separate section of the .o file (to cut down on paging and improve
1218 cache locality). */
1220 static void
1221 find_rarely_executed_basic_blocks_and_crossing_edges (edge *crossing_edges,
1222 int *n_crossing_edges,
1223 int *max_idx)
1225 basic_block bb;
1226 bool has_hot_blocks = false;
1227 edge e;
1228 int i;
1229 edge_iterator ei;
1231 /* Mark which partition (hot/cold) each basic block belongs in. */
1233 FOR_EACH_BB (bb)
1235 if (probably_never_executed_bb_p (bb))
1236 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1237 else
1239 BB_SET_PARTITION (bb, BB_HOT_PARTITION);
1240 has_hot_blocks = true;
1244 /* Mark every edge that crosses between sections. */
1246 i = 0;
1247 FOR_EACH_BB (bb)
1248 FOR_EACH_EDGE (e, ei, bb->succs)
1250 if (e->src != ENTRY_BLOCK_PTR
1251 && e->dest != EXIT_BLOCK_PTR
1252 && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1254 e->flags |= EDGE_CROSSING;
1255 if (i == *max_idx)
1257 *max_idx *= 2;
1258 crossing_edges = xrealloc (crossing_edges,
1259 (*max_idx) * sizeof (edge));
1261 crossing_edges[i++] = e;
1263 else
1264 e->flags &= ~EDGE_CROSSING;
1266 *n_crossing_edges = i;
1269 /* If any destination of a crossing edge does not have a label, add label;
1270 Convert any fall-through crossing edges (for blocks that do not contain
1271 a jump) to unconditional jumps. */
1273 static void
1274 add_labels_and_missing_jumps (edge *crossing_edges, int n_crossing_edges)
1276 int i;
1277 basic_block src;
1278 basic_block dest;
1279 rtx label;
1280 rtx barrier;
1281 rtx new_jump;
1283 for (i=0; i < n_crossing_edges; i++)
1285 if (crossing_edges[i])
1287 src = crossing_edges[i]->src;
1288 dest = crossing_edges[i]->dest;
1290 /* Make sure dest has a label. */
1292 if (dest && (dest != EXIT_BLOCK_PTR))
1294 label = block_label (dest);
1296 /* Make sure source block ends with a jump. */
1298 if (src && (src != ENTRY_BLOCK_PTR))
1300 if (!JUMP_P (BB_END (src)))
1301 /* bb just falls through. */
1303 /* make sure there's only one successor */
1304 gcc_assert (single_succ_p (src));
1306 /* Find label in dest block. */
1307 label = block_label (dest);
1309 new_jump = emit_jump_insn_after (gen_jump (label),
1310 BB_END (src));
1311 barrier = emit_barrier_after (new_jump);
1312 JUMP_LABEL (new_jump) = label;
1313 LABEL_NUSES (label) += 1;
1314 src->il.rtl->footer = unlink_insn_chain (barrier, barrier);
1315 /* Mark edge as non-fallthru. */
1316 crossing_edges[i]->flags &= ~EDGE_FALLTHRU;
1317 } /* end: 'if (GET_CODE ... ' */
1318 } /* end: 'if (src && src->index...' */
1319 } /* end: 'if (dest && dest->index...' */
1320 } /* end: 'if (crossing_edges[i]...' */
1321 } /* end for loop */
1324 /* Find any bb's where the fall-through edge is a crossing edge (note that
1325 these bb's must also contain a conditional jump; we've already
1326 dealt with fall-through edges for blocks that didn't have a
1327 conditional jump in the call to add_labels_and_missing_jumps).
1328 Convert the fall-through edge to non-crossing edge by inserting a
1329 new bb to fall-through into. The new bb will contain an
1330 unconditional jump (crossing edge) to the original fall through
1331 destination. */
1333 static void
1334 fix_up_fall_thru_edges (void)
1336 basic_block cur_bb;
1337 basic_block new_bb;
1338 edge succ1;
1339 edge succ2;
1340 edge fall_thru;
1341 edge cond_jump = NULL;
1342 edge e;
1343 bool cond_jump_crosses;
1344 int invert_worked;
1345 rtx old_jump;
1346 rtx fall_thru_label;
1347 rtx barrier;
1349 FOR_EACH_BB (cur_bb)
1351 fall_thru = NULL;
1352 if (EDGE_COUNT (cur_bb->succs) > 0)
1353 succ1 = EDGE_SUCC (cur_bb, 0);
1354 else
1355 succ1 = NULL;
1357 if (EDGE_COUNT (cur_bb->succs) > 1)
1358 succ2 = EDGE_SUCC (cur_bb, 1);
1359 else
1360 succ2 = NULL;
1362 /* Find the fall-through edge. */
1364 if (succ1
1365 && (succ1->flags & EDGE_FALLTHRU))
1367 fall_thru = succ1;
1368 cond_jump = succ2;
1370 else if (succ2
1371 && (succ2->flags & EDGE_FALLTHRU))
1373 fall_thru = succ2;
1374 cond_jump = succ1;
1377 if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
1379 /* Check to see if the fall-thru edge is a crossing edge. */
1381 if (fall_thru->flags & EDGE_CROSSING)
1383 /* The fall_thru edge crosses; now check the cond jump edge, if
1384 it exists. */
1386 cond_jump_crosses = true;
1387 invert_worked = 0;
1388 old_jump = BB_END (cur_bb);
1390 /* Find the jump instruction, if there is one. */
1392 if (cond_jump)
1394 if (!(cond_jump->flags & EDGE_CROSSING))
1395 cond_jump_crosses = false;
1397 /* We know the fall-thru edge crosses; if the cond
1398 jump edge does NOT cross, and its destination is the
1399 next block in the bb order, invert the jump
1400 (i.e. fix it so the fall thru does not cross and
1401 the cond jump does). */
1403 if (!cond_jump_crosses
1404 && cur_bb->aux == cond_jump->dest)
1406 /* Find label in fall_thru block. We've already added
1407 any missing labels, so there must be one. */
1409 fall_thru_label = block_label (fall_thru->dest);
1411 if (old_jump && fall_thru_label)
1412 invert_worked = invert_jump (old_jump,
1413 fall_thru_label,0);
1414 if (invert_worked)
1416 fall_thru->flags &= ~EDGE_FALLTHRU;
1417 cond_jump->flags |= EDGE_FALLTHRU;
1418 update_br_prob_note (cur_bb);
1419 e = fall_thru;
1420 fall_thru = cond_jump;
1421 cond_jump = e;
1422 cond_jump->flags |= EDGE_CROSSING;
1423 fall_thru->flags &= ~EDGE_CROSSING;
1428 if (cond_jump_crosses || !invert_worked)
1430 /* This is the case where both edges out of the basic
1431 block are crossing edges. Here we will fix up the
1432 fall through edge. The jump edge will be taken care
1433 of later. */
1435 new_bb = force_nonfallthru (fall_thru);
1437 if (new_bb)
1439 new_bb->aux = cur_bb->aux;
1440 cur_bb->aux = new_bb;
1442 /* Make sure new fall-through bb is in same
1443 partition as bb it's falling through from. */
1445 BB_COPY_PARTITION (new_bb, cur_bb);
1446 single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
1449 /* Add barrier after new jump */
1451 if (new_bb)
1453 barrier = emit_barrier_after (BB_END (new_bb));
1454 new_bb->il.rtl->footer = unlink_insn_chain (barrier,
1455 barrier);
1457 else
1459 barrier = emit_barrier_after (BB_END (cur_bb));
1460 cur_bb->il.rtl->footer = unlink_insn_chain (barrier,
1461 barrier);
1469 /* This function checks the destination blockof a "crossing jump" to
1470 see if it has any crossing predecessors that begin with a code label
1471 and end with an unconditional jump. If so, it returns that predecessor
1472 block. (This is to avoid creating lots of new basic blocks that all
1473 contain unconditional jumps to the same destination). */
1475 static basic_block
1476 find_jump_block (basic_block jump_dest)
1478 basic_block source_bb = NULL;
1479 edge e;
1480 rtx insn;
1481 edge_iterator ei;
1483 FOR_EACH_EDGE (e, ei, jump_dest->preds)
1484 if (e->flags & EDGE_CROSSING)
1486 basic_block src = e->src;
1488 /* Check each predecessor to see if it has a label, and contains
1489 only one executable instruction, which is an unconditional jump.
1490 If so, we can use it. */
1492 if (LABEL_P (BB_HEAD (src)))
1493 for (insn = BB_HEAD (src);
1494 !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
1495 insn = NEXT_INSN (insn))
1497 if (INSN_P (insn)
1498 && insn == BB_END (src)
1499 && JUMP_P (insn)
1500 && !any_condjump_p (insn))
1502 source_bb = src;
1503 break;
1507 if (source_bb)
1508 break;
1511 return source_bb;
1514 /* Find all BB's with conditional jumps that are crossing edges;
1515 insert a new bb and make the conditional jump branch to the new
1516 bb instead (make the new bb same color so conditional branch won't
1517 be a 'crossing' edge). Insert an unconditional jump from the
1518 new bb to the original destination of the conditional jump. */
1520 static void
1521 fix_crossing_conditional_branches (void)
1523 basic_block cur_bb;
1524 basic_block new_bb;
1525 basic_block last_bb;
1526 basic_block dest;
1527 basic_block prev_bb;
1528 edge succ1;
1529 edge succ2;
1530 edge crossing_edge;
1531 edge new_edge;
1532 rtx old_jump;
1533 rtx set_src;
1534 rtx old_label = NULL_RTX;
1535 rtx new_label;
1536 rtx new_jump;
1537 rtx barrier;
1539 last_bb = EXIT_BLOCK_PTR->prev_bb;
1541 FOR_EACH_BB (cur_bb)
1543 crossing_edge = NULL;
1544 if (EDGE_COUNT (cur_bb->succs) > 0)
1545 succ1 = EDGE_SUCC (cur_bb, 0);
1546 else
1547 succ1 = NULL;
1549 if (EDGE_COUNT (cur_bb->succs) > 1)
1550 succ2 = EDGE_SUCC (cur_bb, 1);
1551 else
1552 succ2 = NULL;
1554 /* We already took care of fall-through edges, so only one successor
1555 can be a crossing edge. */
1557 if (succ1 && (succ1->flags & EDGE_CROSSING))
1558 crossing_edge = succ1;
1559 else if (succ2 && (succ2->flags & EDGE_CROSSING))
1560 crossing_edge = succ2;
1562 if (crossing_edge)
1564 old_jump = BB_END (cur_bb);
1566 /* Check to make sure the jump instruction is a
1567 conditional jump. */
1569 set_src = NULL_RTX;
1571 if (any_condjump_p (old_jump))
1573 if (GET_CODE (PATTERN (old_jump)) == SET)
1574 set_src = SET_SRC (PATTERN (old_jump));
1575 else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
1577 set_src = XVECEXP (PATTERN (old_jump), 0,0);
1578 if (GET_CODE (set_src) == SET)
1579 set_src = SET_SRC (set_src);
1580 else
1581 set_src = NULL_RTX;
1585 if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
1587 if (GET_CODE (XEXP (set_src, 1)) == PC)
1588 old_label = XEXP (set_src, 2);
1589 else if (GET_CODE (XEXP (set_src, 2)) == PC)
1590 old_label = XEXP (set_src, 1);
1592 /* Check to see if new bb for jumping to that dest has
1593 already been created; if so, use it; if not, create
1594 a new one. */
1596 new_bb = find_jump_block (crossing_edge->dest);
1598 if (new_bb)
1599 new_label = block_label (new_bb);
1600 else
1602 /* Create new basic block to be dest for
1603 conditional jump. */
1605 new_bb = create_basic_block (NULL, NULL, last_bb);
1606 new_bb->aux = last_bb->aux;
1607 last_bb->aux = new_bb;
1608 prev_bb = last_bb;
1609 last_bb = new_bb;
1611 /* Update register liveness information. */
1613 new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
1614 new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
1615 COPY_REG_SET (new_bb->il.rtl->global_live_at_end,
1616 prev_bb->il.rtl->global_live_at_end);
1617 COPY_REG_SET (new_bb->il.rtl->global_live_at_start,
1618 prev_bb->il.rtl->global_live_at_end);
1620 /* Put appropriate instructions in new bb. */
1622 new_label = gen_label_rtx ();
1623 emit_label_before (new_label, BB_HEAD (new_bb));
1624 BB_HEAD (new_bb) = new_label;
1626 if (GET_CODE (old_label) == LABEL_REF)
1628 old_label = JUMP_LABEL (old_jump);
1629 new_jump = emit_jump_insn_after (gen_jump
1630 (old_label),
1631 BB_END (new_bb));
1633 else
1635 gcc_assert (HAVE_return
1636 && GET_CODE (old_label) == RETURN);
1637 new_jump = emit_jump_insn_after (gen_return (),
1638 BB_END (new_bb));
1641 barrier = emit_barrier_after (new_jump);
1642 JUMP_LABEL (new_jump) = old_label;
1643 new_bb->il.rtl->footer = unlink_insn_chain (barrier,
1644 barrier);
1646 /* Make sure new bb is in same partition as source
1647 of conditional branch. */
1648 BB_COPY_PARTITION (new_bb, cur_bb);
1651 /* Make old jump branch to new bb. */
1653 redirect_jump (old_jump, new_label, 0);
1655 /* Remove crossing_edge as predecessor of 'dest'. */
1657 dest = crossing_edge->dest;
1659 redirect_edge_succ (crossing_edge, new_bb);
1661 /* Make a new edge from new_bb to old dest; new edge
1662 will be a successor for new_bb and a predecessor
1663 for 'dest'. */
1665 if (EDGE_COUNT (new_bb->succs) == 0)
1666 new_edge = make_edge (new_bb, dest, 0);
1667 else
1668 new_edge = EDGE_SUCC (new_bb, 0);
1670 crossing_edge->flags &= ~EDGE_CROSSING;
1671 new_edge->flags |= EDGE_CROSSING;
1677 /* Find any unconditional branches that cross between hot and cold
1678 sections. Convert them into indirect jumps instead. */
1680 static void
1681 fix_crossing_unconditional_branches (void)
1683 basic_block cur_bb;
1684 rtx last_insn;
1685 rtx label;
1686 rtx label_addr;
1687 rtx indirect_jump_sequence;
1688 rtx jump_insn = NULL_RTX;
1689 rtx new_reg;
1690 rtx cur_insn;
1691 edge succ;
1693 FOR_EACH_BB (cur_bb)
1695 last_insn = BB_END (cur_bb);
1697 if (EDGE_COUNT (cur_bb->succs) < 1)
1698 continue;
1700 succ = EDGE_SUCC (cur_bb, 0);
1702 /* Check to see if bb ends in a crossing (unconditional) jump. At
1703 this point, no crossing jumps should be conditional. */
1705 if (JUMP_P (last_insn)
1706 && (succ->flags & EDGE_CROSSING))
1708 rtx label2, table;
1710 gcc_assert (!any_condjump_p (last_insn));
1712 /* Make sure the jump is not already an indirect or table jump. */
1714 if (!computed_jump_p (last_insn)
1715 && !tablejump_p (last_insn, &label2, &table))
1717 /* We have found a "crossing" unconditional branch. Now
1718 we must convert it to an indirect jump. First create
1719 reference of label, as target for jump. */
1721 label = JUMP_LABEL (last_insn);
1722 label_addr = gen_rtx_LABEL_REF (Pmode, label);
1723 LABEL_NUSES (label) += 1;
1725 /* Get a register to use for the indirect jump. */
1727 new_reg = gen_reg_rtx (Pmode);
1729 /* Generate indirect the jump sequence. */
1731 start_sequence ();
1732 emit_move_insn (new_reg, label_addr);
1733 emit_indirect_jump (new_reg);
1734 indirect_jump_sequence = get_insns ();
1735 end_sequence ();
1737 /* Make sure every instruction in the new jump sequence has
1738 its basic block set to be cur_bb. */
1740 for (cur_insn = indirect_jump_sequence; cur_insn;
1741 cur_insn = NEXT_INSN (cur_insn))
1743 if (!BARRIER_P (cur_insn))
1744 BLOCK_FOR_INSN (cur_insn) = cur_bb;
1745 if (JUMP_P (cur_insn))
1746 jump_insn = cur_insn;
1749 /* Insert the new (indirect) jump sequence immediately before
1750 the unconditional jump, then delete the unconditional jump. */
1752 emit_insn_before (indirect_jump_sequence, last_insn);
1753 delete_insn (last_insn);
1755 /* Make BB_END for cur_bb be the jump instruction (NOT the
1756 barrier instruction at the end of the sequence...). */
1758 BB_END (cur_bb) = jump_insn;
1764 /* Add REG_CROSSING_JUMP note to all crossing jump insns. */
1766 static void
1767 add_reg_crossing_jump_notes (void)
1769 basic_block bb;
1770 edge e;
1771 edge_iterator ei;
1773 FOR_EACH_BB (bb)
1774 FOR_EACH_EDGE (e, ei, bb->succs)
1775 if ((e->flags & EDGE_CROSSING)
1776 && JUMP_P (BB_END (e->src)))
1777 REG_NOTES (BB_END (e->src)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
1778 NULL_RTX,
1779 REG_NOTES (BB_END
1780 (e->src)));
1783 /* Hot and cold basic blocks are partitioned and put in separate
1784 sections of the .o file, to reduce paging and improve cache
1785 performance (hopefully). This can result in bits of code from the
1786 same function being widely separated in the .o file. However this
1787 is not obvious to the current bb structure. Therefore we must take
1788 care to ensure that: 1). There are no fall_thru edges that cross
1789 between sections; 2). For those architectures which have "short"
1790 conditional branches, all conditional branches that attempt to
1791 cross between sections are converted to unconditional branches;
1792 and, 3). For those architectures which have "short" unconditional
1793 branches, all unconditional branches that attempt to cross between
1794 sections are converted to indirect jumps.
1796 The code for fixing up fall_thru edges that cross between hot and
1797 cold basic blocks does so by creating new basic blocks containing
1798 unconditional branches to the appropriate label in the "other"
1799 section. The new basic block is then put in the same (hot or cold)
1800 section as the original conditional branch, and the fall_thru edge
1801 is modified to fall into the new basic block instead. By adding
1802 this level of indirection we end up with only unconditional branches
1803 crossing between hot and cold sections.
1805 Conditional branches are dealt with by adding a level of indirection.
1806 A new basic block is added in the same (hot/cold) section as the
1807 conditional branch, and the conditional branch is retargeted to the
1808 new basic block. The new basic block contains an unconditional branch
1809 to the original target of the conditional branch (in the other section).
1811 Unconditional branches are dealt with by converting them into
1812 indirect jumps. */
1814 static void
1815 fix_edges_for_rarely_executed_code (edge *crossing_edges,
1816 int n_crossing_edges)
1818 /* Make sure the source of any crossing edge ends in a jump and the
1819 destination of any crossing edge has a label. */
1821 add_labels_and_missing_jumps (crossing_edges, n_crossing_edges);
1823 /* Convert all crossing fall_thru edges to non-crossing fall
1824 thrus to unconditional jumps (that jump to the original fall
1825 thru dest). */
1827 fix_up_fall_thru_edges ();
1829 /* If the architecture does not have conditional branches that can
1830 span all of memory, convert crossing conditional branches into
1831 crossing unconditional branches. */
1833 if (!HAS_LONG_COND_BRANCH)
1834 fix_crossing_conditional_branches ();
1836 /* If the architecture does not have unconditional branches that
1837 can span all of memory, convert crossing unconditional branches
1838 into indirect jumps. Since adding an indirect jump also adds
1839 a new register usage, update the register usage information as
1840 well. */
1842 if (!HAS_LONG_UNCOND_BRANCH)
1844 fix_crossing_unconditional_branches ();
1845 reg_scan (get_insns (), max_reg_num ());
1848 add_reg_crossing_jump_notes ();
1851 /* Verify, in the basic block chain, that there is at most one switch
1852 between hot/cold partitions. This is modelled on
1853 rtl_verify_flow_info_1, but it cannot go inside that function
1854 because this condition will not be true until after
1855 reorder_basic_blocks is called. */
1857 static void
1858 verify_hot_cold_block_grouping (void)
1860 basic_block bb;
1861 int err = 0;
1862 bool switched_sections = false;
1863 int current_partition = 0;
1865 FOR_EACH_BB (bb)
1867 if (!current_partition)
1868 current_partition = BB_PARTITION (bb);
1869 if (BB_PARTITION (bb) != current_partition)
1871 if (switched_sections)
1873 error ("multiple hot/cold transitions found (bb %i)",
1874 bb->index);
1875 err = 1;
1877 else
1879 switched_sections = true;
1880 current_partition = BB_PARTITION (bb);
1885 gcc_assert(!err);
1888 /* Reorder basic blocks. The main entry point to this file. FLAGS is
1889 the set of flags to pass to cfg_layout_initialize(). */
1891 void
1892 reorder_basic_blocks (unsigned int flags)
1894 int n_traces;
1895 int i;
1896 struct trace *traces;
1898 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
1899 return;
1901 if (targetm.cannot_modify_jumps_p ())
1902 return;
1904 cfg_layout_initialize (flags);
1906 set_edge_can_fallthru_flag ();
1907 mark_dfs_back_edges ();
1909 /* We are estimating the length of uncond jump insn only once since the code
1910 for getting the insn length always returns the minimal length now. */
1911 if (uncond_jump_length == 0)
1912 uncond_jump_length = get_uncond_jump_length ();
1914 /* We need to know some information for each basic block. */
1915 array_size = GET_ARRAY_SIZE (last_basic_block);
1916 bbd = XNEWVEC (bbro_basic_block_data, array_size);
1917 for (i = 0; i < array_size; i++)
1919 bbd[i].start_of_trace = -1;
1920 bbd[i].in_trace = -1;
1921 bbd[i].end_of_trace = -1;
1922 bbd[i].heap = NULL;
1923 bbd[i].node = NULL;
1926 traces = XNEWVEC (struct trace, n_basic_blocks);
1927 n_traces = 0;
1928 find_traces (&n_traces, traces);
1929 connect_traces (n_traces, traces);
1930 FREE (traces);
1931 FREE (bbd);
1933 if (dump_file)
1934 dump_flow_info (dump_file, dump_flags);
1936 cfg_layout_finalize ();
1937 if (flag_reorder_blocks_and_partition)
1938 verify_hot_cold_block_grouping ();
1941 /* Determine which partition the first basic block in the function
1942 belongs to, then find the first basic block in the current function
1943 that belongs to a different section, and insert a
1944 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
1945 instruction stream. When writing out the assembly code,
1946 encountering this note will make the compiler switch between the
1947 hot and cold text sections. */
1949 static void
1950 insert_section_boundary_note (void)
1952 basic_block bb;
1953 rtx new_note;
1954 int first_partition = 0;
1956 if (flag_reorder_blocks_and_partition)
1957 FOR_EACH_BB (bb)
1959 if (!first_partition)
1960 first_partition = BB_PARTITION (bb);
1961 if (BB_PARTITION (bb) != first_partition)
1963 new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS,
1964 BB_HEAD (bb));
1965 break;
1970 /* Duplicate the blocks containing computed gotos. This basically unfactors
1971 computed gotos that were factored early on in the compilation process to
1972 speed up edge based data flow. We used to not unfactoring them again,
1973 which can seriously pessimize code with many computed jumps in the source
1974 code, such as interpreters. See e.g. PR15242. */
1976 static bool
1977 gate_duplicate_computed_gotos (void)
1979 return (optimize > 0 && flag_expensive_optimizations && !optimize_size);
1983 static unsigned int
1984 duplicate_computed_gotos (void)
1986 basic_block bb, new_bb;
1987 bitmap candidates;
1988 int max_size;
1990 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
1991 return 0;
1993 if (targetm.cannot_modify_jumps_p ())
1994 return 0;
1996 cfg_layout_initialize (0);
1998 /* We are estimating the length of uncond jump insn only once
1999 since the code for getting the insn length always returns
2000 the minimal length now. */
2001 if (uncond_jump_length == 0)
2002 uncond_jump_length = get_uncond_jump_length ();
2004 max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
2005 candidates = BITMAP_ALLOC (NULL);
2007 /* Look for blocks that end in a computed jump, and see if such blocks
2008 are suitable for unfactoring. If a block is a candidate for unfactoring,
2009 mark it in the candidates. */
2010 FOR_EACH_BB (bb)
2012 rtx insn;
2013 edge e;
2014 edge_iterator ei;
2015 int size, all_flags;
2017 /* Build the reorder chain for the original order of blocks. */
2018 if (bb->next_bb != EXIT_BLOCK_PTR)
2019 bb->aux = bb->next_bb;
2021 /* Obviously the block has to end in a computed jump. */
2022 if (!computed_jump_p (BB_END (bb)))
2023 continue;
2025 /* Only consider blocks that can be duplicated. */
2026 if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX)
2027 || !can_duplicate_block_p (bb))
2028 continue;
2030 /* Make sure that the block is small enough. */
2031 size = 0;
2032 FOR_BB_INSNS (bb, insn)
2033 if (INSN_P (insn))
2035 size += get_attr_min_length (insn);
2036 if (size > max_size)
2037 break;
2039 if (size > max_size)
2040 continue;
2042 /* Final check: there must not be any incoming abnormal edges. */
2043 all_flags = 0;
2044 FOR_EACH_EDGE (e, ei, bb->preds)
2045 all_flags |= e->flags;
2046 if (all_flags & EDGE_COMPLEX)
2047 continue;
2049 bitmap_set_bit (candidates, bb->index);
2052 /* Nothing to do if there is no computed jump here. */
2053 if (bitmap_empty_p (candidates))
2054 goto done;
2056 /* Duplicate computed gotos. */
2057 FOR_EACH_BB (bb)
2059 if (bb->il.rtl->visited)
2060 continue;
2062 bb->il.rtl->visited = 1;
2064 /* BB must have one outgoing edge. That edge must not lead to
2065 the exit block or the next block.
2066 The destination must have more than one predecessor. */
2067 if (!single_succ_p (bb)
2068 || single_succ (bb) == EXIT_BLOCK_PTR
2069 || single_succ (bb) == bb->next_bb
2070 || single_pred_p (single_succ (bb)))
2071 continue;
2073 /* The successor block has to be a duplication candidate. */
2074 if (!bitmap_bit_p (candidates, single_succ (bb)->index))
2075 continue;
2077 new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
2078 new_bb->aux = bb->aux;
2079 bb->aux = new_bb;
2080 new_bb->il.rtl->visited = 1;
2083 done:
2084 cfg_layout_finalize ();
2086 BITMAP_FREE (candidates);
2087 return 0;
2090 struct tree_opt_pass pass_duplicate_computed_gotos =
2092 "compgotos", /* name */
2093 gate_duplicate_computed_gotos, /* gate */
2094 duplicate_computed_gotos, /* execute */
2095 NULL, /* sub */
2096 NULL, /* next */
2097 0, /* static_pass_number */
2098 TV_REORDER_BLOCKS, /* tv_id */
2099 0, /* properties_required */
2100 0, /* properties_provided */
2101 0, /* properties_destroyed */
2102 0, /* todo_flags_start */
2103 TODO_dump_func, /* todo_flags_finish */
2104 0 /* letter */
2108 /* This function is the main 'entrance' for the optimization that
2109 partitions hot and cold basic blocks into separate sections of the
2110 .o file (to improve performance and cache locality). Ideally it
2111 would be called after all optimizations that rearrange the CFG have
2112 been called. However part of this optimization may introduce new
2113 register usage, so it must be called before register allocation has
2114 occurred. This means that this optimization is actually called
2115 well before the optimization that reorders basic blocks (see
2116 function above).
2118 This optimization checks the feedback information to determine
2119 which basic blocks are hot/cold, updates flags on the basic blocks
2120 to indicate which section they belong in. This information is
2121 later used for writing out sections in the .o file. Because hot
2122 and cold sections can be arbitrarily large (within the bounds of
2123 memory), far beyond the size of a single function, it is necessary
2124 to fix up all edges that cross section boundaries, to make sure the
2125 instructions used can actually span the required distance. The
2126 fixes are described below.
2128 Fall-through edges must be changed into jumps; it is not safe or
2129 legal to fall through across a section boundary. Whenever a
2130 fall-through edge crossing a section boundary is encountered, a new
2131 basic block is inserted (in the same section as the fall-through
2132 source), and the fall through edge is redirected to the new basic
2133 block. The new basic block contains an unconditional jump to the
2134 original fall-through target. (If the unconditional jump is
2135 insufficient to cross section boundaries, that is dealt with a
2136 little later, see below).
2138 In order to deal with architectures that have short conditional
2139 branches (which cannot span all of memory) we take any conditional
2140 jump that attempts to cross a section boundary and add a level of
2141 indirection: it becomes a conditional jump to a new basic block, in
2142 the same section. The new basic block contains an unconditional
2143 jump to the original target, in the other section.
2145 For those architectures whose unconditional branch is also
2146 incapable of reaching all of memory, those unconditional jumps are
2147 converted into indirect jumps, through a register.
2149 IMPORTANT NOTE: This optimization causes some messy interactions
2150 with the cfg cleanup optimizations; those optimizations want to
2151 merge blocks wherever possible, and to collapse indirect jump
2152 sequences (change "A jumps to B jumps to C" directly into "A jumps
2153 to C"). Those optimizations can undo the jump fixes that
2154 partitioning is required to make (see above), in order to ensure
2155 that jumps attempting to cross section boundaries are really able
2156 to cover whatever distance the jump requires (on many architectures
2157 conditional or unconditional jumps are not able to reach all of
2158 memory). Therefore tests have to be inserted into each such
2159 optimization to make sure that it does not undo stuff necessary to
2160 cross partition boundaries. This would be much less of a problem
2161 if we could perform this optimization later in the compilation, but
2162 unfortunately the fact that we may need to create indirect jumps
2163 (through registers) requires that this optimization be performed
2164 before register allocation. */
2166 static void
2167 partition_hot_cold_basic_blocks (void)
2169 basic_block cur_bb;
2170 edge *crossing_edges;
2171 int n_crossing_edges;
2172 int max_edges = 2 * last_basic_block;
2174 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
2175 return;
2177 crossing_edges = XCNEWVEC (edge, max_edges);
2179 cfg_layout_initialize (0);
2181 FOR_EACH_BB (cur_bb)
2182 if (cur_bb->index >= NUM_FIXED_BLOCKS
2183 && cur_bb->next_bb->index >= NUM_FIXED_BLOCKS)
2184 cur_bb->aux = cur_bb->next_bb;
2186 find_rarely_executed_basic_blocks_and_crossing_edges (crossing_edges,
2187 &n_crossing_edges,
2188 &max_edges);
2190 if (n_crossing_edges > 0)
2191 fix_edges_for_rarely_executed_code (crossing_edges, n_crossing_edges);
2193 free (crossing_edges);
2195 cfg_layout_finalize ();
2198 static bool
2199 gate_handle_reorder_blocks (void)
2201 return (optimize > 0);
2205 /* Reorder basic blocks. */
2206 static unsigned int
2207 rest_of_handle_reorder_blocks (void)
2209 bool changed;
2210 unsigned int liveness_flags;
2212 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2213 splitting possibly introduced more crossjumping opportunities. */
2214 liveness_flags = (!HAVE_conditional_execution ? CLEANUP_UPDATE_LIFE : 0);
2215 changed = cleanup_cfg (CLEANUP_EXPENSIVE | liveness_flags);
2217 if (flag_sched2_use_traces && flag_schedule_insns_after_reload)
2219 timevar_push (TV_TRACER);
2220 tracer (liveness_flags);
2221 timevar_pop (TV_TRACER);
2224 if (flag_reorder_blocks || flag_reorder_blocks_and_partition)
2225 reorder_basic_blocks (liveness_flags);
2226 if (flag_reorder_blocks || flag_reorder_blocks_and_partition
2227 || (flag_sched2_use_traces && flag_schedule_insns_after_reload))
2228 changed |= cleanup_cfg (CLEANUP_EXPENSIVE | liveness_flags);
2230 /* On conditional execution targets we can not update the life cheaply, so
2231 we deffer the updating to after both cleanups. This may lose some cases
2232 but should not be terribly bad. */
2233 if (changed && HAVE_conditional_execution)
2234 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
2235 PROP_DEATH_NOTES);
2237 /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */
2238 insert_section_boundary_note ();
2239 return 0;
2242 struct tree_opt_pass pass_reorder_blocks =
2244 "bbro", /* name */
2245 gate_handle_reorder_blocks, /* gate */
2246 rest_of_handle_reorder_blocks, /* execute */
2247 NULL, /* sub */
2248 NULL, /* next */
2249 0, /* static_pass_number */
2250 TV_REORDER_BLOCKS, /* tv_id */
2251 0, /* properties_required */
2252 0, /* properties_provided */
2253 0, /* properties_destroyed */
2254 0, /* todo_flags_start */
2255 TODO_dump_func, /* todo_flags_finish */
2256 'B' /* letter */
2259 static bool
2260 gate_handle_partition_blocks (void)
2262 /* The optimization to partition hot/cold basic blocks into separate
2263 sections of the .o file does not work well with linkonce or with
2264 user defined section attributes. Don't call it if either case
2265 arises. */
2267 return (flag_reorder_blocks_and_partition
2268 && !DECL_ONE_ONLY (current_function_decl)
2269 && !user_defined_section_attribute);
2272 /* Partition hot and cold basic blocks. */
2273 static unsigned int
2274 rest_of_handle_partition_blocks (void)
2276 no_new_pseudos = 0;
2277 partition_hot_cold_basic_blocks ();
2278 allocate_reg_life_data ();
2279 update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
2280 PROP_LOG_LINKS | PROP_REG_INFO | PROP_DEATH_NOTES);
2281 no_new_pseudos = 1;
2282 return 0;
2285 struct tree_opt_pass pass_partition_blocks =
2287 "bbpart", /* name */
2288 gate_handle_partition_blocks, /* gate */
2289 rest_of_handle_partition_blocks, /* execute */
2290 NULL, /* sub */
2291 NULL, /* next */
2292 0, /* static_pass_number */
2293 TV_REORDER_BLOCKS, /* tv_id */
2294 0, /* properties_required */
2295 0, /* properties_provided */
2296 0, /* properties_destroyed */
2297 0, /* todo_flags_start */
2298 TODO_dump_func, /* todo_flags_finish */
2299 0 /* letter */