[arm][2/2] Remove support for -march=armv3 and older
[official-gcc.git] / gcc / bb-reorder.c
blob6f2ad5a522058333015ee24aa96d50d86856d70b
1 /* Basic block reordering routines for the GNU compiler.
2 Copyright (C) 2000-2018 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
9 any later version.
11 GCC is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
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.
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. */
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.
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.
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.
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.
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.
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.
85 References:
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
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 #include "common/common-target.h"
122 /* The number of rounds. In most cases there will only be 4 rounds, but
123 when partitioning hot and cold basic blocks into separate sections of
124 the object file there will be an extra round. */
125 #define N_ROUNDS 5
127 struct target_bb_reorder default_target_bb_reorder;
128 #if SWITCHABLE_TARGET
129 struct target_bb_reorder *this_target_bb_reorder = &default_target_bb_reorder;
130 #endif
132 #define uncond_jump_length \
133 (this_target_bb_reorder->x_uncond_jump_length)
135 /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
136 static const int branch_threshold[N_ROUNDS] = {400, 200, 100, 0, 0};
138 /* Exec thresholds in thousandths (per mille) of the count of bb 0. */
139 static const int exec_threshold[N_ROUNDS] = {500, 200, 50, 0, 0};
141 /* If edge count is lower than DUPLICATION_THRESHOLD per mille of entry
142 block the edge destination is not duplicated while connecting traces. */
143 #define DUPLICATION_THRESHOLD 100
145 typedef fibonacci_heap <long, basic_block_def> bb_heap_t;
146 typedef fibonacci_node <long, basic_block_def> bb_heap_node_t;
148 /* Structure to hold needed information for each basic block. */
149 struct bbro_basic_block_data
151 /* Which trace is the bb start of (-1 means it is not a start of any). */
152 int start_of_trace;
154 /* Which trace is the bb end of (-1 means it is not an end of any). */
155 int end_of_trace;
157 /* Which trace is the bb in? */
158 int in_trace;
160 /* Which trace was this bb visited in? */
161 int visited;
163 /* Cached maximum frequency of interesting incoming edges.
164 Minus one means not yet computed. */
165 int priority;
167 /* Which heap is BB in (if any)? */
168 bb_heap_t *heap;
170 /* Which heap node is BB in (if any)? */
171 bb_heap_node_t *node;
174 /* The current size of the following dynamic array. */
175 static int array_size;
177 /* The array which holds needed information for basic blocks. */
178 static bbro_basic_block_data *bbd;
180 /* To avoid frequent reallocation the size of arrays is greater than needed,
181 the number of elements is (not less than) 1.25 * size_wanted. */
182 #define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
184 /* Free the memory and set the pointer to NULL. */
185 #define FREE(P) (gcc_assert (P), free (P), P = 0)
187 /* Structure for holding information about a trace. */
188 struct trace
190 /* First and last basic block of the trace. */
191 basic_block first, last;
193 /* The round of the STC creation which this trace was found in. */
194 int round;
196 /* The length (i.e. the number of basic blocks) of the trace. */
197 int length;
200 /* Maximum count of one of the entry blocks. */
201 static profile_count max_entry_count;
203 /* Local function prototypes. */
204 static void find_traces_1_round (int, profile_count, struct trace *, int *,
205 int, bb_heap_t **, int);
206 static basic_block copy_bb (basic_block, edge, basic_block, int);
207 static long bb_to_key (basic_block);
208 static bool better_edge_p (const_basic_block, const_edge, profile_probability,
209 profile_count, profile_probability, profile_count,
210 const_edge);
211 static bool copy_bb_p (const_basic_block, int);
213 /* Return the trace number in which BB was visited. */
215 static int
216 bb_visited_trace (const_basic_block bb)
218 gcc_assert (bb->index < array_size);
219 return bbd[bb->index].visited;
222 /* This function marks BB that it was visited in trace number TRACE. */
224 static void
225 mark_bb_visited (basic_block bb, int trace)
227 bbd[bb->index].visited = trace;
228 if (bbd[bb->index].heap)
230 bbd[bb->index].heap->delete_node (bbd[bb->index].node);
231 bbd[bb->index].heap = NULL;
232 bbd[bb->index].node = NULL;
236 /* Check to see if bb should be pushed into the next round of trace
237 collections or not. Reasons for pushing the block forward are 1).
238 If the block is cold, we are doing partitioning, and there will be
239 another round (cold partition blocks are not supposed to be
240 collected into traces until the very last round); or 2). There will
241 be another round, and the basic block is not "hot enough" for the
242 current round of trace collection. */
244 static bool
245 push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
246 profile_count count_th)
248 bool there_exists_another_round;
249 bool block_not_hot_enough;
251 there_exists_another_round = round < number_of_rounds - 1;
253 block_not_hot_enough = (bb->count < count_th
254 || probably_never_executed_bb_p (cfun, bb));
256 if (there_exists_another_round
257 && block_not_hot_enough)
258 return true;
259 else
260 return false;
263 /* Find the traces for Software Trace Cache. Chain each trace through
264 RBI()->next. Store the number of traces to N_TRACES and description of
265 traces to TRACES. */
267 static void
268 find_traces (int *n_traces, struct trace *traces)
270 int i;
271 int number_of_rounds;
272 edge e;
273 edge_iterator ei;
274 bb_heap_t *heap = new bb_heap_t (LONG_MIN);
276 /* Add one extra round of trace collection when partitioning hot/cold
277 basic blocks into separate sections. The last round is for all the
278 cold blocks (and ONLY the cold blocks). */
280 number_of_rounds = N_ROUNDS - 1;
282 /* Insert entry points of function into heap. */
283 max_entry_count = profile_count::zero ();
284 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
286 bbd[e->dest->index].heap = heap;
287 bbd[e->dest->index].node = heap->insert (bb_to_key (e->dest), e->dest);
288 if (e->dest->count > max_entry_count)
289 max_entry_count = e->dest->count;
292 /* Find the traces. */
293 for (i = 0; i < number_of_rounds; i++)
295 profile_count count_threshold;
297 if (dump_file)
298 fprintf (dump_file, "STC - round %d\n", i + 1);
300 count_threshold = max_entry_count.apply_scale (exec_threshold[i], 1000);
302 find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
303 count_threshold, traces, n_traces, i, &heap,
304 number_of_rounds);
306 delete heap;
308 if (dump_file)
310 for (i = 0; i < *n_traces; i++)
312 basic_block bb;
313 fprintf (dump_file, "Trace %d (round %d): ", i + 1,
314 traces[i].round + 1);
315 for (bb = traces[i].first;
316 bb != traces[i].last;
317 bb = (basic_block) bb->aux)
319 fprintf (dump_file, "%d [", bb->index);
320 bb->count.dump (dump_file);
321 fprintf (dump_file, "] ");
323 fprintf (dump_file, "%d [", bb->index);
324 bb->count.dump (dump_file);
325 fprintf (dump_file, "]\n");
327 fflush (dump_file);
331 /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
332 (with sequential number TRACE_N). */
334 static basic_block
335 rotate_loop (edge back_edge, struct trace *trace, int trace_n)
337 basic_block bb;
339 /* Information about the best end (end after rotation) of the loop. */
340 basic_block best_bb = NULL;
341 edge best_edge = NULL;
342 profile_count best_count = profile_count::uninitialized ();
343 /* The best edge is preferred when its destination is not visited yet
344 or is a start block of some trace. */
345 bool is_preferred = false;
347 /* Find the most frequent edge that goes out from current trace. */
348 bb = back_edge->dest;
351 edge e;
352 edge_iterator ei;
354 FOR_EACH_EDGE (e, ei, bb->succs)
355 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
356 && bb_visited_trace (e->dest) != trace_n
357 && (e->flags & EDGE_CAN_FALLTHRU)
358 && !(e->flags & EDGE_COMPLEX))
360 if (is_preferred)
362 /* The best edge is preferred. */
363 if (!bb_visited_trace (e->dest)
364 || bbd[e->dest->index].start_of_trace >= 0)
366 /* The current edge E is also preferred. */
367 if (e->count () > best_count)
369 best_count = e->count ();
370 best_edge = e;
371 best_bb = bb;
375 else
377 if (!bb_visited_trace (e->dest)
378 || bbd[e->dest->index].start_of_trace >= 0)
380 /* The current edge E is preferred. */
381 is_preferred = true;
382 best_count = e->count ();
383 best_edge = e;
384 best_bb = bb;
386 else
388 if (!best_edge || e->count () > best_count)
390 best_count = e->count ();
391 best_edge = e;
392 best_bb = bb;
397 bb = (basic_block) bb->aux;
399 while (bb != back_edge->dest);
401 if (best_bb)
403 /* Rotate the loop so that the BEST_EDGE goes out from the last block of
404 the trace. */
405 if (back_edge->dest == trace->first)
407 trace->first = (basic_block) best_bb->aux;
409 else
411 basic_block prev_bb;
413 for (prev_bb = trace->first;
414 prev_bb->aux != back_edge->dest;
415 prev_bb = (basic_block) prev_bb->aux)
417 prev_bb->aux = best_bb->aux;
419 /* Try to get rid of uncond jump to cond jump. */
420 if (single_succ_p (prev_bb))
422 basic_block header = single_succ (prev_bb);
424 /* Duplicate HEADER if it is a small block containing cond jump
425 in the end. */
426 if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
427 && !CROSSING_JUMP_P (BB_END (header)))
428 copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
432 else
434 /* We have not found suitable loop tail so do no rotation. */
435 best_bb = back_edge->src;
437 best_bb->aux = NULL;
438 return best_bb;
441 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
442 not include basic blocks whose probability is lower than BRANCH_TH or whose
443 count is lower than EXEC_TH into traces (or whose count is lower than
444 COUNT_TH). Store the new traces into TRACES and modify the number of
445 traces *N_TRACES. Set the round (which the trace belongs to) to ROUND.
446 The function expects starting basic blocks to be in *HEAP and will delete
447 *HEAP and store starting points for the next round into new *HEAP. */
449 static void
450 find_traces_1_round (int branch_th, profile_count count_th,
451 struct trace *traces, int *n_traces, int round,
452 bb_heap_t **heap, int number_of_rounds)
454 /* Heap for discarded basic blocks which are possible starting points for
455 the next round. */
456 bb_heap_t *new_heap = new bb_heap_t (LONG_MIN);
457 bool for_size = optimize_function_for_size_p (cfun);
459 while (!(*heap)->empty ())
461 basic_block bb;
462 struct trace *trace;
463 edge best_edge, e;
464 long key;
465 edge_iterator ei;
467 bb = (*heap)->extract_min ();
468 bbd[bb->index].heap = NULL;
469 bbd[bb->index].node = NULL;
471 if (dump_file)
472 fprintf (dump_file, "Getting bb %d\n", bb->index);
474 /* If the BB's count is too low, send BB to the next round. When
475 partitioning hot/cold blocks into separate sections, make sure all
476 the cold blocks (and ONLY the cold blocks) go into the (extra) final
477 round. When optimizing for size, do not push to next round. */
479 if (!for_size
480 && push_to_next_round_p (bb, round, number_of_rounds,
481 count_th))
483 int key = bb_to_key (bb);
484 bbd[bb->index].heap = new_heap;
485 bbd[bb->index].node = new_heap->insert (key, bb);
487 if (dump_file)
488 fprintf (dump_file,
489 " Possible start point of next round: %d (key: %d)\n",
490 bb->index, key);
491 continue;
494 trace = traces + *n_traces;
495 trace->first = bb;
496 trace->round = round;
497 trace->length = 0;
498 bbd[bb->index].in_trace = *n_traces;
499 (*n_traces)++;
503 bool ends_in_call;
505 /* The probability and count of the best edge. */
506 profile_probability best_prob = profile_probability::uninitialized ();
507 profile_count best_count = profile_count::uninitialized ();
509 best_edge = NULL;
510 mark_bb_visited (bb, *n_traces);
511 trace->length++;
513 if (dump_file)
514 fprintf (dump_file, "Basic block %d was visited in trace %d\n",
515 bb->index, *n_traces);
517 ends_in_call = block_ends_with_call_p (bb);
519 /* Select the successor that will be placed after BB. */
520 FOR_EACH_EDGE (e, ei, bb->succs)
522 gcc_assert (!(e->flags & EDGE_FAKE));
524 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
525 continue;
527 if (bb_visited_trace (e->dest)
528 && bb_visited_trace (e->dest) != *n_traces)
529 continue;
531 /* If partitioning hot/cold basic blocks, don't consider edges
532 that cross section boundaries. */
533 if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
534 continue;
536 profile_probability prob = e->probability;
537 profile_count count = e->dest->count;
539 /* The only sensible preference for a call instruction is the
540 fallthru edge. Don't bother selecting anything else. */
541 if (ends_in_call)
543 if (e->flags & EDGE_CAN_FALLTHRU)
545 best_edge = e;
546 best_prob = prob;
547 best_count = count;
549 continue;
552 /* Edge that cannot be fallthru or improbable or infrequent
553 successor (i.e. it is unsuitable successor). When optimizing
554 for size, ignore the probability and count. */
555 if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
556 || !prob.initialized_p ()
557 || ((prob.to_reg_br_prob_base () < branch_th
558 || e->count () < count_th) && (!for_size)))
559 continue;
561 if (better_edge_p (bb, e, prob, count, best_prob, best_count,
562 best_edge))
564 best_edge = e;
565 best_prob = prob;
566 best_count = count;
570 /* If the best destination has multiple predecessors and can be
571 duplicated cheaper than a jump, don't allow it to be added to
572 a trace; we'll duplicate it when connecting the traces later.
573 However, we need to check that this duplication wouldn't leave
574 the best destination with only crossing predecessors, because
575 this would change its effective partition from hot to cold. */
576 if (best_edge
577 && EDGE_COUNT (best_edge->dest->preds) >= 2
578 && copy_bb_p (best_edge->dest, 0))
580 bool only_crossing_preds = true;
581 edge e;
582 edge_iterator ei;
583 FOR_EACH_EDGE (e, ei, best_edge->dest->preds)
584 if (e != best_edge && !(e->flags & EDGE_CROSSING))
586 only_crossing_preds = false;
587 break;
589 if (!only_crossing_preds)
590 best_edge = NULL;
593 /* If the best destination has multiple successors or predecessors,
594 don't allow it to be added when optimizing for size. This makes
595 sure predecessors with smaller index are handled before the best
596 destinarion. It breaks long trace and reduces long jumps.
598 Take if-then-else as an example.
604 If we do not remove the best edge B->D/C->D, the final order might
605 be A B D ... C. C is at the end of the program. If D's successors
606 and D are complicated, might need long jumps for A->C and C->D.
607 Similar issue for order: A C D ... B.
609 After removing the best edge, the final result will be ABCD/ ACBD.
610 It does not add jump compared with the previous order. But it
611 reduces the possibility of long jumps. */
612 if (best_edge && for_size
613 && (EDGE_COUNT (best_edge->dest->succs) > 1
614 || EDGE_COUNT (best_edge->dest->preds) > 1))
615 best_edge = NULL;
617 /* Add all non-selected successors to the heaps. */
618 FOR_EACH_EDGE (e, ei, bb->succs)
620 if (e == best_edge
621 || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
622 || bb_visited_trace (e->dest))
623 continue;
625 key = bb_to_key (e->dest);
627 if (bbd[e->dest->index].heap)
629 /* E->DEST is already in some heap. */
630 if (key != bbd[e->dest->index].node->get_key ())
632 if (dump_file)
634 fprintf (dump_file,
635 "Changing key for bb %d from %ld to %ld.\n",
636 e->dest->index,
637 (long) bbd[e->dest->index].node->get_key (),
638 key);
640 bbd[e->dest->index].heap->replace_key
641 (bbd[e->dest->index].node, key);
644 else
646 bb_heap_t *which_heap = *heap;
648 profile_probability prob = e->probability;
650 if (!(e->flags & EDGE_CAN_FALLTHRU)
651 || (e->flags & EDGE_COMPLEX)
652 || !prob.initialized_p ()
653 || prob.to_reg_br_prob_base () < branch_th
654 || e->count () < count_th)
656 /* When partitioning hot/cold basic blocks, make sure
657 the cold blocks (and only the cold blocks) all get
658 pushed to the last round of trace collection. When
659 optimizing for size, do not push to next round. */
661 if (!for_size && push_to_next_round_p (e->dest, round,
662 number_of_rounds,
663 count_th))
664 which_heap = new_heap;
667 bbd[e->dest->index].heap = which_heap;
668 bbd[e->dest->index].node = which_heap->insert (key, e->dest);
670 if (dump_file)
672 fprintf (dump_file,
673 " Possible start of %s round: %d (key: %ld)\n",
674 (which_heap == new_heap) ? "next" : "this",
675 e->dest->index, (long) key);
681 if (best_edge) /* Suitable successor was found. */
683 if (bb_visited_trace (best_edge->dest) == *n_traces)
685 /* We do nothing with one basic block loops. */
686 if (best_edge->dest != bb)
688 if (best_edge->count ()
689 > best_edge->dest->count.apply_scale (4, 5))
691 /* The loop has at least 4 iterations. If the loop
692 header is not the first block of the function
693 we can rotate the loop. */
695 if (best_edge->dest
696 != ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
698 if (dump_file)
700 fprintf (dump_file,
701 "Rotating loop %d - %d\n",
702 best_edge->dest->index, bb->index);
704 bb->aux = best_edge->dest;
705 bbd[best_edge->dest->index].in_trace =
706 (*n_traces) - 1;
707 bb = rotate_loop (best_edge, trace, *n_traces);
710 else
712 /* The loop has less than 4 iterations. */
714 if (single_succ_p (bb)
715 && copy_bb_p (best_edge->dest,
716 optimize_edge_for_speed_p
717 (best_edge)))
719 bb = copy_bb (best_edge->dest, best_edge, bb,
720 *n_traces);
721 trace->length++;
726 /* Terminate the trace. */
727 break;
729 else
731 /* Check for a situation
739 where
740 AB->count () + BC->count () >= AC->count ().
741 (i.e. 2 * B->count >= AC->count )
742 Best ordering is then A B C.
744 When optimizing for size, A B C is always the best order.
746 This situation is created for example by:
748 if (A) B;
753 FOR_EACH_EDGE (e, ei, bb->succs)
754 if (e != best_edge
755 && (e->flags & EDGE_CAN_FALLTHRU)
756 && !(e->flags & EDGE_COMPLEX)
757 && !bb_visited_trace (e->dest)
758 && single_pred_p (e->dest)
759 && !(e->flags & EDGE_CROSSING)
760 && single_succ_p (e->dest)
761 && (single_succ_edge (e->dest)->flags
762 & EDGE_CAN_FALLTHRU)
763 && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
764 && single_succ (e->dest) == best_edge->dest
765 && (e->dest->count.apply_scale (2, 1)
766 >= best_edge->count () || for_size))
768 best_edge = e;
769 if (dump_file)
770 fprintf (dump_file, "Selecting BB %d\n",
771 best_edge->dest->index);
772 break;
775 bb->aux = best_edge->dest;
776 bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
777 bb = best_edge->dest;
781 while (best_edge);
782 trace->last = bb;
783 bbd[trace->first->index].start_of_trace = *n_traces - 1;
784 if (bbd[trace->last->index].end_of_trace != *n_traces - 1)
786 bbd[trace->last->index].end_of_trace = *n_traces - 1;
787 /* Update the cached maximum frequency for interesting predecessor
788 edges for successors of the new trace end. */
789 FOR_EACH_EDGE (e, ei, trace->last->succs)
790 if (EDGE_FREQUENCY (e) > bbd[e->dest->index].priority)
791 bbd[e->dest->index].priority = EDGE_FREQUENCY (e);
794 /* The trace is terminated so we have to recount the keys in heap
795 (some block can have a lower key because now one of its predecessors
796 is an end of the trace). */
797 FOR_EACH_EDGE (e, ei, bb->succs)
799 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
800 || bb_visited_trace (e->dest))
801 continue;
803 if (bbd[e->dest->index].heap)
805 key = bb_to_key (e->dest);
806 if (key != bbd[e->dest->index].node->get_key ())
808 if (dump_file)
810 fprintf (dump_file,
811 "Changing key for bb %d from %ld to %ld.\n",
812 e->dest->index,
813 (long) bbd[e->dest->index].node->get_key (), key);
815 bbd[e->dest->index].heap->replace_key
816 (bbd[e->dest->index].node, key);
822 delete (*heap);
824 /* "Return" the new heap. */
825 *heap = new_heap;
828 /* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
829 it to trace after BB, mark OLD_BB visited and update pass' data structures
830 (TRACE is a number of trace which OLD_BB is duplicated to). */
832 static basic_block
833 copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
835 basic_block new_bb;
837 new_bb = duplicate_block (old_bb, e, bb);
838 BB_COPY_PARTITION (new_bb, old_bb);
840 gcc_assert (e->dest == new_bb);
842 if (dump_file)
843 fprintf (dump_file,
844 "Duplicated bb %d (created bb %d)\n",
845 old_bb->index, new_bb->index);
847 if (new_bb->index >= array_size
848 || last_basic_block_for_fn (cfun) > array_size)
850 int i;
851 int new_size;
853 new_size = MAX (last_basic_block_for_fn (cfun), new_bb->index + 1);
854 new_size = GET_ARRAY_SIZE (new_size);
855 bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
856 for (i = array_size; i < new_size; i++)
858 bbd[i].start_of_trace = -1;
859 bbd[i].end_of_trace = -1;
860 bbd[i].in_trace = -1;
861 bbd[i].visited = 0;
862 bbd[i].priority = -1;
863 bbd[i].heap = NULL;
864 bbd[i].node = NULL;
866 array_size = new_size;
868 if (dump_file)
870 fprintf (dump_file,
871 "Growing the dynamic array to %d elements.\n",
872 array_size);
876 gcc_assert (!bb_visited_trace (e->dest));
877 mark_bb_visited (new_bb, trace);
878 new_bb->aux = bb->aux;
879 bb->aux = new_bb;
881 bbd[new_bb->index].in_trace = trace;
883 return new_bb;
886 /* Compute and return the key (for the heap) of the basic block BB. */
888 static long
889 bb_to_key (basic_block bb)
891 edge e;
892 edge_iterator ei;
894 /* Use index as key to align with its original order. */
895 if (optimize_function_for_size_p (cfun))
896 return bb->index;
898 /* Do not start in probably never executed blocks. */
900 if (BB_PARTITION (bb) == BB_COLD_PARTITION
901 || probably_never_executed_bb_p (cfun, bb))
902 return BB_FREQ_MAX;
904 /* Prefer blocks whose predecessor is an end of some trace
905 or whose predecessor edge is EDGE_DFS_BACK. */
906 int priority = bbd[bb->index].priority;
907 if (priority == -1)
909 priority = 0;
910 FOR_EACH_EDGE (e, ei, bb->preds)
912 if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
913 && bbd[e->src->index].end_of_trace >= 0)
914 || (e->flags & EDGE_DFS_BACK))
916 int edge_freq = EDGE_FREQUENCY (e);
918 if (edge_freq > priority)
919 priority = edge_freq;
922 bbd[bb->index].priority = priority;
925 if (priority)
926 /* The block with priority should have significantly lower key. */
927 return -(100 * BB_FREQ_MAX + 100 * priority + bb->count.to_frequency (cfun));
929 return -bb->count.to_frequency (cfun);
932 /* Return true when the edge E from basic block BB is better than the temporary
933 best edge (details are in function). The probability of edge E is PROB. The
934 count of the successor is COUNT. The current best probability is
935 BEST_PROB, the best count is BEST_COUNT.
936 The edge is considered to be equivalent when PROB does not differ much from
937 BEST_PROB; similarly for count. */
939 static bool
940 better_edge_p (const_basic_block bb, const_edge e, profile_probability prob,
941 profile_count count, profile_probability best_prob,
942 profile_count best_count, const_edge cur_best_edge)
944 bool is_better_edge;
946 /* The BEST_* values do not have to be best, but can be a bit smaller than
947 maximum values. */
948 profile_probability diff_prob = best_prob.apply_scale (1, 10);
950 /* The smaller one is better to keep the original order. */
951 if (optimize_function_for_size_p (cfun))
952 return !cur_best_edge
953 || cur_best_edge->dest->index > e->dest->index;
955 /* Those edges are so expensive that continuing a trace is not useful
956 performance wise. */
957 if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
958 return false;
960 if (prob > best_prob + diff_prob
961 || (!best_prob.initialized_p ()
962 && prob > profile_probability::guessed_never ()))
963 /* The edge has higher probability than the temporary best edge. */
964 is_better_edge = true;
965 else if (prob < best_prob - diff_prob)
966 /* The edge has lower probability than the temporary best edge. */
967 is_better_edge = false;
968 else
970 profile_count diff_count = best_count.apply_scale (1, 10);
971 if (count < best_count - diff_count
972 || (!best_count.initialized_p ()
973 && count.nonzero_p ()))
974 /* The edge and the temporary best edge have almost equivalent
975 probabilities. The higher countuency of a successor now means
976 that there is another edge going into that successor.
977 This successor has lower countuency so it is better. */
978 is_better_edge = true;
979 else if (count > best_count + diff_count)
980 /* This successor has higher countuency so it is worse. */
981 is_better_edge = false;
982 else if (e->dest->prev_bb == bb)
983 /* The edges have equivalent probabilities and the successors
984 have equivalent frequencies. Select the previous successor. */
985 is_better_edge = true;
986 else
987 is_better_edge = false;
990 return is_better_edge;
993 /* Return true when the edge E is better than the temporary best edge
994 CUR_BEST_EDGE. If SRC_INDEX_P is true, the function compares the src bb of
995 E and CUR_BEST_EDGE; otherwise it will compare the dest bb.
996 BEST_LEN is the trace length of src (or dest) bb in CUR_BEST_EDGE.
997 TRACES record the information about traces.
998 When optimizing for size, the edge with smaller index is better.
999 When optimizing for speed, the edge with bigger probability or longer trace
1000 is better. */
1002 static bool
1003 connect_better_edge_p (const_edge e, bool src_index_p, int best_len,
1004 const_edge cur_best_edge, struct trace *traces)
1006 int e_index;
1007 int b_index;
1008 bool is_better_edge;
1010 if (!cur_best_edge)
1011 return true;
1013 if (optimize_function_for_size_p (cfun))
1015 e_index = src_index_p ? e->src->index : e->dest->index;
1016 b_index = src_index_p ? cur_best_edge->src->index
1017 : cur_best_edge->dest->index;
1018 /* The smaller one is better to keep the original order. */
1019 return b_index > e_index;
1022 if (src_index_p)
1024 e_index = e->src->index;
1026 /* We are looking for predecessor, so probabilities are not that
1027 informative. We do not want to connect A to B becuse A has
1028 only one sucessor (probablity is 100%) while there is edge
1029 A' to B where probability is 90% but which is much more frequent. */
1030 if (e->count () > cur_best_edge->count ())
1031 /* The edge has higher probability than the temporary best edge. */
1032 is_better_edge = true;
1033 else if (e->count () < cur_best_edge->count ())
1034 /* The edge has lower probability than the temporary best edge. */
1035 is_better_edge = false;
1036 if (e->probability > cur_best_edge->probability)
1037 /* The edge has higher probability than the temporary best edge. */
1038 is_better_edge = true;
1039 else if (e->probability < cur_best_edge->probability)
1040 /* The edge has lower probability than the temporary best edge. */
1041 is_better_edge = false;
1042 else if (traces[bbd[e_index].end_of_trace].length > best_len)
1043 /* The edge and the temporary best edge have equivalent probabilities.
1044 The edge with longer trace is better. */
1045 is_better_edge = true;
1046 else
1047 is_better_edge = false;
1049 else
1051 e_index = e->dest->index;
1053 if (e->probability > cur_best_edge->probability)
1054 /* The edge has higher probability than the temporary best edge. */
1055 is_better_edge = true;
1056 else if (e->probability < cur_best_edge->probability)
1057 /* The edge has lower probability than the temporary best edge. */
1058 is_better_edge = false;
1059 else if (traces[bbd[e_index].start_of_trace].length > best_len)
1060 /* The edge and the temporary best edge have equivalent probabilities.
1061 The edge with longer trace is better. */
1062 is_better_edge = true;
1063 else
1064 is_better_edge = false;
1067 return is_better_edge;
1070 /* Connect traces in array TRACES, N_TRACES is the count of traces. */
1072 static void
1073 connect_traces (int n_traces, struct trace *traces)
1075 int i;
1076 bool *connected;
1077 bool two_passes;
1078 int last_trace;
1079 int current_pass;
1080 int current_partition;
1081 profile_count count_threshold;
1082 bool for_size = optimize_function_for_size_p (cfun);
1084 count_threshold = max_entry_count.apply_scale (DUPLICATION_THRESHOLD, 1000);
1086 connected = XCNEWVEC (bool, n_traces);
1087 last_trace = -1;
1088 current_pass = 1;
1089 current_partition = BB_PARTITION (traces[0].first);
1090 two_passes = false;
1092 if (crtl->has_bb_partition)
1093 for (i = 0; i < n_traces && !two_passes; i++)
1094 if (BB_PARTITION (traces[0].first)
1095 != BB_PARTITION (traces[i].first))
1096 two_passes = true;
1098 for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
1100 int t = i;
1101 int t2;
1102 edge e, best;
1103 int best_len;
1105 if (i >= n_traces)
1107 gcc_assert (two_passes && current_pass == 1);
1108 i = 0;
1109 t = i;
1110 current_pass = 2;
1111 if (current_partition == BB_HOT_PARTITION)
1112 current_partition = BB_COLD_PARTITION;
1113 else
1114 current_partition = BB_HOT_PARTITION;
1117 if (connected[t])
1118 continue;
1120 if (two_passes
1121 && BB_PARTITION (traces[t].first) != current_partition)
1122 continue;
1124 connected[t] = true;
1126 /* Find the predecessor traces. */
1127 for (t2 = t; t2 > 0;)
1129 edge_iterator ei;
1130 best = NULL;
1131 best_len = 0;
1132 FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
1134 int si = e->src->index;
1136 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1137 && (e->flags & EDGE_CAN_FALLTHRU)
1138 && !(e->flags & EDGE_COMPLEX)
1139 && bbd[si].end_of_trace >= 0
1140 && !connected[bbd[si].end_of_trace]
1141 && (BB_PARTITION (e->src) == current_partition)
1142 && connect_better_edge_p (e, true, best_len, best, traces))
1144 best = e;
1145 best_len = traces[bbd[si].end_of_trace].length;
1148 if (best)
1150 best->src->aux = best->dest;
1151 t2 = bbd[best->src->index].end_of_trace;
1152 connected[t2] = true;
1154 if (dump_file)
1156 fprintf (dump_file, "Connection: %d %d\n",
1157 best->src->index, best->dest->index);
1160 else
1161 break;
1164 if (last_trace >= 0)
1165 traces[last_trace].last->aux = traces[t2].first;
1166 last_trace = t;
1168 /* Find the successor traces. */
1169 while (1)
1171 /* Find the continuation of the chain. */
1172 edge_iterator ei;
1173 best = NULL;
1174 best_len = 0;
1175 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1177 int di = e->dest->index;
1179 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1180 && (e->flags & EDGE_CAN_FALLTHRU)
1181 && !(e->flags & EDGE_COMPLEX)
1182 && bbd[di].start_of_trace >= 0
1183 && !connected[bbd[di].start_of_trace]
1184 && (BB_PARTITION (e->dest) == current_partition)
1185 && connect_better_edge_p (e, false, best_len, best, traces))
1187 best = e;
1188 best_len = traces[bbd[di].start_of_trace].length;
1192 if (for_size)
1194 if (!best)
1195 /* Stop finding the successor traces. */
1196 break;
1198 /* It is OK to connect block n with block n + 1 or a block
1199 before n. For others, only connect to the loop header. */
1200 if (best->dest->index > (traces[t].last->index + 1))
1202 int count = EDGE_COUNT (best->dest->preds);
1204 FOR_EACH_EDGE (e, ei, best->dest->preds)
1205 if (e->flags & EDGE_DFS_BACK)
1206 count--;
1208 /* If dest has multiple predecessors, skip it. We expect
1209 that one predecessor with smaller index connects with it
1210 later. */
1211 if (count != 1)
1212 break;
1215 /* Only connect Trace n with Trace n + 1. It is conservative
1216 to keep the order as close as possible to the original order.
1217 It also helps to reduce long jumps. */
1218 if (last_trace != bbd[best->dest->index].start_of_trace - 1)
1219 break;
1221 if (dump_file)
1222 fprintf (dump_file, "Connection: %d %d\n",
1223 best->src->index, best->dest->index);
1225 t = bbd[best->dest->index].start_of_trace;
1226 traces[last_trace].last->aux = traces[t].first;
1227 connected[t] = true;
1228 last_trace = t;
1230 else if (best)
1232 if (dump_file)
1234 fprintf (dump_file, "Connection: %d %d\n",
1235 best->src->index, best->dest->index);
1237 t = bbd[best->dest->index].start_of_trace;
1238 traces[last_trace].last->aux = traces[t].first;
1239 connected[t] = true;
1240 last_trace = t;
1242 else
1244 /* Try to connect the traces by duplication of 1 block. */
1245 edge e2;
1246 basic_block next_bb = NULL;
1247 bool try_copy = false;
1249 FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1250 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1251 && (e->flags & EDGE_CAN_FALLTHRU)
1252 && !(e->flags & EDGE_COMPLEX)
1253 && (!best || e->probability > best->probability))
1255 edge_iterator ei;
1256 edge best2 = NULL;
1257 int best2_len = 0;
1259 /* If the destination is a start of a trace which is only
1260 one block long, then no need to search the successor
1261 blocks of the trace. Accept it. */
1262 if (bbd[e->dest->index].start_of_trace >= 0
1263 && traces[bbd[e->dest->index].start_of_trace].length
1264 == 1)
1266 best = e;
1267 try_copy = true;
1268 continue;
1271 FOR_EACH_EDGE (e2, ei, e->dest->succs)
1273 int di = e2->dest->index;
1275 if (e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
1276 || ((e2->flags & EDGE_CAN_FALLTHRU)
1277 && !(e2->flags & EDGE_COMPLEX)
1278 && bbd[di].start_of_trace >= 0
1279 && !connected[bbd[di].start_of_trace]
1280 && BB_PARTITION (e2->dest) == current_partition
1281 && e2->count () >= count_threshold
1282 && (!best2
1283 || e2->probability > best2->probability
1284 || (e2->probability == best2->probability
1285 && traces[bbd[di].start_of_trace].length
1286 > best2_len))))
1288 best = e;
1289 best2 = e2;
1290 if (e2->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1291 best2_len = traces[bbd[di].start_of_trace].length;
1292 else
1293 best2_len = INT_MAX;
1294 next_bb = e2->dest;
1295 try_copy = true;
1300 /* Copy tiny blocks always; copy larger blocks only when the
1301 edge is traversed frequently enough. */
1302 if (try_copy
1303 && BB_PARTITION (best->src) == BB_PARTITION (best->dest)
1304 && copy_bb_p (best->dest,
1305 optimize_edge_for_speed_p (best)
1306 && (!best->count ().initialized_p ()
1307 || best->count () >= count_threshold)))
1309 basic_block new_bb;
1311 if (dump_file)
1313 fprintf (dump_file, "Connection: %d %d ",
1314 traces[t].last->index, best->dest->index);
1315 if (!next_bb)
1316 fputc ('\n', dump_file);
1317 else if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1318 fprintf (dump_file, "exit\n");
1319 else
1320 fprintf (dump_file, "%d\n", next_bb->index);
1323 new_bb = copy_bb (best->dest, best, traces[t].last, t);
1324 traces[t].last = new_bb;
1325 if (next_bb && next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1327 t = bbd[next_bb->index].start_of_trace;
1328 traces[last_trace].last->aux = traces[t].first;
1329 connected[t] = true;
1330 last_trace = t;
1332 else
1333 break; /* Stop finding the successor traces. */
1335 else
1336 break; /* Stop finding the successor traces. */
1341 if (dump_file)
1343 basic_block bb;
1345 fprintf (dump_file, "Final order:\n");
1346 for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
1347 fprintf (dump_file, "%d ", bb->index);
1348 fprintf (dump_file, "\n");
1349 fflush (dump_file);
1352 FREE (connected);
1355 /* Return true when BB can and should be copied. CODE_MAY_GROW is true
1356 when code size is allowed to grow by duplication. */
1358 static bool
1359 copy_bb_p (const_basic_block bb, int code_may_grow)
1361 int size = 0;
1362 int max_size = uncond_jump_length;
1363 rtx_insn *insn;
1365 if (EDGE_COUNT (bb->preds) < 2)
1366 return false;
1367 if (!can_duplicate_block_p (bb))
1368 return false;
1370 /* Avoid duplicating blocks which have many successors (PR/13430). */
1371 if (EDGE_COUNT (bb->succs) > 8)
1372 return false;
1374 if (code_may_grow && optimize_bb_for_speed_p (bb))
1375 max_size *= PARAM_VALUE (PARAM_MAX_GROW_COPY_BB_INSNS);
1377 FOR_BB_INSNS (bb, insn)
1379 if (INSN_P (insn))
1380 size += get_attr_min_length (insn);
1383 if (size <= max_size)
1384 return true;
1386 if (dump_file)
1388 fprintf (dump_file,
1389 "Block %d can't be copied because its size = %d.\n",
1390 bb->index, size);
1393 return false;
1396 /* Return the length of unconditional jump instruction. */
1399 get_uncond_jump_length (void)
1401 int length;
1403 start_sequence ();
1404 rtx_code_label *label = emit_label (gen_label_rtx ());
1405 rtx_insn *jump = emit_jump_insn (targetm.gen_jump (label));
1406 length = get_attr_min_length (jump);
1407 end_sequence ();
1409 return length;
1412 /* Create a forwarder block to OLD_BB starting with NEW_LABEL and in the
1413 other partition wrt OLD_BB. */
1415 static basic_block
1416 create_forwarder_block (rtx_code_label *new_label, basic_block old_bb)
1418 /* Put the new label and a jump in the new basic block. */
1419 rtx_insn *label = emit_label (new_label);
1420 rtx_code_label *old_label = block_label (old_bb);
1421 rtx_insn *jump = emit_jump_insn (targetm.gen_jump (old_label));
1422 JUMP_LABEL (jump) = old_label;
1424 /* Create the new basic block and put it in last position. */
1425 basic_block last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
1426 basic_block new_bb = create_basic_block (label, jump, last_bb);
1427 new_bb->aux = last_bb->aux;
1428 new_bb->count = old_bb->count;
1429 last_bb->aux = new_bb;
1431 emit_barrier_after_bb (new_bb);
1433 make_single_succ_edge (new_bb, old_bb, 0);
1435 /* Make sure the new basic block is in the other partition. */
1436 unsigned new_partition = BB_PARTITION (old_bb);
1437 new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1438 BB_SET_PARTITION (new_bb, new_partition);
1440 return new_bb;
1443 /* The common landing pad in block OLD_BB has edges from both partitions.
1444 Add a new landing pad that will just jump to the old one and split the
1445 edges so that no EH edge crosses partitions. */
1447 static void
1448 sjlj_fix_up_crossing_landing_pad (basic_block old_bb)
1450 const unsigned lp_len = cfun->eh->lp_array->length ();
1451 edge_iterator ei;
1452 edge e;
1454 /* Generate the new common landing-pad label. */
1455 rtx_code_label *new_label = gen_label_rtx ();
1456 LABEL_PRESERVE_P (new_label) = 1;
1458 /* Create the forwarder block. */
1459 basic_block new_bb = create_forwarder_block (new_label, old_bb);
1461 /* Create the map from old to new lp index and initialize it. */
1462 unsigned *index_map = (unsigned *) alloca (lp_len * sizeof (unsigned));
1463 memset (index_map, 0, lp_len * sizeof (unsigned));
1465 /* Fix up the edges. */
1466 for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
1467 if (e->src != new_bb && BB_PARTITION (e->src) == BB_PARTITION (new_bb))
1469 rtx_insn *insn = BB_END (e->src);
1470 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1472 gcc_assert (note != NULL);
1473 const unsigned old_index = INTVAL (XEXP (note, 0));
1475 /* Generate the new landing-pad structure. */
1476 if (index_map[old_index] == 0)
1478 eh_landing_pad old_lp = (*cfun->eh->lp_array)[old_index];
1479 eh_landing_pad new_lp = gen_eh_landing_pad (old_lp->region);
1480 new_lp->post_landing_pad = old_lp->post_landing_pad;
1481 new_lp->landing_pad = new_label;
1482 index_map[old_index] = new_lp->index;
1484 XEXP (note, 0) = GEN_INT (index_map[old_index]);
1486 /* Adjust the edge to the new destination. */
1487 redirect_edge_succ (e, new_bb);
1489 else
1490 ei_next (&ei);
1493 /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1494 Add a new landing pad that will just jump to the old one and split the
1495 edges so that no EH edge crosses partitions. */
1497 static void
1498 dw2_fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
1500 eh_landing_pad new_lp;
1501 edge_iterator ei;
1502 edge e;
1504 /* Generate the new landing-pad structure. */
1505 new_lp = gen_eh_landing_pad (old_lp->region);
1506 new_lp->post_landing_pad = old_lp->post_landing_pad;
1507 new_lp->landing_pad = gen_label_rtx ();
1508 LABEL_PRESERVE_P (new_lp->landing_pad) = 1;
1510 /* Create the forwarder block. */
1511 basic_block new_bb = create_forwarder_block (new_lp->landing_pad, old_bb);
1513 /* Fix up the edges. */
1514 for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
1515 if (e->src != new_bb && BB_PARTITION (e->src) == BB_PARTITION (new_bb))
1517 rtx_insn *insn = BB_END (e->src);
1518 rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1520 gcc_assert (note != NULL);
1521 gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index);
1522 XEXP (note, 0) = GEN_INT (new_lp->index);
1524 /* Adjust the edge to the new destination. */
1525 redirect_edge_succ (e, new_bb);
1527 else
1528 ei_next (&ei);
1532 /* Ensure that all hot bbs are included in a hot path through the
1533 procedure. This is done by calling this function twice, once
1534 with WALK_UP true (to look for paths from the entry to hot bbs) and
1535 once with WALK_UP false (to look for paths from hot bbs to the exit).
1536 Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs
1537 to BBS_IN_HOT_PARTITION. */
1539 static unsigned int
1540 sanitize_hot_paths (bool walk_up, unsigned int cold_bb_count,
1541 vec<basic_block> *bbs_in_hot_partition)
1543 /* Callers check this. */
1544 gcc_checking_assert (cold_bb_count);
1546 /* Keep examining hot bbs while we still have some left to check
1547 and there are remaining cold bbs. */
1548 vec<basic_block> hot_bbs_to_check = bbs_in_hot_partition->copy ();
1549 while (! hot_bbs_to_check.is_empty ()
1550 && cold_bb_count)
1552 basic_block bb = hot_bbs_to_check.pop ();
1553 vec<edge, va_gc> *edges = walk_up ? bb->preds : bb->succs;
1554 edge e;
1555 edge_iterator ei;
1556 profile_probability highest_probability
1557 = profile_probability::uninitialized ();
1558 profile_count highest_count = profile_count::uninitialized ();
1559 bool found = false;
1561 /* Walk the preds/succs and check if there is at least one already
1562 marked hot. Keep track of the most frequent pred/succ so that we
1563 can mark it hot if we don't find one. */
1564 FOR_EACH_EDGE (e, ei, edges)
1566 basic_block reach_bb = walk_up ? e->src : e->dest;
1568 if (e->flags & EDGE_DFS_BACK)
1569 continue;
1571 /* Do not expect profile insanities when profile was not adjusted. */
1572 if (e->probability == profile_probability::never ()
1573 || e->count () == profile_count::zero ())
1574 continue;
1576 if (BB_PARTITION (reach_bb) != BB_COLD_PARTITION)
1578 found = true;
1579 break;
1581 /* The following loop will look for the hottest edge via
1582 the edge count, if it is non-zero, then fallback to
1583 the edge probability. */
1584 if (!(e->count () > highest_count))
1585 highest_count = e->count ();
1586 if (!highest_probability.initialized_p ()
1587 || e->probability > highest_probability)
1588 highest_probability = e->probability;
1591 /* If bb is reached by (or reaches, in the case of !WALK_UP) another hot
1592 block (or unpartitioned, e.g. the entry block) then it is ok. If not,
1593 then the most frequent pred (or succ) needs to be adjusted. In the
1594 case where multiple preds/succs have the same frequency (e.g. a
1595 50-50 branch), then both will be adjusted. */
1596 if (found)
1597 continue;
1599 FOR_EACH_EDGE (e, ei, edges)
1601 if (e->flags & EDGE_DFS_BACK)
1602 continue;
1603 /* Do not expect profile insanities when profile was not adjusted. */
1604 if (e->probability == profile_probability::never ()
1605 || e->count () == profile_count::zero ())
1606 continue;
1607 /* Select the hottest edge using the edge count, if it is non-zero,
1608 then fallback to the edge probability. */
1609 if (highest_count.initialized_p ())
1611 if (!(e->count () >= highest_count))
1612 continue;
1614 else if (!(e->probability >= highest_probability))
1615 continue;
1617 basic_block reach_bb = walk_up ? e->src : e->dest;
1619 /* We have a hot bb with an immediate dominator that is cold.
1620 The dominator needs to be re-marked hot. */
1621 BB_SET_PARTITION (reach_bb, BB_HOT_PARTITION);
1622 if (dump_file)
1623 fprintf (dump_file, "Promoting bb %i to hot partition to sanitize "
1624 "profile of bb %i in %s walk\n", reach_bb->index,
1625 bb->index, walk_up ? "backward" : "forward");
1626 cold_bb_count--;
1628 /* Now we need to examine newly-hot reach_bb to see if it is also
1629 dominated by a cold bb. */
1630 bbs_in_hot_partition->safe_push (reach_bb);
1631 hot_bbs_to_check.safe_push (reach_bb);
1634 hot_bbs_to_check.release ();
1636 return cold_bb_count;
1640 /* Find the basic blocks that are rarely executed and need to be moved to
1641 a separate section of the .o file (to cut down on paging and improve
1642 cache locality). Return a vector of all edges that cross. */
1644 static vec<edge>
1645 find_rarely_executed_basic_blocks_and_crossing_edges (void)
1647 vec<edge> crossing_edges = vNULL;
1648 basic_block bb;
1649 edge e;
1650 edge_iterator ei;
1651 unsigned int cold_bb_count = 0;
1652 auto_vec<basic_block> bbs_in_hot_partition;
1654 propagate_unlikely_bbs_forward ();
1656 /* Mark which partition (hot/cold) each basic block belongs in. */
1657 FOR_EACH_BB_FN (bb, cfun)
1659 bool cold_bb = false;
1661 if (probably_never_executed_bb_p (cfun, bb))
1663 /* Handle profile insanities created by upstream optimizations
1664 by also checking the incoming edge weights. If there is a non-cold
1665 incoming edge, conservatively prevent this block from being split
1666 into the cold section. */
1667 cold_bb = true;
1668 FOR_EACH_EDGE (e, ei, bb->preds)
1669 if (!probably_never_executed_edge_p (cfun, e))
1671 cold_bb = false;
1672 break;
1675 if (cold_bb)
1677 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1678 cold_bb_count++;
1680 else
1682 BB_SET_PARTITION (bb, BB_HOT_PARTITION);
1683 bbs_in_hot_partition.safe_push (bb);
1687 /* Ensure that hot bbs are included along a hot path from the entry to exit.
1688 Several different possibilities may include cold bbs along all paths
1689 to/from a hot bb. One is that there are edge weight insanities
1690 due to optimization phases that do not properly update basic block profile
1691 counts. The second is that the entry of the function may not be hot, because
1692 it is entered fewer times than the number of profile training runs, but there
1693 is a loop inside the function that causes blocks within the function to be
1694 above the threshold for hotness. This is fixed by walking up from hot bbs
1695 to the entry block, and then down from hot bbs to the exit, performing
1696 partitioning fixups as necessary. */
1697 if (cold_bb_count)
1699 mark_dfs_back_edges ();
1700 cold_bb_count = sanitize_hot_paths (true, cold_bb_count,
1701 &bbs_in_hot_partition);
1702 if (cold_bb_count)
1703 sanitize_hot_paths (false, cold_bb_count, &bbs_in_hot_partition);
1705 hash_set <basic_block> set;
1706 find_bbs_reachable_by_hot_paths (&set);
1707 FOR_EACH_BB_FN (bb, cfun)
1708 if (!set.contains (bb))
1709 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1712 /* The format of .gcc_except_table does not allow landing pads to
1713 be in a different partition as the throw. Fix this by either
1714 moving the landing pads or inserting forwarder landing pads. */
1715 if (cfun->eh->lp_array)
1717 const bool sjlj
1718 = (targetm_common.except_unwind_info (&global_options) == UI_SJLJ);
1719 unsigned i;
1720 eh_landing_pad lp;
1722 FOR_EACH_VEC_ELT (*cfun->eh->lp_array, i, lp)
1724 bool all_same, all_diff;
1726 if (lp == NULL
1727 || lp->landing_pad == NULL_RTX
1728 || !LABEL_P (lp->landing_pad))
1729 continue;
1731 all_same = all_diff = true;
1732 bb = BLOCK_FOR_INSN (lp->landing_pad);
1733 FOR_EACH_EDGE (e, ei, bb->preds)
1735 gcc_assert (e->flags & EDGE_EH);
1736 if (BB_PARTITION (bb) == BB_PARTITION (e->src))
1737 all_diff = false;
1738 else
1739 all_same = false;
1742 if (all_same)
1744 else if (all_diff)
1746 int which = BB_PARTITION (bb);
1747 which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1748 BB_SET_PARTITION (bb, which);
1750 else if (sjlj)
1751 sjlj_fix_up_crossing_landing_pad (bb);
1752 else
1753 dw2_fix_up_crossing_landing_pad (lp, bb);
1755 /* There is a single, common landing pad in SJLJ mode. */
1756 if (sjlj)
1757 break;
1761 /* Mark every edge that crosses between sections. */
1762 FOR_EACH_BB_FN (bb, cfun)
1763 FOR_EACH_EDGE (e, ei, bb->succs)
1765 unsigned int flags = e->flags;
1767 /* We should never have EDGE_CROSSING set yet. */
1768 gcc_checking_assert ((flags & EDGE_CROSSING) == 0);
1770 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1771 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1772 && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1774 crossing_edges.safe_push (e);
1775 flags |= EDGE_CROSSING;
1778 /* Now that we've split eh edges as appropriate, allow landing pads
1779 to be merged with the post-landing pads. */
1780 flags &= ~EDGE_PRESERVE;
1782 e->flags = flags;
1785 return crossing_edges;
1788 /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
1790 static void
1791 set_edge_can_fallthru_flag (void)
1793 basic_block bb;
1795 FOR_EACH_BB_FN (bb, cfun)
1797 edge e;
1798 edge_iterator ei;
1800 FOR_EACH_EDGE (e, ei, bb->succs)
1802 e->flags &= ~EDGE_CAN_FALLTHRU;
1804 /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
1805 if (e->flags & EDGE_FALLTHRU)
1806 e->flags |= EDGE_CAN_FALLTHRU;
1809 /* If the BB ends with an invertible condjump all (2) edges are
1810 CAN_FALLTHRU edges. */
1811 if (EDGE_COUNT (bb->succs) != 2)
1812 continue;
1813 if (!any_condjump_p (BB_END (bb)))
1814 continue;
1816 rtx_jump_insn *bb_end_jump = as_a <rtx_jump_insn *> (BB_END (bb));
1817 if (!invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0))
1818 continue;
1819 invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0);
1820 EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
1821 EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
1825 /* If any destination of a crossing edge does not have a label, add label;
1826 Convert any easy fall-through crossing edges to unconditional jumps. */
1828 static void
1829 add_labels_and_missing_jumps (vec<edge> crossing_edges)
1831 size_t i;
1832 edge e;
1834 FOR_EACH_VEC_ELT (crossing_edges, i, e)
1836 basic_block src = e->src;
1837 basic_block dest = e->dest;
1838 rtx_jump_insn *new_jump;
1840 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1841 continue;
1843 /* Make sure dest has a label. */
1844 rtx_code_label *label = block_label (dest);
1846 /* Nothing to do for non-fallthru edges. */
1847 if (src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1848 continue;
1849 if ((e->flags & EDGE_FALLTHRU) == 0)
1850 continue;
1852 /* If the block does not end with a control flow insn, then we
1853 can trivially add a jump to the end to fixup the crossing.
1854 Otherwise the jump will have to go in a new bb, which will
1855 be handled by fix_up_fall_thru_edges function. */
1856 if (control_flow_insn_p (BB_END (src)))
1857 continue;
1859 /* Make sure there's only one successor. */
1860 gcc_assert (single_succ_p (src));
1862 new_jump = emit_jump_insn_after (targetm.gen_jump (label), BB_END (src));
1863 BB_END (src) = new_jump;
1864 JUMP_LABEL (new_jump) = label;
1865 LABEL_NUSES (label) += 1;
1867 emit_barrier_after_bb (src);
1869 /* Mark edge as non-fallthru. */
1870 e->flags &= ~EDGE_FALLTHRU;
1874 /* Find any bb's where the fall-through edge is a crossing edge (note that
1875 these bb's must also contain a conditional jump or end with a call
1876 instruction; we've already dealt with fall-through edges for blocks
1877 that didn't have a conditional jump or didn't end with call instruction
1878 in the call to add_labels_and_missing_jumps). Convert the fall-through
1879 edge to non-crossing edge by inserting a new bb to fall-through into.
1880 The new bb will contain an unconditional jump (crossing edge) to the
1881 original fall through destination. */
1883 static void
1884 fix_up_fall_thru_edges (void)
1886 basic_block cur_bb;
1888 FOR_EACH_BB_FN (cur_bb, cfun)
1890 edge succ1;
1891 edge succ2;
1892 edge fall_thru = NULL;
1893 edge cond_jump = NULL;
1895 fall_thru = NULL;
1896 if (EDGE_COUNT (cur_bb->succs) > 0)
1897 succ1 = EDGE_SUCC (cur_bb, 0);
1898 else
1899 succ1 = NULL;
1901 if (EDGE_COUNT (cur_bb->succs) > 1)
1902 succ2 = EDGE_SUCC (cur_bb, 1);
1903 else
1904 succ2 = NULL;
1906 /* Find the fall-through edge. */
1908 if (succ1
1909 && (succ1->flags & EDGE_FALLTHRU))
1911 fall_thru = succ1;
1912 cond_jump = succ2;
1914 else if (succ2
1915 && (succ2->flags & EDGE_FALLTHRU))
1917 fall_thru = succ2;
1918 cond_jump = succ1;
1920 else if (succ2 && EDGE_COUNT (cur_bb->succs) > 2)
1921 fall_thru = find_fallthru_edge (cur_bb->succs);
1923 if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)))
1925 /* Check to see if the fall-thru edge is a crossing edge. */
1927 if (fall_thru->flags & EDGE_CROSSING)
1929 /* The fall_thru edge crosses; now check the cond jump edge, if
1930 it exists. */
1932 bool cond_jump_crosses = true;
1933 int invert_worked = 0;
1934 rtx_insn *old_jump = BB_END (cur_bb);
1936 /* Find the jump instruction, if there is one. */
1938 if (cond_jump)
1940 if (!(cond_jump->flags & EDGE_CROSSING))
1941 cond_jump_crosses = false;
1943 /* We know the fall-thru edge crosses; if the cond
1944 jump edge does NOT cross, and its destination is the
1945 next block in the bb order, invert the jump
1946 (i.e. fix it so the fall through does not cross and
1947 the cond jump does). */
1949 if (!cond_jump_crosses)
1951 /* Find label in fall_thru block. We've already added
1952 any missing labels, so there must be one. */
1954 rtx_code_label *fall_thru_label
1955 = block_label (fall_thru->dest);
1957 if (old_jump && fall_thru_label)
1959 rtx_jump_insn *old_jump_insn
1960 = dyn_cast <rtx_jump_insn *> (old_jump);
1961 if (old_jump_insn)
1962 invert_worked = invert_jump (old_jump_insn,
1963 fall_thru_label, 0);
1966 if (invert_worked)
1968 fall_thru->flags &= ~EDGE_FALLTHRU;
1969 cond_jump->flags |= EDGE_FALLTHRU;
1970 update_br_prob_note (cur_bb);
1971 std::swap (fall_thru, cond_jump);
1972 cond_jump->flags |= EDGE_CROSSING;
1973 fall_thru->flags &= ~EDGE_CROSSING;
1978 if (cond_jump_crosses || !invert_worked)
1980 /* This is the case where both edges out of the basic
1981 block are crossing edges. Here we will fix up the
1982 fall through edge. The jump edge will be taken care
1983 of later. The EDGE_CROSSING flag of fall_thru edge
1984 is unset before the call to force_nonfallthru
1985 function because if a new basic-block is created
1986 this edge remains in the current section boundary
1987 while the edge between new_bb and the fall_thru->dest
1988 becomes EDGE_CROSSING. */
1990 fall_thru->flags &= ~EDGE_CROSSING;
1991 basic_block new_bb = force_nonfallthru (fall_thru);
1993 if (new_bb)
1995 new_bb->aux = cur_bb->aux;
1996 cur_bb->aux = new_bb;
1998 /* This is done by force_nonfallthru_and_redirect. */
1999 gcc_assert (BB_PARTITION (new_bb)
2000 == BB_PARTITION (cur_bb));
2002 single_succ_edge (new_bb)->flags |= EDGE_CROSSING;
2004 else
2006 /* If a new basic-block was not created; restore
2007 the EDGE_CROSSING flag. */
2008 fall_thru->flags |= EDGE_CROSSING;
2011 /* Add barrier after new jump */
2012 emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
2019 /* This function checks the destination block of a "crossing jump" to
2020 see if it has any crossing predecessors that begin with a code label
2021 and end with an unconditional jump. If so, it returns that predecessor
2022 block. (This is to avoid creating lots of new basic blocks that all
2023 contain unconditional jumps to the same destination). */
2025 static basic_block
2026 find_jump_block (basic_block jump_dest)
2028 basic_block source_bb = NULL;
2029 edge e;
2030 rtx_insn *insn;
2031 edge_iterator ei;
2033 FOR_EACH_EDGE (e, ei, jump_dest->preds)
2034 if (e->flags & EDGE_CROSSING)
2036 basic_block src = e->src;
2038 /* Check each predecessor to see if it has a label, and contains
2039 only one executable instruction, which is an unconditional jump.
2040 If so, we can use it. */
2042 if (LABEL_P (BB_HEAD (src)))
2043 for (insn = BB_HEAD (src);
2044 !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
2045 insn = NEXT_INSN (insn))
2047 if (INSN_P (insn)
2048 && insn == BB_END (src)
2049 && JUMP_P (insn)
2050 && !any_condjump_p (insn))
2052 source_bb = src;
2053 break;
2057 if (source_bb)
2058 break;
2061 return source_bb;
2064 /* Find all BB's with conditional jumps that are crossing edges;
2065 insert a new bb and make the conditional jump branch to the new
2066 bb instead (make the new bb same color so conditional branch won't
2067 be a 'crossing' edge). Insert an unconditional jump from the
2068 new bb to the original destination of the conditional jump. */
2070 static void
2071 fix_crossing_conditional_branches (void)
2073 basic_block cur_bb;
2074 basic_block new_bb;
2075 basic_block dest;
2076 edge succ1;
2077 edge succ2;
2078 edge crossing_edge;
2079 edge new_edge;
2080 rtx set_src;
2081 rtx old_label = NULL_RTX;
2082 rtx_code_label *new_label;
2084 FOR_EACH_BB_FN (cur_bb, cfun)
2086 crossing_edge = NULL;
2087 if (EDGE_COUNT (cur_bb->succs) > 0)
2088 succ1 = EDGE_SUCC (cur_bb, 0);
2089 else
2090 succ1 = NULL;
2092 if (EDGE_COUNT (cur_bb->succs) > 1)
2093 succ2 = EDGE_SUCC (cur_bb, 1);
2094 else
2095 succ2 = NULL;
2097 /* We already took care of fall-through edges, so only one successor
2098 can be a crossing edge. */
2100 if (succ1 && (succ1->flags & EDGE_CROSSING))
2101 crossing_edge = succ1;
2102 else if (succ2 && (succ2->flags & EDGE_CROSSING))
2103 crossing_edge = succ2;
2105 if (crossing_edge)
2107 rtx_insn *old_jump = BB_END (cur_bb);
2109 /* Check to make sure the jump instruction is a
2110 conditional jump. */
2112 set_src = NULL_RTX;
2114 if (any_condjump_p (old_jump))
2116 if (GET_CODE (PATTERN (old_jump)) == SET)
2117 set_src = SET_SRC (PATTERN (old_jump));
2118 else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
2120 set_src = XVECEXP (PATTERN (old_jump), 0,0);
2121 if (GET_CODE (set_src) == SET)
2122 set_src = SET_SRC (set_src);
2123 else
2124 set_src = NULL_RTX;
2128 if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
2130 rtx_jump_insn *old_jump_insn =
2131 as_a <rtx_jump_insn *> (old_jump);
2133 if (GET_CODE (XEXP (set_src, 1)) == PC)
2134 old_label = XEXP (set_src, 2);
2135 else if (GET_CODE (XEXP (set_src, 2)) == PC)
2136 old_label = XEXP (set_src, 1);
2138 /* Check to see if new bb for jumping to that dest has
2139 already been created; if so, use it; if not, create
2140 a new one. */
2142 new_bb = find_jump_block (crossing_edge->dest);
2144 if (new_bb)
2145 new_label = block_label (new_bb);
2146 else
2148 basic_block last_bb;
2149 rtx_code_label *old_jump_target;
2150 rtx_jump_insn *new_jump;
2152 /* Create new basic block to be dest for
2153 conditional jump. */
2155 /* Put appropriate instructions in new bb. */
2157 new_label = gen_label_rtx ();
2158 emit_label (new_label);
2160 gcc_assert (GET_CODE (old_label) == LABEL_REF);
2161 old_jump_target = old_jump_insn->jump_target ();
2162 new_jump = as_a <rtx_jump_insn *>
2163 (emit_jump_insn (targetm.gen_jump (old_jump_target)));
2164 new_jump->set_jump_target (old_jump_target);
2166 last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
2167 new_bb = create_basic_block (new_label, new_jump, last_bb);
2168 new_bb->aux = last_bb->aux;
2169 last_bb->aux = new_bb;
2171 emit_barrier_after_bb (new_bb);
2173 /* Make sure new bb is in same partition as source
2174 of conditional branch. */
2175 BB_COPY_PARTITION (new_bb, cur_bb);
2178 /* Make old jump branch to new bb. */
2180 redirect_jump (old_jump_insn, new_label, 0);
2182 /* Remove crossing_edge as predecessor of 'dest'. */
2184 dest = crossing_edge->dest;
2186 redirect_edge_succ (crossing_edge, new_bb);
2188 /* Make a new edge from new_bb to old dest; new edge
2189 will be a successor for new_bb and a predecessor
2190 for 'dest'. */
2192 if (EDGE_COUNT (new_bb->succs) == 0)
2193 new_edge = make_single_succ_edge (new_bb, dest, 0);
2194 else
2195 new_edge = EDGE_SUCC (new_bb, 0);
2197 crossing_edge->flags &= ~EDGE_CROSSING;
2198 new_edge->flags |= EDGE_CROSSING;
2204 /* Find any unconditional branches that cross between hot and cold
2205 sections. Convert them into indirect jumps instead. */
2207 static void
2208 fix_crossing_unconditional_branches (void)
2210 basic_block cur_bb;
2211 rtx_insn *last_insn;
2212 rtx label;
2213 rtx label_addr;
2214 rtx_insn *indirect_jump_sequence;
2215 rtx_insn *jump_insn = NULL;
2216 rtx new_reg;
2217 rtx_insn *cur_insn;
2218 edge succ;
2220 FOR_EACH_BB_FN (cur_bb, cfun)
2222 last_insn = BB_END (cur_bb);
2224 if (EDGE_COUNT (cur_bb->succs) < 1)
2225 continue;
2227 succ = EDGE_SUCC (cur_bb, 0);
2229 /* Check to see if bb ends in a crossing (unconditional) jump. At
2230 this point, no crossing jumps should be conditional. */
2232 if (JUMP_P (last_insn)
2233 && (succ->flags & EDGE_CROSSING))
2235 gcc_assert (!any_condjump_p (last_insn));
2237 /* Make sure the jump is not already an indirect or table jump. */
2239 if (!computed_jump_p (last_insn)
2240 && !tablejump_p (last_insn, NULL, NULL))
2242 /* We have found a "crossing" unconditional branch. Now
2243 we must convert it to an indirect jump. First create
2244 reference of label, as target for jump. */
2246 label = JUMP_LABEL (last_insn);
2247 label_addr = gen_rtx_LABEL_REF (Pmode, label);
2248 LABEL_NUSES (label) += 1;
2250 /* Get a register to use for the indirect jump. */
2252 new_reg = gen_reg_rtx (Pmode);
2254 /* Generate indirect the jump sequence. */
2256 start_sequence ();
2257 emit_move_insn (new_reg, label_addr);
2258 emit_indirect_jump (new_reg);
2259 indirect_jump_sequence = get_insns ();
2260 end_sequence ();
2262 /* Make sure every instruction in the new jump sequence has
2263 its basic block set to be cur_bb. */
2265 for (cur_insn = indirect_jump_sequence; cur_insn;
2266 cur_insn = NEXT_INSN (cur_insn))
2268 if (!BARRIER_P (cur_insn))
2269 BLOCK_FOR_INSN (cur_insn) = cur_bb;
2270 if (JUMP_P (cur_insn))
2271 jump_insn = cur_insn;
2274 /* Insert the new (indirect) jump sequence immediately before
2275 the unconditional jump, then delete the unconditional jump. */
2277 emit_insn_before (indirect_jump_sequence, last_insn);
2278 delete_insn (last_insn);
2280 JUMP_LABEL (jump_insn) = label;
2281 LABEL_NUSES (label)++;
2283 /* Make BB_END for cur_bb be the jump instruction (NOT the
2284 barrier instruction at the end of the sequence...). */
2286 BB_END (cur_bb) = jump_insn;
2292 /* Update CROSSING_JUMP_P flags on all jump insns. */
2294 static void
2295 update_crossing_jump_flags (void)
2297 basic_block bb;
2298 edge e;
2299 edge_iterator ei;
2301 FOR_EACH_BB_FN (bb, cfun)
2302 FOR_EACH_EDGE (e, ei, bb->succs)
2303 if (e->flags & EDGE_CROSSING)
2305 if (JUMP_P (BB_END (bb)))
2306 CROSSING_JUMP_P (BB_END (bb)) = 1;
2307 break;
2311 /* Reorder basic blocks using the software trace cache (STC) algorithm. */
2313 static void
2314 reorder_basic_blocks_software_trace_cache (void)
2316 if (dump_file)
2317 fprintf (dump_file, "\nReordering with the STC algorithm.\n\n");
2319 int n_traces;
2320 int i;
2321 struct trace *traces;
2323 /* We are estimating the length of uncond jump insn only once since the code
2324 for getting the insn length always returns the minimal length now. */
2325 if (uncond_jump_length == 0)
2326 uncond_jump_length = get_uncond_jump_length ();
2328 /* We need to know some information for each basic block. */
2329 array_size = GET_ARRAY_SIZE (last_basic_block_for_fn (cfun));
2330 bbd = XNEWVEC (bbro_basic_block_data, array_size);
2331 for (i = 0; i < array_size; i++)
2333 bbd[i].start_of_trace = -1;
2334 bbd[i].end_of_trace = -1;
2335 bbd[i].in_trace = -1;
2336 bbd[i].visited = 0;
2337 bbd[i].priority = -1;
2338 bbd[i].heap = NULL;
2339 bbd[i].node = NULL;
2342 traces = XNEWVEC (struct trace, n_basic_blocks_for_fn (cfun));
2343 n_traces = 0;
2344 find_traces (&n_traces, traces);
2345 connect_traces (n_traces, traces);
2346 FREE (traces);
2347 FREE (bbd);
2350 /* Return true if edge E1 is more desirable as a fallthrough edge than
2351 edge E2 is. */
2353 static bool
2354 edge_order (edge e1, edge e2)
2356 return e1->count () > e2->count ();
2359 /* Reorder basic blocks using the "simple" algorithm. This tries to
2360 maximize the dynamic number of branches that are fallthrough, without
2361 copying instructions. The algorithm is greedy, looking at the most
2362 frequently executed branch first. */
2364 static void
2365 reorder_basic_blocks_simple (void)
2367 if (dump_file)
2368 fprintf (dump_file, "\nReordering with the \"simple\" algorithm.\n\n");
2370 edge *edges = new edge[2 * n_basic_blocks_for_fn (cfun)];
2372 /* First, collect all edges that can be optimized by reordering blocks:
2373 simple jumps and conditional jumps, as well as the function entry edge. */
2375 int n = 0;
2376 edges[n++] = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0);
2378 basic_block bb;
2379 FOR_EACH_BB_FN (bb, cfun)
2381 rtx_insn *end = BB_END (bb);
2383 if (computed_jump_p (end) || tablejump_p (end, NULL, NULL))
2384 continue;
2386 /* We cannot optimize asm goto. */
2387 if (JUMP_P (end) && extract_asm_operands (end))
2388 continue;
2390 if (single_succ_p (bb))
2391 edges[n++] = EDGE_SUCC (bb, 0);
2392 else if (any_condjump_p (end))
2394 edge e0 = EDGE_SUCC (bb, 0);
2395 edge e1 = EDGE_SUCC (bb, 1);
2396 /* When optimizing for size it is best to keep the original
2397 fallthrough edges. */
2398 if (e1->flags & EDGE_FALLTHRU)
2399 std::swap (e0, e1);
2400 edges[n++] = e0;
2401 edges[n++] = e1;
2405 /* Sort the edges, the most desirable first. When optimizing for size
2406 all edges are equally desirable. */
2408 if (optimize_function_for_speed_p (cfun))
2409 std::stable_sort (edges, edges + n, edge_order);
2411 /* Now decide which of those edges to make fallthrough edges. We set
2412 BB_VISITED if a block already has a fallthrough successor assigned
2413 to it. We make ->AUX of an endpoint point to the opposite endpoint
2414 of a sequence of blocks that fall through, and ->AUX will be NULL
2415 for a block that is in such a sequence but not an endpoint anymore.
2417 To start with, everything points to itself, nothing is assigned yet. */
2419 FOR_ALL_BB_FN (bb, cfun)
2421 bb->aux = bb;
2422 bb->flags &= ~BB_VISITED;
2425 EXIT_BLOCK_PTR_FOR_FN (cfun)->aux = 0;
2427 /* Now for all edges, the most desirable first, see if that edge can
2428 connect two sequences. If it can, update AUX and BB_VISITED; if it
2429 cannot, zero out the edge in the table. */
2431 for (int j = 0; j < n; j++)
2433 edge e = edges[j];
2435 basic_block tail_a = e->src;
2436 basic_block head_b = e->dest;
2437 basic_block head_a = (basic_block) tail_a->aux;
2438 basic_block tail_b = (basic_block) head_b->aux;
2440 /* An edge cannot connect two sequences if:
2441 - it crosses partitions;
2442 - its src is not a current endpoint;
2443 - its dest is not a current endpoint;
2444 - or, it would create a loop. */
2446 if (e->flags & EDGE_CROSSING
2447 || tail_a->flags & BB_VISITED
2448 || !tail_b
2449 || (!(head_b->flags & BB_VISITED) && head_b != tail_b)
2450 || tail_a == tail_b)
2452 edges[j] = 0;
2453 continue;
2456 tail_a->aux = 0;
2457 head_b->aux = 0;
2458 head_a->aux = tail_b;
2459 tail_b->aux = head_a;
2460 tail_a->flags |= BB_VISITED;
2463 /* Put the pieces together, in the same order that the start blocks of
2464 the sequences already had. The hot/cold partitioning gives a little
2465 complication: as a first pass only do this for blocks in the same
2466 partition as the start block, and (if there is anything left to do)
2467 in a second pass handle the other partition. */
2469 basic_block last_tail = (basic_block) ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux;
2471 int current_partition
2472 = BB_PARTITION (last_tail == ENTRY_BLOCK_PTR_FOR_FN (cfun)
2473 ? EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0)->dest
2474 : last_tail);
2475 bool need_another_pass = true;
2477 for (int pass = 0; pass < 2 && need_another_pass; pass++)
2479 need_another_pass = false;
2481 FOR_EACH_BB_FN (bb, cfun)
2482 if ((bb->flags & BB_VISITED && bb->aux) || bb->aux == bb)
2484 if (BB_PARTITION (bb) != current_partition)
2486 need_another_pass = true;
2487 continue;
2490 last_tail->aux = bb;
2491 last_tail = (basic_block) bb->aux;
2494 current_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
2497 last_tail->aux = 0;
2499 /* Finally, link all the chosen fallthrough edges. */
2501 for (int j = 0; j < n; j++)
2502 if (edges[j])
2503 edges[j]->src->aux = edges[j]->dest;
2505 delete[] edges;
2507 /* If the entry edge no longer falls through we have to make a new
2508 block so it can do so again. */
2510 edge e = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0);
2511 if (e->dest != ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux)
2513 force_nonfallthru (e);
2514 e->src->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux;
2518 /* Reorder basic blocks. The main entry point to this file. */
2520 static void
2521 reorder_basic_blocks (void)
2523 gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
2525 if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1)
2526 return;
2528 set_edge_can_fallthru_flag ();
2529 mark_dfs_back_edges ();
2531 switch (flag_reorder_blocks_algorithm)
2533 case REORDER_BLOCKS_ALGORITHM_SIMPLE:
2534 reorder_basic_blocks_simple ();
2535 break;
2537 case REORDER_BLOCKS_ALGORITHM_STC:
2538 reorder_basic_blocks_software_trace_cache ();
2539 break;
2541 default:
2542 gcc_unreachable ();
2545 relink_block_chain (/*stay_in_cfglayout_mode=*/true);
2547 if (dump_file)
2549 if (dump_flags & TDF_DETAILS)
2550 dump_reg_info (dump_file);
2551 dump_flow_info (dump_file, dump_flags);
2554 /* Signal that rtl_verify_flow_info_1 can now verify that there
2555 is at most one switch between hot/cold sections. */
2556 crtl->bb_reorder_complete = true;
2559 /* Determine which partition the first basic block in the function
2560 belongs to, then find the first basic block in the current function
2561 that belongs to a different section, and insert a
2562 NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
2563 instruction stream. When writing out the assembly code,
2564 encountering this note will make the compiler switch between the
2565 hot and cold text sections. */
2567 void
2568 insert_section_boundary_note (void)
2570 basic_block bb;
2571 bool switched_sections = false;
2572 int current_partition = 0;
2574 if (!crtl->has_bb_partition)
2575 return;
2577 FOR_EACH_BB_FN (bb, cfun)
2579 if (!current_partition)
2580 current_partition = BB_PARTITION (bb);
2581 if (BB_PARTITION (bb) != current_partition)
2583 gcc_assert (!switched_sections);
2584 switched_sections = true;
2585 emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS, BB_HEAD (bb));
2586 current_partition = BB_PARTITION (bb);
2590 /* Make sure crtl->has_bb_partition matches reality even if bbpart finds
2591 some hot and some cold basic blocks, but later one of those kinds is
2592 optimized away. */
2593 crtl->has_bb_partition = switched_sections;
2596 namespace {
2598 const pass_data pass_data_reorder_blocks =
2600 RTL_PASS, /* type */
2601 "bbro", /* name */
2602 OPTGROUP_NONE, /* optinfo_flags */
2603 TV_REORDER_BLOCKS, /* tv_id */
2604 0, /* properties_required */
2605 0, /* properties_provided */
2606 0, /* properties_destroyed */
2607 0, /* todo_flags_start */
2608 0, /* todo_flags_finish */
2611 class pass_reorder_blocks : public rtl_opt_pass
2613 public:
2614 pass_reorder_blocks (gcc::context *ctxt)
2615 : rtl_opt_pass (pass_data_reorder_blocks, ctxt)
2618 /* opt_pass methods: */
2619 virtual bool gate (function *)
2621 if (targetm.cannot_modify_jumps_p ())
2622 return false;
2623 return (optimize > 0
2624 && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
2627 virtual unsigned int execute (function *);
2629 }; // class pass_reorder_blocks
2631 unsigned int
2632 pass_reorder_blocks::execute (function *fun)
2634 basic_block bb;
2636 /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2637 splitting possibly introduced more crossjumping opportunities. */
2638 cfg_layout_initialize (CLEANUP_EXPENSIVE);
2640 reorder_basic_blocks ();
2641 cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_NO_PARTITIONING);
2643 FOR_EACH_BB_FN (bb, fun)
2644 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
2645 bb->aux = bb->next_bb;
2646 cfg_layout_finalize ();
2648 return 0;
2651 } // anon namespace
2653 rtl_opt_pass *
2654 make_pass_reorder_blocks (gcc::context *ctxt)
2656 return new pass_reorder_blocks (ctxt);
2659 /* Duplicate a block (that we already know ends in a computed jump) into its
2660 predecessors, where possible. Return whether anything is changed. */
2661 static bool
2662 maybe_duplicate_computed_goto (basic_block bb, int max_size)
2664 if (single_pred_p (bb))
2665 return false;
2667 /* Make sure that the block is small enough. */
2668 rtx_insn *insn;
2669 FOR_BB_INSNS (bb, insn)
2670 if (INSN_P (insn))
2672 max_size -= get_attr_min_length (insn);
2673 if (max_size < 0)
2674 return false;
2677 bool changed = false;
2678 edge e;
2679 edge_iterator ei;
2680 for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
2682 basic_block pred = e->src;
2684 /* Do not duplicate BB into PRED if that is the last predecessor, or if
2685 we cannot merge a copy of BB with PRED. */
2686 if (single_pred_p (bb)
2687 || !single_succ_p (pred)
2688 || e->flags & EDGE_COMPLEX
2689 || pred->index < NUM_FIXED_BLOCKS
2690 || (JUMP_P (BB_END (pred)) && !simplejump_p (BB_END (pred)))
2691 || (JUMP_P (BB_END (pred)) && CROSSING_JUMP_P (BB_END (pred))))
2693 ei_next (&ei);
2694 continue;
2697 if (dump_file)
2698 fprintf (dump_file, "Duplicating computed goto bb %d into bb %d\n",
2699 bb->index, e->src->index);
2701 /* Remember if PRED can be duplicated; if so, the copy of BB merged
2702 with PRED can be duplicated as well. */
2703 bool can_dup_more = can_duplicate_block_p (pred);
2705 /* Make a copy of BB, merge it into PRED. */
2706 basic_block copy = duplicate_block (bb, e, NULL);
2707 emit_barrier_after_bb (copy);
2708 reorder_insns_nobb (BB_HEAD (copy), BB_END (copy), BB_END (pred));
2709 merge_blocks (pred, copy);
2711 changed = true;
2713 /* Try to merge the resulting merged PRED into further predecessors. */
2714 if (can_dup_more)
2715 maybe_duplicate_computed_goto (pred, max_size);
2718 return changed;
2721 /* Duplicate the blocks containing computed gotos. This basically unfactors
2722 computed gotos that were factored early on in the compilation process to
2723 speed up edge based data flow. We used to not unfactor them again, which
2724 can seriously pessimize code with many computed jumps in the source code,
2725 such as interpreters. See e.g. PR15242. */
2726 static void
2727 duplicate_computed_gotos (function *fun)
2729 /* We are estimating the length of uncond jump insn only once
2730 since the code for getting the insn length always returns
2731 the minimal length now. */
2732 if (uncond_jump_length == 0)
2733 uncond_jump_length = get_uncond_jump_length ();
2735 /* Never copy a block larger than this. */
2736 int max_size
2737 = uncond_jump_length * PARAM_VALUE (PARAM_MAX_GOTO_DUPLICATION_INSNS);
2739 bool changed = false;
2741 /* Try to duplicate all blocks that end in a computed jump and that
2742 can be duplicated at all. */
2743 basic_block bb;
2744 FOR_EACH_BB_FN (bb, fun)
2745 if (computed_jump_p (BB_END (bb)) && can_duplicate_block_p (bb))
2746 changed |= maybe_duplicate_computed_goto (bb, max_size);
2748 /* Duplicating blocks will redirect edges and may cause hot blocks
2749 previously reached by both hot and cold blocks to become dominated
2750 only by cold blocks. */
2751 if (changed)
2752 fixup_partitions ();
2755 namespace {
2757 const pass_data pass_data_duplicate_computed_gotos =
2759 RTL_PASS, /* type */
2760 "compgotos", /* name */
2761 OPTGROUP_NONE, /* optinfo_flags */
2762 TV_REORDER_BLOCKS, /* tv_id */
2763 0, /* properties_required */
2764 0, /* properties_provided */
2765 0, /* properties_destroyed */
2766 0, /* todo_flags_start */
2767 0, /* todo_flags_finish */
2770 class pass_duplicate_computed_gotos : public rtl_opt_pass
2772 public:
2773 pass_duplicate_computed_gotos (gcc::context *ctxt)
2774 : rtl_opt_pass (pass_data_duplicate_computed_gotos, ctxt)
2777 /* opt_pass methods: */
2778 virtual bool gate (function *);
2779 virtual unsigned int execute (function *);
2781 }; // class pass_duplicate_computed_gotos
2783 bool
2784 pass_duplicate_computed_gotos::gate (function *fun)
2786 if (targetm.cannot_modify_jumps_p ())
2787 return false;
2788 return (optimize > 0
2789 && flag_expensive_optimizations
2790 && ! optimize_function_for_size_p (fun));
2793 unsigned int
2794 pass_duplicate_computed_gotos::execute (function *fun)
2796 duplicate_computed_gotos (fun);
2798 return 0;
2801 } // anon namespace
2803 rtl_opt_pass *
2804 make_pass_duplicate_computed_gotos (gcc::context *ctxt)
2806 return new pass_duplicate_computed_gotos (ctxt);
2809 /* This function is the main 'entrance' for the optimization that
2810 partitions hot and cold basic blocks into separate sections of the
2811 .o file (to improve performance and cache locality). Ideally it
2812 would be called after all optimizations that rearrange the CFG have
2813 been called. However part of this optimization may introduce new
2814 register usage, so it must be called before register allocation has
2815 occurred. This means that this optimization is actually called
2816 well before the optimization that reorders basic blocks (see
2817 function above).
2819 This optimization checks the feedback information to determine
2820 which basic blocks are hot/cold, updates flags on the basic blocks
2821 to indicate which section they belong in. This information is
2822 later used for writing out sections in the .o file. Because hot
2823 and cold sections can be arbitrarily large (within the bounds of
2824 memory), far beyond the size of a single function, it is necessary
2825 to fix up all edges that cross section boundaries, to make sure the
2826 instructions used can actually span the required distance. The
2827 fixes are described below.
2829 Fall-through edges must be changed into jumps; it is not safe or
2830 legal to fall through across a section boundary. Whenever a
2831 fall-through edge crossing a section boundary is encountered, a new
2832 basic block is inserted (in the same section as the fall-through
2833 source), and the fall through edge is redirected to the new basic
2834 block. The new basic block contains an unconditional jump to the
2835 original fall-through target. (If the unconditional jump is
2836 insufficient to cross section boundaries, that is dealt with a
2837 little later, see below).
2839 In order to deal with architectures that have short conditional
2840 branches (which cannot span all of memory) we take any conditional
2841 jump that attempts to cross a section boundary and add a level of
2842 indirection: it becomes a conditional jump to a new basic block, in
2843 the same section. The new basic block contains an unconditional
2844 jump to the original target, in the other section.
2846 For those architectures whose unconditional branch is also
2847 incapable of reaching all of memory, those unconditional jumps are
2848 converted into indirect jumps, through a register.
2850 IMPORTANT NOTE: This optimization causes some messy interactions
2851 with the cfg cleanup optimizations; those optimizations want to
2852 merge blocks wherever possible, and to collapse indirect jump
2853 sequences (change "A jumps to B jumps to C" directly into "A jumps
2854 to C"). Those optimizations can undo the jump fixes that
2855 partitioning is required to make (see above), in order to ensure
2856 that jumps attempting to cross section boundaries are really able
2857 to cover whatever distance the jump requires (on many architectures
2858 conditional or unconditional jumps are not able to reach all of
2859 memory). Therefore tests have to be inserted into each such
2860 optimization to make sure that it does not undo stuff necessary to
2861 cross partition boundaries. This would be much less of a problem
2862 if we could perform this optimization later in the compilation, but
2863 unfortunately the fact that we may need to create indirect jumps
2864 (through registers) requires that this optimization be performed
2865 before register allocation.
2867 Hot and cold basic blocks are partitioned and put in separate
2868 sections of the .o file, to reduce paging and improve cache
2869 performance (hopefully). This can result in bits of code from the
2870 same function being widely separated in the .o file. However this
2871 is not obvious to the current bb structure. Therefore we must take
2872 care to ensure that: 1). There are no fall_thru edges that cross
2873 between sections; 2). For those architectures which have "short"
2874 conditional branches, all conditional branches that attempt to
2875 cross between sections are converted to unconditional branches;
2876 and, 3). For those architectures which have "short" unconditional
2877 branches, all unconditional branches that attempt to cross between
2878 sections are converted to indirect jumps.
2880 The code for fixing up fall_thru edges that cross between hot and
2881 cold basic blocks does so by creating new basic blocks containing
2882 unconditional branches to the appropriate label in the "other"
2883 section. The new basic block is then put in the same (hot or cold)
2884 section as the original conditional branch, and the fall_thru edge
2885 is modified to fall into the new basic block instead. By adding
2886 this level of indirection we end up with only unconditional branches
2887 crossing between hot and cold sections.
2889 Conditional branches are dealt with by adding a level of indirection.
2890 A new basic block is added in the same (hot/cold) section as the
2891 conditional branch, and the conditional branch is retargeted to the
2892 new basic block. The new basic block contains an unconditional branch
2893 to the original target of the conditional branch (in the other section).
2895 Unconditional branches are dealt with by converting them into
2896 indirect jumps. */
2898 namespace {
2900 const pass_data pass_data_partition_blocks =
2902 RTL_PASS, /* type */
2903 "bbpart", /* name */
2904 OPTGROUP_NONE, /* optinfo_flags */
2905 TV_REORDER_BLOCKS, /* tv_id */
2906 PROP_cfglayout, /* properties_required */
2907 0, /* properties_provided */
2908 0, /* properties_destroyed */
2909 0, /* todo_flags_start */
2910 0, /* todo_flags_finish */
2913 class pass_partition_blocks : public rtl_opt_pass
2915 public:
2916 pass_partition_blocks (gcc::context *ctxt)
2917 : rtl_opt_pass (pass_data_partition_blocks, ctxt)
2920 /* opt_pass methods: */
2921 virtual bool gate (function *);
2922 virtual unsigned int execute (function *);
2924 }; // class pass_partition_blocks
2926 bool
2927 pass_partition_blocks::gate (function *fun)
2929 /* The optimization to partition hot/cold basic blocks into separate
2930 sections of the .o file does not work well with linkonce or with
2931 user defined section attributes. Don't call it if either case
2932 arises. */
2933 return (flag_reorder_blocks_and_partition
2934 && optimize
2935 /* See pass_reorder_blocks::gate. We should not partition if
2936 we are going to omit the reordering. */
2937 && optimize_function_for_speed_p (fun)
2938 && !DECL_COMDAT_GROUP (current_function_decl)
2939 && !lookup_attribute ("section", DECL_ATTRIBUTES (fun->decl))
2940 /* Workaround a bug in GDB where read_partial_die doesn't cope
2941 with DIEs with DW_AT_ranges, see PR81115. */
2942 && !(in_lto_p && MAIN_NAME_P (DECL_NAME (fun->decl))));
2945 unsigned
2946 pass_partition_blocks::execute (function *fun)
2948 vec<edge> crossing_edges;
2950 if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1)
2951 return 0;
2953 df_set_flags (DF_DEFER_INSN_RESCAN);
2955 crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
2956 if (!crossing_edges.exists ())
2957 /* Make sure to process deferred rescans and clear changeable df flags. */
2958 return TODO_df_finish;
2960 crtl->has_bb_partition = true;
2962 /* Make sure the source of any crossing edge ends in a jump and the
2963 destination of any crossing edge has a label. */
2964 add_labels_and_missing_jumps (crossing_edges);
2966 /* Convert all crossing fall_thru edges to non-crossing fall
2967 thrus to unconditional jumps (that jump to the original fall
2968 through dest). */
2969 fix_up_fall_thru_edges ();
2971 /* If the architecture does not have conditional branches that can
2972 span all of memory, convert crossing conditional branches into
2973 crossing unconditional branches. */
2974 if (!HAS_LONG_COND_BRANCH)
2975 fix_crossing_conditional_branches ();
2977 /* If the architecture does not have unconditional branches that
2978 can span all of memory, convert crossing unconditional branches
2979 into indirect jumps. Since adding an indirect jump also adds
2980 a new register usage, update the register usage information as
2981 well. */
2982 if (!HAS_LONG_UNCOND_BRANCH)
2983 fix_crossing_unconditional_branches ();
2985 update_crossing_jump_flags ();
2987 /* Clear bb->aux fields that the above routines were using. */
2988 clear_aux_for_blocks ();
2990 crossing_edges.release ();
2992 /* ??? FIXME: DF generates the bb info for a block immediately.
2993 And by immediately, I mean *during* creation of the block.
2995 #0 df_bb_refs_collect
2996 #1 in df_bb_refs_record
2997 #2 in create_basic_block_structure
2999 Which means that the bb_has_eh_pred test in df_bb_refs_collect
3000 will *always* fail, because no edges can have been added to the
3001 block yet. Which of course means we don't add the right
3002 artificial refs, which means we fail df_verify (much) later.
3004 Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
3005 that we also shouldn't grab data from the new blocks those new
3006 insns are in either. In this way one can create the block, link
3007 it up properly, and have everything Just Work later, when deferred
3008 insns are processed.
3010 In the meantime, we have no other option but to throw away all
3011 of the DF data and recompute it all. */
3012 if (fun->eh->lp_array)
3014 df_finish_pass (true);
3015 df_scan_alloc (NULL);
3016 df_scan_blocks ();
3017 /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
3018 data. We blindly generated all of them when creating the new
3019 landing pad. Delete those assignments we don't use. */
3020 df_set_flags (DF_LR_RUN_DCE);
3021 df_analyze ();
3024 /* Make sure to process deferred rescans and clear changeable df flags. */
3025 return TODO_df_finish;
3028 } // anon namespace
3030 rtl_opt_pass *
3031 make_pass_partition_blocks (gcc::context *ctxt)
3033 return new pass_partition_blocks (ctxt);