1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011,
3 2012 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
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.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
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.
27
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.
35
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.
49
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.
58
59
60 References:
61
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
65
66 */
67
68 #include "config.h"
69 #include "system.h"
70 #include "coretypes.h"
71 #include "tm.h"
72 #include "rtl.h"
73 #include "regs.h"
74 #include "flags.h"
75 #include "timevar.h"
76 #include "output.h"
77 #include "cfglayout.h"
78 #include "fibheap.h"
79 #include "target.h"
80 #include "function.h"
81 #include "tm_p.h"
82 #include "obstack.h"
83 #include "expr.h"
84 #include "params.h"
85 #include "diagnostic-core.h"
86 #include "toplev.h" /* user_defined_section_attribute */
87 #include "tree-pass.h"
88 #include "df.h"
89 #include "bb-reorder.h"
90 #include "except.h"
91
92 /* The number of rounds. In most cases there will only be 4 rounds, but
93 when partitioning hot and cold basic blocks into separate sections of
94 the .o file there will be an extra round.*/
95 #define N_ROUNDS 5
96
97 /* Stubs in case we don't have a return insn.
98 We have to check at runtime too, not only compiletime. */
99
100 #ifndef HAVE_return
101 #define HAVE_return 0
102 #define gen_return() NULL_RTX
103 #endif
104
105
106 struct target_bb_reorder default_target_bb_reorder;
107 #if SWITCHABLE_TARGET
108 struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder;
109 #endif
110
111 #define uncond_jump_length \
112 (this_target_bb_reorder->x_uncond_jump_length)
113
114 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
115 static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
116
117 /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
118 static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
119
120 /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
121 block the edge destination is not duplicated while connecting traces. */
122 #define DUPLICATION_THRESHOLD 100
123
124 /* Structure to hold needed information for each basic block. */
125 typedef struct bbro_basic_block_data_def
126 {
127 /* Which trace is the bb start of (-1 means it is not a start of a trace). */
128 int start_of_trace;
129
130 /* Which trace is the bb end of (-1 means it is not an end of a trace). */
131 int end_of_trace;
132
133 /* Which trace is the bb in? */
134 int in_trace;
135
136 /* Which heap is BB in (if any)? */
137 fibheap_t heap;
138
139 /* Which heap node is BB in (if any)? */
140 fibnode_t node;
141 } bbro_basic_block_data;
142
143 /* The current size of the following dynamic array. */
144 static int array_size;
145
146 /* The array which holds needed information for basic blocks. */
147 static bbro_basic_block_data *bbd;
148
149 /* To avoid frequent reallocation the size of arrays is greater than needed,
150 the number of elements is (not less than) 1.25 * size_wanted. */
151 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
152
153 /* Free the memory and set the pointer to NULL. */
154 #define FREE(P) (gcc_assert (P), free (P), P = 0)
155
156 /* Structure for holding information about a trace. */
157 struct trace
158 {
159 /* First and last basic block of the trace. */
160 basic_block first, last;
161
162 /* The round of the STC creation which this trace was found in. */
163 int round;
164
165 /* The length (i.e. the number of basic blocks) of the trace. */
166 int length;
167 };
168
169 /* Maximum frequency and count of one of the entry blocks. */
170 static int max_entry_frequency;
171 static gcov_type max_entry_count;
172
173 /* Local function prototypes. */
174 static void find_traces (int *, struct trace *);
175 static basic_block rotate_loop (edge, struct trace *, int);
176 static void mark_bb_visited (basic_block, int);
177 static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
178 int, fibheap_t *, int);
179 static basic_block copy_bb (basic_block, edge, basic_block, int);
180 static fibheapkey_t bb_to_key (basic_block);
181 static bool better_edge_p (const_basic_block, const_edge, int, int, int, int, const_edge);
182 static void connect_traces (int, struct trace *);
183 static bool copy_bb_p (const_basic_block, int);
184 static bool push_to_next_round_p (const_basic_block, int, int, int, gcov_type);
185
186 /* Check to see if bb should be pushed into the next round of trace
187 collections or not. Reasons for pushing the block forward are 1).
188 If the block is cold, we are doing partitioning, and there will be
189 another round (cold partition blocks are not supposed to be
190 collected into traces until the very last round); or 2). There will
191 be another round, and the basic block is not "hot enough" for the
192 current round of trace collection. */
193
194 static bool
push_to_next_round_p(const_basic_block bb,int round,int number_of_rounds,int exec_th,gcov_type count_th)195 push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
196 int exec_th, gcov_type count_th)
197 {
198 bool there_exists_another_round;
199 bool block_not_hot_enough;
200
201 there_exists_another_round = round < number_of_rounds - 1;
202
203 block_not_hot_enough = (bb->frequency < exec_th
204 || bb->count < count_th
205 || probably_never_executed_bb_p (bb));
206
207 if (there_exists_another_round
208 && block_not_hot_enough)
209 return true;
210 else
211 return false;
212 }
213
214 /* Find the traces for Software Trace Cache. Chain each trace through
215 RBI()->next. Store the number of traces to N_TRACES and description of
216 traces to TRACES. */
217
218 static void
find_traces(int * n_traces,struct trace * traces)219 find_traces (int *n_traces, struct trace *traces)
220 {
221 int i;
222 int number_of_rounds;
223 edge e;
224 edge_iterator ei;
225 fibheap_t heap;
226
227 /* Add one extra round of trace collection when partitioning hot/cold
228 basic blocks into separate sections. The last round is for all the
229 cold blocks (and ONLY the cold blocks). */
230
231 number_of_rounds = N_ROUNDS - 1;
232
233 /* Insert entry points of function into heap. */
234 heap = fibheap_new ();
235 max_entry_frequency = 0;
236 max_entry_count = 0;
237 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
238 {
239 bbd[e->dest->index].heap = heap;
240 bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
241 e->dest);
242 if (e->dest->frequency > max_entry_frequency)
243 max_entry_frequency = e->dest->frequency;
244 if (e->dest->count > max_entry_count)
245 max_entry_count = e->dest->count;
246 }
247
248 /* Find the traces. */
249 for (i = 0; i < number_of_rounds; i++)
250 {
251 gcov_type count_threshold;
252
253 if (dump_file)
254 fprintf (dump_file, "STC - round %d\n", i + 1);
255
256 if (max_entry_count < INT_MAX / 1000)
257 count_threshold = max_entry_count * exec_threshold[i] / 1000;
258 else
259 count_threshold = max_entry_count / 1000 * exec_threshold[i];
260
261 find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
262 max_entry_frequency * exec_threshold[i] / 1000,
263 count_threshold, traces, n_traces, i, &heap,
264 number_of_rounds);
265 }
266 fibheap_delete (heap);
267
268 if (dump_file)
269 {
270 for (i = 0; i < *n_traces; i++)
271 {
272 basic_block bb;
273 fprintf (dump_file, "Trace %d (round %d): ", i + 1,
274 traces[i].round + 1);
275 for (bb = traces[i].first; bb != traces[i].last; bb = (basic_block) bb->aux)
276 fprintf (dump_file, "%d [%d] ", bb->index, bb->frequency);
277 fprintf (dump_file, "%d [%d]\n", bb->index, bb->frequency);
278 }
279 fflush (dump_file);
280 }
281 }
282
283 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
284 (with sequential number TRACE_N). */
285
286 static basic_block
rotate_loop(edge back_edge,struct trace * trace,int trace_n)287 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
288 {
289 basic_block bb;
290
291 /* Information about the best end (end after rotation) of the loop. */
292 basic_block best_bb = NULL;
293 edge best_edge = NULL;
294 int best_freq = -1;
295 gcov_type best_count = -1;
296 /* The best edge is preferred when its destination is not visited yet
297 or is a start block of some trace. */
298 bool is_preferred = false;
299
300 /* Find the most frequent edge that goes out from current trace. */
301 bb = back_edge->dest;
302 do
303 {
304 edge e;
305 edge_iterator ei;
306
307 FOR_EACH_EDGE (e, ei, bb->succs)
308 if (e->dest != EXIT_BLOCK_PTR
309 && e->dest->il.rtl->visited != trace_n
310 && (e->flags & EDGE_CAN_FALLTHRU)
311 && !(e->flags & EDGE_COMPLEX))
312 {
313 if (is_preferred)
314 {
315 /* The best edge is preferred. */
316 if (!e->dest->il.rtl->visited
317 || bbd[e->dest->index].start_of_trace >= 0)
318 {
319 /* The current edge E is also preferred. */
320 int freq = EDGE_FREQUENCY (e);
321 if (freq > best_freq || e->count > best_count)
322 {
323 best_freq = freq;
324 best_count = e->count;
325 best_edge = e;
326 best_bb = bb;
327 }
328 }
329 }
330 else
331 {
332 if (!e->dest->il.rtl->visited
333 || bbd[e->dest->index].start_of_trace >= 0)
334 {
335 /* The current edge E is preferred. */
336 is_preferred = true;
337 best_freq = EDGE_FREQUENCY (e);
338 best_count = e->count;
339 best_edge = e;
340 best_bb = bb;
341 }
342 else
343 {
344 int freq = EDGE_FREQUENCY (e);
345 if (!best_edge || freq > best_freq || e->count > best_count)
346 {
347 best_freq = freq;
348 best_count = e->count;
349 best_edge = e;
350 best_bb = bb;
351 }
352 }
353 }
354 }
355 bb = (basic_block) bb->aux;
356 }
357 while (bb != back_edge->dest);
358
359 if (best_bb)
360 {
361 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
362 the trace. */
363 if (back_edge->dest == trace->first)
364 {
365 trace->first = (basic_block) best_bb->aux;
366 }
367 else
368 {
369 basic_block prev_bb;
370
371 for (prev_bb = trace->first;
372 prev_bb->aux != back_edge->dest;
373 prev_bb = (basic_block) prev_bb->aux)
374 ;
375 prev_bb->aux = best_bb->aux;
376
377 /* Try to get rid of uncond jump to cond jump. */
378 if (single_succ_p (prev_bb))
379 {
380 basic_block header = single_succ (prev_bb);
381
382 /* Duplicate HEADER if it is a small block containing cond jump
383 in the end. */
384 if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
385 && !find_reg_note (BB_END (header), REG_CROSSING_JUMP,
386 NULL_RTX))
387 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
388 }
389 }
390 }
391 else
392 {
393 /* We have not found suitable loop tail so do no rotation. */
394 best_bb = back_edge->src;
395 }
396 best_bb->aux = NULL;
397 return best_bb;
398 }
399
400 /* This function marks BB that it was visited in trace number TRACE. */
401
402 static void
mark_bb_visited(basic_block bb,int trace)403 mark_bb_visited (basic_block bb, int trace)
404 {
405 bb->il.rtl->visited = trace;
406 if (bbd[bb->index].heap)
407 {
408 fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
409 bbd[bb->index].heap = NULL;
410 bbd[bb->index].node = NULL;
411 }
412 }
413
414 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
415 not include basic blocks their probability is lower than BRANCH_TH or their
416 frequency is lower than EXEC_TH into traces (or count is lower than
417 COUNT_TH). It stores the new traces into TRACES and modifies the number of
418 traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
419 expects that starting basic blocks are in *HEAP and at the end it deletes
420 *HEAP and stores starting points for the next round into new *HEAP. */
421
422 static void
find_traces_1_round(int branch_th,int exec_th,gcov_type count_th,struct trace * traces,int * n_traces,int round,fibheap_t * heap,int number_of_rounds)423 find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
424 struct trace *traces, int *n_traces, int round,
425 fibheap_t *heap, int number_of_rounds)
426 {
427 /* Heap for discarded basic blocks which are possible starting points for
428 the next round. */
429 fibheap_t new_heap = fibheap_new ();
430
431 while (!fibheap_empty (*heap))
432 {
433 basic_block bb;
434 struct trace *trace;
435 edge best_edge, e;
436 fibheapkey_t key;
437 edge_iterator ei;
438
439 bb = (basic_block) fibheap_extract_min (*heap);
440 bbd[bb->index].heap = NULL;
441 bbd[bb->index].node = NULL;
442
443 if (dump_file)
444 fprintf (dump_file, "Getting bb %d\n", bb->index);
445
446 /* If the BB's frequency is too low send BB to the next round. When
447 partitioning hot/cold blocks into separate sections, make sure all
448 the cold blocks (and ONLY the cold blocks) go into the (extra) final
449 round. */
450
451 if (push_to_next_round_p (bb, round, number_of_rounds, exec_th,
452 count_th))
453 {
454 int key = bb_to_key (bb);
455 bbd[bb->index].heap = new_heap;
456 bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
457
458 if (dump_file)
459 fprintf (dump_file,
460 " Possible start point of next round: %d (key: %d)\n",
461 bb->index, key);
462 continue;
463 }
464
465 trace = traces + *n_traces;
466 trace->first = bb;
467 trace->round = round;
468 trace->length = 0;
469 bbd[bb->index].in_trace = *n_traces;
470 (*n_traces)++;
471
472 do
473 {
474 int prob, freq;
475 bool ends_in_call;
476
477 /* The probability and frequency of the best edge. */
478 int best_prob = INT_MIN / 2;
479 int best_freq = INT_MIN / 2;
480
481 best_edge = NULL;
482 mark_bb_visited (bb, *n_traces);
483 trace->length++;
484
485 if (dump_file)
486 fprintf (dump_file, "Basic block %d was visited in trace %d\n",
487 bb->index, *n_traces - 1);
488
489 ends_in_call = block_ends_with_call_p (bb);
490
491 /* Select the successor that will be placed after BB. */
492 FOR_EACH_EDGE (e, ei, bb->succs)
493 {
494 gcc_assert (!(e->flags & EDGE_FAKE));
495
496 if (e->dest == EXIT_BLOCK_PTR)
497 continue;
498
499 if (e->dest->il.rtl->visited
500 && e->dest->il.rtl->visited != *n_traces)
501 continue;
502
503 if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
504 continue;
505
506 prob = e->probability;
507 freq = e->dest->frequency;
508
509 /* The only sensible preference for a call instruction is the
510 fallthru edge. Don't bother selecting anything else. */
511 if (ends_in_call)
512 {
513 if (e->flags & EDGE_CAN_FALLTHRU)
514 {
515 best_edge = e;
516 best_prob = prob;
517 best_freq = freq;
518 }
519 continue;
520 }
521
522 /* Edge that cannot be fallthru or improbable or infrequent
523 successor (i.e. it is unsuitable successor). */
524 if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
525 || prob < branch_th || EDGE_FREQUENCY (e) < exec_th
526 || e->count < count_th)
527 continue;
528
529 /* If partitioning hot/cold basic blocks, don't consider edges
530 that cross section boundaries. */
531
532 if (better_edge_p (bb, e, prob, freq, best_prob, best_freq,
533 best_edge))
534 {
535 best_edge = e;
536 best_prob = prob;
537 best_freq = freq;
538 }
539 }
540
541 /* If the best destination has multiple predecessors, and can be
542 duplicated cheaper than a jump, don't allow it to be added
543 to a trace. We'll duplicate it when connecting traces. */
544 if (best_edge && EDGE_COUNT (best_edge->dest->preds) >= 2
545 && copy_bb_p (best_edge->dest, 0))
546 best_edge = NULL;
547
548 /* Add all non-selected successors to the heaps. */
549 FOR_EACH_EDGE (e, ei, bb->succs)
550 {
551 if (e == best_edge
552 || e->dest == EXIT_BLOCK_PTR
553 || e->dest->il.rtl->visited)
554 continue;
555
556 key = bb_to_key (e->dest);
557
558 if (bbd[e->dest->index].heap)
559 {
560 /* E->DEST is already in some heap. */
561 if (key != bbd[e->dest->index].node->key)
562 {
563 if (dump_file)
564 {
565 fprintf (dump_file,
566 "Changing key for bb %d from %ld to %ld.\n",
567 e->dest->index,
568 (long) bbd[e->dest->index].node->key,
569 key);
570 }
571 fibheap_replace_key (bbd[e->dest->index].heap,
572 bbd[e->dest->index].node, key);
573 }
574 }
575 else
576 {
577 fibheap_t which_heap = *heap;
578
579 prob = e->probability;
580 freq = EDGE_FREQUENCY (e);
581
582 if (!(e->flags & EDGE_CAN_FALLTHRU)
583 || (e->flags & EDGE_COMPLEX)
584 || prob < branch_th || freq < exec_th
585 || e->count < count_th)
586 {
587 /* When partitioning hot/cold basic blocks, make sure
588 the cold blocks (and only the cold blocks) all get
589 pushed to the last round of trace collection. */
590
591 if (push_to_next_round_p (e->dest, round,
592 number_of_rounds,
593 exec_th, count_th))
594 which_heap = new_heap;
595 }
596
597 bbd[e->dest->index].heap = which_heap;
598 bbd[e->dest->index].node = fibheap_insert (which_heap,
599 key, e->dest);
600
601 if (dump_file)
602 {
603 fprintf (dump_file,
604 " Possible start of %s round: %d (key: %ld)\n",
605 (which_heap == new_heap) ? "next" : "this",
606 e->dest->index, (long) key);
607 }
608
609 }
610 }
611
612 if (best_edge) /* Suitable successor was found. */
613 {
614 if (best_edge->dest->il.rtl->visited == *n_traces)
615 {
616 /* We do nothing with one basic block loops. */
617 if (best_edge->dest != bb)
618 {
619 if (EDGE_FREQUENCY (best_edge)
620 > 4 * best_edge->dest->frequency / 5)
621 {
622 /* The loop has at least 4 iterations. If the loop
623 header is not the first block of the function
624 we can rotate the loop. */
625
626 if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
627 {
628 if (dump_file)
629 {
630 fprintf (dump_file,
631 "Rotating loop %d - %d\n",
632 best_edge->dest->index, bb->index);
633 }
634 bb->aux = best_edge->dest;
635 bbd[best_edge->dest->index].in_trace =
636 (*n_traces) - 1;
637 bb = rotate_loop (best_edge, trace, *n_traces);
638 }
639 }
640 else
641 {
642 /* The loop has less than 4 iterations. */
643
644 if (single_succ_p (bb)
645 && copy_bb_p (best_edge->dest,
646 optimize_edge_for_speed_p (best_edge)))
647 {
648 bb = copy_bb (best_edge->dest, best_edge, bb,
649 *n_traces);
650 trace->length++;
651 }
652 }
653 }
654
655 /* Terminate the trace. */
656 break;
657 }
658 else
659 {
660 /* Check for a situation
661
662 A
663 /|
664 B |
665 \|
666 C
667
668 where
669 EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
670 >= EDGE_FREQUENCY (AC).
671 (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
672 Best ordering is then A B C.
673
674 This situation is created for example by:
675
676 if (A) B;
677 C;
678
679 */
680
681 FOR_EACH_EDGE (e, ei, bb->succs)
682 if (e != best_edge
683 && (e->flags & EDGE_CAN_FALLTHRU)
684 && !(e->flags & EDGE_COMPLEX)
685 && !e->dest->il.rtl->visited
686 && single_pred_p (e->dest)
687 && !(e->flags & EDGE_CROSSING)
688 && single_succ_p (e->dest)
689 && (single_succ_edge (e->dest)->flags
690 & EDGE_CAN_FALLTHRU)
691 && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
692 && single_succ (e->dest) == best_edge->dest
693 && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
694 {
695 best_edge = e;
696 if (dump_file)
697 fprintf (dump_file, "Selecting BB %d\n",
698 best_edge->dest->index);
699 break;
700 }
701
702 bb->aux = best_edge->dest;
703 bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
704 bb = best_edge->dest;
705 }
706 }
707 }
708 while (best_edge);
709 trace->last = bb;
710 bbd[trace->first->index].start_of_trace = *n_traces - 1;
711 bbd[trace->last->index].end_of_trace = *n_traces - 1;
712
713 /* The trace is terminated so we have to recount the keys in heap
714 (some block can have a lower key because now one of its predecessors
715 is an end of the trace). */
716 FOR_EACH_EDGE (e, ei, bb->succs)
717 {
718 if (e->dest == EXIT_BLOCK_PTR
719 || e->dest->il.rtl->visited)
720 continue;
721
722 if (bbd[e->dest->index].heap)
723 {
724 key = bb_to_key (e->dest);
725 if (key != bbd[e->dest->index].node->key)
726 {
727 if (dump_file)
728 {
729 fprintf (dump_file,
730 "Changing key for bb %d from %ld to %ld.\n",
731 e->dest->index,
732 (long) bbd[e->dest->index].node->key, key);
733 }
734 fibheap_replace_key (bbd[e->dest->index].heap,
735 bbd[e->dest->index].node,
736 key);
737 }
738 }
739 }
740 }
741
742 fibheap_delete (*heap);
743
744 /* "Return" the new heap. */
745 *heap = new_heap;
746 }
747
748 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
749 it to trace after BB, mark OLD_BB visited and update pass' data structures
750 (TRACE is a number of trace which OLD_BB is duplicated to). */
751
752 static basic_block
copy_bb(basic_block old_bb,edge e,basic_block bb,int trace)753 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
754 {
755 basic_block new_bb;
756
757 new_bb = duplicate_block (old_bb, e, bb);
758 BB_COPY_PARTITION (new_bb, old_bb);
759
760 gcc_assert (e->dest == new_bb);
761 gcc_assert (!e->dest->il.rtl->visited);
762
763 if (dump_file)
764 fprintf (dump_file,
765 "Duplicated bb %d (created bb %d)\n",
766 old_bb->index, new_bb->index);
767 new_bb->il.rtl->visited = trace;
768 new_bb->aux = bb->aux;
769 bb->aux = new_bb;
770
771 if (new_bb->index >= array_size || last_basic_block > array_size)
772 {
773 int i;
774 int new_size;
775
776 new_size = MAX (last_basic_block, new_bb->index + 1);
777 new_size = GET_ARRAY_SIZE (new_size);
778 bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
779 for (i = array_size; i < new_size; i++)
780 {
781 bbd[i].start_of_trace = -1;
782 bbd[i].in_trace = -1;
783 bbd[i].end_of_trace = -1;
784 bbd[i].heap = NULL;
785 bbd[i].node = NULL;
786 }
787 array_size = new_size;
788
789 if (dump_file)
790 {
791 fprintf (dump_file,
792 "Growing the dynamic array to %d elements.\n",
793 array_size);
794 }
795 }
796
797 bbd[new_bb->index].in_trace = trace;
798
799 return new_bb;
800 }
801
802 /* Compute and return the key (for the heap) of the basic block BB. */
803
804 static fibheapkey_t
bb_to_key(basic_block bb)805 bb_to_key (basic_block bb)
806 {
807 edge e;
808 edge_iterator ei;
809 int priority = 0;
810
811 /* Do not start in probably never executed blocks. */
812
813 if (BB_PARTITION (bb) == BB_COLD_PARTITION
814 || probably_never_executed_bb_p (bb))
815 return BB_FREQ_MAX;
816
817 /* Prefer blocks whose predecessor is an end of some trace
818 or whose predecessor edge is EDGE_DFS_BACK. */
819 FOR_EACH_EDGE (e, ei, bb->preds)
820 {
821 if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
822 || (e->flags & EDGE_DFS_BACK))
823 {
824 int edge_freq = EDGE_FREQUENCY (e);
825
826 if (edge_freq > priority)
827 priority = edge_freq;
828 }
829 }
830
831 if (priority)
832 /* The block with priority should have significantly lower key. */
833 return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
834 return -bb->frequency;
835 }
836
837 /* Return true when the edge E from basic block BB is better than the temporary
838 best edge (details are in function). The probability of edge E is PROB. The
839 frequency of the successor is FREQ. The current best probability is
840 BEST_PROB, the best frequency is BEST_FREQ.
841 The edge is considered to be equivalent when PROB does not differ much from
842 BEST_PROB; similarly for frequency. */
843
844 static bool
better_edge_p(const_basic_block bb,const_edge e,int prob,int freq,int best_prob,int best_freq,const_edge cur_best_edge)845 better_edge_p (const_basic_block bb, const_edge e, int prob, int freq, int best_prob,
846 int best_freq, const_edge cur_best_edge)
847 {
848 bool is_better_edge;
849
850 /* The BEST_* values do not have to be best, but can be a bit smaller than
851 maximum values. */
852 int diff_prob = best_prob / 10;
853 int diff_freq = best_freq / 10;
854
855 if (prob > best_prob + diff_prob)
856 /* The edge has higher probability than the temporary best edge. */
857 is_better_edge = true;
858 else if (prob < best_prob - diff_prob)
859 /* The edge has lower probability than the temporary best edge. */
860 is_better_edge = false;
861 else if (freq < best_freq - diff_freq)
862 /* The edge and the temporary best edge have almost equivalent
863 probabilities. The higher frequency of a successor now means
864 that there is another edge going into that successor.
865 This successor has lower frequency so it is better. */
866 is_better_edge = true;
867 else if (freq > best_freq + diff_freq)
868 /* This successor has higher frequency so it is worse. */
869 is_better_edge = false;
870 else if (e->dest->prev_bb == bb)
871 /* The edges have equivalent probabilities and the successors
872 have equivalent frequencies. Select the previous successor. */
873 is_better_edge = true;
874 else
875 is_better_edge = false;
876
877 /* If we are doing hot/cold partitioning, make sure that we always favor
878 non-crossing edges over crossing edges. */
879
880 if (!is_better_edge
881 && flag_reorder_blocks_and_partition
882 && cur_best_edge
883 && (cur_best_edge->flags & EDGE_CROSSING)
884 && !(e->flags & EDGE_CROSSING))
885 is_better_edge = true;
886
887 return is_better_edge;
888 }
889
890 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
891
892 static void
connect_traces(int n_traces,struct trace * traces)893 connect_traces (int n_traces, struct trace *traces)
894 {
895 int i;
896 bool *connected;
897 bool two_passes;
898 int last_trace;
899 int current_pass;
900 int current_partition;
901 int freq_threshold;
902 gcov_type count_threshold;
903
904 freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
905 if (max_entry_count < INT_MAX / 1000)
906 count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
907 else
908 count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
909
910 connected = XCNEWVEC (bool, n_traces);
911 last_trace = -1;
912 current_pass = 1;
913 current_partition = BB_PARTITION (traces[0].first);
914 two_passes = false;
915
916 if (flag_reorder_blocks_and_partition)
917 for (i = 0; i < n_traces && !two_passes; i++)
918 if (BB_PARTITION (traces[0].first)
919 != BB_PARTITION (traces[i].first))
920 two_passes = true;
921
922 for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
923 {
924 int t = i;
925 int t2;
926 edge e, best;
927 int best_len;
928
929 if (i >= n_traces)
930 {
931 gcc_assert (two_passes && current_pass == 1);
932 i = 0;
933 t = i;
934 current_pass = 2;
935 if (current_partition == BB_HOT_PARTITION)
936 current_partition = BB_COLD_PARTITION;
937 else
938 current_partition = BB_HOT_PARTITION;
939 }
940
941 if (connected[t])
942 continue;
943
944 if (two_passes
945 && BB_PARTITION (traces[t].first) != current_partition)
946 continue;
947
948 connected[t] = true;
949
950 /* Find the predecessor traces. */
951 for (t2 = t; t2 > 0;)
952 {
953 edge_iterator ei;
954 best = NULL;
955 best_len = 0;
956 FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
957 {
958 int si = e->src->index;
959
960 if (e->src != ENTRY_BLOCK_PTR
961 && (e->flags & EDGE_CAN_FALLTHRU)
962 && !(e->flags & EDGE_COMPLEX)
963 && bbd[si].end_of_trace >= 0
964 && !connected[bbd[si].end_of_trace]
965 && (BB_PARTITION (e->src) == current_partition)
966 && (!best
967 || e->probability > best->probability
968 || (e->probability == best->probability
969 && traces[bbd[si].end_of_trace].length > best_len)))
970 {
971 best = e;
972 best_len = traces[bbd[si].end_of_trace].length;
973 }
974 }
975 if (best)
976 {
977 best->src->aux = best->dest;
978 t2 = bbd[best->src->index].end_of_trace;
979 connected[t2] = true;
980
981 if (dump_file)
982 {
983 fprintf (dump_file, "Connection: %d %d\n",
984 best->src->index, best->dest->index);
985 }
986 }
987 else
988 break;
989 }
990
991 if (last_trace >= 0)
992 traces[last_trace].last->aux = traces[t2].first;
993 last_trace = t;
994
995 /* Find the successor traces. */
996 while (1)
997 {
998 /* Find the continuation of the chain. */
999 edge_iterator ei;
1000 best = NULL;
1001 best_len = 0;
1002 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1003 {
1004 int di = e->dest->index;
1005
1006 if (e->dest != EXIT_BLOCK_PTR
1007 && (e->flags & EDGE_CAN_FALLTHRU)
1008 && !(e->flags & EDGE_COMPLEX)
1009 && bbd[di].start_of_trace >= 0
1010 && !connected[bbd[di].start_of_trace]
1011 && (BB_PARTITION (e->dest) == current_partition)
1012 && (!best
1013 || e->probability > best->probability
1014 || (e->probability == best->probability
1015 && traces[bbd[di].start_of_trace].length > best_len)))
1016 {
1017 best = e;
1018 best_len = traces[bbd[di].start_of_trace].length;
1019 }
1020 }
1021
1022 if (best)
1023 {
1024 if (dump_file)
1025 {
1026 fprintf (dump_file, "Connection: %d %d\n",
1027 best->src->index, best->dest->index);
1028 }
1029 t = bbd[best->dest->index].start_of_trace;
1030 traces[last_trace].last->aux = traces[t].first;
1031 connected[t] = true;
1032 last_trace = t;
1033 }
1034 else
1035 {
1036 /* Try to connect the traces by duplication of 1 block. */
1037 edge e2;
1038 basic_block next_bb = NULL;
1039 bool try_copy = false;
1040
1041 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1042 if (e->dest != EXIT_BLOCK_PTR
1043 && (e->flags & EDGE_CAN_FALLTHRU)
1044 && !(e->flags & EDGE_COMPLEX)
1045 && (!best || e->probability > best->probability))
1046 {
1047 edge_iterator ei;
1048 edge best2 = NULL;
1049 int best2_len = 0;
1050
1051 /* If the destination is a start of a trace which is only
1052 one block long, then no need to search the successor
1053 blocks of the trace. Accept it. */
1054 if (bbd[e->dest->index].start_of_trace >= 0
1055 && traces[bbd[e->dest->index].start_of_trace].length
1056 == 1)
1057 {
1058 best = e;
1059 try_copy = true;
1060 continue;
1061 }
1062
1063 FOR_EACH_EDGE (e2, ei, e->dest->succs)
1064 {
1065 int di = e2->dest->index;
1066
1067 if (e2->dest == EXIT_BLOCK_PTR
1068 || ((e2->flags & EDGE_CAN_FALLTHRU)
1069 && !(e2->flags & EDGE_COMPLEX)
1070 && bbd[di].start_of_trace >= 0
1071 && !connected[bbd[di].start_of_trace]
1072 && (BB_PARTITION (e2->dest) == current_partition)
1073 && (EDGE_FREQUENCY (e2) >= freq_threshold)
1074 && (e2->count >= count_threshold)
1075 && (!best2
1076 || e2->probability > best2->probability
1077 || (e2->probability == best2->probability
1078 && traces[bbd[di].start_of_trace].length
1079 > best2_len))))
1080 {
1081 best = e;
1082 best2 = e2;
1083 if (e2->dest != EXIT_BLOCK_PTR)
1084 best2_len = traces[bbd[di].start_of_trace].length;
1085 else
1086 best2_len = INT_MAX;
1087 next_bb = e2->dest;
1088 try_copy = true;
1089 }
1090 }
1091 }
1092
1093 if (flag_reorder_blocks_and_partition)
1094 try_copy = false;
1095
1096 /* Copy tiny blocks always; copy larger blocks only when the
1097 edge is traversed frequently enough. */
1098 if (try_copy
1099 && copy_bb_p (best->dest,
1100 optimize_edge_for_speed_p (best)
1101 && EDGE_FREQUENCY (best) >= freq_threshold
1102 && best->count >= count_threshold))
1103 {
1104 basic_block new_bb;
1105
1106 if (dump_file)
1107 {
1108 fprintf (dump_file, "Connection: %d %d ",
1109 traces[t].last->index, best->dest->index);
1110 if (!next_bb)
1111 fputc ('\n', dump_file);
1112 else if (next_bb == EXIT_BLOCK_PTR)
1113 fprintf (dump_file, "exit\n");
1114 else
1115 fprintf (dump_file, "%d\n", next_bb->index);
1116 }
1117
1118 new_bb = copy_bb (best->dest, best, traces[t].last, t);
1119 traces[t].last = new_bb;
1120 if (next_bb && next_bb != EXIT_BLOCK_PTR)
1121 {
1122 t = bbd[next_bb->index].start_of_trace;
1123 traces[last_trace].last->aux = traces[t].first;
1124 connected[t] = true;
1125 last_trace = t;
1126 }
1127 else
1128 break; /* Stop finding the successor traces. */
1129 }
1130 else
1131 break; /* Stop finding the successor traces. */
1132 }
1133 }
1134 }
1135
1136 if (dump_file)
1137 {
1138 basic_block bb;
1139
1140 fprintf (dump_file, "Final order:\n");
1141 for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
1142 fprintf (dump_file, "%d ", bb->index);
1143 fprintf (dump_file, "\n");
1144 fflush (dump_file);
1145 }
1146
1147 FREE (connected);
1148 }
1149
1150 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1151 when code size is allowed to grow by duplication. */
1152
1153 static bool
copy_bb_p(const_basic_block bb,int code_may_grow)1154 copy_bb_p (const_basic_block bb, int code_may_grow)
1155 {
1156 int size = 0;
1157 int max_size = uncond_jump_length;
1158 rtx insn;
1159
1160 if (!bb->frequency)
1161 return false;
1162 if (EDGE_COUNT (bb->preds) < 2)
1163 return false;
1164 if (!can_duplicate_block_p (bb))
1165 return false;
1166
1167 /* Avoid duplicating blocks which have many successors (PR/13430). */
1168 if (EDGE_COUNT (bb->succs) > 8)
1169 return false;
1170
1171 if (code_may_grow && optimize_bb_for_speed_p (bb))
1172 max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
1173
1174 FOR_BB_INSNS (bb, insn)
1175 {
1176 if (INSN_P (insn))
1177 size += get_attr_min_length (insn);
1178 }
1179
1180 if (size <= max_size)
1181 return true;
1182
1183 if (dump_file)
1184 {
1185 fprintf (dump_file,
1186 "Block %d can't be copied because its size = %d.\n",
1187 bb->index, size);
1188 }
1189
1190 return false;
1191 }
1192
1193 /* Return the length of unconditional jump instruction. */
1194
1195 int
get_uncond_jump_length(void)1196 get_uncond_jump_length (void)
1197 {
1198 rtx label, jump;
1199 int length;
1200
1201 label = emit_label_before (gen_label_rtx (), get_insns ());
1202 jump = emit_jump_insn (gen_jump (label));
1203
1204 length = get_attr_min_length (jump);
1205
1206 delete_insn (jump);
1207 delete_insn (label);
1208 return length;
1209 }
1210
1211 /* Emit a barrier into the footer of BB. */
1212
1213 static void
emit_barrier_after_bb(basic_block bb)1214 emit_barrier_after_bb (basic_block bb)
1215 {
1216 rtx barrier = emit_barrier_after (BB_END (bb));
1217 bb->il.rtl->footer = unlink_insn_chain (barrier, barrier);
1218 }
1219
1220 /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1221 Duplicate the landing pad and split the edges so that no EH edge
1222 crosses partitions. */
1223
1224 static void
fix_up_crossing_landing_pad(eh_landing_pad old_lp,basic_block old_bb)1225 fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
1226 {
1227 eh_landing_pad new_lp;
1228 basic_block new_bb, last_bb, post_bb;
1229 rtx new_label, jump, post_label;
1230 unsigned new_partition;
1231 edge_iterator ei;
1232 edge e;
1233
1234 /* Generate the new landing-pad structure. */
1235 new_lp = gen_eh_landing_pad (old_lp->region);
1236 new_lp->post_landing_pad = old_lp->post_landing_pad;
1237 new_lp->landing_pad = gen_label_rtx ();
1238 LABEL_PRESERVE_P (new_lp->landing_pad) = 1;
1239
1240 /* Put appropriate instructions in new bb. */
1241 new_label = emit_label (new_lp->landing_pad);
1242
1243 expand_dw2_landing_pad_for_region (old_lp->region);
1244
1245 post_bb = BLOCK_FOR_INSN (old_lp->landing_pad);
1246 post_bb = single_succ (post_bb);
1247 post_label = block_label (post_bb);
1248 jump = emit_jump_insn (gen_jump (post_label));
1249 JUMP_LABEL (jump) = post_label;
1250
1251 /* Create new basic block to be dest for lp. */
1252 last_bb = EXIT_BLOCK_PTR->prev_bb;
1253 new_bb = create_basic_block (new_label, jump, last_bb);
1254 new_bb->aux = last_bb->aux;
1255 last_bb->aux = new_bb;
1256
1257 emit_barrier_after_bb (new_bb);
1258
1259 make_edge (new_bb, post_bb, 0);
1260
1261 /* Make sure new bb is in the other partition. */
1262 new_partition = BB_PARTITION (old_bb);
1263 new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1264 BB_SET_PARTITION (new_bb, new_partition);
1265
1266 /* Fix up the edges. */
1267 for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
1268 if (BB_PARTITION (e->src) == new_partition)
1269 {
1270 rtx insn = BB_END (e->src);
1271 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1272
1273 gcc_assert (note != NULL);
1274 gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index);
1275 XEXP (note, 0) = GEN_INT (new_lp->index);
1276
1277 /* Adjust the edge to the new destination. */
1278 redirect_edge_succ (e, new_bb);
1279 }
1280 else
1281 ei_next (&ei);
1282 }
1283
1284 /* Find the basic blocks that are rarely executed and need to be moved to
1285 a separate section of the .o file (to cut down on paging and improve
1286 cache locality). Return a vector of all edges that cross. */
1287
VEC(edge,heap)1288 static VEC(edge, heap) *
1289 find_rarely_executed_basic_blocks_and_crossing_edges (void)
1290 {
1291 VEC(edge, heap) *crossing_edges = NULL;
1292 basic_block bb;
1293 edge e;
1294 edge_iterator ei;
1295
1296 /* Mark which partition (hot/cold) each basic block belongs in. */
1297 FOR_EACH_BB (bb)
1298 {
1299 if (probably_never_executed_bb_p (bb))
1300 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1301 else
1302 BB_SET_PARTITION (bb, BB_HOT_PARTITION);
1303 }
1304
1305 /* The format of .gcc_except_table does not allow landing pads to
1306 be in a different partition as the throw. Fix this by either
1307 moving or duplicating the landing pads. */
1308 if (cfun->eh->lp_array)
1309 {
1310 unsigned i;
1311 eh_landing_pad lp;
1312
1313 FOR_EACH_VEC_ELT (eh_landing_pad, cfun->eh->lp_array, i, lp)
1314 {
1315 bool all_same, all_diff;
1316
1317 if (lp == NULL
1318 || lp->landing_pad == NULL_RTX
1319 || !LABEL_P (lp->landing_pad))
1320 continue;
1321
1322 all_same = all_diff = true;
1323 bb = BLOCK_FOR_INSN (lp->landing_pad);
1324 FOR_EACH_EDGE (e, ei, bb->preds)
1325 {
1326 gcc_assert (e->flags & EDGE_EH);
1327 if (BB_PARTITION (bb) == BB_PARTITION (e->src))
1328 all_diff = false;
1329 else
1330 all_same = false;
1331 }
1332
1333 if (all_same)
1334 ;
1335 else if (all_diff)
1336 {
1337 int which = BB_PARTITION (bb);
1338 which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1339 BB_SET_PARTITION (bb, which);
1340 }
1341 else
1342 fix_up_crossing_landing_pad (lp, bb);
1343 }
1344 }
1345
1346 /* Mark every edge that crosses between sections. */
1347
1348 FOR_EACH_BB (bb)
1349 FOR_EACH_EDGE (e, ei, bb->succs)
1350 {
1351 unsigned int flags = e->flags;
1352
1353 /* We should never have EDGE_CROSSING set yet. */
1354 gcc_checking_assert ((flags & EDGE_CROSSING) == 0);
1355
1356 if (e->src != ENTRY_BLOCK_PTR
1357 && e->dest != EXIT_BLOCK_PTR
1358 && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1359 {
1360 VEC_safe_push (edge, heap, crossing_edges, e);
1361 flags |= EDGE_CROSSING;
1362 }
1363
1364 /* Now that we've split eh edges as appropriate, allow landing pads
1365 to be merged with the post-landing pads. */
1366 flags &= ~EDGE_PRESERVE;
1367
1368 e->flags = flags;
1369 }
1370
1371 return crossing_edges;
1372 }
1373
1374 /* If any destination of a crossing edge does not have a label, add label;
1375 Convert any easy fall-through crossing edges to unconditional jumps. */
1376
1377 static void
add_labels_and_missing_jumps(VEC (edge,heap)* crossing_edges)1378 add_labels_and_missing_jumps (VEC(edge, heap) *crossing_edges)
1379 {
1380 size_t i;
1381 edge e;
1382
1383 FOR_EACH_VEC_ELT (edge, crossing_edges, i, e)
1384 {
1385 basic_block src = e->src;
1386 basic_block dest = e->dest;
1387 rtx label, new_jump;
1388
1389 if (dest == EXIT_BLOCK_PTR)
1390 continue;
1391
1392 /* Make sure dest has a label. */
1393 label = block_label (dest);
1394
1395 /* Nothing to do for non-fallthru edges. */
1396 if (src == ENTRY_BLOCK_PTR)
1397 continue;
1398 if ((e->flags & EDGE_FALLTHRU) == 0)
1399 continue;
1400
1401 /* If the block does not end with a control flow insn, then we
1402 can trivially add a jump to the end to fixup the crossing.
1403 Otherwise the jump will have to go in a new bb, which will
1404 be handled by fix_up_fall_thru_edges function. */
1405 if (control_flow_insn_p (BB_END (src)))
1406 continue;
1407
1408 /* Make sure there's only one successor. */
1409 gcc_assert (single_succ_p (src));
1410
1411 new_jump = emit_jump_insn_after (gen_jump (label), BB_END (src));
1412 BB_END (src) = new_jump;
1413 JUMP_LABEL (new_jump) = label;
1414 LABEL_NUSES (label) += 1;
1415
1416 emit_barrier_after_bb (src);
1417
1418 /* Mark edge as non-fallthru. */
1419 e->flags &= ~EDGE_FALLTHRU;
1420 }
1421 }
1422
1423 /* Find any bb's where the fall-through edge is a crossing edge (note that
1424 these bb's must also contain a conditional jump or end with a call
1425 instruction; we've already dealt with fall-through edges for blocks
1426 that didn't have a conditional jump or didn't end with call instruction
1427 in the call to add_labels_and_missing_jumps). Convert the fall-through
1428 edge to non-crossing edge by inserting a new bb to fall-through into.
1429 The new bb will contain an unconditional jump (crossing edge) to the
1430 original fall through destination. */
1431
1432 static void
fix_up_fall_thru_edges(void)1433 fix_up_fall_thru_edges (void)
1434 {
1435 basic_block cur_bb;
1436 basic_block new_bb;
1437 edge succ1;
1438 edge succ2;
1439 edge fall_thru;
1440 edge cond_jump = NULL;
1441 edge e;
1442 bool cond_jump_crosses;
1443 int invert_worked;
1444 rtx old_jump;
1445 rtx fall_thru_label;
1446
1447 FOR_EACH_BB (cur_bb)
1448 {
1449 fall_thru = NULL;
1450 if (EDGE_COUNT (cur_bb->succs) > 0)
1451 succ1 = EDGE_SUCC (cur_bb, 0);
1452 else
1453 succ1 = NULL;
1454
1455 if (EDGE_COUNT (cur_bb->succs) > 1)
1456 succ2 = EDGE_SUCC (cur_bb, 1);
1457 else
1458 succ2 = NULL;
1459
1460 /* Find the fall-through edge. */
1461
1462 if (succ1
1463 && (succ1->flags & EDGE_FALLTHRU))
1464 {
1465 fall_thru = succ1;
1466 cond_jump = succ2;
1467 }
1468 else if (succ2
1469 && (succ2->flags & EDGE_FALLTHRU))
1470 {
1471 fall_thru = succ2;
1472 cond_jump = succ1;
1473 }
1474 else if (succ1
1475 && (block_ends_with_call_p (cur_bb)
1476 || can_throw_internal (BB_END (cur_bb))))
1477 {
1478 edge e;
1479 edge_iterator ei;
1480
1481 FOR_EACH_EDGE (e, ei, cur_bb->succs)
1482 if (e->flags & EDGE_FALLTHRU)
1483 {
1484 fall_thru = e;
1485 break;
1486 }
1487 }
1488
1489 if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR))
1490 {
1491 /* Check to see if the fall-thru edge is a crossing edge. */
1492
1493 if (fall_thru->flags & EDGE_CROSSING)
1494 {
1495 /* The fall_thru edge crosses; now check the cond jump edge, if
1496 it exists. */
1497
1498 cond_jump_crosses = true;
1499 invert_worked = 0;
1500 old_jump = BB_END (cur_bb);
1501
1502 /* Find the jump instruction, if there is one. */
1503
1504 if (cond_jump)
1505 {
1506 if (!(cond_jump->flags & EDGE_CROSSING))
1507 cond_jump_crosses = false;
1508
1509 /* We know the fall-thru edge crosses; if the cond
1510 jump edge does NOT cross, and its destination is the
1511 next block in the bb order, invert the jump
1512 (i.e. fix it so the fall thru does not cross and
1513 the cond jump does). */
1514
1515 if (!cond_jump_crosses
1516 && cur_bb->aux == cond_jump->dest)
1517 {
1518 /* Find label in fall_thru block. We've already added
1519 any missing labels, so there must be one. */
1520
1521 fall_thru_label = block_label (fall_thru->dest);
1522
1523 if (old_jump && JUMP_P (old_jump) && fall_thru_label)
1524 invert_worked = invert_jump (old_jump,
1525 fall_thru_label,0);
1526 if (invert_worked)
1527 {
1528 fall_thru->flags &= ~EDGE_FALLTHRU;
1529 cond_jump->flags |= EDGE_FALLTHRU;
1530 update_br_prob_note (cur_bb);
1531 e = fall_thru;
1532 fall_thru = cond_jump;
1533 cond_jump = e;
1534 cond_jump->flags |= EDGE_CROSSING;
1535 fall_thru->flags &= ~EDGE_CROSSING;
1536 }
1537 }
1538 }
1539
1540 if (cond_jump_crosses || !invert_worked)
1541 {
1542 /* This is the case where both edges out of the basic
1543 block are crossing edges. Here we will fix up the
1544 fall through edge. The jump edge will be taken care
1545 of later. The EDGE_CROSSING flag of fall_thru edge
1546 is unset before the call to force_nonfallthru
1547 function because if a new basic-block is created
1548 this edge remains in the current section boundary
1549 while the edge between new_bb and the fall_thru->dest
1550 becomes EDGE_CROSSING. */
1551
1552 fall_thru->flags &= ~EDGE_CROSSING;
1553 new_bb = force_nonfallthru (fall_thru);
1554
1555 if (new_bb)
1556 {
1557 new_bb->aux = cur_bb->aux;
1558 cur_bb->aux = new_bb;
1559
1560 /* Make sure new fall-through bb is in same
1561 partition as bb it's falling through from. */
1562
1563 BB_COPY_PARTITION (new_bb, cur_bb);
1564 single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
1565 }
1566 else
1567 {
1568 /* If a new basic-block was not created; restore
1569 the EDGE_CROSSING flag. */
1570 fall_thru->flags |= EDGE_CROSSING;
1571 }
1572
1573 /* Add barrier after new jump */
1574 emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
1575 }
1576 }
1577 }
1578 }
1579 }
1580
1581 /* This function checks the destination block of a "crossing jump" to
1582 see if it has any crossing predecessors that begin with a code label
1583 and end with an unconditional jump. If so, it returns that predecessor
1584 block. (This is to avoid creating lots of new basic blocks that all
1585 contain unconditional jumps to the same destination). */
1586
1587 static basic_block
find_jump_block(basic_block jump_dest)1588 find_jump_block (basic_block jump_dest)
1589 {
1590 basic_block source_bb = NULL;
1591 edge e;
1592 rtx insn;
1593 edge_iterator ei;
1594
1595 FOR_EACH_EDGE (e, ei, jump_dest->preds)
1596 if (e->flags & EDGE_CROSSING)
1597 {
1598 basic_block src = e->src;
1599
1600 /* Check each predecessor to see if it has a label, and contains
1601 only one executable instruction, which is an unconditional jump.
1602 If so, we can use it. */
1603
1604 if (LABEL_P (BB_HEAD (src)))
1605 for (insn = BB_HEAD (src);
1606 !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
1607 insn = NEXT_INSN (insn))
1608 {
1609 if (INSN_P (insn)
1610 && insn == BB_END (src)
1611 && JUMP_P (insn)
1612 && !any_condjump_p (insn))
1613 {
1614 source_bb = src;
1615 break;
1616 }
1617 }
1618
1619 if (source_bb)
1620 break;
1621 }
1622
1623 return source_bb;
1624 }
1625
1626 /* Find all BB's with conditional jumps that are crossing edges;
1627 insert a new bb and make the conditional jump branch to the new
1628 bb instead (make the new bb same color so conditional branch won't
1629 be a 'crossing' edge). Insert an unconditional jump from the
1630 new bb to the original destination of the conditional jump. */
1631
1632 static void
fix_crossing_conditional_branches(void)1633 fix_crossing_conditional_branches (void)
1634 {
1635 basic_block cur_bb;
1636 basic_block new_bb;
1637 basic_block dest;
1638 edge succ1;
1639 edge succ2;
1640 edge crossing_edge;
1641 edge new_edge;
1642 rtx old_jump;
1643 rtx set_src;
1644 rtx old_label = NULL_RTX;
1645 rtx new_label;
1646
1647 FOR_EACH_BB (cur_bb)
1648 {
1649 crossing_edge = NULL;
1650 if (EDGE_COUNT (cur_bb->succs) > 0)
1651 succ1 = EDGE_SUCC (cur_bb, 0);
1652 else
1653 succ1 = NULL;
1654
1655 if (EDGE_COUNT (cur_bb->succs) > 1)
1656 succ2 = EDGE_SUCC (cur_bb, 1);
1657 else
1658 succ2 = NULL;
1659
1660 /* We already took care of fall-through edges, so only one successor
1661 can be a crossing edge. */
1662
1663 if (succ1 && (succ1->flags & EDGE_CROSSING))
1664 crossing_edge = succ1;
1665 else if (succ2 && (succ2->flags & EDGE_CROSSING))
1666 crossing_edge = succ2;
1667
1668 if (crossing_edge)
1669 {
1670 old_jump = BB_END (cur_bb);
1671
1672 /* Check to make sure the jump instruction is a
1673 conditional jump. */
1674
1675 set_src = NULL_RTX;
1676
1677 if (any_condjump_p (old_jump))
1678 {
1679 if (GET_CODE (PATTERN (old_jump)) == SET)
1680 set_src = SET_SRC (PATTERN (old_jump));
1681 else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
1682 {
1683 set_src = XVECEXP (PATTERN (old_jump), 0,0);
1684 if (GET_CODE (set_src) == SET)
1685 set_src = SET_SRC (set_src);
1686 else
1687 set_src = NULL_RTX;
1688 }
1689 }
1690
1691 if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
1692 {
1693 if (GET_CODE (XEXP (set_src, 1)) == PC)
1694 old_label = XEXP (set_src, 2);
1695 else if (GET_CODE (XEXP (set_src, 2)) == PC)
1696 old_label = XEXP (set_src, 1);
1697
1698 /* Check to see if new bb for jumping to that dest has
1699 already been created; if so, use it; if not, create
1700 a new one. */
1701
1702 new_bb = find_jump_block (crossing_edge->dest);
1703
1704 if (new_bb)
1705 new_label = block_label (new_bb);
1706 else
1707 {
1708 basic_block last_bb;
1709 rtx new_jump;
1710
1711 /* Create new basic block to be dest for
1712 conditional jump. */
1713
1714 /* Put appropriate instructions in new bb. */
1715
1716 new_label = gen_label_rtx ();
1717 emit_label (new_label);
1718
1719 gcc_assert (GET_CODE (old_label) == LABEL_REF);
1720 old_label = JUMP_LABEL (old_jump);
1721 new_jump = emit_jump_insn (gen_jump (old_label));
1722 JUMP_LABEL (new_jump) = old_label;
1723
1724 last_bb = EXIT_BLOCK_PTR->prev_bb;
1725 new_bb = create_basic_block (new_label, new_jump, last_bb);
1726 new_bb->aux = last_bb->aux;
1727 last_bb->aux = new_bb;
1728
1729 emit_barrier_after_bb (new_bb);
1730
1731 /* Make sure new bb is in same partition as source
1732 of conditional branch. */
1733 BB_COPY_PARTITION (new_bb, cur_bb);
1734 }
1735
1736 /* Make old jump branch to new bb. */
1737
1738 redirect_jump (old_jump, new_label, 0);
1739
1740 /* Remove crossing_edge as predecessor of 'dest'. */
1741
1742 dest = crossing_edge->dest;
1743
1744 redirect_edge_succ (crossing_edge, new_bb);
1745
1746 /* Make a new edge from new_bb to old dest; new edge
1747 will be a successor for new_bb and a predecessor
1748 for 'dest'. */
1749
1750 if (EDGE_COUNT (new_bb->succs) == 0)
1751 new_edge = make_edge (new_bb, dest, 0);
1752 else
1753 new_edge = EDGE_SUCC (new_bb, 0);
1754
1755 crossing_edge->flags &= ~EDGE_CROSSING;
1756 new_edge->flags |= EDGE_CROSSING;
1757 }
1758 }
1759 }
1760 }
1761
1762 /* Find any unconditional branches that cross between hot and cold
1763 sections. Convert them into indirect jumps instead. */
1764
1765 static void
fix_crossing_unconditional_branches(void)1766 fix_crossing_unconditional_branches (void)
1767 {
1768 basic_block cur_bb;
1769 rtx last_insn;
1770 rtx label;
1771 rtx label_addr;
1772 rtx indirect_jump_sequence;
1773 rtx jump_insn = NULL_RTX;
1774 rtx new_reg;
1775 rtx cur_insn;
1776 edge succ;
1777
1778 FOR_EACH_BB (cur_bb)
1779 {
1780 last_insn = BB_END (cur_bb);
1781
1782 if (EDGE_COUNT (cur_bb->succs) < 1)
1783 continue;
1784
1785 succ = EDGE_SUCC (cur_bb, 0);
1786
1787 /* Check to see if bb ends in a crossing (unconditional) jump. At
1788 this point, no crossing jumps should be conditional. */
1789
1790 if (JUMP_P (last_insn)
1791 && (succ->flags & EDGE_CROSSING))
1792 {
1793 rtx label2, table;
1794
1795 gcc_assert (!any_condjump_p (last_insn));
1796
1797 /* Make sure the jump is not already an indirect or table jump. */
1798
1799 if (!computed_jump_p (last_insn)
1800 && !tablejump_p (last_insn, &label2, &table))
1801 {
1802 /* We have found a "crossing" unconditional branch. Now
1803 we must convert it to an indirect jump. First create
1804 reference of label, as target for jump. */
1805
1806 label = JUMP_LABEL (last_insn);
1807 label_addr = gen_rtx_LABEL_REF (Pmode, label);
1808 LABEL_NUSES (label) += 1;
1809
1810 /* Get a register to use for the indirect jump. */
1811
1812 new_reg = gen_reg_rtx (Pmode);
1813
1814 /* Generate indirect the jump sequence. */
1815
1816 start_sequence ();
1817 emit_move_insn (new_reg, label_addr);
1818 emit_indirect_jump (new_reg);
1819 indirect_jump_sequence = get_insns ();
1820 end_sequence ();
1821
1822 /* Make sure every instruction in the new jump sequence has
1823 its basic block set to be cur_bb. */
1824
1825 for (cur_insn = indirect_jump_sequence; cur_insn;
1826 cur_insn = NEXT_INSN (cur_insn))
1827 {
1828 if (!BARRIER_P (cur_insn))
1829 BLOCK_FOR_INSN (cur_insn) = cur_bb;
1830 if (JUMP_P (cur_insn))
1831 jump_insn = cur_insn;
1832 }
1833
1834 /* Insert the new (indirect) jump sequence immediately before
1835 the unconditional jump, then delete the unconditional jump. */
1836
1837 emit_insn_before (indirect_jump_sequence, last_insn);
1838 delete_insn (last_insn);
1839
1840 /* Make BB_END for cur_bb be the jump instruction (NOT the
1841 barrier instruction at the end of the sequence...). */
1842
1843 BB_END (cur_bb) = jump_insn;
1844 }
1845 }
1846 }
1847 }
1848
1849 /* Add REG_CROSSING_JUMP note to all crossing jump insns. */
1850
1851 static void
add_reg_crossing_jump_notes(void)1852 add_reg_crossing_jump_notes (void)
1853 {
1854 basic_block bb;
1855 edge e;
1856 edge_iterator ei;
1857
1858 FOR_EACH_BB (bb)
1859 FOR_EACH_EDGE (e, ei, bb->succs)
1860 if ((e->flags & EDGE_CROSSING)
1861 && JUMP_P (BB_END (e->src)))
1862 add_reg_note (BB_END (e->src), REG_CROSSING_JUMP, NULL_RTX);
1863 }
1864
1865 /* Verify, in the basic block chain, that there is at most one switch
1866 between hot/cold partitions. This is modelled on
1867 rtl_verify_flow_info_1, but it cannot go inside that function
1868 because this condition will not be true until after
1869 reorder_basic_blocks is called. */
1870
1871 static void
verify_hot_cold_block_grouping(void)1872 verify_hot_cold_block_grouping (void)
1873 {
1874 basic_block bb;
1875 int err = 0;
1876 bool switched_sections = false;
1877 int current_partition = 0;
1878
1879 FOR_EACH_BB (bb)
1880 {
1881 if (!current_partition)
1882 current_partition = BB_PARTITION (bb);
1883 if (BB_PARTITION (bb) != current_partition)
1884 {
1885 if (switched_sections)
1886 {
1887 error ("multiple hot/cold transitions found (bb %i)",
1888 bb->index);
1889 err = 1;
1890 }
1891 else
1892 {
1893 switched_sections = true;
1894 current_partition = BB_PARTITION (bb);
1895 }
1896 }
1897 }
1898
1899 gcc_assert(!err);
1900 }
1901
1902 /* Reorder basic blocks. The main entry point to this file. FLAGS is
1903 the set of flags to pass to cfg_layout_initialize(). */
1904
1905 void
reorder_basic_blocks(void)1906 reorder_basic_blocks (void)
1907 {
1908 int n_traces;
1909 int i;
1910 struct trace *traces;
1911
1912 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
1913
1914 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
1915 return;
1916
1917 set_edge_can_fallthru_flag ();
1918 mark_dfs_back_edges ();
1919
1920 /* We are estimating the length of uncond jump insn only once since the code
1921 for getting the insn length always returns the minimal length now. */
1922 if (uncond_jump_length == 0)
1923 uncond_jump_length = get_uncond_jump_length ();
1924
1925 /* We need to know some information for each basic block. */
1926 array_size = GET_ARRAY_SIZE (last_basic_block);
1927 bbd = XNEWVEC (bbro_basic_block_data, array_size);
1928 for (i = 0; i < array_size; i++)
1929 {
1930 bbd[i].start_of_trace = -1;
1931 bbd[i].in_trace = -1;
1932 bbd[i].end_of_trace = -1;
1933 bbd[i].heap = NULL;
1934 bbd[i].node = NULL;
1935 }
1936
1937 traces = XNEWVEC (struct trace, n_basic_blocks);
1938 n_traces = 0;
1939 find_traces (&n_traces, traces);
1940 connect_traces (n_traces, traces);
1941 FREE (traces);
1942 FREE (bbd);
1943
1944 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
1945
1946 if (dump_file)
1947 dump_flow_info (dump_file, dump_flags);
1948
1949 if (flag_reorder_blocks_and_partition)
1950 verify_hot_cold_block_grouping ();
1951 }
1952
1953 /* Determine which partition the first basic block in the function
1954 belongs to, then find the first basic block in the current function
1955 that belongs to a different section, and insert a
1956 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
1957 instruction stream. When writing out the assembly code,
1958 encountering this note will make the compiler switch between the
1959 hot and cold text sections. */
1960
1961 static void
insert_section_boundary_note(void)1962 insert_section_boundary_note (void)
1963 {
1964 basic_block bb;
1965 rtx new_note;
1966 int first_partition = 0;
1967
1968 if (!flag_reorder_blocks_and_partition)
1969 return;
1970
1971 FOR_EACH_BB (bb)
1972 {
1973 if (!first_partition)
1974 first_partition = BB_PARTITION (bb);
1975 if (BB_PARTITION (bb) != first_partition)
1976 {
1977 new_note = emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS,
1978 BB_HEAD (bb));
1979 /* ??? This kind of note always lives between basic blocks,
1980 but add_insn_before will set BLOCK_FOR_INSN anyway. */
1981 BLOCK_FOR_INSN (new_note) = NULL;
1982 break;
1983 }
1984 }
1985 }
1986
1987 /* Duplicate the blocks containing computed gotos. This basically unfactors
1988 computed gotos that were factored early on in the compilation process to
1989 speed up edge based data flow. We used to not unfactoring them again,
1990 which can seriously pessimize code with many computed jumps in the source
1991 code, such as interpreters. See e.g. PR15242. */
1992
1993 static bool
gate_duplicate_computed_gotos(void)1994 gate_duplicate_computed_gotos (void)
1995 {
1996 if (targetm.cannot_modify_jumps_p ())
1997 return false;
1998 return (optimize > 0
1999 && flag_expensive_optimizations
2000 && ! optimize_function_for_size_p (cfun));
2001 }
2002
2003
2004 static unsigned int
duplicate_computed_gotos(void)2005 duplicate_computed_gotos (void)
2006 {
2007 basic_block bb, new_bb;
2008 bitmap candidates;
2009 int max_size;
2010
2011 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
2012 return 0;
2013
2014 cfg_layout_initialize (0);
2015
2016 /* We are estimating the length of uncond jump insn only once
2017 since the code for getting the insn length always returns
2018 the minimal length now. */
2019 if (uncond_jump_length == 0)
2020 uncond_jump_length = get_uncond_jump_length ();
2021
2022 max_size = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
2023 candidates = BITMAP_ALLOC (NULL);
2024
2025 /* Look for blocks that end in a computed jump, and see if such blocks
2026 are suitable for unfactoring. If a block is a candidate for unfactoring,
2027 mark it in the candidates. */
2028 FOR_EACH_BB (bb)
2029 {
2030 rtx insn;
2031 edge e;
2032 edge_iterator ei;
2033 int size, all_flags;
2034
2035 /* Build the reorder chain for the original order of blocks. */
2036 if (bb->next_bb != EXIT_BLOCK_PTR)
2037 bb->aux = bb->next_bb;
2038
2039 /* Obviously the block has to end in a computed jump. */
2040 if (!computed_jump_p (BB_END (bb)))
2041 continue;
2042
2043 /* Only consider blocks that can be duplicated. */
2044 if (find_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX)
2045 || !can_duplicate_block_p (bb))
2046 continue;
2047
2048 /* Make sure that the block is small enough. */
2049 size = 0;
2050 FOR_BB_INSNS (bb, insn)
2051 if (INSN_P (insn))
2052 {
2053 size += get_attr_min_length (insn);
2054 if (size > max_size)
2055 break;
2056 }
2057 if (size > max_size)
2058 continue;
2059
2060 /* Final check: there must not be any incoming abnormal edges. */
2061 all_flags = 0;
2062 FOR_EACH_EDGE (e, ei, bb->preds)
2063 all_flags |= e->flags;
2064 if (all_flags & EDGE_COMPLEX)
2065 continue;
2066
2067 bitmap_set_bit (candidates, bb->index);
2068 }
2069
2070 /* Nothing to do if there is no computed jump here. */
2071 if (bitmap_empty_p (candidates))
2072 goto done;
2073
2074 /* Duplicate computed gotos. */
2075 FOR_EACH_BB (bb)
2076 {
2077 if (bb->il.rtl->visited)
2078 continue;
2079
2080 bb->il.rtl->visited = 1;
2081
2082 /* BB must have one outgoing edge. That edge must not lead to
2083 the exit block or the next block.
2084 The destination must have more than one predecessor. */
2085 if (!single_succ_p (bb)
2086 || single_succ (bb) == EXIT_BLOCK_PTR
2087 || single_succ (bb) == bb->next_bb
2088 || single_pred_p (single_succ (bb)))
2089 continue;
2090
2091 /* The successor block has to be a duplication candidate. */
2092 if (!bitmap_bit_p (candidates, single_succ (bb)->index))
2093 continue;
2094
2095 new_bb = duplicate_block (single_succ (bb), single_succ_edge (bb), bb);
2096 new_bb->aux = bb->aux;
2097 bb->aux = new_bb;
2098 new_bb->il.rtl->visited = 1;
2099 }
2100
2101 done:
2102 cfg_layout_finalize ();
2103
2104 BITMAP_FREE (candidates);
2105 return 0;
2106 }
2107
2108 struct rtl_opt_pass pass_duplicate_computed_gotos =
2109 {
2110 {
2111 RTL_PASS,
2112 "compgotos", /* name */
2113 gate_duplicate_computed_gotos, /* gate */
2114 duplicate_computed_gotos, /* execute */
2115 NULL, /* sub */
2116 NULL, /* next */
2117 0, /* static_pass_number */
2118 TV_REORDER_BLOCKS, /* tv_id */
2119 0, /* properties_required */
2120 0, /* properties_provided */
2121 0, /* properties_destroyed */
2122 0, /* todo_flags_start */
2123 TODO_verify_rtl_sharing,/* todo_flags_finish */
2124 }
2125 };
2126
2127
2128 /* This function is the main 'entrance' for the optimization that
2129 partitions hot and cold basic blocks into separate sections of the
2130 .o file (to improve performance and cache locality). Ideally it
2131 would be called after all optimizations that rearrange the CFG have
2132 been called. However part of this optimization may introduce new
2133 register usage, so it must be called before register allocation has
2134 occurred. This means that this optimization is actually called
2135 well before the optimization that reorders basic blocks (see
2136 function above).
2137
2138 This optimization checks the feedback information to determine
2139 which basic blocks are hot/cold, updates flags on the basic blocks
2140 to indicate which section they belong in. This information is
2141 later used for writing out sections in the .o file. Because hot
2142 and cold sections can be arbitrarily large (within the bounds of
2143 memory), far beyond the size of a single function, it is necessary
2144 to fix up all edges that cross section boundaries, to make sure the
2145 instructions used can actually span the required distance. The
2146 fixes are described below.
2147
2148 Fall-through edges must be changed into jumps; it is not safe or
2149 legal to fall through across a section boundary. Whenever a
2150 fall-through edge crossing a section boundary is encountered, a new
2151 basic block is inserted (in the same section as the fall-through
2152 source), and the fall through edge is redirected to the new basic
2153 block. The new basic block contains an unconditional jump to the
2154 original fall-through target. (If the unconditional jump is
2155 insufficient to cross section boundaries, that is dealt with a
2156 little later, see below).
2157
2158 In order to deal with architectures that have short conditional
2159 branches (which cannot span all of memory) we take any conditional
2160 jump that attempts to cross a section boundary and add a level of
2161 indirection: it becomes a conditional jump to a new basic block, in
2162 the same section. The new basic block contains an unconditional
2163 jump to the original target, in the other section.
2164
2165 For those architectures whose unconditional branch is also
2166 incapable of reaching all of memory, those unconditional jumps are
2167 converted into indirect jumps, through a register.
2168
2169 IMPORTANT NOTE: This optimization causes some messy interactions
2170 with the cfg cleanup optimizations; those optimizations want to
2171 merge blocks wherever possible, and to collapse indirect jump
2172 sequences (change "A jumps to B jumps to C" directly into "A jumps
2173 to C"). Those optimizations can undo the jump fixes that
2174 partitioning is required to make (see above), in order to ensure
2175 that jumps attempting to cross section boundaries are really able
2176 to cover whatever distance the jump requires (on many architectures
2177 conditional or unconditional jumps are not able to reach all of
2178 memory). Therefore tests have to be inserted into each such
2179 optimization to make sure that it does not undo stuff necessary to
2180 cross partition boundaries. This would be much less of a problem
2181 if we could perform this optimization later in the compilation, but
2182 unfortunately the fact that we may need to create indirect jumps
2183 (through registers) requires that this optimization be performed
2184 before register allocation.
2185
2186 Hot and cold basic blocks are partitioned and put in separate
2187 sections of the .o file, to reduce paging and improve cache
2188 performance (hopefully). This can result in bits of code from the
2189 same function being widely separated in the .o file. However this
2190 is not obvious to the current bb structure. Therefore we must take
2191 care to ensure that: 1). There are no fall_thru edges that cross
2192 between sections; 2). For those architectures which have "short"
2193 conditional branches, all conditional branches that attempt to
2194 cross between sections are converted to unconditional branches;
2195 and, 3). For those architectures which have "short" unconditional
2196 branches, all unconditional branches that attempt to cross between
2197 sections are converted to indirect jumps.
2198
2199 The code for fixing up fall_thru edges that cross between hot and
2200 cold basic blocks does so by creating new basic blocks containing
2201 unconditional branches to the appropriate label in the "other"
2202 section. The new basic block is then put in the same (hot or cold)
2203 section as the original conditional branch, and the fall_thru edge
2204 is modified to fall into the new basic block instead. By adding
2205 this level of indirection we end up with only unconditional branches
2206 crossing between hot and cold sections.
2207
2208 Conditional branches are dealt with by adding a level of indirection.
2209 A new basic block is added in the same (hot/cold) section as the
2210 conditional branch, and the conditional branch is retargeted to the
2211 new basic block. The new basic block contains an unconditional branch
2212 to the original target of the conditional branch (in the other section).
2213
2214 Unconditional branches are dealt with by converting them into
2215 indirect jumps. */
2216
2217 static unsigned
partition_hot_cold_basic_blocks(void)2218 partition_hot_cold_basic_blocks (void)
2219 {
2220 VEC(edge, heap) *crossing_edges;
2221
2222 if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1)
2223 return 0;
2224
2225 df_set_flags (DF_DEFER_INSN_RESCAN);
2226
2227 crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
2228 if (crossing_edges == NULL)
2229 return 0;
2230
2231 /* Make sure the source of any crossing edge ends in a jump and the
2232 destination of any crossing edge has a label. */
2233 add_labels_and_missing_jumps (crossing_edges);
2234
2235 /* Convert all crossing fall_thru edges to non-crossing fall
2236 thrus to unconditional jumps (that jump to the original fall
2237 thru dest). */
2238 fix_up_fall_thru_edges ();
2239
2240 /* If the architecture does not have conditional branches that can
2241 span all of memory, convert crossing conditional branches into
2242 crossing unconditional branches. */
2243 if (!HAS_LONG_COND_BRANCH)
2244 fix_crossing_conditional_branches ();
2245
2246 /* If the architecture does not have unconditional branches that
2247 can span all of memory, convert crossing unconditional branches
2248 into indirect jumps. Since adding an indirect jump also adds
2249 a new register usage, update the register usage information as
2250 well. */
2251 if (!HAS_LONG_UNCOND_BRANCH)
2252 fix_crossing_unconditional_branches ();
2253
2254 add_reg_crossing_jump_notes ();
2255
2256 /* Clear bb->aux fields that the above routines were using. */
2257 clear_aux_for_blocks ();
2258
2259 VEC_free (edge, heap, crossing_edges);
2260
2261 /* ??? FIXME: DF generates the bb info for a block immediately.
2262 And by immediately, I mean *during* creation of the block.
2263
2264 #0 df_bb_refs_collect
2265 #1 in df_bb_refs_record
2266 #2 in create_basic_block_structure
2267
2268 Which means that the bb_has_eh_pred test in df_bb_refs_collect
2269 will *always* fail, because no edges can have been added to the
2270 block yet. Which of course means we don't add the right
2271 artificial refs, which means we fail df_verify (much) later.
2272
2273 Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
2274 that we also shouldn't grab data from the new blocks those new
2275 insns are in either. In this way one can create the block, link
2276 it up properly, and have everything Just Work later, when deferred
2277 insns are processed.
2278
2279 In the meantime, we have no other option but to throw away all
2280 of the DF data and recompute it all. */
2281 if (cfun->eh->lp_array)
2282 {
2283 df_finish_pass (true);
2284 df_scan_alloc (NULL);
2285 df_scan_blocks ();
2286 /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
2287 data. We blindly generated all of them when creating the new
2288 landing pad. Delete those assignments we don't use. */
2289 df_set_flags (DF_LR_RUN_DCE);
2290 df_analyze ();
2291 }
2292
2293 return TODO_verify_flow | TODO_verify_rtl_sharing;
2294 }
2295
2296 static bool
gate_handle_reorder_blocks(void)2297 gate_handle_reorder_blocks (void)
2298 {
2299 if (targetm.cannot_modify_jumps_p ())
2300 return false;
2301 /* Don't reorder blocks when optimizing for size because extra jump insns may
2302 be created; also barrier may create extra padding.
2303
2304 More correctly we should have a block reordering mode that tried to
2305 minimize the combined size of all the jumps. This would more or less
2306 automatically remove extra jumps, but would also try to use more short
2307 jumps instead of long jumps. */
2308 if (!optimize_function_for_speed_p (cfun))
2309 return false;
2310 return (optimize > 0
2311 && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
2312 }
2313
2314
2315 /* Reorder basic blocks. */
2316 static unsigned int
rest_of_handle_reorder_blocks(void)2317 rest_of_handle_reorder_blocks (void)
2318 {
2319 basic_block bb;
2320
2321 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2322 splitting possibly introduced more crossjumping opportunities. */
2323 cfg_layout_initialize (CLEANUP_EXPENSIVE);
2324
2325 reorder_basic_blocks ();
2326 cleanup_cfg (CLEANUP_EXPENSIVE);
2327
2328 FOR_EACH_BB (bb)
2329 if (bb->next_bb != EXIT_BLOCK_PTR)
2330 bb->aux = bb->next_bb;
2331 cfg_layout_finalize ();
2332
2333 /* Add NOTE_INSN_SWITCH_TEXT_SECTIONS notes. */
2334 insert_section_boundary_note ();
2335 return 0;
2336 }
2337
2338 struct rtl_opt_pass pass_reorder_blocks =
2339 {
2340 {
2341 RTL_PASS,
2342 "bbro", /* name */
2343 gate_handle_reorder_blocks, /* gate */
2344 rest_of_handle_reorder_blocks, /* execute */
2345 NULL, /* sub */
2346 NULL, /* next */
2347 0, /* static_pass_number */
2348 TV_REORDER_BLOCKS, /* tv_id */
2349 0, /* properties_required */
2350 0, /* properties_provided */
2351 0, /* properties_destroyed */
2352 0, /* todo_flags_start */
2353 TODO_verify_rtl_sharing, /* todo_flags_finish */
2354 }
2355 };
2356
2357 static bool
gate_handle_partition_blocks(void)2358 gate_handle_partition_blocks (void)
2359 {
2360 /* The optimization to partition hot/cold basic blocks into separate
2361 sections of the .o file does not work well with linkonce or with
2362 user defined section attributes. Don't call it if either case
2363 arises. */
2364 return (flag_reorder_blocks_and_partition
2365 && optimize
2366 /* See gate_handle_reorder_blocks. We should not partition if
2367 we are going to omit the reordering. */
2368 && optimize_function_for_speed_p (cfun)
2369 && !DECL_ONE_ONLY (current_function_decl)
2370 && !user_defined_section_attribute);
2371 }
2372
2373 struct rtl_opt_pass pass_partition_blocks =
2374 {
2375 {
2376 RTL_PASS,
2377 "bbpart", /* name */
2378 gate_handle_partition_blocks, /* gate */
2379 partition_hot_cold_basic_blocks, /* execute */
2380 NULL, /* sub */
2381 NULL, /* next */
2382 0, /* static_pass_number */
2383 TV_REORDER_BLOCKS, /* tv_id */
2384 PROP_cfglayout, /* properties_required */
2385 0, /* properties_provided */
2386 0, /* properties_destroyed */
2387 0, /* todo_flags_start */
2388 0 /* todo_flags_finish */
2389 }
2390 };
2391