Line data Source code
1 : /* Control flow graph building code for GNU compiler.
2 : Copyright (C) 1987-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 under
7 : the terms of the GNU General Public License as published by the Free
8 : Software Foundation; either version 3, or (at your option) any later
9 : version.
10 :
11 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 : 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 :
21 : #include "config.h"
22 : #include "system.h"
23 : #include "coretypes.h"
24 : #include "backend.h"
25 : #include "rtl.h"
26 : #include "cfghooks.h"
27 : #include "memmodel.h"
28 : #include "emit-rtl.h"
29 : #include "cfgrtl.h"
30 : #include "cfganal.h"
31 : #include "cfgbuild.h"
32 : #include "except.h"
33 : #include "stmt.h"
34 :
35 : static void make_edges (basic_block, basic_block, int);
36 : static void make_label_edge (sbitmap, basic_block, rtx, int);
37 : static void find_bb_boundaries (basic_block);
38 : static void compute_outgoing_frequencies (basic_block);
39 :
40 : /* Return true if insn is something that should be contained inside basic
41 : block. */
42 :
43 : bool
44 202540655 : inside_basic_block_p (const rtx_insn *insn)
45 : {
46 202540655 : switch (GET_CODE (insn))
47 : {
48 11704082 : case CODE_LABEL:
49 : /* Avoid creating of basic block for jumptables. */
50 11704082 : return (NEXT_INSN (insn) == 0
51 11704082 : || ! JUMP_TABLE_DATA_P (NEXT_INSN (insn)));
52 :
53 : case JUMP_INSN:
54 : case CALL_INSN:
55 : case INSN:
56 : case DEBUG_INSN:
57 : return true;
58 :
59 : case JUMP_TABLE_DATA:
60 : case BARRIER:
61 : case NOTE:
62 : return false;
63 :
64 0 : default:
65 0 : gcc_unreachable ();
66 : }
67 : }
68 :
69 : /* Return true if INSN may cause control flow transfer, so it should be last in
70 : the basic block. */
71 :
72 : bool
73 11260429918 : control_flow_insn_p (const rtx_insn *insn)
74 : {
75 11260429918 : switch (GET_CODE (insn))
76 : {
77 : case NOTE:
78 : case CODE_LABEL:
79 : case DEBUG_INSN:
80 : return false;
81 :
82 : case JUMP_INSN:
83 : return true;
84 :
85 406095625 : case CALL_INSN:
86 : /* Noreturn and sibling call instructions terminate the basic blocks
87 : (but only if they happen unconditionally). */
88 406095625 : if ((SIBLING_CALL_P (insn)
89 405191440 : || find_reg_note (insn, REG_NORETURN, 0))
90 409634741 : && GET_CODE (PATTERN (insn)) != COND_EXEC)
91 : return true;
92 :
93 : /* Call insn may return to the nonlocal goto handler. */
94 401652324 : if (can_nonlocal_goto (insn))
95 : return true;
96 : break;
97 :
98 5414471878 : case INSN:
99 : /* Treat trap instructions like noreturn calls (same provision). */
100 5414471878 : if (GET_CODE (PATTERN (insn)) == TRAP_IF
101 5414471878 : && XEXP (PATTERN (insn), 0) == const1_rtx)
102 : return true;
103 5414390757 : if (!cfun->can_throw_non_call_exceptions)
104 : return false;
105 : break;
106 :
107 : case JUMP_TABLE_DATA:
108 : case BARRIER:
109 : /* It is nonsense to reach this when looking for the
110 : end of basic block, but before dead code is eliminated
111 : this may happen. */
112 : return false;
113 :
114 0 : default:
115 0 : gcc_unreachable ();
116 : }
117 :
118 1756147094 : return can_throw_internal (insn);
119 : }
120 :
121 :
122 : /* Create an edge between two basic blocks. FLAGS are auxiliary information
123 : about the edge that is accumulated between calls. */
124 :
125 : /* Create an edge from a basic block to a label. */
126 :
127 : static void
128 16219164 : make_label_edge (sbitmap edge_cache, basic_block src, rtx label, int flags)
129 : {
130 16219164 : gcc_assert (LABEL_P (label));
131 :
132 : /* If the label was never emitted, this insn is junk, but avoid a
133 : crash trying to refer to BLOCK_FOR_INSN (label). This can happen
134 : as a result of a syntax error and a diagnostic has already been
135 : printed. */
136 :
137 16219164 : if (INSN_UID (label) == 0)
138 : return;
139 :
140 16219164 : cached_make_edge (edge_cache, src, BLOCK_FOR_INSN (label), flags);
141 : }
142 :
143 : /* Create the edges generated by INSN in REGION. */
144 :
145 : void
146 9867322 : rtl_make_eh_edge (sbitmap edge_cache, basic_block src, rtx_insn *insn)
147 : {
148 9867322 : eh_landing_pad lp = get_eh_landing_pad_from_rtx (insn);
149 :
150 9867322 : if (lp)
151 : {
152 1287638 : rtx_insn *label = lp->landing_pad;
153 :
154 : /* During initial rtl generation, use the post_landing_pad. */
155 1287638 : if (label == NULL)
156 : {
157 747507 : gcc_assert (lp->post_landing_pad);
158 747507 : label = label_rtx (lp->post_landing_pad);
159 : }
160 :
161 1287638 : make_label_edge (edge_cache, src, label,
162 : EDGE_ABNORMAL | EDGE_EH
163 1287638 : | (CALL_P (insn) ? EDGE_ABNORMAL_CALL : 0));
164 : }
165 9867322 : }
166 :
167 : /* States of basic block as seen by find_many_sub_basic_blocks. */
168 : enum state {
169 : /* Basic blocks created via split_block belong to this state.
170 : make_edges will examine these basic blocks to see if we need to
171 : create edges going out of them. */
172 : BLOCK_NEW = 0,
173 :
174 : /* Basic blocks that do not need examining belong to this state.
175 : These blocks will be left intact. In particular, make_edges will
176 : not create edges going out of these basic blocks. */
177 : BLOCK_ORIGINAL,
178 :
179 : /* Basic blocks that may need splitting (due to a label appearing in
180 : the middle, etc) belong to this state. After splitting them,
181 : make_edges will create edges going out of them as needed. */
182 : BLOCK_TO_SPLIT
183 : };
184 :
185 : #define STATE(BB) (enum state) ((size_t) (BB)->aux)
186 : #define SET_STATE(BB, STATE) ((BB)->aux = (void *) (size_t) (STATE))
187 :
188 : /* Used internally by purge_dead_tablejump_edges, ORed into state. */
189 : #define BLOCK_USED_BY_TABLEJUMP 32
190 : #define FULL_STATE(BB) ((size_t) (BB)->aux)
191 :
192 : /* Identify the edges going out of basic blocks between MIN and MAX,
193 : inclusive, that have their states set to BLOCK_NEW or
194 : BLOCK_TO_SPLIT.
195 :
196 : UPDATE_P should be nonzero if we are updating CFG and zero if we
197 : are building CFG from scratch. */
198 :
199 : static void
200 4013372 : make_edges (basic_block min, basic_block max, int update_p)
201 : {
202 4013372 : basic_block bb;
203 4013372 : sbitmap edge_cache = NULL;
204 :
205 : /* Heavy use of computed goto in machine-generated code can lead to
206 : nearly fully-connected CFGs. In that case we spend a significant
207 : amount of time searching the edge lists for duplicates. */
208 4013372 : if (!vec_safe_is_empty (forced_labels)
209 3967643 : || cfun->cfg->max_jumptable_ents > 100)
210 46206 : edge_cache = sbitmap_alloc (last_basic_block_for_fn (cfun));
211 :
212 : /* By nature of the way these get numbered, ENTRY_BLOCK_PTR->next_bb block
213 : is always the entry. */
214 4013372 : if (min == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb)
215 3520578 : make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), min, EDGE_FALLTHRU);
216 :
217 40211099 : FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
218 : {
219 36197727 : rtx_insn *insn;
220 36197727 : enum rtx_code code;
221 36197727 : edge e;
222 36197727 : edge_iterator ei;
223 :
224 36197727 : if (STATE (bb) == BLOCK_ORIGINAL)
225 9218647 : continue;
226 :
227 : /* If we have an edge cache, cache edges going out of BB. */
228 26979080 : if (edge_cache)
229 : {
230 242051 : bitmap_clear (edge_cache);
231 242051 : if (update_p)
232 : {
233 550339 : FOR_EACH_EDGE (e, ei, bb->succs)
234 308288 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
235 285219 : bitmap_set_bit (edge_cache, e->dest->index);
236 : }
237 : }
238 :
239 26979080 : auto label = dyn_cast<rtx_code_label *> (BB_HEAD (bb));
240 12579820 : if (label && LABEL_ALT_ENTRY_P (label))
241 0 : cached_make_edge (NULL, ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, 0);
242 :
243 : /* Examine the last instruction of the block, and discover the
244 : ways we can leave the block. */
245 :
246 26979080 : insn = BB_END (bb);
247 26979080 : code = GET_CODE (insn);
248 :
249 : /* A branch. */
250 26979080 : if (code == JUMP_INSN)
251 : {
252 15249255 : rtx tmp;
253 15249255 : rtx_jump_table_data *table;
254 :
255 : /* Recognize a non-local goto as a branch outside the
256 : current function. */
257 15249255 : if (find_reg_note (insn, REG_NON_LOCAL_GOTO, NULL_RTX))
258 : ;
259 :
260 : /* Recognize a tablejump and do the right thing. */
261 15247795 : else if (tablejump_p (insn, NULL, &table))
262 : {
263 9052 : rtvec vec = table->get_labels ();
264 9052 : int j;
265 :
266 210935 : for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
267 403766 : make_label_edge (edge_cache, bb,
268 201883 : label_ref_label (RTVEC_ELT (vec, j)), 0);
269 :
270 : /* Some targets (eg, ARM) emit a conditional jump that also
271 : contains the out-of-range target. Scan for these and
272 : add an edge if necessary. */
273 9052 : if ((tmp = single_set (insn)) != NULL
274 9052 : && SET_DEST (tmp) == pc_rtx
275 9052 : && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
276 9052 : && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
277 0 : make_label_edge (edge_cache, bb,
278 0 : label_ref_label (XEXP (SET_SRC (tmp), 2)), 0);
279 : }
280 :
281 : /* If this is a computed jump, then mark it as reaching
282 : everything on the forced_labels list. */
283 15238743 : else if (computed_jump_p (insn))
284 : {
285 : rtx_insn *insn;
286 : unsigned int i;
287 15251134 : FOR_EACH_VEC_SAFE_ELT (forced_labels, i, insn)
288 1458 : make_label_edge (edge_cache, bb, insn, EDGE_ABNORMAL);
289 : }
290 :
291 : /* Returns create an exit out. */
292 15238257 : else if (returnjump_p (insn))
293 578764 : cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR_FOR_FN (cfun), 0);
294 :
295 : /* Recognize asm goto and do the right thing. */
296 14659493 : else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
297 : {
298 792 : int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
299 1943 : for (i = 0; i < n; ++i)
300 2302 : make_label_edge (edge_cache, bb,
301 1151 : label_ref_label (ASM_OPERANDS_LABEL (tmp, i)),
302 : 0);
303 : }
304 :
305 : /* Otherwise, we have a plain conditional or unconditional jump. */
306 : else
307 : {
308 14658701 : gcc_assert (JUMP_LABEL (insn));
309 14658701 : make_label_edge (edge_cache, bb, JUMP_LABEL (insn), 0);
310 : }
311 : }
312 :
313 : /* If this is a sibling call insn, then this is in effect a combined call
314 : and return, and so we need an edge to the exit block. No need to
315 : worry about EH edges, since we wouldn't have created the sibling call
316 : in the first place. */
317 26979080 : auto call = dyn_cast<rtx_call_insn *> (insn);
318 2748956 : if (call && SIBLING_CALL_P (call))
319 157923 : cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR_FOR_FN (cfun),
320 : EDGE_SIBCALL | EDGE_ABNORMAL);
321 :
322 : /* If this is a CALL_INSN, then mark it as reaching the active EH
323 : handler for this CALL_INSN. If we're handling non-call
324 : exceptions then any insn can reach any of the active handlers.
325 : Also mark the CALL_INSN as reaching any nonlocal goto handler. */
326 26821157 : else if (call || cfun->can_throw_non_call_exceptions)
327 : {
328 : /* Add any appropriate EH edges. */
329 9857351 : rtl_make_eh_edge (edge_cache, bb, insn);
330 :
331 9857351 : if (call)
332 : {
333 2591033 : if (can_nonlocal_goto (call))
334 : {
335 : /* ??? This could be made smarter: in some cases it's
336 : possible to tell that certain calls will not do a
337 : nonlocal goto. For example, if the nested functions
338 : that do the nonlocal gotos do not have their addresses
339 : taken, then only calls to those functions or to other
340 : nested functions that use them could possibly do
341 : nonlocal gotos. */
342 72788 : for (rtx_insn_list *x = nonlocal_goto_handler_labels;
343 72788 : x;
344 68333 : x = x->next ())
345 68333 : make_label_edge (edge_cache, bb, x->insn (),
346 : EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
347 : }
348 :
349 2591033 : if (flag_tm)
350 : {
351 1524 : rtx note;
352 5004 : for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
353 3480 : if (REG_NOTE_KIND (note) == REG_TM)
354 0 : make_label_edge (edge_cache, bb, XEXP (note, 0),
355 : EDGE_ABNORMAL | EDGE_ABNORMAL_CALL);
356 : }
357 : }
358 : }
359 :
360 : /* Find out if we can drop through to the next block. */
361 26979080 : insn = NEXT_INSN (insn);
362 26979080 : e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
363 26979080 : if (e && e->flags & EDGE_FALLTHRU)
364 26979080 : insn = NULL;
365 :
366 : rtx_note *note;
367 39333983 : while ((note = safe_dyn_cast<rtx_note *> (insn))
368 39337640 : && NOTE_KIND (note) != NOTE_INSN_BASIC_BLOCK)
369 3657 : insn = NEXT_INSN (insn);
370 :
371 26979080 : if (!insn)
372 1916588 : cached_make_edge (edge_cache, bb, EXIT_BLOCK_PTR_FOR_FN (cfun),
373 : EDGE_FALLTHRU);
374 25062492 : else if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
375 : {
376 24438144 : if (insn == BB_HEAD (bb->next_bb))
377 18627322 : cached_make_edge (edge_cache, bb, bb->next_bb, EDGE_FALLTHRU);
378 : }
379 : }
380 :
381 4013372 : if (edge_cache)
382 46206 : sbitmap_free (edge_cache);
383 4013372 : }
384 :
385 : static void
386 171475 : mark_tablejump_edge (rtx_insn *label)
387 : {
388 171475 : basic_block bb;
389 :
390 171475 : gcc_assert (LABEL_P (label));
391 : /* See comment in make_label_edge. */
392 171475 : if (INSN_UID (label) == 0)
393 : return;
394 171475 : bb = BLOCK_FOR_INSN (label);
395 171475 : SET_STATE (bb, FULL_STATE (bb) | BLOCK_USED_BY_TABLEJUMP);
396 : }
397 :
398 : static void
399 7583 : purge_dead_tablejump_edges (basic_block bb, rtx_jump_table_data *table)
400 : {
401 7583 : rtx_insn *insn = BB_END (bb);
402 7583 : rtx tmp;
403 7583 : rtvec vec;
404 7583 : int j;
405 7583 : edge_iterator ei;
406 7583 : edge e;
407 :
408 7583 : vec = table->get_labels ();
409 :
410 179058 : for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
411 171475 : mark_tablejump_edge (label_ref_label (RTVEC_ELT (vec, j)));
412 :
413 : /* Some targets (eg, ARM) emit a conditional jump that also
414 : contains the out-of-range target. Scan for these and
415 : add an edge if necessary. */
416 7583 : if ((tmp = single_set (insn)) != NULL
417 7583 : && SET_DEST (tmp) == pc_rtx
418 7583 : && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
419 7583 : && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF)
420 0 : mark_tablejump_edge (label_ref_label (XEXP (SET_SRC (tmp), 2)));
421 :
422 91697 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
423 : {
424 84114 : if (FULL_STATE (e->dest) & BLOCK_USED_BY_TABLEJUMP)
425 82621 : SET_STATE (e->dest, FULL_STATE (e->dest)
426 : & ~(size_t) BLOCK_USED_BY_TABLEJUMP);
427 1493 : else if (!(e->flags & (EDGE_ABNORMAL | EDGE_EH)))
428 : {
429 1493 : remove_edge (e);
430 1493 : continue;
431 : }
432 82621 : ei_next (&ei);
433 : }
434 7583 : }
435 :
436 : /* Scan basic block BB for possible BB boundaries inside the block
437 : and create new basic blocks in the progress. */
438 :
439 : static void
440 27222155 : find_bb_boundaries (basic_block bb)
441 : {
442 27222155 : basic_block orig_bb = bb;
443 27222155 : rtx_insn *insn = BB_HEAD (bb);
444 27222155 : rtx_insn *end = BB_END (bb), *x;
445 27222155 : rtx_jump_table_data *table;
446 27222155 : rtx_insn *flow_transfer_insn = NULL;
447 27222155 : rtx_insn *debug_insn = NULL;
448 27222155 : edge fallthru = NULL;
449 27222155 : bool skip_purge;
450 27222155 : bool seen_note_after_debug = false;
451 :
452 27222155 : if (insn == end)
453 159092 : return;
454 :
455 27074626 : if (DEBUG_INSN_P (insn) || DEBUG_INSN_P (end))
456 : {
457 : /* Check whether, without debug insns, the insn==end test above
458 : would have caused us to return immediately, and behave the
459 : same way even with debug insns. If we don't do this, debug
460 : insns could cause us to purge dead edges at different times,
461 : which could in turn change the cfg and affect codegen
462 : decisions in subtle but undesirable ways. */
463 395446 : while (insn != end && DEBUG_INSN_P (insn))
464 0 : insn = NEXT_INSN (insn);
465 : rtx_insn *e = end;
466 3178350 : while (insn != e && DEBUG_INSN_P (e))
467 2782904 : e = PREV_INSN (e);
468 395446 : if (insn == e)
469 : {
470 : /* If there are debug insns after a single insn that is a
471 : control flow insn in the block, we'd have left right
472 : away, but we should clean up the debug insns after the
473 : control flow insn, because they can't remain in the same
474 : block. So, do the debug insn cleaning up, but then bail
475 : out without purging dead edges as we would if the debug
476 : insns hadn't been there. */
477 11563 : if (e != end && !DEBUG_INSN_P (e) && control_flow_insn_p (e))
478 : {
479 0 : skip_purge = true;
480 0 : flow_transfer_insn = e;
481 0 : goto clean_up_debug_after_control_flow;
482 : }
483 : return;
484 : }
485 : }
486 :
487 27063063 : if (LABEL_P (insn))
488 12699740 : insn = NEXT_INSN (insn);
489 :
490 : /* Scan insn chain and try to find new basic block boundaries. */
491 319283049 : while (1)
492 : {
493 346346112 : enum rtx_code code = GET_CODE (insn);
494 :
495 346346112 : if (code == DEBUG_INSN)
496 : {
497 85863673 : if (flow_transfer_insn && !debug_insn)
498 : {
499 497 : debug_insn = insn;
500 497 : seen_note_after_debug = false;
501 : }
502 : }
503 : /* In case we've previously seen an insn that effects a control
504 : flow transfer, split the block. */
505 260482439 : else if ((flow_transfer_insn || code == CODE_LABEL)
506 260482439 : && inside_basic_block_p (insn))
507 : {
508 2589382 : rtx_insn *prev = PREV_INSN (insn);
509 :
510 : /* If the first non-debug inside_basic_block_p insn after a control
511 : flow transfer is not a label, split the block before the debug
512 : insn instead of before the non-debug insn, so that the debug
513 : insns are not lost. */
514 2589382 : if (debug_insn && code != CODE_LABEL && code != BARRIER)
515 : {
516 497 : prev = PREV_INSN (debug_insn);
517 497 : if (seen_note_after_debug)
518 : {
519 : /* Though, if there are NOTEs intermixed with DEBUG_INSNs,
520 : move the NOTEs before the DEBUG_INSNs and split after
521 : the last NOTE. */
522 : rtx_insn *first = NULL, *last = NULL;
523 0 : for (x = debug_insn; x != insn; x = NEXT_INSN (x))
524 : {
525 0 : if (NOTE_P (x))
526 : {
527 0 : if (first == NULL)
528 0 : first = x;
529 : last = x;
530 : }
531 : else
532 : {
533 0 : gcc_assert (DEBUG_INSN_P (x));
534 0 : if (first)
535 : {
536 0 : reorder_insns_nobb (first, last, prev);
537 0 : prev = last;
538 0 : first = last = NULL;
539 : }
540 : }
541 : }
542 0 : if (first)
543 : {
544 0 : reorder_insns_nobb (first, last, prev);
545 0 : prev = last;
546 : }
547 : }
548 : }
549 2589382 : fallthru = split_block (bb, prev);
550 2589382 : if (flow_transfer_insn)
551 : {
552 2054135 : BB_END (bb) = flow_transfer_insn;
553 :
554 2054135 : rtx_insn *next;
555 : /* Clean up the bb field for the insns between the blocks. */
556 2054135 : for (x = NEXT_INSN (flow_transfer_insn);
557 2536852 : x != BB_HEAD (fallthru->dest);
558 482717 : x = next)
559 : {
560 482717 : next = NEXT_INSN (x);
561 : /* Debug insns should not be in between basic blocks,
562 : drop them on the floor. */
563 482717 : if (DEBUG_INSN_P (x))
564 0 : delete_insn (x);
565 482717 : else if (!BARRIER_P (x))
566 0 : set_block_for_insn (x, NULL);
567 : }
568 : }
569 :
570 2589382 : bb = fallthru->dest;
571 2589382 : remove_edge (fallthru);
572 : /* BB is unreachable at this point - we need to determine its profile
573 : once edges are built. */
574 2589382 : bb->count = profile_count::uninitialized ();
575 2589382 : flow_transfer_insn = NULL;
576 2589382 : debug_insn = NULL;
577 2589382 : auto label = dyn_cast<rtx_code_label *> (insn);
578 1031692 : if (label && LABEL_ALT_ENTRY_P (label))
579 0 : make_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb, 0);
580 : }
581 257893057 : else if (code == BARRIER)
582 : {
583 : /* __builtin_unreachable () may cause a barrier to be emitted in
584 : the middle of a BB. We need to split it in the same manner as
585 : if the barrier were preceded by a control_flow_insn_p insn. */
586 611151 : if (!flow_transfer_insn)
587 0 : flow_transfer_insn = prev_nonnote_nondebug_insn_bb (insn);
588 : debug_insn = NULL;
589 : }
590 257281906 : else if (debug_insn)
591 : {
592 0 : if (code == NOTE)
593 : seen_note_after_debug = true;
594 : else
595 : /* Jump tables. */
596 257281906 : debug_insn = NULL;
597 : }
598 :
599 346346112 : if (control_flow_insn_p (insn))
600 20516517 : flow_transfer_insn = insn;
601 346346112 : if (insn == end)
602 : break;
603 319283049 : insn = NEXT_INSN (insn);
604 319283049 : }
605 :
606 : /* In case expander replaced normal insn by sequence terminating by
607 : return and barrier, or possibly other sequence not behaving like
608 : ordinary jump, we need to take care and move basic block boundary. */
609 27063063 : if (flow_transfer_insn && flow_transfer_insn != end)
610 : {
611 : skip_purge = false;
612 :
613 128434 : clean_up_debug_after_control_flow:
614 128434 : BB_END (bb) = flow_transfer_insn;
615 :
616 : /* Clean up the bb field for the insns that do not belong to BB. */
617 128434 : rtx_insn *next;
618 128434 : for (x = NEXT_INSN (flow_transfer_insn); ; x = next)
619 : {
620 128434 : next = NEXT_INSN (x);
621 : /* Debug insns should not be in between basic blocks,
622 : drop them on the floor. */
623 128434 : if (DEBUG_INSN_P (x))
624 0 : delete_insn (x);
625 128434 : else if (!BARRIER_P (x))
626 0 : set_block_for_insn (x, NULL);
627 128434 : if (x == end)
628 : break;
629 : }
630 :
631 128434 : if (skip_purge)
632 : return;
633 : }
634 :
635 : /* We've possibly replaced the conditional jump by conditional jump
636 : followed by cleanup at fallthru edge, so the outgoing edges may
637 : be dead. */
638 27063063 : purge_dead_edges (bb);
639 :
640 : /* purge_dead_edges doesn't handle tablejump's, but if we have split the
641 : basic block, we might need to kill some edges. */
642 27063063 : if (bb != orig_bb && tablejump_p (BB_END (bb), NULL, &table))
643 7583 : purge_dead_tablejump_edges (bb, table);
644 : }
645 :
646 : /* Assume that frequency of basic block B is known. Compute frequencies
647 : and probabilities of outgoing edges. */
648 :
649 : static void
650 3240463 : compute_outgoing_frequencies (basic_block b)
651 : {
652 3240463 : edge e, f;
653 3240463 : edge_iterator ei;
654 :
655 3240463 : if (EDGE_COUNT (b->succs) == 2)
656 : {
657 1736517 : rtx note = find_reg_note (BB_END (b), REG_BR_PROB, NULL);
658 1736517 : int probability;
659 :
660 1736517 : if (note)
661 : {
662 1130605 : probability = XINT (note, 0);
663 1130605 : e = BRANCH_EDGE (b);
664 1130605 : e->probability
665 1130605 : = profile_probability::from_reg_br_prob_note (probability);
666 1130605 : f = FALLTHRU_EDGE (b);
667 1130605 : f->probability = e->probability.invert ();
668 2623376 : return;
669 : }
670 : else
671 : {
672 605912 : guess_outgoing_edge_probabilities (b);
673 : }
674 : }
675 1503946 : else if (single_succ_p (b))
676 : {
677 1492771 : e = single_succ_edge (b);
678 1492771 : e->probability = profile_probability::always ();
679 1492771 : return;
680 : }
681 : else
682 : {
683 : /* We rely on BBs with more than two successors to have sane probabilities
684 : and do not guess them here. For BBs terminated by switch statements
685 : expanded to jump-table jump, we have done the right thing during
686 : expansion. For EH edges, we still guess the probabilities here. */
687 11175 : bool complex_edge = false;
688 93855 : FOR_EACH_EDGE (e, ei, b->succs)
689 83766 : if (e->flags & EDGE_COMPLEX)
690 : {
691 : complex_edge = true;
692 : break;
693 : }
694 11175 : if (complex_edge)
695 1086 : guess_outgoing_edge_probabilities (b);
696 : }
697 : }
698 :
699 : /* Update the profile information for BB, which was created by splitting
700 : an RTL block that had a non-final jump. */
701 :
702 : static void
703 2195603 : update_profile_for_new_sub_basic_block (basic_block bb)
704 : {
705 2195603 : edge e;
706 2195603 : edge_iterator ei;
707 :
708 2195603 : bool initialized_src = false, uninitialized_src = false;
709 2195603 : bb->count = profile_count::zero ();
710 5016429 : FOR_EACH_EDGE (e, ei, bb->preds)
711 : {
712 2820826 : if (e->count ().initialized_p ())
713 : {
714 2788182 : bb->count += e->count ();
715 2788182 : initialized_src = true;
716 : }
717 : else
718 : uninitialized_src = true;
719 : }
720 : /* When some edges are missing with read profile, this is
721 : most likely because RTL expansion introduced loop.
722 : When profile is guessed we may have BB that is reachable
723 : from unlikely path as well as from normal path.
724 :
725 : TODO: We should handle loops created during BB expansion
726 : correctly here. For now we assume all those loop to cycle
727 : precisely once. */
728 2195603 : if (!initialized_src
729 2180350 : || (uninitialized_src
730 28405 : && profile_status_for_fn (cfun) < PROFILE_GUESSED))
731 15253 : bb->count = profile_count::uninitialized ();
732 :
733 2195603 : compute_outgoing_frequencies (bb);
734 2195603 : }
735 :
736 : /* Assume that some pass has inserted labels or control flow
737 : instructions within a basic block. Split basic blocks as needed
738 : and create edges. */
739 :
740 : void
741 3753382 : find_many_sub_basic_blocks (sbitmap blocks)
742 : {
743 3753382 : basic_block bb, min, max;
744 3753382 : bool found = false;
745 3753382 : auto_vec<unsigned int> n_succs;
746 3753382 : n_succs.safe_grow_cleared (last_basic_block_for_fn (cfun), true);
747 :
748 60112655 : FOR_EACH_BB_FN (bb, cfun)
749 88588838 : SET_STATE (bb,
750 : bitmap_bit_p (blocks, bb->index) ? BLOCK_TO_SPLIT : BLOCK_ORIGINAL);
751 :
752 62182045 : FOR_EACH_BB_FN (bb, cfun)
753 58428663 : if (STATE (bb) == BLOCK_TO_SPLIT)
754 : {
755 24129708 : int n = last_basic_block_for_fn (cfun);
756 24129708 : unsigned int ns = EDGE_COUNT (bb->succs);
757 :
758 24129708 : find_bb_boundaries (bb);
759 47123194 : if (n == last_basic_block_for_fn (cfun) && ns == EDGE_COUNT (bb->succs))
760 23204222 : n_succs[bb->index] = EDGE_COUNT (bb->succs);
761 : }
762 :
763 8600295 : FOR_EACH_BB_FN (bb, cfun)
764 8600295 : if (STATE (bb) != BLOCK_ORIGINAL)
765 : {
766 : found = true;
767 : break;
768 : }
769 :
770 3753382 : if (!found)
771 0 : return;
772 :
773 : min = max = bb;
774 57335132 : for (; bb != EXIT_BLOCK_PTR_FOR_FN (cfun); bb = bb->next_bb)
775 53581750 : if (STATE (bb) != BLOCK_ORIGINAL)
776 26199098 : max = bb;
777 :
778 : /* Now re-scan and wire in all edges. This expect simple (conditional)
779 : jumps at the end of each new basic blocks. */
780 3753382 : make_edges (min, max, 1);
781 :
782 : /* Update branch probabilities. Expect only (un)conditional jumps
783 : to be created with only the forward edges. */
784 3753382 : if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
785 31017820 : FOR_BB_BETWEEN (bb, min, max->next_bb, next_bb)
786 : {
787 28386407 : if (STATE (bb) == BLOCK_ORIGINAL)
788 8069714 : continue;
789 20316693 : if (STATE (bb) == BLOCK_NEW)
790 : {
791 1706341 : update_profile_for_new_sub_basic_block (bb);
792 1706341 : continue;
793 : }
794 : /* If nothing changed, there is no need to create new BBs. */
795 37201387 : if (EDGE_COUNT (bb->succs) == n_succs[bb->index])
796 : {
797 : /* In rare occasions RTL expansion might have mistakely assigned
798 : a probabilities different from what is in CFG. This happens
799 : when we try to split branch to two but optimize out the
800 : second branch during the way. See PR81030. */
801 10372714 : if (JUMP_P (BB_END (bb)) && any_condjump_p (BB_END (bb))
802 24566222 : && EDGE_COUNT (bb->succs) >= 2)
803 6756103 : update_br_prob_note (bb);
804 17810119 : continue;
805 : }
806 800233 : compute_outgoing_frequencies (bb);
807 : }
808 :
809 62182045 : FOR_EACH_BB_FN (bb, cfun)
810 58428663 : SET_STATE (bb, 0);
811 3753382 : }
812 :
813 : /* Like find_many_sub_basic_blocks, but look only within BB. */
814 :
815 : void
816 3092447 : find_sub_basic_blocks (basic_block bb)
817 : {
818 3092447 : basic_block end_bb = bb->next_bb;
819 3092447 : find_bb_boundaries (bb);
820 3092447 : if (bb->next_bb == end_bb)
821 : return;
822 :
823 : /* Re-scan and wire in all edges. This expects simple (conditional)
824 : jumps at the end of each new basic blocks. */
825 259990 : make_edges (bb, end_bb->prev_bb, 1);
826 :
827 : /* Update branch probabilities. Expect only (un)conditional jumps
828 : to be created with only the forward edges. */
829 259990 : if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
830 : {
831 244627 : compute_outgoing_frequencies (bb);
832 733889 : for (bb = bb->next_bb; bb != end_bb; bb = bb->next_bb)
833 489262 : update_profile_for_new_sub_basic_block (bb);
834 : }
835 : }
|