1/* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000-2017 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
19
20/* This file contains the "reorder blocks" pass, which changes the control
21 flow of a function to encounter fewer branches; the "partition blocks"
22 pass, which divides the basic blocks into "hot" and "cold" partitions,
23 which are kept separate; and the "duplicate computed gotos" pass, which
24 duplicates blocks ending in an indirect jump.
25
26 There are two algorithms for "reorder blocks": the "simple" algorithm,
27 which just rearranges blocks, trying to minimize the number of executed
28 unconditional branches; and the "software trace cache" algorithm, which
29 also copies code, and in general tries a lot harder to have long linear
30 pieces of machine code executed. This algorithm is described next. */
31
32/* This (greedy) algorithm constructs traces in several rounds.
33 The construction starts from "seeds". The seed for the first round
34 is the entry point of the function. When there are more than one seed,
35 the one with the lowest key in the heap is selected first (see bb_to_key).
36 Then the algorithm repeatedly adds the most probable successor to the end
37 of a trace. Finally it connects the traces.
38
39 There are two parameters: Branch Threshold and Exec Threshold.
40 If the probability of an edge to a successor of the current basic block is
41 lower than Branch Threshold or its count is lower than Exec Threshold,
42 then the successor will be the seed in one of the next rounds.
43 Each round has these parameters lower than the previous one.
44 The last round has to have these parameters set to zero so that the
45 remaining blocks are picked up.
46
47 The algorithm selects the most probable successor from all unvisited
48 successors and successors that have been added to this trace.
49 The other successors (that has not been "sent" to the next round) will be
50 other seeds for this round and the secondary traces will start from them.
51 If the successor has not been visited in this trace, it is added to the
52 trace (however, there is some heuristic for simple branches).
53 If the successor has been visited in this trace, a loop has been found.
54 If the loop has many iterations, the loop is rotated so that the source
55 block of the most probable edge going out of the loop is the last block
56 of the trace.
57 If the loop has few iterations and there is no edge from the last block of
58 the loop going out of the loop, the loop header is duplicated.
59
60 When connecting traces, the algorithm first checks whether there is an edge
61 from the last block of a trace to the first block of another trace.
62 When there are still some unconnected traces it checks whether there exists
63 a basic block BB such that BB is a successor of the last block of a trace
64 and BB is a predecessor of the first block of another trace. In this case,
65 BB is duplicated, added at the end of the first trace and the traces are
66 connected through it.
67 The rest of traces are simply connected so there will be a jump to the
68 beginning of the rest of traces.
69
70 The above description is for the full algorithm, which is used when the
71 function is optimized for speed. When the function is optimized for size,
72 in order to reduce long jumps and connect more fallthru edges, the
73 algorithm is modified as follows:
74 (1) Break long traces to short ones. A trace is broken at a block that has
75 multiple predecessors/ successors during trace discovery. When connecting
76 traces, only connect Trace n with Trace n + 1. This change reduces most
77 long jumps compared with the above algorithm.
78 (2) Ignore the edge probability and count for fallthru edges.
79 (3) Keep the original order of blocks when there is no chance to fall
80 through. We rely on the results of cfg_cleanup.
81
82 To implement the change for code size optimization, block's index is
83 selected as the key and all traces are found in one round.
84
85 References:
86
87 "Software Trace Cache"
88 A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
89 http://citeseer.nj.nec.com/15361.html
90
91*/
92
93#include "config.h"
94#define INCLUDE_ALGORITHM /* stable_sort */
95#include "system.h"
96#include "coretypes.h"
97#include "backend.h"
98#include "target.h"
99#include "rtl.h"
100#include "tree.h"
101#include "cfghooks.h"
102#include "df.h"
103#include "memmodel.h"
104#include "optabs.h"
105#include "regs.h"
106#include "emit-rtl.h"
107#include "output.h"
108#include "expr.h"
109#include "params.h"
110#include "tree-pass.h"
111#include "cfgrtl.h"
112#include "cfganal.h"
113#include "cfgbuild.h"
114#include "cfgcleanup.h"
115#include "bb-reorder.h"
116#include "except.h"
117#include "fibonacci_heap.h"
118#include "stringpool.h"
119#include "attribs.h"
120
121/* The number of rounds. In most cases there will only be 4 rounds, but
122 when partitioning hot and cold basic blocks into separate sections of
123 the object file there will be an extra round. */
124#define N_ROUNDS 5
125
126struct target_bb_reorder default_target_bb_reorder;
127#if SWITCHABLE_TARGET
128struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder;
129#endif
130
131#define uncond_jump_length \
132 (this_target_bb_reorder->x_uncond_jump_length)
133
134/* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
135static const int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
136
137/* Exec thresholds in thousandths (per mille) of the count of bb 0. */
138static const int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
139
140/* If edge count is lower than DUPLICATION_THRESHOLD per mille of entry
141 block the edge destination is not duplicated while connecting traces. */
142#define DUPLICATION_THRESHOLD 100
143
144typedef fibonacci_heap <long, basic_block_def> bb_heap_t;
145typedef fibonacci_node <long, basic_block_def> bb_heap_node_t;
146
147/* Structure to hold needed information for each basic block. */
148struct bbro_basic_block_data
149{
150 /* Which trace is the bb start of (-1 means it is not a start of any). */
151 int start_of_trace;
152
153 /* Which trace is the bb end of (-1 means it is not an end of any). */
154 int end_of_trace;
155
156 /* Which trace is the bb in? */
157 int in_trace;
158
159 /* Which trace was this bb visited in? */
160 int visited;
161
162 /* Cached maximum frequency of interesting incoming edges.
163 Minus one means not yet computed. */
164 int priority;
165
166 /* Which heap is BB in (if any)? */
167 bb_heap_t *heap;
168
169 /* Which heap node is BB in (if any)? */
170 bb_heap_node_t *node;
171};
172
173/* The current size of the following dynamic array. */
174static int array_size;
175
176/* The array which holds needed information for basic blocks. */
177static bbro_basic_block_data *bbd;
178
179/* To avoid frequent reallocation the size of arrays is greater than needed,
180 the number of elements is (not less than) 1.25 * size_wanted. */
181#define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
182
183/* Free the memory and set the pointer to NULL. */
184#define FREE(P) (gcc_assert (P), free (P), P = 0)
185
186/* Structure for holding information about a trace. */
187struct trace
188{
189 /* First and last basic block of the trace. */
190 basic_block first, last;
191
192 /* The round of the STC creation which this trace was found in. */
193 int round;
194
195 /* The length (i.e. the number of basic blocks) of the trace. */
196 int length;
197};
198
199/* Maximum count of one of the entry blocks. */
200static profile_count max_entry_count;
201
202/* Local function prototypes. */
203static void find_traces_1_round (int, profile_count, struct trace *, int *,
204 int, bb_heap_t **, int);
205static basic_block copy_bb (basic_block, edge, basic_block, int);
206static long bb_to_key (basic_block);
207static bool better_edge_p (const_basic_block, const_edge, profile_probability,
208 profile_count, profile_probability, profile_count,
209 const_edge);
210static bool copy_bb_p (const_basic_block, int);
211
212/* Return the trace number in which BB was visited. */
213
214static int
215bb_visited_trace (const_basic_block bb)
216{
217 gcc_assert (bb->index < array_size);
218 return bbd[bb->index].visited;
219}
220
221/* This function marks BB that it was visited in trace number TRACE. */
222
223static void
224mark_bb_visited (basic_block bb, int trace)
225{
226 bbd[bb->index].visited = trace;
227 if (bbd[bb->index].heap)
228 {
229 bbd[bb->index].heap->delete_node (bbd[bb->index].node);
230 bbd[bb->index].heap = NULL;
231 bbd[bb->index].node = NULL;
232 }
233}
234
235/* Check to see if bb should be pushed into the next round of trace
236 collections or not. Reasons for pushing the block forward are 1).
237 If the block is cold, we are doing partitioning, and there will be
238 another round (cold partition blocks are not supposed to be
239 collected into traces until the very last round); or 2). There will
240 be another round, and the basic block is not "hot enough" for the
241 current round of trace collection. */
242
243static bool
244push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
245 profile_count count_th)
246{
247 bool there_exists_another_round;
248 bool block_not_hot_enough;
249
250 there_exists_another_round = round < number_of_rounds - 1;
251
252 block_not_hot_enough = (bb->count < count_th
253 || probably_never_executed_bb_p (cfun, bb));
254
255 if (there_exists_another_round
256 && block_not_hot_enough)
257 return true;
258 else
259 return false;
260}
261
262/* Find the traces for Software Trace Cache. Chain each trace through
263 RBI()->next. Store the number of traces to N_TRACES and description of
264 traces to TRACES. */
265
266static void
267find_traces (int *n_traces, struct trace *traces)
268{
269 int i;
270 int number_of_rounds;
271 edge e;
272 edge_iterator ei;
273 bb_heap_t *heap = new bb_heap_t (LONG_MIN);
274
275 /* Add one extra round of trace collection when partitioning hot/cold
276 basic blocks into separate sections. The last round is for all the
277 cold blocks (and ONLY the cold blocks). */
278
279 number_of_rounds = N_ROUNDS - 1;
280
281 /* Insert entry points of function into heap. */
282 max_entry_count = profile_count::zero ();
283 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
284 {
285 bbd[e->dest->index].heap = heap;
286 bbd[e->dest->index].node = heap->insert (bb_to_key (e->dest), e->dest);
287 if (e->dest->count > max_entry_count)
288 max_entry_count = e->dest->count;
289 }
290
291 /* Find the traces. */
292 for (i = 0; i < number_of_rounds; i++)
293 {
294 profile_count count_threshold;
295
296 if (dump_file)
297 fprintf (dump_file, "STC - round %d\n", i + 1);
298
299 count_threshold = max_entry_count.apply_scale (exec_threshold[i], 1000);
300
301 find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
302 count_threshold, traces, n_traces, i, &heap,
303 number_of_rounds);
304 }
305 delete heap;
306
307 if (dump_file)
308 {
309 for (i = 0; i < *n_traces; i++)
310 {
311 basic_block bb;
312 fprintf (dump_file, "Trace %d (round %d): ", i + 1,
313 traces[i].round + 1);
314 for (bb = traces[i].first;
315 bb != traces[i].last;
316 bb = (basic_block) bb->aux)
317 {
318 fprintf (dump_file, "%d [", bb->index);
319 bb->count.dump (dump_file);
320 fprintf (dump_file, "] ");
321 }
322 fprintf (dump_file, "%d [", bb->index);
323 bb->count.dump (dump_file);
324 fprintf (dump_file, "]\n");
325 }
326 fflush (dump_file);
327 }
328}
329
330/* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
331 (with sequential number TRACE_N). */
332
333static basic_block
334rotate_loop (edge back_edge, struct trace *trace, int trace_n)
335{
336 basic_block bb;
337
338 /* Information about the best end (end after rotation) of the loop. */
339 basic_block best_bb = NULL;
340 edge best_edge = NULL;
341 profile_count best_count = profile_count::uninitialized ();
342 /* The best edge is preferred when its destination is not visited yet
343 or is a start block of some trace. */
344 bool is_preferred = false;
345
346 /* Find the most frequent edge that goes out from current trace. */
347 bb = back_edge->dest;
348 do
349 {
350 edge e;
351 edge_iterator ei;
352
353 FOR_EACH_EDGE (e, ei, bb->succs)
354 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
355 && bb_visited_trace (e->dest) != trace_n
356 && (e->flags & EDGE_CAN_FALLTHRU)
357 && !(e->flags & EDGE_COMPLEX))
358 {
359 if (is_preferred)
360 {
361 /* The best edge is preferred. */
362 if (!bb_visited_trace (e->dest)
363 || bbd[e->dest->index].start_of_trace >= 0)
364 {
365 /* The current edge E is also preferred. */
366 if (e->count () > best_count)
367 {
368 best_count = e->count ();
369 best_edge = e;
370 best_bb = bb;
371 }
372 }
373 }
374 else
375 {
376 if (!bb_visited_trace (e->dest)
377 || bbd[e->dest->index].start_of_trace >= 0)
378 {
379 /* The current edge E is preferred. */
380 is_preferred = true;
381 best_count = e->count ();
382 best_edge = e;
383 best_bb = bb;
384 }
385 else
386 {
387 if (!best_edge || e->count () > best_count)
388 {
389 best_count = e->count ();
390 best_edge = e;
391 best_bb = bb;
392 }
393 }
394 }
395 }
396 bb = (basic_block) bb->aux;
397 }
398 while (bb != back_edge->dest);
399
400 if (best_bb)
401 {
402 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
403 the trace. */
404 if (back_edge->dest == trace->first)
405 {
406 trace->first = (basic_block) best_bb->aux;
407 }
408 else
409 {
410 basic_block prev_bb;
411
412 for (prev_bb = trace->first;
413 prev_bb->aux != back_edge->dest;
414 prev_bb = (basic_block) prev_bb->aux)
415 ;
416 prev_bb->aux = best_bb->aux;
417
418 /* Try to get rid of uncond jump to cond jump. */
419 if (single_succ_p (prev_bb))
420 {
421 basic_block header = single_succ (prev_bb);
422
423 /* Duplicate HEADER if it is a small block containing cond jump
424 in the end. */
425 if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
426 && !CROSSING_JUMP_P (BB_END (header)))
427 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
428 }
429 }
430 }
431 else
432 {
433 /* We have not found suitable loop tail so do no rotation. */
434 best_bb = back_edge->src;
435 }
436 best_bb->aux = NULL;
437 return best_bb;
438}
439
440/* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
441 not include basic blocks whose probability is lower than BRANCH_TH or whose
442 count is lower than EXEC_TH into traces (or whose count is lower than
443 COUNT_TH). Store the new traces into TRACES and modify the number of
444 traces *N_TRACES. Set the round (which the trace belongs to) to ROUND.
445 The function expects starting basic blocks to be in *HEAP and will delete
446 *HEAP and store starting points for the next round into new *HEAP. */
447
448static void
449find_traces_1_round (int branch_th, profile_count count_th,
450 struct trace *traces, int *n_traces, int round,
451 bb_heap_t **heap, int number_of_rounds)
452{
453 /* Heap for discarded basic blocks which are possible starting points for
454 the next round. */
455 bb_heap_t *new_heap = new bb_heap_t (LONG_MIN);
456 bool for_size = optimize_function_for_size_p (cfun);
457
458 while (!(*heap)->empty ())
459 {
460 basic_block bb;
461 struct trace *trace;
462 edge best_edge, e;
463 long key;
464 edge_iterator ei;
465
466 bb = (*heap)->extract_min ();
467 bbd[bb->index].heap = NULL;
468 bbd[bb->index].node = NULL;
469
470 if (dump_file)
471 fprintf (dump_file, "Getting bb %d\n", bb->index);
472
473 /* If the BB's count is too low, send BB to the next round. When
474 partitioning hot/cold blocks into separate sections, make sure all
475 the cold blocks (and ONLY the cold blocks) go into the (extra) final
476 round. When optimizing for size, do not push to next round. */
477
478 if (!for_size
479 && push_to_next_round_p (bb, round, number_of_rounds,
480 count_th))
481 {
482 int key = bb_to_key (bb);
483 bbd[bb->index].heap = new_heap;
484 bbd[bb->index].node = new_heap->insert (key, bb);
485
486 if (dump_file)
487 fprintf (dump_file,
488 " Possible start point of next round: %d (key: %d)\n",
489 bb->index, key);
490 continue;
491 }
492
493 trace = traces + *n_traces;
494 trace->first = bb;
495 trace->round = round;
496 trace->length = 0;
497 bbd[bb->index].in_trace = *n_traces;
498 (*n_traces)++;
499
500 do
501 {
502 bool ends_in_call;
503
504 /* The probability and count of the best edge. */
505 profile_probability best_prob = profile_probability::uninitialized ();
506 profile_count best_count = profile_count::uninitialized ();
507
508 best_edge = NULL;
509 mark_bb_visited (bb, *n_traces);
510 trace->length++;
511
512 if (dump_file)
513 fprintf (dump_file, "Basic block %d was visited in trace %d\n",
514 bb->index, *n_traces);
515
516 ends_in_call = block_ends_with_call_p (bb);
517
518 /* Select the successor that will be placed after BB. */
519 FOR_EACH_EDGE (e, ei, bb->succs)
520 {
521 gcc_assert (!(e->flags & EDGE_FAKE));
522
523 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
524 continue;
525
526 if (bb_visited_trace (e->dest)
527 && bb_visited_trace (e->dest) != *n_traces)
528 continue;
529
530 /* If partitioning hot/cold basic blocks, don't consider edges
531 that cross section boundaries. */
532 if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
533 continue;
534
535 profile_probability prob = e->probability;
536 profile_count count = e->dest->count;
537
538 /* The only sensible preference for a call instruction is the
539 fallthru edge. Don't bother selecting anything else. */
540 if (ends_in_call)
541 {
542 if (e->flags & EDGE_CAN_FALLTHRU)
543 {
544 best_edge = e;
545 best_prob = prob;
546 best_count = count;
547 }
548 continue;
549 }
550
551 /* Edge that cannot be fallthru or improbable or infrequent
552 successor (i.e. it is unsuitable successor). When optimizing
553 for size, ignore the probability and count. */
554 if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
555 || !prob.initialized_p ()
556 || ((prob.to_reg_br_prob_base () < branch_th
557 || e->count () < count_th) && (!for_size)))
558 continue;
559
560 if (better_edge_p (bb, e, prob, count, best_prob, best_count,
561 best_edge))
562 {
563 best_edge = e;
564 best_prob = prob;
565 best_count = count;
566 }
567 }
568
569 /* If the best destination has multiple predecessors and can be
570 duplicated cheaper than a jump, don't allow it to be added to
571 a trace; we'll duplicate it when connecting the traces later.
572 However, we need to check that this duplication wouldn't leave
573 the best destination with only crossing predecessors, because
574 this would change its effective partition from hot to cold. */
575 if (best_edge
576 && EDGE_COUNT (best_edge->dest->preds) >= 2
577 && copy_bb_p (best_edge->dest, 0))
578 {
579 bool only_crossing_preds = true;
580 edge e;
581 edge_iterator ei;
582 FOR_EACH_EDGE (e, ei, best_edge->dest->preds)
583 if (e != best_edge && !(e->flags & EDGE_CROSSING))
584 {
585 only_crossing_preds = false;
586 break;
587 }
588 if (!only_crossing_preds)
589 best_edge = NULL;
590 }
591
592 /* If the best destination has multiple successors or predecessors,
593 don't allow it to be added when optimizing for size. This makes
594 sure predecessors with smaller index are handled before the best
595 destinarion. It breaks long trace and reduces long jumps.
596
597 Take if-then-else as an example.
598 A
599 / \
600 B C
601 \ /
602 D
603 If we do not remove the best edge B->D/C->D, the final order might
604 be A B D ... C. C is at the end of the program. If D's successors
605 and D are complicated, might need long jumps for A->C and C->D.
606 Similar issue for order: A C D ... B.
607
608 After removing the best edge, the final result will be ABCD/ ACBD.
609 It does not add jump compared with the previous order. But it
610 reduces the possibility of long jumps. */
611 if (best_edge && for_size
612 && (EDGE_COUNT (best_edge->dest->succs) > 1
613 || EDGE_COUNT (best_edge->dest->preds) > 1))
614 best_edge = NULL;
615
616 /* Add all non-selected successors to the heaps. */
617 FOR_EACH_EDGE (e, ei, bb->succs)
618 {
619 if (e == best_edge
620 || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
621 || bb_visited_trace (e->dest))
622 continue;
623
624 key = bb_to_key (e->dest);
625
626 if (bbd[e->dest->index].heap)
627 {
628 /* E->DEST is already in some heap. */
629 if (key != bbd[e->dest->index].node->get_key ())
630 {
631 if (dump_file)
632 {
633 fprintf (dump_file,
634 "Changing key for bb %d from %ld to %ld.\n",
635 e->dest->index,
636 (long) bbd[e->dest->index].node->get_key (),
637 key);
638 }
639 bbd[e->dest->index].heap->replace_key
640 (bbd[e->dest->index].node, key);
641 }
642 }
643 else
644 {
645 bb_heap_t *which_heap = *heap;
646
647 profile_probability prob = e->probability;
648
649 if (!(e->flags & EDGE_CAN_FALLTHRU)
650 || (e->flags & EDGE_COMPLEX)
651 || !prob.initialized_p ()
652 || prob.to_reg_br_prob_base () < branch_th
653 || e->count () < count_th)
654 {
655 /* When partitioning hot/cold basic blocks, make sure
656 the cold blocks (and only the cold blocks) all get
657 pushed to the last round of trace collection. When
658 optimizing for size, do not push to next round. */
659
660 if (!for_size && push_to_next_round_p (e->dest, round,
661 number_of_rounds,
662 count_th))
663 which_heap = new_heap;
664 }
665
666 bbd[e->dest->index].heap = which_heap;
667 bbd[e->dest->index].node = which_heap->insert (key, e->dest);
668
669 if (dump_file)
670 {
671 fprintf (dump_file,
672 " Possible start of %s round: %d (key: %ld)\n",
673 (which_heap == new_heap) ? "next" : "this",
674 e->dest->index, (long) key);
675 }
676
677 }
678 }
679
680 if (best_edge) /* Suitable successor was found. */
681 {
682 if (bb_visited_trace (best_edge->dest) == *n_traces)
683 {
684 /* We do nothing with one basic block loops. */
685 if (best_edge->dest != bb)
686 {
687 if (best_edge->count ()
688 > best_edge->dest->count.apply_scale (4, 5))
689 {
690 /* The loop has at least 4 iterations. If the loop
691 header is not the first block of the function
692 we can rotate the loop. */
693
694 if (best_edge->dest
695 != ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
696 {
697 if (dump_file)
698 {
699 fprintf (dump_file,
700 "Rotating loop %d - %d\n",
701 best_edge->dest->index, bb->index);
702 }
703 bb->aux = best_edge->dest;
704 bbd[best_edge->dest->index].in_trace =
705 (*n_traces) - 1;
706 bb = rotate_loop (best_edge, trace, *n_traces);
707 }
708 }
709 else
710 {
711 /* The loop has less than 4 iterations. */
712
713 if (single_succ_p (bb)
714 && copy_bb_p (best_edge->dest,
715 optimize_edge_for_speed_p
716 (best_edge)))
717 {
718 bb = copy_bb (best_edge->dest, best_edge, bb,
719 *n_traces);
720 trace->length++;
721 }
722 }
723 }
724
725 /* Terminate the trace. */
726 break;
727 }
728 else
729 {
730 /* Check for a situation
731
732 A
733 /|
734 B |
735 \|
736 C
737
738 where
739 AB->count () + BC->count () >= AC->count ().
740 (i.e. 2 * B->count >= AC->count )
741 Best ordering is then A B C.
742
743 When optimizing for size, A B C is always the best order.
744
745 This situation is created for example by:
746
747 if (A) B;
748 C;
749
750 */
751
752 FOR_EACH_EDGE (e, ei, bb->succs)
753 if (e != best_edge
754 && (e->flags & EDGE_CAN_FALLTHRU)
755 && !(e->flags & EDGE_COMPLEX)
756 && !bb_visited_trace (e->dest)
757 && single_pred_p (e->dest)
758 && !(e->flags & EDGE_CROSSING)
759 && single_succ_p (e->dest)
760 && (single_succ_edge (e->dest)->flags
761 & EDGE_CAN_FALLTHRU)
762 && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
763 && single_succ (e->dest) == best_edge->dest
764 && (e->dest->count.apply_scale (2, 1)
765 >= best_edge->count () || for_size))
766 {
767 best_edge = e;
768 if (dump_file)
769 fprintf (dump_file, "Selecting BB %d\n",
770 best_edge->dest->index);
771 break;
772 }
773
774 bb->aux = best_edge->dest;
775 bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
776 bb = best_edge->dest;
777 }
778 }
779 }
780 while (best_edge);
781 trace->last = bb;
782 bbd[trace->first->index].start_of_trace = *n_traces - 1;
783 if (bbd[trace->last->index].end_of_trace != *n_traces - 1)
784 {
785 bbd[trace->last->index].end_of_trace = *n_traces - 1;
786 /* Update the cached maximum frequency for interesting predecessor
787 edges for successors of the new trace end. */
788 FOR_EACH_EDGE (e, ei, trace->last->succs)
789 if (EDGE_FREQUENCY (e) > bbd[e->dest->index].priority)
790 bbd[e->dest->index].priority = EDGE_FREQUENCY (e);
791 }
792
793 /* The trace is terminated so we have to recount the keys in heap
794 (some block can have a lower key because now one of its predecessors
795 is an end of the trace). */
796 FOR_EACH_EDGE (e, ei, bb->succs)
797 {
798 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
799 || bb_visited_trace (e->dest))
800 continue;
801
802 if (bbd[e->dest->index].heap)
803 {
804 key = bb_to_key (e->dest);
805 if (key != bbd[e->dest->index].node->get_key ())
806 {
807 if (dump_file)
808 {
809 fprintf (dump_file,
810 "Changing key for bb %d from %ld to %ld.\n",
811 e->dest->index,
812 (long) bbd[e->dest->index].node->get_key (), key);
813 }
814 bbd[e->dest->index].heap->replace_key
815 (bbd[e->dest->index].node, key);
816 }
817 }
818 }
819 }
820
821 delete (*heap);
822
823 /* "Return" the new heap. */
824 *heap = new_heap;
825}
826
827/* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
828 it to trace after BB, mark OLD_BB visited and update pass' data structures
829 (TRACE is a number of trace which OLD_BB is duplicated to). */
830
831static basic_block
832copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
833{
834 basic_block new_bb;
835
836 new_bb = duplicate_block (old_bb, e, bb);
837 BB_COPY_PARTITION (new_bb, old_bb);
838
839 gcc_assert (e->dest == new_bb);
840
841 if (dump_file)
842 fprintf (dump_file,
843 "Duplicated bb %d (created bb %d)\n",
844 old_bb->index, new_bb->index);
845
846 if (new_bb->index >= array_size
847 || last_basic_block_for_fn (cfun) > array_size)
848 {
849 int i;
850 int new_size;
851
852 new_size = MAX (last_basic_block_for_fn (cfun), new_bb->index + 1);
853 new_size = GET_ARRAY_SIZE (new_size);
854 bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
855 for (i = array_size; i < new_size; i++)
856 {
857 bbd[i].start_of_trace = -1;
858 bbd[i].end_of_trace = -1;
859 bbd[i].in_trace = -1;
860 bbd[i].visited = 0;
861 bbd[i].priority = -1;
862 bbd[i].heap = NULL;
863 bbd[i].node = NULL;
864 }
865 array_size = new_size;
866
867 if (dump_file)
868 {
869 fprintf (dump_file,
870 "Growing the dynamic array to %d elements.\n",
871 array_size);
872 }
873 }
874
875 gcc_assert (!bb_visited_trace (e->dest));
876 mark_bb_visited (new_bb, trace);
877 new_bb->aux = bb->aux;
878 bb->aux = new_bb;
879
880 bbd[new_bb->index].in_trace = trace;
881
882 return new_bb;
883}
884
885/* Compute and return the key (for the heap) of the basic block BB. */
886
887static long
888bb_to_key (basic_block bb)
889{
890 edge e;
891 edge_iterator ei;
892
893 /* Use index as key to align with its original order. */
894 if (optimize_function_for_size_p (cfun))
895 return bb->index;
896
897 /* Do not start in probably never executed blocks. */
898
899 if (BB_PARTITION (bb) == BB_COLD_PARTITION
900 || probably_never_executed_bb_p (cfun, bb))
901 return BB_FREQ_MAX;
902
903 /* Prefer blocks whose predecessor is an end of some trace
904 or whose predecessor edge is EDGE_DFS_BACK. */
905 int priority = bbd[bb->index].priority;
906 if (priority == -1)
907 {
908 priority = 0;
909 FOR_EACH_EDGE (e, ei, bb->preds)
910 {
911 if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
912 && bbd[e->src->index].end_of_trace >= 0)
913 || (e->flags & EDGE_DFS_BACK))
914 {
915 int edge_freq = EDGE_FREQUENCY (e);
916
917 if (edge_freq > priority)
918 priority = edge_freq;
919 }
920 }
921 bbd[bb->index].priority = priority;
922 }
923
924 if (priority)
925 /* The block with priority should have significantly lower key. */
926 return -(100 * BB_FREQ_MAX + 100 * priority + bb->count.to_frequency (cfun));
927
928 return -bb->count.to_frequency (cfun);
929}
930
931/* Return true when the edge E from basic block BB is better than the temporary
932 best edge (details are in function). The probability of edge E is PROB. The
933 count of the successor is COUNT. The current best probability is
934 BEST_PROB, the best count is BEST_COUNT.
935 The edge is considered to be equivalent when PROB does not differ much from
936 BEST_PROB; similarly for count. */
937
938static bool
939better_edge_p (const_basic_block bb, const_edge e, profile_probability prob,
940 profile_count count, profile_probability best_prob,
941 profile_count best_count, const_edge cur_best_edge)
942{
943 bool is_better_edge;
944
945 /* The BEST_* values do not have to be best, but can be a bit smaller than
946 maximum values. */
947 profile_probability diff_prob = best_prob.apply_scale (1, 10);
948
949 /* The smaller one is better to keep the original order. */
950 if (optimize_function_for_size_p (cfun))
951 return !cur_best_edge
952 || cur_best_edge->dest->index > e->dest->index;
953
954 /* Those edges are so expensive that continuing a trace is not useful
955 performance wise. */
956 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
957 return false;
958
959 if (prob > best_prob + diff_prob
960 || (!best_prob.initialized_p ()
961 && prob > profile_probability::guessed_never ()))
962 /* The edge has higher probability than the temporary best edge. */
963 is_better_edge = true;
964 else if (prob < best_prob - diff_prob)
965 /* The edge has lower probability than the temporary best edge. */
966 is_better_edge = false;
967 else
968 {
969 profile_count diff_count = best_count.apply_scale (1, 10);
970 if (count < best_count - diff_count
971 || (!best_count.initialized_p ()
972 && count.nonzero_p ()))
973 /* The edge and the temporary best edge have almost equivalent
974 probabilities. The higher countuency of a successor now means
975 that there is another edge going into that successor.
976 This successor has lower countuency so it is better. */
977 is_better_edge = true;
978 else if (count > best_count + diff_count)
979 /* This successor has higher countuency so it is worse. */
980 is_better_edge = false;
981 else if (e->dest->prev_bb == bb)
982 /* The edges have equivalent probabilities and the successors
983 have equivalent frequencies. Select the previous successor. */
984 is_better_edge = true;
985 else
986 is_better_edge = false;
987 }
988
989 return is_better_edge;
990}
991
992/* Return true when the edge E is better than the temporary best edge
993 CUR_BEST_EDGE. If SRC_INDEX_P is true, the function compares the src bb of
994 E and CUR_BEST_EDGE; otherwise it will compare the dest bb.
995 BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE.
996 TRACES record the information about traces.
997 When optimizing for size, the edge with smaller index is better.
998 When optimizing for speed, the edge with bigger probability or longer trace
999 is better. */
1000
1001static bool
1002connect_better_edge_p (const_edge e, bool src_index_p, int best_len,
1003 const_edge cur_best_edge, struct trace *traces)
1004{
1005 int e_index;
1006 int b_index;
1007 bool is_better_edge;
1008
1009 if (!cur_best_edge)
1010 return true;
1011
1012 if (optimize_function_for_size_p (cfun))
1013 {
1014 e_index = src_index_p ? e->src->index : e->dest->index;
1015 b_index = src_index_p ? cur_best_edge->src->index
1016 : cur_best_edge->dest->index;
1017 /* The smaller one is better to keep the original order. */
1018 return b_index > e_index;
1019 }
1020
1021 if (src_index_p)
1022 {
1023 e_index = e->src->index;
1024
1025 /* We are looking for predecessor, so probabilities are not that
1026 informative. We do not want to connect A to B becuse A has
1027 only one sucessor (probablity is 100%) while there is edge
1028 A' to B where probability is 90% but which is much more frequent. */
1029 if (e->count () > cur_best_edge->count ())
1030 /* The edge has higher probability than the temporary best edge. */
1031 is_better_edge = true;
1032 else if (e->count () < cur_best_edge->count ())
1033 /* The edge has lower probability than the temporary best edge. */
1034 is_better_edge = false;
1035 if (e->probability > cur_best_edge->probability)
1036 /* The edge has higher probability than the temporary best edge. */
1037 is_better_edge = true;
1038 else if (e->probability < cur_best_edge->probability)
1039 /* The edge has lower probability than the temporary best edge. */
1040 is_better_edge = false;
1041 else if (traces[bbd[e_index].end_of_trace].length > best_len)
1042 /* The edge and the temporary best edge have equivalent probabilities.
1043 The edge with longer trace is better. */
1044 is_better_edge = true;
1045 else
1046 is_better_edge = false;
1047 }
1048 else
1049 {
1050 e_index = e->dest->index;
1051
1052 if (e->probability > cur_best_edge->probability)
1053 /* The edge has higher probability than the temporary best edge. */
1054 is_better_edge = true;
1055 else if (e->probability < cur_best_edge->probability)
1056 /* The edge has lower probability than the temporary best edge. */
1057 is_better_edge = false;
1058 else if (traces[bbd[e_index].start_of_trace].length > best_len)
1059 /* The edge and the temporary best edge have equivalent probabilities.
1060 The edge with longer trace is better. */
1061 is_better_edge = true;
1062 else
1063 is_better_edge = false;
1064 }
1065
1066 return is_better_edge;
1067}
1068
1069/* Connect traces in array TRACES, N_TRACES is the count of traces. */
1070
1071static void
1072connect_traces (int n_traces, struct trace *traces)
1073{
1074 int i;
1075 bool *connected;
1076 bool two_passes;
1077 int last_trace;
1078 int current_pass;
1079 int current_partition;
1080 profile_count count_threshold;
1081 bool for_size = optimize_function_for_size_p (cfun);
1082
1083 count_threshold = max_entry_count.apply_scale (DUPLICATION_THRESHOLD, 1000);
1084
1085 connected = XCNEWVEC (bool, n_traces);
1086 last_trace = -1;
1087 current_pass = 1;
1088 current_partition = BB_PARTITION (traces[0].first);
1089 two_passes = false;
1090
1091 if (crtl->has_bb_partition)
1092 for (i = 0; i < n_traces && !two_passes; i++)
1093 if (BB_PARTITION (traces[0].first)
1094 != BB_PARTITION (traces[i].first))
1095 two_passes = true;
1096
1097 for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
1098 {
1099 int t = i;
1100 int t2;
1101 edge e, best;
1102 int best_len;
1103
1104 if (i >= n_traces)
1105 {
1106 gcc_assert (two_passes && current_pass == 1);
1107 i = 0;
1108 t = i;
1109 current_pass = 2;
1110 if (current_partition == BB_HOT_PARTITION)
1111 current_partition = BB_COLD_PARTITION;
1112 else
1113 current_partition = BB_HOT_PARTITION;
1114 }
1115
1116 if (connected[t])
1117 continue;
1118
1119 if (two_passes
1120 && BB_PARTITION (traces[t].first) != current_partition)
1121 continue;
1122
1123 connected[t] = true;
1124
1125 /* Find the predecessor traces. */
1126 for (t2 = t; t2 > 0;)
1127 {
1128 edge_iterator ei;
1129 best = NULL;
1130 best_len = 0;
1131 FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
1132 {
1133 int si = e->src->index;
1134
1135 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1136 && (e->flags & EDGE_CAN_FALLTHRU)
1137 && !(e->flags & EDGE_COMPLEX)
1138 && bbd[si].end_of_trace >= 0
1139 && !connected[bbd[si].end_of_trace]
1140 && (BB_PARTITION (e->src) == current_partition)
1141 && connect_better_edge_p (e, true, best_len, best, traces))
1142 {
1143 best = e;
1144 best_len = traces[bbd[si].end_of_trace].length;
1145 }
1146 }
1147 if (best)
1148 {
1149 best->src->aux = best->dest;
1150 t2 = bbd[best->src->index].end_of_trace;
1151 connected[t2] = true;
1152
1153 if (dump_file)
1154 {
1155 fprintf (dump_file, "Connection: %d %d\n",
1156 best->src->index, best->dest->index);
1157 }
1158 }
1159 else
1160 break;
1161 }
1162
1163 if (last_trace >= 0)
1164 traces[last_trace].last->aux = traces[t2].first;
1165 last_trace = t;
1166
1167 /* Find the successor traces. */
1168 while (1)
1169 {
1170 /* Find the continuation of the chain. */
1171 edge_iterator ei;
1172 best = NULL;
1173 best_len = 0;
1174 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1175 {
1176 int di = e->dest->index;
1177
1178 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1179 && (e->flags & EDGE_CAN_FALLTHRU)
1180 && !(e->flags & EDGE_COMPLEX)
1181 && bbd[di].start_of_trace >= 0
1182 && !connected[bbd[di].start_of_trace]
1183 && (BB_PARTITION (e->dest) == current_partition)
1184 && connect_better_edge_p (e, false, best_len, best, traces))
1185 {
1186 best = e;
1187 best_len = traces[bbd[di].start_of_trace].length;
1188 }
1189 }
1190
1191 if (for_size)
1192 {
1193 if (!best)
1194 /* Stop finding the successor traces. */
1195 break;
1196
1197 /* It is OK to connect block n with block n + 1 or a block
1198 before n. For others, only connect to the loop header. */
1199 if (best->dest->index > (traces[t].last->index + 1))
1200 {
1201 int count = EDGE_COUNT (best->dest->preds);
1202
1203 FOR_EACH_EDGE (e, ei, best->dest->preds)
1204 if (e->flags & EDGE_DFS_BACK)
1205 count--;
1206
1207 /* If dest has multiple predecessors, skip it. We expect
1208 that one predecessor with smaller index connects with it
1209 later. */
1210 if (count != 1)
1211 break;
1212 }
1213
1214 /* Only connect Trace n with Trace n + 1. It is conservative
1215 to keep the order as close as possible to the original order.
1216 It also helps to reduce long jumps. */
1217 if (last_trace != bbd[best->dest->index].start_of_trace - 1)
1218 break;
1219
1220 if (dump_file)
1221 fprintf (dump_file, "Connection: %d %d\n",
1222 best->src->index, best->dest->index);
1223
1224 t = bbd[best->dest->index].start_of_trace;
1225 traces[last_trace].last->aux = traces[t].first;
1226 connected[t] = true;
1227 last_trace = t;
1228 }
1229 else if (best)
1230 {
1231 if (dump_file)
1232 {
1233 fprintf (dump_file, "Connection: %d %d\n",
1234 best->src->index, best->dest->index);
1235 }
1236 t = bbd[best->dest->index].start_of_trace;
1237 traces[last_trace].last->aux = traces[t].first;
1238 connected[t] = true;
1239 last_trace = t;
1240 }
1241 else
1242 {
1243 /* Try to connect the traces by duplication of 1 block. */
1244 edge e2;
1245 basic_block next_bb = NULL;
1246 bool try_copy = false;
1247
1248 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1249 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1250 && (e->flags & EDGE_CAN_FALLTHRU)
1251 && !(e->flags & EDGE_COMPLEX)
1252 && (!best || e->probability > best->probability))
1253 {
1254 edge_iterator ei;
1255 edge best2 = NULL;
1256 int best2_len = 0;
1257
1258 /* If the destination is a start of a trace which is only
1259 one block long, then no need to search the successor
1260 blocks of the trace. Accept it. */
1261 if (bbd[e->dest->index].start_of_trace >= 0
1262 && traces[bbd[e->dest->index].start_of_trace].length
1263 == 1)
1264 {
1265 best = e;
1266 try_copy = true;
1267 continue;
1268 }
1269
1270 FOR_EACH_EDGE (e2, ei, e->dest->succs)
1271 {
1272 int di = e2->dest->index;
1273
1274 if (e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
1275 || ((e2->flags & EDGE_CAN_FALLTHRU)
1276 && !(e2->flags & EDGE_COMPLEX)
1277 && bbd[di].start_of_trace >= 0
1278 && !connected[bbd[di].start_of_trace]
1279 && BB_PARTITION (e2->dest) == current_partition
1280 && e2->count () >= count_threshold
1281 && (!best2
1282 || e2->probability > best2->probability
1283 || (e2->probability == best2->probability
1284 && traces[bbd[di].start_of_trace].length
1285 > best2_len))))
1286 {
1287 best = e;
1288 best2 = e2;
1289 if (e2->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1290 best2_len = traces[bbd[di].start_of_trace].length;
1291 else
1292 best2_len = INT_MAX;
1293 next_bb = e2->dest;
1294 try_copy = true;
1295 }
1296 }
1297 }
1298
1299 /* Copy tiny blocks always; copy larger blocks only when the
1300 edge is traversed frequently enough. */
1301 if (try_copy
1302 && BB_PARTITION (best->src) == BB_PARTITION (best->dest)
1303 && copy_bb_p (best->dest,
1304 optimize_edge_for_speed_p (best)
1305 && (!best->count ().initialized_p ()
1306 || best->count () >= count_threshold)))
1307 {
1308 basic_block new_bb;
1309
1310 if (dump_file)
1311 {
1312 fprintf (dump_file, "Connection: %d %d ",
1313 traces[t].last->index, best->dest->index);
1314 if (!next_bb)
1315 fputc ('\n', dump_file);
1316 else if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1317 fprintf (dump_file, "exit\n");
1318 else
1319 fprintf (dump_file, "%d\n", next_bb->index);
1320 }
1321
1322 new_bb = copy_bb (best->dest, best, traces[t].last, t);
1323 traces[t].last = new_bb;
1324 if (next_bb && next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1325 {
1326 t = bbd[next_bb->index].start_of_trace;
1327 traces[last_trace].last->aux = traces[t].first;
1328 connected[t] = true;
1329 last_trace = t;
1330 }
1331 else
1332 break; /* Stop finding the successor traces. */
1333 }
1334 else
1335 break; /* Stop finding the successor traces. */
1336 }
1337 }
1338 }
1339
1340 if (dump_file)
1341 {
1342 basic_block bb;
1343
1344 fprintf (dump_file, "Final order:\n");
1345 for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
1346 fprintf (dump_file, "%d ", bb->index);
1347 fprintf (dump_file, "\n");
1348 fflush (dump_file);
1349 }
1350
1351 FREE (connected);
1352}
1353
1354/* Return true when BB can and should be copied. CODE_MAY_GROW is true
1355 when code size is allowed to grow by duplication. */
1356
1357static bool
1358copy_bb_p (const_basic_block bb, int code_may_grow)
1359{
1360 int size = 0;
1361 int max_size = uncond_jump_length;
1362 rtx_insn *insn;
1363
1364 if (EDGE_COUNT (bb->preds) < 2)
1365 return false;
1366 if (!can_duplicate_block_p (bb))
1367 return false;
1368
1369 /* Avoid duplicating blocks which have many successors (PR/13430). */
1370 if (EDGE_COUNT (bb->succs) > 8)
1371 return false;
1372
1373 if (code_may_grow && optimize_bb_for_speed_p (bb))
1374 max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
1375
1376 FOR_BB_INSNS (bb, insn)
1377 {
1378 if (INSN_P (insn))
1379 size += get_attr_min_length (insn);
1380 }
1381
1382 if (size <= max_size)
1383 return true;
1384
1385 if (dump_file)
1386 {
1387 fprintf (dump_file,
1388 "Block %d can't be copied because its size = %d.\n",
1389 bb->index, size);
1390 }
1391
1392 return false;
1393}
1394
1395/* Return the length of unconditional jump instruction. */
1396
1397int
1398get_uncond_jump_length (void)
1399{
1400 int length;
1401
1402 start_sequence ();
1403 rtx_code_label *label = emit_label (gen_label_rtx ());
1404 rtx_insn *jump = emit_jump_insn (targetm.gen_jump (label));
1405 length = get_attr_min_length (jump);
1406 end_sequence ();
1407
1408 return length;
1409}
1410
1411/* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1412 Duplicate the landing pad and split the edges so that no EH edge
1413 crosses partitions. */
1414
1415static void
1416fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
1417{
1418 eh_landing_pad new_lp;
1419 basic_block new_bb, last_bb, post_bb;
1420 rtx_insn *jump;
1421 unsigned new_partition;
1422 edge_iterator ei;
1423 edge e;
1424
1425 /* Generate the new landing-pad structure. */
1426 new_lp = gen_eh_landing_pad (old_lp->region);
1427 new_lp->post_landing_pad = old_lp->post_landing_pad;
1428 new_lp->landing_pad = gen_label_rtx ();
1429 LABEL_PRESERVE_P (new_lp->landing_pad) = 1;
1430
1431 /* Put appropriate instructions in new bb. */
1432 rtx_code_label *new_label = emit_label (new_lp->landing_pad);
1433
1434 expand_dw2_landing_pad_for_region (old_lp->region);
1435
1436 post_bb = BLOCK_FOR_INSN (old_lp->landing_pad);
1437 post_bb = single_succ (post_bb);
1438 rtx_code_label *post_label = block_label (post_bb);
1439 jump = emit_jump_insn (targetm.gen_jump (post_label));
1440 JUMP_LABEL (jump) = post_label;
1441
1442 /* Create new basic block to be dest for lp. */
1443 last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
1444 new_bb = create_basic_block (new_label, jump, last_bb);
1445 new_bb->aux = last_bb->aux;
1446 new_bb->count = post_bb->count;
1447 last_bb->aux = new_bb;
1448
1449 emit_barrier_after_bb (new_bb);
1450
1451 make_single_succ_edge (new_bb, post_bb, 0);
1452
1453 /* Make sure new bb is in the other partition. */
1454 new_partition = BB_PARTITION (old_bb);
1455 new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1456 BB_SET_PARTITION (new_bb, new_partition);
1457
1458 /* Fix up the edges. */
1459 for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
1460 if (BB_PARTITION (e->src) == new_partition)
1461 {
1462 rtx_insn *insn = BB_END (e->src);
1463 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1464
1465 gcc_assert (note != NULL);
1466 gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index);
1467 XEXP (note, 0) = GEN_INT (new_lp->index);
1468
1469 /* Adjust the edge to the new destination. */
1470 redirect_edge_succ (e, new_bb);
1471 }
1472 else
1473 ei_next (&ei);
1474}
1475
1476
1477/* Ensure that all hot bbs are included in a hot path through the
1478 procedure. This is done by calling this function twice, once
1479 with WALK_UP true (to look for paths from the entry to hot bbs) and
1480 once with WALK_UP false (to look for paths from hot bbs to the exit).
1481 Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs
1482 to BBS_IN_HOT_PARTITION. */
1483
1484static unsigned int
1485sanitize_hot_paths (bool walk_up, unsigned int cold_bb_count,
1486 vec<basic_block> *bbs_in_hot_partition)
1487{
1488 /* Callers check this. */
1489 gcc_checking_assert (cold_bb_count);
1490
1491 /* Keep examining hot bbs while we still have some left to check
1492 and there are remaining cold bbs. */
1493 vec<basic_block> hot_bbs_to_check = bbs_in_hot_partition->copy ();
1494 while (! hot_bbs_to_check.is_empty ()
1495 && cold_bb_count)
1496 {
1497 basic_block bb = hot_bbs_to_check.pop ();
1498 vec<edge, va_gc> *edges = walk_up ? bb->preds : bb->succs;
1499 edge e;
1500 edge_iterator ei;
1501 profile_probability highest_probability
1502 = profile_probability::uninitialized ();
1503 profile_count highest_count = profile_count::uninitialized ();
1504 bool found = false;
1505
1506 /* Walk the preds/succs and check if there is at least one already
1507 marked hot. Keep track of the most frequent pred/succ so that we
1508 can mark it hot if we don't find one. */
1509 FOR_EACH_EDGE (e, ei, edges)
1510 {
1511 basic_block reach_bb = walk_up ? e->src : e->dest;
1512
1513 if (e->flags & EDGE_DFS_BACK)
1514 continue;
1515
1516 /* Do not expect profile insanities when profile was not adjusted. */
1517 if (e->probability == profile_probability::never ()
1518 || e->count () == profile_count::zero ())
1519 continue;
1520
1521 if (BB_PARTITION (reach_bb) != BB_COLD_PARTITION)
1522 {
1523 found = true;
1524 break;
1525 }
1526 /* The following loop will look for the hottest edge via
1527 the edge count, if it is non-zero, then fallback to
1528 the edge probability. */
1529 if (!(e->count () > highest_count))
1530 highest_count = e->count ();
1531 if (!highest_probability.initialized_p ()
1532 || e->probability > highest_probability)
1533 highest_probability = e->probability;
1534 }
1535
1536 /* If bb is reached by (or reaches, in the case of !WALK_UP) another hot
1537 block (or unpartitioned, e.g. the entry block) then it is ok. If not,
1538 then the most frequent pred (or succ) needs to be adjusted. In the
1539 case where multiple preds/succs have the same frequency (e.g. a
1540 50-50 branch), then both will be adjusted. */
1541 if (found)
1542 continue;
1543
1544 FOR_EACH_EDGE (e, ei, edges)
1545 {
1546 if (e->flags & EDGE_DFS_BACK)
1547 continue;
1548 /* Do not expect profile insanities when profile was not adjusted. */
1549 if (e->probability == profile_probability::never ()
1550 || e->count () == profile_count::zero ())
1551 continue;
1552 /* Select the hottest edge using the edge count, if it is non-zero,
1553 then fallback to the edge probability. */
1554 if (highest_count.initialized_p ())
1555 {
1556 if (!(e->count () >= highest_count))
1557 continue;
1558 }
1559 else if (!(e->probability >= highest_probability))
1560 continue;
1561
1562 basic_block reach_bb = walk_up ? e->src : e->dest;
1563
1564 /* We have a hot bb with an immediate dominator that is cold.
1565 The dominator needs to be re-marked hot. */
1566 BB_SET_PARTITION (reach_bb, BB_HOT_PARTITION);
1567 if (dump_file)
1568 fprintf (dump_file, "Promoting bb %i to hot partition to sanitize "
1569 "profile of bb %i in %s walk\n", reach_bb->index,
1570 bb->index, walk_up ? "backward" : "forward");
1571 cold_bb_count--;
1572
1573 /* Now we need to examine newly-hot reach_bb to see if it is also
1574 dominated by a cold bb. */
1575 bbs_in_hot_partition->safe_push (reach_bb);
1576 hot_bbs_to_check.safe_push (reach_bb);
1577 }
1578 }
1579
1580 return cold_bb_count;
1581}
1582
1583
1584/* Find the basic blocks that are rarely executed and need to be moved to
1585 a separate section of the .o file (to cut down on paging and improve
1586 cache locality). Return a vector of all edges that cross. */
1587
1588static vec<edge>
1589find_rarely_executed_basic_blocks_and_crossing_edges (void)
1590{
1591 vec<edge> crossing_edges = vNULL;
1592 basic_block bb;
1593 edge e;
1594 edge_iterator ei;
1595 unsigned int cold_bb_count = 0;
1596 auto_vec<basic_block> bbs_in_hot_partition;
1597
1598 propagate_unlikely_bbs_forward ();
1599
1600 /* Mark which partition (hot/cold) each basic block belongs in. */
1601 FOR_EACH_BB_FN (bb, cfun)
1602 {
1603 bool cold_bb = false;
1604
1605 if (probably_never_executed_bb_p (cfun, bb))
1606 {
1607 /* Handle profile insanities created by upstream optimizations
1608 by also checking the incoming edge weights. If there is a non-cold
1609 incoming edge, conservatively prevent this block from being split
1610 into the cold section. */
1611 cold_bb = true;
1612 FOR_EACH_EDGE (e, ei, bb->preds)
1613 if (!probably_never_executed_edge_p (cfun, e))
1614 {
1615 cold_bb = false;
1616 break;
1617 }
1618 }
1619 if (cold_bb)
1620 {
1621 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1622 cold_bb_count++;
1623 }
1624 else
1625 {
1626 BB_SET_PARTITION (bb, BB_HOT_PARTITION);
1627 bbs_in_hot_partition.safe_push (bb);
1628 }
1629 }
1630
1631 /* Ensure that hot bbs are included along a hot path from the entry to exit.
1632 Several different possibilities may include cold bbs along all paths
1633 to/from a hot bb. One is that there are edge weight insanities
1634 due to optimization phases that do not properly update basic block profile
1635 counts. The second is that the entry of the function may not be hot, because
1636 it is entered fewer times than the number of profile training runs, but there
1637 is a loop inside the function that causes blocks within the function to be
1638 above the threshold for hotness. This is fixed by walking up from hot bbs
1639 to the entry block, and then down from hot bbs to the exit, performing
1640 partitioning fixups as necessary. */
1641 if (cold_bb_count)
1642 {
1643 mark_dfs_back_edges ();
1644 cold_bb_count = sanitize_hot_paths (true, cold_bb_count,
1645 &bbs_in_hot_partition);
1646 if (cold_bb_count)
1647 sanitize_hot_paths (false, cold_bb_count, &bbs_in_hot_partition);
1648
1649 hash_set <basic_block> set;
1650 find_bbs_reachable_by_hot_paths (&set);
1651 FOR_EACH_BB_FN (bb, cfun)
1652 if (!set.contains (bb))
1653 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1654 }
1655
1656 /* The format of .gcc_except_table does not allow landing pads to
1657 be in a different partition as the throw. Fix this by either
1658 moving or duplicating the landing pads. */
1659 if (cfun->eh->lp_array)
1660 {
1661 unsigned i;
1662 eh_landing_pad lp;
1663
1664 FOR_EACH_VEC_ELT (*cfun->eh->lp_array, i, lp)
1665 {
1666 bool all_same, all_diff;
1667
1668 if (lp == NULL
1669 || lp->landing_pad == NULL_RTX
1670 || !LABEL_P (lp->landing_pad))
1671 continue;
1672
1673 all_same = all_diff = true;
1674 bb = BLOCK_FOR_INSN (lp->landing_pad);
1675 FOR_EACH_EDGE (e, ei, bb->preds)
1676 {
1677 gcc_assert (e->flags & EDGE_EH);
1678 if (BB_PARTITION (bb) == BB_PARTITION (e->src))
1679 all_diff = false;
1680 else
1681 all_same = false;
1682 }
1683
1684 if (all_same)
1685 ;
1686 else if (all_diff)
1687 {
1688 int which = BB_PARTITION (bb);
1689 which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1690 BB_SET_PARTITION (bb, which);
1691 }
1692 else
1693 fix_up_crossing_landing_pad (lp, bb);
1694 }
1695 }
1696
1697 /* Mark every edge that crosses between sections. */
1698
1699 FOR_EACH_BB_FN (bb, cfun)
1700 FOR_EACH_EDGE (e, ei, bb->succs)
1701 {
1702 unsigned int flags = e->flags;
1703
1704 /* We should never have EDGE_CROSSING set yet. */
1705 gcc_checking_assert ((flags & EDGE_CROSSING) == 0);
1706
1707 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1708 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1709 && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1710 {
1711 crossing_edges.safe_push (e);
1712 flags |= EDGE_CROSSING;
1713 }
1714
1715 /* Now that we've split eh edges as appropriate, allow landing pads
1716 to be merged with the post-landing pads. */
1717 flags &= ~EDGE_PRESERVE;
1718
1719 e->flags = flags;
1720 }
1721
1722 return crossing_edges;
1723}
1724
1725/* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
1726
1727static void
1728set_edge_can_fallthru_flag (void)
1729{
1730 basic_block bb;
1731
1732 FOR_EACH_BB_FN (bb, cfun)
1733 {
1734 edge e;
1735 edge_iterator ei;
1736
1737 FOR_EACH_EDGE (e, ei, bb->succs)
1738 {
1739 e->flags &= ~EDGE_CAN_FALLTHRU;
1740
1741 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
1742 if (e->flags & EDGE_FALLTHRU)
1743 e->flags |= EDGE_CAN_FALLTHRU;
1744 }
1745
1746 /* If the BB ends with an invertible condjump all (2) edges are
1747 CAN_FALLTHRU edges. */
1748 if (EDGE_COUNT (bb->succs) != 2)
1749 continue;
1750 if (!any_condjump_p (BB_END (bb)))
1751 continue;
1752
1753 rtx_jump_insn *bb_end_jump = as_a <rtx_jump_insn *> (BB_END (bb));
1754 if (!invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0))
1755 continue;
1756 invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0);
1757 EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
1758 EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
1759 }
1760}
1761
1762/* If any destination of a crossing edge does not have a label, add label;
1763 Convert any easy fall-through crossing edges to unconditional jumps. */
1764
1765static void
1766add_labels_and_missing_jumps (vec<edge> crossing_edges)
1767{
1768 size_t i;
1769 edge e;
1770
1771 FOR_EACH_VEC_ELT (crossing_edges, i, e)
1772 {
1773 basic_block src = e->src;
1774 basic_block dest = e->dest;
1775 rtx_jump_insn *new_jump;
1776
1777 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1778 continue;
1779
1780 /* Make sure dest has a label. */
1781 rtx_code_label *label = block_label (dest);
1782
1783 /* Nothing to do for non-fallthru edges. */
1784 if (src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1785 continue;
1786 if ((e->flags & EDGE_FALLTHRU) == 0)
1787 continue;
1788
1789 /* If the block does not end with a control flow insn, then we
1790 can trivially add a jump to the end to fixup the crossing.
1791 Otherwise the jump will have to go in a new bb, which will
1792 be handled by fix_up_fall_thru_edges function. */
1793 if (control_flow_insn_p (BB_END (src)))
1794 continue;
1795
1796 /* Make sure there's only one successor. */
1797 gcc_assert (single_succ_p (src));
1798
1799 new_jump = emit_jump_insn_after (targetm.gen_jump (label), BB_END (src));
1800 BB_END (src) = new_jump;
1801 JUMP_LABEL (new_jump) = label;
1802 LABEL_NUSES (label) += 1;
1803
1804 emit_barrier_after_bb (src);
1805
1806 /* Mark edge as non-fallthru. */
1807 e->flags &= ~EDGE_FALLTHRU;
1808 }
1809}
1810
1811/* Find any bb's where the fall-through edge is a crossing edge (note that
1812 these bb's must also contain a conditional jump or end with a call
1813 instruction; we've already dealt with fall-through edges for blocks
1814 that didn't have a conditional jump or didn't end with call instruction
1815 in the call to add_labels_and_missing_jumps). Convert the fall-through
1816 edge to non-crossing edge by inserting a new bb to fall-through into.
1817 The new bb will contain an unconditional jump (crossing edge) to the
1818 original fall through destination. */
1819
1820static void
1821fix_up_fall_thru_edges (void)
1822{
1823 basic_block cur_bb;
1824
1825 FOR_EACH_BB_FN (cur_bb, cfun)
1826 {
1827 edge succ1;
1828 edge succ2;
1829 edge fall_thru = NULL;
1830 edge cond_jump = NULL;
1831
1832 fall_thru = NULL;
1833 if (EDGE_COUNT (cur_bb->succs) > 0)
1834 succ1 = EDGE_SUCC (cur_bb, 0);
1835 else
1836 succ1 = NULL;
1837
1838 if (EDGE_COUNT (cur_bb->succs) > 1)
1839 succ2 = EDGE_SUCC (cur_bb, 1);
1840 else
1841 succ2 = NULL;
1842
1843 /* Find the fall-through edge. */
1844
1845 if (succ1
1846 && (succ1->flags & EDGE_FALLTHRU))
1847 {
1848 fall_thru = succ1;
1849 cond_jump = succ2;
1850 }
1851 else if (succ2
1852 && (succ2->flags & EDGE_FALLTHRU))
1853 {
1854 fall_thru = succ2;
1855 cond_jump = succ1;
1856 }
1857 else if (succ2 && EDGE_COUNT (cur_bb->succs) > 2)
1858 fall_thru = find_fallthru_edge (cur_bb->succs);
1859
1860 if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)))
1861 {
1862 /* Check to see if the fall-thru edge is a crossing edge. */
1863
1864 if (fall_thru->flags & EDGE_CROSSING)
1865 {
1866 /* The fall_thru edge crosses; now check the cond jump edge, if
1867 it exists. */
1868
1869 bool cond_jump_crosses = true;
1870 int invert_worked = 0;
1871 rtx_insn *old_jump = BB_END (cur_bb);
1872
1873 /* Find the jump instruction, if there is one. */
1874
1875 if (cond_jump)
1876 {
1877 if (!(cond_jump->flags & EDGE_CROSSING))
1878 cond_jump_crosses = false;
1879
1880 /* We know the fall-thru edge crosses; if the cond
1881 jump edge does NOT cross, and its destination is the
1882 next block in the bb order, invert the jump
1883 (i.e. fix it so the fall through does not cross and
1884 the cond jump does). */
1885
1886 if (!cond_jump_crosses)
1887 {
1888 /* Find label in fall_thru block. We've already added
1889 any missing labels, so there must be one. */
1890
1891 rtx_code_label *fall_thru_label
1892 = block_label (fall_thru->dest);
1893
1894 if (old_jump && fall_thru_label)
1895 {
1896 rtx_jump_insn *old_jump_insn
1897 = dyn_cast <rtx_jump_insn *> (old_jump);
1898 if (old_jump_insn)
1899 invert_worked = invert_jump (old_jump_insn,
1900 fall_thru_label, 0);
1901 }
1902
1903 if (invert_worked)
1904 {
1905 fall_thru->flags &= ~EDGE_FALLTHRU;
1906 cond_jump->flags |= EDGE_FALLTHRU;
1907 update_br_prob_note (cur_bb);
1908 std::swap (fall_thru, cond_jump);
1909 cond_jump->flags |= EDGE_CROSSING;
1910 fall_thru->flags &= ~EDGE_CROSSING;
1911 }
1912 }
1913 }
1914
1915 if (cond_jump_crosses || !invert_worked)
1916 {
1917 /* This is the case where both edges out of the basic
1918 block are crossing edges. Here we will fix up the
1919 fall through edge. The jump edge will be taken care
1920 of later. The EDGE_CROSSING flag of fall_thru edge
1921 is unset before the call to force_nonfallthru
1922 function because if a new basic-block is created
1923 this edge remains in the current section boundary
1924 while the edge between new_bb and the fall_thru->dest
1925 becomes EDGE_CROSSING. */
1926
1927 fall_thru->flags &= ~EDGE_CROSSING;
1928 basic_block new_bb = force_nonfallthru (fall_thru);
1929
1930 if (new_bb)
1931 {
1932 new_bb->aux = cur_bb->aux;
1933 cur_bb->aux = new_bb;
1934
1935 /* This is done by force_nonfallthru_and_redirect. */
1936 gcc_assert (BB_PARTITION (new_bb)
1937 == BB_PARTITION (cur_bb));
1938
1939 single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
1940 }
1941 else
1942 {
1943 /* If a new basic-block was not created; restore
1944 the EDGE_CROSSING flag. */
1945 fall_thru->flags |= EDGE_CROSSING;
1946 }
1947
1948 /* Add barrier after new jump */
1949 emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
1950 }
1951 }
1952 }
1953 }
1954}
1955
1956/* This function checks the destination block of a "crossing jump" to
1957 see if it has any crossing predecessors that begin with a code label
1958 and end with an unconditional jump. If so, it returns that predecessor
1959 block. (This is to avoid creating lots of new basic blocks that all
1960 contain unconditional jumps to the same destination). */
1961
1962static basic_block
1963find_jump_block (basic_block jump_dest)
1964{
1965 basic_block source_bb = NULL;
1966 edge e;
1967 rtx_insn *insn;
1968 edge_iterator ei;
1969
1970 FOR_EACH_EDGE (e, ei, jump_dest->preds)
1971 if (e->flags & EDGE_CROSSING)
1972 {
1973 basic_block src = e->src;
1974
1975 /* Check each predecessor to see if it has a label, and contains
1976 only one executable instruction, which is an unconditional jump.
1977 If so, we can use it. */
1978
1979 if (LABEL_P (BB_HEAD (src)))
1980 for (insn = BB_HEAD (src);
1981 !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
1982 insn = NEXT_INSN (insn))
1983 {
1984 if (INSN_P (insn)
1985 && insn == BB_END (src)
1986 && JUMP_P (insn)
1987 && !any_condjump_p (insn))
1988 {
1989 source_bb = src;
1990 break;
1991 }
1992 }
1993
1994 if (source_bb)
1995 break;
1996 }
1997
1998 return source_bb;
1999}
2000
2001/* Find all BB's with conditional jumps that are crossing edges;
2002 insert a new bb and make the conditional jump branch to the new
2003 bb instead (make the new bb same color so conditional branch won't
2004 be a 'crossing' edge). Insert an unconditional jump from the
2005 new bb to the original destination of the conditional jump. */
2006
2007static void
2008fix_crossing_conditional_branches (void)
2009{
2010 basic_block cur_bb;
2011 basic_block new_bb;
2012 basic_block dest;
2013 edge succ1;
2014 edge succ2;
2015 edge crossing_edge;
2016 edge new_edge;
2017 rtx set_src;
2018 rtx old_label = NULL_RTX;
2019 rtx_code_label *new_label;
2020
2021 FOR_EACH_BB_FN (cur_bb, cfun)
2022 {
2023 crossing_edge = NULL;
2024 if (EDGE_COUNT (cur_bb->succs) > 0)
2025 succ1 = EDGE_SUCC (cur_bb, 0);
2026 else
2027 succ1 = NULL;
2028
2029 if (EDGE_COUNT (cur_bb->succs) > 1)
2030 succ2 = EDGE_SUCC (cur_bb, 1);
2031 else
2032 succ2 = NULL;
2033
2034 /* We already took care of fall-through edges, so only one successor
2035 can be a crossing edge. */
2036
2037 if (succ1 && (succ1->flags & EDGE_CROSSING))
2038 crossing_edge = succ1;
2039 else if (succ2 && (succ2->flags & EDGE_CROSSING))
2040 crossing_edge = succ2;
2041
2042 if (crossing_edge)
2043 {
2044 rtx_insn *old_jump = BB_END (cur_bb);
2045
2046 /* Check to make sure the jump instruction is a
2047 conditional jump. */
2048
2049 set_src = NULL_RTX;
2050
2051 if (any_condjump_p (old_jump))
2052 {
2053 if (GET_CODE (PATTERN (old_jump)) == SET)
2054 set_src = SET_SRC (PATTERN (old_jump));
2055 else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
2056 {
2057 set_src = XVECEXP (PATTERN (old_jump), 0,0);
2058 if (GET_CODE (set_src) == SET)
2059 set_src = SET_SRC (set_src);
2060 else
2061 set_src = NULL_RTX;
2062 }
2063 }
2064
2065 if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
2066 {
2067 rtx_jump_insn *old_jump_insn =
2068 as_a <rtx_jump_insn *> (old_jump);
2069
2070 if (GET_CODE (XEXP (set_src, 1)) == PC)
2071 old_label = XEXP (set_src, 2);
2072 else if (GET_CODE (XEXP (set_src, 2)) == PC)
2073 old_label = XEXP (set_src, 1);
2074
2075 /* Check to see if new bb for jumping to that dest has
2076 already been created; if so, use it; if not, create
2077 a new one. */
2078
2079 new_bb = find_jump_block (crossing_edge->dest);
2080
2081 if (new_bb)
2082 new_label = block_label (new_bb);
2083 else
2084 {
2085 basic_block last_bb;
2086 rtx_code_label *old_jump_target;
2087 rtx_jump_insn *new_jump;
2088
2089 /* Create new basic block to be dest for
2090 conditional jump. */
2091
2092 /* Put appropriate instructions in new bb. */
2093
2094 new_label = gen_label_rtx ();
2095 emit_label (new_label);
2096
2097 gcc_assert (GET_CODE (old_label) == LABEL_REF);
2098 old_jump_target = old_jump_insn->jump_target ();
2099 new_jump = as_a <rtx_jump_insn *>
2100 (emit_jump_insn (targetm.gen_jump (old_jump_target)));
2101 new_jump->set_jump_target (old_jump_target);
2102
2103 last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
2104 new_bb = create_basic_block (new_label, new_jump, last_bb);
2105 new_bb->aux = last_bb->aux;
2106 last_bb->aux = new_bb;
2107
2108 emit_barrier_after_bb (new_bb);
2109
2110 /* Make sure new bb is in same partition as source
2111 of conditional branch. */
2112 BB_COPY_PARTITION (new_bb, cur_bb);
2113 }
2114
2115 /* Make old jump branch to new bb. */
2116
2117 redirect_jump (old_jump_insn, new_label, 0);
2118
2119 /* Remove crossing_edge as predecessor of 'dest'. */
2120
2121 dest = crossing_edge->dest;
2122
2123 redirect_edge_succ (crossing_edge, new_bb);
2124
2125 /* Make a new edge from new_bb to old dest; new edge
2126 will be a successor for new_bb and a predecessor
2127 for 'dest'. */
2128
2129 if (EDGE_COUNT (new_bb->succs) == 0)
2130 new_edge = make_single_succ_edge (new_bb, dest, 0);
2131 else
2132 new_edge = EDGE_SUCC (new_bb, 0);
2133
2134 crossing_edge->flags &= ~EDGE_CROSSING;
2135 new_edge->flags |= EDGE_CROSSING;
2136 }
2137 }
2138 }
2139}
2140
2141/* Find any unconditional branches that cross between hot and cold
2142 sections. Convert them into indirect jumps instead. */
2143
2144static void
2145fix_crossing_unconditional_branches (void)
2146{
2147 basic_block cur_bb;
2148 rtx_insn *last_insn;
2149 rtx label;
2150 rtx label_addr;
2151 rtx_insn *indirect_jump_sequence;
2152 rtx_insn *jump_insn = NULL;
2153 rtx new_reg;
2154 rtx_insn *cur_insn;
2155 edge succ;
2156
2157 FOR_EACH_BB_FN (cur_bb, cfun)
2158 {
2159 last_insn = BB_END (cur_bb);
2160
2161 if (EDGE_COUNT (cur_bb->succs) < 1)
2162 continue;
2163
2164 succ = EDGE_SUCC (cur_bb, 0);
2165
2166 /* Check to see if bb ends in a crossing (unconditional) jump. At
2167 this point, no crossing jumps should be conditional. */
2168
2169 if (JUMP_P (last_insn)
2170 && (succ->flags & EDGE_CROSSING))
2171 {
2172 gcc_assert (!any_condjump_p (last_insn));
2173
2174 /* Make sure the jump is not already an indirect or table jump. */
2175
2176 if (!computed_jump_p (last_insn)
2177 && !tablejump_p (last_insn, NULL, NULL))
2178 {
2179 /* We have found a "crossing" unconditional branch. Now
2180 we must convert it to an indirect jump. First create
2181 reference of label, as target for jump. */
2182
2183 label = JUMP_LABEL (last_insn);
2184 label_addr = gen_rtx_LABEL_REF (Pmode, label);
2185 LABEL_NUSES (label) += 1;
2186
2187 /* Get a register to use for the indirect jump. */
2188
2189 new_reg = gen_reg_rtx (Pmode);
2190
2191 /* Generate indirect the jump sequence. */
2192
2193 start_sequence ();
2194 emit_move_insn (new_reg, label_addr);
2195 emit_indirect_jump (new_reg);
2196 indirect_jump_sequence = get_insns ();
2197 end_sequence ();
2198
2199 /* Make sure every instruction in the new jump sequence has
2200 its basic block set to be cur_bb. */
2201
2202 for (cur_insn = indirect_jump_sequence; cur_insn;
2203 cur_insn = NEXT_INSN (cur_insn))
2204 {
2205 if (!BARRIER_P (cur_insn))
2206 BLOCK_FOR_INSN (cur_insn) = cur_bb;
2207 if (JUMP_P (cur_insn))
2208 jump_insn = cur_insn;
2209 }
2210
2211 /* Insert the new (indirect) jump sequence immediately before
2212 the unconditional jump, then delete the unconditional jump. */
2213
2214 emit_insn_before (indirect_jump_sequence, last_insn);
2215 delete_insn (last_insn);
2216
2217 JUMP_LABEL (jump_insn) = label;
2218 LABEL_NUSES (label)++;
2219
2220 /* Make BB_END for cur_bb be the jump instruction (NOT the
2221 barrier instruction at the end of the sequence...). */
2222
2223 BB_END (cur_bb) = jump_insn;
2224 }
2225 }
2226 }
2227}
2228
2229/* Update CROSSING_JUMP_P flags on all jump insns. */
2230
2231static void
2232update_crossing_jump_flags (void)
2233{
2234 basic_block bb;
2235 edge e;
2236 edge_iterator ei;
2237
2238 FOR_EACH_BB_FN (bb, cfun)
2239 FOR_EACH_EDGE (e, ei, bb->succs)
2240 if (e->flags & EDGE_CROSSING)
2241 {
2242 if (JUMP_P (BB_END (bb)))
2243 CROSSING_JUMP_P (BB_END (bb)) = 1;
2244 break;
2245 }
2246}
2247
2248/* Reorder basic blocks using the software trace cache (STC) algorithm. */
2249
2250static void
2251reorder_basic_blocks_software_trace_cache (void)
2252{
2253 if (dump_file)
2254 fprintf (dump_file, "\nReordering with the STC algorithm.\n\n");
2255
2256 int n_traces;
2257 int i;
2258 struct trace *traces;
2259
2260 /* We are estimating the length of uncond jump insn only once since the code
2261 for getting the insn length always returns the minimal length now. */
2262 if (uncond_jump_length == 0)
2263 uncond_jump_length = get_uncond_jump_length ();
2264
2265 /* We need to know some information for each basic block. */
2266 array_size = GET_ARRAY_SIZE (last_basic_block_for_fn (cfun));
2267 bbd = XNEWVEC (bbro_basic_block_data, array_size);
2268 for (i = 0; i < array_size; i++)
2269 {
2270 bbd[i].start_of_trace = -1;
2271 bbd[i].end_of_trace = -1;
2272 bbd[i].in_trace = -1;
2273 bbd[i].visited = 0;
2274 bbd[i].priority = -1;
2275 bbd[i].heap = NULL;
2276 bbd[i].node = NULL;
2277 }
2278
2279 traces = XNEWVEC (struct trace, n_basic_blocks_for_fn (cfun));
2280 n_traces = 0;
2281 find_traces (&n_traces, traces);
2282 connect_traces (n_traces, traces);
2283 FREE (traces);
2284 FREE (bbd);
2285}
2286
2287/* Return true if edge E1 is more desirable as a fallthrough edge than
2288 edge E2 is. */
2289
2290static bool
2291edge_order (edge e1, edge e2)
2292{
2293 return e1->count () > e2->count ();
2294}
2295
2296/* Reorder basic blocks using the "simple" algorithm. This tries to
2297 maximize the dynamic number of branches that are fallthrough, without
2298 copying instructions. The algorithm is greedy, looking at the most
2299 frequently executed branch first. */
2300
2301static void
2302reorder_basic_blocks_simple (void)
2303{
2304 if (dump_file)
2305 fprintf (dump_file, "\nReordering with the \"simple\" algorithm.\n\n");
2306
2307 edge *edges = new edge[2 * n_basic_blocks_for_fn (cfun)];
2308
2309 /* First, collect all edges that can be optimized by reordering blocks:
2310 simple jumps and conditional jumps, as well as the function entry edge. */
2311
2312 int n = 0;
2313 edges[n++] = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0);
2314
2315 basic_block bb;
2316 FOR_EACH_BB_FN (bb, cfun)
2317 {
2318 rtx_insn *end = BB_END (bb);
2319
2320 if (computed_jump_p (end) || tablejump_p (end, NULL, NULL))
2321 continue;
2322
2323 /* We cannot optimize asm goto. */
2324 if (JUMP_P (end) && extract_asm_operands (end))
2325 continue;
2326
2327 if (single_succ_p (bb))
2328 edges[n++] = EDGE_SUCC (bb, 0);
2329 else if (any_condjump_p (end))
2330 {
2331 edge e0 = EDGE_SUCC (bb, 0);
2332 edge e1 = EDGE_SUCC (bb, 1);
2333 /* When optimizing for size it is best to keep the original
2334 fallthrough edges. */
2335 if (e1->flags & EDGE_FALLTHRU)
2336 std::swap (e0, e1);
2337 edges[n++] = e0;
2338 edges[n++] = e1;
2339 }
2340 }
2341
2342 /* Sort the edges, the most desirable first. When optimizing for size
2343 all edges are equally desirable. */
2344
2345 if (optimize_function_for_speed_p (cfun))
2346 std::stable_sort (edges, edges + n, edge_order);
2347
2348 /* Now decide which of those edges to make fallthrough edges. We set
2349 BB_VISITED if a block already has a fallthrough successor assigned
2350 to it. We make ->AUX of an endpoint point to the opposite endpoint
2351 of a sequence of blocks that fall through, and ->AUX will be NULL
2352 for a block that is in such a sequence but not an endpoint anymore.
2353
2354 To start with, everything points to itself, nothing is assigned yet. */
2355
2356 FOR_ALL_BB_FN (bb, cfun)
2357 {
2358 bb->aux = bb;
2359 bb->flags &= ~BB_VISITED;
2360 }
2361
2362 EXIT_BLOCK_PTR_FOR_FN (cfun)->aux = 0;
2363
2364 /* Now for all edges, the most desirable first, see if that edge can
2365 connect two sequences. If it can, update AUX and BB_VISITED; if it
2366 cannot, zero out the edge in the table. */
2367
2368 for (int j = 0; j < n; j++)
2369 {
2370 edge e = edges[j];
2371
2372 basic_block tail_a = e->src;
2373 basic_block head_b = e->dest;
2374 basic_block head_a = (basic_block) tail_a->aux;
2375 basic_block tail_b = (basic_block) head_b->aux;
2376
2377 /* An edge cannot connect two sequences if:
2378 - it crosses partitions;
2379 - its src is not a current endpoint;
2380 - its dest is not a current endpoint;
2381 - or, it would create a loop. */
2382
2383 if (e->flags & EDGE_CROSSING
2384 || tail_a->flags & BB_VISITED
2385 || !tail_b
2386 || (!(head_b->flags & BB_VISITED) && head_b != tail_b)
2387 || tail_a == tail_b)
2388 {
2389 edges[j] = 0;
2390 continue;
2391 }
2392
2393 tail_a->aux = 0;
2394 head_b->aux = 0;
2395 head_a->aux = tail_b;
2396 tail_b->aux = head_a;
2397 tail_a->flags |= BB_VISITED;
2398 }
2399
2400 /* Put the pieces together, in the same order that the start blocks of
2401 the sequences already had. The hot/cold partitioning gives a little
2402 complication: as a first pass only do this for blocks in the same
2403 partition as the start block, and (if there is anything left to do)
2404 in a second pass handle the other partition. */
2405
2406 basic_block last_tail = (basic_block) ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux;
2407
2408 int current_partition = BB_PARTITION (last_tail);
2409 bool need_another_pass = true;
2410
2411 for (int pass = 0; pass < 2 && need_another_pass; pass++)
2412 {
2413 need_another_pass = false;
2414
2415 FOR_EACH_BB_FN (bb, cfun)
2416 if ((bb->flags & BB_VISITED && bb->aux) || bb->aux == bb)
2417 {
2418 if (BB_PARTITION (bb) != current_partition)
2419 {
2420 need_another_pass = true;
2421 continue;
2422 }
2423
2424 last_tail->aux = bb;
2425 last_tail = (basic_block) bb->aux;
2426 }
2427
2428 current_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
2429 }
2430
2431 last_tail->aux = 0;
2432
2433 /* Finally, link all the chosen fallthrough edges. */
2434
2435 for (int j = 0; j < n; j++)
2436 if (edges[j])
2437 edges[j]->src->aux = edges[j]->dest;
2438
2439 delete[] edges;
2440
2441 /* If the entry edge no longer falls through we have to make a new
2442 block so it can do so again. */
2443
2444 edge e = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0);
2445 if (e->dest != ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux)
2446 {
2447 force_nonfallthru (e);
2448 e->src->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux;
2449 BB_COPY_PARTITION (e->src, e->dest);
2450 }
2451}
2452
2453/* Reorder basic blocks. The main entry point to this file. */
2454
2455static void
2456reorder_basic_blocks (void)
2457{
2458 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
2459
2460 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1)
2461 return;
2462
2463 set_edge_can_fallthru_flag ();
2464 mark_dfs_back_edges ();
2465
2466 switch (flag_reorder_blocks_algorithm)
2467 {
2468 case REORDER_BLOCKS_ALGORITHM_SIMPLE:
2469 reorder_basic_blocks_simple ();
2470 break;
2471
2472 case REORDER_BLOCKS_ALGORITHM_STC:
2473 reorder_basic_blocks_software_trace_cache ();
2474 break;
2475
2476 default:
2477 gcc_unreachable ();
2478 }
2479
2480 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
2481
2482 if (dump_file)
2483 {
2484 if (dump_flags & TDF_DETAILS)
2485 dump_reg_info (dump_file);
2486 dump_flow_info (dump_file, dump_flags);
2487 }
2488
2489 /* Signal that rtl_verify_flow_info_1 can now verify that there
2490 is at most one switch between hot/cold sections. */
2491 crtl->bb_reorder_complete = true;
2492}
2493
2494/* Determine which partition the first basic block in the function
2495 belongs to, then find the first basic block in the current function
2496 that belongs to a different section, and insert a
2497 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
2498 instruction stream. When writing out the assembly code,
2499 encountering this note will make the compiler switch between the
2500 hot and cold text sections. */
2501
2502void
2503insert_section_boundary_note (void)
2504{
2505 basic_block bb;
2506 bool switched_sections = false;
2507 int current_partition = 0;
2508
2509 if (!crtl->has_bb_partition)
2510 return;
2511
2512 FOR_EACH_BB_FN (bb, cfun)
2513 {
2514 if (!current_partition)
2515 current_partition = BB_PARTITION (bb);
2516 if (BB_PARTITION (bb) != current_partition)
2517 {
2518 gcc_assert (!switched_sections);
2519 switched_sections = true;
2520 emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS, BB_HEAD (bb));
2521 current_partition = BB_PARTITION (bb);
2522 }
2523 }
2524}
2525
2526namespace {
2527
2528const pass_data pass_data_reorder_blocks =
2529{
2530 RTL_PASS, /* type */
2531 "bbro", /* name */
2532 OPTGROUP_NONE, /* optinfo_flags */
2533 TV_REORDER_BLOCKS, /* tv_id */
2534 0, /* properties_required */
2535 0, /* properties_provided */
2536 0, /* properties_destroyed */
2537 0, /* todo_flags_start */
2538 0, /* todo_flags_finish */
2539};
2540
2541class pass_reorder_blocks : public rtl_opt_pass
2542{
2543public:
2544 pass_reorder_blocks (gcc::context *ctxt)
2545 : rtl_opt_pass (pass_data_reorder_blocks, ctxt)
2546 {}
2547
2548 /* opt_pass methods: */
2549 virtual bool gate (function *)
2550 {
2551 if (targetm.cannot_modify_jumps_p ())
2552 return false;
2553 return (optimize > 0
2554 && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
2555 }
2556
2557 virtual unsigned int execute (function *);
2558
2559}; // class pass_reorder_blocks
2560
2561unsigned int
2562pass_reorder_blocks::execute (function *fun)
2563{
2564 basic_block bb;
2565
2566 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2567 splitting possibly introduced more crossjumping opportunities. */
2568 cfg_layout_initialize (CLEANUP_EXPENSIVE);
2569
2570 reorder_basic_blocks ();
2571 cleanup_cfg (CLEANUP_EXPENSIVE);
2572
2573 FOR_EACH_BB_FN (bb, fun)
2574 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
2575 bb->aux = bb->next_bb;
2576 cfg_layout_finalize ();
2577
2578 return 0;
2579}
2580
2581} // anon namespace
2582
2583rtl_opt_pass *
2584make_pass_reorder_blocks (gcc::context *ctxt)
2585{
2586 return new pass_reorder_blocks (ctxt);
2587}
2588
2589/* Duplicate a block (that we already know ends in a computed jump) into its
2590 predecessors, where possible. Return whether anything is changed. */
2591static bool
2592maybe_duplicate_computed_goto (basic_block bb, int max_size)
2593{
2594 if (single_pred_p (bb))
2595 return false;
2596
2597 /* Make sure that the block is small enough. */
2598 rtx_insn *insn;
2599 FOR_BB_INSNS (bb, insn)
2600 if (INSN_P (insn))
2601 {
2602 max_size -= get_attr_min_length (insn);
2603 if (max_size < 0)
2604 return false;
2605 }
2606
2607 bool changed = false;
2608 edge e;
2609 edge_iterator ei;
2610 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
2611 {
2612 basic_block pred = e->src;
2613
2614 /* Do not duplicate BB into PRED if that is the last predecessor, or if
2615 we cannot merge a copy of BB with PRED. */
2616 if (single_pred_p (bb)
2617 || !single_succ_p (pred)
2618 || e->flags & EDGE_COMPLEX
2619 || pred->index < NUM_FIXED_BLOCKS
2620 || (JUMP_P (BB_END (pred)) && !simplejump_p (BB_END (pred)))
2621 || (JUMP_P (BB_END (pred)) && CROSSING_JUMP_P (BB_END (pred))))
2622 {
2623 ei_next (&ei);
2624 continue;
2625 }
2626
2627 if (dump_file)
2628 fprintf (dump_file, "Duplicating computed goto bb %d into bb %d\n",
2629 bb->index, e->src->index);
2630
2631 /* Remember if PRED can be duplicated; if so, the copy of BB merged
2632 with PRED can be duplicated as well. */
2633 bool can_dup_more = can_duplicate_block_p (pred);
2634
2635 /* Make a copy of BB, merge it into PRED. */
2636 basic_block copy = duplicate_block (bb, e, NULL);
2637 emit_barrier_after_bb (copy);
2638 reorder_insns_nobb (BB_HEAD (copy), BB_END (copy), BB_END (pred));
2639 merge_blocks (pred, copy);
2640
2641 changed = true;
2642
2643 /* Try to merge the resulting merged PRED into further predecessors. */
2644 if (can_dup_more)
2645 maybe_duplicate_computed_goto (pred, max_size);
2646 }
2647
2648 return changed;
2649}
2650
2651/* Duplicate the blocks containing computed gotos. This basically unfactors
2652 computed gotos that were factored early on in the compilation process to
2653 speed up edge based data flow. We used to not unfactor them again, which
2654 can seriously pessimize code with many computed jumps in the source code,
2655 such as interpreters. See e.g. PR15242. */
2656static void
2657duplicate_computed_gotos (function *fun)
2658{
2659 /* We are estimating the length of uncond jump insn only once
2660 since the code for getting the insn length always returns
2661 the minimal length now. */
2662 if (uncond_jump_length == 0)
2663 uncond_jump_length = get_uncond_jump_length ();
2664
2665 /* Never copy a block larger than this. */
2666 int max_size
2667 = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
2668
2669 bool changed = false;
2670
2671 /* Try to duplicate all blocks that end in a computed jump and that
2672 can be duplicated at all. */
2673 basic_block bb;
2674 FOR_EACH_BB_FN (bb, fun)
2675 if (computed_jump_p (BB_END (bb)) && can_duplicate_block_p (bb))
2676 changed |= maybe_duplicate_computed_goto (bb, max_size);
2677
2678 /* Duplicating blocks will redirect edges and may cause hot blocks
2679 previously reached by both hot and cold blocks to become dominated
2680 only by cold blocks. */
2681 if (changed)
2682 fixup_partitions ();
2683}
2684
2685namespace {
2686
2687const pass_data pass_data_duplicate_computed_gotos =
2688{
2689 RTL_PASS, /* type */
2690 "compgotos", /* name */
2691 OPTGROUP_NONE, /* optinfo_flags */
2692 TV_REORDER_BLOCKS, /* tv_id */
2693 0, /* properties_required */
2694 0, /* properties_provided */
2695 0, /* properties_destroyed */
2696 0, /* todo_flags_start */
2697 0, /* todo_flags_finish */
2698};
2699
2700class pass_duplicate_computed_gotos : public rtl_opt_pass
2701{
2702public:
2703 pass_duplicate_computed_gotos (gcc::context *ctxt)
2704 : rtl_opt_pass (pass_data_duplicate_computed_gotos, ctxt)
2705 {}
2706
2707 /* opt_pass methods: */
2708 virtual bool gate (function *);
2709 virtual unsigned int execute (function *);
2710
2711}; // class pass_duplicate_computed_gotos
2712
2713bool
2714pass_duplicate_computed_gotos::gate (function *fun)
2715{
2716 if (targetm.cannot_modify_jumps_p ())
2717 return false;
2718 return (optimize > 0
2719 && flag_expensive_optimizations
2720 && ! optimize_function_for_size_p (fun));
2721}
2722
2723unsigned int
2724pass_duplicate_computed_gotos::execute (function *fun)
2725{
2726 duplicate_computed_gotos (fun);
2727
2728 return 0;
2729}
2730
2731} // anon namespace
2732
2733rtl_opt_pass *
2734make_pass_duplicate_computed_gotos (gcc::context *ctxt)
2735{
2736 return new pass_duplicate_computed_gotos (ctxt);
2737}
2738
2739/* This function is the main 'entrance' for the optimization that
2740 partitions hot and cold basic blocks into separate sections of the
2741 .o file (to improve performance and cache locality). Ideally it
2742 would be called after all optimizations that rearrange the CFG have
2743 been called. However part of this optimization may introduce new
2744 register usage, so it must be called before register allocation has
2745 occurred. This means that this optimization is actually called
2746 well before the optimization that reorders basic blocks (see
2747 function above).
2748
2749 This optimization checks the feedback information to determine
2750 which basic blocks are hot/cold, updates flags on the basic blocks
2751 to indicate which section they belong in. This information is
2752 later used for writing out sections in the .o file. Because hot
2753 and cold sections can be arbitrarily large (within the bounds of
2754 memory), far beyond the size of a single function, it is necessary
2755 to fix up all edges that cross section boundaries, to make sure the
2756 instructions used can actually span the required distance. The
2757 fixes are described below.
2758
2759 Fall-through edges must be changed into jumps; it is not safe or
2760 legal to fall through across a section boundary. Whenever a
2761 fall-through edge crossing a section boundary is encountered, a new
2762 basic block is inserted (in the same section as the fall-through
2763 source), and the fall through edge is redirected to the new basic
2764 block. The new basic block contains an unconditional jump to the
2765 original fall-through target. (If the unconditional jump is
2766 insufficient to cross section boundaries, that is dealt with a
2767 little later, see below).
2768
2769 In order to deal with architectures that have short conditional
2770 branches (which cannot span all of memory) we take any conditional
2771 jump that attempts to cross a section boundary and add a level of
2772 indirection: it becomes a conditional jump to a new basic block, in
2773 the same section. The new basic block contains an unconditional
2774 jump to the original target, in the other section.
2775
2776 For those architectures whose unconditional branch is also
2777 incapable of reaching all of memory, those unconditional jumps are
2778 converted into indirect jumps, through a register.
2779
2780 IMPORTANT NOTE: This optimization causes some messy interactions
2781 with the cfg cleanup optimizations; those optimizations want to
2782 merge blocks wherever possible, and to collapse indirect jump
2783 sequences (change "A jumps to B jumps to C" directly into "A jumps
2784 to C"). Those optimizations can undo the jump fixes that
2785 partitioning is required to make (see above), in order to ensure
2786 that jumps attempting to cross section boundaries are really able
2787 to cover whatever distance the jump requires (on many architectures
2788 conditional or unconditional jumps are not able to reach all of
2789 memory). Therefore tests have to be inserted into each such
2790 optimization to make sure that it does not undo stuff necessary to
2791 cross partition boundaries. This would be much less of a problem
2792 if we could perform this optimization later in the compilation, but
2793 unfortunately the fact that we may need to create indirect jumps
2794 (through registers) requires that this optimization be performed
2795 before register allocation.
2796
2797 Hot and cold basic blocks are partitioned and put in separate
2798 sections of the .o file, to reduce paging and improve cache
2799 performance (hopefully). This can result in bits of code from the
2800 same function being widely separated in the .o file. However this
2801 is not obvious to the current bb structure. Therefore we must take
2802 care to ensure that: 1). There are no fall_thru edges that cross
2803 between sections; 2). For those architectures which have "short"
2804 conditional branches, all conditional branches that attempt to
2805 cross between sections are converted to unconditional branches;
2806 and, 3). For those architectures which have "short" unconditional
2807 branches, all unconditional branches that attempt to cross between
2808 sections are converted to indirect jumps.
2809
2810 The code for fixing up fall_thru edges that cross between hot and
2811 cold basic blocks does so by creating new basic blocks containing
2812 unconditional branches to the appropriate label in the "other"
2813 section. The new basic block is then put in the same (hot or cold)
2814 section as the original conditional branch, and the fall_thru edge
2815 is modified to fall into the new basic block instead. By adding
2816 this level of indirection we end up with only unconditional branches
2817 crossing between hot and cold sections.
2818
2819 Conditional branches are dealt with by adding a level of indirection.
2820 A new basic block is added in the same (hot/cold) section as the
2821 conditional branch, and the conditional branch is retargeted to the
2822 new basic block. The new basic block contains an unconditional branch
2823 to the original target of the conditional branch (in the other section).
2824
2825 Unconditional branches are dealt with by converting them into
2826 indirect jumps. */
2827
2828namespace {
2829
2830const pass_data pass_data_partition_blocks =
2831{
2832 RTL_PASS, /* type */
2833 "bbpart", /* name */
2834 OPTGROUP_NONE, /* optinfo_flags */
2835 TV_REORDER_BLOCKS, /* tv_id */
2836 PROP_cfglayout, /* properties_required */
2837 0, /* properties_provided */
2838 0, /* properties_destroyed */
2839 0, /* todo_flags_start */
2840 0, /* todo_flags_finish */
2841};
2842
2843class pass_partition_blocks : public rtl_opt_pass
2844{
2845public:
2846 pass_partition_blocks (gcc::context *ctxt)
2847 : rtl_opt_pass (pass_data_partition_blocks, ctxt)
2848 {}
2849
2850 /* opt_pass methods: */
2851 virtual bool gate (function *);
2852 virtual unsigned int execute (function *);
2853
2854}; // class pass_partition_blocks
2855
2856bool
2857pass_partition_blocks::gate (function *fun)
2858{
2859 /* The optimization to partition hot/cold basic blocks into separate
2860 sections of the .o file does not work well with linkonce or with
2861 user defined section attributes. Don't call it if either case
2862 arises. */
2863 return (flag_reorder_blocks_and_partition
2864 && optimize
2865 /* See pass_reorder_blocks::gate. We should not partition if
2866 we are going to omit the reordering. */
2867 && optimize_function_for_speed_p (fun)
2868 && !DECL_COMDAT_GROUP (current_function_decl)
2869 && !lookup_attribute ("section", DECL_ATTRIBUTES (fun->decl)));
2870}
2871
2872unsigned
2873pass_partition_blocks::execute (function *fun)
2874{
2875 vec<edge> crossing_edges;
2876
2877 if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1)
2878 return 0;
2879
2880 df_set_flags (DF_DEFER_INSN_RESCAN);
2881
2882 crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
2883 if (!crossing_edges.exists ())
2884 /* Make sure to process deferred rescans and clear changeable df flags. */
2885 return TODO_df_finish;
2886
2887 crtl->has_bb_partition = true;
2888
2889 /* Make sure the source of any crossing edge ends in a jump and the
2890 destination of any crossing edge has a label. */
2891 add_labels_and_missing_jumps (crossing_edges);
2892
2893 /* Convert all crossing fall_thru edges to non-crossing fall
2894 thrus to unconditional jumps (that jump to the original fall
2895 through dest). */
2896 fix_up_fall_thru_edges ();
2897
2898 /* If the architecture does not have conditional branches that can
2899 span all of memory, convert crossing conditional branches into
2900 crossing unconditional branches. */
2901 if (!HAS_LONG_COND_BRANCH)
2902 fix_crossing_conditional_branches ();
2903
2904 /* If the architecture does not have unconditional branches that
2905 can span all of memory, convert crossing unconditional branches
2906 into indirect jumps. Since adding an indirect jump also adds
2907 a new register usage, update the register usage information as
2908 well. */
2909 if (!HAS_LONG_UNCOND_BRANCH)
2910 fix_crossing_unconditional_branches ();
2911
2912 update_crossing_jump_flags ();
2913
2914 /* Clear bb->aux fields that the above routines were using. */
2915 clear_aux_for_blocks ();
2916
2917 crossing_edges.release ();
2918
2919 /* ??? FIXME: DF generates the bb info for a block immediately.
2920 And by immediately, I mean *during* creation of the block.
2921
2922 #0 df_bb_refs_collect
2923 #1 in df_bb_refs_record
2924 #2 in create_basic_block_structure
2925
2926 Which means that the bb_has_eh_pred test in df_bb_refs_collect
2927 will *always* fail, because no edges can have been added to the
2928 block yet. Which of course means we don't add the right
2929 artificial refs, which means we fail df_verify (much) later.
2930
2931 Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
2932 that we also shouldn't grab data from the new blocks those new
2933 insns are in either. In this way one can create the block, link
2934 it up properly, and have everything Just Work later, when deferred
2935 insns are processed.
2936
2937 In the meantime, we have no other option but to throw away all
2938 of the DF data and recompute it all. */
2939 if (fun->eh->lp_array)
2940 {
2941 df_finish_pass (true);
2942 df_scan_alloc (NULL);
2943 df_scan_blocks ();
2944 /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
2945 data. We blindly generated all of them when creating the new
2946 landing pad. Delete those assignments we don't use. */
2947 df_set_flags (DF_LR_RUN_DCE);
2948 df_analyze ();
2949 }
2950
2951 /* Make sure to process deferred rescans and clear changeable df flags. */
2952 return TODO_df_finish;
2953}
2954
2955} // anon namespace
2956
2957rtl_opt_pass *
2958make_pass_partition_blocks (gcc::context *ctxt)
2959{
2960 return new pass_partition_blocks (ctxt);
2961}
2962