Line data Source code
1 : /* Control flow graph manipulation 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 : /* This file contains low level functions to manipulate the CFG and analyze it
21 : that are aware of the RTL intermediate language.
22 :
23 : Available functionality:
24 : - Basic CFG/RTL manipulation API documented in cfghooks.h
25 : - CFG-aware instruction chain manipulation
26 : delete_insn, delete_insn_chain
27 : - Edge splitting and committing to edges
28 : insert_insn_on_edge, prepend_insn_to_edge, commit_edge_insertions
29 : - CFG updating after insn simplification
30 : purge_dead_edges, purge_all_dead_edges
31 : - CFG fixing after coarse manipulation
32 : fixup_abnormal_edges
33 :
34 : Functions not supposed for generic use:
35 : - Infrastructure to determine quickly basic block for insn
36 : compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 : - Edge redirection with updating and optimizing of insn chain
38 : block_label, tidy_fallthru_edge, force_nonfallthru */
39 :
40 : #include "config.h"
41 : #include "system.h"
42 : #include "coretypes.h"
43 : #include "backend.h"
44 : #include "target.h"
45 : #include "rtl.h"
46 : #include "tree.h"
47 : #include "cfghooks.h"
48 : #include "df.h"
49 : #include "insn-config.h"
50 : #include "memmodel.h"
51 : #include "emit-rtl.h"
52 : #include "cfgrtl.h"
53 : #include "cfganal.h"
54 : #include "cfgbuild.h"
55 : #include "cfgcleanup.h"
56 : #include "bb-reorder.h"
57 : #include "rtl-error.h"
58 : #include "insn-attr.h"
59 : #include "dojump.h"
60 : #include "expr.h"
61 : #include "cfgloop.h"
62 : #include "tree-pass.h"
63 : #include "print-rtl.h"
64 : #include "rtl-iter.h"
65 : #include "profile.h"
66 : #include "sreal.h"
67 :
68 : /* Disable warnings about missing quoting in GCC diagnostics. */
69 : #if __GNUC__ >= 10
70 : # pragma GCC diagnostic push
71 : # pragma GCC diagnostic ignored "-Wformat-diag"
72 : #endif
73 :
74 : /* Holds the interesting leading and trailing notes for the function.
75 : Only applicable if the CFG is in cfglayout mode. */
76 : static GTY(()) rtx_insn *cfg_layout_function_footer;
77 : static GTY(()) rtx_insn *cfg_layout_function_header;
78 :
79 : static rtx_insn *skip_insns_after_block (basic_block);
80 : static void record_effective_endpoints (void);
81 : static void fixup_reorder_chain (void);
82 :
83 : void verify_insn_chain (void);
84 : static void fixup_fallthru_exit_predecessor (void);
85 : static bool can_delete_note_p (const rtx_note *);
86 : static bool can_delete_label_p (const rtx_code_label *);
87 : static basic_block rtl_split_edge (edge);
88 : static bool rtl_move_block_after (basic_block, basic_block);
89 : static bool rtl_verify_flow_info (void);
90 : static basic_block cfg_layout_split_block (basic_block, void *);
91 : static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
92 : static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
93 : static void cfg_layout_delete_block (basic_block);
94 : static void rtl_delete_block (basic_block);
95 : static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
96 : static edge rtl_redirect_edge_and_branch (edge, basic_block);
97 : static basic_block rtl_split_block (basic_block, void *);
98 : static void rtl_dump_bb (FILE *, basic_block, int, dump_flags_t);
99 : static bool rtl_verify_flow_info_1 (void);
100 : static void rtl_make_forwarder_block (edge);
101 : static bool rtl_bb_info_initialized_p (basic_block bb);
102 :
103 : /* Return true if NOTE is not one of the ones that must be kept paired,
104 : so that we may simply delete it. */
105 :
106 : static bool
107 10953878 : can_delete_note_p (const rtx_note *note)
108 : {
109 0 : switch (NOTE_KIND (note))
110 : {
111 : case NOTE_INSN_DELETED:
112 : case NOTE_INSN_BASIC_BLOCK:
113 : case NOTE_INSN_EPILOGUE_BEG:
114 : return true;
115 :
116 0 : default:
117 0 : return false;
118 : }
119 : }
120 :
121 : /* True if a given label can be deleted. */
122 :
123 : static bool
124 7840295 : can_delete_label_p (const rtx_code_label *label)
125 : {
126 7840295 : return (!LABEL_PRESERVE_P (label)
127 : /* User declared labels must be preserved. */
128 7831424 : && LABEL_NAME (label) == 0
129 7840295 : && !vec_safe_contains<rtx_insn *> (forced_labels,
130 7783847 : const_cast<rtx_code_label *> (label)));
131 : }
132 :
133 : /* Delete INSN by patching it out. */
134 :
135 : void
136 133819105 : delete_insn (rtx_insn *insn)
137 : {
138 133819105 : rtx note;
139 133819105 : bool really_delete = true;
140 :
141 133819105 : if (rtx_code_label *label = dyn_cast<rtx_code_label *> (insn))
142 : {
143 : /* Some labels can't be directly removed from the INSN chain, as they
144 : might be references via variables, constant pool etc.
145 : Convert them to the special NOTE_INSN_DELETED_LABEL note. */
146 7840295 : if (! can_delete_label_p (label))
147 : {
148 56448 : const char *name = LABEL_NAME (label);
149 56448 : basic_block bb = BLOCK_FOR_INSN (insn);
150 56448 : rtx_insn *bb_note = NEXT_INSN (insn);
151 :
152 56448 : really_delete = false;
153 56448 : PUT_CODE (insn, NOTE);
154 56448 : NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
155 56448 : NOTE_DELETED_LABEL_NAME (insn) = name;
156 :
157 : /* If the note following the label starts a basic block, and the
158 : label is a member of the same basic block, interchange the two. */
159 56448 : if (bb_note != NULL_RTX
160 7854372 : && NOTE_INSN_BASIC_BLOCK_P (bb_note)
161 14077 : && bb != NULL
162 70525 : && bb == BLOCK_FOR_INSN (bb_note))
163 : {
164 11676 : reorder_insns_nobb (insn, insn, bb_note);
165 11676 : BB_HEAD (bb) = bb_note;
166 11676 : if (BB_END (bb) == bb_note)
167 1544 : BB_END (bb) = insn;
168 : }
169 : }
170 :
171 7840295 : remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels);
172 : }
173 :
174 7840295 : if (really_delete)
175 : {
176 : /* If this insn has already been deleted, something is very wrong. */
177 133762657 : gcc_assert (!insn->deleted ());
178 133762657 : if (INSN_P (insn))
179 99043458 : df_insn_delete (insn);
180 133762657 : remove_insn (insn);
181 133762657 : insn->set_deleted ();
182 : }
183 :
184 : /* If deleting a jump, decrement the use count of the label. Deleting
185 : the label itself should happen in the normal course of block merging. */
186 133819105 : if (JUMP_P (insn))
187 : {
188 6957571 : if (JUMP_LABEL (insn)
189 6957343 : && LABEL_P (JUMP_LABEL (insn)))
190 6947688 : LABEL_NUSES (JUMP_LABEL (insn))--;
191 :
192 : /* If there are more targets, remove them too. */
193 : while ((note
194 13915142 : = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
195 6957571 : && LABEL_P (XEXP (note, 0)))
196 : {
197 0 : LABEL_NUSES (XEXP (note, 0))--;
198 0 : remove_note (insn, note);
199 : }
200 : }
201 :
202 : /* Also if deleting any insn that references a label as an operand. */
203 267656594 : while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
204 133828297 : && LABEL_P (XEXP (note, 0)))
205 : {
206 9192 : LABEL_NUSES (XEXP (note, 0))--;
207 9192 : remove_note (insn, note);
208 : }
209 :
210 133819105 : if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
211 : {
212 192 : rtvec vec = table->get_labels ();
213 192 : int len = GET_NUM_ELEM (vec);
214 192 : int i;
215 :
216 2300 : for (i = 0; i < len; i++)
217 : {
218 2108 : rtx_insn *label = label_ref_label (RTVEC_ELT (vec, i));
219 :
220 : /* When deleting code in bulk (e.g. removing many unreachable
221 : blocks) we can delete a label that's a target of the vector
222 : before deleting the vector itself. */
223 2108 : if (!NOTE_P (label))
224 2108 : LABEL_NUSES (label)--;
225 : }
226 : }
227 133819105 : }
228 :
229 : /* Like delete_insn but also purge dead edges from BB.
230 : Return true if any edges are eliminated. */
231 :
232 : bool
233 13000353 : delete_insn_and_edges (rtx_insn *insn)
234 : {
235 13000353 : bool purge = false;
236 :
237 13000353 : if (NONDEBUG_INSN_P (insn) && BLOCK_FOR_INSN (insn))
238 : {
239 12551176 : basic_block bb = BLOCK_FOR_INSN (insn);
240 12551176 : if (BB_END (bb) == insn)
241 : purge = true;
242 11893779 : else if (DEBUG_INSN_P (BB_END (bb)))
243 1031450 : for (rtx_insn *dinsn = NEXT_INSN (insn);
244 1031450 : DEBUG_INSN_P (dinsn); dinsn = NEXT_INSN (dinsn))
245 674798 : if (BB_END (bb) == dinsn)
246 : {
247 : purge = true;
248 : break;
249 : }
250 : }
251 13000353 : delete_insn (insn);
252 13000353 : if (purge)
253 701995 : return purge_dead_edges (BLOCK_FOR_INSN (insn));
254 : return false;
255 : }
256 :
257 : /* Return true if INSN is a shared jump table or its adjacent label. */
258 :
259 : static bool
260 31820185 : shared_jump_table_component_p (rtx_insn *insn)
261 : {
262 31820185 : rtx_insn *table = insn;
263 31820185 : if (LABEL_P (insn))
264 5347238 : table = NEXT_INSN (insn);
265 :
266 31271716 : return (table && JUMP_TABLE_DATA_P (table)
267 5347430 : && JUMP_TABLE_SHARED_P (PATTERN (table)));
268 : }
269 :
270 : /* Return true if the half-open range from FIRST to LAST contains part of a
271 : shared jump table. */
272 :
273 : static bool
274 17681792 : shared_jump_table_between_p (rtx_insn *first, rtx_insn *last)
275 : {
276 18603288 : for (rtx_insn *insn = first; insn != last; insn = NEXT_INSN (insn))
277 921496 : if (shared_jump_table_component_p (insn))
278 : return true;
279 : return false;
280 : }
281 :
282 : /* Return the shared jump table that BB hosts: BB ends in a jump through the
283 : table and the table's label follows BB_END, possibly after barriers.
284 : Return NULL otherwise. */
285 :
286 : static rtx_jump_table_data *
287 6963493 : hosted_shared_table (basic_block bb)
288 : {
289 6963493 : rtx_insn *label;
290 6963493 : rtx_jump_table_data *table;
291 6963493 : if (!shared_tablejump_p (BB_END (bb), &label, &table))
292 : return NULL;
293 :
294 337 : rtx_insn *insn = next_nonnote_nondebug_insn_bb (BB_END (bb));
295 1066 : while (insn && BARRIER_P (insn))
296 392 : insn = next_nonnote_nondebug_insn_bb (insn);
297 337 : return insn == label ? table : NULL;
298 : }
299 :
300 : /* Return a block other than BB that ends in a jump through the table whose
301 : label is LABEL, or NULL if there is none. */
302 :
303 : static basic_block
304 85 : other_table_user (basic_block bb, rtx_insn *label)
305 : {
306 85 : basic_block other;
307 660 : FOR_EACH_BB_FN (other, cfun)
308 660 : if (other != bb
309 654 : && JUMP_P (BB_END (other))
310 543 : && JUMP_LABEL (BB_END (other)) == label)
311 : return other;
312 : return NULL;
313 : }
314 :
315 : /* Move the jump table TABLE, with its label, right after BB_END (BB), which
316 : is a jump through it. */
317 :
318 : static void
319 85 : move_table_after (rtx_jump_table_data *table, basic_block bb)
320 : {
321 85 : rtx_insn *label = PREV_INSN (table);
322 85 : gcc_checking_assert (LABEL_P (label) && JUMP_LABEL (BB_END (bb)) == label);
323 :
324 85 : if (current_ir_type () == IR_RTL_CFGLAYOUT)
325 : {
326 : /* The insns that follow BB are in its footer, outside the chain. */
327 0 : unlink_insn_chain (label, table);
328 0 : SET_NEXT_INSN (table) = BB_FOOTER (bb);
329 0 : if (BB_FOOTER (bb))
330 0 : SET_PREV_INSN (BB_FOOTER (bb)) = table;
331 0 : BB_FOOTER (bb) = label;
332 : }
333 : else
334 85 : reorder_insns_nobb (label, table, BB_END (bb));
335 85 : }
336 :
337 : /* Unlink a chain of insns between START and FINISH, leaving notes
338 : that must be paired. If CLEAR_BB is true, we set bb field for
339 : insns that cannot be removed to NULL. */
340 :
341 : void
342 17962242 : delete_insn_chain (rtx_insn *start, rtx_insn *finish, bool clear_bb)
343 : {
344 : /* Unchain the insns one by one. It would be quicker to delete all of these
345 : with a single unchaining, rather than one at a time, but we need to keep
346 : the NOTE's. */
347 17962242 : rtx_insn *current = finish;
348 30866050 : while (1)
349 : {
350 30866050 : rtx_insn *prev = PREV_INSN (current);
351 30866050 : gcc_checking_assert (!shared_jump_table_component_p (current));
352 30866050 : if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
353 : ;
354 : else
355 30859986 : delete_insn (current);
356 :
357 30866050 : if (clear_bb && !current->deleted ())
358 49278 : set_block_for_insn (current, NULL);
359 :
360 30866050 : if (current == start)
361 : break;
362 : current = prev;
363 : }
364 17962242 : }
365 :
366 : /* Create a new basic block consisting of the instructions between HEAD and END
367 : inclusive. This function is designed to allow fast BB construction - reuses
368 : the note and basic block struct in BB_NOTE, if any and do not grow
369 : BASIC_BLOCK chain and should be used directly only by CFG construction code.
370 : END can be NULL in to create new empty basic block before HEAD. Both END
371 : and HEAD can be NULL to create basic block at the end of INSN chain.
372 : AFTER is the basic block we should be put after. */
373 :
374 : basic_block
375 13319940 : create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
376 : basic_block after)
377 : {
378 13319940 : basic_block bb;
379 :
380 13319940 : if (bb_note
381 0 : && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
382 13319940 : && bb->aux == NULL)
383 : {
384 : /* If we found an existing note, thread it back onto the chain. */
385 :
386 0 : rtx_insn *after;
387 :
388 0 : if (LABEL_P (head))
389 : after = head;
390 : else
391 : {
392 0 : after = PREV_INSN (head);
393 0 : head = bb_note;
394 : }
395 :
396 0 : if (after != bb_note && NEXT_INSN (after) != bb_note)
397 0 : reorder_insns_nobb (bb_note, bb_note, after);
398 : }
399 : else
400 : {
401 : /* Otherwise we must create a note and a basic block structure. */
402 :
403 13319940 : bb = alloc_block ();
404 :
405 13319940 : init_rtl_bb_info (bb);
406 13319940 : if (!head && !end)
407 475761 : head = end = bb_note
408 475761 : = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
409 12844179 : else if (LABEL_P (head) && end)
410 : {
411 2777861 : bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
412 2777861 : if (head == end)
413 949833 : end = bb_note;
414 : }
415 : else
416 : {
417 10066318 : bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
418 10066318 : head = bb_note;
419 10066318 : if (!end)
420 5587811 : end = head;
421 : }
422 :
423 13319940 : NOTE_BASIC_BLOCK (bb_note) = bb;
424 : }
425 :
426 : /* Always include the bb note in the block. */
427 13319940 : if (NEXT_INSN (end) == bb_note)
428 0 : end = bb_note;
429 :
430 13319940 : BB_HEAD (bb) = head;
431 13319940 : BB_END (bb) = end;
432 13319940 : bb->index = last_basic_block_for_fn (cfun)++;
433 13319940 : bb->flags = BB_NEW | BB_RTL;
434 13319940 : link_block (bb, after);
435 13319940 : SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
436 13319940 : df_bb_refs_record (bb->index, false);
437 13319940 : update_bb_for_insn (bb);
438 13319940 : BB_SET_PARTITION (bb, BB_UNPARTITIONED);
439 :
440 : /* Tag the block so that we know it has been used when considering
441 : other basic block notes. */
442 13319940 : bb->aux = bb;
443 :
444 13319940 : return bb;
445 : }
446 :
447 : /* Create new basic block consisting of instructions in between HEAD and END
448 : and place it to the BB chain after block AFTER. END can be NULL to
449 : create a new empty basic block before HEAD. Both END and HEAD can be
450 : NULL to create basic block at the end of INSN chain. */
451 :
452 : static basic_block
453 13319940 : rtl_create_basic_block (void *headp, void *endp, basic_block after)
454 : {
455 13319940 : rtx_insn *head = (rtx_insn *) headp;
456 13319940 : rtx_insn *end = (rtx_insn *) endp;
457 13319940 : basic_block bb;
458 :
459 : /* Grow the basic block array if needed. */
460 13319940 : if ((size_t) last_basic_block_for_fn (cfun)
461 13319940 : >= basic_block_info_for_fn (cfun)->length ())
462 899836 : vec_safe_grow_cleared (basic_block_info_for_fn (cfun),
463 899836 : last_basic_block_for_fn (cfun) + 1);
464 :
465 13319940 : n_basic_blocks_for_fn (cfun)++;
466 :
467 13319940 : bb = create_basic_block_structure (head, end, NULL, after);
468 13319940 : bb->aux = NULL;
469 13319940 : return bb;
470 : }
471 :
472 : static basic_block
473 4340130 : cfg_layout_create_basic_block (void *head, void *end, basic_block after)
474 : {
475 4340130 : basic_block newbb = rtl_create_basic_block (head, end, after);
476 :
477 4340130 : return newbb;
478 : }
479 :
480 : /* Delete the insns in a (non-live) block. We physically delete every
481 : non-deleted-note insn, and update the flow graph appropriately.
482 :
483 : Return nonzero if we deleted an exception handler. */
484 :
485 : /* ??? Preserving all such notes strikes me as wrong. It would be nice
486 : to post-process the stream to remove empty blocks, loops, ranges, etc. */
487 :
488 : static void
489 6963282 : rtl_delete_block (basic_block b)
490 : {
491 6963282 : rtx_insn *insn, *end;
492 :
493 : /* If the head of this block is a CODE_LABEL, then it might be the
494 : label for an exception handler which can't be reached. We need
495 : to remove the label from the exception_handler_label list. */
496 6963282 : insn = BB_HEAD (b);
497 :
498 6963282 : end = get_last_bb_insn (b);
499 :
500 : /* A shared table that B hosts has to go on following one of the jumps
501 : through it. If B has the last such jump, leave the dead table to
502 : delete_dead_jumptables. */
503 6963282 : if (rtx_jump_table_data *table = hosted_shared_table (b))
504 : {
505 85 : if (basic_block user = other_table_user (b, PREV_INSN (table)))
506 : {
507 85 : move_table_after (table, user);
508 85 : end = get_last_bb_insn (b);
509 : }
510 : else
511 0 : end = PREV_INSN (PREV_INSN (table));
512 : }
513 :
514 : /* Selectively delete the entire chain. */
515 6963282 : BB_HEAD (b) = NULL;
516 6963282 : delete_insn_chain (insn, end, true);
517 :
518 :
519 6963282 : if (dump_file)
520 767 : fprintf (dump_file, "deleting block %d\n", b->index);
521 6963282 : df_bb_delete (b->index);
522 6963282 : }
523 :
524 : /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
525 :
526 : void
527 1517186 : compute_bb_for_insn (void)
528 : {
529 1517186 : basic_block bb;
530 :
531 16066654 : FOR_EACH_BB_FN (bb, cfun)
532 : {
533 14549468 : rtx_insn *end = BB_END (bb);
534 14549468 : rtx_insn *insn;
535 :
536 180824194 : for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
537 : {
538 180824194 : BLOCK_FOR_INSN (insn) = bb;
539 180824194 : if (insn == end)
540 : break;
541 : }
542 : }
543 1517186 : }
544 :
545 : /* Release the basic_block_for_insn array. */
546 :
547 : void
548 3035072 : free_bb_for_insn (void)
549 : {
550 3035072 : rtx_insn *insn;
551 217910122 : for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
552 214875050 : if (!BARRIER_P (insn))
553 209999568 : BLOCK_FOR_INSN (insn) = NULL;
554 3035072 : }
555 :
556 : namespace {
557 :
558 : const pass_data pass_data_free_cfg =
559 : {
560 : RTL_PASS, /* type */
561 : "*free_cfg", /* name */
562 : OPTGROUP_NONE, /* optinfo_flags */
563 : TV_NONE, /* tv_id */
564 : 0, /* properties_required */
565 : 0, /* properties_provided */
566 : PROP_cfg, /* properties_destroyed */
567 : 0, /* todo_flags_start */
568 : 0, /* todo_flags_finish */
569 : };
570 :
571 : class pass_free_cfg : public rtl_opt_pass
572 : {
573 : public:
574 297180 : pass_free_cfg (gcc::context *ctxt)
575 594360 : : rtl_opt_pass (pass_data_free_cfg, ctxt)
576 : {}
577 :
578 : /* opt_pass methods: */
579 : unsigned int execute (function *) final override;
580 :
581 : }; // class pass_free_cfg
582 :
583 : unsigned int
584 1517128 : pass_free_cfg::execute (function *)
585 : {
586 : /* The resource.cc machinery uses DF but the CFG isn't guaranteed to be
587 : valid at that point so it would be too late to call df_analyze. */
588 1517128 : if (DELAY_SLOTS && optimize > 0 && flag_delayed_branch)
589 : {
590 : df_note_add_problem ();
591 : df_analyze ();
592 : }
593 :
594 1517128 : if (crtl->has_bb_partition)
595 65368 : insert_section_boundary_note ();
596 :
597 1517128 : free_bb_for_insn ();
598 1517128 : return 0;
599 : }
600 :
601 : } // anon namespace
602 :
603 : rtl_opt_pass *
604 297180 : make_pass_free_cfg (gcc::context *ctxt)
605 : {
606 297180 : return new pass_free_cfg (ctxt);
607 : }
608 :
609 : /* Return RTX to emit after when we want to emit code on the entry of function. */
610 : rtx_insn *
611 7882 : entry_of_function (void)
612 : {
613 7882 : return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
614 7882 : BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
615 : }
616 :
617 : /* Emit INSN at the entry point of the function, ensuring that it is only
618 : executed once per function. */
619 : void
620 0 : emit_insn_at_entry (rtx insn)
621 : {
622 0 : edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
623 0 : edge e = ei_safe_edge (ei);
624 0 : gcc_assert (e->flags & EDGE_FALLTHRU);
625 :
626 0 : insert_insn_on_edge (insn, e);
627 0 : commit_edge_insertions ();
628 0 : }
629 :
630 : /* Update BLOCK_FOR_INSN of insns between BEGIN and END
631 : (or BARRIER if found) and notify df of the bb change.
632 : The insn chain range is inclusive
633 : (i.e. both BEGIN and END will be updated. */
634 :
635 : void
636 33935690 : update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
637 : {
638 33935690 : rtx_insn *insn;
639 :
640 33935690 : end = NEXT_INSN (end);
641 362682676 : for (insn = begin; insn != end; insn = NEXT_INSN (insn))
642 294811296 : if (!BARRIER_P (insn))
643 292225614 : df_insn_change_bb (insn, bb);
644 33935690 : }
645 :
646 : /* Update BLOCK_FOR_INSN of insns in BB to BB,
647 : and notify df of the change. */
648 :
649 : void
650 16979728 : update_bb_for_insn (basic_block bb)
651 : {
652 16979728 : update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
653 16979728 : }
654 :
655 :
656 : /* Return true if adding or removing instances of INSN might affect the
657 : semantics of the RTL. */
658 :
659 : static bool
660 343890440 : flow_active_insn_p (const rtx_insn *insn)
661 : {
662 343890440 : if (active_insn_p (insn))
663 : return true;
664 :
665 : /* We cannot add new clobbers to a path without first proving that
666 : the clobbered thing is dead.
667 :
668 : For example:
669 :
670 : (code_label L1)
671 : (clobber X)
672 : (set (pc) (label_ref L2))
673 :
674 : is a forwarder block in the sense that a jump to L1 can be replaced
675 : with a jump to L2, although perhaps with some loss of dataflow precision.
676 : However, any attempt to merge a jump to L1 with a jump to L2 would be an
677 : asymmetric operation, in that the merged code must jump to L2 rather than
678 : to L1. Our current definition of "forwarder block" does not allow for
679 : this distinction and so we need to take a conservatively correct
680 : approach. */
681 215553536 : if (GET_CODE (PATTERN (insn)) == CLOBBER)
682 : return true;
683 :
684 : /* Keep a USE of the function return value, otherwise the USE is dropped and
685 : we could fail to thread a jump if USE appears on some paths and not on
686 : others, see PR90257. */
687 215489221 : if (GET_CODE (PATTERN (insn)) == USE
688 588308 : && REG_P (XEXP (PATTERN (insn), 0))
689 216077529 : && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
690 582745 : return true;
691 :
692 : return false;
693 : }
694 :
695 : /* Return true if the block has no effect and only forwards control flow to
696 : its single destination. */
697 :
698 : bool
699 319591317 : contains_no_active_insn_p (const_basic_block bb)
700 : {
701 319591317 : rtx_insn *insn;
702 :
703 319591317 : if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
704 319591317 : || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
705 318335751 : || !single_succ_p (bb)
706 467678186 : || (single_succ_edge (bb)->flags & EDGE_FAKE) != 0)
707 : return false;
708 :
709 580351872 : for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
710 533658367 : if (INSN_P (insn) && flow_active_insn_p (insn))
711 : return false;
712 :
713 46693505 : return (!INSN_P (insn)
714 35903187 : || (JUMP_P (insn) && simplejump_p (insn))
715 75290710 : || !flow_active_insn_p (insn));
716 : }
717 :
718 : /* Likewise, but protect loop latches, headers and preheaders. */
719 : /* FIXME: Make this a cfg hook. */
720 :
721 : bool
722 319591317 : forwarder_block_p (const_basic_block bb)
723 : {
724 319591317 : if (!contains_no_active_insn_p (bb))
725 : return false;
726 :
727 : /* Protect loop latches, headers and preheaders. */
728 18436464 : if (current_loops)
729 : {
730 9242659 : basic_block dest;
731 9242659 : if (bb->loop_father->header == bb)
732 : return false;
733 9142342 : dest = EDGE_SUCC (bb, 0)->dest;
734 9142342 : if (dest->loop_father->header == dest)
735 1155375 : return false;
736 : }
737 :
738 : return true;
739 : }
740 :
741 : /* Return nonzero if we can reach target from src by falling through. */
742 : /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
743 :
744 : bool
745 45107848 : can_fallthru (basic_block src, basic_block target)
746 : {
747 45107848 : rtx_insn *insn = BB_END (src);
748 45107848 : rtx_insn *insn2;
749 45107848 : edge e;
750 45107848 : edge_iterator ei;
751 :
752 45107848 : if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
753 : return true;
754 43696222 : if (src->next_bb != target)
755 : return false;
756 :
757 17681728 : if (shared_jump_table_between_p (NEXT_INSN (insn), BB_HEAD (target)))
758 : return false;
759 :
760 : /* ??? Later we may add code to move jump tables offline. */
761 17681728 : if (tablejump_p (insn, NULL, NULL))
762 : return false;
763 :
764 48055152 : FOR_EACH_EDGE (e, ei, src->succs)
765 30373424 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
766 0 : && e->flags & EDGE_FALLTHRU)
767 : return false;
768 :
769 17681728 : insn2 = BB_HEAD (target);
770 17681728 : if (!active_insn_p (insn2))
771 17681728 : insn2 = next_active_insn (insn2);
772 :
773 17681728 : return next_active_insn (insn) == insn2;
774 : }
775 :
776 : /* Return nonzero if we could reach target from src by falling through,
777 : if the target was made adjacent. If we already have a fall-through
778 : edge to the exit block, we can't do that. */
779 : static bool
780 2284684 : could_fall_through (basic_block src, basic_block target)
781 : {
782 2284684 : edge e;
783 2284684 : edge_iterator ei;
784 :
785 2284684 : if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
786 : return true;
787 6854052 : FOR_EACH_EDGE (e, ei, src->succs)
788 4569368 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
789 0 : && e->flags & EDGE_FALLTHRU)
790 : return 0;
791 : return true;
792 : }
793 :
794 : /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
795 : rtx_note *
796 76025002 : bb_note (basic_block bb)
797 : {
798 76025002 : rtx_insn *note;
799 :
800 76025002 : note = BB_HEAD (bb);
801 76025002 : if (LABEL_P (note))
802 36501887 : note = NEXT_INSN (note);
803 :
804 76025002 : gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
805 76025002 : return as_a <rtx_note *> (note);
806 : }
807 :
808 : /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
809 : note associated with the BLOCK. */
810 :
811 : static rtx_insn *
812 8252 : first_insn_after_basic_block_note (basic_block block)
813 : {
814 8252 : rtx_insn *insn;
815 :
816 : /* Get the first instruction in the block. */
817 8252 : insn = BB_HEAD (block);
818 :
819 8252 : if (insn == NULL_RTX)
820 : return NULL;
821 8252 : if (LABEL_P (insn))
822 8252 : insn = NEXT_INSN (insn);
823 8252 : gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
824 :
825 8252 : return NEXT_INSN (insn);
826 : }
827 :
828 : /* Creates a new basic block just after basic block BB by splitting
829 : everything after specified instruction INSNP. */
830 :
831 : static basic_block
832 3041243 : rtl_split_block (basic_block bb, void *insnp)
833 : {
834 3041243 : basic_block new_bb;
835 3041243 : rtx_insn *insn = (rtx_insn *) insnp;
836 3041243 : edge e;
837 3041243 : edge_iterator ei;
838 :
839 3041243 : if (!insn)
840 : {
841 8252 : insn = first_insn_after_basic_block_note (bb);
842 :
843 8252 : if (insn)
844 : {
845 8232 : rtx_insn *next = insn;
846 :
847 8232 : insn = PREV_INSN (insn);
848 :
849 : /* If the block contains only debug insns, insn would have
850 : been NULL in a non-debug compilation, and then we'd end
851 : up emitting a DELETED note. For -fcompare-debug
852 : stability, emit the note too. */
853 8232 : if (insn != BB_END (bb)
854 7976 : && DEBUG_INSN_P (next)
855 676 : && DEBUG_INSN_P (BB_END (bb)))
856 : {
857 272 : while (next != BB_END (bb) && DEBUG_INSN_P (next))
858 183 : next = NEXT_INSN (next);
859 :
860 89 : if (next == BB_END (bb))
861 88 : emit_note_after (NOTE_INSN_DELETED, next);
862 : }
863 : }
864 : else
865 20 : insn = get_last_insn ();
866 : }
867 :
868 : /* We probably should check type of the insn so that we do not create
869 : inconsistent cfg. It is checked in verify_flow_info anyway, so do not
870 : bother. */
871 3041243 : if (insn == BB_END (bb))
872 276 : emit_note_after (NOTE_INSN_DELETED, insn);
873 :
874 : /* Create the new basic block. */
875 3041243 : new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
876 3041243 : BB_COPY_PARTITION (new_bb, bb);
877 3041243 : BB_END (bb) = insn;
878 :
879 : /* Redirect the outgoing edges. */
880 3041243 : new_bb->succs = bb->succs;
881 3041243 : bb->succs = NULL;
882 8386741 : FOR_EACH_EDGE (e, ei, new_bb->succs)
883 5345498 : e->src = new_bb;
884 :
885 : /* The new block starts off being dirty. */
886 3041243 : df_set_bb_dirty (bb);
887 3041243 : return new_bb;
888 : }
889 :
890 : /* Return true if LOC1 and LOC2 are equivalent for
891 : unique_locus_on_edge_between_p purposes. */
892 :
893 : static bool
894 1458498 : loc_equal (location_t loc1, location_t loc2)
895 : {
896 1458498 : if (loc1 == loc2)
897 : return true;
898 :
899 683759 : expanded_location loce1 = expand_location (loc1);
900 683759 : expanded_location loce2 = expand_location (loc2);
901 :
902 683759 : if (loce1.line != loce2.line
903 450821 : || loce1.column != loce2.column
904 318155 : || loce1.data != loce2.data)
905 : return false;
906 277508 : if (loce1.file == loce2.file)
907 : return true;
908 0 : return (loce1.file != NULL
909 0 : && loce2.file != NULL
910 0 : && filename_cmp (loce1.file, loce2.file) == 0);
911 : }
912 :
913 : /* Return true if the single edge between blocks A and B is the only place
914 : in RTL which holds some unique locus. */
915 :
916 : static bool
917 1173940 : unique_locus_on_edge_between_p (basic_block a, basic_block b)
918 : {
919 1173940 : const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
920 1173940 : rtx_insn *insn, *end;
921 :
922 1173940 : if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
923 : return false;
924 :
925 : /* First scan block A backward. */
926 534607 : insn = BB_END (a);
927 534607 : end = PREV_INSN (BB_HEAD (a));
928 1254804 : while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
929 185590 : insn = PREV_INSN (insn);
930 :
931 534607 : if (insn != end && loc_equal (INSN_LOCATION (insn), goto_locus))
932 : return false;
933 :
934 : /* Then scan block B forward. */
935 196643 : insn = BB_HEAD (b);
936 196643 : if (insn)
937 : {
938 186806 : end = NEXT_INSN (BB_END (b));
939 375015 : while (insn != end && !NONDEBUG_INSN_P (insn))
940 1403 : insn = NEXT_INSN (insn);
941 :
942 186553 : if (insn != end && INSN_HAS_LOCATION (insn)
943 372297 : && loc_equal (INSN_LOCATION (insn), goto_locus))
944 173747 : return false;
945 : }
946 :
947 : return true;
948 : }
949 :
950 : /* If the single edge between blocks A and B is the only place in RTL which
951 : holds some unique locus, emit a nop with that locus between the blocks. */
952 :
953 : static void
954 1173940 : emit_nop_for_unique_locus_between (basic_block a, basic_block b)
955 : {
956 1173940 : if (!unique_locus_on_edge_between_p (a, b))
957 : return;
958 :
959 22896 : BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
960 22896 : INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
961 : }
962 :
963 : /* Blocks A and B are to be merged into a single block A. The insns
964 : are already contiguous. */
965 :
966 : static void
967 3863012 : rtl_merge_blocks (basic_block a, basic_block b)
968 : {
969 : /* If B is a forwarder block whose outgoing edge has no location, we'll
970 : propagate the locus of the edge between A and B onto it. */
971 3863012 : const bool forward_edge_locus
972 3863012 : = (b->flags & BB_FORWARDER_BLOCK) != 0
973 3863012 : && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
974 3863012 : rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
975 3863012 : rtx_insn *del_first = NULL, *del_last = NULL;
976 3863012 : rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
977 3863012 : bool b_empty = false;
978 :
979 3863012 : if (dump_file)
980 1003 : fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
981 : a->index);
982 :
983 4327816 : while (DEBUG_INSN_P (b_end))
984 464804 : b_end = PREV_INSN (b_debug_start = b_end);
985 :
986 : /* If there was a CODE_LABEL beginning B, delete it. */
987 3863012 : if (LABEL_P (b_head))
988 : {
989 : /* Detect basic blocks with nothing but a label. This can happen
990 : in particular at the end of a function. */
991 1786877 : if (b_head == b_end)
992 0 : b_empty = true;
993 :
994 1786877 : del_first = del_last = b_head;
995 1786877 : b_head = NEXT_INSN (b_head);
996 : }
997 :
998 : /* Delete the basic block note and handle blocks containing just that
999 : note. */
1000 3863012 : if (NOTE_INSN_BASIC_BLOCK_P (b_head))
1001 : {
1002 3863012 : if (b_head == b_end)
1003 726058 : b_empty = true;
1004 3863012 : if (! del_last)
1005 2076135 : del_first = b_head;
1006 :
1007 3863012 : del_last = b_head;
1008 3863012 : b_head = NEXT_INSN (b_head);
1009 : }
1010 :
1011 : /* If there was a jump out of A, delete it. */
1012 3863012 : if (JUMP_P (a_end))
1013 : {
1014 53817 : rtx_insn *prev;
1015 :
1016 54907 : for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
1017 54907 : if (!NOTE_P (prev)
1018 3864102 : || NOTE_INSN_BASIC_BLOCK_P (prev)
1019 55997 : || prev == BB_HEAD (a))
1020 : break;
1021 :
1022 : del_first = a_end;
1023 :
1024 : a_end = PREV_INSN (del_first);
1025 : }
1026 3809195 : else if (BARRIER_P (NEXT_INSN (a_end)))
1027 0 : del_first = NEXT_INSN (a_end);
1028 :
1029 : /* Delete everything marked above as well as crap that might be
1030 : hanging out between the two blocks. */
1031 3863012 : BB_END (a) = a_end;
1032 3863012 : BB_HEAD (b) = b_empty ? NULL : b_head;
1033 3863012 : delete_insn_chain (del_first, del_last, true);
1034 :
1035 : /* If not optimizing, preserve the locus of the single edge between
1036 : blocks A and B if necessary by emitting a nop. */
1037 3863012 : if (!optimize
1038 1440286 : && !forward_edge_locus
1039 5037691 : && !DECL_IGNORED_P (current_function_decl))
1040 : {
1041 1171644 : emit_nop_for_unique_locus_between (a, b);
1042 1171644 : a_end = BB_END (a);
1043 : }
1044 :
1045 : /* Reassociate the insns of B with A. */
1046 3863012 : if (!b_empty)
1047 : {
1048 3136954 : update_bb_for_insn_chain (a_end, b_debug_end, a);
1049 :
1050 3136954 : BB_END (a) = b_debug_end;
1051 3136954 : BB_HEAD (b) = NULL;
1052 : }
1053 726058 : else if (b_end != b_debug_end)
1054 : {
1055 : /* Move any deleted labels and other notes between the end of A
1056 : and the debug insns that make up B after the debug insns,
1057 : bringing the debug insns into A while keeping the notes after
1058 : the end of A. */
1059 21785 : if (NEXT_INSN (a_end) != b_debug_start)
1060 147 : reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
1061 : b_debug_end);
1062 21785 : update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
1063 21785 : BB_END (a) = b_debug_end;
1064 : }
1065 :
1066 3863012 : df_bb_delete (b->index);
1067 :
1068 3863012 : if (forward_edge_locus)
1069 689650 : EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
1070 :
1071 3863012 : if (dump_file)
1072 1003 : fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
1073 3863012 : }
1074 :
1075 :
1076 : /* Return true when block A and B can be merged. */
1077 :
1078 : static bool
1079 64 : rtl_can_merge_blocks (basic_block a, basic_block b)
1080 : {
1081 : /* If we are partitioning hot/cold basic blocks, we don't want to
1082 : mess up unconditional or indirect jumps that cross between hot
1083 : and cold sections.
1084 :
1085 : Basic block partitioning may result in some jumps that appear to
1086 : be optimizable (or blocks that appear to be mergeable), but which really
1087 : must be left untouched (they are required to make it safely across
1088 : partition boundaries). See the comments at the top of
1089 : bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
1090 :
1091 64 : if (BB_PARTITION (a) != BB_PARTITION (b))
1092 : return false;
1093 :
1094 : /* Protect the loop latches. */
1095 64 : if (current_loops && b->loop_father->latch == b)
1096 : return false;
1097 :
1098 : /* A shared table between the blocks is live data, not disposable material
1099 : that can become part of the merged block. */
1100 64 : if (a->next_bb == b
1101 64 : && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1102 64 : && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
1103 128 : && shared_jump_table_between_p (NEXT_INSN (BB_END (a)), BB_HEAD (b)))
1104 : return false;
1105 :
1106 : /* There must be exactly one edge in between the blocks. */
1107 64 : return (single_succ_p (a)
1108 62 : && single_succ (a) == b
1109 51 : && single_pred_p (b)
1110 51 : && a != b
1111 : /* Must be simple edge. */
1112 51 : && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
1113 51 : && a->next_bb == b
1114 51 : && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1115 51 : && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
1116 : /* If the jump insn has side effects,
1117 : we can't kill the edge. */
1118 115 : && (!JUMP_P (BB_END (a))
1119 0 : || (reload_completed
1120 0 : ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
1121 : }
1122 :
1123 : /* Return the label in the head of basic block BLOCK. Create one if it doesn't
1124 : exist. */
1125 :
1126 : rtx_code_label *
1127 15622324 : block_label (basic_block block)
1128 : {
1129 15622324 : if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
1130 : return NULL;
1131 :
1132 15567598 : if (!LABEL_P (BB_HEAD (block)))
1133 : {
1134 5742004 : BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
1135 : }
1136 :
1137 15567598 : return as_a <rtx_code_label *> (BB_HEAD (block));
1138 : }
1139 :
1140 : /* Remove all barriers from BB_FOOTER of a BB. */
1141 :
1142 : static void
1143 3890595 : remove_barriers_from_footer (basic_block bb)
1144 : {
1145 3890595 : rtx_insn *insn = BB_FOOTER (bb);
1146 :
1147 : /* Remove barriers but keep jumptables. */
1148 7502860 : while (insn)
1149 : {
1150 3612265 : if (BARRIER_P (insn))
1151 : {
1152 3612243 : if (PREV_INSN (insn))
1153 11 : SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1154 : else
1155 3612232 : BB_FOOTER (bb) = NEXT_INSN (insn);
1156 3612243 : if (NEXT_INSN (insn))
1157 62005 : SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1158 : }
1159 3612265 : if (LABEL_P (insn))
1160 : return;
1161 3612265 : insn = NEXT_INSN (insn);
1162 : }
1163 : }
1164 :
1165 : /* Attempt to perform edge redirection by replacing possibly complex jump
1166 : instruction by unconditional jump or removing jump completely. This can
1167 : apply only if all edges now point to the same block. The parameters and
1168 : return values are equivalent to redirect_edge_and_branch. */
1169 :
1170 : edge
1171 48979594 : try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
1172 : {
1173 48979594 : basic_block src = e->src;
1174 48979594 : rtx_insn *insn = BB_END (src);
1175 48979594 : rtx set;
1176 48979594 : bool fallthru = false;
1177 :
1178 : /* If we are partitioning hot/cold basic blocks, we don't want to
1179 : mess up unconditional or indirect jumps that cross between hot
1180 : and cold sections.
1181 :
1182 : Basic block partitioning may result in some jumps that appear to
1183 : be optimizable (or blocks that appear to be mergeable), but which really
1184 : must be left untouched (they are required to make it safely across
1185 : partition boundaries). See the comments at the top of
1186 : bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
1187 :
1188 48979594 : if (BB_PARTITION (src) != BB_PARTITION (target))
1189 : return NULL;
1190 :
1191 : /* We can replace or remove a complex jump only when we have exactly
1192 : two edges. Also, if we have exactly one outgoing edge, we can
1193 : redirect that. */
1194 48923101 : if (EDGE_COUNT (src->succs) >= 3
1195 : /* Verify that all targets will be TARGET. Specifically, the
1196 : edge that is not E must also go to TARGET. */
1197 48923101 : || (EDGE_COUNT (src->succs) == 2
1198 18237118 : && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1199 : return NULL;
1200 :
1201 30820009 : if (!onlyjump_p (insn))
1202 : return NULL;
1203 :
1204 29294765 : rtx_jump_table_data *insn_table;
1205 29294765 : if (tablejump_p (insn, NULL, &insn_table)
1206 29294765 : && (!optimize
1207 110 : || reload_completed
1208 : /* A shared table is still needed by the other jumps that dispatch
1209 : through it, so it cannot be removed along with INSN. */
1210 2 : || JUMP_TABLE_SHARED_P (PATTERN (insn_table))))
1211 : return NULL;
1212 :
1213 : /* Avoid removing branch with side effects. */
1214 29294657 : set = single_set (insn);
1215 29294657 : if (!set || side_effects_p (set))
1216 : return NULL;
1217 :
1218 : /* See if we can create the fallthru edge. */
1219 29294657 : if (in_cfglayout || can_fallthru (src, target))
1220 : {
1221 4767749 : if (dump_file)
1222 804 : fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1223 4767749 : fallthru = true;
1224 :
1225 : /* Selectively unlink whole insn chain. */
1226 4767749 : if (in_cfglayout)
1227 : {
1228 3890595 : delete_insn_chain (insn, BB_END (src), false);
1229 3890595 : remove_barriers_from_footer (src);
1230 : }
1231 : else
1232 877154 : delete_insn_chain (insn, PREV_INSN (BB_HEAD (target)), false);
1233 : }
1234 :
1235 : /* If this already is simplejump, redirect it. */
1236 24526908 : else if (simplejump_p (insn))
1237 : {
1238 24524595 : if (e->dest == target)
1239 : return NULL;
1240 424910 : if (dump_file)
1241 111 : fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1242 111 : INSN_UID (insn), e->dest->index, target->index);
1243 424910 : if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1244 424910 : block_label (target), 0))
1245 : {
1246 0 : gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1247 : return NULL;
1248 : }
1249 : }
1250 :
1251 : /* Cannot do anything for target exit block. */
1252 2313 : else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1253 : return NULL;
1254 :
1255 : /* Or replace possibly complicated jump insn by simple jump insn. */
1256 : else
1257 : {
1258 2313 : rtx_code_label *target_label = block_label (target);
1259 2313 : rtx_insn *barrier;
1260 2313 : rtx_insn *label;
1261 2313 : rtx_jump_table_data *table;
1262 :
1263 2313 : emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn);
1264 2313 : JUMP_LABEL (BB_END (src)) = target_label;
1265 2313 : LABEL_NUSES (target_label)++;
1266 2313 : if (dump_file)
1267 0 : fprintf (dump_file, "Replacing insn %i by jump %i\n",
1268 0 : INSN_UID (insn), INSN_UID (BB_END (src)));
1269 :
1270 :
1271 2313 : delete_insn_chain (insn, insn, false);
1272 :
1273 : /* Recognize a tablejump that we are converting to a
1274 : simple jump and remove its associated CODE_LABEL
1275 : and ADDR_VEC or ADDR_DIFF_VEC. */
1276 2313 : if (tablejump_p (insn, &label, &table))
1277 2 : delete_insn_chain (label, table, false);
1278 :
1279 2313 : barrier = next_nonnote_nondebug_insn (BB_END (src));
1280 2313 : if (!barrier || !BARRIER_P (barrier))
1281 2158 : emit_barrier_after (BB_END (src));
1282 : else
1283 : {
1284 155 : if (barrier != NEXT_INSN (BB_END (src)))
1285 : {
1286 : /* Move the jump before barrier so that the notes
1287 : which originally were or were created before jump table are
1288 : inside the basic block. */
1289 0 : rtx_insn *new_insn = BB_END (src);
1290 :
1291 0 : update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1292 : PREV_INSN (barrier), src);
1293 :
1294 0 : SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1295 0 : SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1296 :
1297 0 : SET_NEXT_INSN (new_insn) = barrier;
1298 0 : SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1299 :
1300 0 : SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1301 0 : SET_PREV_INSN (barrier) = new_insn;
1302 : }
1303 : }
1304 : }
1305 :
1306 : /* Keep only one edge out and set proper flags. */
1307 5194972 : if (!single_succ_p (src))
1308 154528 : remove_edge (e);
1309 5194972 : gcc_assert (single_succ_p (src));
1310 :
1311 5194972 : e = single_succ_edge (src);
1312 5194972 : if (fallthru)
1313 : e->flags = EDGE_FALLTHRU;
1314 : else
1315 427223 : e->flags = 0;
1316 :
1317 5194972 : e->probability = profile_probability::always ();
1318 :
1319 5194972 : if (e->dest != target)
1320 661826 : redirect_edge_succ (e, target);
1321 : return e;
1322 : }
1323 :
1324 : /* Subroutine of redirect_branch_edge that tries to patch the jump
1325 : instruction INSN so that it reaches block NEW. Do this
1326 : only when it originally reached block OLD. Return true if this
1327 : worked or the original target wasn't OLD, return false if redirection
1328 : doesn't work. */
1329 :
1330 : static bool
1331 6970636 : patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1332 : {
1333 6970636 : rtx_jump_table_data *table;
1334 6970636 : rtx tmp;
1335 : /* Recognize a tablejump and adjust all matching cases. */
1336 6970636 : if (tablejump_p (insn, NULL, &table))
1337 : {
1338 16992 : rtvec vec;
1339 16992 : int j;
1340 :
1341 16992 : if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1342 : return false;
1343 :
1344 : /* The table also describes the successors of the other jumps that
1345 : dispatch through it, which this edge says nothing about. */
1346 16992 : if (JUMP_TABLE_SHARED_P (PATTERN (table)))
1347 : return false;
1348 :
1349 16992 : rtx_code_label *new_label = block_label (new_bb);
1350 16992 : vec = table->get_labels ();
1351 :
1352 455298 : for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1353 438306 : if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1354 : {
1355 74755 : RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1356 66919 : --LABEL_NUSES (old_label);
1357 66919 : ++LABEL_NUSES (new_label);
1358 : }
1359 :
1360 : /* Handle casesi dispatch insns. */
1361 16992 : if ((tmp = tablejump_casesi_pattern (insn)) != NULL_RTX
1362 16992 : && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label)
1363 : {
1364 0 : XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1365 : new_label);
1366 0 : --LABEL_NUSES (old_label);
1367 0 : ++LABEL_NUSES (new_label);
1368 : }
1369 : }
1370 6953644 : else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1371 : {
1372 448 : int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1373 448 : rtx note;
1374 :
1375 448 : if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1376 : return false;
1377 448 : rtx_code_label *new_label = block_label (new_bb);
1378 :
1379 1639 : for (i = 0; i < n; ++i)
1380 : {
1381 743 : rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1382 743 : gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1383 743 : if (XEXP (old_ref, 0) == old_label)
1384 : {
1385 872 : ASM_OPERANDS_LABEL (tmp, i)
1386 436 : = gen_rtx_LABEL_REF (Pmode, new_label);
1387 436 : --LABEL_NUSES (old_label);
1388 436 : ++LABEL_NUSES (new_label);
1389 : }
1390 : }
1391 :
1392 448 : if (JUMP_LABEL (insn) == old_label)
1393 : {
1394 332 : JUMP_LABEL (insn) = new_label;
1395 332 : note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1396 332 : if (note)
1397 0 : remove_note (insn, note);
1398 : }
1399 : else
1400 : {
1401 116 : note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1402 116 : if (note)
1403 99 : remove_note (insn, note);
1404 116 : if (JUMP_LABEL (insn) != new_label
1405 116 : && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1406 109 : add_reg_note (insn, REG_LABEL_TARGET, new_label);
1407 : }
1408 896 : while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1409 448 : != NULL_RTX)
1410 0 : XEXP (note, 0) = new_label;
1411 : }
1412 : else
1413 : {
1414 : /* ?? We may play the games with moving the named labels from
1415 : one basic block to the other in case only one computed_jump is
1416 : available. */
1417 6953196 : if (computed_jump_p (insn)
1418 : /* A return instruction can't be redirected. */
1419 6953196 : || returnjump_p (insn))
1420 : return false;
1421 :
1422 6953196 : if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1423 : {
1424 : /* If the insn doesn't go where we think, we're confused. */
1425 6918619 : gcc_assert (JUMP_LABEL (insn) == old_label);
1426 :
1427 : /* If the substitution doesn't succeed, die. This can happen
1428 : if the back end emitted unrecognizable instructions or if
1429 : target is exit block on some arches. Or for crossing
1430 : jumps. */
1431 6918619 : if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1432 6918619 : block_label (new_bb), 0))
1433 : {
1434 0 : gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1435 : || CROSSING_JUMP_P (insn));
1436 : return false;
1437 : }
1438 : }
1439 : }
1440 : return true;
1441 : }
1442 :
1443 :
1444 : /* Redirect edge representing branch of (un)conditional jump or tablejump,
1445 : NULL on failure */
1446 : static edge
1447 14833826 : redirect_branch_edge (edge e, basic_block target)
1448 : {
1449 14833826 : rtx_insn *old_label = BB_HEAD (e->dest);
1450 14833826 : basic_block src = e->src;
1451 14833826 : rtx_insn *insn = BB_END (src);
1452 :
1453 : /* We can only redirect non-fallthru edges of jump insn. */
1454 14833826 : if (e->flags & EDGE_FALLTHRU)
1455 : return NULL;
1456 6924389 : else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1457 : return NULL;
1458 :
1459 6924389 : if (!currently_expanding_to_rtl)
1460 : {
1461 6490841 : if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1462 : return NULL;
1463 : }
1464 : else
1465 : /* When expanding this BB might actually contain multiple
1466 : jumps (i.e. not yet split by find_many_sub_basic_blocks).
1467 : Redirect all of those that match our label. */
1468 7174652 : FOR_BB_INSNS (src, insn)
1469 6741104 : if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1470 : old_label, target))
1471 : return NULL;
1472 :
1473 6924389 : if (dump_file)
1474 796 : fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1475 796 : e->src->index, e->dest->index, target->index);
1476 :
1477 6924389 : if (e->dest != target)
1478 6924389 : e = redirect_edge_succ_nodup (e, target);
1479 :
1480 : return e;
1481 : }
1482 :
1483 : /* Called when edge E has been redirected to a new destination,
1484 : in order to update the region crossing flag on the edge and
1485 : jump. */
1486 :
1487 : static void
1488 18618337 : fixup_partition_crossing (edge e)
1489 : {
1490 18618337 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1491 18618337 : == EXIT_BLOCK_PTR_FOR_FN (cfun))
1492 : return;
1493 : /* If we redirected an existing edge, it may already be marked
1494 : crossing, even though the new src is missing a reg crossing note.
1495 : But make sure reg crossing note doesn't already exist before
1496 : inserting. */
1497 18617471 : if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1498 : {
1499 111475 : e->flags |= EDGE_CROSSING;
1500 111475 : if (JUMP_P (BB_END (e->src)))
1501 111475 : set_crossing_jump (BB_END (e->src), true);
1502 : }
1503 18505996 : else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1504 : {
1505 18505996 : e->flags &= ~EDGE_CROSSING;
1506 : /* Remove the section crossing note from jump at end of
1507 : src if it exists, and if no other successors are
1508 : still crossing. */
1509 18505996 : if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1510 : {
1511 194855 : bool has_crossing_succ = false;
1512 194855 : edge e2;
1513 194855 : edge_iterator ei;
1514 323569 : FOR_EACH_EDGE (e2, ei, e->src->succs)
1515 : {
1516 271414 : has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1517 271414 : if (has_crossing_succ)
1518 : break;
1519 : }
1520 194855 : if (!has_crossing_succ)
1521 52155 : set_crossing_jump (BB_END (e->src), false);
1522 : }
1523 : }
1524 : }
1525 :
1526 : /* Called when block BB has been reassigned to the cold partition,
1527 : because it is now dominated by another cold block,
1528 : to ensure that the region crossing attributes are updated. */
1529 :
1530 : static void
1531 319 : fixup_new_cold_bb (basic_block bb)
1532 : {
1533 319 : edge e;
1534 319 : edge_iterator ei;
1535 :
1536 : /* This is called when a hot bb is found to now be dominated
1537 : by a cold bb and therefore needs to become cold. Therefore,
1538 : its preds will no longer be region crossing. Any non-dominating
1539 : preds that were previously hot would also have become cold
1540 : in the caller for the same region. Any preds that were previously
1541 : region-crossing will be adjusted in fixup_partition_crossing. */
1542 651 : FOR_EACH_EDGE (e, ei, bb->preds)
1543 : {
1544 332 : fixup_partition_crossing (e);
1545 : }
1546 :
1547 : /* Possibly need to make bb's successor edges region crossing,
1548 : or remove stale region crossing. */
1549 653 : FOR_EACH_EDGE (e, ei, bb->succs)
1550 : {
1551 : /* We can't have fall-through edges across partition boundaries.
1552 : Note that force_nonfallthru will do any necessary partition
1553 : boundary fixup by calling fixup_partition_crossing itself. */
1554 334 : if ((e->flags & EDGE_FALLTHRU)
1555 294 : && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1556 270 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1557 0 : force_nonfallthru (e);
1558 : else
1559 334 : fixup_partition_crossing (e);
1560 : }
1561 319 : }
1562 :
1563 : /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1564 : expense of adding new instructions or reordering basic blocks.
1565 :
1566 : Function can be also called with edge destination equivalent to the TARGET.
1567 : Then it should try the simplifications and do nothing if none is possible.
1568 :
1569 : Return edge representing the branch if transformation succeeded. Return NULL
1570 : on failure.
1571 : We still return NULL in case E already destinated TARGET and we didn't
1572 : managed to simplify instruction stream. */
1573 :
1574 : static edge
1575 10074414 : rtl_redirect_edge_and_branch (edge e, basic_block target)
1576 : {
1577 10074414 : edge ret;
1578 10074414 : basic_block src = e->src;
1579 10074414 : basic_block dest = e->dest;
1580 :
1581 10074414 : if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1582 : return NULL;
1583 :
1584 10074414 : if (dest == target)
1585 : return e;
1586 :
1587 10074408 : if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1588 : {
1589 485454 : df_set_bb_dirty (src);
1590 485454 : fixup_partition_crossing (ret);
1591 485454 : return ret;
1592 : }
1593 :
1594 9588954 : ret = redirect_branch_edge (e, target);
1595 9588954 : if (!ret)
1596 : return NULL;
1597 :
1598 1679517 : df_set_bb_dirty (src);
1599 1679517 : fixup_partition_crossing (ret);
1600 1679517 : return ret;
1601 : }
1602 :
1603 : /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1604 :
1605 : void
1606 5504528 : emit_barrier_after_bb (basic_block bb)
1607 : {
1608 5504528 : rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1609 5504528 : gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1610 : || current_ir_type () == IR_RTL_CFGLAYOUT);
1611 5504528 : if (current_ir_type () == IR_RTL_CFGLAYOUT)
1612 : {
1613 75070 : rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1614 :
1615 75070 : if (BB_FOOTER (bb))
1616 : {
1617 : rtx_insn *footer_tail = BB_FOOTER (bb);
1618 :
1619 3111 : while (NEXT_INSN (footer_tail))
1620 : footer_tail = NEXT_INSN (footer_tail);
1621 3111 : if (!BARRIER_P (footer_tail))
1622 : {
1623 0 : SET_NEXT_INSN (footer_tail) = insn;
1624 0 : SET_PREV_INSN (insn) = footer_tail;
1625 : }
1626 : }
1627 : else
1628 71959 : BB_FOOTER (bb) = insn;
1629 : }
1630 5504528 : }
1631 :
1632 : /* Like force_nonfallthru below, but additionally performs redirection
1633 : Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1634 : when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1635 : simple_return_rtx, indicating which kind of returnjump to create.
1636 : It should be NULL otherwise. */
1637 :
1638 : basic_block
1639 5365892 : force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1640 : {
1641 5365892 : basic_block jump_block, new_bb = NULL, src = e->src;
1642 5365892 : rtx note;
1643 5365892 : edge new_edge;
1644 5365892 : int abnormal_edge_flags = 0;
1645 5365892 : bool asm_goto_edge = false;
1646 :
1647 : /* In the case the last instruction is conditional jump to the next
1648 : instruction, first redirect the jump itself and then continue
1649 : by creating a basic block afterwards to redirect fallthru edge. */
1650 5365892 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1651 5365884 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1652 5365884 : && any_condjump_p (BB_END (e->src))
1653 6157049 : && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1654 : {
1655 0 : edge b = unchecked_make_edge (e->src, target, 0);
1656 0 : bool redirected;
1657 :
1658 0 : redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1659 0 : block_label (target), 0);
1660 0 : gcc_assert (redirected);
1661 :
1662 0 : if (rtx note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX))
1663 : {
1664 0 : int prob = XINT (note, 0);
1665 :
1666 0 : b->probability = profile_probability::from_reg_br_prob_note (prob);
1667 0 : e->probability -= e->probability;
1668 : }
1669 : }
1670 :
1671 5365892 : if (e->flags & EDGE_ABNORMAL)
1672 : {
1673 : /* Irritating special case - fallthru edge to the same block as abnormal
1674 : edge.
1675 : We can't redirect abnormal edge, but we still can split the fallthru
1676 : one and create separate abnormal edge to original destination.
1677 : This allows bb-reorder to make such edge non-fallthru. */
1678 0 : gcc_assert (e->dest == target);
1679 0 : abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1680 0 : e->flags &= EDGE_FALLTHRU;
1681 : }
1682 : else
1683 : {
1684 5365892 : gcc_assert (e->flags & EDGE_FALLTHRU);
1685 5365892 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1686 : {
1687 : /* We can't redirect the entry block. Create an empty block
1688 : at the start of the function which we use to add the new
1689 : jump. */
1690 8 : edge tmp;
1691 8 : edge_iterator ei;
1692 8 : bool found = false;
1693 :
1694 8 : basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1695 : ENTRY_BLOCK_PTR_FOR_FN (cfun));
1696 8 : bb->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1697 :
1698 : /* Make sure new block ends up in correct hot/cold section. */
1699 8 : BB_COPY_PARTITION (bb, e->dest);
1700 :
1701 : /* Change the existing edge's source to be the new block, and add
1702 : a new edge from the entry block to the new block. */
1703 8 : e->src = bb;
1704 8 : for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1705 8 : (tmp = ei_safe_edge (ei)); )
1706 : {
1707 8 : if (tmp == e)
1708 : {
1709 8 : ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1710 8 : found = true;
1711 8 : break;
1712 : }
1713 : else
1714 0 : ei_next (&ei);
1715 : }
1716 :
1717 0 : gcc_assert (found);
1718 :
1719 8 : vec_safe_push (bb->succs, e);
1720 8 : make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1721 : EDGE_FALLTHRU);
1722 : }
1723 : }
1724 :
1725 : /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1726 : don't point to the fallthru label. */
1727 5365892 : if (JUMP_P (BB_END (e->src))
1728 791345 : && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1729 790988 : && (e->flags & EDGE_FALLTHRU)
1730 6156880 : && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1731 : {
1732 188 : int n = ASM_OPERANDS_LABEL_LENGTH (note);
1733 :
1734 347 : for (int i = 0; i < n; ++i)
1735 227 : if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1736 : {
1737 : asm_goto_edge = true;
1738 : break;
1739 : }
1740 : }
1741 :
1742 5365892 : if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1743 : {
1744 991094 : rtx_insn *new_head;
1745 991094 : profile_count count = e->count ();
1746 991094 : profile_probability probability = e->probability;
1747 : /* Create the new structures. */
1748 :
1749 : /* If the old block ended with a tablejump, skip its table
1750 : by searching forward from there. Otherwise start searching
1751 : forward from the last instruction of the old block. A shared
1752 : table follows only one of the jumps through it. */
1753 991094 : rtx_jump_table_data *table;
1754 991094 : if (tablejump_p (BB_END (e->src), NULL, &table)
1755 991094 : && (!JUMP_TABLE_SHARED_P (PATTERN (table))
1756 0 : || hosted_shared_table (e->src) == table))
1757 0 : new_head = table;
1758 : else
1759 991094 : new_head = BB_END (e->src);
1760 991094 : new_head = NEXT_INSN (new_head);
1761 :
1762 991094 : jump_block = create_basic_block (new_head, NULL, e->src);
1763 991094 : jump_block->count = count;
1764 :
1765 : /* Make sure new block ends up in correct hot/cold section. */
1766 :
1767 991094 : BB_COPY_PARTITION (jump_block, e->src);
1768 :
1769 : /* Wire edge in. */
1770 991094 : new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1771 991094 : new_edge->probability = probability;
1772 :
1773 : /* Redirect old edge. */
1774 991094 : redirect_edge_pred (e, jump_block);
1775 991094 : e->probability = profile_probability::always ();
1776 :
1777 : /* If e->src was previously region crossing, it no longer is
1778 : and the reg crossing note should be removed. */
1779 991094 : fixup_partition_crossing (new_edge);
1780 :
1781 : /* If asm goto has any label refs to e->dest, change them to point
1782 : to jump_block instead. */
1783 991094 : if (asm_goto_edge)
1784 : {
1785 68 : int n = ASM_OPERANDS_LABEL_LENGTH (note);
1786 :
1787 174 : for (int i = 0; i < n; ++i)
1788 106 : if (label_ref_label (ASM_OPERANDS_LABEL (note, i))
1789 106 : == BB_HEAD (e->dest))
1790 : {
1791 69 : LABEL_NUSES (label_ref_label (ASM_OPERANDS_LABEL (note, i)))--;
1792 69 : set_label_ref_label (ASM_OPERANDS_LABEL (note, i),
1793 69 : block_label (jump_block));
1794 69 : LABEL_NUSES (label_ref_label (ASM_OPERANDS_LABEL (note, i)))++;
1795 : }
1796 :
1797 68 : rtx_insn *insn = BB_END (new_edge->src);
1798 68 : rtx_insn *old_label = BB_HEAD (e->dest);
1799 68 : rtx_insn *new_label = BB_HEAD (jump_block);
1800 :
1801 68 : if (JUMP_LABEL (insn) == old_label)
1802 : {
1803 55 : JUMP_LABEL (insn) = new_label;
1804 55 : if (rtx note = find_reg_note (insn, REG_LABEL_TARGET, new_label))
1805 0 : remove_note (insn, note);
1806 : }
1807 : else
1808 : {
1809 13 : if (rtx note = find_reg_note (insn, REG_LABEL_TARGET, old_label))
1810 13 : remove_note (insn, note);
1811 13 : if (JUMP_LABEL (insn) != new_label
1812 13 : && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1813 13 : add_reg_note (insn, REG_LABEL_TARGET, new_label);
1814 : }
1815 68 : while (rtx note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1816 0 : XEXP (note, 0) = new_label;
1817 : }
1818 :
1819 991094 : new_bb = jump_block;
1820 : }
1821 : else
1822 : jump_block = e->src;
1823 :
1824 5365892 : const location_t loc = e->goto_locus;
1825 5365892 : e->flags &= ~EDGE_FALLTHRU;
1826 5365892 : if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1827 : {
1828 580 : if (jump_label == ret_rtx)
1829 0 : emit_jump_insn_after_setloc (targetm.gen_return (),
1830 0 : BB_END (jump_block), loc);
1831 : else
1832 : {
1833 580 : gcc_assert (jump_label == simple_return_rtx);
1834 580 : emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1835 580 : BB_END (jump_block), loc);
1836 : }
1837 580 : set_return_jump_label (BB_END (jump_block));
1838 : }
1839 : else
1840 : {
1841 5365312 : rtx_code_label *label = block_label (target);
1842 5365312 : emit_jump_insn_after_setloc (targetm.gen_jump (label),
1843 5365312 : BB_END (jump_block), loc);
1844 5365312 : JUMP_LABEL (BB_END (jump_block)) = label;
1845 5365312 : LABEL_NUSES (label)++;
1846 : }
1847 :
1848 : /* We might be in cfg layout mode, and if so, the following routine will
1849 : insert the barrier correctly. */
1850 5365892 : emit_barrier_after_bb (jump_block);
1851 5365892 : redirect_edge_succ_nodup (e, target);
1852 :
1853 5365892 : if (abnormal_edge_flags)
1854 0 : make_edge (src, target, abnormal_edge_flags);
1855 :
1856 5365892 : df_mark_solutions_dirty ();
1857 5365892 : fixup_partition_crossing (e);
1858 5365892 : return new_bb;
1859 : }
1860 :
1861 : /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1862 : (and possibly create new basic block) to make edge non-fallthru.
1863 : Return newly created BB or NULL if none. */
1864 :
1865 : static basic_block
1866 769265 : rtl_force_nonfallthru (edge e)
1867 : {
1868 769265 : return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1869 : }
1870 :
1871 : /* Redirect edge even at the expense of creating new jump insn or
1872 : basic block. Return new basic block if created, NULL otherwise.
1873 : Conversion must be possible. */
1874 :
1875 : static basic_block
1876 497802 : rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1877 : {
1878 497802 : if (redirect_edge_and_branch (e, target)
1879 497802 : || e->dest == target)
1880 : return NULL;
1881 :
1882 : /* In case the edge redirection failed, try to force it to be non-fallthru
1883 : and redirect newly created simplejump. */
1884 405548 : df_set_bb_dirty (e->src);
1885 405548 : return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1886 : }
1887 :
1888 : /* The given edge should potentially be a fallthru edge. If that is in
1889 : fact true, delete the jump and barriers that are in the way. */
1890 :
1891 : static void
1892 832937 : rtl_tidy_fallthru_edge (edge e)
1893 : {
1894 832937 : rtx_insn *q;
1895 832937 : basic_block b = e->src, c = b->next_bb;
1896 :
1897 : /* ??? In a late-running flow pass, other folks may have deleted basic
1898 : blocks by nopping out blocks, leaving multiple BARRIERs between here
1899 : and the target label. They ought to be chastised and fixed.
1900 :
1901 : We can also wind up with a sequence of undeletable labels between
1902 : one block and the next.
1903 :
1904 : So search through a sequence of barriers, labels, and notes for
1905 : the head of block C and assert that we really do fall through. */
1906 :
1907 1698513 : for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1908 32639 : if (NONDEBUG_INSN_P (q) || shared_jump_table_component_p (q))
1909 : return;
1910 :
1911 : /* Remove what will soon cease being the jump insn from the source block.
1912 : If block B consisted only of this single jump, turn it into a deleted
1913 : note. */
1914 832937 : q = BB_END (b);
1915 832937 : if (JUMP_P (q)
1916 40930 : && onlyjump_p (q)
1917 873855 : && (any_uncondjump_p (q)
1918 9219 : || single_succ_p (b)))
1919 : {
1920 33472 : rtx_insn *label;
1921 33472 : rtx_jump_table_data *table;
1922 :
1923 : /* A shared table is still needed by the other jumps that dispatch
1924 : through it; deleting this jump alone just drops one reference. */
1925 33472 : if (tablejump_p (q, &label, &table)
1926 33472 : && !JUMP_TABLE_SHARED_P (PATTERN (table)))
1927 : {
1928 : /* The label is likely mentioned in some instruction before
1929 : the tablejump and might not be DCEd, so turn it into
1930 : a note instead and move before the tablejump that is going to
1931 : be deleted. */
1932 0 : const char *name = LABEL_NAME (label);
1933 0 : PUT_CODE (label, NOTE);
1934 0 : NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1935 0 : NOTE_DELETED_LABEL_NAME (label) = name;
1936 0 : reorder_insns (label, label, PREV_INSN (q));
1937 0 : delete_insn (table);
1938 : }
1939 :
1940 33472 : q = PREV_INSN (q);
1941 : }
1942 : /* Unconditional jumps with side-effects (i.e. which we can't just delete
1943 : together with the barrier) should never have a fallthru edge. */
1944 799465 : else if (JUMP_P (q) && any_uncondjump_p (q))
1945 : return;
1946 :
1947 : /* Selectively unlink the sequence. */
1948 832937 : if (q != PREV_INSN (BB_HEAD (c)))
1949 33933 : delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1950 :
1951 832937 : e->flags |= EDGE_FALLTHRU;
1952 : }
1953 :
1954 : /* Should move basic block BB after basic block AFTER. NIY. */
1955 :
1956 : static bool
1957 702904 : rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1958 : basic_block after ATTRIBUTE_UNUSED)
1959 : {
1960 702904 : return false;
1961 : }
1962 :
1963 : /* Locate the last bb in the same partition as START_BB. */
1964 :
1965 : static basic_block
1966 34200 : last_bb_in_partition (basic_block start_bb)
1967 : {
1968 34200 : basic_block bb;
1969 21621073 : FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1970 : {
1971 21621073 : if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1972 : return bb;
1973 : }
1974 : /* Return bb before the exit block. */
1975 0 : return bb->prev_bb;
1976 : }
1977 :
1978 : /* Split a (typically critical) edge. Return the new block.
1979 : The edge must not be abnormal.
1980 :
1981 : ??? The code generally expects to be called on critical edges.
1982 : The case of a block ending in an unconditional jump to a
1983 : block with multiple predecessors is not handled optimally. */
1984 :
1985 : static basic_block
1986 1205073 : rtl_split_edge (edge edge_in)
1987 : {
1988 1205073 : basic_block bb, new_bb;
1989 1205073 : rtx_insn *before;
1990 :
1991 : /* Abnormal edges cannot be split. */
1992 1205073 : gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1993 :
1994 : /* We are going to place the new block in front of edge destination.
1995 : Avoid existence of fallthru predecessors. */
1996 1205073 : if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1997 : {
1998 683853 : edge e = find_fallthru_edge (edge_in->dest->preds);
1999 :
2000 683853 : if (e)
2001 518080 : force_nonfallthru (e);
2002 : }
2003 :
2004 : /* Create the basic block note. */
2005 1205073 : if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2006 953173 : before = BB_HEAD (edge_in->dest);
2007 : else
2008 : before = NULL;
2009 :
2010 : /* If this is a fall through edge to the exit block, the blocks might be
2011 : not adjacent, and the right place is after the source. */
2012 1205073 : if ((edge_in->flags & EDGE_FALLTHRU)
2013 521220 : && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
2014 : {
2015 251900 : before = NEXT_INSN (BB_END (edge_in->src));
2016 251900 : bb = create_basic_block (before, NULL, edge_in->src);
2017 251900 : BB_COPY_PARTITION (bb, edge_in->src);
2018 251900 : }
2019 : else
2020 : {
2021 953173 : if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2022 : {
2023 79426 : bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
2024 79426 : BB_COPY_PARTITION (bb, edge_in->dest);
2025 : }
2026 : else
2027 : {
2028 873747 : basic_block after = edge_in->dest->prev_bb;
2029 : /* If this is post-bb reordering, and the edge crosses a partition
2030 : boundary, the new block needs to be inserted in the bb chain
2031 : at the end of the src partition (since we put the new bb into
2032 : that partition, see below). Otherwise we may end up creating
2033 : an extra partition crossing in the chain, which is illegal.
2034 : It can't go after the src, because src may have a fall-through
2035 : to a different block. */
2036 873747 : if (crtl->bb_reorder_complete
2037 60212 : && (edge_in->flags & EDGE_CROSSING))
2038 : {
2039 34200 : after = last_bb_in_partition (edge_in->src);
2040 34200 : before = get_last_bb_insn (after);
2041 : /* The instruction following the last bb in partition should
2042 : be a barrier, since it cannot end in a fall-through. */
2043 34200 : gcc_checking_assert (BARRIER_P (before));
2044 34200 : before = NEXT_INSN (before);
2045 : }
2046 873747 : bb = create_basic_block (before, NULL, after);
2047 : /* Put the split bb into the src partition, to avoid creating
2048 : a situation where a cold bb dominates a hot bb, in the case
2049 : where src is cold and dest is hot. The src will dominate
2050 : the new bb (whereas it might not have dominated dest). */
2051 873747 : BB_COPY_PARTITION (bb, edge_in->src);
2052 : }
2053 : }
2054 :
2055 1205073 : make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
2056 :
2057 : /* Can't allow a region crossing edge to be fallthrough. */
2058 1205073 : if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
2059 72715 : && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2060 : {
2061 41150 : new_bb = force_nonfallthru (single_succ_edge (bb));
2062 41150 : gcc_assert (!new_bb);
2063 : }
2064 :
2065 : /* For non-fallthru edges, we must adjust the predecessor's
2066 : jump instruction to target our new block. */
2067 1205073 : if ((edge_in->flags & EDGE_FALLTHRU) == 0)
2068 : {
2069 683853 : edge redirected = redirect_edge_and_branch (edge_in, bb);
2070 683853 : gcc_assert (redirected);
2071 : }
2072 : else
2073 : {
2074 521220 : if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
2075 : {
2076 : /* For asm goto even splitting of fallthru edge might
2077 : need insn patching, as other labels might point to the
2078 : old label. */
2079 441794 : rtx_insn *last = BB_END (edge_in->src);
2080 441794 : if (last
2081 441794 : && JUMP_P (last)
2082 204501 : && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
2083 178964 : && (extract_asm_operands (PATTERN (last))
2084 178955 : || JUMP_LABEL (last) == before)
2085 441803 : && patch_jump_insn (last, before, bb))
2086 9 : df_set_bb_dirty (edge_in->src);
2087 : }
2088 521220 : redirect_edge_succ (edge_in, bb);
2089 : }
2090 :
2091 1205073 : return bb;
2092 : }
2093 :
2094 : /* Queue instructions for insertion on an edge between two basic blocks.
2095 : The new instructions and basic blocks (if any) will not appear in the
2096 : CFG until commit_edge_insertions is called. If there are already
2097 : queued instructions on the edge, PATTERN is appended to them. */
2098 :
2099 : void
2100 5637010 : insert_insn_on_edge (rtx pattern, edge e)
2101 : {
2102 : /* We cannot insert instructions on an abnormal critical edge.
2103 : It will be easier to find the culprit if we die now. */
2104 5637010 : gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
2105 :
2106 5637010 : if (e->insns.r == NULL_RTX)
2107 4718973 : start_sequence ();
2108 : else
2109 918037 : push_to_sequence (e->insns.r);
2110 :
2111 5637010 : emit_insn (pattern);
2112 :
2113 5637010 : e->insns.r = end_sequence ();
2114 5637010 : }
2115 :
2116 : /* Like insert_insn_on_edge, but if there are already queued instructions
2117 : on the edge, PATTERN is prepended to them. */
2118 :
2119 : void
2120 345 : prepend_insn_to_edge (rtx pattern, edge e)
2121 : {
2122 : /* We cannot insert instructions on an abnormal critical edge.
2123 : It will be easier to find the culprit if we die now. */
2124 345 : gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
2125 :
2126 345 : start_sequence ();
2127 :
2128 345 : emit_insn (pattern);
2129 345 : emit_insn (e->insns.r);
2130 :
2131 345 : e->insns.r = end_sequence ();
2132 345 : }
2133 :
2134 : /* Update the CFG for the instructions queued on edge E. */
2135 :
2136 : void
2137 4687272 : commit_one_edge_insertion (edge e)
2138 : {
2139 4687272 : rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
2140 4687272 : basic_block bb;
2141 :
2142 : /* Pull the insns off the edge now since the edge might go away. */
2143 4687272 : insns = e->insns.r;
2144 4687272 : e->insns.r = NULL;
2145 :
2146 : /* Allow the sequence to contain internal jumps, such as a memcpy loop
2147 : or an allocation loop. If such a sequence is emitted during RTL
2148 : expansion, we'll create the appropriate basic blocks later,
2149 : at the end of the pass. But if such a sequence is emitted after
2150 : initial expansion, we'll need to find the subblocks ourselves. */
2151 4687272 : bool contains_jump = false;
2152 4687272 : if (!currently_expanding_to_rtl)
2153 13431976 : for (rtx_insn *insn = insns; insn; insn = NEXT_INSN (insn))
2154 11643506 : if (JUMP_P (insn))
2155 : {
2156 1646674 : rebuild_jump_labels_chain (insns);
2157 1646674 : contains_jump = true;
2158 1646674 : break;
2159 : }
2160 :
2161 : /* Figure out where to put these insns. If the destination has
2162 : one predecessor, insert there. Except for the exit block. */
2163 4687272 : if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2164 : {
2165 1642152 : bb = e->dest;
2166 :
2167 : /* Get the location correct wrt a code label, and "nice" wrt
2168 : a basic block note, and before everything else. */
2169 1642152 : tmp = BB_HEAD (bb);
2170 1642152 : if (LABEL_P (tmp))
2171 75333 : tmp = NEXT_INSN (tmp);
2172 1642152 : if (NOTE_INSN_BASIC_BLOCK_P (tmp))
2173 1642152 : tmp = NEXT_INSN (tmp);
2174 1642152 : if (tmp == BB_HEAD (bb))
2175 : before = tmp;
2176 1642152 : else if (tmp)
2177 1642152 : after = PREV_INSN (tmp);
2178 : else
2179 0 : after = get_last_insn ();
2180 : }
2181 :
2182 : /* If the source has one successor and the edge is not abnormal,
2183 : insert there. Except for the entry block.
2184 : Don't do this if the predecessor ends in a jump other than
2185 : unconditional simple jump. E.g. for asm goto that points all
2186 : its labels at the fallthru basic block, we can't insert instructions
2187 : before the asm goto, as the asm goto can have various of side effects,
2188 : and can't emit instructions after the asm goto, as it must end
2189 : the basic block. */
2190 3045120 : else if ((e->flags & EDGE_ABNORMAL) == 0
2191 3045120 : && single_succ_p (e->src)
2192 2185410 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2193 5229049 : && (!JUMP_P (BB_END (e->src))
2194 376816 : || simplejump_p (BB_END (e->src))))
2195 : {
2196 2183929 : bb = e->src;
2197 :
2198 : /* It is possible to have a non-simple jump here. Consider a target
2199 : where some forms of unconditional jumps clobber a register. This
2200 : happens on the fr30 for example.
2201 :
2202 : We know this block has a single successor, so we can just emit
2203 : the queued insns before the jump. */
2204 2183929 : if (JUMP_P (BB_END (bb)))
2205 : before = BB_END (bb);
2206 : else
2207 : {
2208 : /* We'd better be fallthru, or we've lost track of what's what. */
2209 1807113 : gcc_assert (e->flags & EDGE_FALLTHRU);
2210 :
2211 : after = BB_END (bb);
2212 : }
2213 : }
2214 :
2215 : /* Otherwise we must split the edge. */
2216 : else
2217 : {
2218 861191 : bb = split_edge (e);
2219 :
2220 : /* If E crossed a partition boundary, we needed to make bb end in
2221 : a region-crossing jump, even though it was originally fallthru. */
2222 861191 : if (JUMP_P (BB_END (bb)))
2223 : before = BB_END (bb);
2224 : else
2225 : after = BB_END (bb);
2226 : }
2227 :
2228 : /* Now that we've found the spot, do the insertion. */
2229 1642152 : if (before)
2230 : {
2231 417966 : emit_insn_before_noloc (insns, before, bb);
2232 417966 : last = prev_nonnote_insn (before);
2233 : }
2234 : else
2235 4269306 : last = emit_insn_after_noloc (insns, after, bb);
2236 :
2237 4687272 : if (returnjump_p (last))
2238 : {
2239 : /* ??? Remove all outgoing edges from BB and add one for EXIT.
2240 : This is not currently a problem because this only happens
2241 : for the (single) epilogue, which already has a fallthru edge
2242 : to EXIT. */
2243 :
2244 1386684 : e = single_succ_edge (bb);
2245 2773368 : gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2246 : && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2247 :
2248 1386684 : e->flags &= ~EDGE_FALLTHRU;
2249 1386684 : emit_barrier_after (last);
2250 :
2251 1386684 : if (before)
2252 0 : delete_insn (before);
2253 : }
2254 : else
2255 : /* Sequences inserted after RTL expansion are expected to be SESE,
2256 : with only internal branches allowed. If the sequence jumps outside
2257 : itself then we do not know how to add the associated edges here. */
2258 3300588 : gcc_assert (!JUMP_P (last) || currently_expanding_to_rtl);
2259 :
2260 4687272 : if (contains_jump)
2261 1646674 : find_sub_basic_blocks (bb);
2262 4687272 : }
2263 :
2264 : /* Update the CFG for all queued instructions. */
2265 :
2266 : void
2267 4672569 : commit_edge_insertions (void)
2268 : {
2269 4672569 : basic_block bb;
2270 :
2271 : /* Optimization passes that invoke this routine can cause hot blocks
2272 : previously reached by both hot and cold blocks to become dominated only
2273 : by cold blocks. This will cause the verification below to fail,
2274 : and lead to now cold code in the hot section. In some cases this
2275 : may only be visible after newly unreachable blocks are deleted,
2276 : which will be done by fixup_partitions. */
2277 4672569 : fixup_partitions ();
2278 :
2279 4672569 : if (!currently_expanding_to_rtl)
2280 3154663 : checking_verify_flow_info ();
2281 :
2282 68251058 : FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2283 : EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2284 : {
2285 63578489 : edge e;
2286 63578489 : edge_iterator ei;
2287 :
2288 151953688 : FOR_EACH_EDGE (e, ei, bb->succs)
2289 88375199 : if (e->insns.r)
2290 : {
2291 4646708 : if (currently_expanding_to_rtl)
2292 1252128 : rebuild_jump_labels_chain (e->insns.r);
2293 4646708 : commit_one_edge_insertion (e);
2294 : }
2295 : }
2296 4672569 : }
2297 :
2298 :
2299 : /* Print out RTL-specific basic block information (live information
2300 : at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2301 : documented in dumpfile.h. */
2302 :
2303 : static void
2304 2731 : rtl_dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
2305 : {
2306 2731 : char *s_indent;
2307 :
2308 2731 : s_indent = (char *) alloca ((size_t) indent + 1);
2309 2731 : memset (s_indent, ' ', (size_t) indent);
2310 2731 : s_indent[indent] = '\0';
2311 :
2312 2731 : if (df && (flags & TDF_DETAILS))
2313 : {
2314 728 : df_dump_top (bb, outf);
2315 728 : putc ('\n', outf);
2316 : }
2317 :
2318 2731 : if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK
2319 2731 : && rtl_bb_info_initialized_p (bb))
2320 : {
2321 2149 : rtx_insn *last = BB_END (bb);
2322 2149 : if (last)
2323 2149 : last = NEXT_INSN (last);
2324 15693 : for (rtx_insn *insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
2325 : {
2326 13544 : if (flags & TDF_DETAILS)
2327 4180 : df_dump_insn_top (insn, outf);
2328 13544 : if (! (flags & TDF_SLIM))
2329 13512 : print_rtl_single (outf, insn);
2330 : else
2331 32 : dump_insn_slim (outf, insn);
2332 13544 : if (flags & TDF_DETAILS)
2333 4180 : df_dump_insn_bottom (insn, outf);
2334 : }
2335 : }
2336 :
2337 2731 : if (df && (flags & TDF_DETAILS))
2338 : {
2339 728 : df_dump_bottom (bb, outf);
2340 728 : putc ('\n', outf);
2341 : }
2342 :
2343 2731 : }
2344 :
2345 : /* Like dump_function_to_file, but for RTL. Print out dataflow information
2346 : for the start of each basic block. FLAGS are the TDF_* masks documented
2347 : in dumpfile.h. */
2348 :
2349 : void
2350 4387 : print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, dump_flags_t flags)
2351 : {
2352 4387 : const rtx_insn *tmp_rtx;
2353 4387 : if (rtx_first == 0)
2354 0 : fprintf (outf, "(nil)\n");
2355 : else
2356 : {
2357 4387 : enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2358 4387 : int max_uid = get_max_uid ();
2359 4387 : basic_block *start = XCNEWVEC (basic_block, max_uid);
2360 4387 : basic_block *end = XCNEWVEC (basic_block, max_uid);
2361 4387 : enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2362 4387 : basic_block bb;
2363 :
2364 : /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2365 : insns, but the CFG is not maintained so the basic block info
2366 : is not reliable. Therefore it's omitted from the dumps. */
2367 4387 : if (! (cfun->curr_properties & PROP_cfg))
2368 1090 : flags &= ~TDF_BLOCKS;
2369 :
2370 4387 : if (df)
2371 3347 : df_dump_start (outf);
2372 :
2373 4387 : if (cfun->curr_properties & PROP_cfg)
2374 : {
2375 22366 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
2376 : {
2377 19069 : rtx_insn *x;
2378 :
2379 19069 : start[INSN_UID (BB_HEAD (bb))] = bb;
2380 19069 : end[INSN_UID (BB_END (bb))] = bb;
2381 19069 : if (flags & TDF_BLOCKS)
2382 : {
2383 5317 : for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2384 : {
2385 5317 : enum bb_state state = IN_MULTIPLE_BB;
2386 :
2387 5317 : if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2388 5317 : state = IN_ONE_BB;
2389 5317 : in_bb_p[INSN_UID (x)] = state;
2390 :
2391 5317 : if (x == BB_END (bb))
2392 : break;
2393 : }
2394 : }
2395 : }
2396 : }
2397 :
2398 172741 : for (tmp_rtx = rtx_first; tmp_rtx != NULL; tmp_rtx = NEXT_INSN (tmp_rtx))
2399 : {
2400 168354 : if (flags & TDF_BLOCKS)
2401 : {
2402 6106 : bb = start[INSN_UID (tmp_rtx)];
2403 6106 : if (bb != NULL)
2404 : {
2405 880 : dump_bb_info (outf, bb, 0, dump_flags, true, false);
2406 880 : if (df && (flags & TDF_DETAILS))
2407 582 : df_dump_top (bb, outf);
2408 : }
2409 :
2410 6106 : if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2411 789 : && !NOTE_P (tmp_rtx)
2412 6318 : && !BARRIER_P (tmp_rtx))
2413 0 : fprintf (outf, ";; Insn is not within a basic block\n");
2414 6106 : else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2415 0 : fprintf (outf, ";; Insn is in multiple basic blocks\n");
2416 : }
2417 :
2418 168354 : if (flags & TDF_DETAILS)
2419 19619 : df_dump_insn_top (tmp_rtx, outf);
2420 168354 : if (! (flags & TDF_SLIM))
2421 167818 : print_rtl_single (outf, tmp_rtx);
2422 : else
2423 536 : dump_insn_slim (outf, tmp_rtx);
2424 168354 : if (flags & TDF_DETAILS)
2425 19619 : df_dump_insn_bottom (tmp_rtx, outf);
2426 :
2427 168354 : bb = end[INSN_UID (tmp_rtx)];
2428 168354 : if (bb != NULL)
2429 : {
2430 19069 : if (flags & TDF_BLOCKS)
2431 : {
2432 880 : dump_bb_info (outf, bb, 0, dump_flags, false, true);
2433 880 : if (df && (flags & TDF_DETAILS))
2434 582 : df_dump_bottom (bb, outf);
2435 880 : putc ('\n', outf);
2436 : }
2437 : /* Emit a hint if the fallthrough target of current basic block
2438 : isn't the one placed right next. */
2439 186481 : else if (EDGE_COUNT (bb->succs) > 0)
2440 : {
2441 18127 : gcc_assert (BB_END (bb) == tmp_rtx);
2442 18127 : const rtx_insn *ninsn = NEXT_INSN (tmp_rtx);
2443 : /* Bypass intervening deleted-insn notes and debug insns. */
2444 18127 : while (ninsn
2445 19755 : && !NONDEBUG_INSN_P (ninsn)
2446 42299 : && !start[INSN_UID (ninsn)])
2447 4417 : ninsn = NEXT_INSN (ninsn);
2448 18127 : edge e = find_fallthru_edge (bb->succs);
2449 18127 : if (e && ninsn)
2450 : {
2451 13056 : basic_block dest = e->dest;
2452 13056 : if (start[INSN_UID (ninsn)] != dest)
2453 2166 : fprintf (outf, "%s ; pc falls through to BB %d\n",
2454 : print_rtx_head, dest->index);
2455 : }
2456 : }
2457 : }
2458 : }
2459 :
2460 4387 : free (start);
2461 4387 : free (end);
2462 4387 : free (in_bb_p);
2463 : }
2464 4387 : }
2465 :
2466 : /* Update the branch probability of BB if a REG_BR_PROB is present. */
2467 :
2468 : void
2469 9713724 : update_br_prob_note (basic_block bb)
2470 : {
2471 9713724 : rtx note;
2472 9713724 : note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2473 9713724 : if (!JUMP_P (BB_END (bb)) || !BRANCH_EDGE (bb)->probability.initialized_p ())
2474 : {
2475 255508 : if (note)
2476 : {
2477 0 : rtx *note_link, this_rtx;
2478 :
2479 0 : note_link = ®_NOTES (BB_END (bb));
2480 0 : for (this_rtx = *note_link; this_rtx; this_rtx = XEXP (this_rtx, 1))
2481 0 : if (this_rtx == note)
2482 : {
2483 0 : *note_link = XEXP (this_rtx, 1);
2484 0 : break;
2485 : }
2486 : }
2487 : return;
2488 : }
2489 9458216 : if (!note
2490 9458216 : || XINT (note, 0) == BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ())
2491 : return;
2492 209813 : XINT (note, 0) = BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ();
2493 : }
2494 :
2495 : /* Get the last insn associated with block BB (that includes barriers and
2496 : tablejumps after BB). */
2497 : rtx_insn *
2498 6998473 : get_last_bb_insn (basic_block bb)
2499 : {
2500 6998473 : rtx_jump_table_data *table;
2501 6998473 : rtx_insn *tmp;
2502 6998473 : rtx_insn *end = BB_END (bb);
2503 :
2504 : /* Include any jump table following the basic block. A table that other
2505 : jumps dispatch through as well follows only one of them. */
2506 6998473 : if (tablejump_p (end, NULL, &table)
2507 6998473 : && (!JUMP_TABLE_SHARED_P (PATTERN (table))
2508 211 : || hosted_shared_table (bb) == table))
2509 275 : end = table;
2510 :
2511 : /* Include any barriers that may follow the basic block. */
2512 6998473 : tmp = next_nonnote_nondebug_insn_bb (end);
2513 14606040 : while (tmp && BARRIER_P (tmp))
2514 : {
2515 609094 : end = tmp;
2516 609094 : tmp = next_nonnote_nondebug_insn_bb (end);
2517 : }
2518 :
2519 6998473 : return end;
2520 : }
2521 :
2522 : /* Add all BBs reachable from entry via hot paths into the SET. */
2523 :
2524 : void
2525 572127 : find_bbs_reachable_by_hot_paths (hash_set<basic_block> *set)
2526 : {
2527 572127 : auto_vec<basic_block, 64> worklist;
2528 :
2529 572127 : set->add (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2530 572127 : worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2531 :
2532 19942640 : while (worklist.length () > 0)
2533 : {
2534 18798386 : basic_block bb = worklist.pop ();
2535 18798386 : edge_iterator ei;
2536 18798386 : edge e;
2537 :
2538 47702728 : FOR_EACH_EDGE (e, ei, bb->succs)
2539 28904342 : if (BB_PARTITION (e->dest) != BB_COLD_PARTITION
2540 28904342 : && !set->add (e->dest))
2541 18226259 : worklist.safe_push (e->dest);
2542 : }
2543 572127 : }
2544 :
2545 : /* Sanity check partition hotness to ensure that basic blocks in
2546 : Â the cold partition don't dominate basic blocks in the hot partition.
2547 : If FLAG_ONLY is true, report violations as errors. Otherwise
2548 : re-mark the dominated blocks as cold, since this is run after
2549 : cfg optimizations that may make hot blocks previously reached
2550 : by both hot and cold blocks now only reachable along cold paths. */
2551 :
2552 : static auto_vec<basic_block>
2553 506363 : find_partition_fixes (bool flag_only)
2554 : {
2555 506363 : basic_block bb;
2556 506363 : auto_vec<basic_block> bbs_to_fix;
2557 506363 : hash_set<basic_block> set;
2558 :
2559 : /* Callers check this. */
2560 506363 : gcc_checking_assert (crtl->has_bb_partition);
2561 :
2562 506363 : find_bbs_reachable_by_hot_paths (&set);
2563 :
2564 18746259 : FOR_EACH_BB_FN (bb, cfun)
2565 18239896 : if (!set.contains (bb)
2566 18239896 : && BB_PARTITION (bb) != BB_COLD_PARTITION)
2567 : {
2568 319 : if (flag_only)
2569 0 : error ("non-cold basic block %d reachable only "
2570 : "by paths crossing the cold partition", bb->index);
2571 : else
2572 319 : BB_SET_PARTITION (bb, BB_COLD_PARTITION);
2573 319 : bbs_to_fix.safe_push (bb);
2574 : }
2575 :
2576 506363 : return bbs_to_fix;
2577 506363 : }
2578 :
2579 : /* Perform cleanup on the hot/cold bb partitioning after optimization
2580 : passes that modify the cfg. */
2581 :
2582 : void
2583 13140027 : fixup_partitions (void)
2584 : {
2585 13140027 : if (!crtl->has_bb_partition)
2586 12759107 : return;
2587 :
2588 : /* Delete any blocks that became unreachable and weren't
2589 : already cleaned up, for example during edge forwarding
2590 : and convert_jumps_to_returns. This will expose more
2591 : opportunities for fixing the partition boundaries here.
2592 : Also, the calculation of the dominance graph during verification
2593 : will assert if there are unreachable nodes. */
2594 380920 : delete_unreachable_blocks ();
2595 :
2596 : /* If there are partitions, do a sanity check on them: A basic block in
2597 : Â a cold partition cannot dominate a basic block in a hot partition.
2598 : Fixup any that now violate this requirement, as a result of edge
2599 : forwarding and unreachable block deletion. Â */
2600 380920 : auto_vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2601 :
2602 : /* Do the partition fixup after all necessary blocks have been converted to
2603 : cold, so that we only update the region crossings the minimum number of
2604 : places, which can require forcing edges to be non fallthru. */
2605 381200 : if (! bbs_to_fix.is_empty ())
2606 : {
2607 319 : do
2608 : {
2609 319 : basic_block bb = bbs_to_fix.pop ();
2610 319 : fixup_new_cold_bb (bb);
2611 : }
2612 599 : while (! bbs_to_fix.is_empty ());
2613 :
2614 : /* Fix up hot cold block grouping if needed. */
2615 280 : if (crtl->bb_reorder_complete && current_ir_type () == IR_RTL_CFGRTL)
2616 : {
2617 0 : basic_block bb, first = NULL, second = NULL;
2618 0 : int current_partition = BB_UNPARTITIONED;
2619 :
2620 0 : FOR_EACH_BB_FN (bb, cfun)
2621 : {
2622 0 : if (current_partition != BB_UNPARTITIONED
2623 0 : && BB_PARTITION (bb) != current_partition)
2624 : {
2625 0 : if (first == NULL)
2626 : first = bb;
2627 0 : else if (second == NULL)
2628 : second = bb;
2629 : else
2630 : {
2631 : /* If we switch partitions for the 3rd, 5th etc. time,
2632 : move bbs first (inclusive) .. second (exclusive) right
2633 : before bb. */
2634 0 : basic_block prev_first = first->prev_bb;
2635 0 : basic_block prev_second = second->prev_bb;
2636 0 : basic_block prev_bb = bb->prev_bb;
2637 0 : prev_first->next_bb = second;
2638 0 : second->prev_bb = prev_first;
2639 0 : prev_second->next_bb = bb;
2640 0 : bb->prev_bb = prev_second;
2641 0 : prev_bb->next_bb = first;
2642 0 : first->prev_bb = prev_bb;
2643 0 : rtx_insn *prev_first_insn = PREV_INSN (BB_HEAD (first));
2644 0 : rtx_insn *prev_second_insn
2645 0 : = PREV_INSN (BB_HEAD (second));
2646 0 : rtx_insn *prev_bb_insn = PREV_INSN (BB_HEAD (bb));
2647 0 : SET_NEXT_INSN (prev_first_insn) = BB_HEAD (second);
2648 0 : SET_PREV_INSN (BB_HEAD (second)) = prev_first_insn;
2649 0 : SET_NEXT_INSN (prev_second_insn) = BB_HEAD (bb);
2650 0 : SET_PREV_INSN (BB_HEAD (bb)) = prev_second_insn;
2651 0 : SET_NEXT_INSN (prev_bb_insn) = BB_HEAD (first);
2652 0 : SET_PREV_INSN (BB_HEAD (first)) = prev_bb_insn;
2653 0 : second = NULL;
2654 : }
2655 : }
2656 0 : current_partition = BB_PARTITION (bb);
2657 : }
2658 0 : gcc_assert (!second);
2659 : }
2660 : }
2661 380920 : }
2662 :
2663 : /* Verify, in the basic block chain, that there is at most one switch
2664 : between hot/cold partitions. This condition will not be true until
2665 : after reorder_basic_blocks is called. */
2666 :
2667 : static bool
2668 64338412 : verify_hot_cold_block_grouping (void)
2669 : {
2670 64338412 : basic_block bb;
2671 64338412 : bool err = false;
2672 64338412 : bool switched_sections = false;
2673 64338412 : int current_partition = BB_UNPARTITIONED;
2674 :
2675 : /* Even after bb reordering is complete, we go into cfglayout mode
2676 : again (in compgoto). Ensure we don't call this before going back
2677 : into linearized RTL when any layout fixes would have been committed. */
2678 64338412 : if (!crtl->bb_reorder_complete
2679 64338412 : || current_ir_type () != IR_RTL_CFGRTL)
2680 : return err;
2681 :
2682 132291888 : FOR_EACH_BB_FN (bb, cfun)
2683 : {
2684 124862350 : if (current_partition != BB_UNPARTITIONED
2685 51743466 : && BB_PARTITION (bb) != current_partition)
2686 : {
2687 740974 : if (switched_sections)
2688 : {
2689 0 : error ("multiple hot/cold transitions found (bb %i)",
2690 : bb->index);
2691 0 : err = true;
2692 : }
2693 : else
2694 : switched_sections = true;
2695 :
2696 740974 : if (!crtl->has_bb_partition)
2697 0 : error ("partition found but function partition flag not set");
2698 : }
2699 124862350 : current_partition = BB_PARTITION (bb);
2700 : }
2701 :
2702 : return err;
2703 : }
2704 :
2705 :
2706 : /* Perform several checks on the edges out of each block, such as
2707 : the consistency of the branch probabilities, the correctness
2708 : of hot/cold partition crossing edges, and the number of expected
2709 : successor edges. Also verify that the dominance relationship
2710 : between hot/cold blocks is sane. */
2711 :
2712 : static bool
2713 101463331 : rtl_verify_edges (void)
2714 : {
2715 101463331 : bool err = false;
2716 101463331 : basic_block bb;
2717 101463331 : auto_bitmap succ_dests;
2718 101463331 : auto_bitmap table_dests;
2719 :
2720 1202454438 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
2721 : {
2722 1100991107 : int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2723 1100991107 : int n_eh = 0, n_abnormal = 0;
2724 1100991107 : edge e, fallthru = NULL;
2725 1100991107 : edge_iterator ei;
2726 1100991107 : rtx note;
2727 1100991107 : bool has_crossing_edge = false;
2728 :
2729 1100991107 : if (JUMP_P (BB_END (bb))
2730 645673537 : && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2731 443678522 : && EDGE_COUNT (bb->succs) >= 2
2732 1544669629 : && any_condjump_p (BB_END (bb)))
2733 : {
2734 443678522 : if (!BRANCH_EDGE (bb)->probability.initialized_p ())
2735 : {
2736 182937 : if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
2737 : {
2738 0 : error ("verify_flow_info: "
2739 : "REG_BR_PROB is set but cfg probability is not");
2740 0 : err = true;
2741 : }
2742 : }
2743 443495585 : else if (XINT (note, 0)
2744 443495585 : != BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ()
2745 443495585 : && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2746 : {
2747 0 : error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2748 : XINT (note, 0),
2749 0 : BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ());
2750 0 : err = true;
2751 : }
2752 : }
2753 :
2754 2704942982 : FOR_EACH_EDGE (e, ei, bb->succs)
2755 : {
2756 1603951875 : bool is_crossing;
2757 :
2758 1603951875 : if (e->flags & EDGE_FALLTHRU)
2759 875188384 : n_fallthru++, fallthru = e;
2760 :
2761 3207903750 : is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2762 36807017 : && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2763 1640758892 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2764 1603951875 : has_crossing_edge |= is_crossing;
2765 1603951875 : if (e->flags & EDGE_CROSSING)
2766 : {
2767 20644735 : if (!is_crossing)
2768 : {
2769 0 : error ("EDGE_CROSSING incorrectly set across same section");
2770 0 : err = true;
2771 : }
2772 20644735 : if (e->flags & EDGE_FALLTHRU)
2773 : {
2774 0 : error ("fallthru edge crosses section boundary in bb %i",
2775 0 : e->src->index);
2776 0 : err = true;
2777 : }
2778 20644735 : if (e->flags & EDGE_EH)
2779 : {
2780 0 : error ("EH edge crosses section boundary in bb %i",
2781 0 : e->src->index);
2782 0 : err = true;
2783 : }
2784 20644735 : if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2785 : {
2786 0 : error ("No region crossing jump at section boundary in bb %i",
2787 : bb->index);
2788 0 : err = true;
2789 : }
2790 : }
2791 1583307140 : else if (is_crossing)
2792 : {
2793 0 : error ("EDGE_CROSSING missing across section boundary");
2794 0 : err = true;
2795 : }
2796 :
2797 1603951875 : if ((e->flags & ~(EDGE_DFS_BACK
2798 : | EDGE_CAN_FALLTHRU
2799 : | EDGE_IRREDUCIBLE_LOOP
2800 : | EDGE_LOOP_EXIT
2801 : | EDGE_CROSSING
2802 : | EDGE_PRESERVE)) == 0)
2803 652695162 : n_branch++;
2804 :
2805 1603951875 : if (e->flags & EDGE_ABNORMAL_CALL)
2806 53999801 : n_abnormal_call++;
2807 :
2808 1603951875 : if (e->flags & EDGE_SIBCALL)
2809 10652732 : n_sibcall++;
2810 :
2811 1603951875 : if (e->flags & EDGE_EH)
2812 63531058 : n_eh++;
2813 :
2814 1603951875 : if (e->flags & EDGE_ABNORMAL)
2815 75651366 : n_abnormal++;
2816 : }
2817 :
2818 1100991107 : if (!has_crossing_edge
2819 1080354968 : && JUMP_P (BB_END (bb))
2820 1726032906 : && CROSSING_JUMP_P (BB_END (bb)))
2821 : {
2822 0 : print_rtl_with_bb (stderr, get_insns (), TDF_BLOCKS | TDF_DETAILS);
2823 0 : error ("Region crossing jump across same section in bb %i",
2824 : bb->index);
2825 0 : err = true;
2826 : }
2827 :
2828 1100991107 : if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2829 : {
2830 0 : error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2831 0 : err = true;
2832 : }
2833 1100991107 : if (n_eh > 1)
2834 : {
2835 0 : error ("too many exception handling edges in bb %i", bb->index);
2836 0 : err = true;
2837 : }
2838 1100991107 : if (n_branch
2839 1100991107 : && (!JUMP_P (BB_END (bb))
2840 645568395 : || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2841 733698 : || any_condjump_p (BB_END (bb))))))
2842 : {
2843 0 : error ("too many outgoing branch edges from bb %i", bb->index);
2844 0 : err = true;
2845 : }
2846 1100991107 : if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2847 : {
2848 0 : error ("fallthru edge after unconditional jump in bb %i", bb->index);
2849 0 : err = true;
2850 : }
2851 :
2852 : /* Compare each shared dispatch's normal successors with its table
2853 : entries and optional out-of-range destination. */
2854 1100991107 : rtx_jump_table_data *table;
2855 1100991107 : if (shared_tablejump_p (BB_END (bb), NULL, &table))
2856 : {
2857 52276 : bitmap_clear (succ_dests);
2858 52276 : bitmap_clear (table_dests);
2859 656514 : FOR_EACH_EDGE (e, ei, bb->succs)
2860 : {
2861 604238 : bitmap_set_bit (succ_dests, e->dest->index);
2862 604238 : if (e->flags & (EDGE_ABNORMAL | EDGE_EH))
2863 0 : bitmap_set_bit (table_dests, e->dest->index);
2864 : }
2865 :
2866 1193064 : auto add_destination = [&] (rtx lab)
2867 : {
2868 1140788 : basic_block dest = (LABEL_P (lab)
2869 1140788 : ? BLOCK_FOR_INSN (as_a <rtx_insn *> (lab))
2870 1140788 : : NULL);
2871 1140788 : if (dest)
2872 1140788 : bitmap_set_bit (table_dests, dest->index);
2873 : else
2874 : {
2875 0 : error ("jump table of bb %i has an invalid destination",
2876 0 : bb->index);
2877 0 : err = true;
2878 : }
2879 1193064 : };
2880 52276 : rtvec vec = table->get_labels ();
2881 1193064 : for (int j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
2882 1140788 : add_destination (XEXP (RTVEC_ELT (vec, j), 0));
2883 :
2884 52276 : rtx casesi = tablejump_casesi_pattern (BB_END (bb));
2885 52276 : if (casesi)
2886 0 : add_destination (label_ref_label (XEXP (SET_SRC (casesi), 2)));
2887 :
2888 52276 : if (!bitmap_equal_p (succ_dests, table_dests))
2889 : {
2890 0 : error ("jump table of bb %i does not match its successors",
2891 : bb->index);
2892 0 : err = true;
2893 : }
2894 : }
2895 1100991107 : if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2896 : {
2897 0 : error ("wrong number of branch edges after unconditional jump"
2898 : " in bb %i", bb->index);
2899 0 : err = true;
2900 : }
2901 456156410 : if (n_branch != 1 && any_condjump_p (BB_END (bb))
2902 1100992430 : && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2903 : {
2904 0 : error ("wrong amount of branch edges after conditional jump"
2905 : " in bb %i", bb->index);
2906 0 : err = true;
2907 : }
2908 1100991107 : if (n_abnormal_call && !CALL_P (BB_END (bb)))
2909 : {
2910 0 : error ("abnormal call edges for non-call insn in bb %i", bb->index);
2911 0 : err = true;
2912 : }
2913 1100991107 : if (n_sibcall && !CALL_P (BB_END (bb)))
2914 : {
2915 0 : error ("sibcall edges for non-call insn in bb %i", bb->index);
2916 0 : err = true;
2917 : }
2918 1100991107 : if (n_abnormal > n_eh
2919 10861242 : && !(CALL_P (BB_END (bb))
2920 10839128 : && n_abnormal == n_abnormal_call + n_sibcall)
2921 1101013221 : && (!JUMP_P (BB_END (bb))
2922 22114 : || any_condjump_p (BB_END (bb))
2923 22114 : || any_uncondjump_p (BB_END (bb))))
2924 : {
2925 0 : error ("abnormal edges for no purpose in bb %i", bb->index);
2926 0 : err = true;
2927 : }
2928 :
2929 1100991107 : int has_eh = -1;
2930 2698409449 : FOR_EACH_EDGE (e, ei, bb->preds)
2931 : {
2932 1597418342 : if (has_eh == -1)
2933 1100870483 : has_eh = (e->flags & EDGE_EH);
2934 1597418342 : if ((e->flags & EDGE_EH) == has_eh)
2935 1597418342 : continue;
2936 0 : error ("EH incoming edge mixed with non-EH incoming edges "
2937 : "in bb %i", bb->index);
2938 0 : err = true;
2939 0 : break;
2940 : }
2941 : }
2942 :
2943 : /* If there are partitions, do a sanity check on them: A basic block in
2944 : Â a cold partition cannot dominate a basic block in a hot partition. Â */
2945 3031255 : if (crtl->has_bb_partition && !err
2946 104494586 : && current_ir_type () == IR_RTL_CFGLAYOUT)
2947 : {
2948 125443 : auto_vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2949 250886 : err = !bbs_to_fix.is_empty ();
2950 125443 : }
2951 :
2952 : /* Clean up. */
2953 101463331 : return err;
2954 101463331 : }
2955 :
2956 : /* Checks on the instructions within blocks. Currently checks that each
2957 : block starts with a basic block note, and that basic block notes and
2958 : control flow jumps are not found in the middle of the block. */
2959 :
2960 : static bool
2961 101463331 : rtl_verify_bb_insns (void)
2962 : {
2963 101463331 : rtx_insn *x;
2964 101463331 : bool err = false;
2965 101463331 : basic_block bb;
2966 :
2967 1202454438 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
2968 : {
2969 : /* Now check the header of basic
2970 : block. It ought to contain optional CODE_LABEL followed
2971 : by NOTE_BASIC_BLOCK. */
2972 1100991107 : x = BB_HEAD (bb);
2973 1100991107 : if (LABEL_P (x))
2974 : {
2975 530945094 : if (BB_END (bb) == x)
2976 : {
2977 0 : error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2978 : bb->index);
2979 0 : err = true;
2980 : }
2981 :
2982 530945094 : x = NEXT_INSN (x);
2983 : }
2984 :
2985 2201982214 : if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2986 : {
2987 0 : error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2988 : bb->index);
2989 0 : err = true;
2990 : }
2991 :
2992 1100991107 : if (BB_END (bb) == x)
2993 : /* Do checks for empty blocks here. */
2994 : ;
2995 : else
2996 12675647763 : for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2997 : {
2998 11593537321 : if (NOTE_INSN_BASIC_BLOCK_P (x))
2999 : {
3000 0 : error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
3001 0 : INSN_UID (x), bb->index);
3002 0 : err = true;
3003 : }
3004 :
3005 11593537321 : if (x == BB_END (bb))
3006 : break;
3007 :
3008 10511426879 : if (control_flow_insn_p (x))
3009 : {
3010 0 : error ("in basic block %d:", bb->index);
3011 0 : fatal_insn ("flow control insn inside a basic block", x);
3012 : }
3013 : }
3014 : }
3015 :
3016 : /* Clean up. */
3017 101463331 : return err;
3018 : }
3019 :
3020 : /* Verify that block pointers for instructions in basic blocks, headers and
3021 : footers are set appropriately. */
3022 :
3023 : static bool
3024 101463331 : rtl_verify_bb_pointers (void)
3025 : {
3026 101463331 : bool err = false;
3027 101463331 : basic_block bb;
3028 :
3029 : /* Check the general integrity of the basic blocks. */
3030 1202454438 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
3031 : {
3032 1100991107 : rtx_insn *insn;
3033 :
3034 1100991107 : if (!(bb->flags & BB_RTL))
3035 : {
3036 0 : error ("BB_RTL flag not set for block %d", bb->index);
3037 0 : err = true;
3038 : }
3039 :
3040 14326464629 : FOR_BB_INSNS (bb, insn)
3041 13225473522 : if (BLOCK_FOR_INSN (insn) != bb)
3042 : {
3043 0 : error ("insn %d basic block pointer is %d, should be %d",
3044 0 : INSN_UID (insn),
3045 0 : BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
3046 : bb->index);
3047 0 : err = true;
3048 : }
3049 :
3050 1101573669 : for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
3051 582562 : if (!BARRIER_P (insn)
3052 582562 : && BLOCK_FOR_INSN (insn) != NULL)
3053 : {
3054 0 : error ("insn %d in header of bb %d has non-NULL basic block",
3055 0 : INSN_UID (insn), bb->index);
3056 0 : err = true;
3057 : }
3058 1130624335 : for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
3059 29633228 : if (!BARRIER_P (insn)
3060 29633228 : && BLOCK_FOR_INSN (insn) != NULL)
3061 : {
3062 0 : error ("insn %d in footer of bb %d has non-NULL basic block",
3063 0 : INSN_UID (insn), bb->index);
3064 0 : err = true;
3065 : }
3066 : }
3067 :
3068 : /* Clean up. */
3069 101463331 : return err;
3070 : }
3071 :
3072 : /* Verify the CFG and RTL consistency common for both underlying RTL and
3073 : cfglayout RTL.
3074 :
3075 : Currently it does following checks:
3076 :
3077 : - overlapping of basic blocks
3078 : - insns with wrong BLOCK_FOR_INSN pointers
3079 : - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
3080 : - tails of basic blocks (ensure that boundary is necessary)
3081 : - scans body of the basic block for JUMP_INSN, CODE_LABEL
3082 : and NOTE_INSN_BASIC_BLOCK
3083 : - verify that no fall_thru edge crosses hot/cold partition boundaries
3084 : - verify that there are no pending RTL branch predictions
3085 : - verify that hot blocks are not dominated by cold blocks
3086 :
3087 : In future it can be extended check a lot of other stuff as well
3088 : (reachability of basic blocks, life information, etc. etc.). */
3089 :
3090 : static bool
3091 101463331 : rtl_verify_flow_info_1 (void)
3092 : {
3093 101463331 : bool err = false;
3094 :
3095 101463331 : if (rtl_verify_bb_pointers ())
3096 : err = true;
3097 :
3098 101463331 : if (rtl_verify_bb_insns ())
3099 0 : err = true;
3100 :
3101 101463331 : if (rtl_verify_edges ())
3102 0 : err = true;
3103 :
3104 101463331 : return err;
3105 : }
3106 :
3107 : /* Walk the instruction chain and verify that bb head/end pointers
3108 : are correct, and that instructions are in exactly one bb and have
3109 : correct block pointers. */
3110 :
3111 : static bool
3112 64338412 : rtl_verify_bb_insn_chain (void)
3113 : {
3114 64338412 : basic_block bb;
3115 64338412 : bool err = false;
3116 64338412 : rtx_insn *x;
3117 64338412 : rtx_insn *last_head = get_last_insn ();
3118 64338412 : basic_block *bb_info;
3119 64338412 : const int max_uid = get_max_uid ();
3120 :
3121 64338412 : bb_info = XCNEWVEC (basic_block, max_uid);
3122 :
3123 738761523 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
3124 : {
3125 674423111 : rtx_insn *head = BB_HEAD (bb);
3126 674423111 : rtx_insn *end = BB_END (bb);
3127 :
3128 939608866 : for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
3129 : {
3130 : /* Verify the end of the basic block is in the INSN chain. */
3131 939608866 : if (x == end)
3132 : break;
3133 :
3134 : /* And that the code outside of basic blocks has NULL bb field. */
3135 265185755 : if (!BARRIER_P (x)
3136 265185755 : && BLOCK_FOR_INSN (x) != NULL)
3137 : {
3138 0 : error ("insn %d outside of basic blocks has non-NULL bb field",
3139 0 : INSN_UID (x));
3140 0 : err = true;
3141 : }
3142 : }
3143 :
3144 674423111 : if (!x)
3145 : {
3146 0 : error ("end insn %d for block %d not found in the insn stream",
3147 0 : INSN_UID (end), bb->index);
3148 0 : err = true;
3149 : }
3150 :
3151 : /* Work backwards from the end to the head of the basic block
3152 : to verify the head is in the RTL chain. */
3153 8060615137 : for (; x != NULL_RTX; x = PREV_INSN (x))
3154 : {
3155 : /* While walking over the insn chain, verify insns appear
3156 : in only one basic block. */
3157 8060615137 : if (bb_info[INSN_UID (x)] != NULL)
3158 : {
3159 0 : error ("insn %d is in multiple basic blocks (%d and %d)",
3160 : INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
3161 0 : err = true;
3162 : }
3163 :
3164 8060615137 : bb_info[INSN_UID (x)] = bb;
3165 :
3166 8060615137 : if (x == head)
3167 : break;
3168 : }
3169 674423111 : if (!x)
3170 : {
3171 0 : error ("head insn %d for block %d not found in the insn stream",
3172 0 : INSN_UID (head), bb->index);
3173 0 : err = true;
3174 : }
3175 :
3176 674423111 : last_head = PREV_INSN (x);
3177 : }
3178 :
3179 129707772 : for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
3180 : {
3181 : /* Check that the code before the first basic block has NULL
3182 : bb field. */
3183 65369360 : if (!BARRIER_P (x)
3184 65369360 : && BLOCK_FOR_INSN (x) != NULL)
3185 : {
3186 0 : error ("insn %d outside of basic blocks has non-NULL bb field",
3187 0 : INSN_UID (x));
3188 0 : err = true;
3189 : }
3190 : }
3191 64338412 : free (bb_info);
3192 :
3193 64338412 : return err;
3194 : }
3195 :
3196 : /* Verify that fallthru edges point to adjacent blocks in layout order and
3197 : that barriers exist after non-fallthru blocks. */
3198 :
3199 : static bool
3200 64338412 : rtl_verify_fallthru (void)
3201 : {
3202 64338412 : basic_block bb;
3203 64338412 : bool err = false;
3204 :
3205 738761523 : FOR_EACH_BB_REVERSE_FN (bb, cfun)
3206 : {
3207 674423111 : edge e;
3208 :
3209 674423111 : e = find_fallthru_edge (bb->succs);
3210 674423111 : if (!e)
3211 : {
3212 197035463 : rtx_insn *insn;
3213 :
3214 : /* Ensure existence of barrier in BB with no fallthru edges. */
3215 197601330 : for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
3216 : {
3217 197601330 : if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
3218 : {
3219 0 : error ("missing barrier after block %i", bb->index);
3220 0 : err = true;
3221 0 : break;
3222 : }
3223 197601330 : if (BARRIER_P (insn))
3224 : break;
3225 : }
3226 : }
3227 477387648 : else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
3228 477387648 : && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
3229 : {
3230 446456386 : rtx_insn *insn;
3231 :
3232 446456386 : if (e->src->next_bb != e->dest)
3233 : {
3234 0 : error
3235 0 : ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
3236 : e->src->index, e->dest->index);
3237 0 : err = true;
3238 : }
3239 : else
3240 899729639 : for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
3241 6816867 : insn = NEXT_INSN (insn))
3242 6816867 : if (BARRIER_P (insn) || NONDEBUG_INSN_P (insn))
3243 : {
3244 0 : error ("verify_flow_info: Incorrect fallthru %i->%i",
3245 0 : e->src->index, e->dest->index);
3246 0 : error ("wrong insn in the fallthru edge");
3247 0 : debug_rtx (insn);
3248 0 : err = true;
3249 : }
3250 : }
3251 : }
3252 :
3253 64338412 : return err;
3254 : }
3255 :
3256 : /* Verify that blocks are laid out in consecutive order. While walking the
3257 : instructions, verify that all expected instructions are inside the basic
3258 : blocks, and that all returns are followed by barriers. */
3259 :
3260 : static bool
3261 64338412 : rtl_verify_bb_layout (void)
3262 : {
3263 64338412 : basic_block bb;
3264 64338412 : bool err = false;
3265 64338412 : rtx_insn *x, *y;
3266 64338412 : int num_bb_notes;
3267 64338412 : rtx_insn * const rtx_first = get_insns ();
3268 64338412 : basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
3269 :
3270 64338412 : num_bb_notes = 0;
3271 :
3272 8455111908 : for (x = rtx_first; x; x = NEXT_INSN (x))
3273 : {
3274 8390773496 : if (NOTE_INSN_BASIC_BLOCK_P (x))
3275 : {
3276 674423111 : bb = NOTE_BASIC_BLOCK (x);
3277 :
3278 674423111 : num_bb_notes++;
3279 674423111 : if (bb != last_bb_seen->next_bb)
3280 0 : internal_error ("basic blocks not laid down consecutively");
3281 :
3282 : curr_bb = last_bb_seen = bb;
3283 : }
3284 :
3285 8390773496 : if (!curr_bb)
3286 : {
3287 649358650 : switch (GET_CODE (x))
3288 : {
3289 : case BARRIER:
3290 : case NOTE:
3291 : break;
3292 :
3293 319597047 : case CODE_LABEL:
3294 : /* An ADDR_VEC is placed outside any basic block. */
3295 319597047 : if (NEXT_INSN (x)
3296 319597047 : && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
3297 : x = NEXT_INSN (x);
3298 :
3299 : /* But in any case, non-deletable labels can appear anywhere. */
3300 : break;
3301 :
3302 0 : default:
3303 0 : fatal_insn ("insn outside basic block", x);
3304 : }
3305 : }
3306 :
3307 8390773496 : if (JUMP_P (x)
3308 450137156 : && returnjump_p (x) && ! condjump_p (x)
3309 8422901206 : && ! ((y = next_nonnote_nondebug_insn (x))
3310 32127710 : && BARRIER_P (y)))
3311 0 : fatal_insn ("return not followed by barrier", x);
3312 :
3313 8390773496 : if (curr_bb && x == BB_END (curr_bb))
3314 1323781761 : curr_bb = NULL;
3315 : }
3316 :
3317 64338412 : if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
3318 0 : internal_error
3319 0 : ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
3320 : num_bb_notes, n_basic_blocks_for_fn (cfun));
3321 :
3322 64338412 : return err;
3323 : }
3324 :
3325 : /* Verify the CFG and RTL consistency common for both underlying RTL and
3326 : cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3327 :
3328 : Currently it does following checks:
3329 : - all checks of rtl_verify_flow_info_1
3330 : - test head/end pointers
3331 : - check that blocks are laid out in consecutive order
3332 : - check that all insns are in the basic blocks
3333 : (except the switch handling code, barriers and notes)
3334 : - check that all returns are followed by barriers
3335 : - check that all fallthru edge points to the adjacent blocks
3336 : - verify that there is a single hot/cold partition boundary after bbro */
3337 :
3338 : static bool
3339 64338412 : rtl_verify_flow_info (void)
3340 : {
3341 64338412 : bool err = false;
3342 :
3343 64338412 : if (rtl_verify_flow_info_1 ())
3344 : err = true;
3345 :
3346 64338412 : if (rtl_verify_bb_insn_chain ())
3347 0 : err = true;
3348 :
3349 64338412 : if (rtl_verify_fallthru ())
3350 0 : err = true;
3351 :
3352 64338412 : if (rtl_verify_bb_layout ())
3353 : err = true;
3354 :
3355 64338412 : if (verify_hot_cold_block_grouping ())
3356 0 : err = true;
3357 :
3358 64338412 : return err;
3359 : }
3360 :
3361 : /* Assume that the preceding pass has possibly eliminated jump instructions
3362 : or converted the unconditional jumps. Eliminate the edges from CFG.
3363 : Return true if any edges are eliminated. */
3364 :
3365 : bool
3366 75694617 : purge_dead_edges (basic_block bb)
3367 : {
3368 75694617 : edge e;
3369 75694617 : rtx_insn *insn = BB_END (bb);
3370 75694617 : rtx note;
3371 75694617 : bool purged = false;
3372 75694617 : bool found;
3373 75694617 : edge_iterator ei;
3374 :
3375 75694617 : if ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb))
3376 17232969 : do
3377 17232969 : insn = PREV_INSN (insn);
3378 17232969 : while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3379 :
3380 : /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3381 75694617 : if (NONJUMP_INSN_P (insn)
3382 75694617 : && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3383 : {
3384 1363081 : rtx eqnote;
3385 :
3386 1363081 : if (! may_trap_p (PATTERN (insn))
3387 1363081 : || ((eqnote = find_reg_equal_equiv_note (insn))
3388 167 : && ! may_trap_p (XEXP (eqnote, 0))))
3389 43915 : remove_note (insn, note);
3390 : }
3391 : /* A tail call cannot trap either. The tailc/musttail pass could have
3392 : allowed a tail call if it could throw internally, but perform no
3393 : actual statements and then caused the exception to be thrown externally
3394 : in the hope that it is cleaned up later. If it is not, just
3395 : remove REG_EH_REGION note. While the call maybe can throw, the
3396 : current function's frame will not be there anymore when it does. */
3397 75694617 : auto call = dyn_cast<rtx_call_insn *> (insn);
3398 9491407 : if (call
3399 9491407 : && SIBLING_CALL_P (call)
3400 521959 : && (note = find_reg_note (call, REG_EH_REGION, NULL)))
3401 83695 : remove_note (call, note);
3402 :
3403 : /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3404 181792084 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3405 : {
3406 106097467 : bool remove = false;
3407 :
3408 : /* There are three types of edges we need to handle correctly here: EH
3409 : edges, abnormal call EH edges, and abnormal call non-EH edges. The
3410 : latter can appear when nonlocal gotos are used. */
3411 106097467 : if (e->flags & EDGE_ABNORMAL_CALL)
3412 : {
3413 3502552 : if (!CALL_P (insn))
3414 : remove = true;
3415 3502547 : else if (can_nonlocal_goto (insn))
3416 : ;
3417 3426407 : else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3418 : ;
3419 0 : else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3420 : ;
3421 : else
3422 : remove = true;
3423 : }
3424 102594915 : else if (e->flags & EDGE_EH)
3425 1987171 : remove = !can_throw_internal (insn);
3426 :
3427 1987171 : if (remove)
3428 : {
3429 402687 : remove_edge (e);
3430 402687 : df_set_bb_dirty (bb);
3431 402687 : purged = true;
3432 : }
3433 : else
3434 105694780 : ei_next (&ei);
3435 : }
3436 :
3437 75694617 : if (JUMP_P (insn))
3438 : {
3439 40845712 : rtx note;
3440 40845712 : edge b,f;
3441 40845712 : edge_iterator ei;
3442 :
3443 : /* We do care only about conditional jumps and simplejumps. */
3444 40845712 : if (!any_condjump_p (insn)
3445 13205199 : && !returnjump_p (insn)
3446 50370713 : && !simplejump_p (insn))
3447 : return purged;
3448 :
3449 : /* Branch probability/prediction notes are defined only for
3450 : condjumps. We've possibly turned condjump into simplejump. */
3451 40803045 : if (simplejump_p (insn))
3452 : {
3453 9482334 : note = find_reg_note (insn, REG_BR_PROB, NULL);
3454 9482334 : if (note)
3455 3802 : remove_note (insn, note);
3456 9482334 : while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3457 0 : remove_note (insn, note);
3458 : }
3459 :
3460 109258148 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3461 : {
3462 : /* Avoid abnormal flags to leak from computed jumps turned
3463 : into simplejumps. */
3464 :
3465 68455103 : e->flags &= ~EDGE_ABNORMAL;
3466 :
3467 : /* See if this edge is one we should keep. */
3468 68455103 : if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3469 : /* A conditional jump can fall through into the next
3470 : block, so we should keep the edge. */
3471 : {
3472 27640513 : ei_next (&ei);
3473 27640513 : continue;
3474 : }
3475 40814590 : else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3476 37134392 : && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3477 : /* If the destination block is the target of the jump,
3478 : keep the edge. */
3479 : {
3480 37120403 : ei_next (&ei);
3481 37120403 : continue;
3482 : }
3483 7374385 : else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3484 3694187 : && returnjump_p (insn))
3485 : /* If the destination block is the exit block, and this
3486 : instruction is a return, then keep the edge. */
3487 : {
3488 3680198 : ei_next (&ei);
3489 3680198 : continue;
3490 : }
3491 13989 : else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3492 : /* Keep the edges that correspond to exceptions thrown by
3493 : this instruction and rematerialize the EDGE_ABNORMAL
3494 : flag we just cleared above. */
3495 : {
3496 0 : e->flags |= EDGE_ABNORMAL;
3497 0 : ei_next (&ei);
3498 0 : continue;
3499 : }
3500 :
3501 : /* We do not need this edge. */
3502 13989 : df_set_bb_dirty (bb);
3503 13989 : purged = true;
3504 13989 : remove_edge (e);
3505 : }
3506 :
3507 40997031 : if (EDGE_COUNT (bb->succs) == 0 || !purged)
3508 : return purged;
3509 :
3510 151319 : if (dump_file)
3511 0 : fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3512 :
3513 151319 : if (!optimize)
3514 : return purged;
3515 :
3516 : /* Redistribute probabilities. */
3517 150711 : if (single_succ_p (bb))
3518 : {
3519 150711 : single_succ_edge (bb)->probability = profile_probability::always ();
3520 : }
3521 : else
3522 : {
3523 0 : note = find_reg_note (insn, REG_BR_PROB, NULL);
3524 0 : if (!note)
3525 : return purged;
3526 :
3527 0 : b = BRANCH_EDGE (bb);
3528 0 : f = FALLTHRU_EDGE (bb);
3529 0 : b->probability = profile_probability::from_reg_br_prob_note
3530 0 : (XINT (note, 0));
3531 0 : f->probability = b->probability.invert ();
3532 : }
3533 :
3534 : return purged;
3535 : }
3536 34848905 : else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3537 : {
3538 : /* First, there should not be any EH or ABCALL edges resulting
3539 : from non-local gotos and the like. If there were, we shouldn't
3540 : have created the sibcall in the first place. Second, there
3541 : should of course never have been a fallthru edge. */
3542 521959 : gcc_assert (single_succ_p (bb));
3543 521959 : gcc_assert (single_succ_edge (bb)->flags
3544 : == (EDGE_SIBCALL | EDGE_ABNORMAL));
3545 :
3546 : return false;
3547 : }
3548 :
3549 : /* If we don't see a jump insn, we don't know exactly why the block would
3550 : have been broken at this point. Look for a simple, non-fallthru edge,
3551 : as these are only created by conditional branches. If we find such an
3552 : edge we know that there used to be a jump here and can then safely
3553 : remove all non-fallthru edges. */
3554 34326946 : found = false;
3555 70224480 : FOR_EACH_EDGE (e, ei, bb->succs)
3556 36193311 : if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3557 : {
3558 : found = true;
3559 : break;
3560 : }
3561 :
3562 34326946 : if (!found)
3563 : return purged;
3564 :
3565 : /* Remove all but the fake and fallthru edges. The fake edge may be
3566 : the only successor for this block in the case of noreturn
3567 : calls. */
3568 887463 : for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3569 : {
3570 591686 : if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3571 : {
3572 295909 : df_set_bb_dirty (bb);
3573 295909 : remove_edge (e);
3574 295909 : purged = true;
3575 : }
3576 : else
3577 295777 : ei_next (&ei);
3578 : }
3579 :
3580 295777 : gcc_assert (single_succ_p (bb));
3581 :
3582 295777 : single_succ_edge (bb)->probability = profile_probability::always ();
3583 :
3584 295777 : if (dump_file)
3585 1 : fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3586 : bb->index);
3587 : return purged;
3588 : }
3589 :
3590 : /* Search all basic blocks for potentially dead edges and purge them. Return
3591 : true if some edge has been eliminated. */
3592 :
3593 : bool
3594 3423329 : purge_all_dead_edges (void)
3595 : {
3596 3423329 : bool purged = false;
3597 3423329 : basic_block bb;
3598 :
3599 50294733 : FOR_EACH_BB_FN (bb, cfun)
3600 46871404 : if (purge_dead_edges (bb))
3601 2438 : purged = true;
3602 :
3603 3423329 : return purged;
3604 : }
3605 :
3606 : /* This is used by a few passes that emit some instructions after abnormal
3607 : calls, moving the basic block's end, while they in fact do want to emit
3608 : them on the fallthru edge. Look for abnormal call edges, find backward
3609 : the call in the block and insert the instructions on the edge instead.
3610 :
3611 : Similarly, handle instructions throwing exceptions internally.
3612 :
3613 : Return true when instructions have been found and inserted on edges. */
3614 :
3615 : bool
3616 1552392 : fixup_abnormal_edges (void)
3617 : {
3618 1552392 : bool inserted = false;
3619 1552392 : basic_block bb;
3620 :
3621 17490415 : FOR_EACH_BB_FN (bb, cfun)
3622 : {
3623 15938023 : edge e;
3624 15938023 : edge_iterator ei;
3625 :
3626 : /* Look for cases we are interested in - calls or instructions causing
3627 : exceptions. */
3628 37503849 : FOR_EACH_EDGE (e, ei, bb->succs)
3629 22290142 : if ((e->flags & EDGE_ABNORMAL_CALL)
3630 21676439 : || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3631 : == (EDGE_ABNORMAL | EDGE_EH)))
3632 : break;
3633 :
3634 15938023 : if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3635 : {
3636 9676 : rtx_insn *insn;
3637 :
3638 : /* Get past the new insns generated. Allow notes, as the insns
3639 : may be already deleted. */
3640 9676 : insn = BB_END (bb);
3641 16532 : while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3642 15551 : && !can_throw_internal (insn)
3643 29734 : && insn != BB_HEAD (bb))
3644 8444 : insn = PREV_INSN (insn);
3645 :
3646 9676 : if (CALL_P (insn) || can_throw_internal (insn))
3647 : {
3648 6501 : rtx_insn *stop, *next;
3649 :
3650 6501 : e = find_fallthru_edge (bb->succs);
3651 :
3652 6501 : stop = NEXT_INSN (BB_END (bb));
3653 6501 : BB_END (bb) = insn;
3654 :
3655 21271 : for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3656 : {
3657 8269 : next = NEXT_INSN (insn);
3658 8269 : if (INSN_P (insn))
3659 : {
3660 7192 : delete_insn (insn);
3661 :
3662 : /* Sometimes there's still the return value USE.
3663 : If it's placed after a trapping call (i.e. that
3664 : call is the last insn anyway), we have no fallthru
3665 : edge. Simply delete this use and don't try to insert
3666 : on the non-existent edge.
3667 : Similarly, sometimes a call that can throw is
3668 : followed in the source with __builtin_unreachable (),
3669 : meaning that there is UB if the call returns rather
3670 : than throws. If there weren't any instructions
3671 : following such calls before, supposedly even the ones
3672 : we've deleted aren't significant and can be
3673 : removed. */
3674 7192 : if (e)
3675 : {
3676 : /* We're not deleting it, we're moving it. */
3677 7191 : insn->set_undeleted ();
3678 7191 : SET_PREV_INSN (insn) = NULL_RTX;
3679 7191 : SET_NEXT_INSN (insn) = NULL_RTX;
3680 :
3681 7191 : insert_insn_on_edge (insn, e);
3682 7191 : inserted = true;
3683 : }
3684 : }
3685 1077 : else if (!BARRIER_P (insn))
3686 1077 : set_block_for_insn (insn, NULL);
3687 : }
3688 : }
3689 :
3690 : /* It may be that we don't find any trapping insn. In this
3691 : case we discovered quite late that the insn that had been
3692 : marked as can_throw_internal in fact couldn't trap at all.
3693 : So we should in fact delete the EH edges out of the block. */
3694 : else
3695 3175 : purge_dead_edges (bb);
3696 : }
3697 : }
3698 :
3699 1552392 : return inserted;
3700 : }
3701 :
3702 : /* Delete the unconditional jump INSN and adjust the CFG correspondingly.
3703 : Note that the INSN should be deleted *after* removing dead edges, so
3704 : that the kept edge is the fallthrough edge for a (set (pc) (pc))
3705 : but not for a (set (pc) (label_ref FOO)). */
3706 :
3707 : void
3708 4314 : update_cfg_for_uncondjump (rtx_insn *insn)
3709 : {
3710 4314 : basic_block bb = BLOCK_FOR_INSN (insn);
3711 4314 : gcc_assert (BB_END (bb) == insn);
3712 :
3713 4314 : purge_dead_edges (bb);
3714 :
3715 4314 : if (current_ir_type () != IR_RTL_CFGLAYOUT)
3716 : {
3717 20 : if (!find_fallthru_edge (bb->succs))
3718 : {
3719 20 : auto barrier = next_nonnote_nondebug_insn (insn);
3720 20 : if (!barrier || !BARRIER_P (barrier))
3721 20 : emit_barrier_after (insn);
3722 : }
3723 : return;
3724 : }
3725 :
3726 4294 : delete_insn (insn);
3727 4294 : if (EDGE_COUNT (bb->succs) == 1)
3728 : {
3729 2164 : rtx_insn *insn;
3730 :
3731 2164 : single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
3732 :
3733 : /* Remove barriers from the footer if there are any. */
3734 2169 : for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
3735 5 : if (BARRIER_P (insn))
3736 : {
3737 0 : if (PREV_INSN (insn))
3738 0 : SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
3739 : else
3740 0 : BB_FOOTER (bb) = NEXT_INSN (insn);
3741 0 : if (NEXT_INSN (insn))
3742 0 : SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
3743 : }
3744 5 : else if (LABEL_P (insn))
3745 : break;
3746 : }
3747 : }
3748 :
3749 : /* Cut the insns from FIRST to LAST out of the insns stream. */
3750 :
3751 : rtx_insn *
3752 12127699 : unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3753 : {
3754 12127699 : rtx_insn *prevfirst = PREV_INSN (first);
3755 12127699 : rtx_insn *nextlast = NEXT_INSN (last);
3756 :
3757 12127699 : SET_PREV_INSN (first) = NULL;
3758 12127699 : SET_NEXT_INSN (last) = NULL;
3759 12127699 : if (prevfirst)
3760 9545315 : SET_NEXT_INSN (prevfirst) = nextlast;
3761 12127699 : if (nextlast)
3762 10650887 : SET_PREV_INSN (nextlast) = prevfirst;
3763 : else
3764 1476812 : set_last_insn (prevfirst);
3765 12127699 : if (!prevfirst)
3766 2582384 : set_first_insn (nextlast);
3767 12127699 : return first;
3768 : }
3769 :
3770 : /* Skip over inter-block insns occurring after BB which are typically
3771 : associated with BB (e.g., barriers). If there are any such insns,
3772 : we return the last one. Otherwise, we return the end of BB. */
3773 :
3774 : static rtx_insn *
3775 27081098 : skip_insns_after_block (basic_block bb)
3776 : {
3777 27081098 : rtx_insn *insn, *last_insn, *next_head, *prev;
3778 :
3779 27081098 : next_head = NULL;
3780 27081098 : if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3781 24498699 : next_head = BB_HEAD (bb->next_bb);
3782 :
3783 36074824 : for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3784 : {
3785 33492425 : if (insn == next_head)
3786 : break;
3787 :
3788 8993726 : switch (GET_CODE (insn))
3789 : {
3790 7878390 : case BARRIER:
3791 7878390 : last_insn = insn;
3792 7878390 : continue;
3793 :
3794 1100216 : case NOTE:
3795 1100216 : gcc_assert (NOTE_KIND (insn) != NOTE_INSN_BLOCK_END);
3796 1100216 : continue;
3797 :
3798 15120 : case CODE_LABEL:
3799 15120 : if (NEXT_INSN (insn)
3800 15120 : && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3801 : {
3802 15120 : insn = NEXT_INSN (insn);
3803 15120 : last_insn = insn;
3804 15120 : continue;
3805 : }
3806 : break;
3807 :
3808 : default:
3809 : break;
3810 : }
3811 :
3812 : break;
3813 : }
3814 :
3815 : /* It is possible to hit contradictory sequence. For instance:
3816 :
3817 : jump_insn
3818 : NOTE_INSN_BLOCK_BEG
3819 : barrier
3820 :
3821 : Where barrier belongs to jump_insn, but the note does not. This can be
3822 : created by removing the basic block originally following
3823 : NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3824 :
3825 34990793 : for (insn = last_insn; insn != BB_END (bb); insn = prev)
3826 : {
3827 7909695 : prev = PREV_INSN (insn);
3828 7909695 : if (NOTE_P (insn))
3829 1065 : switch (NOTE_KIND (insn))
3830 : {
3831 0 : case NOTE_INSN_BLOCK_END:
3832 0 : gcc_unreachable ();
3833 1065 : break;
3834 1065 : case NOTE_INSN_DELETED:
3835 1065 : case NOTE_INSN_DELETED_LABEL:
3836 1065 : case NOTE_INSN_DELETED_DEBUG_LABEL:
3837 1065 : continue;
3838 0 : default:
3839 0 : reorder_insns (insn, insn, last_insn);
3840 : }
3841 : }
3842 :
3843 27081098 : return last_insn;
3844 : }
3845 :
3846 : /* Locate or create a label for a given basic block. */
3847 :
3848 : static rtx_insn *
3849 2284684 : label_for_bb (basic_block bb)
3850 : {
3851 2284684 : rtx_insn *label = BB_HEAD (bb);
3852 :
3853 2284684 : if (!LABEL_P (label))
3854 : {
3855 1443079 : if (dump_file)
3856 8 : fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3857 :
3858 1443079 : label = block_label (bb);
3859 : }
3860 :
3861 2284684 : return label;
3862 : }
3863 :
3864 : /* Locate the effective beginning and end of the insn chain for each
3865 : block, as defined by skip_insns_after_block above. */
3866 :
3867 : static void
3868 2582399 : record_effective_endpoints (void)
3869 : {
3870 2582399 : rtx_insn *next_insn;
3871 2582399 : basic_block bb;
3872 2582399 : rtx_insn *insn;
3873 :
3874 2582399 : for (insn = get_insns ();
3875 : insn
3876 5167415 : && NOTE_P (insn)
3877 10333713 : && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3878 2585016 : insn = NEXT_INSN (insn))
3879 2585016 : continue;
3880 : /* No basic blocks at all? */
3881 2582399 : gcc_assert (insn);
3882 :
3883 2582399 : if (PREV_INSN (insn))
3884 2582384 : cfg_layout_function_header =
3885 2582384 : unlink_insn_chain (get_insns (), PREV_INSN (insn));
3886 : else
3887 : cfg_layout_function_header = NULL;
3888 :
3889 2582399 : next_insn = get_insns ();
3890 29663497 : FOR_EACH_BB_FN (bb, cfun)
3891 : {
3892 27081098 : rtx_insn *end;
3893 :
3894 27081098 : if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3895 46071 : BB_HEADER (bb) = unlink_insn_chain (next_insn,
3896 46071 : PREV_INSN (BB_HEAD (bb)));
3897 27081098 : end = skip_insns_after_block (bb);
3898 27081098 : if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3899 7798091 : BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3900 27081098 : next_insn = NEXT_INSN (BB_END (bb));
3901 : }
3902 :
3903 2582399 : cfg_layout_function_footer = next_insn;
3904 2582399 : if (cfg_layout_function_footer)
3905 1040221 : cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3906 2585016 : }
3907 :
3908 : namespace {
3909 :
3910 : const pass_data pass_data_into_cfg_layout_mode =
3911 : {
3912 : RTL_PASS, /* type */
3913 : "into_cfglayout", /* name */
3914 : OPTGROUP_NONE, /* optinfo_flags */
3915 : TV_CFG, /* tv_id */
3916 : 0, /* properties_required */
3917 : PROP_cfglayout, /* properties_provided */
3918 : 0, /* properties_destroyed */
3919 : 0, /* todo_flags_start */
3920 : 0, /* todo_flags_finish */
3921 : };
3922 :
3923 : class pass_into_cfg_layout_mode : public rtl_opt_pass
3924 : {
3925 : public:
3926 297180 : pass_into_cfg_layout_mode (gcc::context *ctxt)
3927 594360 : : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3928 : {}
3929 :
3930 : /* opt_pass methods: */
3931 1517124 : unsigned int execute (function *) final override
3932 : {
3933 1517124 : cfg_layout_initialize (0);
3934 1517124 : return 0;
3935 : }
3936 :
3937 : }; // class pass_into_cfg_layout_mode
3938 :
3939 : } // anon namespace
3940 :
3941 : rtl_opt_pass *
3942 297180 : make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3943 : {
3944 297180 : return new pass_into_cfg_layout_mode (ctxt);
3945 : }
3946 :
3947 : namespace {
3948 :
3949 : const pass_data pass_data_outof_cfg_layout_mode =
3950 : {
3951 : RTL_PASS, /* type */
3952 : "outof_cfglayout", /* name */
3953 : OPTGROUP_NONE, /* optinfo_flags */
3954 : TV_CFG, /* tv_id */
3955 : 0, /* properties_required */
3956 : 0, /* properties_provided */
3957 : PROP_cfglayout, /* properties_destroyed */
3958 : 0, /* todo_flags_start */
3959 : 0, /* todo_flags_finish */
3960 : };
3961 :
3962 : class pass_outof_cfg_layout_mode : public rtl_opt_pass
3963 : {
3964 : public:
3965 297180 : pass_outof_cfg_layout_mode (gcc::context *ctxt)
3966 594360 : : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3967 : {}
3968 :
3969 : /* opt_pass methods: */
3970 : unsigned int execute (function *) final override;
3971 :
3972 : }; // class pass_outof_cfg_layout_mode
3973 :
3974 : unsigned int
3975 1517125 : pass_outof_cfg_layout_mode::execute (function *fun)
3976 : {
3977 1517125 : basic_block bb;
3978 :
3979 15379594 : FOR_EACH_BB_FN (bb, fun)
3980 13862469 : if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3981 12345344 : bb->aux = bb->next_bb;
3982 :
3983 1517125 : cfg_layout_finalize ();
3984 :
3985 1517125 : return 0;
3986 : }
3987 :
3988 : } // anon namespace
3989 :
3990 : rtl_opt_pass *
3991 297180 : make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3992 : {
3993 297180 : return new pass_outof_cfg_layout_mode (ctxt);
3994 : }
3995 :
3996 :
3997 : /* Link the basic blocks in the correct order, compacting the basic
3998 : block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3999 : function also clears the basic block header and footer fields.
4000 :
4001 : This function is usually called after a pass (e.g. tracer) finishes
4002 : some transformations while in cfglayout mode. The required sequence
4003 : of the basic blocks is in a linked list along the bb->aux field.
4004 : This functions re-links the basic block prev_bb and next_bb pointers
4005 : accordingly, and it compacts and renumbers the blocks.
4006 :
4007 : FIXME: This currently works only for RTL, but the only RTL-specific
4008 : bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
4009 : to GIMPLE a long time ago, but it doesn't relink the basic block
4010 : chain. It could do that (to give better initial RTL) if this function
4011 : is made IR-agnostic (and moved to cfganal.cc or cfg.cc while at it). */
4012 :
4013 : void
4014 3225880 : relink_block_chain (bool stay_in_cfglayout_mode)
4015 : {
4016 3225880 : basic_block bb, prev_bb;
4017 3225880 : int index;
4018 :
4019 : /* Maybe dump the re-ordered sequence. */
4020 3225880 : if (dump_file)
4021 : {
4022 168 : fprintf (dump_file, "Reordered sequence:\n");
4023 168 : for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
4024 : NUM_FIXED_BLOCKS;
4025 1093 : bb;
4026 925 : bb = (basic_block) bb->aux, index++)
4027 : {
4028 925 : fprintf (dump_file, " %i ", index);
4029 925 : if (get_bb_original (bb))
4030 28 : fprintf (dump_file, "duplicate of %i\n",
4031 28 : get_bb_original (bb)->index);
4032 897 : else if (forwarder_block_p (bb)
4033 897 : && !LABEL_P (BB_HEAD (bb)))
4034 16 : fprintf (dump_file, "compensation\n");
4035 : else
4036 881 : fprintf (dump_file, "bb %i\n", bb->index);
4037 : }
4038 : }
4039 :
4040 : /* Now reorder the blocks. */
4041 3225880 : prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
4042 3225880 : bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4043 39558515 : for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
4044 : {
4045 36332635 : bb->prev_bb = prev_bb;
4046 36332635 : prev_bb->next_bb = bb;
4047 : }
4048 3225880 : prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
4049 3225880 : EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
4050 :
4051 : /* Then, clean up the aux fields. */
4052 46010275 : FOR_ALL_BB_FN (bb, cfun)
4053 : {
4054 42784395 : bb->aux = NULL;
4055 42784395 : if (!stay_in_cfglayout_mode)
4056 30709874 : BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
4057 : }
4058 :
4059 : /* Maybe reset the original copy tables, they are not valid anymore
4060 : when we renumber the basic blocks in compact_blocks. If we are
4061 : are going out of cfglayout mode, don't re-allocate the tables. */
4062 3225880 : if (original_copy_tables_initialized_p ())
4063 3225879 : free_original_copy_tables ();
4064 3225880 : if (stay_in_cfglayout_mode)
4065 643480 : initialize_original_copy_tables ();
4066 :
4067 : /* Finally, put basic_block_info in the new order. */
4068 3225880 : compact_blocks ();
4069 3225880 : }
4070 :
4071 :
4072 : /* Given a reorder chain, rearrange the code to match. */
4073 :
4074 : static void
4075 2582400 : fixup_reorder_chain (void)
4076 : {
4077 2582400 : basic_block bb;
4078 2582400 : rtx_insn *insn = NULL;
4079 :
4080 2582400 : if (cfg_layout_function_header)
4081 : {
4082 2582384 : set_first_insn (cfg_layout_function_header);
4083 2582384 : insn = cfg_layout_function_header;
4084 2585016 : while (NEXT_INSN (insn))
4085 : insn = NEXT_INSN (insn);
4086 : }
4087 :
4088 : /* First do the bulk reordering -- rechain the blocks without regard to
4089 : the needed changes to jumps and labels. */
4090 :
4091 27369735 : for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
4092 : bb->aux)
4093 : {
4094 24787335 : if (BB_HEADER (bb))
4095 : {
4096 45148 : if (insn)
4097 45148 : SET_NEXT_INSN (insn) = BB_HEADER (bb);
4098 : else
4099 0 : set_first_insn (BB_HEADER (bb));
4100 45148 : SET_PREV_INSN (BB_HEADER (bb)) = insn;
4101 45148 : insn = BB_HEADER (bb);
4102 57539 : while (NEXT_INSN (insn))
4103 : insn = NEXT_INSN (insn);
4104 : }
4105 24787335 : if (insn)
4106 24787319 : SET_NEXT_INSN (insn) = BB_HEAD (bb);
4107 : else
4108 16 : set_first_insn (BB_HEAD (bb));
4109 24787335 : SET_PREV_INSN (BB_HEAD (bb)) = insn;
4110 24787335 : insn = BB_END (bb);
4111 24787335 : if (BB_FOOTER (bb))
4112 : {
4113 3075646 : SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4114 3075646 : SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4115 6202288 : while (NEXT_INSN (insn))
4116 : insn = NEXT_INSN (insn);
4117 : }
4118 : }
4119 :
4120 2582400 : SET_NEXT_INSN (insn) = cfg_layout_function_footer;
4121 2582400 : if (cfg_layout_function_footer)
4122 1040233 : SET_PREV_INSN (cfg_layout_function_footer) = insn;
4123 :
4124 3623525 : while (NEXT_INSN (insn))
4125 : insn = NEXT_INSN (insn);
4126 :
4127 2582400 : set_last_insn (insn);
4128 2582400 : if (flag_checking)
4129 2582362 : verify_insn_chain ();
4130 :
4131 : /* Now add jumps and labels as needed to match the blocks new
4132 : outgoing edges. */
4133 :
4134 2582400 : bool remove_unreachable_blocks = false;
4135 27369735 : for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
4136 : bb->aux)
4137 : {
4138 24787335 : edge e_fall, e_taken, e;
4139 24787335 : rtx_insn *bb_end_insn;
4140 24787335 : rtx ret_label = NULL_RTX;
4141 24787335 : basic_block nb;
4142 24787335 : edge_iterator ei;
4143 24787335 : bool asm_goto = false;
4144 :
4145 24787335 : if (EDGE_COUNT (bb->succs) == 0)
4146 20596256 : continue;
4147 :
4148 : /* Find the old fallthru edge, and another non-EH edge for
4149 : a taken jump. */
4150 23461152 : e_taken = e_fall = NULL;
4151 :
4152 59854814 : FOR_EACH_EDGE (e, ei, bb->succs)
4153 36393662 : if (e->flags & EDGE_FALLTHRU)
4154 : e_fall = e;
4155 14680829 : else if (! (e->flags & EDGE_EH))
4156 13331549 : e_taken = e;
4157 :
4158 23461152 : bb_end_insn = BB_END (bb);
4159 23461152 : if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
4160 : {
4161 12867759 : ret_label = JUMP_LABEL (bb_end_jump);
4162 12867759 : if (any_condjump_p (bb_end_jump))
4163 : {
4164 : /* This might happen if the conditional jump has side
4165 : effects and could therefore not be optimized away.
4166 : Make the basic block to end with a barrier in order
4167 : to prevent rtl_verify_flow_info from complaining. */
4168 11485442 : if (!e_fall)
4169 : {
4170 0 : gcc_assert (!onlyjump_p (bb_end_jump)
4171 : || returnjump_p (bb_end_jump)
4172 : || (e_taken->flags & EDGE_CROSSING));
4173 0 : emit_barrier_after (bb_end_jump);
4174 0 : continue;
4175 : }
4176 :
4177 : /* If the old fallthru is still next, nothing to do. */
4178 11485442 : if (bb->aux == e_fall->dest
4179 2727954 : || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4180 8757500 : continue;
4181 :
4182 : /* The degenerated case of conditional jump jumping to the next
4183 : instruction can happen for jumps with side effects. We need
4184 : to construct a forwarder block and this will be done just
4185 : fine by force_nonfallthru below. */
4186 2727942 : if (!e_taken)
4187 : ;
4188 :
4189 : /* There is another special case: if *neither* block is next,
4190 : such as happens at the very end of a function, then we'll
4191 : need to add a new unconditional jump. Choose the taken
4192 : edge based on known or assumed probability. */
4193 2727942 : else if (bb->aux != e_taken->dest)
4194 : {
4195 570541 : rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
4196 :
4197 570541 : if (note
4198 : && profile_probability::from_reg_br_prob_note
4199 548009 : (XINT (note, 0)) < profile_probability::even ()
4200 768625 : && invert_jump (bb_end_jump,
4201 198084 : (e_fall->dest
4202 198084 : == EXIT_BLOCK_PTR_FOR_FN (cfun)
4203 : ? NULL_RTX
4204 198084 : : label_for_bb (e_fall->dest)), 0))
4205 : {
4206 198084 : e_fall->flags &= ~EDGE_FALLTHRU;
4207 198084 : gcc_checking_assert (could_fall_through
4208 : (e_taken->src, e_taken->dest));
4209 198084 : e_taken->flags |= EDGE_FALLTHRU;
4210 198084 : update_br_prob_note (bb);
4211 198084 : e = e_fall, e_fall = e_taken, e_taken = e;
4212 : }
4213 : }
4214 :
4215 : /* If the "jumping" edge is a crossing edge, and the fall
4216 : through edge is non-crossing, leave things as they are. */
4217 2157401 : else if ((e_taken->flags & EDGE_CROSSING)
4218 70801 : && !(e_fall->flags & EDGE_CROSSING))
4219 70801 : continue;
4220 :
4221 : /* Otherwise we can try to invert the jump. This will
4222 : basically never fail, however, keep up the pretense. */
4223 2086600 : else if (invert_jump (bb_end_jump,
4224 : (e_fall->dest
4225 : == EXIT_BLOCK_PTR_FOR_FN (cfun)
4226 : ? NULL_RTX
4227 2086600 : : label_for_bb (e_fall->dest)), 0))
4228 : {
4229 2086600 : e_fall->flags &= ~EDGE_FALLTHRU;
4230 2086600 : gcc_checking_assert (could_fall_through
4231 : (e_taken->src, e_taken->dest));
4232 2086600 : e_taken->flags |= EDGE_FALLTHRU;
4233 2086600 : update_br_prob_note (bb);
4234 2086600 : if (LABEL_NUSES (ret_label) == 0
4235 2086600 : && single_pred_p (e_taken->dest))
4236 1291964 : delete_insn (as_a<rtx_insn *> (ret_label));
4237 2086600 : continue;
4238 : }
4239 : }
4240 1382317 : else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
4241 : {
4242 : /* If the old fallthru is still next or if
4243 : asm goto doesn't have a fallthru (e.g. when followed by
4244 : __builtin_unreachable ()), nothing to do. */
4245 1257 : if (! e_fall
4246 1191 : || bb->aux == e_fall->dest
4247 137 : || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4248 1120 : continue;
4249 :
4250 : /* Otherwise we'll have to use the fallthru fixup below.
4251 : But avoid redirecting asm goto to EXIT. */
4252 : asm_goto = true;
4253 : }
4254 : else
4255 : {
4256 : /* Otherwise we have some return, switch or computed
4257 : jump. In the 99% case, there should not have been a
4258 : fallthru edge. */
4259 1381060 : gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
4260 1381060 : continue;
4261 : }
4262 : }
4263 : else
4264 : {
4265 : /* No fallthru implies a noreturn function with EH edges, or
4266 : something similarly bizarre. In any case, we don't need to
4267 : do anything. */
4268 10593393 : if (! e_fall)
4269 367193 : continue;
4270 :
4271 : /* If the fallthru block is still next, nothing to do. */
4272 10226200 : if (bb->aux == e_fall->dest)
4273 5194185 : continue;
4274 :
4275 : /* A fallthru to exit block. */
4276 5032015 : if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4277 1411614 : continue;
4278 : }
4279 :
4280 : /* If E_FALL->dest is just a return block, then we can emit a
4281 : return rather than a jump to the return block. */
4282 570541 : rtx_insn *ret, *use;
4283 570541 : basic_block dest;
4284 570541 : if (!asm_goto
4285 4190942 : && bb_is_just_return (e_fall->dest, &ret, &use)
4286 580 : && ((PATTERN (ret) == simple_return_rtx && targetm.have_simple_return ())
4287 0 : || (PATTERN (ret) == ret_rtx && targetm.have_return ())))
4288 : {
4289 580 : ret_label = PATTERN (ret);
4290 580 : dest = EXIT_BLOCK_PTR_FOR_FN (cfun);
4291 :
4292 580 : e_fall->flags &= ~EDGE_CROSSING;
4293 : /* E_FALL->dest might become unreachable as a result of
4294 : replacing the jump with a return. So arrange to remove
4295 : unreachable blocks. */
4296 580 : remove_unreachable_blocks = true;
4297 : }
4298 : else
4299 : {
4300 4190499 : dest = e_fall->dest;
4301 : }
4302 :
4303 : /* We got here if we need to add a new jump insn.
4304 : Note force_nonfallthru can delete E_FALL and thus we have to
4305 : save E_FALL->src prior to the call to force_nonfallthru. */
4306 4191079 : nb = force_nonfallthru_and_redirect (e_fall, dest, ret_label);
4307 4191079 : if (nb)
4308 : {
4309 757739 : nb->aux = bb->aux;
4310 757739 : bb->aux = nb;
4311 : /* Don't process this new block. */
4312 757739 : bb = nb;
4313 : }
4314 : }
4315 :
4316 2582400 : relink_block_chain (/*stay_in_cfglayout_mode=*/false);
4317 :
4318 : /* Annoying special case - jump around dead jumptables left in the code. */
4319 28198275 : FOR_EACH_BB_FN (bb, cfun)
4320 : {
4321 25615875 : edge e = find_fallthru_edge (bb->succs);
4322 :
4323 25615875 : if (e && !can_fallthru (e->src, e->dest))
4324 70801 : force_nonfallthru (e);
4325 : }
4326 :
4327 : /* Ensure goto_locus from edges has some instructions with that locus in RTL
4328 : when not optimizing. */
4329 2582400 : if (!optimize && !DECL_IGNORED_P (current_function_decl))
4330 3961187 : FOR_EACH_BB_FN (bb, cfun)
4331 : {
4332 3510966 : edge e;
4333 3510966 : edge_iterator ei;
4334 :
4335 8334523 : FOR_EACH_EDGE (e, ei, bb->succs)
4336 4823557 : if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
4337 4823557 : && !(e->flags & EDGE_ABNORMAL))
4338 : {
4339 759234 : edge e2;
4340 759234 : edge_iterator ei2;
4341 759234 : basic_block dest, nb;
4342 759234 : rtx_insn *end;
4343 :
4344 759234 : insn = BB_END (e->src);
4345 759234 : end = PREV_INSN (BB_HEAD (e->src));
4346 759234 : while (insn != end
4347 921733 : && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
4348 162499 : insn = PREV_INSN (insn);
4349 1284306 : if (insn != end
4350 759234 : && loc_equal (INSN_LOCATION (insn), e->goto_locus))
4351 540536 : continue;
4352 234162 : if (simplejump_p (BB_END (e->src))
4353 234162 : && !INSN_HAS_LOCATION (BB_END (e->src)))
4354 : {
4355 0 : INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
4356 0 : continue;
4357 : }
4358 234162 : dest = e->dest;
4359 234162 : if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4360 : {
4361 : /* Non-fallthru edges to the exit block cannot be split. */
4362 154315 : if (!(e->flags & EDGE_FALLTHRU))
4363 0 : continue;
4364 : }
4365 : else
4366 : {
4367 79847 : insn = BB_HEAD (dest);
4368 79847 : end = NEXT_INSN (BB_END (dest));
4369 314709 : while (insn != end && !NONDEBUG_INSN_P (insn))
4370 155015 : insn = NEXT_INSN (insn);
4371 50274 : if (insn != end && INSN_HAS_LOCATION (insn)
4372 127899 : && loc_equal (INSN_LOCATION (insn), e->goto_locus))
4373 15464 : continue;
4374 : }
4375 218698 : nb = split_edge (e);
4376 218698 : if (!INSN_P (BB_END (nb)))
4377 218698 : BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
4378 : nb);
4379 218698 : INSN_LOCATION (BB_END (nb)) = e->goto_locus;
4380 :
4381 : /* If there are other incoming edges to the destination block
4382 : with the same goto locus, redirect them to the new block as
4383 : well, this can prevent other such blocks from being created
4384 : in subsequent iterations of the loop. */
4385 509564 : for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
4386 290866 : if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
4387 48249 : && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
4388 339115 : && e->goto_locus == e2->goto_locus)
4389 15984 : redirect_edge_and_branch (e2, nb);
4390 : else
4391 274882 : ei_next (&ei2);
4392 : }
4393 : }
4394 :
4395 : /* Replacing a jump with a return may have exposed an unreachable
4396 : block. Conditionally remove them if such transformations were
4397 : made. */
4398 2582400 : if (remove_unreachable_blocks)
4399 565 : delete_unreachable_blocks ();
4400 2582400 : }
4401 :
4402 : /* Perform sanity checks on the insn chain.
4403 : 1. Check that next/prev pointers are consistent in both the forward and
4404 : reverse direction.
4405 : 2. Count insns in chain, going both directions, and check if equal.
4406 : 3. Check that get_last_insn () returns the actual end of chain. */
4407 :
4408 : DEBUG_FUNCTION void
4409 5164724 : verify_insn_chain (void)
4410 : {
4411 5164724 : rtx_insn *x, *prevx, *nextx;
4412 5164724 : int insn_cnt1, insn_cnt2;
4413 :
4414 5164724 : for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
4415 634033554 : x != 0;
4416 628868830 : prevx = x, insn_cnt1++, x = NEXT_INSN (x))
4417 628868830 : gcc_assert (PREV_INSN (x) == prevx);
4418 :
4419 5164724 : gcc_assert (prevx == get_last_insn ());
4420 :
4421 : for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
4422 634033554 : x != 0;
4423 628868830 : nextx = x, insn_cnt2++, x = PREV_INSN (x))
4424 628868830 : gcc_assert (NEXT_INSN (x) == nextx);
4425 :
4426 5164724 : gcc_assert (insn_cnt1 == insn_cnt2);
4427 5164724 : }
4428 :
4429 : /* If we have assembler epilogues, the block falling through to exit must
4430 : be the last one in the reordered chain when we reach final. Ensure
4431 : that this condition is met. */
4432 : static void
4433 0 : fixup_fallthru_exit_predecessor (void)
4434 : {
4435 0 : edge e;
4436 0 : basic_block bb = NULL;
4437 :
4438 : /* This transformation is not valid before reload, because we might
4439 : separate a call from the instruction that copies the return
4440 : value. */
4441 0 : gcc_assert (reload_completed);
4442 :
4443 0 : e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4444 0 : if (e)
4445 0 : bb = e->src;
4446 :
4447 0 : if (bb && bb->aux)
4448 : {
4449 0 : basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4450 :
4451 : /* If the very first block is the one with the fall-through exit
4452 : edge, we have to split that block. */
4453 0 : if (c == bb)
4454 : {
4455 0 : bb = split_block_after_labels (bb)->dest;
4456 0 : bb->aux = c->aux;
4457 0 : c->aux = bb;
4458 0 : BB_FOOTER (bb) = BB_FOOTER (c);
4459 0 : BB_FOOTER (c) = NULL;
4460 : }
4461 :
4462 0 : while (c->aux != bb)
4463 : c = (basic_block) c->aux;
4464 :
4465 0 : c->aux = bb->aux;
4466 0 : while (c->aux)
4467 : c = (basic_block) c->aux;
4468 :
4469 0 : c->aux = bb;
4470 0 : bb->aux = NULL;
4471 : }
4472 0 : }
4473 :
4474 : /* In case there are more than one fallthru predecessors of exit, force that
4475 : there is only one. */
4476 :
4477 : static void
4478 2582400 : force_one_exit_fallthru (void)
4479 : {
4480 2582400 : edge e, predecessor = NULL;
4481 2582400 : bool more = false;
4482 2582400 : edge_iterator ei;
4483 2582400 : basic_block forwarder, bb;
4484 :
4485 5454902 : FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4486 2872503 : if (e->flags & EDGE_FALLTHRU)
4487 : {
4488 1411627 : if (predecessor == NULL)
4489 : predecessor = e;
4490 : else
4491 : {
4492 : more = true;
4493 : break;
4494 : }
4495 : }
4496 :
4497 2582400 : if (!more)
4498 2582399 : return;
4499 :
4500 : /* Exit has several fallthru predecessors. Create a forwarder block for
4501 : them. */
4502 1 : forwarder = split_edge (predecessor);
4503 1 : for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4504 3 : (e = ei_safe_edge (ei)); )
4505 : {
4506 2 : if (e->src == forwarder
4507 1 : || !(e->flags & EDGE_FALLTHRU))
4508 1 : ei_next (&ei);
4509 : else
4510 1 : redirect_edge_and_branch_force (e, forwarder);
4511 : }
4512 :
4513 : /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4514 : exit block. */
4515 5 : FOR_EACH_BB_FN (bb, cfun)
4516 : {
4517 5 : if (bb->aux == NULL && bb != forwarder)
4518 : {
4519 1 : bb->aux = forwarder;
4520 1 : break;
4521 : }
4522 : }
4523 : }
4524 :
4525 : /* Return true if BB can be duplicated. A tablejump can be duplicated only
4526 : when PROP_rtl_allow_tablejump_duplication is set. Its copy then shares the
4527 : table with BB, see duplicate_insn_chain. */
4528 :
4529 : static bool
4530 8465649 : cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4531 : {
4532 : /* A copy of a tablejump shares the dispatch table with the original.
4533 : Unsharing it is not an option, as the instructions computing the jump
4534 : destination may have been hoisted outside the basic block. The property
4535 : is set while a pass can make the table immutable. */
4536 8465649 : if (!(cfun->curr_properties & PROP_rtl_allow_tablejump_duplication)
4537 8465649 : && tablejump_p (BB_END (bb), NULL, NULL))
4538 : return false;
4539 :
4540 : /* Do not duplicate blocks containing insns that can't be copied. */
4541 8462045 : if (targetm.cannot_copy_insn_p)
4542 : {
4543 0 : rtx_insn *insn = BB_HEAD (bb);
4544 0 : while (1)
4545 : {
4546 0 : if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4547 : return false;
4548 0 : if (insn == BB_END (bb))
4549 : break;
4550 0 : insn = NEXT_INSN (insn);
4551 : }
4552 : }
4553 :
4554 : return true;
4555 : }
4556 :
4557 : rtx_insn *
4558 913403 : duplicate_insn_chain (rtx_insn *from, rtx_insn *to,
4559 : class loop *loop, copy_bb_data *id)
4560 : {
4561 913403 : rtx_insn *insn, *next, *copy;
4562 913403 : rtx_note *last;
4563 :
4564 : /* Avoid updating of boundaries of previous basic block. The
4565 : note will get removed from insn stream in fixup. */
4566 913403 : last = emit_note (NOTE_INSN_DELETED);
4567 :
4568 : /* Create copy at the end of INSN chain. The chain will
4569 : be reordered later. */
4570 7258950 : for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4571 : {
4572 5432144 : switch (GET_CODE (insn))
4573 : {
4574 1408819 : case DEBUG_INSN:
4575 : /* Don't duplicate label debug insns. */
4576 1408819 : if (DEBUG_BIND_INSN_P (insn)
4577 1075730 : && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4578 : break;
4579 : /* FALLTHRU */
4580 3645310 : case INSN:
4581 3645310 : case CALL_INSN:
4582 3645310 : case JUMP_INSN:
4583 3645310 : copy = emit_copy_of_insn_after (insn, get_last_insn ());
4584 3645310 : if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4585 500390 : && ANY_RETURN_P (JUMP_LABEL (insn)))
4586 179388 : JUMP_LABEL (copy) = JUMP_LABEL (insn);
4587 3465922 : else if (JUMP_P (insn))
4588 : {
4589 321230 : rtx_insn *table_label;
4590 321230 : rtx_jump_table_data *table;
4591 321230 : if (tablejump_p (insn, &table_label, &table))
4592 : {
4593 : /* The copy dispatches through the very same table. Mark it:
4594 : its entries now describe the successors of several jumps
4595 : at once and so must not be edited in place. The reference
4596 : itself is recorded by emit_copy_of_insn_after through
4597 : mark_jump_label. */
4598 1737 : gcc_assert (JUMP_LABEL (copy) == table_label);
4599 1737 : JUMP_TABLE_SHARED_P (PATTERN (table)) = 1;
4600 1737 : gcc_assert (tablejump_p (copy, NULL, NULL));
4601 : }
4602 : }
4603 3645310 : maybe_copy_prologue_epilogue_insn (insn, copy);
4604 : /* If requested remap dependence info of cliques brought in
4605 : via inlining. */
4606 3645310 : if (id)
4607 : {
4608 1911319 : subrtx_iterator::array_type array;
4609 11685057 : FOR_EACH_SUBRTX (iter, array, PATTERN (insn), ALL)
4610 9778546 : if (MEM_P (*iter) && MEM_EXPR (*iter))
4611 : {
4612 300562 : tree op = MEM_EXPR (*iter);
4613 300562 : if (TREE_CODE (op) == WITH_SIZE_EXPR)
4614 0 : op = TREE_OPERAND (op, 0);
4615 328598 : while (handled_component_p (op))
4616 28036 : op = TREE_OPERAND (op, 0);
4617 300562 : if ((TREE_CODE (op) == MEM_REF
4618 300562 : || TREE_CODE (op) == TARGET_MEM_REF)
4619 282056 : && MR_DEPENDENCE_CLIQUE (op) > 1
4620 313643 : && (!loop
4621 13081 : || (MR_DEPENDENCE_CLIQUE (op)
4622 13081 : != loop->owned_clique)))
4623 : {
4624 2172 : if (!id->dependence_map)
4625 1213 : id->dependence_map = new hash_map<dependence_hash,
4626 : unsigned short>;
4627 2172 : bool existed;
4628 2172 : unsigned short &newc = id->dependence_map->get_or_insert
4629 2172 : (MR_DEPENDENCE_CLIQUE (op), &existed);
4630 2172 : if (!existed)
4631 : {
4632 1223 : gcc_assert
4633 : (MR_DEPENDENCE_CLIQUE (op) <= cfun->last_clique);
4634 2446 : newc = get_new_clique (cfun);
4635 : }
4636 : /* We cannot adjust MR_DEPENDENCE_CLIQUE in-place
4637 : since MEM_EXPR is shared so make a copy and
4638 : walk to the subtree again. */
4639 2172 : tree new_expr = unshare_expr (MEM_EXPR (*iter));
4640 2172 : tree orig_new_expr = new_expr;
4641 2172 : if (TREE_CODE (new_expr) == WITH_SIZE_EXPR)
4642 0 : new_expr = TREE_OPERAND (new_expr, 0);
4643 2752 : while (handled_component_p (new_expr))
4644 580 : new_expr = TREE_OPERAND (new_expr, 0);
4645 2172 : MR_DEPENDENCE_CLIQUE (new_expr) = newc;
4646 2172 : set_mem_expr (const_cast <rtx> (*iter), orig_new_expr);
4647 : }
4648 : }
4649 1911319 : }
4650 : break;
4651 :
4652 0 : case JUMP_TABLE_DATA:
4653 : /* Avoid copying dispatch tables. A duplicated tablejump continues
4654 : to use the original table. Avoid copying the following barrier as
4655 : well, if any, and debug insns in between. */
4656 0 : for (next = NEXT_INSN (insn);
4657 0 : next != NEXT_INSN (to);
4658 0 : next = NEXT_INSN (next))
4659 0 : if (!DEBUG_INSN_P (next))
4660 : break;
4661 0 : if (next != NEXT_INSN (to) && BARRIER_P (next))
4662 5432144 : insn = next;
4663 : break;
4664 :
4665 : case CODE_LABEL:
4666 : break;
4667 :
4668 180692 : case BARRIER:
4669 180692 : emit_barrier ();
4670 180692 : break;
4671 :
4672 946844 : case NOTE:
4673 946844 : switch (NOTE_KIND (insn))
4674 : {
4675 : /* In case prologue is empty and function contain label
4676 : in first BB, we may want to copy the block. */
4677 : case NOTE_INSN_PROLOGUE_END:
4678 :
4679 : case NOTE_INSN_DELETED:
4680 : case NOTE_INSN_DELETED_LABEL:
4681 : case NOTE_INSN_DELETED_DEBUG_LABEL:
4682 : /* No problem to strip these. */
4683 : case NOTE_INSN_FUNCTION_BEG:
4684 : /* There is always just single entry to function. */
4685 : case NOTE_INSN_BASIC_BLOCK:
4686 : /* We should only switch text sections once. */
4687 : case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4688 : break;
4689 :
4690 176817 : case NOTE_INSN_EPILOGUE_BEG:
4691 176817 : case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4692 176817 : emit_note_copy (as_a <rtx_note *> (insn));
4693 176817 : break;
4694 :
4695 0 : default:
4696 : /* All other notes should have already been eliminated. */
4697 0 : gcc_unreachable ();
4698 : }
4699 : break;
4700 0 : default:
4701 0 : gcc_unreachable ();
4702 : }
4703 : }
4704 913403 : insn = NEXT_INSN (last);
4705 913403 : delete_insn (last);
4706 913403 : return insn;
4707 : }
4708 :
4709 : /* Create a duplicate of the basic block BB. */
4710 :
4711 : static basic_block
4712 730126 : cfg_layout_duplicate_bb (basic_block bb, copy_bb_data *id)
4713 : {
4714 730126 : rtx_insn *insn;
4715 730126 : basic_block new_bb;
4716 :
4717 730126 : class loop *loop = (id && current_loops) ? bb->loop_father : NULL;
4718 :
4719 730126 : insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb), loop, id);
4720 730126 : new_bb = create_basic_block (insn,
4721 : insn ? get_last_insn () : NULL,
4722 730126 : EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4723 :
4724 730126 : BB_COPY_PARTITION (new_bb, bb);
4725 730126 : if (BB_HEADER (bb))
4726 : {
4727 : insn = BB_HEADER (bb);
4728 3444 : while (NEXT_INSN (insn))
4729 : insn = NEXT_INSN (insn);
4730 2467 : insn = duplicate_insn_chain (BB_HEADER (bb), insn, loop, id);
4731 2467 : if (insn)
4732 0 : BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4733 : }
4734 :
4735 730126 : if (BB_FOOTER (bb))
4736 : {
4737 : insn = BB_FOOTER (bb);
4738 180721 : while (NEXT_INSN (insn))
4739 : insn = NEXT_INSN (insn);
4740 180600 : insn = duplicate_insn_chain (BB_FOOTER (bb), insn, loop, id);
4741 180600 : if (insn)
4742 180600 : BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4743 : }
4744 :
4745 730126 : return new_bb;
4746 : }
4747 :
4748 :
4749 : /* Main entry point to this module - initialize the datastructures for
4750 : CFG layout changes. It keeps LOOPS up-to-date if not null.
4751 :
4752 : FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4753 :
4754 : void
4755 2582399 : cfg_layout_initialize (int flags)
4756 : {
4757 2582399 : rtx_insn_list *x;
4758 2582399 : basic_block bb;
4759 :
4760 : /* Once bb partitioning is complete, cfg layout mode should not be
4761 : re-entered. Entering cfg layout mode may require fixups. As an
4762 : example, if edge forwarding performed when optimizing the cfg
4763 : layout required moving a block from the hot to the cold
4764 : section. This would create an illegal partitioning unless some
4765 : manual fixup was performed. */
4766 2582399 : gcc_assert (!crtl->bb_reorder_complete || !crtl->has_bb_partition);
4767 :
4768 2582399 : initialize_original_copy_tables ();
4769 :
4770 2582399 : cfg_layout_rtl_register_cfg_hooks ();
4771 :
4772 2582399 : record_effective_endpoints ();
4773 :
4774 : /* Make sure that the targets of non local gotos are marked. */
4775 2584817 : for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4776 : {
4777 2418 : bb = BLOCK_FOR_INSN (x->insn ());
4778 2418 : bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4779 : }
4780 :
4781 2582399 : cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4782 2582399 : }
4783 :
4784 : /* Splits superblocks. */
4785 : void
4786 66023 : break_superblocks (void)
4787 : {
4788 66023 : bool need = false;
4789 66023 : basic_block bb;
4790 :
4791 66023 : auto_sbitmap superblocks (last_basic_block_for_fn (cfun));
4792 66023 : bitmap_clear (superblocks);
4793 :
4794 3783355 : FOR_EACH_BB_FN (bb, cfun)
4795 3717332 : if (bb->flags & BB_SUPERBLOCK)
4796 : {
4797 221603 : bb->flags &= ~BB_SUPERBLOCK;
4798 221603 : bitmap_set_bit (superblocks, bb->index);
4799 221603 : need = true;
4800 : }
4801 :
4802 66023 : if (need)
4803 : {
4804 56488 : rebuild_jump_labels (get_insns ());
4805 56488 : find_many_sub_basic_blocks (superblocks);
4806 : }
4807 66023 : }
4808 :
4809 : /* Finalize the changes: reorder insn list according to the sequence specified
4810 : by aux pointers, enter compensation code, rebuild scope forest. */
4811 :
4812 : void
4813 2582400 : cfg_layout_finalize (void)
4814 : {
4815 2582400 : free_dominance_info (CDI_DOMINATORS);
4816 2582400 : force_one_exit_fallthru ();
4817 2582400 : rtl_register_cfg_hooks ();
4818 2582400 : if (reload_completed && !targetm.have_epilogue ())
4819 0 : fixup_fallthru_exit_predecessor ();
4820 2582400 : fixup_reorder_chain ();
4821 :
4822 2582400 : rebuild_jump_labels (get_insns ());
4823 2582400 : delete_dead_jumptables ();
4824 :
4825 2582400 : if (flag_checking)
4826 2582362 : verify_insn_chain ();
4827 2582400 : checking_verify_flow_info ();
4828 2582400 : }
4829 :
4830 :
4831 : /* Same as split_block but update cfg_layout structures. */
4832 :
4833 : static basic_block
4834 17856 : cfg_layout_split_block (basic_block bb, void *insnp)
4835 : {
4836 17856 : rtx insn = (rtx) insnp;
4837 17856 : basic_block new_bb = rtl_split_block (bb, insn);
4838 :
4839 17856 : BB_FOOTER (new_bb) = BB_FOOTER (bb);
4840 17856 : BB_FOOTER (bb) = NULL;
4841 :
4842 17856 : return new_bb;
4843 : }
4844 :
4845 : /* Redirect Edge to DEST. */
4846 : static edge
4847 10426784 : cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4848 : {
4849 10426784 : basic_block src = e->src;
4850 10426784 : edge ret;
4851 :
4852 10426784 : if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4853 : return NULL;
4854 :
4855 10426784 : if (e->dest == dest)
4856 : return e;
4857 :
4858 10426784 : if (e->flags & EDGE_CROSSING
4859 5 : && BB_PARTITION (e->src) == BB_PARTITION (dest)
4860 10426784 : && simplejump_p (BB_END (src)))
4861 : {
4862 0 : if (dump_file)
4863 0 : fprintf (dump_file,
4864 : "Removing crossing jump while redirecting edge form %i to %i\n",
4865 0 : e->src->index, dest->index);
4866 0 : delete_insn (BB_END (src));
4867 0 : remove_barriers_from_footer (src);
4868 0 : e->flags |= EDGE_FALLTHRU;
4869 : }
4870 :
4871 10426784 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4872 10426784 : && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4873 : {
4874 330900 : df_set_bb_dirty (src);
4875 330900 : return ret;
4876 : }
4877 :
4878 10095884 : if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4879 0 : && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4880 : {
4881 0 : if (dump_file)
4882 0 : fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4883 : e->src->index, dest->index);
4884 :
4885 0 : df_set_bb_dirty (e->src);
4886 0 : redirect_edge_succ (e, dest);
4887 0 : return e;
4888 : }
4889 :
4890 : /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4891 : in the case the basic block appears to be in sequence. Avoid this
4892 : transformation. */
4893 :
4894 10095884 : if (e->flags & EDGE_FALLTHRU)
4895 : {
4896 : /* Redirect any branch edges unified with the fallthru one. */
4897 4851182 : if (JUMP_P (BB_END (src))
4898 4851182 : && label_is_jump_target_p (BB_HEAD (e->dest),
4899 : BB_END (src)))
4900 : {
4901 170 : edge redirected;
4902 :
4903 170 : if (dump_file)
4904 0 : fprintf (dump_file, "Fallthru edge unified with branch "
4905 : "%i->%i redirected to %i\n",
4906 0 : e->src->index, e->dest->index, dest->index);
4907 170 : e->flags &= ~EDGE_FALLTHRU;
4908 170 : redirected = redirect_branch_edge (e, dest);
4909 170 : gcc_assert (redirected);
4910 170 : redirected->flags |= EDGE_FALLTHRU;
4911 170 : df_set_bb_dirty (redirected->src);
4912 170 : return redirected;
4913 : }
4914 : /* In case we are redirecting fallthru edge to the branch edge
4915 : of conditional jump, remove it. */
4916 4851012 : if (EDGE_COUNT (src->succs) == 2)
4917 : {
4918 : /* Find the edge that is different from E. */
4919 3757546 : edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4920 :
4921 3757546 : if (s->dest == dest
4922 2 : && any_condjump_p (BB_END (src))
4923 3757546 : && onlyjump_p (BB_END (src)))
4924 0 : delete_insn (BB_END (src));
4925 : }
4926 4851012 : if (dump_file)
4927 2229 : fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4928 2229 : e->src->index, e->dest->index, dest->index);
4929 4851012 : ret = redirect_edge_succ_nodup (e, dest);
4930 : }
4931 : else
4932 5244702 : ret = redirect_branch_edge (e, dest);
4933 :
4934 10095714 : if (!ret)
4935 : return NULL;
4936 :
4937 10095714 : fixup_partition_crossing (ret);
4938 : /* We don't want simplejumps in the insn stream during cfglayout. */
4939 10095714 : gcc_assert (!simplejump_p (BB_END (src)) || CROSSING_JUMP_P (BB_END (src)));
4940 :
4941 10095714 : df_set_bb_dirty (src);
4942 10095714 : return ret;
4943 : }
4944 :
4945 : /* Simple wrapper as we always can redirect fallthru edges. */
4946 : static basic_block
4947 4958263 : cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4948 : {
4949 4958263 : edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4950 :
4951 4958263 : gcc_assert (redirected);
4952 4958263 : return NULL;
4953 : }
4954 :
4955 : /* Same as delete_basic_block but update cfg_layout structures. */
4956 :
4957 : static void
4958 5765842 : cfg_layout_delete_block (basic_block bb)
4959 : {
4960 5765842 : rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4961 5765842 : rtx_insn **to;
4962 :
4963 5765842 : if (BB_HEADER (bb))
4964 : {
4965 106 : next = BB_HEAD (bb);
4966 106 : if (prev)
4967 106 : SET_NEXT_INSN (prev) = BB_HEADER (bb);
4968 : else
4969 0 : set_first_insn (BB_HEADER (bb));
4970 106 : SET_PREV_INSN (BB_HEADER (bb)) = prev;
4971 106 : insn = BB_HEADER (bb);
4972 147 : while (NEXT_INSN (insn))
4973 : insn = NEXT_INSN (insn);
4974 106 : SET_NEXT_INSN (insn) = next;
4975 106 : SET_PREV_INSN (next) = insn;
4976 : }
4977 5765842 : next = NEXT_INSN (BB_END (bb));
4978 5765842 : if (BB_FOOTER (bb))
4979 : {
4980 : insn = BB_FOOTER (bb);
4981 2851876 : while (insn)
4982 : {
4983 1425951 : if (BARRIER_P (insn))
4984 : {
4985 1425925 : if (PREV_INSN (insn))
4986 15 : SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4987 : else
4988 1425910 : BB_FOOTER (bb) = NEXT_INSN (insn);
4989 1425925 : if (NEXT_INSN (insn))
4990 16 : SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4991 : }
4992 1425951 : if (LABEL_P (insn))
4993 : break;
4994 1425950 : insn = NEXT_INSN (insn);
4995 : }
4996 1425926 : if (BB_FOOTER (bb))
4997 : {
4998 26 : insn = BB_END (bb);
4999 26 : SET_NEXT_INSN (insn) = BB_FOOTER (bb);
5000 26 : SET_PREV_INSN (BB_FOOTER (bb)) = insn;
5001 54 : while (NEXT_INSN (insn))
5002 : insn = NEXT_INSN (insn);
5003 26 : SET_NEXT_INSN (insn) = next;
5004 26 : if (next)
5005 17 : SET_PREV_INSN (next) = insn;
5006 : else
5007 9 : set_last_insn (insn);
5008 : }
5009 : }
5010 5765842 : if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
5011 5733514 : to = &BB_HEADER (bb->next_bb);
5012 : else
5013 : to = &cfg_layout_function_footer;
5014 :
5015 5765842 : rtl_delete_block (bb);
5016 :
5017 5765842 : if (prev)
5018 5765842 : prev = NEXT_INSN (prev);
5019 : else
5020 0 : prev = get_insns ();
5021 5765842 : if (next)
5022 5733511 : next = PREV_INSN (next);
5023 : else
5024 32331 : next = get_last_insn ();
5025 :
5026 11531684 : if (next && NEXT_INSN (next) != prev)
5027 : {
5028 1785 : remaints = unlink_insn_chain (prev, next);
5029 1785 : insn = remaints;
5030 3937 : while (NEXT_INSN (insn))
5031 : insn = NEXT_INSN (insn);
5032 1785 : SET_NEXT_INSN (insn) = *to;
5033 1785 : if (*to)
5034 344 : SET_PREV_INSN (*to) = insn;
5035 1785 : *to = remaints;
5036 : }
5037 5765842 : }
5038 :
5039 : /* Return true when blocks A and B can be safely merged. */
5040 :
5041 : static bool
5042 2981925 : cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
5043 : {
5044 : /* If we are partitioning hot/cold basic blocks, we don't want to
5045 : mess up unconditional or indirect jumps that cross between hot
5046 : and cold sections.
5047 :
5048 : Basic block partitioning may result in some jumps that appear to
5049 : be optimizable (or blocks that appear to be mergeable), but which really
5050 : must be left untouched (they are required to make it safely across
5051 : partition boundaries). See the comments at the top of
5052 : bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
5053 :
5054 2981925 : if (BB_PARTITION (a) != BB_PARTITION (b))
5055 : return false;
5056 :
5057 : /* Protect the loop latches. */
5058 2817035 : if (current_loops && b->loop_father->latch == b)
5059 : return false;
5060 :
5061 : /* If we would end up moving B's instructions, make sure it doesn't fall
5062 : through into the exit block, since we cannot recover from a fallthrough
5063 : edge into the exit block occurring in the middle of a function. */
5064 2439031 : if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
5065 : {
5066 1493276 : edge e = find_fallthru_edge (b->succs);
5067 1493276 : if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5068 : return false;
5069 : }
5070 :
5071 : /* There must be exactly one edge in between the blocks. */
5072 1764478 : return (single_succ_p (a)
5073 1764478 : && single_succ (a) == b
5074 1764478 : && single_pred_p (b) == 1
5075 1738929 : && a != b
5076 : /* Must be simple edge. */
5077 1738929 : && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
5078 1738929 : && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
5079 1738929 : && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
5080 : /* If the jump insn has side effects, we can't kill the edge.
5081 : When not optimizing, try_redirect_by_replacing_jump will
5082 : not allow us to redirect an edge by replacing a table jump. */
5083 3503407 : && (!JUMP_P (BB_END (a))
5084 62475 : || ((!optimize || reload_completed)
5085 52307 : ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
5086 : }
5087 :
5088 : /* Merge block A and B. The blocks must be mergeable. */
5089 :
5090 : static void
5091 868052 : cfg_layout_merge_blocks (basic_block a, basic_block b)
5092 : {
5093 : /* If B is a forwarder block whose outgoing edge has no location, we'll
5094 : propagate the locus of the edge between A and B onto it. */
5095 868052 : const bool forward_edge_locus
5096 868052 : = (b->flags & BB_FORWARDER_BLOCK) != 0
5097 868052 : && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
5098 868052 : rtx_insn *insn;
5099 :
5100 868052 : gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
5101 :
5102 868052 : if (dump_file)
5103 77 : fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
5104 : a->index);
5105 :
5106 : /* If there was a CODE_LABEL beginning B, delete it. */
5107 868052 : if (LABEL_P (BB_HEAD (b)))
5108 : {
5109 379286 : delete_insn (BB_HEAD (b));
5110 : }
5111 :
5112 : /* We should have fallthru edge in a, or we can do dummy redirection to get
5113 : it cleaned up. */
5114 868052 : if (JUMP_P (BB_END (a)))
5115 24741 : try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
5116 868052 : gcc_assert (!JUMP_P (BB_END (a)));
5117 :
5118 : /* If not optimizing, preserve the locus of the single edge between
5119 : blocks A and B if necessary by emitting a nop. */
5120 868052 : if (!optimize
5121 2763 : && !forward_edge_locus
5122 870348 : && !DECL_IGNORED_P (current_function_decl))
5123 2296 : emit_nop_for_unique_locus_between (a, b);
5124 :
5125 : /* Move things from b->footer after a->footer. */
5126 868052 : if (BB_FOOTER (b))
5127 : {
5128 192444 : if (!BB_FOOTER (a))
5129 192443 : BB_FOOTER (a) = BB_FOOTER (b);
5130 : else
5131 : {
5132 : rtx_insn *last = BB_FOOTER (a);
5133 :
5134 1 : while (NEXT_INSN (last))
5135 : last = NEXT_INSN (last);
5136 1 : SET_NEXT_INSN (last) = BB_FOOTER (b);
5137 1 : SET_PREV_INSN (BB_FOOTER (b)) = last;
5138 : }
5139 192444 : BB_FOOTER (b) = NULL;
5140 : }
5141 :
5142 : /* Move things from b->header before a->footer.
5143 : Note that this may include dead tablejump data, but we don't clean
5144 : those up until we go out of cfglayout mode. */
5145 868052 : if (BB_HEADER (b))
5146 : {
5147 2246 : if (! BB_FOOTER (a))
5148 1155 : BB_FOOTER (a) = BB_HEADER (b);
5149 : else
5150 : {
5151 : rtx_insn *last = BB_HEADER (b);
5152 :
5153 1228 : while (NEXT_INSN (last))
5154 : last = NEXT_INSN (last);
5155 1091 : SET_NEXT_INSN (last) = BB_FOOTER (a);
5156 1091 : SET_PREV_INSN (BB_FOOTER (a)) = last;
5157 1091 : BB_FOOTER (a) = BB_HEADER (b);
5158 : }
5159 2246 : BB_HEADER (b) = NULL;
5160 : }
5161 :
5162 : /* In the case basic blocks are not adjacent, move them around. */
5163 868052 : if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
5164 : {
5165 403477 : insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
5166 :
5167 403477 : emit_insn_after_noloc (insn, BB_END (a), a);
5168 : }
5169 : /* Otherwise just re-associate the instructions. */
5170 : else
5171 : {
5172 464575 : insn = BB_HEAD (b);
5173 464575 : BB_END (a) = BB_END (b);
5174 : }
5175 :
5176 : /* emit_insn_after_noloc doesn't call df_insn_change_bb.
5177 : We need to explicitly call. */
5178 868052 : update_bb_for_insn_chain (insn, BB_END (b), a);
5179 :
5180 : /* Skip possible DELETED_LABEL insn. */
5181 868052 : if (!NOTE_INSN_BASIC_BLOCK_P (insn))
5182 0 : insn = NEXT_INSN (insn);
5183 868052 : gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
5184 868052 : BB_HEAD (b) = BB_END (b) = NULL;
5185 868052 : delete_insn (insn);
5186 :
5187 868052 : df_bb_delete (b->index);
5188 :
5189 868052 : if (forward_edge_locus)
5190 161758 : EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
5191 :
5192 868052 : if (dump_file)
5193 77 : fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
5194 868052 : }
5195 :
5196 : /* Split edge E. */
5197 :
5198 : static basic_block
5199 3626778 : cfg_layout_split_edge (edge e)
5200 : {
5201 3626778 : basic_block new_bb =
5202 7253556 : create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
5203 3626778 : ? NEXT_INSN (BB_END (e->src)) : get_insns (),
5204 : NULL_RTX, e->src);
5205 :
5206 3626778 : if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
5207 1 : BB_COPY_PARTITION (new_bb, e->src);
5208 : else
5209 3626777 : BB_COPY_PARTITION (new_bb, e->dest);
5210 3626778 : make_edge (new_bb, e->dest, EDGE_FALLTHRU);
5211 3626778 : redirect_edge_and_branch_force (e, new_bb);
5212 :
5213 3626778 : return new_bb;
5214 : }
5215 :
5216 : /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
5217 :
5218 : static void
5219 1525 : rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
5220 : {
5221 1525 : }
5222 :
5223 : /* Return true if BB contains only labels or non-executable
5224 : instructions. */
5225 :
5226 : static bool
5227 0 : rtl_block_empty_p (basic_block bb)
5228 : {
5229 0 : rtx_insn *insn;
5230 :
5231 0 : if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
5232 0 : || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
5233 : return true;
5234 :
5235 0 : FOR_BB_INSNS (bb, insn)
5236 0 : if (NONDEBUG_INSN_P (insn)
5237 0 : && (!any_uncondjump_p (insn) || !onlyjump_p (insn)))
5238 : return false;
5239 :
5240 : return true;
5241 : }
5242 :
5243 : /* Split a basic block if it ends with a conditional branch and if
5244 : the other part of the block is not empty. */
5245 :
5246 : static basic_block
5247 0 : rtl_split_block_before_cond_jump (basic_block bb)
5248 : {
5249 0 : rtx_insn *insn;
5250 0 : rtx_insn *split_point = NULL;
5251 0 : rtx_insn *last = NULL;
5252 0 : bool found_code = false;
5253 :
5254 0 : FOR_BB_INSNS (bb, insn)
5255 : {
5256 0 : if (any_condjump_p (insn))
5257 : split_point = last;
5258 0 : else if (NONDEBUG_INSN_P (insn))
5259 0 : found_code = true;
5260 0 : last = insn;
5261 : }
5262 :
5263 : /* Did not find everything. */
5264 0 : if (found_code && split_point)
5265 0 : return split_block (bb, split_point)->dest;
5266 : else
5267 : return NULL;
5268 : }
5269 :
5270 : /* Return true if BB ends with a call, possibly followed by some
5271 : instructions that must stay with the call, false otherwise. */
5272 :
5273 : static bool
5274 9982793 : rtl_block_ends_with_call_p (basic_block bb)
5275 : {
5276 9982793 : rtx_insn *insn = BB_END (bb);
5277 :
5278 9982793 : while (!CALL_P (insn)
5279 11421384 : && insn != BB_HEAD (bb)
5280 24173156 : && (keep_with_call_p (insn)
5281 11366124 : || NOTE_P (insn)
5282 11241580 : || DEBUG_INSN_P (insn)))
5283 2823876 : insn = PREV_INSN (insn);
5284 9982793 : return (CALL_P (insn));
5285 : }
5286 :
5287 : /* Return true if BB ends with a conditional branch, false otherwise. */
5288 :
5289 : static bool
5290 0 : rtl_block_ends_with_condjump_p (const_basic_block bb)
5291 : {
5292 0 : return any_condjump_p (BB_END (bb));
5293 : }
5294 :
5295 : /* Return true if we need to add fake edge to exit.
5296 : Helper function for rtl_flow_call_edges_add. */
5297 :
5298 : static bool
5299 0 : need_fake_edge_p (const rtx_insn *insn)
5300 : {
5301 0 : if (!INSN_P (insn))
5302 : return false;
5303 :
5304 0 : auto call = dyn_cast<const rtx_call_insn *> (insn);
5305 0 : if ((call
5306 0 : && !SIBLING_CALL_P (call)
5307 0 : && !find_reg_note (call, REG_NORETURN, NULL)
5308 0 : && !(RTL_CONST_OR_PURE_CALL_P (call))))
5309 : return true;
5310 :
5311 0 : return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5312 0 : && MEM_VOLATILE_P (PATTERN (insn)))
5313 0 : || (GET_CODE (PATTERN (insn)) == PARALLEL
5314 0 : && asm_noperands (insn) != -1
5315 0 : && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
5316 0 : || GET_CODE (PATTERN (insn)) == ASM_INPUT);
5317 : }
5318 :
5319 : /* Add fake edges to the function exit for any non constant and non noreturn
5320 : calls, volatile inline assembly in the bitmap of blocks specified by
5321 : BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
5322 : that were split.
5323 :
5324 : The goal is to expose cases in which entering a basic block does not imply
5325 : that all subsequent instructions must be executed. */
5326 :
5327 : static int
5328 0 : rtl_flow_call_edges_add (sbitmap blocks)
5329 : {
5330 0 : int i;
5331 0 : int blocks_split = 0;
5332 0 : int last_bb = last_basic_block_for_fn (cfun);
5333 0 : bool check_last_block = false;
5334 :
5335 0 : if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
5336 : return 0;
5337 :
5338 0 : if (! blocks)
5339 : check_last_block = true;
5340 : else
5341 0 : check_last_block = bitmap_bit_p (blocks,
5342 0 : EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
5343 :
5344 : /* In the last basic block, before epilogue generation, there will be
5345 : a fallthru edge to EXIT. Special care is required if the last insn
5346 : of the last basic block is a call because make_edge folds duplicate
5347 : edges, which would result in the fallthru edge also being marked
5348 : fake, which would result in the fallthru edge being removed by
5349 : remove_fake_edges, which would result in an invalid CFG.
5350 :
5351 : Moreover, we can't elide the outgoing fake edge, since the block
5352 : profiler needs to take this into account in order to solve the minimal
5353 : spanning tree in the case that the call doesn't return.
5354 :
5355 : Handle this by adding a dummy instruction in a new last basic block. */
5356 0 : if (check_last_block)
5357 : {
5358 0 : basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
5359 0 : rtx_insn *insn = BB_END (bb);
5360 :
5361 : /* Back up past insns that must be kept in the same block as a call. */
5362 0 : while (insn != BB_HEAD (bb)
5363 0 : && keep_with_call_p (insn))
5364 0 : insn = PREV_INSN (insn);
5365 :
5366 0 : if (need_fake_edge_p (insn))
5367 : {
5368 0 : edge e;
5369 :
5370 0 : e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5371 0 : if (e)
5372 : {
5373 0 : insert_insn_on_edge (gen_use (const0_rtx), e);
5374 0 : commit_edge_insertions ();
5375 : }
5376 : }
5377 : }
5378 :
5379 : /* Now add fake edges to the function exit for any non constant
5380 : calls since there is no way that we can determine if they will
5381 : return or not... */
5382 :
5383 0 : for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
5384 : {
5385 0 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
5386 0 : rtx_insn *insn;
5387 0 : rtx_insn *prev_insn;
5388 :
5389 0 : if (!bb)
5390 0 : continue;
5391 :
5392 0 : if (blocks && !bitmap_bit_p (blocks, i))
5393 0 : continue;
5394 :
5395 0 : for (insn = BB_END (bb); ; insn = prev_insn)
5396 : {
5397 0 : prev_insn = PREV_INSN (insn);
5398 0 : if (need_fake_edge_p (insn))
5399 : {
5400 0 : edge e;
5401 0 : rtx_insn *split_at_insn = insn;
5402 :
5403 : /* Don't split the block between a call and an insn that should
5404 : remain in the same block as the call. */
5405 0 : if (CALL_P (insn))
5406 0 : while (split_at_insn != BB_END (bb)
5407 0 : && keep_with_call_p (NEXT_INSN (split_at_insn)))
5408 0 : split_at_insn = NEXT_INSN (split_at_insn);
5409 :
5410 : /* The handling above of the final block before the epilogue
5411 : should be enough to verify that there is no edge to the exit
5412 : block in CFG already. Calling make_edge in such case would
5413 : cause us to mark that edge as fake and remove it later. */
5414 :
5415 0 : if (flag_checking && split_at_insn == BB_END (bb))
5416 : {
5417 0 : e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5418 0 : gcc_assert (e == NULL);
5419 : }
5420 :
5421 : /* Note that the following may create a new basic block
5422 : and renumber the existing basic blocks. */
5423 0 : if (split_at_insn != BB_END (bb))
5424 : {
5425 0 : e = split_block (bb, split_at_insn);
5426 0 : if (e)
5427 0 : blocks_split++;
5428 : }
5429 :
5430 0 : edge ne = make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
5431 0 : ne->probability = profile_probability::guessed_never ();
5432 : }
5433 :
5434 0 : if (insn == BB_HEAD (bb))
5435 : break;
5436 : }
5437 : }
5438 :
5439 0 : if (blocks_split)
5440 0 : verify_flow_info ();
5441 :
5442 : return blocks_split;
5443 : }
5444 :
5445 : /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
5446 : the conditional branch target, SECOND_HEAD should be the fall-thru
5447 : there is no need to handle this here the loop versioning code handles
5448 : this. the reason for SECON_HEAD is that it is needed for condition
5449 : in trees, and this should be of the same type since it is a hook. */
5450 : static void
5451 0 : rtl_lv_add_condition_to_bb (basic_block first_head ,
5452 : basic_block second_head ATTRIBUTE_UNUSED,
5453 : basic_block cond_bb, void *comp_rtx)
5454 : {
5455 0 : rtx_code_label *label;
5456 0 : rtx_insn *seq, *jump;
5457 0 : rtx op0 = XEXP ((rtx)comp_rtx, 0);
5458 0 : rtx op1 = XEXP ((rtx)comp_rtx, 1);
5459 0 : enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
5460 0 : machine_mode mode;
5461 :
5462 :
5463 0 : label = block_label (first_head);
5464 0 : mode = GET_MODE (op0);
5465 0 : if (mode == VOIDmode)
5466 0 : mode = GET_MODE (op1);
5467 :
5468 0 : start_sequence ();
5469 0 : op0 = force_operand (op0, NULL_RTX);
5470 0 : op1 = force_operand (op1, NULL_RTX);
5471 0 : do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label,
5472 : profile_probability::uninitialized ());
5473 0 : jump = get_last_insn ();
5474 0 : JUMP_LABEL (jump) = label;
5475 0 : LABEL_NUSES (label)++;
5476 0 : seq = end_sequence ();
5477 :
5478 : /* Add the new cond, in the new head. */
5479 0 : emit_insn_after (seq, BB_END (cond_bb));
5480 0 : }
5481 :
5482 :
5483 : /* Given a block B with unconditional branch at its end, get the
5484 : store the return the branch edge and the fall-thru edge in
5485 : BRANCH_EDGE and FALLTHRU_EDGE respectively. */
5486 : static void
5487 0 : rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
5488 : edge *fallthru_edge)
5489 : {
5490 0 : edge e = EDGE_SUCC (b, 0);
5491 :
5492 0 : if (e->flags & EDGE_FALLTHRU)
5493 : {
5494 0 : *fallthru_edge = e;
5495 0 : *branch_edge = EDGE_SUCC (b, 1);
5496 : }
5497 : else
5498 : {
5499 0 : *branch_edge = e;
5500 0 : *fallthru_edge = EDGE_SUCC (b, 1);
5501 : }
5502 0 : }
5503 :
5504 : void
5505 29285278 : init_rtl_bb_info (basic_block bb)
5506 : {
5507 29285278 : gcc_assert (!bb->il.x.rtl);
5508 29285278 : bb->il.x.head_ = NULL;
5509 29285278 : bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
5510 29285278 : }
5511 :
5512 : static bool
5513 2149 : rtl_bb_info_initialized_p (basic_block bb)
5514 : {
5515 2149 : return bb->il.x.rtl;
5516 : }
5517 :
5518 : /* Returns true if it is possible to remove edge E by redirecting
5519 : it to the destination of the other edge from E->src. */
5520 :
5521 : static bool
5522 150824 : rtl_can_remove_branch_p (const_edge e)
5523 : {
5524 150824 : const_basic_block src = e->src;
5525 150824 : const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
5526 150824 : const rtx_insn *insn = BB_END (src);
5527 150824 : rtx set;
5528 :
5529 : /* The conditions are taken from try_redirect_by_replacing_jump. */
5530 150824 : if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
5531 : return false;
5532 :
5533 150824 : if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
5534 : return false;
5535 :
5536 150824 : if (BB_PARTITION (src) != BB_PARTITION (target))
5537 : return false;
5538 :
5539 150824 : if (!onlyjump_p (insn)
5540 150824 : || tablejump_p (insn, NULL, NULL))
5541 : return false;
5542 :
5543 150824 : set = single_set (insn);
5544 150824 : if (!set || side_effects_p (set))
5545 0 : return false;
5546 :
5547 : return true;
5548 : }
5549 :
5550 : static basic_block
5551 44409 : rtl_duplicate_bb (basic_block bb, copy_bb_data *id)
5552 : {
5553 44409 : bb = cfg_layout_duplicate_bb (bb, id);
5554 44409 : bb->aux = NULL;
5555 44409 : return bb;
5556 : }
5557 :
5558 : /* Do book-keeping of basic block BB for the profile consistency checker.
5559 : Store the counting in RECORD. */
5560 : static void
5561 0 : rtl_account_profile_record (basic_block bb, struct profile_record *record)
5562 : {
5563 0 : rtx_insn *insn;
5564 0 : FOR_BB_INSNS (bb, insn)
5565 0 : if (INSN_P (insn))
5566 : {
5567 0 : record->size += insn_cost (insn, false);
5568 0 : if (profile_info)
5569 : {
5570 0 : if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().initialized_p ()
5571 0 : && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().nonzero_p ()
5572 0 : && bb->count.ipa ().initialized_p ())
5573 0 : record->time
5574 0 : += insn_cost (insn, true) * bb->count.ipa ().to_gcov_type ();
5575 : }
5576 0 : else if (bb->count.initialized_p ()
5577 0 : && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
5578 0 : record->time
5579 0 : += insn_cost (insn, true)
5580 0 : * bb->count.to_sreal_scale
5581 0 : (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
5582 : else
5583 0 : record->time += insn_cost (insn, true);
5584 : }
5585 0 : }
5586 :
5587 : /* Implementation of CFG manipulation for linearized RTL. */
5588 : const struct cfg_hooks rtl_cfg_hooks = {
5589 : IR_RTL_CFGRTL,
5590 : rtl_verify_flow_info,
5591 : rtl_dump_bb,
5592 : rtl_dump_bb_for_graph,
5593 : rtl_dump_bb_as_sarif_properties,
5594 : rtl_create_basic_block,
5595 : rtl_redirect_edge_and_branch,
5596 : rtl_redirect_edge_and_branch_force,
5597 : rtl_can_remove_branch_p,
5598 : rtl_delete_block,
5599 : rtl_split_block,
5600 : rtl_move_block_after,
5601 : rtl_can_merge_blocks, /* can_merge_blocks_p */
5602 : rtl_merge_blocks,
5603 : rtl_predict_edge,
5604 : rtl_predicted_by_p,
5605 : cfg_layout_can_duplicate_bb_p,
5606 : rtl_duplicate_bb,
5607 : rtl_split_edge,
5608 : rtl_make_forwarder_block,
5609 : rtl_tidy_fallthru_edge,
5610 : rtl_force_nonfallthru,
5611 : rtl_block_ends_with_call_p,
5612 : rtl_block_ends_with_condjump_p,
5613 : rtl_flow_call_edges_add,
5614 : NULL, /* execute_on_growing_pred */
5615 : NULL, /* execute_on_shrinking_pred */
5616 : NULL, /* duplicate loop for trees */
5617 : NULL, /* lv_add_condition_to_bb */
5618 : NULL, /* lv_adjust_loop_header_phi*/
5619 : NULL, /* extract_cond_bb_edges */
5620 : NULL, /* flush_pending_stmts */
5621 : rtl_block_empty_p, /* block_empty_p */
5622 : rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5623 : rtl_account_profile_record,
5624 : };
5625 :
5626 : /* Implementation of CFG manipulation for cfg layout RTL, where
5627 : basic block connected via fallthru edges does not have to be adjacent.
5628 : This representation will hopefully become the default one in future
5629 : version of the compiler. */
5630 :
5631 : const struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5632 : IR_RTL_CFGLAYOUT,
5633 : rtl_verify_flow_info_1,
5634 : rtl_dump_bb,
5635 : rtl_dump_bb_for_graph,
5636 : rtl_dump_bb_as_sarif_properties,
5637 : cfg_layout_create_basic_block,
5638 : cfg_layout_redirect_edge_and_branch,
5639 : cfg_layout_redirect_edge_and_branch_force,
5640 : rtl_can_remove_branch_p,
5641 : cfg_layout_delete_block,
5642 : cfg_layout_split_block,
5643 : rtl_move_block_after,
5644 : cfg_layout_can_merge_blocks_p,
5645 : cfg_layout_merge_blocks,
5646 : rtl_predict_edge,
5647 : rtl_predicted_by_p,
5648 : cfg_layout_can_duplicate_bb_p,
5649 : cfg_layout_duplicate_bb,
5650 : cfg_layout_split_edge,
5651 : rtl_make_forwarder_block,
5652 : NULL, /* tidy_fallthru_edge */
5653 : rtl_force_nonfallthru,
5654 : rtl_block_ends_with_call_p,
5655 : rtl_block_ends_with_condjump_p,
5656 : rtl_flow_call_edges_add,
5657 : NULL, /* execute_on_growing_pred */
5658 : NULL, /* execute_on_shrinking_pred */
5659 : duplicate_loop_body_to_header_edge, /* duplicate loop for rtl */
5660 : rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5661 : NULL, /* lv_adjust_loop_header_phi*/
5662 : rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5663 : NULL, /* flush_pending_stmts */
5664 : rtl_block_empty_p, /* block_empty_p */
5665 : rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5666 : rtl_account_profile_record,
5667 : };
5668 :
5669 : #include "gt-cfgrtl.h"
5670 :
5671 : #if __GNUC__ >= 10
5672 : # pragma GCC diagnostic pop
5673 : #endif
|