Line data Source code
1 : /* Basic block reordering routines for the GNU compiler.
2 : Copyright (C) 2000-2026 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 : #include "system.h"
95 : #include "coretypes.h"
96 : #include "backend.h"
97 : #include "target.h"
98 : #include "rtl.h"
99 : #include "tree.h"
100 : #include "cfghooks.h"
101 : #include "df.h"
102 : #include "memmodel.h"
103 : #include "optabs.h"
104 : #include "regs.h"
105 : #include "emit-rtl.h"
106 : #include "output.h"
107 : #include "insn-attr.h"
108 : #include "expr.h"
109 : #include "tree-pass.h"
110 : #include "cfgrtl.h"
111 : #include "cfganal.h"
112 : #include "cfgbuild.h"
113 : #include "cfgcleanup.h"
114 : #include "bb-reorder.h"
115 : #include "except.h"
116 : #include "alloc-pool.h"
117 : #include "fibonacci_heap.h"
118 : #include "stringpool.h"
119 : #include "attribs.h"
120 : #include "common/common-target.h"
121 :
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
126 :
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
131 :
132 : #define uncond_jump_length \
133 : (this_target_bb_reorder->x_uncond_jump_length)
134 :
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};
137 :
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};
140 :
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
144 :
145 : typedef fibonacci_heap <long, basic_block_def> bb_heap_t;
146 : typedef fibonacci_node <long, basic_block_def> bb_heap_node_t;
147 :
148 : /* Structure to hold needed information for each basic block. */
149 : struct bbro_basic_block_data
150 : {
151 : /* Which trace is the bb start of (-1 means it is not a start of any). */
152 : int start_of_trace;
153 :
154 : /* Which trace is the bb end of (-1 means it is not an end of any). */
155 : int end_of_trace;
156 :
157 : /* Which trace is the bb in? */
158 : int in_trace;
159 :
160 : /* Which trace was this bb visited in? */
161 : int visited;
162 :
163 : /* Cached maximum frequency of interesting incoming edges.
164 : Minus one means not yet computed. */
165 : int priority;
166 :
167 : /* Which heap is BB in (if any)? */
168 : bb_heap_t *heap;
169 :
170 : /* Which heap node is BB in (if any)? */
171 : bb_heap_node_t *node;
172 : };
173 :
174 : /* The current size of the following dynamic array. */
175 : static int array_size;
176 :
177 : /* The array which holds needed information for basic blocks. */
178 : static bbro_basic_block_data *bbd;
179 :
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)
183 :
184 : /* Free the memory and set the pointer to NULL. */
185 : #define FREE(P) (gcc_assert (P), free (P), P = 0)
186 :
187 : /* Structure for holding information about a trace. */
188 : struct trace
189 : {
190 : /* First and last basic block of the trace. */
191 : basic_block first, last;
192 :
193 : /* The round of the STC creation which this trace was found in. */
194 : int round;
195 :
196 : /* The length (i.e. the number of basic blocks) of the trace. */
197 : int length;
198 : };
199 :
200 : /* Maximum count of one of the entry blocks. */
201 : static profile_count max_entry_count;
202 :
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);
212 :
213 : /* Return the trace number in which BB was visited. */
214 :
215 : static int
216 38513232 : bb_visited_trace (const_basic_block bb)
217 : {
218 38513232 : gcc_assert (bb->index < array_size);
219 38513232 : return bbd[bb->index].visited;
220 : }
221 :
222 : /* This function marks BB that it was visited in trace number TRACE. */
223 :
224 : static void
225 10244252 : mark_bb_visited (basic_block bb, int trace)
226 : {
227 10244252 : bbd[bb->index].visited = trace;
228 10244252 : if (bbd[bb->index].heap)
229 : {
230 388520 : bbd[bb->index].heap->delete_node (bbd[bb->index].node);
231 388520 : bbd[bb->index].heap = NULL;
232 388520 : bbd[bb->index].node = NULL;
233 : }
234 10244252 : }
235 :
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. */
243 :
244 : static bool
245 8933824 : push_to_next_round_p (const_basic_block bb, int round, int number_of_rounds,
246 : profile_count count_th)
247 : {
248 8933824 : bool there_exists_another_round;
249 8933824 : bool block_not_hot_enough;
250 :
251 8933824 : there_exists_another_round = round < number_of_rounds - 1;
252 :
253 8933824 : block_not_hot_enough = (bb->count < count_th
254 8933824 : || probably_never_executed_bb_p (cfun, bb));
255 :
256 4304815 : if (there_exists_another_round
257 : && block_not_hot_enough)
258 : return true;
259 : else
260 5445279 : return false;
261 : }
262 :
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. */
266 :
267 : static void
268 607561 : find_traces (int *n_traces, struct trace *traces)
269 : {
270 607561 : int i;
271 607561 : int number_of_rounds;
272 607561 : edge e;
273 607561 : edge_iterator ei;
274 607561 : bb_heap_t *heap = new bb_heap_t (LONG_MIN);
275 :
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). */
279 :
280 607561 : number_of_rounds = N_ROUNDS - 1;
281 :
282 : /* Insert entry points of function into heap. */
283 607561 : max_entry_count = profile_count::zero ();
284 1215122 : FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs)
285 : {
286 607561 : bbd[e->dest->index].heap = heap;
287 607561 : bbd[e->dest->index].node = heap->insert (bb_to_key (e->dest), e->dest);
288 607561 : if (e->dest->count > max_entry_count)
289 606398 : max_entry_count = e->dest->count;
290 : }
291 :
292 : /* Find the traces. */
293 3037805 : for (i = 0; i < number_of_rounds; i++)
294 : {
295 2430244 : profile_count count_threshold;
296 :
297 2430244 : if (dump_file)
298 92 : fprintf (dump_file, "STC - round %d\n", i + 1);
299 :
300 2430244 : count_threshold = max_entry_count.apply_scale (exec_threshold[i], 1000);
301 :
302 2430244 : find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
303 : count_threshold, traces, n_traces, i, &heap,
304 : number_of_rounds);
305 : }
306 607561 : delete heap;
307 :
308 607561 : if (dump_file)
309 : {
310 115 : for (i = 0; i < *n_traces; i++)
311 : {
312 92 : basic_block bb;
313 92 : fprintf (dump_file, "Trace %d (round %d): ", i + 1,
314 92 : traces[i].round + 1);
315 92 : for (bb = traces[i].first;
316 188 : bb != traces[i].last;
317 96 : bb = (basic_block) bb->aux)
318 : {
319 96 : fprintf (dump_file, "%d [", bb->index);
320 96 : bb->count.dump (dump_file);
321 96 : fprintf (dump_file, "] ");
322 : }
323 92 : fprintf (dump_file, "%d [", bb->index);
324 92 : bb->count.dump (dump_file);
325 92 : fprintf (dump_file, "]\n");
326 : }
327 23 : fflush (dump_file);
328 : }
329 607561 : }
330 :
331 : /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
332 : (with sequential number TRACE_N). */
333 :
334 : static basic_block
335 166174 : rotate_loop (edge back_edge, struct trace *trace, int trace_n)
336 : {
337 166174 : basic_block bb;
338 :
339 : /* Information about the best end (end after rotation) of the loop. */
340 166174 : basic_block best_bb = NULL;
341 166174 : edge best_edge = NULL;
342 166174 : 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 166174 : bool is_preferred = false;
346 :
347 : /* Find the most frequent edge that goes out from current trace. */
348 166174 : bb = back_edge->dest;
349 638786 : do
350 : {
351 638786 : edge e;
352 638786 : edge_iterator ei;
353 :
354 1794644 : FOR_EACH_EDGE (e, ei, bb->succs)
355 1155858 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
356 1155858 : && bb_visited_trace (e->dest) != trace_n
357 466304 : && (e->flags & EDGE_CAN_FALLTHRU)
358 1585761 : && !(e->flags & EDGE_COMPLEX))
359 : {
360 429903 : if (is_preferred)
361 : {
362 : /* The best edge is preferred. */
363 261007 : if (!bb_visited_trace (e->dest)
364 261007 : || bbd[e->dest->index].start_of_trace >= 0)
365 : {
366 : /* The current edge E is also preferred. */
367 257096 : if (e->count () > best_count)
368 : {
369 65184 : best_count = e->count ();
370 65184 : best_edge = e;
371 65184 : best_bb = bb;
372 : }
373 : }
374 : }
375 : else
376 : {
377 168896 : if (!bb_visited_trace (e->dest)
378 168896 : || bbd[e->dest->index].start_of_trace >= 0)
379 : {
380 : /* The current edge E is preferred. */
381 164846 : is_preferred = true;
382 164846 : best_count = e->count ();
383 164846 : best_edge = e;
384 164846 : best_bb = bb;
385 : }
386 : else
387 : {
388 4050 : if (!best_edge || e->count () > best_count)
389 : {
390 3378 : best_count = e->count ();
391 3378 : best_edge = e;
392 3378 : best_bb = bb;
393 : }
394 : }
395 : }
396 : }
397 638786 : bb = (basic_block) bb->aux;
398 : }
399 638786 : while (bb != back_edge->dest);
400 :
401 166174 : if (best_bb)
402 : {
403 : /* Rotate the loop so that the BEST_EDGE goes out from the last block of
404 : the trace. */
405 166082 : if (back_edge->dest == trace->first)
406 : {
407 6172 : trace->first = (basic_block) best_bb->aux;
408 : }
409 : else
410 : {
411 : basic_block prev_bb;
412 :
413 : for (prev_bb = trace->first;
414 483698 : prev_bb->aux != back_edge->dest;
415 : prev_bb = (basic_block) prev_bb->aux)
416 : ;
417 159910 : prev_bb->aux = best_bb->aux;
418 :
419 : /* Try to get rid of uncond jump to cond jump. */
420 159910 : if (single_succ_p (prev_bb))
421 : {
422 136963 : basic_block header = single_succ (prev_bb);
423 :
424 : /* Duplicate HEADER if it is a small block containing cond jump
425 : in the end. */
426 264838 : if (any_condjump_p (BB_END (header)) && copy_bb_p (header, 0)
427 136963 : && !CROSSING_JUMP_P (BB_END (header)))
428 0 : copy_bb (header, single_succ_edge (prev_bb), prev_bb, trace_n);
429 : }
430 : }
431 : }
432 : else
433 : {
434 : /* We have not found suitable loop tail so do no rotation. */
435 92 : best_bb = back_edge->src;
436 : }
437 166174 : best_bb->aux = NULL;
438 166174 : return best_bb;
439 : }
440 :
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. */
448 :
449 : static void
450 2430244 : 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)
453 : {
454 : /* Heap for discarded basic blocks which are possible starting points for
455 : the next round. */
456 2430244 : bb_heap_t *new_heap = new bb_heap_t (LONG_MIN);
457 2430244 : bool for_size = optimize_function_for_size_p (cfun);
458 :
459 8483444 : while (!(*heap)->empty ())
460 : {
461 6053200 : basic_block bb;
462 6053200 : struct trace *trace;
463 6053200 : edge best_edge, e;
464 6053200 : long key;
465 6053200 : edge_iterator ei;
466 :
467 6053200 : bb = (*heap)->extract_min ();
468 6053200 : bbd[bb->index].heap = NULL;
469 6053200 : bbd[bb->index].node = NULL;
470 :
471 6053200 : if (dump_file)
472 108 : fprintf (dump_file, "Getting bb %d\n", bb->index);
473 :
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. */
478 :
479 6053200 : if (!for_size
480 6053200 : && push_to_next_round_p (bb, round, number_of_rounds,
481 : count_th))
482 : {
483 1513712 : int key = bb_to_key (bb);
484 1513712 : bbd[bb->index].heap = new_heap;
485 1513712 : bbd[bb->index].node = new_heap->insert (key, bb);
486 :
487 1513712 : if (dump_file)
488 16 : fprintf (dump_file,
489 : " Possible start point of next round: %d (key: %d)\n",
490 : bb->index, key);
491 1513712 : continue;
492 1513712 : }
493 :
494 4539488 : trace = traces + *n_traces;
495 4539488 : trace->first = bb;
496 4539488 : trace->round = round;
497 4539488 : trace->length = 0;
498 4539488 : bbd[bb->index].in_trace = *n_traces;
499 4539488 : (*n_traces)++;
500 :
501 9982793 : do
502 : {
503 9982793 : bool ends_in_call;
504 :
505 : /* The probability and count of the best edge. */
506 9982793 : profile_probability best_prob = profile_probability::uninitialized ();
507 9982793 : profile_count best_count = profile_count::uninitialized ();
508 :
509 9982793 : best_edge = NULL;
510 9982793 : mark_bb_visited (bb, *n_traces);
511 9982793 : trace->length++;
512 :
513 9982793 : if (dump_file)
514 188 : fprintf (dump_file, "Basic block %d was visited in trace %d\n",
515 : bb->index, *n_traces);
516 :
517 9982793 : ends_in_call = block_ends_with_call_p (bb);
518 :
519 : /* Select the successor that will be placed after BB. */
520 25027654 : FOR_EACH_EDGE (e, ei, bb->succs)
521 : {
522 15044861 : gcc_assert (!(e->flags & EDGE_FAKE));
523 :
524 15044861 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
525 8328941 : continue;
526 :
527 14334993 : if (bb_visited_trace (e->dest)
528 14334993 : && bb_visited_trace (e->dest) != *n_traces)
529 2662378 : continue;
530 :
531 : /* If partitioning hot/cold basic blocks, don't consider edges
532 : that cross section boundaries. */
533 11672615 : if (BB_PARTITION (e->dest) != BB_PARTITION (bb))
534 410181 : continue;
535 :
536 11262434 : profile_probability prob = e->probability;
537 11262434 : profile_count count = e->dest->count;
538 :
539 : /* The only sensible preference for a call instruction is the
540 : fallthru edge. Don't bother selecting anything else. */
541 11262434 : if (ends_in_call)
542 : {
543 1070205 : if (e->flags & EDGE_CAN_FALLTHRU)
544 : {
545 555591 : best_edge = e;
546 555591 : best_prob = prob;
547 555591 : best_count = count;
548 : }
549 1070205 : continue;
550 : }
551 :
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 9997576 : if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
556 9935015 : || !prob.initialized_p ()
557 20125693 : || ((prob.to_reg_br_prob_base () < branch_th
558 10192229 : || e->count () < count_th) && (!for_size)))
559 3476309 : continue;
560 :
561 6715920 : if (better_edge_p (bb, e, prob, count, best_prob, best_count,
562 : best_edge))
563 : {
564 6150368 : best_edge = e;
565 6150368 : best_prob = prob;
566 6150368 : best_count = count;
567 : }
568 : }
569 :
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 9982793 : if (best_edge
577 6152310 : && EDGE_COUNT (best_edge->dest->preds) >= 2
578 12598773 : && copy_bb_p (best_edge->dest, 0))
579 : {
580 72543 : bool only_crossing_preds = true;
581 72543 : edge e;
582 72543 : edge_iterator ei;
583 98810 : FOR_EACH_EDGE (e, ei, best_edge->dest->preds)
584 98789 : if (e != best_edge && !(e->flags & EDGE_CROSSING))
585 : {
586 : only_crossing_preds = false;
587 : break;
588 : }
589 72543 : if (!only_crossing_preds)
590 72522 : best_edge = NULL;
591 : }
592 :
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 : destination. It breaks long trace and reduces long jumps.
597 :
598 : Take if-then-else as an example.
599 : A
600 : / \
601 : B C
602 : \ /
603 : D
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.
608 :
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 9982793 : if (best_edge && for_size
613 9982793 : && (EDGE_COUNT (best_edge->dest->succs) > 1
614 138420 : || EDGE_COUNT (best_edge->dest->preds) > 1))
615 : best_edge = NULL;
616 :
617 : /* Add all non-selected successors to the heaps. */
618 25027654 : FOR_EACH_EDGE (e, ei, bb->succs)
619 : {
620 24341973 : if (e == best_edge
621 9167597 : || e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
622 23502590 : || bb_visited_trace (e->dest))
623 9297112 : continue;
624 :
625 5747749 : key = bb_to_key (e->dest);
626 :
627 5747749 : if (bbd[e->dest->index].heap)
628 : {
629 : /* E->DEST is already in some heap. */
630 1427302 : if (key != bbd[e->dest->index].node->get_key ())
631 : {
632 0 : if (dump_file)
633 : {
634 0 : fprintf (dump_file,
635 : "Changing key for bb %d from %ld to %ld.\n",
636 : e->dest->index,
637 0 : (long) bbd[e->dest->index].node->get_key (),
638 : key);
639 : }
640 0 : bbd[e->dest->index].heap->replace_key
641 0 : (bbd[e->dest->index].node, key);
642 : }
643 : }
644 : else
645 : {
646 4320447 : bb_heap_t *which_heap = *heap;
647 :
648 4320447 : profile_probability prob = e->probability;
649 :
650 4320447 : if (!(e->flags & EDGE_CAN_FALLTHRU)
651 4001483 : || (e->flags & EDGE_COMPLEX)
652 3939872 : || !prob.initialized_p ()
653 3938494 : || prob.to_reg_br_prob_base () < branch_th
654 8321930 : || e->count () < count_th)
655 : {
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. */
660 :
661 3243071 : if (!for_size && push_to_next_round_p (e->dest, round,
662 : number_of_rounds,
663 : count_th))
664 : which_heap = new_heap;
665 : }
666 :
667 4320447 : bbd[e->dest->index].heap = which_heap;
668 4320447 : bbd[e->dest->index].node = which_heap->insert (key, e->dest);
669 :
670 4320447 : if (dump_file)
671 : {
672 87 : fprintf (dump_file,
673 : " Possible start of %s round: %d (key: %ld)\n",
674 : (which_heap == new_heap) ? "next" : "this",
675 87 : e->dest->index, (long) key);
676 : }
677 :
678 : }
679 : }
680 :
681 9982793 : if (best_edge) /* Suitable successor was found. */
682 : {
683 5877264 : if (bb_visited_trace (best_edge->dest) == *n_traces)
684 : {
685 : /* We do nothing with one basic block loops. */
686 433959 : if (best_edge->dest != bb)
687 : {
688 622653 : if (best_edge->count ()
689 207551 : > best_edge->dest->count.apply_scale (4, 5))
690 : {
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. */
694 :
695 166231 : if (best_edge->dest
696 166231 : != ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
697 : {
698 166174 : if (dump_file)
699 : {
700 0 : fprintf (dump_file,
701 : "Rotating loop %d - %d\n",
702 : best_edge->dest->index, bb->index);
703 : }
704 166174 : bb->aux = best_edge->dest;
705 166174 : bbd[best_edge->dest->index].in_trace =
706 166174 : (*n_traces) - 1;
707 166174 : bb = rotate_loop (best_edge, trace, *n_traces);
708 : }
709 : }
710 : else
711 : {
712 : /* The loop has less than 4 iterations. */
713 :
714 41320 : if (single_succ_p (bb)
715 54082 : && copy_bb_p (best_edge->dest,
716 : optimize_edge_for_speed_p
717 12762 : (best_edge)))
718 : {
719 7059 : bb = copy_bb (best_edge->dest, best_edge, bb,
720 : *n_traces);
721 7059 : trace->length++;
722 : }
723 : }
724 : }
725 :
726 : /* Terminate the trace. */
727 433959 : break;
728 : }
729 : else
730 : {
731 : /* Check for a situation
732 :
733 : A
734 : /|
735 : B |
736 : \|
737 : C
738 :
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.
743 :
744 : When optimizing for size, A B C is always the best order.
745 :
746 : This situation is created for example by:
747 :
748 : if (A) B;
749 : C;
750 :
751 : */
752 :
753 14978923 : FOR_EACH_EDGE (e, ei, bb->succs)
754 9549694 : if (e != best_edge
755 4118217 : && (e->flags & EDGE_CAN_FALLTHRU)
756 3607746 : && !(e->flags & EDGE_COMPLEX)
757 3607746 : && !bb_visited_trace (e->dest)
758 11222220 : && single_pred_p (e->dest)
759 1686602 : && !(e->flags & EDGE_CROSSING)
760 1640516 : && single_succ_p (e->dest)
761 1001225 : && (single_succ_edge (e->dest)->flags
762 1001225 : & EDGE_CAN_FALLTHRU)
763 881146 : && !(single_succ_edge (e->dest)->flags & EDGE_COMPLEX)
764 881146 : && single_succ (e->dest) == best_edge->dest
765 9846639 : && (e->dest->count * 2
766 9846639 : >= best_edge->count () || for_size))
767 : {
768 14076 : best_edge = e;
769 14076 : if (dump_file)
770 0 : fprintf (dump_file, "Selecting BB %d\n",
771 0 : best_edge->dest->index);
772 : break;
773 : }
774 :
775 5443305 : bb->aux = best_edge->dest;
776 5443305 : bbd[best_edge->dest->index].in_trace = (*n_traces) - 1;
777 5443305 : bb = best_edge->dest;
778 : }
779 : }
780 : }
781 9548834 : while (best_edge);
782 4539488 : trace->last = bb;
783 4539488 : bbd[trace->first->index].start_of_trace = *n_traces - 1;
784 4539488 : if (bbd[trace->last->index].end_of_trace != *n_traces - 1)
785 : {
786 4539488 : 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 10067539 : FOR_EACH_EDGE (e, ei, trace->last->succs)
790 5528051 : if (EDGE_FREQUENCY (e) > bbd[e->dest->index].priority)
791 4208707 : bbd[e->dest->index].priority = EDGE_FREQUENCY (e);
792 : }
793 :
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 10067539 : FOR_EACH_EDGE (e, ei, bb->succs)
798 : {
799 8987085 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
800 5528051 : || bb_visited_trace (e->dest))
801 3459034 : continue;
802 :
803 2069017 : if (bbd[e->dest->index].heap)
804 : {
805 2069017 : key = bb_to_key (e->dest);
806 2069017 : if (key != bbd[e->dest->index].node->get_key ())
807 : {
808 1331755 : if (dump_file)
809 : {
810 45 : fprintf (dump_file,
811 : "Changing key for bb %d from %ld to %ld.\n",
812 : e->dest->index,
813 45 : (long) bbd[e->dest->index].node->get_key (), key);
814 : }
815 1331755 : bbd[e->dest->index].heap->replace_key
816 1331755 : (bbd[e->dest->index].node, key);
817 : }
818 : }
819 : }
820 : }
821 :
822 2430244 : delete (*heap);
823 :
824 : /* "Return" the new heap. */
825 2430244 : *heap = new_heap;
826 2430244 : }
827 :
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). */
831 :
832 : static basic_block
833 261459 : copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
834 : {
835 261459 : basic_block new_bb;
836 :
837 261459 : new_bb = duplicate_block (old_bb, e, bb);
838 261459 : BB_COPY_PARTITION (new_bb, old_bb);
839 :
840 261459 : gcc_assert (e->dest == new_bb);
841 :
842 261459 : if (dump_file)
843 0 : fprintf (dump_file,
844 : "Duplicated bb %d (created bb %d)\n",
845 : old_bb->index, new_bb->index);
846 :
847 261459 : if (new_bb->index >= array_size
848 261142 : || last_basic_block_for_fn (cfun) > array_size)
849 : {
850 317 : int i;
851 317 : int new_size;
852 :
853 317 : new_size = MAX (last_basic_block_for_fn (cfun), new_bb->index + 1);
854 317 : new_size = GET_ARRAY_SIZE (new_size);
855 317 : bbd = XRESIZEVEC (bbro_basic_block_data, bbd, new_size);
856 23542 : for (i = array_size; i < new_size; i++)
857 : {
858 23225 : bbd[i].start_of_trace = -1;
859 23225 : bbd[i].end_of_trace = -1;
860 23225 : bbd[i].in_trace = -1;
861 23225 : bbd[i].visited = 0;
862 23225 : bbd[i].priority = -1;
863 23225 : bbd[i].heap = NULL;
864 23225 : bbd[i].node = NULL;
865 : }
866 317 : array_size = new_size;
867 :
868 317 : if (dump_file)
869 : {
870 0 : fprintf (dump_file,
871 : "Growing the dynamic array to %d elements.\n",
872 : array_size);
873 : }
874 : }
875 :
876 261459 : gcc_assert (!bb_visited_trace (e->dest));
877 261459 : mark_bb_visited (new_bb, trace);
878 261459 : new_bb->aux = bb->aux;
879 261459 : bb->aux = new_bb;
880 :
881 261459 : bbd[new_bb->index].in_trace = trace;
882 :
883 261459 : return new_bb;
884 : }
885 :
886 : /* Compute and return the key (for the heap) of the basic block BB. */
887 :
888 : static long
889 9938039 : bb_to_key (basic_block bb)
890 : {
891 9938039 : edge e;
892 9938039 : edge_iterator ei;
893 :
894 : /* Use index as key to align with its original order. */
895 9938039 : if (optimize_function_for_size_p (cfun))
896 621616 : return bb->index;
897 :
898 : /* Do not start in probably never executed blocks. */
899 :
900 9316423 : if (BB_PARTITION (bb) == BB_COLD_PARTITION
901 9316423 : || probably_never_executed_bb_p (cfun, bb))
902 : return BB_FREQ_MAX;
903 :
904 : /* Prefer blocks whose predecessor is an end of some trace
905 : or whose predecessor edge is EDGE_DFS_BACK. */
906 7231079 : int priority = bbd[bb->index].priority;
907 7231079 : if (priority == -1)
908 : {
909 4099729 : priority = 0;
910 9998850 : FOR_EACH_EDGE (e, ei, bb->preds)
911 : {
912 5899121 : if ((e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
913 5328250 : && bbd[e->src->index].end_of_trace >= 0)
914 5899121 : || (e->flags & EDGE_DFS_BACK))
915 : {
916 62377 : int edge_freq = EDGE_FREQUENCY (e);
917 :
918 62377 : if (edge_freq > priority)
919 5899121 : priority = edge_freq;
920 : }
921 : }
922 4099729 : bbd[bb->index].priority = priority;
923 : }
924 :
925 7231079 : if (priority)
926 : /* The block with priority should have significantly lower key. */
927 1602938 : return -(100 * BB_FREQ_MAX + 100 * priority + bb->count.to_frequency (cfun));
928 :
929 5628141 : return -bb->count.to_frequency (cfun);
930 : }
931 :
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. */
938 :
939 : static bool
940 6715920 : 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)
943 : {
944 6715920 : bool is_better_edge;
945 :
946 : /* The BEST_* values do not have to be best, but can be a bit smaller than
947 : maximum values. */
948 6715920 : profile_probability diff_prob = best_prob / 10;
949 :
950 : /* The smaller one is better to keep the original order. */
951 6715920 : if (optimize_function_for_size_p (cfun))
952 406820 : return !cur_best_edge
953 406820 : || cur_best_edge->dest->index > e->dest->index;
954 :
955 : /* Those edges are so expensive that continuing a trace is not useful
956 : performance wise. */
957 6309100 : if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
958 : return false;
959 :
960 12618200 : if (prob > best_prob + diff_prob
961 5968384 : || (!best_prob.initialized_p ()
962 10634454 : && prob > profile_probability::guessed_never ()))
963 : /* The edge has higher probability than the temporary best edge. */
964 : is_better_edge = true;
965 989645 : 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
969 : {
970 319261 : profile_count diff_count = best_count / 10;
971 380520 : if (count < best_count - diff_count
972 319261 : || (!best_count.initialized_p ()
973 1179 : && 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 256823 : else if (count > best_count + diff_count)
980 : /* This successor has higher countuency so it is worse. */
981 : is_better_edge = false;
982 155554 : 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 319261 : is_better_edge = false;
988 : }
989 :
990 : return is_better_edge;
991 : }
992 :
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. */
1001 :
1002 : static bool
1003 1921832 : connect_better_edge_p (const_edge e, bool src_index_p, int best_len,
1004 : const_edge cur_best_edge, struct trace *traces)
1005 : {
1006 1921832 : int e_index;
1007 1921832 : int b_index;
1008 1921832 : bool is_better_edge;
1009 :
1010 1921832 : if (!cur_best_edge)
1011 : return true;
1012 :
1013 486583 : if (optimize_function_for_size_p (cfun))
1014 : {
1015 48788 : e_index = src_index_p ? e->src->index : e->dest->index;
1016 48788 : b_index = src_index_p ? cur_best_edge->src->index
1017 46274 : : cur_best_edge->dest->index;
1018 : /* The smaller one is better to keep the original order. */
1019 48788 : return b_index > e_index;
1020 : }
1021 :
1022 437795 : if (src_index_p)
1023 : {
1024 42099 : e_index = e->src->index;
1025 :
1026 : /* We are looking for predecessor, so probabilities are not that
1027 : informative. We do not want to connect A to B because A has
1028 : only one successor (probability is 100%) while there is edge
1029 : A' to B where probability is 90% but which is much more frequent. */
1030 42099 : if (e->count () > cur_best_edge->count ())
1031 : /* The edge has higher probability than the temporary best edge. */
1032 : is_better_edge = true;
1033 33634 : 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 19127 : else if (e->probability > cur_best_edge->probability)
1037 : /* The edge has higher probability than the temporary best edge. */
1038 : is_better_edge = true;
1039 18301 : 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 16308 : 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;
1048 : }
1049 : else
1050 : {
1051 395696 : e_index = e->dest->index;
1052 :
1053 395696 : if (e->probability > cur_best_edge->probability)
1054 : /* The edge has higher probability than the temporary best edge. */
1055 : is_better_edge = true;
1056 251534 : 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 118830 : 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;
1065 : }
1066 :
1067 : return is_better_edge;
1068 : }
1069 :
1070 : /* Connect traces in array TRACES, N_TRACES is the count of traces. */
1071 :
1072 : static void
1073 607561 : connect_traces (int n_traces, struct trace *traces)
1074 : {
1075 607561 : int i;
1076 607561 : bool *connected;
1077 607561 : bool two_passes;
1078 607561 : int last_trace;
1079 607561 : int current_pass;
1080 607561 : int current_partition;
1081 607561 : profile_count count_threshold;
1082 607561 : bool for_size = optimize_function_for_size_p (cfun);
1083 :
1084 607561 : count_threshold = max_entry_count.apply_scale (DUPLICATION_THRESHOLD, 1000);
1085 :
1086 607561 : connected = XCNEWVEC (bool, n_traces);
1087 607561 : last_trace = -1;
1088 607561 : current_pass = 1;
1089 607561 : current_partition = BB_PARTITION (traces[0].first);
1090 607561 : two_passes = false;
1091 :
1092 607561 : if (crtl->has_bb_partition)
1093 581530 : for (i = 0; i < n_traces && !two_passes; i++)
1094 516168 : if (BB_PARTITION (traces[0].first)
1095 516168 : != BB_PARTITION (traces[i].first))
1096 65362 : two_passes = true;
1097 :
1098 5833980 : for (i = 0; i < n_traces || (two_passes && current_pass == 1) ; i++)
1099 : {
1100 5226419 : int t = i;
1101 5226419 : int t2;
1102 5226419 : edge e, best;
1103 5226419 : int best_len;
1104 :
1105 5226419 : if (i >= n_traces)
1106 : {
1107 65362 : gcc_assert (two_passes && current_pass == 1);
1108 65362 : i = 0;
1109 65362 : t = i;
1110 65362 : current_pass = 2;
1111 65362 : if (current_partition == BB_HOT_PARTITION)
1112 : current_partition = BB_COLD_PARTITION;
1113 : else
1114 0 : current_partition = BB_HOT_PARTITION;
1115 : }
1116 :
1117 5226419 : if (connected[t])
1118 2156567 : continue;
1119 :
1120 3251525 : if (two_passes
1121 664621 : && BB_PARTITION (traces[t].first) != current_partition)
1122 181673 : continue;
1123 :
1124 3069852 : connected[t] = true;
1125 :
1126 : /* Find the predecessor traces. */
1127 3176802 : for (t2 = t; t2 > 0;)
1128 : {
1129 2569241 : edge_iterator ei;
1130 2569241 : best = NULL;
1131 2569241 : best_len = 0;
1132 6466267 : FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
1133 : {
1134 3897026 : int si = e->src->index;
1135 :
1136 3897026 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1137 3897026 : && (e->flags & EDGE_CAN_FALLTHRU)
1138 3106392 : && !(e->flags & EDGE_COMPLEX)
1139 3050419 : && bbd[si].end_of_trace >= 0
1140 539042 : && !connected[bbd[si].end_of_trace]
1141 151580 : && (BB_PARTITION (e->src) == current_partition)
1142 4048589 : && connect_better_edge_p (e, true, best_len, best, traces))
1143 : {
1144 117144 : best = e;
1145 117144 : best_len = traces[bbd[si].end_of_trace].length;
1146 : }
1147 : }
1148 2569241 : if (best)
1149 : {
1150 106950 : best->src->aux = best->dest;
1151 106950 : t2 = bbd[best->src->index].end_of_trace;
1152 106950 : connected[t2] = true;
1153 :
1154 106950 : if (dump_file)
1155 : {
1156 2 : fprintf (dump_file, "Connection: %d %d\n",
1157 : best->src->index, best->dest->index);
1158 : }
1159 : }
1160 : else
1161 : break;
1162 : }
1163 :
1164 3069852 : if (last_trace >= 0)
1165 2462291 : traces[last_trace].last->aux = traces[t2].first;
1166 3069852 : last_trace = t;
1167 :
1168 : /* Find the successor traces. */
1169 5795224 : while (1)
1170 : {
1171 : /* Find the continuation of the chain. */
1172 4432538 : edge_iterator ei;
1173 4432538 : best = NULL;
1174 4432538 : best_len = 0;
1175 9812932 : FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1176 : {
1177 5380394 : int di = e->dest->index;
1178 :
1179 5380394 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1180 4670526 : && (e->flags & EDGE_CAN_FALLTHRU)
1181 4364458 : && !(e->flags & EDGE_COMPLEX)
1182 4296523 : && bbd[di].start_of_trace >= 0
1183 2331395 : && !connected[bbd[di].start_of_trace]
1184 1789238 : && (BB_PARTITION (e->dest) == current_partition)
1185 7150663 : && connect_better_edge_p (e, false, best_len, best, traces))
1186 : {
1187 1542224 : best = e;
1188 1542224 : best_len = traces[bbd[di].start_of_trace].length;
1189 : }
1190 : }
1191 :
1192 4432538 : if (for_size)
1193 : {
1194 279150 : if (!best)
1195 : /* Stop finding the successor traces. */
1196 : break;
1197 :
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 198183 : if (best->dest->index > (traces[t].last->index + 1))
1201 : {
1202 22952 : int count = EDGE_COUNT (best->dest->preds);
1203 :
1204 128327 : FOR_EACH_EDGE (e, ei, best->dest->preds)
1205 105375 : if (e->flags & EDGE_DFS_BACK)
1206 5966 : count--;
1207 :
1208 : /* If dest has multiple predecessors, skip it. We expect
1209 : that one predecessor with smaller index connects with it
1210 : later. */
1211 22952 : if (count != 1)
1212 : break;
1213 : }
1214 :
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 182724 : if (last_trace != bbd[best->dest->index].start_of_trace - 1)
1219 : break;
1220 :
1221 178818 : if (dump_file)
1222 5 : fprintf (dump_file, "Connection: %d %d\n",
1223 5 : best->src->index, best->dest->index);
1224 :
1225 178818 : t = bbd[best->dest->index].start_of_trace;
1226 178818 : traces[last_trace].last->aux = traces[t].first;
1227 178818 : connected[t] = true;
1228 178818 : last_trace = t;
1229 : }
1230 4153388 : else if (best)
1231 : {
1232 1130116 : if (dump_file)
1233 : {
1234 45 : fprintf (dump_file, "Connection: %d %d\n",
1235 45 : best->src->index, best->dest->index);
1236 : }
1237 1130116 : t = bbd[best->dest->index].start_of_trace;
1238 1130116 : traces[last_trace].last->aux = traces[t].first;
1239 1130116 : connected[t] = true;
1240 1130116 : last_trace = t;
1241 : }
1242 : else
1243 : {
1244 : /* Try to connect the traces by duplication of 1 block. */
1245 3023272 : edge e2;
1246 3023272 : basic_block next_bb = NULL;
1247 3023272 : bool try_copy = false;
1248 :
1249 5923689 : FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1250 2900417 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1251 2228711 : && (e->flags & EDGE_CAN_FALLTHRU)
1252 1928353 : && !(e->flags & EDGE_COMPLEX)
1253 6991138 : && (!best || e->probability > best->probability))
1254 : {
1255 1848628 : edge_iterator ei;
1256 1848628 : edge best2 = NULL;
1257 1848628 : int best2_len = 0;
1258 :
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 1848628 : if (bbd[e->dest->index].start_of_trace >= 0
1263 394465 : && traces[bbd[e->dest->index].start_of_trace].length
1264 : == 1)
1265 : {
1266 262680 : best = e;
1267 262680 : try_copy = true;
1268 262680 : continue;
1269 : }
1270 :
1271 4048813 : FOR_EACH_EDGE (e2, ei, e->dest->succs)
1272 : {
1273 2462865 : int di = e2->dest->index;
1274 :
1275 2462865 : if (e2->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
1276 2462865 : || ((e2->flags & EDGE_CAN_FALLTHRU)
1277 2051789 : && !(e2->flags & EDGE_COMPLEX)
1278 2051787 : && bbd[di].start_of_trace >= 0
1279 730385 : && !connected[bbd[di].start_of_trace]
1280 253559 : && BB_PARTITION (e2->dest) == current_partition
1281 2579204 : && e2->count () >= count_threshold
1282 116636 : && (!best2
1283 1322 : || e2->probability > best2->probability
1284 728 : || (e2->probability == best2->probability
1285 61 : && traces[bbd[di].start_of_trace].length
1286 : > best2_len))))
1287 : {
1288 394630 : best = e;
1289 394630 : best2 = e2;
1290 394630 : if (e2->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1291 115934 : 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;
1296 : }
1297 : }
1298 : }
1299 :
1300 : /* Copy tiny blocks always; copy larger blocks only when the
1301 : edge is traversed frequently enough. */
1302 3023272 : if (try_copy
1303 651338 : && BB_PARTITION (best->src) == BB_PARTITION (best->dest)
1304 3672335 : && copy_bb_p (best->dest,
1305 649063 : optimize_edge_for_speed_p (best)
1306 1071305 : && (!best->count ().initialized_p ()
1307 3191000 : || best->count () >= count_threshold)))
1308 : {
1309 254400 : basic_block new_bb;
1310 :
1311 254400 : if (dump_file)
1312 : {
1313 0 : fprintf (dump_file, "Connection: %d %d ",
1314 0 : traces[t].last->index, best->dest->index);
1315 0 : if (!next_bb)
1316 0 : fputc ('\n', dump_file);
1317 0 : else if (next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1318 0 : fprintf (dump_file, "exit\n");
1319 : else
1320 0 : fprintf (dump_file, "%d\n", next_bb->index);
1321 : }
1322 :
1323 254400 : new_bb = copy_bb (best->dest, best, traces[t].last, t);
1324 254400 : traces[t].last = new_bb;
1325 254400 : if (next_bb && next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1326 : {
1327 53752 : t = bbd[next_bb->index].start_of_trace;
1328 53752 : traces[last_trace].last->aux = traces[t].first;
1329 53752 : connected[t] = true;
1330 53752 : last_trace = t;
1331 : }
1332 : else
1333 : break; /* Stop finding the successor traces. */
1334 : }
1335 : else
1336 : break; /* Stop finding the successor traces. */
1337 : }
1338 1362686 : }
1339 : }
1340 :
1341 607561 : if (dump_file)
1342 : {
1343 23 : basic_block bb;
1344 :
1345 23 : fprintf (dump_file, "Final order:\n");
1346 211 : for (bb = traces[0].first; bb; bb = (basic_block) bb->aux)
1347 188 : fprintf (dump_file, "%d ", bb->index);
1348 23 : fprintf (dump_file, "\n");
1349 23 : fflush (dump_file);
1350 : }
1351 :
1352 607561 : FREE (connected);
1353 607561 : }
1354 :
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. */
1357 :
1358 : static bool
1359 3405680 : copy_bb_p (const_basic_block bb, int code_may_grow)
1360 : {
1361 3405680 : unsigned int size = 0;
1362 3405680 : unsigned int max_size = uncond_jump_length;
1363 3405680 : rtx_insn *insn;
1364 :
1365 3405680 : if (EDGE_COUNT (bb->preds) < 2)
1366 : return false;
1367 3402720 : if (!can_duplicate_block_p (bb))
1368 : return false;
1369 :
1370 : /* Avoid duplicating blocks which have many successors (PR/13430). */
1371 3402503 : if (EDGE_COUNT (bb->succs) > 8)
1372 : return false;
1373 :
1374 3402496 : if (code_may_grow && optimize_bb_for_speed_p (bb))
1375 310917 : max_size *= param_max_grow_copy_bb_insns;
1376 :
1377 24758237 : FOR_BB_INSNS (bb, insn)
1378 : {
1379 24424235 : if (INSN_P (insn))
1380 : {
1381 16681071 : size += get_attr_min_length (insn);
1382 16681071 : if (size > max_size)
1383 : break;
1384 : }
1385 : }
1386 :
1387 3402496 : if (size <= max_size)
1388 : return true;
1389 :
1390 3068494 : if (dump_file)
1391 : {
1392 59 : fprintf (dump_file,
1393 : "Block %d can't be copied because its size = %u.\n",
1394 59 : bb->index, size);
1395 : }
1396 :
1397 : return false;
1398 : }
1399 :
1400 : /* Return the length of unconditional jump instruction. */
1401 :
1402 : int
1403 787688 : get_uncond_jump_length (void)
1404 : {
1405 787688 : unsigned int length;
1406 :
1407 787688 : start_sequence ();
1408 787688 : rtx_code_label *label = emit_label (gen_label_rtx ());
1409 787688 : rtx_insn *jump = emit_jump_insn (targetm.gen_jump (label));
1410 787688 : length = get_attr_min_length (jump);
1411 787688 : end_sequence ();
1412 :
1413 787688 : gcc_assert (length < INT_MAX);
1414 787688 : return length;
1415 : }
1416 :
1417 : /* Create a forwarder block to OLD_BB starting with NEW_LABEL and in the
1418 : other partition wrt OLD_BB. */
1419 :
1420 : static basic_block
1421 6660 : create_eh_forwarder_block (rtx_code_label *new_label, basic_block old_bb)
1422 : {
1423 : /* Split OLD_BB, so that EH pads have always only incoming EH edges,
1424 : bb_has_eh_pred bbs are treated specially by DF infrastructure. */
1425 6660 : old_bb = split_block_after_labels (old_bb)->dest;
1426 :
1427 : /* Put the new label and a jump in the new basic block. */
1428 6660 : rtx_insn *label = emit_label (new_label);
1429 6660 : rtx_code_label *old_label = block_label (old_bb);
1430 6660 : rtx_insn *jump = emit_jump_insn (targetm.gen_jump (old_label));
1431 6660 : JUMP_LABEL (jump) = old_label;
1432 :
1433 : /* Create the new basic block and put it in last position. */
1434 6660 : basic_block last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
1435 6660 : basic_block new_bb = create_basic_block (label, jump, last_bb);
1436 6660 : new_bb->aux = last_bb->aux;
1437 6660 : new_bb->count = old_bb->count;
1438 6660 : last_bb->aux = new_bb;
1439 :
1440 6660 : emit_barrier_after_bb (new_bb);
1441 :
1442 6660 : make_single_succ_edge (new_bb, old_bb, 0);
1443 :
1444 : /* Make sure the new basic block is in the other partition. */
1445 6660 : unsigned new_partition = BB_PARTITION (old_bb);
1446 6660 : new_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1447 6660 : BB_SET_PARTITION (new_bb, new_partition);
1448 :
1449 6660 : return new_bb;
1450 : }
1451 :
1452 : /* The common landing pad in block OLD_BB has edges from both partitions.
1453 : Add a new landing pad that will just jump to the old one and split the
1454 : edges so that no EH edge crosses partitions. */
1455 :
1456 : static void
1457 0 : sjlj_fix_up_crossing_landing_pad (basic_block old_bb)
1458 : {
1459 0 : const unsigned lp_len = cfun->eh->lp_array->length ();
1460 0 : edge_iterator ei;
1461 0 : edge e;
1462 :
1463 : /* Generate the new common landing-pad label. */
1464 0 : rtx_code_label *new_label = gen_label_rtx ();
1465 0 : LABEL_PRESERVE_P (new_label) = 1;
1466 :
1467 : /* Create the forwarder block. */
1468 0 : basic_block new_bb = create_eh_forwarder_block (new_label, old_bb);
1469 :
1470 : /* Create the map from old to new lp index and initialize it. */
1471 0 : unsigned *index_map = (unsigned *) alloca (lp_len * sizeof (unsigned));
1472 0 : memset (index_map, 0, lp_len * sizeof (unsigned));
1473 :
1474 : /* Fix up the edges. */
1475 0 : for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
1476 0 : if (e->src != new_bb && BB_PARTITION (e->src) == BB_PARTITION (new_bb))
1477 : {
1478 0 : rtx_insn *insn = BB_END (e->src);
1479 0 : rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1480 :
1481 0 : gcc_assert (note != NULL);
1482 0 : const unsigned old_index = INTVAL (XEXP (note, 0));
1483 :
1484 : /* Generate the new landing-pad structure. */
1485 0 : if (index_map[old_index] == 0)
1486 : {
1487 0 : eh_landing_pad old_lp = (*cfun->eh->lp_array)[old_index];
1488 0 : eh_landing_pad new_lp = gen_eh_landing_pad (old_lp->region);
1489 0 : new_lp->post_landing_pad = old_lp->post_landing_pad;
1490 0 : new_lp->landing_pad = new_label;
1491 0 : index_map[old_index] = new_lp->index;
1492 : }
1493 0 : XEXP (note, 0) = GEN_INT (index_map[old_index]);
1494 :
1495 : /* Adjust the edge to the new destination. */
1496 0 : redirect_edge_succ (e, new_bb);
1497 0 : }
1498 : else
1499 0 : ei_next (&ei);
1500 0 : }
1501 :
1502 : /* The landing pad OLD_LP, in block OLD_BB, has edges from both partitions.
1503 : Add a new landing pad that will just jump to the old one and split the
1504 : edges so that no EH edge crosses partitions. */
1505 :
1506 : static void
1507 6660 : dw2_fix_up_crossing_landing_pad (eh_landing_pad old_lp, basic_block old_bb)
1508 : {
1509 6660 : eh_landing_pad new_lp;
1510 6660 : edge_iterator ei;
1511 6660 : edge e;
1512 :
1513 : /* Generate the new landing-pad structure. */
1514 6660 : new_lp = gen_eh_landing_pad (old_lp->region);
1515 6660 : new_lp->post_landing_pad = old_lp->post_landing_pad;
1516 6660 : new_lp->landing_pad = gen_label_rtx ();
1517 6660 : LABEL_PRESERVE_P (new_lp->landing_pad) = 1;
1518 :
1519 : /* Create the forwarder block. */
1520 6660 : basic_block new_bb = create_eh_forwarder_block (new_lp->landing_pad, old_bb);
1521 :
1522 : /* Fix up the edges. */
1523 52221 : for (ei = ei_start (old_bb->preds); (e = ei_safe_edge (ei)) != NULL; )
1524 45561 : if (e->src != new_bb && BB_PARTITION (e->src) == BB_PARTITION (new_bb))
1525 : {
1526 34205 : rtx_insn *insn = BB_END (e->src);
1527 34205 : rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
1528 :
1529 34205 : gcc_assert (note != NULL);
1530 34205 : gcc_checking_assert (INTVAL (XEXP (note, 0)) == old_lp->index);
1531 34205 : XEXP (note, 0) = GEN_INT (new_lp->index);
1532 :
1533 : /* Adjust the edge to the new destination. */
1534 34205 : redirect_edge_succ (e, new_bb);
1535 34205 : }
1536 : else
1537 11356 : ei_next (&ei);
1538 6660 : }
1539 :
1540 :
1541 : /* Ensure that all hot bbs are included in a hot path through the
1542 : procedure. This is done by calling this function twice, once
1543 : with WALK_UP true (to look for paths from the entry to hot bbs) and
1544 : once with WALK_UP false (to look for paths from hot bbs to the exit).
1545 : Returns the updated value of COLD_BB_COUNT and adds newly-hot bbs
1546 : to BBS_IN_HOT_PARTITION. */
1547 :
1548 : static unsigned int
1549 131528 : sanitize_hot_paths (bool walk_up, unsigned int cold_bb_count,
1550 : vec<basic_block> *bbs_in_hot_partition)
1551 : {
1552 : /* Callers check this. */
1553 131528 : gcc_checking_assert (cold_bb_count);
1554 :
1555 : /* Keep examining hot bbs while we still have some left to check
1556 : and there are remaining cold bbs. */
1557 131528 : vec<basic_block> hot_bbs_to_check = bbs_in_hot_partition->copy ();
1558 131528 : while (! hot_bbs_to_check.is_empty ()
1559 5984787 : && cold_bb_count)
1560 : {
1561 2926514 : basic_block bb = hot_bbs_to_check.pop ();
1562 2926514 : vec<edge, va_gc> *edges = walk_up ? bb->preds : bb->succs;
1563 2926514 : edge e;
1564 2926514 : edge_iterator ei;
1565 2926514 : profile_probability highest_probability
1566 2926514 : = profile_probability::uninitialized ();
1567 2926514 : profile_count highest_count = profile_count::uninitialized ();
1568 2926514 : bool found = false;
1569 :
1570 : /* Walk the preds/succs and check if there is at least one already
1571 : marked hot. Keep track of the most frequent pred/succ so that we
1572 : can mark it hot if we don't find one. */
1573 3455901 : FOR_EACH_EDGE (e, ei, edges)
1574 : {
1575 3408629 : basic_block reach_bb = walk_up ? e->src : e->dest;
1576 :
1577 3408629 : if (e->flags & EDGE_DFS_BACK)
1578 136178 : continue;
1579 :
1580 : /* Do not expect profile insanities when profile was not adjusted. */
1581 3272451 : if (e->probability == profile_probability::never ()
1582 6176616 : || e->count () == profile_count::zero ())
1583 372886 : continue;
1584 :
1585 2899565 : if (BB_PARTITION (reach_bb) != BB_COLD_PARTITION)
1586 : {
1587 : found = true;
1588 : break;
1589 : }
1590 : /* The following loop will look for the hottest edge via
1591 : the edge count, if it is non-zero, then fallback to
1592 : the edge probability. */
1593 20323 : if (!(e->count () > highest_count))
1594 20259 : highest_count = e->count ();
1595 20323 : if (!highest_probability.initialized_p ()
1596 549710 : || e->probability > highest_probability)
1597 20259 : highest_probability = e->probability;
1598 : }
1599 :
1600 : /* If bb is reached by (or reaches, in the case of !WALK_UP) another hot
1601 : block (or unpartitioned, e.g. the entry block) then it is ok. If not,
1602 : then the most frequent pred (or succ) needs to be adjusted. In the
1603 : case where multiple preds/succs have the same frequency (e.g. a
1604 : 50-50 branch), then both will be adjusted. */
1605 2926514 : if (found)
1606 2879242 : continue;
1607 :
1608 92152 : FOR_EACH_EDGE (e, ei, edges)
1609 : {
1610 44880 : if (e->flags & EDGE_DFS_BACK)
1611 39479 : continue;
1612 : /* Do not expect profile insanities when profile was not adjusted. */
1613 24272 : if (e->probability == profile_probability::never ()
1614 30559 : || e->count () == profile_count::zero ())
1615 18871 : continue;
1616 : /* Select the hottest edge using the edge count, if it is non-zero,
1617 : then fallback to the edge probability. */
1618 5401 : if (highest_count.initialized_p ())
1619 : {
1620 5401 : if (!(e->count () >= highest_count))
1621 0 : continue;
1622 : }
1623 0 : else if (!(e->probability >= highest_probability))
1624 0 : continue;
1625 :
1626 5401 : basic_block reach_bb = walk_up ? e->src : e->dest;
1627 :
1628 : /* We have a hot bb with an immediate dominator that is cold.
1629 : The dominator needs to be re-marked hot. */
1630 5401 : BB_SET_PARTITION (reach_bb, BB_HOT_PARTITION);
1631 5401 : if (dump_file)
1632 0 : fprintf (dump_file, "Promoting bb %i to hot partition to sanitize "
1633 : "profile of bb %i in %s walk\n", reach_bb->index,
1634 : bb->index, walk_up ? "backward" : "forward");
1635 5401 : cold_bb_count--;
1636 :
1637 : /* Now we need to examine newly-hot reach_bb to see if it is also
1638 : dominated by a cold bb. */
1639 5401 : bbs_in_hot_partition->safe_push (reach_bb);
1640 5401 : hot_bbs_to_check.safe_push (reach_bb);
1641 : }
1642 : }
1643 131528 : hot_bbs_to_check.release ();
1644 :
1645 131528 : return cold_bb_count;
1646 : }
1647 :
1648 :
1649 : /* Find the basic blocks that are rarely executed and need to be moved to
1650 : a separate section of the .o file (to cut down on paging and improve
1651 : cache locality). Return a vector of all edges that cross. */
1652 :
1653 : static vec<edge>
1654 270447 : find_rarely_executed_basic_blocks_and_crossing_edges (void)
1655 : {
1656 270447 : vec<edge> crossing_edges = vNULL;
1657 270447 : basic_block bb;
1658 270447 : edge e;
1659 270447 : edge_iterator ei;
1660 270447 : unsigned int cold_bb_count = 0;
1661 270447 : auto_vec<basic_block> bbs_in_hot_partition;
1662 :
1663 270447 : propagate_unlikely_bbs_forward ();
1664 :
1665 : /* Mark which partition (hot/cold) each basic block belongs in. */
1666 4943276 : FOR_EACH_BB_FN (bb, cfun)
1667 : {
1668 4672829 : bool cold_bb = false;
1669 :
1670 4672829 : if (probably_never_executed_bb_p (cfun, bb))
1671 : {
1672 285346 : cold_bb = true;
1673 :
1674 : /* Handle profile insanities created by upstream optimizations
1675 : by also checking the incoming edge weights. If there is a non-cold
1676 : incoming edge, conservatively prevent this block from being split
1677 : into the cold section. */
1678 285346 : if (!bb->count.precise_p ())
1679 341 : FOR_EACH_EDGE (e, ei, bb->preds)
1680 195 : if (!probably_never_executed_edge_p (cfun, e))
1681 : {
1682 : cold_bb = false;
1683 : break;
1684 : }
1685 : }
1686 146 : if (cold_bb)
1687 : {
1688 285346 : BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1689 285346 : cold_bb_count++;
1690 : }
1691 : else
1692 : {
1693 4387483 : BB_SET_PARTITION (bb, BB_HOT_PARTITION);
1694 4387483 : bbs_in_hot_partition.safe_push (bb);
1695 : }
1696 : }
1697 :
1698 : /* Ensure that hot bbs are included along a hot path from the entry to exit.
1699 : Several different possibilities may include cold bbs along all paths
1700 : to/from a hot bb. One is that there are edge weight insanities
1701 : due to optimization phases that do not properly update basic block profile
1702 : counts. The second is that the entry of the function may not be hot, because
1703 : it is entered fewer times than the number of profile training runs, but there
1704 : is a loop inside the function that causes blocks within the function to be
1705 : above the threshold for hotness. This is fixed by walking up from hot bbs
1706 : to the entry block, and then down from hot bbs to the exit, performing
1707 : partitioning fixups as necessary. */
1708 270447 : if (cold_bb_count)
1709 : {
1710 65764 : mark_dfs_back_edges ();
1711 65764 : cold_bb_count = sanitize_hot_paths (true, cold_bb_count,
1712 : &bbs_in_hot_partition);
1713 65764 : if (cold_bb_count)
1714 65764 : sanitize_hot_paths (false, cold_bb_count, &bbs_in_hot_partition);
1715 :
1716 65764 : hash_set <basic_block> set;
1717 65764 : find_bbs_reachable_by_hot_paths (&set);
1718 1814683 : FOR_EACH_BB_FN (bb, cfun)
1719 1748919 : if (!set.contains (bb))
1720 279945 : BB_SET_PARTITION (bb, BB_COLD_PARTITION);
1721 65764 : }
1722 :
1723 : /* The format of .gcc_except_table does not allow landing pads to
1724 : be in a different partition as the throw. Fix this by either
1725 : moving the landing pads or inserting forwarder landing pads. */
1726 270447 : if (cfun->eh->lp_array)
1727 : {
1728 270447 : const bool sjlj
1729 270447 : = (targetm_common.except_unwind_info (&global_options) == UI_SJLJ);
1730 270447 : unsigned i;
1731 270447 : eh_landing_pad lp;
1732 :
1733 1143450 : FOR_EACH_VEC_ELT (*cfun->eh->lp_array, i, lp)
1734 : {
1735 602556 : bool all_same, all_diff;
1736 :
1737 602556 : if (lp == NULL
1738 82681 : || lp->landing_pad == NULL_RTX
1739 82681 : || !LABEL_P (lp->landing_pad))
1740 519934 : continue;
1741 :
1742 82622 : all_same = all_diff = true;
1743 82622 : bb = BLOCK_FOR_INSN (lp->landing_pad);
1744 277799 : FOR_EACH_EDGE (e, ei, bb->preds)
1745 : {
1746 195177 : gcc_assert (e->flags & EDGE_EH);
1747 195177 : if (BB_PARTITION (bb) == BB_PARTITION (e->src))
1748 : all_diff = false;
1749 : else
1750 134153 : all_same = false;
1751 : }
1752 :
1753 82622 : if (all_same)
1754 : ;
1755 63230 : else if (all_diff)
1756 : {
1757 56570 : int which = BB_PARTITION (bb);
1758 56570 : which ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
1759 56570 : BB_SET_PARTITION (bb, which);
1760 : }
1761 6660 : else if (sjlj)
1762 0 : sjlj_fix_up_crossing_landing_pad (bb);
1763 : else
1764 6660 : dw2_fix_up_crossing_landing_pad (lp, bb);
1765 :
1766 : /* There is a single, common landing pad in SJLJ mode. */
1767 82622 : if (sjlj)
1768 : break;
1769 : }
1770 : }
1771 :
1772 : /* Mark every edge that crosses between sections. */
1773 4956596 : FOR_EACH_BB_FN (bb, cfun)
1774 11819867 : FOR_EACH_EDGE (e, ei, bb->succs)
1775 : {
1776 7133718 : unsigned int flags = e->flags;
1777 :
1778 : /* We should never have EDGE_CROSSING set yet. */
1779 7133718 : gcc_checking_assert ((flags & EDGE_CROSSING) == 0);
1780 :
1781 7133718 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1782 7133718 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1783 6827926 : && BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1784 : {
1785 437434 : crossing_edges.safe_push (e);
1786 437434 : flags |= EDGE_CROSSING;
1787 : }
1788 :
1789 : /* Now that we've split eh edges as appropriate, allow landing pads
1790 : to be merged with the post-landing pads. */
1791 7133718 : flags &= ~EDGE_PRESERVE;
1792 :
1793 7133718 : e->flags = flags;
1794 : }
1795 :
1796 270447 : return crossing_edges;
1797 270447 : }
1798 :
1799 : /* Set the flag EDGE_CAN_FALLTHRU for edges that can be fallthru. */
1800 :
1801 : static void
1802 643480 : set_edge_can_fallthru_flag (void)
1803 : {
1804 643480 : basic_block bb;
1805 :
1806 11169574 : FOR_EACH_BB_FN (bb, cfun)
1807 : {
1808 10526094 : edge e;
1809 10526094 : edge_iterator ei;
1810 :
1811 26303329 : FOR_EACH_EDGE (e, ei, bb->succs)
1812 : {
1813 15777235 : e->flags &= ~EDGE_CAN_FALLTHRU;
1814 :
1815 : /* The FALLTHRU edge is also CAN_FALLTHRU edge. */
1816 15777235 : if (e->flags & EDGE_FALLTHRU)
1817 9098711 : e->flags |= EDGE_CAN_FALLTHRU;
1818 : }
1819 :
1820 : /* If the BB ends with an invertible condjump all (2) edges are
1821 : CAN_FALLTHRU edges. */
1822 10526094 : if (EDGE_COUNT (bb->succs) != 2)
1823 5425806 : continue;
1824 5683406 : if (!any_condjump_p (BB_END (bb)))
1825 583118 : continue;
1826 :
1827 5100288 : rtx_jump_insn *bb_end_jump = as_a <rtx_jump_insn *> (BB_END (bb));
1828 5100288 : if (!invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0))
1829 0 : continue;
1830 5100288 : invert_jump (bb_end_jump, JUMP_LABEL (bb_end_jump), 0);
1831 5100288 : EDGE_SUCC (bb, 0)->flags |= EDGE_CAN_FALLTHRU;
1832 5100288 : EDGE_SUCC (bb, 1)->flags |= EDGE_CAN_FALLTHRU;
1833 : }
1834 643480 : }
1835 :
1836 : /* If any destination of a crossing edge does not have a label, add label;
1837 : Convert any easy fall-through crossing edges to unconditional jumps. */
1838 :
1839 : static void
1840 65368 : add_labels_and_missing_jumps (vec<edge> crossing_edges)
1841 : {
1842 65368 : size_t i;
1843 65368 : edge e;
1844 :
1845 502802 : FOR_EACH_VEC_ELT (crossing_edges, i, e)
1846 : {
1847 437434 : basic_block src = e->src;
1848 437434 : basic_block dest = e->dest;
1849 437434 : rtx_jump_insn *new_jump;
1850 :
1851 437434 : if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1852 0 : continue;
1853 :
1854 : /* Make sure dest has a label. */
1855 437434 : rtx_code_label *label = block_label (dest);
1856 :
1857 : /* Nothing to do for non-fallthru edges. */
1858 437434 : if (src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1859 0 : continue;
1860 437434 : if ((e->flags & EDGE_FALLTHRU) == 0)
1861 257838 : continue;
1862 :
1863 : /* If the block does not end with a control flow insn, then we
1864 : can trivially add a jump to the end to fixup the crossing.
1865 : Otherwise the jump will have to go in a new bb, which will
1866 : be handled by fix_up_fall_thru_edges function. */
1867 179596 : if (control_flow_insn_p (BB_END (src)))
1868 117416 : continue;
1869 :
1870 : /* Make sure there's only one successor. */
1871 62180 : gcc_assert (single_succ_p (src));
1872 :
1873 62180 : new_jump = emit_jump_insn_after (targetm.gen_jump (label), BB_END (src));
1874 62180 : BB_END (src) = new_jump;
1875 62180 : JUMP_LABEL (new_jump) = label;
1876 62180 : LABEL_NUSES (label) += 1;
1877 :
1878 62180 : emit_barrier_after_bb (src);
1879 :
1880 : /* Mark edge as non-fallthru. */
1881 62180 : e->flags &= ~EDGE_FALLTHRU;
1882 : }
1883 65368 : }
1884 :
1885 : /* Find any bb's where the fall-through edge is a crossing edge (note that
1886 : these bb's must also contain a conditional jump or end with a call
1887 : instruction; we've already dealt with fall-through edges for blocks
1888 : that didn't have a conditional jump or didn't end with call instruction
1889 : in the call to add_labels_and_missing_jumps). Convert the fall-through
1890 : edge to non-crossing edge by inserting a new bb to fall-through into.
1891 : The new bb will contain an unconditional jump (crossing edge) to the
1892 : original fall through destination. */
1893 :
1894 : static void
1895 65368 : fix_up_fall_thru_edges (void)
1896 : {
1897 65368 : basic_block cur_bb;
1898 :
1899 1821063 : FOR_EACH_BB_FN (cur_bb, cfun)
1900 : {
1901 1755695 : edge succ1;
1902 1755695 : edge succ2;
1903 1755695 : edge fall_thru = NULL;
1904 1755695 : edge cond_jump = NULL;
1905 :
1906 1755695 : fall_thru = NULL;
1907 1755695 : if (EDGE_COUNT (cur_bb->succs) > 0)
1908 1649182 : succ1 = EDGE_SUCC (cur_bb, 0);
1909 : else
1910 : succ1 = NULL;
1911 :
1912 1755695 : if (EDGE_COUNT (cur_bb->succs) > 1)
1913 1042466 : succ2 = EDGE_SUCC (cur_bb, 1);
1914 : else
1915 : succ2 = NULL;
1916 :
1917 : /* Find the fall-through edge. */
1918 :
1919 1755695 : if (succ1
1920 1649182 : && (succ1->flags & EDGE_FALLTHRU))
1921 : {
1922 : fall_thru = succ1;
1923 : cond_jump = succ2;
1924 : }
1925 867888 : else if (succ2
1926 667805 : && (succ2->flags & EDGE_FALLTHRU))
1927 : {
1928 : fall_thru = succ2;
1929 : cond_jump = succ1;
1930 : }
1931 1756600 : else if (succ2 && EDGE_COUNT (cur_bb->succs) > 2)
1932 905 : fall_thru = find_fallthru_edge (cur_bb->succs);
1933 :
1934 1555570 : if (fall_thru && (fall_thru->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)))
1935 : {
1936 : /* Check to see if the fall-thru edge is a crossing edge. */
1937 :
1938 1494103 : if (fall_thru->flags & EDGE_CROSSING)
1939 : {
1940 : /* The fall_thru edge crosses; now check the cond jump edge, if
1941 : it exists. */
1942 :
1943 117416 : bool cond_jump_crosses = true;
1944 117416 : int invert_worked = 0;
1945 117416 : rtx_insn *old_jump = BB_END (cur_bb);
1946 :
1947 : /* Find the jump instruction, if there is one. */
1948 :
1949 117416 : if (cond_jump)
1950 : {
1951 117326 : if (!(cond_jump->flags & EDGE_CROSSING))
1952 116720 : cond_jump_crosses = false;
1953 :
1954 : /* We know the fall-thru edge crosses; if the cond
1955 : jump edge does NOT cross, and its destination is the
1956 : next block in the bb order, invert the jump
1957 : (i.e. fix it so the fall through does not cross and
1958 : the cond jump does). */
1959 :
1960 116720 : if (!cond_jump_crosses)
1961 : {
1962 : /* Find label in fall_thru block. We've already added
1963 : any missing labels, so there must be one. */
1964 :
1965 116720 : rtx_code_label *fall_thru_label
1966 116720 : = block_label (fall_thru->dest);
1967 :
1968 116720 : if (old_jump && fall_thru_label)
1969 : {
1970 116720 : rtx_jump_insn *old_jump_insn
1971 231731 : = dyn_cast <rtx_jump_insn *> (old_jump);
1972 114315 : if (old_jump_insn)
1973 114315 : invert_worked = invert_jump (old_jump_insn,
1974 : fall_thru_label, 0);
1975 : }
1976 :
1977 114315 : if (invert_worked)
1978 : {
1979 114305 : fall_thru->flags &= ~EDGE_FALLTHRU;
1980 114305 : cond_jump->flags |= EDGE_FALLTHRU;
1981 114305 : update_br_prob_note (cur_bb);
1982 114305 : std::swap (fall_thru, cond_jump);
1983 114305 : cond_jump->flags |= EDGE_CROSSING;
1984 114305 : fall_thru->flags &= ~EDGE_CROSSING;
1985 : }
1986 : }
1987 : }
1988 :
1989 117416 : if (cond_jump_crosses || !invert_worked)
1990 : {
1991 : /* This is the case where both edges out of the basic
1992 : block are crossing edges. Here we will fix up the
1993 : fall through edge. The jump edge will be taken care
1994 : of later. The EDGE_CROSSING flag of fall_thru edge
1995 : is unset before the call to force_nonfallthru
1996 : function because if a new basic-block is created
1997 : this edge remains in the current section boundary
1998 : while the edge between new_bb and the fall_thru->dest
1999 : becomes EDGE_CROSSING. */
2000 :
2001 3111 : fall_thru->flags &= ~EDGE_CROSSING;
2002 3111 : unsigned old_count = EDGE_COUNT (cur_bb->succs);
2003 3111 : basic_block new_bb = force_nonfallthru (fall_thru);
2004 :
2005 3111 : if (new_bb)
2006 : {
2007 3111 : new_bb->aux = cur_bb->aux;
2008 3111 : cur_bb->aux = new_bb;
2009 :
2010 : /* This is done by force_nonfallthru_and_redirect. */
2011 3111 : gcc_assert (BB_PARTITION (new_bb)
2012 : == BB_PARTITION (cur_bb));
2013 :
2014 3111 : edge e = single_succ_edge (new_bb);
2015 3111 : e->flags |= EDGE_CROSSING;
2016 3111 : if (EDGE_COUNT (cur_bb->succs) > old_count)
2017 : {
2018 : /* If asm goto has a crossing fallthrough edge
2019 : and at least one of the labels to the same bb,
2020 : force_nonfallthru can result in the fallthrough
2021 : edge being redirected and a new edge added for the
2022 : label or more labels to e->dest. As we've
2023 : temporarily cleared EDGE_CROSSING flag on the
2024 : fallthrough edge, we need to restore it again.
2025 : See PR108596. */
2026 0 : rtx_insn *j = BB_END (cur_bb);
2027 0 : gcc_checking_assert (JUMP_P (j)
2028 : && (asm_noperands (PATTERN (j))
2029 : > 0));
2030 0 : edge e2 = find_edge (cur_bb, e->dest);
2031 0 : if (e2)
2032 0 : e2->flags |= EDGE_CROSSING;
2033 : }
2034 : }
2035 : else
2036 : {
2037 : /* If a new basic-block was not created; restore
2038 : the EDGE_CROSSING flag. */
2039 0 : fall_thru->flags |= EDGE_CROSSING;
2040 : }
2041 :
2042 : /* Add barrier after new jump */
2043 3111 : emit_barrier_after_bb (new_bb ? new_bb : cur_bb);
2044 : }
2045 : }
2046 : }
2047 : }
2048 65368 : }
2049 :
2050 : /* This function checks the destination block of a "crossing jump" to
2051 : see if it has any crossing predecessors that begin with a code label
2052 : and end with an unconditional jump. If so, it returns that predecessor
2053 : block. (This is to avoid creating lots of new basic blocks that all
2054 : contain unconditional jumps to the same destination). */
2055 :
2056 : static basic_block
2057 0 : find_jump_block (basic_block jump_dest)
2058 : {
2059 0 : basic_block source_bb = NULL;
2060 0 : edge e;
2061 0 : rtx_insn *insn;
2062 0 : edge_iterator ei;
2063 :
2064 0 : FOR_EACH_EDGE (e, ei, jump_dest->preds)
2065 0 : if (e->flags & EDGE_CROSSING)
2066 : {
2067 0 : basic_block src = e->src;
2068 :
2069 : /* Check each predecessor to see if it has a label, and contains
2070 : only one executable instruction, which is an unconditional jump.
2071 : If so, we can use it. */
2072 :
2073 0 : if (LABEL_P (BB_HEAD (src)))
2074 0 : for (insn = BB_HEAD (src);
2075 0 : !INSN_P (insn) && insn != NEXT_INSN (BB_END (src));
2076 0 : insn = NEXT_INSN (insn))
2077 : {
2078 0 : if (INSN_P (insn)
2079 : && insn == BB_END (src)
2080 : && JUMP_P (insn)
2081 : && !any_condjump_p (insn))
2082 : {
2083 : source_bb = src;
2084 : break;
2085 : }
2086 : }
2087 :
2088 : if (source_bb)
2089 : break;
2090 : }
2091 :
2092 0 : return source_bb;
2093 : }
2094 :
2095 : /* Find all BB's with conditional jumps that are crossing edges;
2096 : insert a new bb and make the conditional jump branch to the new
2097 : bb instead (make the new bb same color so conditional branch won't
2098 : be a 'crossing' edge). Insert an unconditional jump from the
2099 : new bb to the original destination of the conditional jump. */
2100 :
2101 : static void
2102 0 : fix_crossing_conditional_branches (void)
2103 : {
2104 0 : basic_block cur_bb;
2105 0 : basic_block new_bb;
2106 0 : basic_block dest;
2107 0 : edge succ1;
2108 0 : edge succ2;
2109 0 : edge crossing_edge;
2110 0 : edge new_edge;
2111 0 : rtx set_src;
2112 0 : rtx old_label = NULL_RTX;
2113 0 : rtx_code_label *new_label;
2114 :
2115 0 : FOR_EACH_BB_FN (cur_bb, cfun)
2116 : {
2117 0 : crossing_edge = NULL;
2118 0 : if (EDGE_COUNT (cur_bb->succs) > 0)
2119 0 : succ1 = EDGE_SUCC (cur_bb, 0);
2120 : else
2121 : succ1 = NULL;
2122 :
2123 0 : if (EDGE_COUNT (cur_bb->succs) > 1)
2124 0 : succ2 = EDGE_SUCC (cur_bb, 1);
2125 : else
2126 : succ2 = NULL;
2127 :
2128 : /* We already took care of fall-through edges, so only one successor
2129 : can be a crossing edge. */
2130 :
2131 0 : if (succ1 && (succ1->flags & EDGE_CROSSING))
2132 : crossing_edge = succ1;
2133 0 : else if (succ2 && (succ2->flags & EDGE_CROSSING))
2134 : crossing_edge = succ2;
2135 :
2136 : if (crossing_edge)
2137 : {
2138 0 : rtx_insn *old_jump = BB_END (cur_bb);
2139 :
2140 : /* Check to make sure the jump instruction is a
2141 : conditional jump. */
2142 :
2143 0 : set_src = NULL_RTX;
2144 :
2145 0 : if (any_condjump_p (old_jump))
2146 : {
2147 0 : if (GET_CODE (PATTERN (old_jump)) == SET)
2148 0 : set_src = SET_SRC (PATTERN (old_jump));
2149 0 : else if (GET_CODE (PATTERN (old_jump)) == PARALLEL)
2150 : {
2151 0 : set_src = XVECEXP (PATTERN (old_jump), 0,0);
2152 0 : if (GET_CODE (set_src) == SET)
2153 0 : set_src = SET_SRC (set_src);
2154 : else
2155 : set_src = NULL_RTX;
2156 : }
2157 : }
2158 :
2159 0 : if (set_src && (GET_CODE (set_src) == IF_THEN_ELSE))
2160 : {
2161 0 : rtx_jump_insn *old_jump_insn =
2162 0 : as_a <rtx_jump_insn *> (old_jump);
2163 :
2164 0 : if (GET_CODE (XEXP (set_src, 1)) == PC)
2165 0 : old_label = XEXP (set_src, 2);
2166 0 : else if (GET_CODE (XEXP (set_src, 2)) == PC)
2167 0 : old_label = XEXP (set_src, 1);
2168 :
2169 : /* Check to see if new bb for jumping to that dest has
2170 : already been created; if so, use it; if not, create
2171 : a new one. */
2172 :
2173 0 : new_bb = find_jump_block (crossing_edge->dest);
2174 :
2175 0 : if (new_bb)
2176 : new_label = block_label (new_bb);
2177 : else
2178 : {
2179 0 : basic_block last_bb;
2180 0 : rtx_code_label *old_jump_target;
2181 0 : rtx_jump_insn *new_jump;
2182 :
2183 : /* Create new basic block to be dest for
2184 : conditional jump. */
2185 :
2186 : /* Put appropriate instructions in new bb. */
2187 :
2188 0 : new_label = gen_label_rtx ();
2189 0 : emit_label (new_label);
2190 :
2191 0 : gcc_assert (GET_CODE (old_label) == LABEL_REF);
2192 0 : old_jump_target = old_jump_insn->jump_target ();
2193 0 : new_jump = as_a <rtx_jump_insn *>
2194 0 : (emit_jump_insn (targetm.gen_jump (old_jump_target)));
2195 0 : new_jump->set_jump_target (old_jump_target);
2196 :
2197 0 : last_bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
2198 0 : new_bb = create_basic_block (new_label, new_jump, last_bb);
2199 0 : new_bb->aux = last_bb->aux;
2200 0 : last_bb->aux = new_bb;
2201 :
2202 0 : emit_barrier_after_bb (new_bb);
2203 :
2204 : /* Make sure new bb is in same partition as source
2205 : of conditional branch. */
2206 0 : BB_COPY_PARTITION (new_bb, cur_bb);
2207 : }
2208 :
2209 : /* Make old jump branch to new bb. */
2210 :
2211 0 : redirect_jump (old_jump_insn, new_label, 0);
2212 :
2213 : /* Remove crossing_edge as predecessor of 'dest'. */
2214 :
2215 0 : dest = crossing_edge->dest;
2216 :
2217 0 : redirect_edge_succ (crossing_edge, new_bb);
2218 :
2219 : /* Make a new edge from new_bb to old dest; new edge
2220 : will be a successor for new_bb and a predecessor
2221 : for 'dest'. */
2222 :
2223 0 : if (EDGE_COUNT (new_bb->succs) == 0)
2224 0 : new_edge = make_single_succ_edge (new_bb, dest, 0);
2225 : else
2226 0 : new_edge = EDGE_SUCC (new_bb, 0);
2227 :
2228 0 : crossing_edge->flags &= ~EDGE_CROSSING;
2229 0 : new_edge->flags |= EDGE_CROSSING;
2230 : }
2231 : }
2232 : }
2233 0 : }
2234 :
2235 : /* Find any unconditional branches that cross between hot and cold
2236 : sections. Convert them into indirect jumps instead. */
2237 :
2238 : static void
2239 0 : fix_crossing_unconditional_branches (void)
2240 : {
2241 0 : basic_block cur_bb;
2242 0 : rtx_insn *last_insn;
2243 0 : rtx label;
2244 0 : rtx label_addr;
2245 0 : rtx_insn *indirect_jump_sequence;
2246 0 : rtx_insn *jump_insn = NULL;
2247 0 : rtx new_reg;
2248 0 : rtx_insn *cur_insn;
2249 0 : edge succ;
2250 :
2251 0 : FOR_EACH_BB_FN (cur_bb, cfun)
2252 : {
2253 0 : last_insn = BB_END (cur_bb);
2254 :
2255 0 : if (EDGE_COUNT (cur_bb->succs) < 1)
2256 0 : continue;
2257 :
2258 0 : succ = EDGE_SUCC (cur_bb, 0);
2259 :
2260 : /* Check to see if bb ends in a crossing (unconditional) jump. At
2261 : this point, no crossing jumps should be conditional. */
2262 :
2263 0 : if (JUMP_P (last_insn)
2264 0 : && (succ->flags & EDGE_CROSSING))
2265 : {
2266 0 : gcc_assert (!any_condjump_p (last_insn));
2267 :
2268 : /* Make sure the jump is not already an indirect or table jump. */
2269 :
2270 0 : if (!computed_jump_p (last_insn)
2271 0 : && !tablejump_p (last_insn, NULL, NULL)
2272 0 : && asm_noperands (PATTERN (last_insn)) < 0)
2273 : {
2274 : /* We have found a "crossing" unconditional branch. Now
2275 : we must convert it to an indirect jump. First create
2276 : reference of label, as target for jump. */
2277 :
2278 0 : label = JUMP_LABEL (last_insn);
2279 0 : label_addr = gen_rtx_LABEL_REF (Pmode, label);
2280 0 : LABEL_NUSES (label) += 1;
2281 :
2282 : /* Get a register to use for the indirect jump. */
2283 :
2284 0 : new_reg = gen_reg_rtx (Pmode);
2285 :
2286 : /* Generate indirect the jump sequence. */
2287 :
2288 0 : start_sequence ();
2289 0 : emit_move_insn (new_reg, label_addr);
2290 0 : emit_indirect_jump (new_reg);
2291 0 : indirect_jump_sequence = end_sequence ();
2292 :
2293 : /* Make sure every instruction in the new jump sequence has
2294 : its basic block set to be cur_bb. */
2295 :
2296 0 : for (cur_insn = indirect_jump_sequence; cur_insn;
2297 0 : cur_insn = NEXT_INSN (cur_insn))
2298 : {
2299 0 : if (!BARRIER_P (cur_insn))
2300 0 : BLOCK_FOR_INSN (cur_insn) = cur_bb;
2301 0 : if (JUMP_P (cur_insn))
2302 0 : jump_insn = cur_insn;
2303 : }
2304 :
2305 : /* Insert the new (indirect) jump sequence immediately before
2306 : the unconditional jump, then delete the unconditional jump. */
2307 :
2308 0 : emit_insn_before (indirect_jump_sequence, last_insn);
2309 0 : delete_insn (last_insn);
2310 :
2311 0 : JUMP_LABEL (jump_insn) = label;
2312 0 : LABEL_NUSES (label)++;
2313 :
2314 : /* Make BB_END for cur_bb be the jump instruction (NOT the
2315 : barrier instruction at the end of the sequence...). */
2316 :
2317 0 : BB_END (cur_bb) = jump_insn;
2318 : }
2319 : }
2320 : }
2321 0 : }
2322 :
2323 : /* Update CROSSING_JUMP_P flags on all jump insns. */
2324 :
2325 : static void
2326 65368 : update_crossing_jump_flags (void)
2327 : {
2328 65368 : basic_block bb;
2329 65368 : edge e;
2330 65368 : edge_iterator ei;
2331 :
2332 1821063 : FOR_EACH_BB_FN (bb, cfun)
2333 3735548 : FOR_EACH_EDGE (e, ei, bb->succs)
2334 2417102 : if (e->flags & EDGE_CROSSING)
2335 : {
2336 437249 : if (JUMP_P (BB_END (bb)))
2337 437152 : set_crossing_jump (BB_END (bb), true);
2338 : break;
2339 : }
2340 65368 : }
2341 :
2342 : /* Reorder basic blocks using the software trace cache (STC) algorithm. */
2343 :
2344 : static void
2345 607561 : reorder_basic_blocks_software_trace_cache (void)
2346 : {
2347 607561 : if (dump_file)
2348 23 : fprintf (dump_file, "\nReordering with the STC algorithm.\n\n");
2349 :
2350 607561 : int n_traces;
2351 607561 : int i;
2352 607561 : struct trace *traces;
2353 :
2354 : /* We are estimating the length of uncond jump insn only once since the code
2355 : for getting the insn length always returns the minimal length now. */
2356 607561 : if (uncond_jump_length == 0)
2357 9506 : uncond_jump_length = get_uncond_jump_length ();
2358 :
2359 : /* We need to know some information for each basic block. */
2360 607561 : array_size = GET_ARRAY_SIZE (last_basic_block_for_fn (cfun));
2361 607561 : bbd = XNEWVEC (bbro_basic_block_data, array_size);
2362 17352041 : for (i = 0; i < array_size; i++)
2363 : {
2364 16744480 : bbd[i].start_of_trace = -1;
2365 16744480 : bbd[i].end_of_trace = -1;
2366 16744480 : bbd[i].in_trace = -1;
2367 16744480 : bbd[i].visited = 0;
2368 16744480 : bbd[i].priority = -1;
2369 16744480 : bbd[i].heap = NULL;
2370 16744480 : bbd[i].node = NULL;
2371 : }
2372 :
2373 607561 : traces = XNEWVEC (struct trace, n_basic_blocks_for_fn (cfun));
2374 607561 : n_traces = 0;
2375 607561 : find_traces (&n_traces, traces);
2376 607561 : connect_traces (n_traces, traces);
2377 607561 : FREE (traces);
2378 607561 : FREE (bbd);
2379 607561 : }
2380 :
2381 : /* Order edges by execution frequency, higher first.
2382 : Return:
2383 : 1 iff frequency (VE1) < frequency (VE2)
2384 : 0 iff frequency (VE1) == frequency (VE2)
2385 : -1 iff frequency (VE1) > frequency (VE2) */
2386 :
2387 : static int
2388 21174815 : edge_order (const void *ve1, const void *ve2)
2389 : {
2390 21174815 : edge e1 = *(const edge *) ve1;
2391 21174815 : edge e2 = *(const edge *) ve2;
2392 21174815 : profile_count c1 = e1->count ();
2393 21174815 : profile_count c2 = e2->count ();
2394 : /* Since profile_count::operator< does not establish a strict weak order
2395 : in presence of uninitialized counts, use 'max': this makes them appear
2396 : as if having execution frequency less than any initialized count. */
2397 21174815 : gcov_type gc1 = c1.initialized_p () ? c1.to_gcov_type () : 0;
2398 21174815 : gcov_type gc2 = c2.initialized_p () ? c2.to_gcov_type () : 0;
2399 21174815 : gcov_type m = MAX (gc1, gc2);
2400 21174815 : int low_to_high_cmp = (m == gc1) - (m == gc2);
2401 : /* gcc_stablesort sorts values in low-to-high order. But edges should
2402 : be sorted in the opposite order - with highest execution frequency first.
2403 : So return an inverted comparison to trick gcc_stablesort into
2404 : performing a reversed sorting order. */
2405 21174815 : return -1 * low_to_high_cmp;
2406 : }
2407 :
2408 : /* Reorder basic blocks using the "simple" algorithm. This tries to
2409 : maximize the dynamic number of branches that are fallthrough, without
2410 : copying instructions. The algorithm is greedy, looking at the most
2411 : frequently executed branch first. */
2412 :
2413 : static void
2414 35919 : reorder_basic_blocks_simple (void)
2415 : {
2416 35919 : if (dump_file)
2417 8 : fprintf (dump_file, "\nReordering with the \"simple\" algorithm.\n\n");
2418 :
2419 35919 : edge *edges = new edge[2 * n_basic_blocks_for_fn (cfun)];
2420 :
2421 : /* First, collect all edges that can be optimized by reordering blocks:
2422 : simple jumps and conditional jumps, as well as the function entry edge. */
2423 :
2424 35919 : int n = 0;
2425 35919 : edges[n++] = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0);
2426 :
2427 35919 : basic_block bb;
2428 579220 : FOR_EACH_BB_FN (bb, cfun)
2429 : {
2430 543301 : rtx_insn *end = BB_END (bb);
2431 :
2432 543301 : if (computed_jump_p (end) || tablejump_p (end, NULL, NULL))
2433 417 : continue;
2434 :
2435 : /* We cannot optimize asm goto. */
2436 542884 : if (JUMP_P (end) && extract_asm_operands (end))
2437 0 : continue;
2438 :
2439 542884 : if (single_succ_p (bb))
2440 165453 : edges[n++] = EDGE_SUCC (bb, 0);
2441 377431 : else if (any_condjump_p (end))
2442 : {
2443 276542 : edge e0 = EDGE_SUCC (bb, 0);
2444 276542 : edge e1 = EDGE_SUCC (bb, 1);
2445 : /* When optimizing for size it is best to keep the original
2446 : fallthrough edges. */
2447 276542 : if (e1->flags & EDGE_FALLTHRU)
2448 149557 : std::swap (e0, e1);
2449 276542 : edges[n++] = e0;
2450 276542 : edges[n++] = e1;
2451 : }
2452 : }
2453 :
2454 : /* Sort the edges, the most desirable first. When optimizing for size
2455 : all edges are equally desirable. */
2456 :
2457 35919 : if (optimize_function_for_speed_p (cfun))
2458 35754 : gcc_stablesort (edges, n, sizeof *edges, edge_order);
2459 :
2460 : /* Now decide which of those edges to make fallthrough edges. We set
2461 : BB_VISITED if a block already has a fallthrough successor assigned
2462 : to it. We make ->AUX of an endpoint point to the opposite endpoint
2463 : of a sequence of blocks that fall through, and ->AUX will be NULL
2464 : for a block that is in such a sequence but not an endpoint anymore.
2465 :
2466 : To start with, everything points to itself, nothing is assigned yet. */
2467 :
2468 651058 : FOR_ALL_BB_FN (bb, cfun)
2469 : {
2470 615139 : bb->aux = bb;
2471 615139 : bb->flags &= ~BB_VISITED;
2472 : }
2473 :
2474 35919 : EXIT_BLOCK_PTR_FOR_FN (cfun)->aux = 0;
2475 :
2476 : /* Now for all edges, the most desirable first, see if that edge can
2477 : connect two sequences. If it can, update AUX and BB_VISITED; if it
2478 : cannot, zero out the edge in the table. */
2479 :
2480 790375 : for (int j = 0; j < n; j++)
2481 : {
2482 754456 : edge e = edges[j];
2483 :
2484 754456 : basic_block tail_a = e->src;
2485 754456 : basic_block head_b = e->dest;
2486 754456 : basic_block head_a = (basic_block) tail_a->aux;
2487 754456 : basic_block tail_b = (basic_block) head_b->aux;
2488 :
2489 : /* An edge cannot connect two sequences if:
2490 : - it crosses partitions;
2491 : - its src is not a current endpoint;
2492 : - its dest is not a current endpoint;
2493 : - or, it would create a loop. */
2494 :
2495 754456 : if (e->flags & EDGE_CROSSING
2496 754446 : || tail_a->flags & BB_VISITED
2497 518934 : || !tail_b
2498 440091 : || (!(head_b->flags & BB_VISITED) && head_b != tail_b)
2499 413334 : || tail_a == tail_b)
2500 : {
2501 380868 : edges[j] = 0;
2502 380868 : continue;
2503 : }
2504 :
2505 373588 : tail_a->aux = 0;
2506 373588 : head_b->aux = 0;
2507 373588 : head_a->aux = tail_b;
2508 373588 : tail_b->aux = head_a;
2509 373588 : tail_a->flags |= BB_VISITED;
2510 : }
2511 :
2512 : /* Put the pieces together, in the same order that the start blocks of
2513 : the sequences already had. The hot/cold partitioning gives a little
2514 : complication: as a first pass only do this for blocks in the same
2515 : partition as the start block, and (if there is anything left to do)
2516 : in a second pass handle the other partition. */
2517 :
2518 35919 : basic_block last_tail = (basic_block) ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux;
2519 :
2520 35919 : int current_partition
2521 35919 : = BB_PARTITION (last_tail == ENTRY_BLOCK_PTR_FOR_FN (cfun)
2522 : ? EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0)->dest
2523 : : last_tail);
2524 35919 : bool need_another_pass = true;
2525 :
2526 71844 : for (int pass = 0; pass < 2 && need_another_pass; pass++)
2527 : {
2528 35925 : need_another_pass = false;
2529 :
2530 579269 : FOR_EACH_BB_FN (bb, cfun)
2531 543344 : if ((bb->flags & BB_VISITED && bb->aux) || bb->aux == bb)
2532 : {
2533 169727 : if (BB_PARTITION (bb) != current_partition)
2534 : {
2535 14 : need_another_pass = true;
2536 14 : continue;
2537 : }
2538 :
2539 169713 : last_tail->aux = bb;
2540 169713 : last_tail = (basic_block) bb->aux;
2541 : }
2542 :
2543 35925 : current_partition ^= BB_HOT_PARTITION | BB_COLD_PARTITION;
2544 : }
2545 :
2546 35919 : last_tail->aux = 0;
2547 :
2548 : /* Finally, link all the chosen fallthrough edges. */
2549 :
2550 790375 : for (int j = 0; j < n; j++)
2551 754456 : if (edges[j])
2552 373588 : edges[j]->src->aux = edges[j]->dest;
2553 :
2554 35919 : delete[] edges;
2555 :
2556 : /* If the entry edge no longer falls through we have to make a new
2557 : block so it can do so again. */
2558 :
2559 35919 : edge e = EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0);
2560 35919 : if (e->dest != ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux)
2561 : {
2562 8 : force_nonfallthru (e);
2563 8 : e->src->aux = ENTRY_BLOCK_PTR_FOR_FN (cfun)->aux;
2564 : }
2565 35919 : }
2566 :
2567 : /* Reorder basic blocks. The main entry point to this file. */
2568 :
2569 : static void
2570 1064962 : reorder_basic_blocks (void)
2571 : {
2572 1064962 : gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT);
2573 :
2574 1064962 : if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1)
2575 : return;
2576 :
2577 643480 : set_edge_can_fallthru_flag ();
2578 643480 : mark_dfs_back_edges ();
2579 :
2580 643480 : switch (flag_reorder_blocks_algorithm)
2581 : {
2582 35919 : case REORDER_BLOCKS_ALGORITHM_SIMPLE:
2583 35919 : reorder_basic_blocks_simple ();
2584 35919 : break;
2585 :
2586 607561 : case REORDER_BLOCKS_ALGORITHM_STC:
2587 607561 : reorder_basic_blocks_software_trace_cache ();
2588 607561 : break;
2589 :
2590 0 : default:
2591 0 : gcc_unreachable ();
2592 : }
2593 :
2594 643480 : relink_block_chain (/*stay_in_cfglayout_mode=*/true);
2595 :
2596 643480 : if (dump_file)
2597 : {
2598 31 : if (dump_flags & TDF_DETAILS)
2599 0 : dump_reg_info (dump_file);
2600 31 : dump_flow_info (dump_file, dump_flags);
2601 : }
2602 :
2603 : /* Signal that rtl_verify_flow_info_1 can now verify that there
2604 : is at most one switch between hot/cold sections. */
2605 643480 : crtl->bb_reorder_complete = true;
2606 : }
2607 :
2608 : /* Determine which partition the first basic block in the function
2609 : belongs to, then find the first basic block in the current function
2610 : that belongs to a different section, and insert a
2611 : NOTE_INSN_SWITCH_TEXT_SECTIONS note immediately before it in the
2612 : instruction stream. When writing out the assembly code,
2613 : encountering this note will make the compiler switch between the
2614 : hot and cold text sections. */
2615 :
2616 : void
2617 65368 : insert_section_boundary_note (void)
2618 : {
2619 65368 : basic_block bb;
2620 65368 : bool switched_sections = false;
2621 65368 : int current_partition = 0;
2622 :
2623 65368 : if (!crtl->has_bb_partition)
2624 : return;
2625 :
2626 1871810 : FOR_EACH_BB_FN (bb, cfun)
2627 : {
2628 1806442 : if (!current_partition)
2629 65368 : current_partition = BB_PARTITION (bb);
2630 1806442 : if (BB_PARTITION (bb) != current_partition)
2631 : {
2632 65368 : gcc_assert (!switched_sections);
2633 65368 : switched_sections = true;
2634 65368 : emit_note_before (NOTE_INSN_SWITCH_TEXT_SECTIONS, BB_HEAD (bb));
2635 65368 : current_partition = BB_PARTITION (bb);
2636 : }
2637 : }
2638 :
2639 : /* Make sure crtl->has_bb_partition matches reality even if bbpart finds
2640 : some hot and some cold basic blocks, but later one of those kinds is
2641 : optimized away. */
2642 65368 : crtl->has_bb_partition = switched_sections;
2643 : }
2644 :
2645 : namespace {
2646 :
2647 : const pass_data pass_data_reorder_blocks =
2648 : {
2649 : RTL_PASS, /* type */
2650 : "bbro", /* name */
2651 : OPTGROUP_NONE, /* optinfo_flags */
2652 : TV_REORDER_BLOCKS, /* tv_id */
2653 : 0, /* properties_required */
2654 : 0, /* properties_provided */
2655 : 0, /* properties_destroyed */
2656 : 0, /* todo_flags_start */
2657 : 0, /* todo_flags_finish */
2658 : };
2659 :
2660 : class pass_reorder_blocks : public rtl_opt_pass
2661 : {
2662 : public:
2663 297180 : pass_reorder_blocks (gcc::context *ctxt)
2664 594360 : : rtl_opt_pass (pass_data_reorder_blocks, ctxt)
2665 : {}
2666 :
2667 : /* opt_pass methods: */
2668 1517135 : bool gate (function *) final override
2669 : {
2670 1517135 : if (targetm.cannot_modify_jumps_p ())
2671 : return false;
2672 1517135 : return (optimize > 0
2673 1517135 : && (flag_reorder_blocks || flag_reorder_blocks_and_partition));
2674 : }
2675 :
2676 : unsigned int execute (function *) final override;
2677 :
2678 : }; // class pass_reorder_blocks
2679 :
2680 : unsigned int
2681 1064962 : pass_reorder_blocks::execute (function *fun)
2682 : {
2683 1064962 : basic_block bb;
2684 :
2685 : /* Last attempt to optimize CFG, as scheduling, peepholing and insn
2686 : splitting possibly introduced more crossjumping opportunities. */
2687 1064962 : cfg_layout_initialize (CLEANUP_EXPENSIVE);
2688 :
2689 1064962 : reorder_basic_blocks ();
2690 1064962 : cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_NO_PARTITIONING);
2691 :
2692 11987840 : FOR_EACH_BB_FN (bb, fun)
2693 10922878 : if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
2694 9857916 : bb->aux = bb->next_bb;
2695 1064962 : cfg_layout_finalize ();
2696 :
2697 12176903 : FOR_EACH_BB_FN (bb, fun)
2698 11111941 : df_recompute_luids (bb);
2699 1064962 : return 0;
2700 : }
2701 :
2702 : } // anon namespace
2703 :
2704 : rtl_opt_pass *
2705 297180 : make_pass_reorder_blocks (gcc::context *ctxt)
2706 : {
2707 297180 : return new pass_reorder_blocks (ctxt);
2708 : }
2709 :
2710 : /* Return the unit of --param=max-goto-duplication-insns: the length of an
2711 : unconditional jump, or 1 if the target has no length attribute. */
2712 :
2713 : static int
2714 924404 : duplication_unit (void)
2715 : {
2716 924404 : if (!HAVE_ATTR_length)
2717 : return 1;
2718 :
2719 : /* We are estimating the length of uncond jump insn only once
2720 : since the code for getting the insn length always returns
2721 : the minimal length now. */
2722 924404 : if (uncond_jump_length == 0)
2723 112997 : uncond_jump_length = get_uncond_jump_length ();
2724 :
2725 : /* A target with insn lengths gives a jump a nonzero length. A zero unit
2726 : would make every budget 0, whatever the parameter says. */
2727 924404 : gcc_checking_assert (uncond_jump_length > 0);
2728 924404 : return uncond_jump_length;
2729 : }
2730 :
2731 : /* Return the size of INSN in the units of duplication_unit: its minimum
2732 : length, or 1 for an active insn if the target has no length attribute.
2733 : Debug insns never count, so they cannot change the decision. */
2734 :
2735 : static int
2736 82782 : duplication_size (rtx_insn *insn)
2737 : {
2738 82782 : if (HAVE_ATTR_length)
2739 0 : return get_attr_min_length (insn);
2740 : return active_insn_p (insn);
2741 : }
2742 :
2743 : /* Return true if INSN is a jump whose predecessors are worth giving a copy
2744 : of their own. Every transition through such a jump uses the same indirect
2745 : branch instruction, which can make indirect target prediction less
2746 : effective. */
2747 :
2748 : static bool
2749 10615574 : dispatch_jump_p (rtx_insn *insn)
2750 : {
2751 10615574 : if (computed_jump_p (insn))
2752 : return true;
2753 :
2754 : /* A switch lowered to a jump table dispatches exactly like a factored
2755 : computed goto. Copying such a block makes the copies share the one
2756 : table, so only the branch is replicated, not the table. The target
2757 : decides whether the dispatch can share its table. Sharing a table in a
2758 : partitioned function would require explicit ownership of the section of
2759 : the base of the table entries. */
2760 10621752 : if (!(flag_duplicate_switch_dispatch
2761 10614675 : && !crtl->has_bb_partition
2762 8703392 : && tablejump_p (insn, NULL, NULL)
2763 6945 : && targetm.can_share_jump_table_p (insn)))
2764 : return false;
2765 :
2766 : #ifdef STACK_REGS
2767 : /* Stack-register conversion can split outgoing edges to reconcile stack
2768 : layouts. Such edges cannot be redirected for one shared-table user. */
2769 59633 : for (int regno = FIRST_STACK_REG; regno <= LAST_STACK_REG; ++regno)
2770 53047 : if (df_regs_ever_live_p (regno))
2771 : return false;
2772 : #endif
2773 :
2774 : return true;
2775 : }
2776 :
2777 : /* Return true if a copy of the dispatch can be attached to the source of E,
2778 : taking over that edge. */
2779 :
2780 : static bool
2781 18541 : can_attach_dispatch_copy_p (edge e)
2782 : {
2783 18541 : basic_block pred = e->src;
2784 :
2785 18541 : return (single_succ_p (pred)
2786 2488 : && !(e->flags & EDGE_COMPLEX)
2787 2488 : && pred->index >= NUM_FIXED_BLOCKS
2788 20513 : && (!JUMP_P (BB_END (pred))
2789 987 : || (simplejump_p (BB_END (pred))
2790 981 : && !CROSSING_JUMP_P (BB_END (pred)))));
2791 : }
2792 :
2793 : /* Return true if the fall-through edge E also stands for a branch, that is
2794 : if the jump at the end of its source names its destination as well.
2795 : Such an edge cannot move to a copy of its destination without changing
2796 : the jump. */
2797 :
2798 : static bool
2799 9903 : fallthru_unified_with_branch_p (edge e)
2800 : {
2801 9903 : rtx_insn *end = BB_END (e->src);
2802 9903 : return JUMP_P (end) && label_is_jump_target_p (BB_HEAD (e->dest), end);
2803 : }
2804 :
2805 : /* Collect into CHAIN the blocks that have to be copied together with the
2806 : dispatch block BB, innermost first, and return the head of the chain: the
2807 : block whose predecessors the copies are attached to. Anything above the
2808 : dispatch is reached only through the chain, so copying the lot into a
2809 : predecessor of the head is sound. The chain is what makes a jump table
2810 : dispatch reachable at all, since the range check that guards it sits in a
2811 : block of its own. Return NULL if the chain is larger than MAX_SIZE, which
2812 : is in units of duplication_unit. */
2813 :
2814 : static basic_block
2815 9315 : find_dispatch_chain (basic_block bb, int max_size,
2816 : vec<basic_block> *chain)
2817 : {
2818 9315 : int size = 0;
2819 :
2820 : /* Count a tablejump as one instruction. Its target sequence is an
2821 : indivisible part of every copy, while the budget still bounds the work
2822 : copied with it. */
2823 9315 : rtx_insn *dispatch = NULL;
2824 9315 : if (tablejump_p (BB_END (bb), NULL, NULL))
2825 8323 : dispatch = BB_END (bb);
2826 :
2827 17546 : for (basic_block b = bb; ; b = single_pred (b))
2828 : {
2829 17546 : rtx_insn *insn;
2830 140897 : FOR_BB_INSNS (b, insn)
2831 128451 : if (INSN_P (insn))
2832 : {
2833 181604 : size += (insn == dispatch
2834 90802 : ? duplication_unit () : duplication_size (insn));
2835 90802 : if (size > max_size)
2836 5100 : return NULL;
2837 : }
2838 :
2839 12446 : chain->safe_push (b);
2840 :
2841 : /* Stop at the block the copies attach to, and at anything we may not
2842 : copy. Only a jump table dispatch needs more than its own block, and
2843 : only a plain fall-through predecessor can be taken along: the copies
2844 : are laid out one after the other, so any other edge into the chain
2845 : would need a jump of its own, and a jump that also targets the next
2846 : block would still name the original block. */
2847 12446 : if (!dispatch || !single_pred_p (b))
2848 : break;
2849 9359 : edge in = single_pred_edge (b);
2850 9359 : if (can_attach_dispatch_copy_p (in)
2851 9356 : || !(in->flags & EDGE_FALLTHRU)
2852 8699 : || in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
2853 8237 : || !can_duplicate_block_p (in->src)
2854 17596 : || fallthru_unified_with_branch_p (in))
2855 : break;
2856 8231 : }
2857 :
2858 4215 : return chain->last ();
2859 : }
2860 :
2861 : /* Duplicate the dispatch block BB, along with the blocks it can only be
2862 : reached through, into the predecessors of that chain, where possible.
2863 : MAX_SIZE limits the size of the chain, in units of duplication_unit.
2864 : If REQUIRE_BACK_EDGE is true, first require a DFS back edge into the head
2865 : of the chain. Return whether anything is changed. */
2866 : static bool
2867 9315 : maybe_duplicate_dispatch (basic_block bb, int max_size,
2868 : bool require_back_edge)
2869 : {
2870 9315 : auto_vec<basic_block, 4> chain;
2871 9315 : basic_block head = find_dispatch_chain (bb, max_size, &chain);
2872 9315 : if (!head)
2873 : return false;
2874 :
2875 4215 : if (require_back_edge)
2876 : {
2877 3224 : bool found = false;
2878 3224 : edge e;
2879 3224 : edge_iterator ei;
2880 14938 : FOR_EACH_EDGE (e, ei, head->preds)
2881 12680 : if (e->flags & EDGE_DFS_BACK)
2882 : {
2883 : found = true;
2884 : break;
2885 : }
2886 3224 : if (!found)
2887 2258 : return false;
2888 : }
2889 :
2890 1957 : bool changed = false;
2891 1957 : edge e;
2892 1957 : edge_iterator ei;
2893 11139 : for (ei = ei_start (head->preds); (e = ei_safe_edge (ei)); )
2894 : {
2895 9182 : basic_block pred = e->src;
2896 :
2897 : /* Do not duplicate the chain into PRED if we cannot merge a copy of
2898 : its head with PRED. */
2899 9182 : if (!can_attach_dispatch_copy_p (e))
2900 : {
2901 7220 : ei_next (&ei);
2902 7220 : continue;
2903 : }
2904 :
2905 1962 : if (dump_file)
2906 83 : fprintf (dump_file, "Duplicating dispatch bb %d into bb %d\n",
2907 : bb->index, pred->index);
2908 :
2909 : /* Remember if PRED can be duplicated; if so, the copy of the chain
2910 : merged with PRED can be duplicated as well. */
2911 1962 : bool can_dup_more = can_duplicate_block_p (pred);
2912 :
2913 : /* Copy the chain head first, so that the copies end up in the
2914 : instruction stream in the order they are executed in. Only the head
2915 : takes over the edge from PRED; the edges inside the chain are
2916 : fall-through and so are moved onto the copies directly. */
2917 1962 : auto_vec<basic_block, 4> copies;
2918 7552 : for (unsigned i = chain.length (); i-- > 0; )
2919 : {
2920 3628 : basic_block copy;
2921 3628 : if (copies.is_empty ())
2922 1962 : copy = duplicate_block (chain[i], e, NULL);
2923 : else
2924 : {
2925 1666 : edge in = find_edge (copies.last (), chain[i]);
2926 1666 : gcc_checking_assert (!fallthru_unified_with_branch_p (in));
2927 1666 : profile_count count = in->count ();
2928 1666 : if (chain[i]->count < count)
2929 15 : count = chain[i]->count;
2930 1666 : copy = duplicate_block (chain[i], NULL, NULL);
2931 1666 : copy->count = count;
2932 1666 : chain[i]->count -= count;
2933 1666 : redirect_edge_succ (in, copy);
2934 : }
2935 3628 : copies.safe_push (copy);
2936 : }
2937 :
2938 1962 : basic_block first = copies[0];
2939 1962 : basic_block last = copies.last ();
2940 :
2941 : /* Move the copies after PRED and fold the head into it. */
2942 1962 : emit_barrier_after_bb (last);
2943 1962 : reorder_insns_nobb (BB_HEAD (first), BB_END (last), BB_END (pred));
2944 1962 : merge_blocks (pred, first);
2945 :
2946 : /* The rest of the chain stays as separate blocks that PRED falls
2947 : through to, so put them in the block order to match. */
2948 1962 : basic_block after = pred;
2949 5590 : for (unsigned i = 1; i < copies.length (); i++)
2950 : {
2951 1666 : unlink_block (copies[i]);
2952 1666 : link_block (copies[i], after);
2953 1666 : after = copies[i];
2954 : }
2955 :
2956 1962 : changed = true;
2957 :
2958 : /* Try to merge the resulting dispatch block into further
2959 : predecessors. */
2960 1962 : if (can_dup_more)
2961 3593 : maybe_duplicate_dispatch (first == last ? pred : last, max_size, false);
2962 1962 : }
2963 :
2964 : return changed;
2965 9315 : }
2966 :
2967 : /* Duplicate the blocks containing computed gotos. This basically unfactors
2968 : computed gotos that were factored early on in the compilation process to
2969 : speed up edge based data flow. We used to not unfactor them again, which
2970 : can seriously pessimize code with many computed jumps in the source code,
2971 : such as interpreters. See e.g. PR15242.
2972 :
2973 : With -fduplicate-switch-dispatch the same is done for a switch lowered to
2974 : a jump table, which an interpreter written without the labels-as-values
2975 : extension ends up with. See PR126236. */
2976 : static void
2977 916384 : duplicate_computed_gotos (function *fun)
2978 : {
2979 : /* Never copy a block larger than this. */
2980 916384 : int max_size = duplication_unit () * param_max_goto_duplication_insns;
2981 :
2982 916384 : bool changed = false;
2983 916384 : bool back_edges_marked = false;
2984 :
2985 916384 : gcc_checking_assert (!(fun->curr_properties
2986 : & PROP_rtl_allow_tablejump_duplication));
2987 916384 : fun->curr_properties |= PROP_rtl_allow_tablejump_duplication;
2988 :
2989 : /* Try to duplicate all blocks that end in a dispatching jump and that
2990 : can be duplicated at all. */
2991 916384 : basic_block bb;
2992 11531958 : FOR_EACH_BB_FN (bb, fun)
2993 : {
2994 10615574 : if (!dispatch_jump_p (BB_END (bb))
2995 10615574 : || !can_duplicate_block_p (bb))
2996 10608221 : continue;
2997 :
2998 7353 : bool tablejump = tablejump_p (BB_END (bb), NULL, NULL);
2999 7353 : if (tablejump && !back_edges_marked)
3000 : {
3001 4491 : mark_dfs_back_edges ();
3002 4491 : back_edges_marked = true;
3003 : }
3004 :
3005 7353 : changed |= maybe_duplicate_dispatch (bb, max_size, tablejump);
3006 : }
3007 :
3008 916384 : fun->curr_properties &= ~PROP_rtl_allow_tablejump_duplication;
3009 :
3010 : /* Some blocks may have become unreachable. */
3011 916384 : if (changed)
3012 990 : cleanup_cfg (0);
3013 :
3014 : /* Duplicating blocks will redirect edges and may cause hot blocks
3015 : previously reached by both hot and cold blocks to become dominated
3016 : only by cold blocks. */
3017 990 : if (changed)
3018 990 : fixup_partitions ();
3019 916384 : }
3020 :
3021 : namespace {
3022 :
3023 : const pass_data pass_data_duplicate_computed_gotos =
3024 : {
3025 : RTL_PASS, /* type */
3026 : "compgotos", /* name */
3027 : OPTGROUP_NONE, /* optinfo_flags */
3028 : TV_DUP_COMPGOTO, /* tv_id */
3029 : 0, /* properties_required */
3030 : 0, /* properties_provided */
3031 : 0, /* properties_destroyed */
3032 : 0, /* todo_flags_start */
3033 : 0, /* todo_flags_finish */
3034 : };
3035 :
3036 : class pass_duplicate_computed_gotos : public rtl_opt_pass
3037 : {
3038 : public:
3039 297180 : pass_duplicate_computed_gotos (gcc::context *ctxt)
3040 594360 : : rtl_opt_pass (pass_data_duplicate_computed_gotos, ctxt)
3041 : {}
3042 :
3043 : /* opt_pass methods: */
3044 : bool gate (function *) final override;
3045 : unsigned int execute (function *) final override;
3046 :
3047 : }; // class pass_duplicate_computed_gotos
3048 :
3049 : bool
3050 1517135 : pass_duplicate_computed_gotos::gate (function *fun)
3051 : {
3052 1517135 : if (targetm.cannot_modify_jumps_p ())
3053 : return false;
3054 1517135 : return (optimize > 0
3055 1064964 : && flag_expensive_optimizations
3056 2499833 : && ! optimize_function_for_size_p (fun));
3057 : }
3058 :
3059 : unsigned int
3060 916384 : pass_duplicate_computed_gotos::execute (function *fun)
3061 : {
3062 916384 : duplicate_computed_gotos (fun);
3063 :
3064 916384 : return 0;
3065 : }
3066 :
3067 : } // anon namespace
3068 :
3069 : rtl_opt_pass *
3070 297180 : make_pass_duplicate_computed_gotos (gcc::context *ctxt)
3071 : {
3072 297180 : return new pass_duplicate_computed_gotos (ctxt);
3073 : }
3074 :
3075 : /* This function is the main 'entrance' for the optimization that
3076 : partitions hot and cold basic blocks into separate sections of the
3077 : .o file (to improve performance and cache locality). Ideally it
3078 : would be called after all optimizations that rearrange the CFG have
3079 : been called. However part of this optimization may introduce new
3080 : register usage, so it must be called before register allocation has
3081 : occurred. This means that this optimization is actually called
3082 : well before the optimization that reorders basic blocks (see
3083 : function above).
3084 :
3085 : This optimization checks the feedback information to determine
3086 : which basic blocks are hot/cold, updates flags on the basic blocks
3087 : to indicate which section they belong in. This information is
3088 : later used for writing out sections in the .o file. Because hot
3089 : and cold sections can be arbitrarily large (within the bounds of
3090 : memory), far beyond the size of a single function, it is necessary
3091 : to fix up all edges that cross section boundaries, to make sure the
3092 : instructions used can actually span the required distance. The
3093 : fixes are described below.
3094 :
3095 : Fall-through edges must be changed into jumps; it is not safe or
3096 : legal to fall through across a section boundary. Whenever a
3097 : fall-through edge crossing a section boundary is encountered, a new
3098 : basic block is inserted (in the same section as the fall-through
3099 : source), and the fall through edge is redirected to the new basic
3100 : block. The new basic block contains an unconditional jump to the
3101 : original fall-through target. (If the unconditional jump is
3102 : insufficient to cross section boundaries, that is dealt with a
3103 : little later, see below).
3104 :
3105 : In order to deal with architectures that have short conditional
3106 : branches (which cannot span all of memory) we take any conditional
3107 : jump that attempts to cross a section boundary and add a level of
3108 : indirection: it becomes a conditional jump to a new basic block, in
3109 : the same section. The new basic block contains an unconditional
3110 : jump to the original target, in the other section.
3111 :
3112 : For those architectures whose unconditional branch is also
3113 : incapable of reaching all of memory, those unconditional jumps are
3114 : converted into indirect jumps, through a register.
3115 :
3116 : IMPORTANT NOTE: This optimization causes some messy interactions
3117 : with the cfg cleanup optimizations; those optimizations want to
3118 : merge blocks wherever possible, and to collapse indirect jump
3119 : sequences (change "A jumps to B jumps to C" directly into "A jumps
3120 : to C"). Those optimizations can undo the jump fixes that
3121 : partitioning is required to make (see above), in order to ensure
3122 : that jumps attempting to cross section boundaries are really able
3123 : to cover whatever distance the jump requires (on many architectures
3124 : conditional or unconditional jumps are not able to reach all of
3125 : memory). Therefore tests have to be inserted into each such
3126 : optimization to make sure that it does not undo stuff necessary to
3127 : cross partition boundaries. This would be much less of a problem
3128 : if we could perform this optimization later in the compilation, but
3129 : unfortunately the fact that we may need to create indirect jumps
3130 : (through registers) requires that this optimization be performed
3131 : before register allocation.
3132 :
3133 : Hot and cold basic blocks are partitioned and put in separate
3134 : sections of the .o file, to reduce paging and improve cache
3135 : performance (hopefully). This can result in bits of code from the
3136 : same function being widely separated in the .o file. However this
3137 : is not obvious to the current bb structure. Therefore we must take
3138 : care to ensure that: 1). There are no fall_thru edges that cross
3139 : between sections; 2). For those architectures which have "short"
3140 : conditional branches, all conditional branches that attempt to
3141 : cross between sections are converted to unconditional branches;
3142 : and, 3). For those architectures which have "short" unconditional
3143 : branches, all unconditional branches that attempt to cross between
3144 : sections are converted to indirect jumps.
3145 :
3146 : The code for fixing up fall_thru edges that cross between hot and
3147 : cold basic blocks does so by creating new basic blocks containing
3148 : unconditional branches to the appropriate label in the "other"
3149 : section. The new basic block is then put in the same (hot or cold)
3150 : section as the original conditional branch, and the fall_thru edge
3151 : is modified to fall into the new basic block instead. By adding
3152 : this level of indirection we end up with only unconditional branches
3153 : crossing between hot and cold sections.
3154 :
3155 : Conditional branches are dealt with by adding a level of indirection.
3156 : A new basic block is added in the same (hot/cold) section as the
3157 : conditional branch, and the conditional branch is retargeted to the
3158 : new basic block. The new basic block contains an unconditional branch
3159 : to the original target of the conditional branch (in the other section).
3160 :
3161 : Unconditional branches are dealt with by converting them into
3162 : indirect jumps. */
3163 :
3164 : namespace {
3165 :
3166 : const pass_data pass_data_partition_blocks =
3167 : {
3168 : RTL_PASS, /* type */
3169 : "bbpart", /* name */
3170 : OPTGROUP_NONE, /* optinfo_flags */
3171 : TV_REORDER_BLOCKS, /* tv_id */
3172 : PROP_cfglayout, /* properties_required */
3173 : 0, /* properties_provided */
3174 : 0, /* properties_destroyed */
3175 : 0, /* todo_flags_start */
3176 : 0, /* todo_flags_finish */
3177 : };
3178 :
3179 : class pass_partition_blocks : public rtl_opt_pass
3180 : {
3181 : public:
3182 297180 : pass_partition_blocks (gcc::context *ctxt)
3183 594360 : : rtl_opt_pass (pass_data_partition_blocks, ctxt)
3184 : {}
3185 :
3186 : /* opt_pass methods: */
3187 : bool gate (function *) final override;
3188 : unsigned int execute (function *) final override;
3189 :
3190 : }; // class pass_partition_blocks
3191 :
3192 : bool
3193 1517135 : pass_partition_blocks::gate (function *fun)
3194 : {
3195 : /* The optimization to partition hot/cold basic blocks into separate
3196 : sections of the .o file does not work well with linkonce or with
3197 : user defined section attributes or with naked attribute. Don't call
3198 : it if either case arises. */
3199 1517135 : return (flag_reorder_blocks_and_partition
3200 742154 : && optimize
3201 : /* See pass_reorder_blocks::gate. We should not partition if
3202 : we are going to omit the reordering. */
3203 742122 : && optimize_function_for_speed_p (fun)
3204 691353 : && !DECL_COMDAT_GROUP (current_function_decl)
3205 582463 : && !lookup_attribute ("section", DECL_ATTRIBUTES (fun->decl))
3206 582417 : && !lookup_attribute ("naked", DECL_ATTRIBUTES (fun->decl))
3207 : /* Workaround a bug in GDB where read_partial_die doesn't cope
3208 : with DIEs with DW_AT_ranges, see PR81115. */
3209 2099503 : && !(in_lto_p && MAIN_NAME_P (DECL_NAME (fun->decl))));
3210 : }
3211 :
3212 : unsigned
3213 572432 : pass_partition_blocks::execute (function *fun)
3214 : {
3215 572432 : vec<edge> crossing_edges;
3216 :
3217 572432 : if (n_basic_blocks_for_fn (fun) <= NUM_FIXED_BLOCKS + 1)
3218 : return 0;
3219 :
3220 270447 : df_set_flags (DF_DEFER_INSN_RESCAN);
3221 :
3222 270447 : crossing_edges = find_rarely_executed_basic_blocks_and_crossing_edges ();
3223 270447 : if (!crossing_edges.exists ())
3224 : /* Make sure to process deferred rescans and clear changeable df flags. */
3225 : return TODO_df_finish;
3226 :
3227 65368 : crtl->has_bb_partition = true;
3228 :
3229 : /* Make sure the source of any crossing edge ends in a jump and the
3230 : destination of any crossing edge has a label. */
3231 65368 : add_labels_and_missing_jumps (crossing_edges);
3232 :
3233 : /* Convert all crossing fall_thru edges to non-crossing fall
3234 : thrus to unconditional jumps (that jump to the original fall
3235 : through dest). */
3236 65368 : fix_up_fall_thru_edges ();
3237 :
3238 : /* If the architecture does not have conditional branches that can
3239 : span all of memory, convert crossing conditional branches into
3240 : crossing unconditional branches. */
3241 65368 : if (!HAS_LONG_COND_BRANCH)
3242 : fix_crossing_conditional_branches ();
3243 :
3244 : /* If the architecture does not have unconditional branches that
3245 : can span all of memory, convert crossing unconditional branches
3246 : into indirect jumps. Since adding an indirect jump also adds
3247 : a new register usage, update the register usage information as
3248 : well. */
3249 65368 : if (!HAS_LONG_UNCOND_BRANCH)
3250 : fix_crossing_unconditional_branches ();
3251 :
3252 65368 : update_crossing_jump_flags ();
3253 :
3254 : /* Clear bb->aux fields that the above routines were using. */
3255 65368 : clear_aux_for_blocks ();
3256 :
3257 65368 : crossing_edges.release ();
3258 :
3259 : /* ??? FIXME: DF generates the bb info for a block immediately.
3260 : And by immediately, I mean *during* creation of the block.
3261 :
3262 : #0 df_bb_refs_collect
3263 : #1 in df_bb_refs_record
3264 : #2 in create_basic_block_structure
3265 :
3266 : Which means that the bb_has_eh_pred test in df_bb_refs_collect
3267 : will *always* fail, because no edges can have been added to the
3268 : block yet. Which of course means we don't add the right
3269 : artificial refs, which means we fail df_verify (much) later.
3270 :
3271 : Cleanest solution would seem to make DF_DEFER_INSN_RESCAN imply
3272 : that we also shouldn't grab data from the new blocks those new
3273 : insns are in either. In this way one can create the block, link
3274 : it up properly, and have everything Just Work later, when deferred
3275 : insns are processed.
3276 :
3277 : In the meantime, we have no other option but to throw away all
3278 : of the DF data and recompute it all. */
3279 65368 : if (fun->eh->lp_array)
3280 : {
3281 65368 : df_finish_pass (true);
3282 65368 : df_scan_alloc (NULL);
3283 65368 : df_scan_blocks ();
3284 : /* Not all post-landing pads use all of the EH_RETURN_DATA_REGNO
3285 : data. We blindly generated all of them when creating the new
3286 : landing pad. Delete those assignments we don't use. */
3287 65368 : df_set_flags (DF_LR_RUN_DCE);
3288 65368 : df_analyze ();
3289 : }
3290 :
3291 : /* Make sure to process deferred rescans and clear changeable df flags. */
3292 : return TODO_df_finish;
3293 : }
3294 :
3295 : } // anon namespace
3296 :
3297 : rtl_opt_pass *
3298 297180 : make_pass_partition_blocks (gcc::context *ctxt)
3299 : {
3300 297180 : return new pass_partition_blocks (ctxt);
3301 : }
|