Daily bump.
[official-gcc.git] / gcc / cfgrtl.c
blobe3a724bddb4547f93986a2a81ecc093037fca2af
1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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.
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.
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
20 /* This file contains low level functions to manipulate the CFG and analyze it
21 that are aware of the RTL intermediate language.
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, 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
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 */
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 "gimplify.h"
67 /* Disable warnings about missing quoting in GCC diagnostics. */
68 #if __GNUC__ >= 10
69 # pragma GCC diagnostic push
70 # pragma GCC diagnostic ignored "-Wformat-diag"
71 #endif
73 /* Holds the interesting leading and trailing notes for the function.
74 Only applicable if the CFG is in cfglayout mode. */
75 static GTY(()) rtx_insn *cfg_layout_function_footer;
76 static GTY(()) rtx_insn *cfg_layout_function_header;
78 static rtx_insn *skip_insns_after_block (basic_block);
79 static void record_effective_endpoints (void);
80 static void fixup_reorder_chain (void);
82 void verify_insn_chain (void);
83 static void fixup_fallthru_exit_predecessor (void);
84 static int can_delete_note_p (const rtx_note *);
85 static int can_delete_label_p (const rtx_code_label *);
86 static basic_block rtl_split_edge (edge);
87 static bool rtl_move_block_after (basic_block, basic_block);
88 static int rtl_verify_flow_info (void);
89 static basic_block cfg_layout_split_block (basic_block, void *);
90 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
91 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
92 static void cfg_layout_delete_block (basic_block);
93 static void rtl_delete_block (basic_block);
94 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
95 static edge rtl_redirect_edge_and_branch (edge, basic_block);
96 static basic_block rtl_split_block (basic_block, void *);
97 static void rtl_dump_bb (FILE *, basic_block, int, dump_flags_t);
98 static int rtl_verify_flow_info_1 (void);
99 static void rtl_make_forwarder_block (edge);
100 static bool rtl_bb_info_initialized_p (basic_block bb);
102 /* Return true if NOTE is not one of the ones that must be kept paired,
103 so that we may simply delete it. */
105 static int
106 can_delete_note_p (const rtx_note *note)
108 switch (NOTE_KIND (note))
110 case NOTE_INSN_DELETED:
111 case NOTE_INSN_BASIC_BLOCK:
112 case NOTE_INSN_EPILOGUE_BEG:
113 return true;
115 default:
116 return false;
120 /* True if a given label can be deleted. */
122 static int
123 can_delete_label_p (const rtx_code_label *label)
125 return (!LABEL_PRESERVE_P (label)
126 /* User declared labels must be preserved. */
127 && LABEL_NAME (label) == 0
128 && !vec_safe_contains<rtx_insn *> (forced_labels,
129 const_cast<rtx_code_label *> (label)));
132 /* Delete INSN by patching it out. */
134 void
135 delete_insn (rtx_insn *insn)
137 rtx note;
138 bool really_delete = true;
140 if (LABEL_P (insn))
142 /* Some labels can't be directly removed from the INSN chain, as they
143 might be references via variables, constant pool etc.
144 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
145 if (! can_delete_label_p (as_a <rtx_code_label *> (insn)))
147 const char *name = LABEL_NAME (insn);
148 basic_block bb = BLOCK_FOR_INSN (insn);
149 rtx_insn *bb_note = NEXT_INSN (insn);
151 really_delete = false;
152 PUT_CODE (insn, NOTE);
153 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
154 NOTE_DELETED_LABEL_NAME (insn) = name;
156 /* If the note following the label starts a basic block, and the
157 label is a member of the same basic block, interchange the two. */
158 if (bb_note != NULL_RTX
159 && NOTE_INSN_BASIC_BLOCK_P (bb_note)
160 && bb != NULL
161 && bb == BLOCK_FOR_INSN (bb_note))
163 reorder_insns_nobb (insn, insn, bb_note);
164 BB_HEAD (bb) = bb_note;
165 if (BB_END (bb) == bb_note)
166 BB_END (bb) = insn;
170 remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels);
173 if (really_delete)
175 /* If this insn has already been deleted, something is very wrong. */
176 gcc_assert (!insn->deleted ());
177 if (INSN_P (insn))
178 df_insn_delete (insn);
179 remove_insn (insn);
180 insn->set_deleted ();
183 /* If deleting a jump, decrement the use count of the label. Deleting
184 the label itself should happen in the normal course of block merging. */
185 if (JUMP_P (insn))
187 if (JUMP_LABEL (insn)
188 && LABEL_P (JUMP_LABEL (insn)))
189 LABEL_NUSES (JUMP_LABEL (insn))--;
191 /* If there are more targets, remove them too. */
192 while ((note
193 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
194 && LABEL_P (XEXP (note, 0)))
196 LABEL_NUSES (XEXP (note, 0))--;
197 remove_note (insn, note);
201 /* Also if deleting any insn that references a label as an operand. */
202 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
203 && LABEL_P (XEXP (note, 0)))
205 LABEL_NUSES (XEXP (note, 0))--;
206 remove_note (insn, note);
209 if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
211 rtvec vec = table->get_labels ();
212 int len = GET_NUM_ELEM (vec);
213 int i;
215 for (i = 0; i < len; i++)
217 rtx label = XEXP (RTVEC_ELT (vec, i), 0);
219 /* When deleting code in bulk (e.g. removing many unreachable
220 blocks) we can delete a label that's a target of the vector
221 before deleting the vector itself. */
222 if (!NOTE_P (label))
223 LABEL_NUSES (label)--;
228 /* Like delete_insn but also purge dead edges from BB.
229 Return true if any edges are eliminated. */
231 bool
232 delete_insn_and_edges (rtx_insn *insn)
234 bool purge = false;
236 if (INSN_P (insn) && BLOCK_FOR_INSN (insn))
238 basic_block bb = BLOCK_FOR_INSN (insn);
239 if (BB_END (bb) == insn)
240 purge = true;
241 else if (DEBUG_INSN_P (BB_END (bb)))
242 for (rtx_insn *dinsn = NEXT_INSN (insn);
243 DEBUG_INSN_P (dinsn); dinsn = NEXT_INSN (dinsn))
244 if (BB_END (bb) == dinsn)
246 purge = true;
247 break;
250 delete_insn (insn);
251 if (purge)
252 return purge_dead_edges (BLOCK_FOR_INSN (insn));
253 return false;
256 /* Unlink a chain of insns between START and FINISH, leaving notes
257 that must be paired. If CLEAR_BB is true, we set bb field for
258 insns that cannot be removed to NULL. */
260 void
261 delete_insn_chain (rtx start, rtx_insn *finish, bool clear_bb)
263 /* Unchain the insns one by one. It would be quicker to delete all of these
264 with a single unchaining, rather than one at a time, but we need to keep
265 the NOTE's. */
266 rtx_insn *current = finish;
267 while (1)
269 rtx_insn *prev = PREV_INSN (current);
270 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
272 else
273 delete_insn (current);
275 if (clear_bb && !current->deleted ())
276 set_block_for_insn (current, NULL);
278 if (current == start)
279 break;
280 current = prev;
284 /* Create a new basic block consisting of the instructions between HEAD and END
285 inclusive. This function is designed to allow fast BB construction - reuses
286 the note and basic block struct in BB_NOTE, if any and do not grow
287 BASIC_BLOCK chain and should be used directly only by CFG construction code.
288 END can be NULL in to create new empty basic block before HEAD. Both END
289 and HEAD can be NULL to create basic block at the end of INSN chain.
290 AFTER is the basic block we should be put after. */
292 basic_block
293 create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
294 basic_block after)
296 basic_block bb;
298 if (bb_note
299 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
300 && bb->aux == NULL)
302 /* If we found an existing note, thread it back onto the chain. */
304 rtx_insn *after;
306 if (LABEL_P (head))
307 after = head;
308 else
310 after = PREV_INSN (head);
311 head = bb_note;
314 if (after != bb_note && NEXT_INSN (after) != bb_note)
315 reorder_insns_nobb (bb_note, bb_note, after);
317 else
319 /* Otherwise we must create a note and a basic block structure. */
321 bb = alloc_block ();
323 init_rtl_bb_info (bb);
324 if (!head && !end)
325 head = end = bb_note
326 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
327 else if (LABEL_P (head) && end)
329 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
330 if (head == end)
331 end = bb_note;
333 else
335 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
336 head = bb_note;
337 if (!end)
338 end = head;
341 NOTE_BASIC_BLOCK (bb_note) = bb;
344 /* Always include the bb note in the block. */
345 if (NEXT_INSN (end) == bb_note)
346 end = bb_note;
348 BB_HEAD (bb) = head;
349 BB_END (bb) = end;
350 bb->index = last_basic_block_for_fn (cfun)++;
351 bb->flags = BB_NEW | BB_RTL;
352 link_block (bb, after);
353 SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
354 df_bb_refs_record (bb->index, false);
355 update_bb_for_insn (bb);
356 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
358 /* Tag the block so that we know it has been used when considering
359 other basic block notes. */
360 bb->aux = bb;
362 return bb;
365 /* Create new basic block consisting of instructions in between HEAD and END
366 and place it to the BB chain after block AFTER. END can be NULL to
367 create a new empty basic block before HEAD. Both END and HEAD can be
368 NULL to create basic block at the end of INSN chain. */
370 static basic_block
371 rtl_create_basic_block (void *headp, void *endp, basic_block after)
373 rtx_insn *head = (rtx_insn *) headp;
374 rtx_insn *end = (rtx_insn *) endp;
375 basic_block bb;
377 /* Grow the basic block array if needed. */
378 if ((size_t) last_basic_block_for_fn (cfun)
379 >= basic_block_info_for_fn (cfun)->length ())
380 vec_safe_grow_cleared (basic_block_info_for_fn (cfun),
381 last_basic_block_for_fn (cfun) + 1);
383 n_basic_blocks_for_fn (cfun)++;
385 bb = create_basic_block_structure (head, end, NULL, after);
386 bb->aux = NULL;
387 return bb;
390 static basic_block
391 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
393 basic_block newbb = rtl_create_basic_block (head, end, after);
395 return newbb;
398 /* Delete the insns in a (non-live) block. We physically delete every
399 non-deleted-note insn, and update the flow graph appropriately.
401 Return nonzero if we deleted an exception handler. */
403 /* ??? Preserving all such notes strikes me as wrong. It would be nice
404 to post-process the stream to remove empty blocks, loops, ranges, etc. */
406 static void
407 rtl_delete_block (basic_block b)
409 rtx_insn *insn, *end;
411 /* If the head of this block is a CODE_LABEL, then it might be the
412 label for an exception handler which can't be reached. We need
413 to remove the label from the exception_handler_label list. */
414 insn = BB_HEAD (b);
416 end = get_last_bb_insn (b);
418 /* Selectively delete the entire chain. */
419 BB_HEAD (b) = NULL;
420 delete_insn_chain (insn, end, true);
423 if (dump_file)
424 fprintf (dump_file, "deleting block %d\n", b->index);
425 df_bb_delete (b->index);
428 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
430 void
431 compute_bb_for_insn (void)
433 basic_block bb;
435 FOR_EACH_BB_FN (bb, cfun)
437 rtx_insn *end = BB_END (bb);
438 rtx_insn *insn;
440 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
442 BLOCK_FOR_INSN (insn) = bb;
443 if (insn == end)
444 break;
449 /* Release the basic_block_for_insn array. */
451 unsigned int
452 free_bb_for_insn (void)
454 rtx_insn *insn;
455 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
456 if (!BARRIER_P (insn))
457 BLOCK_FOR_INSN (insn) = NULL;
458 return 0;
461 namespace {
463 const pass_data pass_data_free_cfg =
465 RTL_PASS, /* type */
466 "*free_cfg", /* name */
467 OPTGROUP_NONE, /* optinfo_flags */
468 TV_NONE, /* tv_id */
469 0, /* properties_required */
470 0, /* properties_provided */
471 PROP_cfg, /* properties_destroyed */
472 0, /* todo_flags_start */
473 0, /* todo_flags_finish */
476 class pass_free_cfg : public rtl_opt_pass
478 public:
479 pass_free_cfg (gcc::context *ctxt)
480 : rtl_opt_pass (pass_data_free_cfg, ctxt)
483 /* opt_pass methods: */
484 virtual unsigned int execute (function *);
486 }; // class pass_free_cfg
488 unsigned int
489 pass_free_cfg::execute (function *)
491 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
492 valid at that point so it would be too late to call df_analyze. */
493 if (DELAY_SLOTS && optimize > 0 && flag_delayed_branch)
495 df_note_add_problem ();
496 df_analyze ();
499 if (crtl->has_bb_partition)
500 insert_section_boundary_note ();
502 free_bb_for_insn ();
503 return 0;
506 } // anon namespace
508 rtl_opt_pass *
509 make_pass_free_cfg (gcc::context *ctxt)
511 return new pass_free_cfg (ctxt);
514 /* Return RTX to emit after when we want to emit code on the entry of function. */
515 rtx_insn *
516 entry_of_function (void)
518 return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
519 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
522 /* Emit INSN at the entry point of the function, ensuring that it is only
523 executed once per function. */
524 void
525 emit_insn_at_entry (rtx insn)
527 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
528 edge e = ei_safe_edge (ei);
529 gcc_assert (e->flags & EDGE_FALLTHRU);
531 insert_insn_on_edge (insn, e);
532 commit_edge_insertions ();
535 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
536 (or BARRIER if found) and notify df of the bb change.
537 The insn chain range is inclusive
538 (i.e. both BEGIN and END will be updated. */
540 static void
541 update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
543 rtx_insn *insn;
545 end = NEXT_INSN (end);
546 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
547 if (!BARRIER_P (insn))
548 df_insn_change_bb (insn, bb);
551 /* Update BLOCK_FOR_INSN of insns in BB to BB,
552 and notify df of the change. */
554 void
555 update_bb_for_insn (basic_block bb)
557 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
561 /* Like active_insn_p, except keep the return value use or clobber around
562 even after reload. */
564 static bool
565 flow_active_insn_p (const rtx_insn *insn)
567 if (active_insn_p (insn))
568 return true;
570 /* A clobber of the function return value exists for buggy
571 programs that fail to return a value. Its effect is to
572 keep the return value from being live across the entire
573 function. If we allow it to be skipped, we introduce the
574 possibility for register lifetime confusion.
575 Similarly, keep a USE of the function return value, otherwise
576 the USE is dropped and we could fail to thread jump if USE
577 appears on some paths and not on others, see PR90257. */
578 if ((GET_CODE (PATTERN (insn)) == CLOBBER
579 || GET_CODE (PATTERN (insn)) == USE)
580 && REG_P (XEXP (PATTERN (insn), 0))
581 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
582 return true;
584 return false;
587 /* Return true if the block has no effect and only forwards control flow to
588 its single destination. */
590 bool
591 contains_no_active_insn_p (const_basic_block bb)
593 rtx_insn *insn;
595 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
596 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
597 || !single_succ_p (bb)
598 || (single_succ_edge (bb)->flags & EDGE_FAKE) != 0)
599 return false;
601 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
602 if (INSN_P (insn) && flow_active_insn_p (insn))
603 return false;
605 return (!INSN_P (insn)
606 || (JUMP_P (insn) && simplejump_p (insn))
607 || !flow_active_insn_p (insn));
610 /* Likewise, but protect loop latches, headers and preheaders. */
611 /* FIXME: Make this a cfg hook. */
613 bool
614 forwarder_block_p (const_basic_block bb)
616 if (!contains_no_active_insn_p (bb))
617 return false;
619 /* Protect loop latches, headers and preheaders. */
620 if (current_loops)
622 basic_block dest;
623 if (bb->loop_father->header == bb)
624 return false;
625 dest = EDGE_SUCC (bb, 0)->dest;
626 if (dest->loop_father->header == dest)
627 return false;
630 return true;
633 /* Return nonzero if we can reach target from src by falling through. */
634 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
636 bool
637 can_fallthru (basic_block src, basic_block target)
639 rtx_insn *insn = BB_END (src);
640 rtx_insn *insn2;
641 edge e;
642 edge_iterator ei;
644 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
645 return true;
646 if (src->next_bb != target)
647 return false;
649 /* ??? Later we may add code to move jump tables offline. */
650 if (tablejump_p (insn, NULL, NULL))
651 return false;
653 FOR_EACH_EDGE (e, ei, src->succs)
654 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
655 && e->flags & EDGE_FALLTHRU)
656 return false;
658 insn2 = BB_HEAD (target);
659 if (!active_insn_p (insn2))
660 insn2 = next_active_insn (insn2);
662 return next_active_insn (insn) == insn2;
665 /* Return nonzero if we could reach target from src by falling through,
666 if the target was made adjacent. If we already have a fall-through
667 edge to the exit block, we can't do that. */
668 static bool
669 could_fall_through (basic_block src, basic_block target)
671 edge e;
672 edge_iterator ei;
674 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
675 return true;
676 FOR_EACH_EDGE (e, ei, src->succs)
677 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
678 && e->flags & EDGE_FALLTHRU)
679 return 0;
680 return true;
683 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
684 rtx_note *
685 bb_note (basic_block bb)
687 rtx_insn *note;
689 note = BB_HEAD (bb);
690 if (LABEL_P (note))
691 note = NEXT_INSN (note);
693 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
694 return as_a <rtx_note *> (note);
697 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
698 note associated with the BLOCK. */
700 static rtx_insn *
701 first_insn_after_basic_block_note (basic_block block)
703 rtx_insn *insn;
705 /* Get the first instruction in the block. */
706 insn = BB_HEAD (block);
708 if (insn == NULL_RTX)
709 return NULL;
710 if (LABEL_P (insn))
711 insn = NEXT_INSN (insn);
712 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
714 return NEXT_INSN (insn);
717 /* Creates a new basic block just after basic block BB by splitting
718 everything after specified instruction INSNP. */
720 static basic_block
721 rtl_split_block (basic_block bb, void *insnp)
723 basic_block new_bb;
724 rtx_insn *insn = (rtx_insn *) insnp;
725 edge e;
726 edge_iterator ei;
728 if (!insn)
730 insn = first_insn_after_basic_block_note (bb);
732 if (insn)
734 rtx_insn *next = insn;
736 insn = PREV_INSN (insn);
738 /* If the block contains only debug insns, insn would have
739 been NULL in a non-debug compilation, and then we'd end
740 up emitting a DELETED note. For -fcompare-debug
741 stability, emit the note too. */
742 if (insn != BB_END (bb)
743 && DEBUG_INSN_P (next)
744 && DEBUG_INSN_P (BB_END (bb)))
746 while (next != BB_END (bb) && DEBUG_INSN_P (next))
747 next = NEXT_INSN (next);
749 if (next == BB_END (bb))
750 emit_note_after (NOTE_INSN_DELETED, next);
753 else
754 insn = get_last_insn ();
757 /* We probably should check type of the insn so that we do not create
758 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
759 bother. */
760 if (insn == BB_END (bb))
761 emit_note_after (NOTE_INSN_DELETED, insn);
763 /* Create the new basic block. */
764 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
765 BB_COPY_PARTITION (new_bb, bb);
766 BB_END (bb) = insn;
768 /* Redirect the outgoing edges. */
769 new_bb->succs = bb->succs;
770 bb->succs = NULL;
771 FOR_EACH_EDGE (e, ei, new_bb->succs)
772 e->src = new_bb;
774 /* The new block starts off being dirty. */
775 df_set_bb_dirty (bb);
776 return new_bb;
779 /* Return true if the single edge between blocks A and B is the only place
780 in RTL which holds some unique locus. */
782 static bool
783 unique_locus_on_edge_between_p (basic_block a, basic_block b)
785 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
786 rtx_insn *insn, *end;
788 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
789 return false;
791 /* First scan block A backward. */
792 insn = BB_END (a);
793 end = PREV_INSN (BB_HEAD (a));
794 while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
795 insn = PREV_INSN (insn);
797 if (insn != end && INSN_LOCATION (insn) == goto_locus)
798 return false;
800 /* Then scan block B forward. */
801 insn = BB_HEAD (b);
802 if (insn)
804 end = NEXT_INSN (BB_END (b));
805 while (insn != end && !NONDEBUG_INSN_P (insn))
806 insn = NEXT_INSN (insn);
808 if (insn != end && INSN_HAS_LOCATION (insn)
809 && INSN_LOCATION (insn) == goto_locus)
810 return false;
813 return true;
816 /* If the single edge between blocks A and B is the only place in RTL which
817 holds some unique locus, emit a nop with that locus between the blocks. */
819 static void
820 emit_nop_for_unique_locus_between (basic_block a, basic_block b)
822 if (!unique_locus_on_edge_between_p (a, b))
823 return;
825 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
826 INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
829 /* Blocks A and B are to be merged into a single block A. The insns
830 are already contiguous. */
832 static void
833 rtl_merge_blocks (basic_block a, basic_block b)
835 /* If B is a forwarder block whose outgoing edge has no location, we'll
836 propagate the locus of the edge between A and B onto it. */
837 const bool forward_edge_locus
838 = (b->flags & BB_FORWARDER_BLOCK) != 0
839 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
840 rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
841 rtx_insn *del_first = NULL, *del_last = NULL;
842 rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
843 int b_empty = 0;
845 if (dump_file)
846 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
847 a->index);
849 while (DEBUG_INSN_P (b_end))
850 b_end = PREV_INSN (b_debug_start = b_end);
852 /* If there was a CODE_LABEL beginning B, delete it. */
853 if (LABEL_P (b_head))
855 /* Detect basic blocks with nothing but a label. This can happen
856 in particular at the end of a function. */
857 if (b_head == b_end)
858 b_empty = 1;
860 del_first = del_last = b_head;
861 b_head = NEXT_INSN (b_head);
864 /* Delete the basic block note and handle blocks containing just that
865 note. */
866 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
868 if (b_head == b_end)
869 b_empty = 1;
870 if (! del_last)
871 del_first = b_head;
873 del_last = b_head;
874 b_head = NEXT_INSN (b_head);
877 /* If there was a jump out of A, delete it. */
878 if (JUMP_P (a_end))
880 rtx_insn *prev;
882 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
883 if (!NOTE_P (prev)
884 || NOTE_INSN_BASIC_BLOCK_P (prev)
885 || prev == BB_HEAD (a))
886 break;
888 del_first = a_end;
890 a_end = PREV_INSN (del_first);
892 else if (BARRIER_P (NEXT_INSN (a_end)))
893 del_first = NEXT_INSN (a_end);
895 /* Delete everything marked above as well as crap that might be
896 hanging out between the two blocks. */
897 BB_END (a) = a_end;
898 BB_HEAD (b) = b_empty ? NULL : b_head;
899 delete_insn_chain (del_first, del_last, true);
901 /* If not optimizing, preserve the locus of the single edge between
902 blocks A and B if necessary by emitting a nop. */
903 if (!optimize
904 && !forward_edge_locus
905 && !DECL_IGNORED_P (current_function_decl))
907 emit_nop_for_unique_locus_between (a, b);
908 a_end = BB_END (a);
911 /* Reassociate the insns of B with A. */
912 if (!b_empty)
914 update_bb_for_insn_chain (a_end, b_debug_end, a);
916 BB_END (a) = b_debug_end;
917 BB_HEAD (b) = NULL;
919 else if (b_end != b_debug_end)
921 /* Move any deleted labels and other notes between the end of A
922 and the debug insns that make up B after the debug insns,
923 bringing the debug insns into A while keeping the notes after
924 the end of A. */
925 if (NEXT_INSN (a_end) != b_debug_start)
926 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
927 b_debug_end);
928 update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
929 BB_END (a) = b_debug_end;
932 df_bb_delete (b->index);
934 if (forward_edge_locus)
935 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
937 if (dump_file)
938 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
942 /* Return true when block A and B can be merged. */
944 static bool
945 rtl_can_merge_blocks (basic_block a, basic_block b)
947 /* If we are partitioning hot/cold basic blocks, we don't want to
948 mess up unconditional or indirect jumps that cross between hot
949 and cold sections.
951 Basic block partitioning may result in some jumps that appear to
952 be optimizable (or blocks that appear to be mergeable), but which really
953 must be left untouched (they are required to make it safely across
954 partition boundaries). See the comments at the top of
955 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
957 if (BB_PARTITION (a) != BB_PARTITION (b))
958 return false;
960 /* Protect the loop latches. */
961 if (current_loops && b->loop_father->latch == b)
962 return false;
964 /* There must be exactly one edge in between the blocks. */
965 return (single_succ_p (a)
966 && single_succ (a) == b
967 && single_pred_p (b)
968 && a != b
969 /* Must be simple edge. */
970 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
971 && a->next_bb == b
972 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
973 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
974 /* If the jump insn has side effects,
975 we can't kill the edge. */
976 && (!JUMP_P (BB_END (a))
977 || (reload_completed
978 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
981 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
982 exist. */
984 rtx_code_label *
985 block_label (basic_block block)
987 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
988 return NULL;
990 if (!LABEL_P (BB_HEAD (block)))
992 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
995 return as_a <rtx_code_label *> (BB_HEAD (block));
998 /* Remove all barriers from BB_FOOTER of a BB. */
1000 static void
1001 remove_barriers_from_footer (basic_block bb)
1003 rtx_insn *insn = BB_FOOTER (bb);
1005 /* Remove barriers but keep jumptables. */
1006 while (insn)
1008 if (BARRIER_P (insn))
1010 if (PREV_INSN (insn))
1011 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1012 else
1013 BB_FOOTER (bb) = NEXT_INSN (insn);
1014 if (NEXT_INSN (insn))
1015 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1017 if (LABEL_P (insn))
1018 return;
1019 insn = NEXT_INSN (insn);
1023 /* Attempt to perform edge redirection by replacing possibly complex jump
1024 instruction by unconditional jump or removing jump completely. This can
1025 apply only if all edges now point to the same block. The parameters and
1026 return values are equivalent to redirect_edge_and_branch. */
1028 edge
1029 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
1031 basic_block src = e->src;
1032 rtx_insn *insn = BB_END (src);
1033 rtx set;
1034 int fallthru = 0;
1036 /* If we are partitioning hot/cold basic blocks, we don't want to
1037 mess up unconditional or indirect jumps that cross between hot
1038 and cold sections.
1040 Basic block partitioning may result in some jumps that appear to
1041 be optimizable (or blocks that appear to be mergeable), but which really
1042 must be left untouched (they are required to make it safely across
1043 partition boundaries). See the comments at the top of
1044 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1046 if (BB_PARTITION (src) != BB_PARTITION (target))
1047 return NULL;
1049 /* We can replace or remove a complex jump only when we have exactly
1050 two edges. Also, if we have exactly one outgoing edge, we can
1051 redirect that. */
1052 if (EDGE_COUNT (src->succs) >= 3
1053 /* Verify that all targets will be TARGET. Specifically, the
1054 edge that is not E must also go to TARGET. */
1055 || (EDGE_COUNT (src->succs) == 2
1056 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1057 return NULL;
1059 if (!onlyjump_p (insn))
1060 return NULL;
1061 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1062 return NULL;
1064 /* Avoid removing branch with side effects. */
1065 set = single_set (insn);
1066 if (!set || side_effects_p (set))
1067 return NULL;
1069 /* See if we can create the fallthru edge. */
1070 if (in_cfglayout || can_fallthru (src, target))
1072 if (dump_file)
1073 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1074 fallthru = 1;
1076 /* Selectively unlink whole insn chain. */
1077 if (in_cfglayout)
1079 delete_insn_chain (insn, BB_END (src), false);
1080 remove_barriers_from_footer (src);
1082 else
1083 delete_insn_chain (insn, PREV_INSN (BB_HEAD (target)), false);
1086 /* If this already is simplejump, redirect it. */
1087 else if (simplejump_p (insn))
1089 if (e->dest == target)
1090 return NULL;
1091 if (dump_file)
1092 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1093 INSN_UID (insn), e->dest->index, target->index);
1094 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1095 block_label (target), 0))
1097 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1098 return NULL;
1102 /* Cannot do anything for target exit block. */
1103 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1104 return NULL;
1106 /* Or replace possibly complicated jump insn by simple jump insn. */
1107 else
1109 rtx_code_label *target_label = block_label (target);
1110 rtx_insn *barrier;
1111 rtx_insn *label;
1112 rtx_jump_table_data *table;
1114 emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn);
1115 JUMP_LABEL (BB_END (src)) = target_label;
1116 LABEL_NUSES (target_label)++;
1117 if (dump_file)
1118 fprintf (dump_file, "Replacing insn %i by jump %i\n",
1119 INSN_UID (insn), INSN_UID (BB_END (src)));
1122 delete_insn_chain (insn, insn, false);
1124 /* Recognize a tablejump that we are converting to a
1125 simple jump and remove its associated CODE_LABEL
1126 and ADDR_VEC or ADDR_DIFF_VEC. */
1127 if (tablejump_p (insn, &label, &table))
1128 delete_insn_chain (label, table, false);
1130 barrier = next_nonnote_nondebug_insn (BB_END (src));
1131 if (!barrier || !BARRIER_P (barrier))
1132 emit_barrier_after (BB_END (src));
1133 else
1135 if (barrier != NEXT_INSN (BB_END (src)))
1137 /* Move the jump before barrier so that the notes
1138 which originally were or were created before jump table are
1139 inside the basic block. */
1140 rtx_insn *new_insn = BB_END (src);
1142 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1143 PREV_INSN (barrier), src);
1145 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1146 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1148 SET_NEXT_INSN (new_insn) = barrier;
1149 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1151 SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1152 SET_PREV_INSN (barrier) = new_insn;
1157 /* Keep only one edge out and set proper flags. */
1158 if (!single_succ_p (src))
1159 remove_edge (e);
1160 gcc_assert (single_succ_p (src));
1162 e = single_succ_edge (src);
1163 if (fallthru)
1164 e->flags = EDGE_FALLTHRU;
1165 else
1166 e->flags = 0;
1168 e->probability = profile_probability::always ();
1170 if (e->dest != target)
1171 redirect_edge_succ (e, target);
1172 return e;
1175 /* Subroutine of redirect_branch_edge that tries to patch the jump
1176 instruction INSN so that it reaches block NEW. Do this
1177 only when it originally reached block OLD. Return true if this
1178 worked or the original target wasn't OLD, return false if redirection
1179 doesn't work. */
1181 static bool
1182 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1184 rtx_jump_table_data *table;
1185 rtx tmp;
1186 /* Recognize a tablejump and adjust all matching cases. */
1187 if (tablejump_p (insn, NULL, &table))
1189 rtvec vec;
1190 int j;
1191 rtx_code_label *new_label = block_label (new_bb);
1193 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1194 return false;
1195 vec = table->get_labels ();
1197 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1198 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1200 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1201 --LABEL_NUSES (old_label);
1202 ++LABEL_NUSES (new_label);
1205 /* Handle casesi dispatch insns. */
1206 if ((tmp = tablejump_casesi_pattern (insn)) != NULL_RTX
1207 && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label)
1209 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1210 new_label);
1211 --LABEL_NUSES (old_label);
1212 ++LABEL_NUSES (new_label);
1215 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1217 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1218 rtx note;
1220 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1221 return false;
1222 rtx_code_label *new_label = block_label (new_bb);
1224 for (i = 0; i < n; ++i)
1226 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1227 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1228 if (XEXP (old_ref, 0) == old_label)
1230 ASM_OPERANDS_LABEL (tmp, i)
1231 = gen_rtx_LABEL_REF (Pmode, new_label);
1232 --LABEL_NUSES (old_label);
1233 ++LABEL_NUSES (new_label);
1237 if (JUMP_LABEL (insn) == old_label)
1239 JUMP_LABEL (insn) = new_label;
1240 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1241 if (note)
1242 remove_note (insn, note);
1244 else
1246 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1247 if (note)
1248 remove_note (insn, note);
1249 if (JUMP_LABEL (insn) != new_label
1250 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1251 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1253 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1254 != NULL_RTX)
1255 XEXP (note, 0) = new_label;
1257 else
1259 /* ?? We may play the games with moving the named labels from
1260 one basic block to the other in case only one computed_jump is
1261 available. */
1262 if (computed_jump_p (insn)
1263 /* A return instruction can't be redirected. */
1264 || returnjump_p (insn))
1265 return false;
1267 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1269 /* If the insn doesn't go where we think, we're confused. */
1270 gcc_assert (JUMP_LABEL (insn) == old_label);
1272 /* If the substitution doesn't succeed, die. This can happen
1273 if the back end emitted unrecognizable instructions or if
1274 target is exit block on some arches. Or for crossing
1275 jumps. */
1276 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1277 block_label (new_bb), 0))
1279 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1280 || CROSSING_JUMP_P (insn));
1281 return false;
1285 return true;
1289 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1290 NULL on failure */
1291 static edge
1292 redirect_branch_edge (edge e, basic_block target)
1294 rtx_insn *old_label = BB_HEAD (e->dest);
1295 basic_block src = e->src;
1296 rtx_insn *insn = BB_END (src);
1298 /* We can only redirect non-fallthru edges of jump insn. */
1299 if (e->flags & EDGE_FALLTHRU)
1300 return NULL;
1301 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1302 return NULL;
1304 if (!currently_expanding_to_rtl)
1306 if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1307 return NULL;
1309 else
1310 /* When expanding this BB might actually contain multiple
1311 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1312 Redirect all of those that match our label. */
1313 FOR_BB_INSNS (src, insn)
1314 if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1315 old_label, target))
1316 return NULL;
1318 if (dump_file)
1319 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1320 e->src->index, e->dest->index, target->index);
1322 if (e->dest != target)
1323 e = redirect_edge_succ_nodup (e, target);
1325 return e;
1328 /* Called when edge E has been redirected to a new destination,
1329 in order to update the region crossing flag on the edge and
1330 jump. */
1332 static void
1333 fixup_partition_crossing (edge e)
1335 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1336 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1337 return;
1338 /* If we redirected an existing edge, it may already be marked
1339 crossing, even though the new src is missing a reg crossing note.
1340 But make sure reg crossing note doesn't already exist before
1341 inserting. */
1342 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1344 e->flags |= EDGE_CROSSING;
1345 if (JUMP_P (BB_END (e->src)))
1346 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1348 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1350 e->flags &= ~EDGE_CROSSING;
1351 /* Remove the section crossing note from jump at end of
1352 src if it exists, and if no other successors are
1353 still crossing. */
1354 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1356 bool has_crossing_succ = false;
1357 edge e2;
1358 edge_iterator ei;
1359 FOR_EACH_EDGE (e2, ei, e->src->succs)
1361 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1362 if (has_crossing_succ)
1363 break;
1365 if (!has_crossing_succ)
1366 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1371 /* Called when block BB has been reassigned to the cold partition,
1372 because it is now dominated by another cold block,
1373 to ensure that the region crossing attributes are updated. */
1375 static void
1376 fixup_new_cold_bb (basic_block bb)
1378 edge e;
1379 edge_iterator ei;
1381 /* This is called when a hot bb is found to now be dominated
1382 by a cold bb and therefore needs to become cold. Therefore,
1383 its preds will no longer be region crossing. Any non-dominating
1384 preds that were previously hot would also have become cold
1385 in the caller for the same region. Any preds that were previously
1386 region-crossing will be adjusted in fixup_partition_crossing. */
1387 FOR_EACH_EDGE (e, ei, bb->preds)
1389 fixup_partition_crossing (e);
1392 /* Possibly need to make bb's successor edges region crossing,
1393 or remove stale region crossing. */
1394 FOR_EACH_EDGE (e, ei, bb->succs)
1396 /* We can't have fall-through edges across partition boundaries.
1397 Note that force_nonfallthru will do any necessary partition
1398 boundary fixup by calling fixup_partition_crossing itself. */
1399 if ((e->flags & EDGE_FALLTHRU)
1400 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1401 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1402 force_nonfallthru (e);
1403 else
1404 fixup_partition_crossing (e);
1408 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1409 expense of adding new instructions or reordering basic blocks.
1411 Function can be also called with edge destination equivalent to the TARGET.
1412 Then it should try the simplifications and do nothing if none is possible.
1414 Return edge representing the branch if transformation succeeded. Return NULL
1415 on failure.
1416 We still return NULL in case E already destinated TARGET and we didn't
1417 managed to simplify instruction stream. */
1419 static edge
1420 rtl_redirect_edge_and_branch (edge e, basic_block target)
1422 edge ret;
1423 basic_block src = e->src;
1424 basic_block dest = e->dest;
1426 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1427 return NULL;
1429 if (dest == target)
1430 return e;
1432 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1434 df_set_bb_dirty (src);
1435 fixup_partition_crossing (ret);
1436 return ret;
1439 ret = redirect_branch_edge (e, target);
1440 if (!ret)
1441 return NULL;
1443 df_set_bb_dirty (src);
1444 fixup_partition_crossing (ret);
1445 return ret;
1448 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1450 void
1451 emit_barrier_after_bb (basic_block bb)
1453 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1454 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1455 || current_ir_type () == IR_RTL_CFGLAYOUT);
1456 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1458 rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1460 if (BB_FOOTER (bb))
1462 rtx_insn *footer_tail = BB_FOOTER (bb);
1464 while (NEXT_INSN (footer_tail))
1465 footer_tail = NEXT_INSN (footer_tail);
1466 if (!BARRIER_P (footer_tail))
1468 SET_NEXT_INSN (footer_tail) = insn;
1469 SET_PREV_INSN (insn) = footer_tail;
1472 else
1473 BB_FOOTER (bb) = insn;
1477 /* Like force_nonfallthru below, but additionally performs redirection
1478 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1479 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1480 simple_return_rtx, indicating which kind of returnjump to create.
1481 It should be NULL otherwise. */
1483 basic_block
1484 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1486 basic_block jump_block, new_bb = NULL, src = e->src;
1487 rtx note;
1488 edge new_edge;
1489 int abnormal_edge_flags = 0;
1490 bool asm_goto_edge = false;
1491 int loc;
1493 /* In the case the last instruction is conditional jump to the next
1494 instruction, first redirect the jump itself and then continue
1495 by creating a basic block afterwards to redirect fallthru edge. */
1496 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1497 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1498 && any_condjump_p (BB_END (e->src))
1499 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1501 rtx note;
1502 edge b = unchecked_make_edge (e->src, target, 0);
1503 bool redirected;
1505 redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1506 block_label (target), 0);
1507 gcc_assert (redirected);
1509 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1510 if (note)
1512 int prob = XINT (note, 0);
1514 b->probability = profile_probability::from_reg_br_prob_note (prob);
1515 e->probability -= e->probability;
1519 if (e->flags & EDGE_ABNORMAL)
1521 /* Irritating special case - fallthru edge to the same block as abnormal
1522 edge.
1523 We can't redirect abnormal edge, but we still can split the fallthru
1524 one and create separate abnormal edge to original destination.
1525 This allows bb-reorder to make such edge non-fallthru. */
1526 gcc_assert (e->dest == target);
1527 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1528 e->flags &= EDGE_FALLTHRU;
1530 else
1532 gcc_assert (e->flags & EDGE_FALLTHRU);
1533 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1535 /* We can't redirect the entry block. Create an empty block
1536 at the start of the function which we use to add the new
1537 jump. */
1538 edge tmp;
1539 edge_iterator ei;
1540 bool found = false;
1542 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1543 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1544 bb->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1546 /* Make sure new block ends up in correct hot/cold section. */
1547 BB_COPY_PARTITION (bb, e->dest);
1549 /* Change the existing edge's source to be the new block, and add
1550 a new edge from the entry block to the new block. */
1551 e->src = bb;
1552 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1553 (tmp = ei_safe_edge (ei)); )
1555 if (tmp == e)
1557 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1558 found = true;
1559 break;
1561 else
1562 ei_next (&ei);
1565 gcc_assert (found);
1567 vec_safe_push (bb->succs, e);
1568 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1569 EDGE_FALLTHRU);
1573 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1574 don't point to the target or fallthru label. */
1575 if (JUMP_P (BB_END (e->src))
1576 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1577 && (e->flags & EDGE_FALLTHRU)
1578 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1580 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1581 bool adjust_jump_target = false;
1583 for (i = 0; i < n; ++i)
1585 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1587 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1588 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1589 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1590 adjust_jump_target = true;
1592 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1593 asm_goto_edge = true;
1595 if (adjust_jump_target)
1597 rtx_insn *insn = BB_END (e->src);
1598 rtx note;
1599 rtx_insn *old_label = BB_HEAD (e->dest);
1600 rtx_insn *new_label = BB_HEAD (target);
1602 if (JUMP_LABEL (insn) == old_label)
1604 JUMP_LABEL (insn) = new_label;
1605 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1606 if (note)
1607 remove_note (insn, note);
1609 else
1611 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1612 if (note)
1613 remove_note (insn, note);
1614 if (JUMP_LABEL (insn) != new_label
1615 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1616 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1618 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1619 != NULL_RTX)
1620 XEXP (note, 0) = new_label;
1624 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1626 rtx_insn *new_head;
1627 profile_count count = e->count ();
1628 profile_probability probability = e->probability;
1629 /* Create the new structures. */
1631 /* If the old block ended with a tablejump, skip its table
1632 by searching forward from there. Otherwise start searching
1633 forward from the last instruction of the old block. */
1634 rtx_jump_table_data *table;
1635 if (tablejump_p (BB_END (e->src), NULL, &table))
1636 new_head = table;
1637 else
1638 new_head = BB_END (e->src);
1639 new_head = NEXT_INSN (new_head);
1641 jump_block = create_basic_block (new_head, NULL, e->src);
1642 jump_block->count = count;
1644 /* Make sure new block ends up in correct hot/cold section. */
1646 BB_COPY_PARTITION (jump_block, e->src);
1648 /* Wire edge in. */
1649 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1650 new_edge->probability = probability;
1652 /* Redirect old edge. */
1653 redirect_edge_pred (e, jump_block);
1654 e->probability = profile_probability::always ();
1656 /* If e->src was previously region crossing, it no longer is
1657 and the reg crossing note should be removed. */
1658 fixup_partition_crossing (new_edge);
1660 /* If asm goto has any label refs to target's label,
1661 add also edge from asm goto bb to target. */
1662 if (asm_goto_edge)
1664 new_edge->probability = new_edge->probability.apply_scale (1, 2);
1665 jump_block->count = jump_block->count.apply_scale (1, 2);
1666 edge new_edge2 = make_edge (new_edge->src, target,
1667 e->flags & ~EDGE_FALLTHRU);
1668 new_edge2->probability = probability - new_edge->probability;
1671 new_bb = jump_block;
1673 else
1674 jump_block = e->src;
1676 loc = e->goto_locus;
1677 e->flags &= ~EDGE_FALLTHRU;
1678 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1680 if (jump_label == ret_rtx)
1681 emit_jump_insn_after_setloc (targetm.gen_return (),
1682 BB_END (jump_block), loc);
1683 else
1685 gcc_assert (jump_label == simple_return_rtx);
1686 emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1687 BB_END (jump_block), loc);
1689 set_return_jump_label (BB_END (jump_block));
1691 else
1693 rtx_code_label *label = block_label (target);
1694 emit_jump_insn_after_setloc (targetm.gen_jump (label),
1695 BB_END (jump_block), loc);
1696 JUMP_LABEL (BB_END (jump_block)) = label;
1697 LABEL_NUSES (label)++;
1700 /* We might be in cfg layout mode, and if so, the following routine will
1701 insert the barrier correctly. */
1702 emit_barrier_after_bb (jump_block);
1703 redirect_edge_succ_nodup (e, target);
1705 if (abnormal_edge_flags)
1706 make_edge (src, target, abnormal_edge_flags);
1708 df_mark_solutions_dirty ();
1709 fixup_partition_crossing (e);
1710 return new_bb;
1713 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1714 (and possibly create new basic block) to make edge non-fallthru.
1715 Return newly created BB or NULL if none. */
1717 static basic_block
1718 rtl_force_nonfallthru (edge e)
1720 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1723 /* Redirect edge even at the expense of creating new jump insn or
1724 basic block. Return new basic block if created, NULL otherwise.
1725 Conversion must be possible. */
1727 static basic_block
1728 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1730 if (redirect_edge_and_branch (e, target)
1731 || e->dest == target)
1732 return NULL;
1734 /* In case the edge redirection failed, try to force it to be non-fallthru
1735 and redirect newly created simplejump. */
1736 df_set_bb_dirty (e->src);
1737 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1740 /* The given edge should potentially be a fallthru edge. If that is in
1741 fact true, delete the jump and barriers that are in the way. */
1743 static void
1744 rtl_tidy_fallthru_edge (edge e)
1746 rtx_insn *q;
1747 basic_block b = e->src, c = b->next_bb;
1749 /* ??? In a late-running flow pass, other folks may have deleted basic
1750 blocks by nopping out blocks, leaving multiple BARRIERs between here
1751 and the target label. They ought to be chastised and fixed.
1753 We can also wind up with a sequence of undeletable labels between
1754 one block and the next.
1756 So search through a sequence of barriers, labels, and notes for
1757 the head of block C and assert that we really do fall through. */
1759 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1760 if (NONDEBUG_INSN_P (q))
1761 return;
1763 /* Remove what will soon cease being the jump insn from the source block.
1764 If block B consisted only of this single jump, turn it into a deleted
1765 note. */
1766 q = BB_END (b);
1767 if (JUMP_P (q)
1768 && onlyjump_p (q)
1769 && (any_uncondjump_p (q)
1770 || single_succ_p (b)))
1772 rtx_insn *label;
1773 rtx_jump_table_data *table;
1775 if (tablejump_p (q, &label, &table))
1777 /* The label is likely mentioned in some instruction before
1778 the tablejump and might not be DCEd, so turn it into
1779 a note instead and move before the tablejump that is going to
1780 be deleted. */
1781 const char *name = LABEL_NAME (label);
1782 PUT_CODE (label, NOTE);
1783 NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1784 NOTE_DELETED_LABEL_NAME (label) = name;
1785 reorder_insns (label, label, PREV_INSN (q));
1786 delete_insn (table);
1789 q = PREV_INSN (q);
1791 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1792 together with the barrier) should never have a fallthru edge. */
1793 else if (JUMP_P (q) && any_uncondjump_p (q))
1794 return;
1796 /* Selectively unlink the sequence. */
1797 if (q != PREV_INSN (BB_HEAD (c)))
1798 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1800 e->flags |= EDGE_FALLTHRU;
1803 /* Should move basic block BB after basic block AFTER. NIY. */
1805 static bool
1806 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1807 basic_block after ATTRIBUTE_UNUSED)
1809 return false;
1812 /* Locate the last bb in the same partition as START_BB. */
1814 static basic_block
1815 last_bb_in_partition (basic_block start_bb)
1817 basic_block bb;
1818 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1820 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1821 return bb;
1823 /* Return bb before the exit block. */
1824 return bb->prev_bb;
1827 /* Split a (typically critical) edge. Return the new block.
1828 The edge must not be abnormal.
1830 ??? The code generally expects to be called on critical edges.
1831 The case of a block ending in an unconditional jump to a
1832 block with multiple predecessors is not handled optimally. */
1834 static basic_block
1835 rtl_split_edge (edge edge_in)
1837 basic_block bb, new_bb;
1838 rtx_insn *before;
1840 /* Abnormal edges cannot be split. */
1841 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1843 /* We are going to place the new block in front of edge destination.
1844 Avoid existence of fallthru predecessors. */
1845 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1847 edge e = find_fallthru_edge (edge_in->dest->preds);
1849 if (e)
1850 force_nonfallthru (e);
1853 /* Create the basic block note. */
1854 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1855 before = BB_HEAD (edge_in->dest);
1856 else
1857 before = NULL;
1859 /* If this is a fall through edge to the exit block, the blocks might be
1860 not adjacent, and the right place is after the source. */
1861 if ((edge_in->flags & EDGE_FALLTHRU)
1862 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1864 before = NEXT_INSN (BB_END (edge_in->src));
1865 bb = create_basic_block (before, NULL, edge_in->src);
1866 BB_COPY_PARTITION (bb, edge_in->src);
1868 else
1870 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1872 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1873 BB_COPY_PARTITION (bb, edge_in->dest);
1875 else
1877 basic_block after = edge_in->dest->prev_bb;
1878 /* If this is post-bb reordering, and the edge crosses a partition
1879 boundary, the new block needs to be inserted in the bb chain
1880 at the end of the src partition (since we put the new bb into
1881 that partition, see below). Otherwise we may end up creating
1882 an extra partition crossing in the chain, which is illegal.
1883 It can't go after the src, because src may have a fall-through
1884 to a different block. */
1885 if (crtl->bb_reorder_complete
1886 && (edge_in->flags & EDGE_CROSSING))
1888 after = last_bb_in_partition (edge_in->src);
1889 before = get_last_bb_insn (after);
1890 /* The instruction following the last bb in partition should
1891 be a barrier, since it cannot end in a fall-through. */
1892 gcc_checking_assert (BARRIER_P (before));
1893 before = NEXT_INSN (before);
1895 bb = create_basic_block (before, NULL, after);
1896 /* Put the split bb into the src partition, to avoid creating
1897 a situation where a cold bb dominates a hot bb, in the case
1898 where src is cold and dest is hot. The src will dominate
1899 the new bb (whereas it might not have dominated dest). */
1900 BB_COPY_PARTITION (bb, edge_in->src);
1904 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1906 /* Can't allow a region crossing edge to be fallthrough. */
1907 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1908 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1910 new_bb = force_nonfallthru (single_succ_edge (bb));
1911 gcc_assert (!new_bb);
1914 /* For non-fallthru edges, we must adjust the predecessor's
1915 jump instruction to target our new block. */
1916 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1918 edge redirected = redirect_edge_and_branch (edge_in, bb);
1919 gcc_assert (redirected);
1921 else
1923 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1925 /* For asm goto even splitting of fallthru edge might
1926 need insn patching, as other labels might point to the
1927 old label. */
1928 rtx_insn *last = BB_END (edge_in->src);
1929 if (last
1930 && JUMP_P (last)
1931 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1932 && (extract_asm_operands (PATTERN (last))
1933 || JUMP_LABEL (last) == before)
1934 && patch_jump_insn (last, before, bb))
1935 df_set_bb_dirty (edge_in->src);
1937 redirect_edge_succ (edge_in, bb);
1940 return bb;
1943 /* Queue instructions for insertion on an edge between two basic blocks.
1944 The new instructions and basic blocks (if any) will not appear in the
1945 CFG until commit_edge_insertions is called. */
1947 void
1948 insert_insn_on_edge (rtx pattern, edge e)
1950 /* We cannot insert instructions on an abnormal critical edge.
1951 It will be easier to find the culprit if we die now. */
1952 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1954 if (e->insns.r == NULL_RTX)
1955 start_sequence ();
1956 else
1957 push_to_sequence (e->insns.r);
1959 emit_insn (pattern);
1961 e->insns.r = get_insns ();
1962 end_sequence ();
1965 /* Update the CFG for the instructions queued on edge E. */
1967 void
1968 commit_one_edge_insertion (edge e)
1970 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1971 basic_block bb;
1973 /* Pull the insns off the edge now since the edge might go away. */
1974 insns = e->insns.r;
1975 e->insns.r = NULL;
1977 /* Figure out where to put these insns. If the destination has
1978 one predecessor, insert there. Except for the exit block. */
1979 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1981 bb = e->dest;
1983 /* Get the location correct wrt a code label, and "nice" wrt
1984 a basic block note, and before everything else. */
1985 tmp = BB_HEAD (bb);
1986 if (LABEL_P (tmp))
1987 tmp = NEXT_INSN (tmp);
1988 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1989 tmp = NEXT_INSN (tmp);
1990 if (tmp == BB_HEAD (bb))
1991 before = tmp;
1992 else if (tmp)
1993 after = PREV_INSN (tmp);
1994 else
1995 after = get_last_insn ();
1998 /* If the source has one successor and the edge is not abnormal,
1999 insert there. Except for the entry block.
2000 Don't do this if the predecessor ends in a jump other than
2001 unconditional simple jump. E.g. for asm goto that points all
2002 its labels at the fallthru basic block, we can't insert instructions
2003 before the asm goto, as the asm goto can have various of side effects,
2004 and can't emit instructions after the asm goto, as it must end
2005 the basic block. */
2006 else if ((e->flags & EDGE_ABNORMAL) == 0
2007 && single_succ_p (e->src)
2008 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2009 && (!JUMP_P (BB_END (e->src))
2010 || simplejump_p (BB_END (e->src))))
2012 bb = e->src;
2014 /* It is possible to have a non-simple jump here. Consider a target
2015 where some forms of unconditional jumps clobber a register. This
2016 happens on the fr30 for example.
2018 We know this block has a single successor, so we can just emit
2019 the queued insns before the jump. */
2020 if (JUMP_P (BB_END (bb)))
2021 before = BB_END (bb);
2022 else
2024 /* We'd better be fallthru, or we've lost track of what's what. */
2025 gcc_assert (e->flags & EDGE_FALLTHRU);
2027 after = BB_END (bb);
2031 /* Otherwise we must split the edge. */
2032 else
2034 bb = split_edge (e);
2036 /* If E crossed a partition boundary, we needed to make bb end in
2037 a region-crossing jump, even though it was originally fallthru. */
2038 if (JUMP_P (BB_END (bb)))
2039 before = BB_END (bb);
2040 else
2041 after = BB_END (bb);
2044 /* Now that we've found the spot, do the insertion. */
2045 if (before)
2047 emit_insn_before_noloc (insns, before, bb);
2048 last = prev_nonnote_insn (before);
2050 else
2051 last = emit_insn_after_noloc (insns, after, bb);
2053 if (returnjump_p (last))
2055 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2056 This is not currently a problem because this only happens
2057 for the (single) epilogue, which already has a fallthru edge
2058 to EXIT. */
2060 e = single_succ_edge (bb);
2061 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2062 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2064 e->flags &= ~EDGE_FALLTHRU;
2065 emit_barrier_after (last);
2067 if (before)
2068 delete_insn (before);
2070 else
2071 gcc_assert (!JUMP_P (last));
2074 /* Update the CFG for all queued instructions. */
2076 void
2077 commit_edge_insertions (void)
2079 basic_block bb;
2081 /* Optimization passes that invoke this routine can cause hot blocks
2082 previously reached by both hot and cold blocks to become dominated only
2083 by cold blocks. This will cause the verification below to fail,
2084 and lead to now cold code in the hot section. In some cases this
2085 may only be visible after newly unreachable blocks are deleted,
2086 which will be done by fixup_partitions. */
2087 fixup_partitions ();
2089 if (!currently_expanding_to_rtl)
2090 checking_verify_flow_info ();
2092 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2093 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2095 edge e;
2096 edge_iterator ei;
2098 FOR_EACH_EDGE (e, ei, bb->succs)
2099 if (e->insns.r)
2101 if (currently_expanding_to_rtl)
2102 rebuild_jump_labels_chain (e->insns.r);
2103 commit_one_edge_insertion (e);
2109 /* Print out RTL-specific basic block information (live information
2110 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2111 documented in dumpfile.h. */
2113 static void
2114 rtl_dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
2116 char *s_indent;
2118 s_indent = (char *) alloca ((size_t) indent + 1);
2119 memset (s_indent, ' ', (size_t) indent);
2120 s_indent[indent] = '\0';
2122 if (df && (flags & TDF_DETAILS))
2124 df_dump_top (bb, outf);
2125 putc ('\n', outf);
2128 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK
2129 && rtl_bb_info_initialized_p (bb))
2131 rtx_insn *last = BB_END (bb);
2132 if (last)
2133 last = NEXT_INSN (last);
2134 for (rtx_insn *insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
2136 if (flags & TDF_DETAILS)
2137 df_dump_insn_top (insn, outf);
2138 if (! (flags & TDF_SLIM))
2139 print_rtl_single (outf, insn);
2140 else
2141 dump_insn_slim (outf, insn);
2142 if (flags & TDF_DETAILS)
2143 df_dump_insn_bottom (insn, outf);
2147 if (df && (flags & TDF_DETAILS))
2149 df_dump_bottom (bb, outf);
2150 putc ('\n', outf);
2155 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2156 for the start of each basic block. FLAGS are the TDF_* masks documented
2157 in dumpfile.h. */
2159 void
2160 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, dump_flags_t flags)
2162 const rtx_insn *tmp_rtx;
2163 if (rtx_first == 0)
2164 fprintf (outf, "(nil)\n");
2165 else
2167 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2168 int max_uid = get_max_uid ();
2169 basic_block *start = XCNEWVEC (basic_block, max_uid);
2170 basic_block *end = XCNEWVEC (basic_block, max_uid);
2171 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2172 basic_block bb;
2174 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2175 insns, but the CFG is not maintained so the basic block info
2176 is not reliable. Therefore it's omitted from the dumps. */
2177 if (! (cfun->curr_properties & PROP_cfg))
2178 flags &= ~TDF_BLOCKS;
2180 if (df)
2181 df_dump_start (outf);
2183 if (cfun->curr_properties & PROP_cfg)
2185 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2187 rtx_insn *x;
2189 start[INSN_UID (BB_HEAD (bb))] = bb;
2190 end[INSN_UID (BB_END (bb))] = bb;
2191 if (flags & TDF_BLOCKS)
2193 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2195 enum bb_state state = IN_MULTIPLE_BB;
2197 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2198 state = IN_ONE_BB;
2199 in_bb_p[INSN_UID (x)] = state;
2201 if (x == BB_END (bb))
2202 break;
2208 for (tmp_rtx = rtx_first; tmp_rtx != NULL; tmp_rtx = NEXT_INSN (tmp_rtx))
2210 if (flags & TDF_BLOCKS)
2212 bb = start[INSN_UID (tmp_rtx)];
2213 if (bb != NULL)
2215 dump_bb_info (outf, bb, 0, dump_flags, true, false);
2216 if (df && (flags & TDF_DETAILS))
2217 df_dump_top (bb, outf);
2220 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2221 && !NOTE_P (tmp_rtx)
2222 && !BARRIER_P (tmp_rtx))
2223 fprintf (outf, ";; Insn is not within a basic block\n");
2224 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2225 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2228 if (flags & TDF_DETAILS)
2229 df_dump_insn_top (tmp_rtx, outf);
2230 if (! (flags & TDF_SLIM))
2231 print_rtl_single (outf, tmp_rtx);
2232 else
2233 dump_insn_slim (outf, tmp_rtx);
2234 if (flags & TDF_DETAILS)
2235 df_dump_insn_bottom (tmp_rtx, outf);
2237 bb = end[INSN_UID (tmp_rtx)];
2238 if (bb != NULL)
2240 if (flags & TDF_BLOCKS)
2242 dump_bb_info (outf, bb, 0, dump_flags, false, true);
2243 if (df && (flags & TDF_DETAILS))
2244 df_dump_bottom (bb, outf);
2245 putc ('\n', outf);
2247 /* Emit a hint if the fallthrough target of current basic block
2248 isn't the one placed right next. */
2249 else if (EDGE_COUNT (bb->succs) > 0)
2251 gcc_assert (BB_END (bb) == tmp_rtx);
2252 const rtx_insn *ninsn = NEXT_INSN (tmp_rtx);
2253 /* Bypass intervening deleted-insn notes and debug insns. */
2254 while (ninsn
2255 && !NONDEBUG_INSN_P (ninsn)
2256 && !start[INSN_UID (ninsn)])
2257 ninsn = NEXT_INSN (ninsn);
2258 edge e = find_fallthru_edge (bb->succs);
2259 if (e && ninsn)
2261 basic_block dest = e->dest;
2262 if (start[INSN_UID (ninsn)] != dest)
2263 fprintf (outf, "%s ; pc falls through to BB %d\n",
2264 print_rtx_head, dest->index);
2270 free (start);
2271 free (end);
2272 free (in_bb_p);
2276 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2278 void
2279 update_br_prob_note (basic_block bb)
2281 rtx note;
2282 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2283 if (!JUMP_P (BB_END (bb)) || !BRANCH_EDGE (bb)->probability.initialized_p ())
2285 if (note)
2287 rtx *note_link, this_rtx;
2289 note_link = &REG_NOTES (BB_END (bb));
2290 for (this_rtx = *note_link; this_rtx; this_rtx = XEXP (this_rtx, 1))
2291 if (this_rtx == note)
2293 *note_link = XEXP (this_rtx, 1);
2294 break;
2297 return;
2299 if (!note
2300 || XINT (note, 0) == BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ())
2301 return;
2302 XINT (note, 0) = BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ();
2305 /* Get the last insn associated with block BB (that includes barriers and
2306 tablejumps after BB). */
2307 rtx_insn *
2308 get_last_bb_insn (basic_block bb)
2310 rtx_jump_table_data *table;
2311 rtx_insn *tmp;
2312 rtx_insn *end = BB_END (bb);
2314 /* Include any jump table following the basic block. */
2315 if (tablejump_p (end, NULL, &table))
2316 end = table;
2318 /* Include any barriers that may follow the basic block. */
2319 tmp = next_nonnote_nondebug_insn_bb (end);
2320 while (tmp && BARRIER_P (tmp))
2322 end = tmp;
2323 tmp = next_nonnote_nondebug_insn_bb (end);
2326 return end;
2329 /* Add all BBs reachable from entry via hot paths into the SET. */
2331 void
2332 find_bbs_reachable_by_hot_paths (hash_set<basic_block> *set)
2334 auto_vec<basic_block, 64> worklist;
2336 set->add (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2337 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2339 while (worklist.length () > 0)
2341 basic_block bb = worklist.pop ();
2342 edge_iterator ei;
2343 edge e;
2345 FOR_EACH_EDGE (e, ei, bb->succs)
2346 if (BB_PARTITION (e->dest) != BB_COLD_PARTITION
2347 && !set->add (e->dest))
2348 worklist.safe_push (e->dest);
2352 /* Sanity check partition hotness to ensure that basic blocks in
2353   the cold partition don't dominate basic blocks in the hot partition.
2354 If FLAG_ONLY is true, report violations as errors. Otherwise
2355 re-mark the dominated blocks as cold, since this is run after
2356 cfg optimizations that may make hot blocks previously reached
2357 by both hot and cold blocks now only reachable along cold paths. */
2359 static auto_vec<basic_block>
2360 find_partition_fixes (bool flag_only)
2362 basic_block bb;
2363 auto_vec<basic_block> bbs_to_fix;
2364 hash_set<basic_block> set;
2366 /* Callers check this. */
2367 gcc_checking_assert (crtl->has_bb_partition);
2369 find_bbs_reachable_by_hot_paths (&set);
2371 FOR_EACH_BB_FN (bb, cfun)
2372 if (!set.contains (bb)
2373 && BB_PARTITION (bb) != BB_COLD_PARTITION)
2375 if (flag_only)
2376 error ("non-cold basic block %d reachable only "
2377 "by paths crossing the cold partition", bb->index);
2378 else
2379 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
2380 bbs_to_fix.safe_push (bb);
2383 return bbs_to_fix;
2386 /* Perform cleanup on the hot/cold bb partitioning after optimization
2387 passes that modify the cfg. */
2389 void
2390 fixup_partitions (void)
2392 if (!crtl->has_bb_partition)
2393 return;
2395 /* Delete any blocks that became unreachable and weren't
2396 already cleaned up, for example during edge forwarding
2397 and convert_jumps_to_returns. This will expose more
2398 opportunities for fixing the partition boundaries here.
2399 Also, the calculation of the dominance graph during verification
2400 will assert if there are unreachable nodes. */
2401 delete_unreachable_blocks ();
2403 /* If there are partitions, do a sanity check on them: A basic block in
2404   a cold partition cannot dominate a basic block in a hot partition.
2405 Fixup any that now violate this requirement, as a result of edge
2406 forwarding and unreachable block deletion.  */
2407 auto_vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2409 /* Do the partition fixup after all necessary blocks have been converted to
2410 cold, so that we only update the region crossings the minimum number of
2411 places, which can require forcing edges to be non fallthru. */
2412 if (! bbs_to_fix.is_empty ())
2416 basic_block bb = bbs_to_fix.pop ();
2417 fixup_new_cold_bb (bb);
2419 while (! bbs_to_fix.is_empty ());
2421 /* Fix up hot cold block grouping if needed. */
2422 if (crtl->bb_reorder_complete && current_ir_type () == IR_RTL_CFGRTL)
2424 basic_block bb, first = NULL, second = NULL;
2425 int current_partition = BB_UNPARTITIONED;
2427 FOR_EACH_BB_FN (bb, cfun)
2429 if (current_partition != BB_UNPARTITIONED
2430 && BB_PARTITION (bb) != current_partition)
2432 if (first == NULL)
2433 first = bb;
2434 else if (second == NULL)
2435 second = bb;
2436 else
2438 /* If we switch partitions for the 3rd, 5th etc. time,
2439 move bbs first (inclusive) .. second (exclusive) right
2440 before bb. */
2441 basic_block prev_first = first->prev_bb;
2442 basic_block prev_second = second->prev_bb;
2443 basic_block prev_bb = bb->prev_bb;
2444 prev_first->next_bb = second;
2445 second->prev_bb = prev_first;
2446 prev_second->next_bb = bb;
2447 bb->prev_bb = prev_second;
2448 prev_bb->next_bb = first;
2449 first->prev_bb = prev_bb;
2450 rtx_insn *prev_first_insn = PREV_INSN (BB_HEAD (first));
2451 rtx_insn *prev_second_insn
2452 = PREV_INSN (BB_HEAD (second));
2453 rtx_insn *prev_bb_insn = PREV_INSN (BB_HEAD (bb));
2454 SET_NEXT_INSN (prev_first_insn) = BB_HEAD (second);
2455 SET_PREV_INSN (BB_HEAD (second)) = prev_first_insn;
2456 SET_NEXT_INSN (prev_second_insn) = BB_HEAD (bb);
2457 SET_PREV_INSN (BB_HEAD (bb)) = prev_second_insn;
2458 SET_NEXT_INSN (prev_bb_insn) = BB_HEAD (first);
2459 SET_PREV_INSN (BB_HEAD (first)) = prev_bb_insn;
2460 second = NULL;
2463 current_partition = BB_PARTITION (bb);
2465 gcc_assert (!second);
2470 /* Verify, in the basic block chain, that there is at most one switch
2471 between hot/cold partitions. This condition will not be true until
2472 after reorder_basic_blocks is called. */
2474 static int
2475 verify_hot_cold_block_grouping (void)
2477 basic_block bb;
2478 int err = 0;
2479 bool switched_sections = false;
2480 int current_partition = BB_UNPARTITIONED;
2482 /* Even after bb reordering is complete, we go into cfglayout mode
2483 again (in compgoto). Ensure we don't call this before going back
2484 into linearized RTL when any layout fixes would have been committed. */
2485 if (!crtl->bb_reorder_complete
2486 || current_ir_type () != IR_RTL_CFGRTL)
2487 return err;
2489 FOR_EACH_BB_FN (bb, cfun)
2491 if (current_partition != BB_UNPARTITIONED
2492 && BB_PARTITION (bb) != current_partition)
2494 if (switched_sections)
2496 error ("multiple hot/cold transitions found (bb %i)",
2497 bb->index);
2498 err = 1;
2500 else
2501 switched_sections = true;
2503 if (!crtl->has_bb_partition)
2504 error ("partition found but function partition flag not set");
2506 current_partition = BB_PARTITION (bb);
2509 return err;
2513 /* Perform several checks on the edges out of each block, such as
2514 the consistency of the branch probabilities, the correctness
2515 of hot/cold partition crossing edges, and the number of expected
2516 successor edges. Also verify that the dominance relationship
2517 between hot/cold blocks is sane. */
2519 static int
2520 rtl_verify_edges (void)
2522 int err = 0;
2523 basic_block bb;
2525 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2527 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2528 int n_eh = 0, n_abnormal = 0;
2529 edge e, fallthru = NULL;
2530 edge_iterator ei;
2531 rtx note;
2532 bool has_crossing_edge = false;
2534 if (JUMP_P (BB_END (bb))
2535 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2536 && EDGE_COUNT (bb->succs) >= 2
2537 && any_condjump_p (BB_END (bb)))
2539 if (!BRANCH_EDGE (bb)->probability.initialized_p ())
2541 if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
2543 error ("verify_flow_info: "
2544 "REG_BR_PROB is set but cfg probability is not");
2545 err = 1;
2548 else if (XINT (note, 0)
2549 != BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ()
2550 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2552 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2553 XINT (note, 0),
2554 BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ());
2555 err = 1;
2559 FOR_EACH_EDGE (e, ei, bb->succs)
2561 bool is_crossing;
2563 if (e->flags & EDGE_FALLTHRU)
2564 n_fallthru++, fallthru = e;
2566 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2567 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2568 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2569 has_crossing_edge |= is_crossing;
2570 if (e->flags & EDGE_CROSSING)
2572 if (!is_crossing)
2574 error ("EDGE_CROSSING incorrectly set across same section");
2575 err = 1;
2577 if (e->flags & EDGE_FALLTHRU)
2579 error ("fallthru edge crosses section boundary in bb %i",
2580 e->src->index);
2581 err = 1;
2583 if (e->flags & EDGE_EH)
2585 error ("EH edge crosses section boundary in bb %i",
2586 e->src->index);
2587 err = 1;
2589 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2591 error ("No region crossing jump at section boundary in bb %i",
2592 bb->index);
2593 err = 1;
2596 else if (is_crossing)
2598 error ("EDGE_CROSSING missing across section boundary");
2599 err = 1;
2602 if ((e->flags & ~(EDGE_DFS_BACK
2603 | EDGE_CAN_FALLTHRU
2604 | EDGE_IRREDUCIBLE_LOOP
2605 | EDGE_LOOP_EXIT
2606 | EDGE_CROSSING
2607 | EDGE_PRESERVE)) == 0)
2608 n_branch++;
2610 if (e->flags & EDGE_ABNORMAL_CALL)
2611 n_abnormal_call++;
2613 if (e->flags & EDGE_SIBCALL)
2614 n_sibcall++;
2616 if (e->flags & EDGE_EH)
2617 n_eh++;
2619 if (e->flags & EDGE_ABNORMAL)
2620 n_abnormal++;
2623 if (!has_crossing_edge
2624 && JUMP_P (BB_END (bb))
2625 && CROSSING_JUMP_P (BB_END (bb)))
2627 print_rtl_with_bb (stderr, get_insns (), TDF_BLOCKS | TDF_DETAILS);
2628 error ("Region crossing jump across same section in bb %i",
2629 bb->index);
2630 err = 1;
2633 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2635 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2636 err = 1;
2638 if (n_eh > 1)
2640 error ("too many exception handling edges in bb %i", bb->index);
2641 err = 1;
2643 if (n_branch
2644 && (!JUMP_P (BB_END (bb))
2645 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2646 || any_condjump_p (BB_END (bb))))))
2648 error ("too many outgoing branch edges from bb %i", bb->index);
2649 err = 1;
2651 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2653 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2654 err = 1;
2656 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2658 error ("wrong number of branch edges after unconditional jump"
2659 " in bb %i", bb->index);
2660 err = 1;
2662 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2663 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2665 error ("wrong amount of branch edges after conditional jump"
2666 " in bb %i", bb->index);
2667 err = 1;
2669 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2671 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2672 err = 1;
2674 if (n_sibcall && !CALL_P (BB_END (bb)))
2676 error ("sibcall edges for non-call insn in bb %i", bb->index);
2677 err = 1;
2679 if (n_abnormal > n_eh
2680 && !(CALL_P (BB_END (bb))
2681 && n_abnormal == n_abnormal_call + n_sibcall)
2682 && (!JUMP_P (BB_END (bb))
2683 || any_condjump_p (BB_END (bb))
2684 || any_uncondjump_p (BB_END (bb))))
2686 error ("abnormal edges for no purpose in bb %i", bb->index);
2687 err = 1;
2690 int has_eh = -1;
2691 FOR_EACH_EDGE (e, ei, bb->preds)
2693 if (has_eh == -1)
2694 has_eh = (e->flags & EDGE_EH);
2695 if ((e->flags & EDGE_EH) == has_eh)
2696 continue;
2697 error ("EH incoming edge mixed with non-EH incoming edges "
2698 "in bb %i", bb->index);
2699 err = 1;
2700 break;
2704 /* If there are partitions, do a sanity check on them: A basic block in
2705   a cold partition cannot dominate a basic block in a hot partition.  */
2706 if (crtl->has_bb_partition && !err
2707 && current_ir_type () == IR_RTL_CFGLAYOUT)
2709 auto_vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2710 err = !bbs_to_fix.is_empty ();
2713 /* Clean up. */
2714 return err;
2717 /* Checks on the instructions within blocks. Currently checks that each
2718 block starts with a basic block note, and that basic block notes and
2719 control flow jumps are not found in the middle of the block. */
2721 static int
2722 rtl_verify_bb_insns (void)
2724 rtx_insn *x;
2725 int err = 0;
2726 basic_block bb;
2728 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2730 /* Now check the header of basic
2731 block. It ought to contain optional CODE_LABEL followed
2732 by NOTE_BASIC_BLOCK. */
2733 x = BB_HEAD (bb);
2734 if (LABEL_P (x))
2736 if (BB_END (bb) == x)
2738 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2739 bb->index);
2740 err = 1;
2743 x = NEXT_INSN (x);
2746 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2748 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2749 bb->index);
2750 err = 1;
2753 if (BB_END (bb) == x)
2754 /* Do checks for empty blocks here. */
2756 else
2757 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2759 if (NOTE_INSN_BASIC_BLOCK_P (x))
2761 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2762 INSN_UID (x), bb->index);
2763 err = 1;
2766 if (x == BB_END (bb))
2767 break;
2769 if (control_flow_insn_p (x))
2771 error ("in basic block %d:", bb->index);
2772 fatal_insn ("flow control insn inside a basic block", x);
2777 /* Clean up. */
2778 return err;
2781 /* Verify that block pointers for instructions in basic blocks, headers and
2782 footers are set appropriately. */
2784 static int
2785 rtl_verify_bb_pointers (void)
2787 int err = 0;
2788 basic_block bb;
2790 /* Check the general integrity of the basic blocks. */
2791 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2793 rtx_insn *insn;
2795 if (!(bb->flags & BB_RTL))
2797 error ("BB_RTL flag not set for block %d", bb->index);
2798 err = 1;
2801 FOR_BB_INSNS (bb, insn)
2802 if (BLOCK_FOR_INSN (insn) != bb)
2804 error ("insn %d basic block pointer is %d, should be %d",
2805 INSN_UID (insn),
2806 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2807 bb->index);
2808 err = 1;
2811 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2812 if (!BARRIER_P (insn)
2813 && BLOCK_FOR_INSN (insn) != NULL)
2815 error ("insn %d in header of bb %d has non-NULL basic block",
2816 INSN_UID (insn), bb->index);
2817 err = 1;
2819 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2820 if (!BARRIER_P (insn)
2821 && BLOCK_FOR_INSN (insn) != NULL)
2823 error ("insn %d in footer of bb %d has non-NULL basic block",
2824 INSN_UID (insn), bb->index);
2825 err = 1;
2829 /* Clean up. */
2830 return err;
2833 /* Verify the CFG and RTL consistency common for both underlying RTL and
2834 cfglayout RTL.
2836 Currently it does following checks:
2838 - overlapping of basic blocks
2839 - insns with wrong BLOCK_FOR_INSN pointers
2840 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2841 - tails of basic blocks (ensure that boundary is necessary)
2842 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2843 and NOTE_INSN_BASIC_BLOCK
2844 - verify that no fall_thru edge crosses hot/cold partition boundaries
2845 - verify that there are no pending RTL branch predictions
2846 - verify that hot blocks are not dominated by cold blocks
2848 In future it can be extended check a lot of other stuff as well
2849 (reachability of basic blocks, life information, etc. etc.). */
2851 static int
2852 rtl_verify_flow_info_1 (void)
2854 int err = 0;
2856 err |= rtl_verify_bb_pointers ();
2858 err |= rtl_verify_bb_insns ();
2860 err |= rtl_verify_edges ();
2862 return err;
2865 /* Walk the instruction chain and verify that bb head/end pointers
2866 are correct, and that instructions are in exactly one bb and have
2867 correct block pointers. */
2869 static int
2870 rtl_verify_bb_insn_chain (void)
2872 basic_block bb;
2873 int err = 0;
2874 rtx_insn *x;
2875 rtx_insn *last_head = get_last_insn ();
2876 basic_block *bb_info;
2877 const int max_uid = get_max_uid ();
2879 bb_info = XCNEWVEC (basic_block, max_uid);
2881 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2883 rtx_insn *head = BB_HEAD (bb);
2884 rtx_insn *end = BB_END (bb);
2886 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2888 /* Verify the end of the basic block is in the INSN chain. */
2889 if (x == end)
2890 break;
2892 /* And that the code outside of basic blocks has NULL bb field. */
2893 if (!BARRIER_P (x)
2894 && BLOCK_FOR_INSN (x) != NULL)
2896 error ("insn %d outside of basic blocks has non-NULL bb field",
2897 INSN_UID (x));
2898 err = 1;
2902 if (!x)
2904 error ("end insn %d for block %d not found in the insn stream",
2905 INSN_UID (end), bb->index);
2906 err = 1;
2909 /* Work backwards from the end to the head of the basic block
2910 to verify the head is in the RTL chain. */
2911 for (; x != NULL_RTX; x = PREV_INSN (x))
2913 /* While walking over the insn chain, verify insns appear
2914 in only one basic block. */
2915 if (bb_info[INSN_UID (x)] != NULL)
2917 error ("insn %d is in multiple basic blocks (%d and %d)",
2918 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2919 err = 1;
2922 bb_info[INSN_UID (x)] = bb;
2924 if (x == head)
2925 break;
2927 if (!x)
2929 error ("head insn %d for block %d not found in the insn stream",
2930 INSN_UID (head), bb->index);
2931 err = 1;
2934 last_head = PREV_INSN (x);
2937 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2939 /* Check that the code before the first basic block has NULL
2940 bb field. */
2941 if (!BARRIER_P (x)
2942 && BLOCK_FOR_INSN (x) != NULL)
2944 error ("insn %d outside of basic blocks has non-NULL bb field",
2945 INSN_UID (x));
2946 err = 1;
2949 free (bb_info);
2951 return err;
2954 /* Verify that fallthru edges point to adjacent blocks in layout order and
2955 that barriers exist after non-fallthru blocks. */
2957 static int
2958 rtl_verify_fallthru (void)
2960 basic_block bb;
2961 int err = 0;
2963 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2965 edge e;
2967 e = find_fallthru_edge (bb->succs);
2968 if (!e)
2970 rtx_insn *insn;
2972 /* Ensure existence of barrier in BB with no fallthru edges. */
2973 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
2975 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
2977 error ("missing barrier after block %i", bb->index);
2978 err = 1;
2979 break;
2981 if (BARRIER_P (insn))
2982 break;
2985 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2986 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2988 rtx_insn *insn;
2990 if (e->src->next_bb != e->dest)
2992 error
2993 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2994 e->src->index, e->dest->index);
2995 err = 1;
2997 else
2998 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2999 insn = NEXT_INSN (insn))
3000 if (BARRIER_P (insn) || NONDEBUG_INSN_P (insn))
3002 error ("verify_flow_info: Incorrect fallthru %i->%i",
3003 e->src->index, e->dest->index);
3004 fatal_insn ("wrong insn in the fallthru edge", insn);
3005 err = 1;
3010 return err;
3013 /* Verify that blocks are laid out in consecutive order. While walking the
3014 instructions, verify that all expected instructions are inside the basic
3015 blocks, and that all returns are followed by barriers. */
3017 static int
3018 rtl_verify_bb_layout (void)
3020 basic_block bb;
3021 int err = 0;
3022 rtx_insn *x, *y;
3023 int num_bb_notes;
3024 rtx_insn * const rtx_first = get_insns ();
3025 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
3027 num_bb_notes = 0;
3029 for (x = rtx_first; x; x = NEXT_INSN (x))
3031 if (NOTE_INSN_BASIC_BLOCK_P (x))
3033 bb = NOTE_BASIC_BLOCK (x);
3035 num_bb_notes++;
3036 if (bb != last_bb_seen->next_bb)
3037 internal_error ("basic blocks not laid down consecutively");
3039 curr_bb = last_bb_seen = bb;
3042 if (!curr_bb)
3044 switch (GET_CODE (x))
3046 case BARRIER:
3047 case NOTE:
3048 break;
3050 case CODE_LABEL:
3051 /* An ADDR_VEC is placed outside any basic block. */
3052 if (NEXT_INSN (x)
3053 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
3054 x = NEXT_INSN (x);
3056 /* But in any case, non-deletable labels can appear anywhere. */
3057 break;
3059 default:
3060 fatal_insn ("insn outside basic block", x);
3064 if (JUMP_P (x)
3065 && returnjump_p (x) && ! condjump_p (x)
3066 && ! ((y = next_nonnote_nondebug_insn (x))
3067 && BARRIER_P (y)))
3068 fatal_insn ("return not followed by barrier", x);
3070 if (curr_bb && x == BB_END (curr_bb))
3071 curr_bb = NULL;
3074 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
3075 internal_error
3076 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
3077 num_bb_notes, n_basic_blocks_for_fn (cfun));
3079 return err;
3082 /* Verify the CFG and RTL consistency common for both underlying RTL and
3083 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3085 Currently it does following checks:
3086 - all checks of rtl_verify_flow_info_1
3087 - test head/end pointers
3088 - check that blocks are laid out in consecutive order
3089 - check that all insns are in the basic blocks
3090 (except the switch handling code, barriers and notes)
3091 - check that all returns are followed by barriers
3092 - check that all fallthru edge points to the adjacent blocks
3093 - verify that there is a single hot/cold partition boundary after bbro */
3095 static int
3096 rtl_verify_flow_info (void)
3098 int err = 0;
3100 err |= rtl_verify_flow_info_1 ();
3102 err |= rtl_verify_bb_insn_chain ();
3104 err |= rtl_verify_fallthru ();
3106 err |= rtl_verify_bb_layout ();
3108 err |= verify_hot_cold_block_grouping ();
3110 return err;
3113 /* Assume that the preceding pass has possibly eliminated jump instructions
3114 or converted the unconditional jumps. Eliminate the edges from CFG.
3115 Return true if any edges are eliminated. */
3117 bool
3118 purge_dead_edges (basic_block bb)
3120 edge e;
3121 rtx_insn *insn = BB_END (bb);
3122 rtx note;
3123 bool purged = false;
3124 bool found;
3125 edge_iterator ei;
3127 if ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb))
3129 insn = PREV_INSN (insn);
3130 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3132 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3133 if (NONJUMP_INSN_P (insn)
3134 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3136 rtx eqnote;
3138 if (! may_trap_p (PATTERN (insn))
3139 || ((eqnote = find_reg_equal_equiv_note (insn))
3140 && ! may_trap_p (XEXP (eqnote, 0))))
3141 remove_note (insn, note);
3144 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3145 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3147 bool remove = false;
3149 /* There are three types of edges we need to handle correctly here: EH
3150 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3151 latter can appear when nonlocal gotos are used. */
3152 if (e->flags & EDGE_ABNORMAL_CALL)
3154 if (!CALL_P (insn))
3155 remove = true;
3156 else if (can_nonlocal_goto (insn))
3158 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3160 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3162 else
3163 remove = true;
3165 else if (e->flags & EDGE_EH)
3166 remove = !can_throw_internal (insn);
3168 if (remove)
3170 remove_edge (e);
3171 df_set_bb_dirty (bb);
3172 purged = true;
3174 else
3175 ei_next (&ei);
3178 if (JUMP_P (insn))
3180 rtx note;
3181 edge b,f;
3182 edge_iterator ei;
3184 /* We do care only about conditional jumps and simplejumps. */
3185 if (!any_condjump_p (insn)
3186 && !returnjump_p (insn)
3187 && !simplejump_p (insn))
3188 return purged;
3190 /* Branch probability/prediction notes are defined only for
3191 condjumps. We've possibly turned condjump into simplejump. */
3192 if (simplejump_p (insn))
3194 note = find_reg_note (insn, REG_BR_PROB, NULL);
3195 if (note)
3196 remove_note (insn, note);
3197 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3198 remove_note (insn, note);
3201 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3203 /* Avoid abnormal flags to leak from computed jumps turned
3204 into simplejumps. */
3206 e->flags &= ~EDGE_ABNORMAL;
3208 /* See if this edge is one we should keep. */
3209 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3210 /* A conditional jump can fall through into the next
3211 block, so we should keep the edge. */
3213 ei_next (&ei);
3214 continue;
3216 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3217 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3218 /* If the destination block is the target of the jump,
3219 keep the edge. */
3221 ei_next (&ei);
3222 continue;
3224 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3225 && returnjump_p (insn))
3226 /* If the destination block is the exit block, and this
3227 instruction is a return, then keep the edge. */
3229 ei_next (&ei);
3230 continue;
3232 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3233 /* Keep the edges that correspond to exceptions thrown by
3234 this instruction and rematerialize the EDGE_ABNORMAL
3235 flag we just cleared above. */
3237 e->flags |= EDGE_ABNORMAL;
3238 ei_next (&ei);
3239 continue;
3242 /* We do not need this edge. */
3243 df_set_bb_dirty (bb);
3244 purged = true;
3245 remove_edge (e);
3248 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3249 return purged;
3251 if (dump_file)
3252 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3254 if (!optimize)
3255 return purged;
3257 /* Redistribute probabilities. */
3258 if (single_succ_p (bb))
3260 single_succ_edge (bb)->probability = profile_probability::always ();
3262 else
3264 note = find_reg_note (insn, REG_BR_PROB, NULL);
3265 if (!note)
3266 return purged;
3268 b = BRANCH_EDGE (bb);
3269 f = FALLTHRU_EDGE (bb);
3270 b->probability = profile_probability::from_reg_br_prob_note
3271 (XINT (note, 0));
3272 f->probability = b->probability.invert ();
3275 return purged;
3277 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3279 /* First, there should not be any EH or ABCALL edges resulting
3280 from non-local gotos and the like. If there were, we shouldn't
3281 have created the sibcall in the first place. Second, there
3282 should of course never have been a fallthru edge. */
3283 gcc_assert (single_succ_p (bb));
3284 gcc_assert (single_succ_edge (bb)->flags
3285 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3287 return 0;
3290 /* If we don't see a jump insn, we don't know exactly why the block would
3291 have been broken at this point. Look for a simple, non-fallthru edge,
3292 as these are only created by conditional branches. If we find such an
3293 edge we know that there used to be a jump here and can then safely
3294 remove all non-fallthru edges. */
3295 found = false;
3296 FOR_EACH_EDGE (e, ei, bb->succs)
3297 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3299 found = true;
3300 break;
3303 if (!found)
3304 return purged;
3306 /* Remove all but the fake and fallthru edges. The fake edge may be
3307 the only successor for this block in the case of noreturn
3308 calls. */
3309 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3311 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3313 df_set_bb_dirty (bb);
3314 remove_edge (e);
3315 purged = true;
3317 else
3318 ei_next (&ei);
3321 gcc_assert (single_succ_p (bb));
3323 single_succ_edge (bb)->probability = profile_probability::always ();
3325 if (dump_file)
3326 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3327 bb->index);
3328 return purged;
3331 /* Search all basic blocks for potentially dead edges and purge them. Return
3332 true if some edge has been eliminated. */
3334 bool
3335 purge_all_dead_edges (void)
3337 int purged = false;
3338 basic_block bb;
3340 FOR_EACH_BB_FN (bb, cfun)
3342 bool purged_here = purge_dead_edges (bb);
3344 purged |= purged_here;
3347 return purged;
3350 /* This is used by a few passes that emit some instructions after abnormal
3351 calls, moving the basic block's end, while they in fact do want to emit
3352 them on the fallthru edge. Look for abnormal call edges, find backward
3353 the call in the block and insert the instructions on the edge instead.
3355 Similarly, handle instructions throwing exceptions internally.
3357 Return true when instructions have been found and inserted on edges. */
3359 bool
3360 fixup_abnormal_edges (void)
3362 bool inserted = false;
3363 basic_block bb;
3365 FOR_EACH_BB_FN (bb, cfun)
3367 edge e;
3368 edge_iterator ei;
3370 /* Look for cases we are interested in - calls or instructions causing
3371 exceptions. */
3372 FOR_EACH_EDGE (e, ei, bb->succs)
3373 if ((e->flags & EDGE_ABNORMAL_CALL)
3374 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3375 == (EDGE_ABNORMAL | EDGE_EH)))
3376 break;
3378 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3380 rtx_insn *insn;
3382 /* Get past the new insns generated. Allow notes, as the insns
3383 may be already deleted. */
3384 insn = BB_END (bb);
3385 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3386 && !can_throw_internal (insn)
3387 && insn != BB_HEAD (bb))
3388 insn = PREV_INSN (insn);
3390 if (CALL_P (insn) || can_throw_internal (insn))
3392 rtx_insn *stop, *next;
3394 e = find_fallthru_edge (bb->succs);
3396 stop = NEXT_INSN (BB_END (bb));
3397 BB_END (bb) = insn;
3399 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3401 next = NEXT_INSN (insn);
3402 if (INSN_P (insn))
3404 delete_insn (insn);
3406 /* Sometimes there's still the return value USE.
3407 If it's placed after a trapping call (i.e. that
3408 call is the last insn anyway), we have no fallthru
3409 edge. Simply delete this use and don't try to insert
3410 on the non-existent edge.
3411 Similarly, sometimes a call that can throw is
3412 followed in the source with __builtin_unreachable (),
3413 meaning that there is UB if the call returns rather
3414 than throws. If there weren't any instructions
3415 following such calls before, supposedly even the ones
3416 we've deleted aren't significant and can be
3417 removed. */
3418 if (e)
3420 /* We're not deleting it, we're moving it. */
3421 insn->set_undeleted ();
3422 SET_PREV_INSN (insn) = NULL_RTX;
3423 SET_NEXT_INSN (insn) = NULL_RTX;
3425 insert_insn_on_edge (insn, e);
3426 inserted = true;
3429 else if (!BARRIER_P (insn))
3430 set_block_for_insn (insn, NULL);
3434 /* It may be that we don't find any trapping insn. In this
3435 case we discovered quite late that the insn that had been
3436 marked as can_throw_internal in fact couldn't trap at all.
3437 So we should in fact delete the EH edges out of the block. */
3438 else
3439 purge_dead_edges (bb);
3443 return inserted;
3446 /* Delete the unconditional jump INSN and adjust the CFG correspondingly.
3447 Note that the INSN should be deleted *after* removing dead edges, so
3448 that the kept edge is the fallthrough edge for a (set (pc) (pc))
3449 but not for a (set (pc) (label_ref FOO)). */
3451 void
3452 update_cfg_for_uncondjump (rtx_insn *insn)
3454 basic_block bb = BLOCK_FOR_INSN (insn);
3455 gcc_assert (BB_END (bb) == insn);
3457 purge_dead_edges (bb);
3459 if (current_ir_type () != IR_RTL_CFGLAYOUT)
3461 if (!find_fallthru_edge (bb->succs))
3463 auto barrier = next_nonnote_nondebug_insn (insn);
3464 if (!barrier || !BARRIER_P (barrier))
3465 emit_barrier_after (insn);
3467 return;
3470 delete_insn (insn);
3471 if (EDGE_COUNT (bb->succs) == 1)
3473 rtx_insn *insn;
3475 single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
3477 /* Remove barriers from the footer if there are any. */
3478 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
3479 if (BARRIER_P (insn))
3481 if (PREV_INSN (insn))
3482 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
3483 else
3484 BB_FOOTER (bb) = NEXT_INSN (insn);
3485 if (NEXT_INSN (insn))
3486 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
3488 else if (LABEL_P (insn))
3489 break;
3493 /* Cut the insns from FIRST to LAST out of the insns stream. */
3495 rtx_insn *
3496 unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3498 rtx_insn *prevfirst = PREV_INSN (first);
3499 rtx_insn *nextlast = NEXT_INSN (last);
3501 SET_PREV_INSN (first) = NULL;
3502 SET_NEXT_INSN (last) = NULL;
3503 if (prevfirst)
3504 SET_NEXT_INSN (prevfirst) = nextlast;
3505 if (nextlast)
3506 SET_PREV_INSN (nextlast) = prevfirst;
3507 else
3508 set_last_insn (prevfirst);
3509 if (!prevfirst)
3510 set_first_insn (nextlast);
3511 return first;
3514 /* Skip over inter-block insns occurring after BB which are typically
3515 associated with BB (e.g., barriers). If there are any such insns,
3516 we return the last one. Otherwise, we return the end of BB. */
3518 static rtx_insn *
3519 skip_insns_after_block (basic_block bb)
3521 rtx_insn *insn, *last_insn, *next_head, *prev;
3523 next_head = NULL;
3524 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3525 next_head = BB_HEAD (bb->next_bb);
3527 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3529 if (insn == next_head)
3530 break;
3532 switch (GET_CODE (insn))
3534 case BARRIER:
3535 last_insn = insn;
3536 continue;
3538 case NOTE:
3539 switch (NOTE_KIND (insn))
3541 case NOTE_INSN_BLOCK_END:
3542 gcc_unreachable ();
3543 continue;
3544 default:
3545 continue;
3546 break;
3548 break;
3550 case CODE_LABEL:
3551 if (NEXT_INSN (insn)
3552 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3554 insn = NEXT_INSN (insn);
3555 last_insn = insn;
3556 continue;
3558 break;
3560 default:
3561 break;
3564 break;
3567 /* It is possible to hit contradictory sequence. For instance:
3569 jump_insn
3570 NOTE_INSN_BLOCK_BEG
3571 barrier
3573 Where barrier belongs to jump_insn, but the note does not. This can be
3574 created by removing the basic block originally following
3575 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3577 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3579 prev = PREV_INSN (insn);
3580 if (NOTE_P (insn))
3581 switch (NOTE_KIND (insn))
3583 case NOTE_INSN_BLOCK_END:
3584 gcc_unreachable ();
3585 break;
3586 case NOTE_INSN_DELETED:
3587 case NOTE_INSN_DELETED_LABEL:
3588 case NOTE_INSN_DELETED_DEBUG_LABEL:
3589 continue;
3590 default:
3591 reorder_insns (insn, insn, last_insn);
3595 return last_insn;
3598 /* Locate or create a label for a given basic block. */
3600 static rtx_insn *
3601 label_for_bb (basic_block bb)
3603 rtx_insn *label = BB_HEAD (bb);
3605 if (!LABEL_P (label))
3607 if (dump_file)
3608 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3610 label = block_label (bb);
3613 return label;
3616 /* Locate the effective beginning and end of the insn chain for each
3617 block, as defined by skip_insns_after_block above. */
3619 static void
3620 record_effective_endpoints (void)
3622 rtx_insn *next_insn;
3623 basic_block bb;
3624 rtx_insn *insn;
3626 for (insn = get_insns ();
3627 insn
3628 && NOTE_P (insn)
3629 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3630 insn = NEXT_INSN (insn))
3631 continue;
3632 /* No basic blocks at all? */
3633 gcc_assert (insn);
3635 if (PREV_INSN (insn))
3636 cfg_layout_function_header =
3637 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3638 else
3639 cfg_layout_function_header = NULL;
3641 next_insn = get_insns ();
3642 FOR_EACH_BB_FN (bb, cfun)
3644 rtx_insn *end;
3646 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3647 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3648 PREV_INSN (BB_HEAD (bb)));
3649 end = skip_insns_after_block (bb);
3650 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3651 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3652 next_insn = NEXT_INSN (BB_END (bb));
3655 cfg_layout_function_footer = next_insn;
3656 if (cfg_layout_function_footer)
3657 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3660 namespace {
3662 const pass_data pass_data_into_cfg_layout_mode =
3664 RTL_PASS, /* type */
3665 "into_cfglayout", /* name */
3666 OPTGROUP_NONE, /* optinfo_flags */
3667 TV_CFG, /* tv_id */
3668 0, /* properties_required */
3669 PROP_cfglayout, /* properties_provided */
3670 0, /* properties_destroyed */
3671 0, /* todo_flags_start */
3672 0, /* todo_flags_finish */
3675 class pass_into_cfg_layout_mode : public rtl_opt_pass
3677 public:
3678 pass_into_cfg_layout_mode (gcc::context *ctxt)
3679 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3682 /* opt_pass methods: */
3683 virtual unsigned int execute (function *)
3685 cfg_layout_initialize (0);
3686 return 0;
3689 }; // class pass_into_cfg_layout_mode
3691 } // anon namespace
3693 rtl_opt_pass *
3694 make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3696 return new pass_into_cfg_layout_mode (ctxt);
3699 namespace {
3701 const pass_data pass_data_outof_cfg_layout_mode =
3703 RTL_PASS, /* type */
3704 "outof_cfglayout", /* name */
3705 OPTGROUP_NONE, /* optinfo_flags */
3706 TV_CFG, /* tv_id */
3707 0, /* properties_required */
3708 0, /* properties_provided */
3709 PROP_cfglayout, /* properties_destroyed */
3710 0, /* todo_flags_start */
3711 0, /* todo_flags_finish */
3714 class pass_outof_cfg_layout_mode : public rtl_opt_pass
3716 public:
3717 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3718 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3721 /* opt_pass methods: */
3722 virtual unsigned int execute (function *);
3724 }; // class pass_outof_cfg_layout_mode
3726 unsigned int
3727 pass_outof_cfg_layout_mode::execute (function *fun)
3729 basic_block bb;
3731 FOR_EACH_BB_FN (bb, fun)
3732 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3733 bb->aux = bb->next_bb;
3735 cfg_layout_finalize ();
3737 return 0;
3740 } // anon namespace
3742 rtl_opt_pass *
3743 make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3745 return new pass_outof_cfg_layout_mode (ctxt);
3749 /* Link the basic blocks in the correct order, compacting the basic
3750 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3751 function also clears the basic block header and footer fields.
3753 This function is usually called after a pass (e.g. tracer) finishes
3754 some transformations while in cfglayout mode. The required sequence
3755 of the basic blocks is in a linked list along the bb->aux field.
3756 This functions re-links the basic block prev_bb and next_bb pointers
3757 accordingly, and it compacts and renumbers the blocks.
3759 FIXME: This currently works only for RTL, but the only RTL-specific
3760 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3761 to GIMPLE a long time ago, but it doesn't relink the basic block
3762 chain. It could do that (to give better initial RTL) if this function
3763 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3765 void
3766 relink_block_chain (bool stay_in_cfglayout_mode)
3768 basic_block bb, prev_bb;
3769 int index;
3771 /* Maybe dump the re-ordered sequence. */
3772 if (dump_file)
3774 fprintf (dump_file, "Reordered sequence:\n");
3775 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3776 NUM_FIXED_BLOCKS;
3778 bb = (basic_block) bb->aux, index++)
3780 fprintf (dump_file, " %i ", index);
3781 if (get_bb_original (bb))
3782 fprintf (dump_file, "duplicate of %i\n",
3783 get_bb_original (bb)->index);
3784 else if (forwarder_block_p (bb)
3785 && !LABEL_P (BB_HEAD (bb)))
3786 fprintf (dump_file, "compensation\n");
3787 else
3788 fprintf (dump_file, "bb %i\n", bb->index);
3792 /* Now reorder the blocks. */
3793 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3794 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3795 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3797 bb->prev_bb = prev_bb;
3798 prev_bb->next_bb = bb;
3800 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3801 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3803 /* Then, clean up the aux fields. */
3804 FOR_ALL_BB_FN (bb, cfun)
3806 bb->aux = NULL;
3807 if (!stay_in_cfglayout_mode)
3808 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3811 /* Maybe reset the original copy tables, they are not valid anymore
3812 when we renumber the basic blocks in compact_blocks. If we are
3813 are going out of cfglayout mode, don't re-allocate the tables. */
3814 if (original_copy_tables_initialized_p ())
3815 free_original_copy_tables ();
3816 if (stay_in_cfglayout_mode)
3817 initialize_original_copy_tables ();
3819 /* Finally, put basic_block_info in the new order. */
3820 compact_blocks ();
3824 /* Given a reorder chain, rearrange the code to match. */
3826 static void
3827 fixup_reorder_chain (void)
3829 basic_block bb;
3830 rtx_insn *insn = NULL;
3832 if (cfg_layout_function_header)
3834 set_first_insn (cfg_layout_function_header);
3835 insn = cfg_layout_function_header;
3836 while (NEXT_INSN (insn))
3837 insn = NEXT_INSN (insn);
3840 /* First do the bulk reordering -- rechain the blocks without regard to
3841 the needed changes to jumps and labels. */
3843 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3844 bb->aux)
3846 if (BB_HEADER (bb))
3848 if (insn)
3849 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3850 else
3851 set_first_insn (BB_HEADER (bb));
3852 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3853 insn = BB_HEADER (bb);
3854 while (NEXT_INSN (insn))
3855 insn = NEXT_INSN (insn);
3857 if (insn)
3858 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3859 else
3860 set_first_insn (BB_HEAD (bb));
3861 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3862 insn = BB_END (bb);
3863 if (BB_FOOTER (bb))
3865 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3866 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3867 while (NEXT_INSN (insn))
3868 insn = NEXT_INSN (insn);
3872 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3873 if (cfg_layout_function_footer)
3874 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3876 while (NEXT_INSN (insn))
3877 insn = NEXT_INSN (insn);
3879 set_last_insn (insn);
3880 if (flag_checking)
3881 verify_insn_chain ();
3883 /* Now add jumps and labels as needed to match the blocks new
3884 outgoing edges. */
3886 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3887 bb->aux)
3889 edge e_fall, e_taken, e;
3890 rtx_insn *bb_end_insn;
3891 rtx ret_label = NULL_RTX;
3892 basic_block nb;
3893 edge_iterator ei;
3895 if (EDGE_COUNT (bb->succs) == 0)
3896 continue;
3898 /* Find the old fallthru edge, and another non-EH edge for
3899 a taken jump. */
3900 e_taken = e_fall = NULL;
3902 FOR_EACH_EDGE (e, ei, bb->succs)
3903 if (e->flags & EDGE_FALLTHRU)
3904 e_fall = e;
3905 else if (! (e->flags & EDGE_EH))
3906 e_taken = e;
3908 bb_end_insn = BB_END (bb);
3909 if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
3911 ret_label = JUMP_LABEL (bb_end_jump);
3912 if (any_condjump_p (bb_end_jump))
3914 /* This might happen if the conditional jump has side
3915 effects and could therefore not be optimized away.
3916 Make the basic block to end with a barrier in order
3917 to prevent rtl_verify_flow_info from complaining. */
3918 if (!e_fall)
3920 gcc_assert (!onlyjump_p (bb_end_jump)
3921 || returnjump_p (bb_end_jump)
3922 || (e_taken->flags & EDGE_CROSSING));
3923 emit_barrier_after (bb_end_jump);
3924 continue;
3927 /* If the old fallthru is still next, nothing to do. */
3928 if (bb->aux == e_fall->dest
3929 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3930 continue;
3932 /* The degenerated case of conditional jump jumping to the next
3933 instruction can happen for jumps with side effects. We need
3934 to construct a forwarder block and this will be done just
3935 fine by force_nonfallthru below. */
3936 if (!e_taken)
3939 /* There is another special case: if *neither* block is next,
3940 such as happens at the very end of a function, then we'll
3941 need to add a new unconditional jump. Choose the taken
3942 edge based on known or assumed probability. */
3943 else if (bb->aux != e_taken->dest)
3945 rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
3947 if (note
3948 && profile_probability::from_reg_br_prob_note
3949 (XINT (note, 0)) < profile_probability::even ()
3950 && invert_jump (bb_end_jump,
3951 (e_fall->dest
3952 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3953 ? NULL_RTX
3954 : label_for_bb (e_fall->dest)), 0))
3956 e_fall->flags &= ~EDGE_FALLTHRU;
3957 gcc_checking_assert (could_fall_through
3958 (e_taken->src, e_taken->dest));
3959 e_taken->flags |= EDGE_FALLTHRU;
3960 update_br_prob_note (bb);
3961 e = e_fall, e_fall = e_taken, e_taken = e;
3965 /* If the "jumping" edge is a crossing edge, and the fall
3966 through edge is non-crossing, leave things as they are. */
3967 else if ((e_taken->flags & EDGE_CROSSING)
3968 && !(e_fall->flags & EDGE_CROSSING))
3969 continue;
3971 /* Otherwise we can try to invert the jump. This will
3972 basically never fail, however, keep up the pretense. */
3973 else if (invert_jump (bb_end_jump,
3974 (e_fall->dest
3975 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3976 ? NULL_RTX
3977 : label_for_bb (e_fall->dest)), 0))
3979 e_fall->flags &= ~EDGE_FALLTHRU;
3980 gcc_checking_assert (could_fall_through
3981 (e_taken->src, e_taken->dest));
3982 e_taken->flags |= EDGE_FALLTHRU;
3983 update_br_prob_note (bb);
3984 if (LABEL_NUSES (ret_label) == 0
3985 && single_pred_p (e_taken->dest))
3986 delete_insn (as_a<rtx_insn *> (ret_label));
3987 continue;
3990 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
3992 /* If the old fallthru is still next or if
3993 asm goto doesn't have a fallthru (e.g. when followed by
3994 __builtin_unreachable ()), nothing to do. */
3995 if (! e_fall
3996 || bb->aux == e_fall->dest
3997 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3998 continue;
4000 /* Otherwise we'll have to use the fallthru fixup below. */
4002 else
4004 /* Otherwise we have some return, switch or computed
4005 jump. In the 99% case, there should not have been a
4006 fallthru edge. */
4007 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
4008 continue;
4011 else
4013 /* No fallthru implies a noreturn function with EH edges, or
4014 something similarly bizarre. In any case, we don't need to
4015 do anything. */
4016 if (! e_fall)
4017 continue;
4019 /* If the fallthru block is still next, nothing to do. */
4020 if (bb->aux == e_fall->dest)
4021 continue;
4023 /* A fallthru to exit block. */
4024 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4025 continue;
4028 /* We got here if we need to add a new jump insn.
4029 Note force_nonfallthru can delete E_FALL and thus we have to
4030 save E_FALL->src prior to the call to force_nonfallthru. */
4031 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
4032 if (nb)
4034 nb->aux = bb->aux;
4035 bb->aux = nb;
4036 /* Don't process this new block. */
4037 bb = nb;
4041 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
4043 /* Annoying special case - jump around dead jumptables left in the code. */
4044 FOR_EACH_BB_FN (bb, cfun)
4046 edge e = find_fallthru_edge (bb->succs);
4048 if (e && !can_fallthru (e->src, e->dest))
4049 force_nonfallthru (e);
4052 /* Ensure goto_locus from edges has some instructions with that locus in RTL
4053 when not optimizing. */
4054 if (!optimize && !DECL_IGNORED_P (current_function_decl))
4055 FOR_EACH_BB_FN (bb, cfun)
4057 edge e;
4058 edge_iterator ei;
4060 FOR_EACH_EDGE (e, ei, bb->succs)
4061 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
4062 && !(e->flags & EDGE_ABNORMAL))
4064 edge e2;
4065 edge_iterator ei2;
4066 basic_block dest, nb;
4067 rtx_insn *end;
4069 insn = BB_END (e->src);
4070 end = PREV_INSN (BB_HEAD (e->src));
4071 while (insn != end
4072 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
4073 insn = PREV_INSN (insn);
4074 if (insn != end
4075 && INSN_LOCATION (insn) == e->goto_locus)
4076 continue;
4077 if (simplejump_p (BB_END (e->src))
4078 && !INSN_HAS_LOCATION (BB_END (e->src)))
4080 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
4081 continue;
4083 dest = e->dest;
4084 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4086 /* Non-fallthru edges to the exit block cannot be split. */
4087 if (!(e->flags & EDGE_FALLTHRU))
4088 continue;
4090 else
4092 insn = BB_HEAD (dest);
4093 end = NEXT_INSN (BB_END (dest));
4094 while (insn != end && !NONDEBUG_INSN_P (insn))
4095 insn = NEXT_INSN (insn);
4096 if (insn != end && INSN_HAS_LOCATION (insn)
4097 && INSN_LOCATION (insn) == e->goto_locus)
4098 continue;
4100 nb = split_edge (e);
4101 if (!INSN_P (BB_END (nb)))
4102 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
4103 nb);
4104 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
4106 /* If there are other incoming edges to the destination block
4107 with the same goto locus, redirect them to the new block as
4108 well, this can prevent other such blocks from being created
4109 in subsequent iterations of the loop. */
4110 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
4111 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
4112 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
4113 && e->goto_locus == e2->goto_locus)
4114 redirect_edge_and_branch (e2, nb);
4115 else
4116 ei_next (&ei2);
4121 /* Perform sanity checks on the insn chain.
4122 1. Check that next/prev pointers are consistent in both the forward and
4123 reverse direction.
4124 2. Count insns in chain, going both directions, and check if equal.
4125 3. Check that get_last_insn () returns the actual end of chain. */
4127 DEBUG_FUNCTION void
4128 verify_insn_chain (void)
4130 rtx_insn *x, *prevx, *nextx;
4131 int insn_cnt1, insn_cnt2;
4133 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
4134 x != 0;
4135 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
4136 gcc_assert (PREV_INSN (x) == prevx);
4138 gcc_assert (prevx == get_last_insn ());
4140 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
4141 x != 0;
4142 nextx = x, insn_cnt2++, x = PREV_INSN (x))
4143 gcc_assert (NEXT_INSN (x) == nextx);
4145 gcc_assert (insn_cnt1 == insn_cnt2);
4148 /* If we have assembler epilogues, the block falling through to exit must
4149 be the last one in the reordered chain when we reach final. Ensure
4150 that this condition is met. */
4151 static void
4152 fixup_fallthru_exit_predecessor (void)
4154 edge e;
4155 basic_block bb = NULL;
4157 /* This transformation is not valid before reload, because we might
4158 separate a call from the instruction that copies the return
4159 value. */
4160 gcc_assert (reload_completed);
4162 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4163 if (e)
4164 bb = e->src;
4166 if (bb && bb->aux)
4168 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4170 /* If the very first block is the one with the fall-through exit
4171 edge, we have to split that block. */
4172 if (c == bb)
4174 bb = split_block_after_labels (bb)->dest;
4175 bb->aux = c->aux;
4176 c->aux = bb;
4177 BB_FOOTER (bb) = BB_FOOTER (c);
4178 BB_FOOTER (c) = NULL;
4181 while (c->aux != bb)
4182 c = (basic_block) c->aux;
4184 c->aux = bb->aux;
4185 while (c->aux)
4186 c = (basic_block) c->aux;
4188 c->aux = bb;
4189 bb->aux = NULL;
4193 /* In case there are more than one fallthru predecessors of exit, force that
4194 there is only one. */
4196 static void
4197 force_one_exit_fallthru (void)
4199 edge e, predecessor = NULL;
4200 bool more = false;
4201 edge_iterator ei;
4202 basic_block forwarder, bb;
4204 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4205 if (e->flags & EDGE_FALLTHRU)
4207 if (predecessor == NULL)
4208 predecessor = e;
4209 else
4211 more = true;
4212 break;
4216 if (!more)
4217 return;
4219 /* Exit has several fallthru predecessors. Create a forwarder block for
4220 them. */
4221 forwarder = split_edge (predecessor);
4222 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4223 (e = ei_safe_edge (ei)); )
4225 if (e->src == forwarder
4226 || !(e->flags & EDGE_FALLTHRU))
4227 ei_next (&ei);
4228 else
4229 redirect_edge_and_branch_force (e, forwarder);
4232 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4233 exit block. */
4234 FOR_EACH_BB_FN (bb, cfun)
4236 if (bb->aux == NULL && bb != forwarder)
4238 bb->aux = forwarder;
4239 break;
4244 /* Return true in case it is possible to duplicate the basic block BB. */
4246 static bool
4247 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4249 /* Do not attempt to duplicate tablejumps, as we need to unshare
4250 the dispatch table. This is difficult to do, as the instructions
4251 computing jump destination may be hoisted outside the basic block. */
4252 if (tablejump_p (BB_END (bb), NULL, NULL))
4253 return false;
4255 /* Do not duplicate blocks containing insns that can't be copied. */
4256 if (targetm.cannot_copy_insn_p)
4258 rtx_insn *insn = BB_HEAD (bb);
4259 while (1)
4261 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4262 return false;
4263 if (insn == BB_END (bb))
4264 break;
4265 insn = NEXT_INSN (insn);
4269 return true;
4272 rtx_insn *
4273 duplicate_insn_chain (rtx_insn *from, rtx_insn *to,
4274 class loop *loop, copy_bb_data *id)
4276 rtx_insn *insn, *next, *copy;
4277 rtx_note *last;
4279 /* Avoid updating of boundaries of previous basic block. The
4280 note will get removed from insn stream in fixup. */
4281 last = emit_note (NOTE_INSN_DELETED);
4283 /* Create copy at the end of INSN chain. The chain will
4284 be reordered later. */
4285 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4287 switch (GET_CODE (insn))
4289 case DEBUG_INSN:
4290 /* Don't duplicate label debug insns. */
4291 if (DEBUG_BIND_INSN_P (insn)
4292 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4293 break;
4294 /* FALLTHRU */
4295 case INSN:
4296 case CALL_INSN:
4297 case JUMP_INSN:
4298 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4299 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4300 && ANY_RETURN_P (JUMP_LABEL (insn)))
4301 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4302 maybe_copy_prologue_epilogue_insn (insn, copy);
4303 /* If requested remap dependence info of cliques brought in
4304 via inlining. */
4305 if (id)
4307 subrtx_iterator::array_type array;
4308 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), ALL)
4309 if (MEM_P (*iter) && MEM_EXPR (*iter))
4311 tree op = MEM_EXPR (*iter);
4312 if (TREE_CODE (op) == WITH_SIZE_EXPR)
4313 op = TREE_OPERAND (op, 0);
4314 while (handled_component_p (op))
4315 op = TREE_OPERAND (op, 0);
4316 if ((TREE_CODE (op) == MEM_REF
4317 || TREE_CODE (op) == TARGET_MEM_REF)
4318 && MR_DEPENDENCE_CLIQUE (op) > 1
4319 && (!loop
4320 || (MR_DEPENDENCE_CLIQUE (op)
4321 != loop->owned_clique)))
4323 if (!id->dependence_map)
4324 id->dependence_map = new hash_map<dependence_hash,
4325 unsigned short>;
4326 bool existed;
4327 unsigned short &newc = id->dependence_map->get_or_insert
4328 (MR_DEPENDENCE_CLIQUE (op), &existed);
4329 if (!existed)
4331 gcc_assert
4332 (MR_DEPENDENCE_CLIQUE (op) <= cfun->last_clique);
4333 newc = ++cfun->last_clique;
4335 /* We cannot adjust MR_DEPENDENCE_CLIQUE in-place
4336 since MEM_EXPR is shared so make a copy and
4337 walk to the subtree again. */
4338 tree new_expr = unshare_expr (MEM_EXPR (*iter));
4339 if (TREE_CODE (new_expr) == WITH_SIZE_EXPR)
4340 new_expr = TREE_OPERAND (new_expr, 0);
4341 while (handled_component_p (new_expr))
4342 new_expr = TREE_OPERAND (new_expr, 0);
4343 MR_DEPENDENCE_CLIQUE (new_expr) = newc;
4344 set_mem_expr (const_cast <rtx> (*iter), new_expr);
4348 break;
4350 case JUMP_TABLE_DATA:
4351 /* Avoid copying of dispatch tables. We never duplicate
4352 tablejumps, so this can hit only in case the table got
4353 moved far from original jump.
4354 Avoid copying following barrier as well if any
4355 (and debug insns in between). */
4356 for (next = NEXT_INSN (insn);
4357 next != NEXT_INSN (to);
4358 next = NEXT_INSN (next))
4359 if (!DEBUG_INSN_P (next))
4360 break;
4361 if (next != NEXT_INSN (to) && BARRIER_P (next))
4362 insn = next;
4363 break;
4365 case CODE_LABEL:
4366 break;
4368 case BARRIER:
4369 emit_barrier ();
4370 break;
4372 case NOTE:
4373 switch (NOTE_KIND (insn))
4375 /* In case prologue is empty and function contain label
4376 in first BB, we may want to copy the block. */
4377 case NOTE_INSN_PROLOGUE_END:
4379 case NOTE_INSN_DELETED:
4380 case NOTE_INSN_DELETED_LABEL:
4381 case NOTE_INSN_DELETED_DEBUG_LABEL:
4382 /* No problem to strip these. */
4383 case NOTE_INSN_FUNCTION_BEG:
4384 /* There is always just single entry to function. */
4385 case NOTE_INSN_BASIC_BLOCK:
4386 /* We should only switch text sections once. */
4387 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4388 break;
4390 case NOTE_INSN_EPILOGUE_BEG:
4391 case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4392 emit_note_copy (as_a <rtx_note *> (insn));
4393 break;
4395 default:
4396 /* All other notes should have already been eliminated. */
4397 gcc_unreachable ();
4399 break;
4400 default:
4401 gcc_unreachable ();
4404 insn = NEXT_INSN (last);
4405 delete_insn (last);
4406 return insn;
4409 /* Create a duplicate of the basic block BB. */
4411 static basic_block
4412 cfg_layout_duplicate_bb (basic_block bb, copy_bb_data *id)
4414 rtx_insn *insn;
4415 basic_block new_bb;
4417 class loop *loop = (id && current_loops) ? bb->loop_father : NULL;
4419 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb), loop, id);
4420 new_bb = create_basic_block (insn,
4421 insn ? get_last_insn () : NULL,
4422 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4424 BB_COPY_PARTITION (new_bb, bb);
4425 if (BB_HEADER (bb))
4427 insn = BB_HEADER (bb);
4428 while (NEXT_INSN (insn))
4429 insn = NEXT_INSN (insn);
4430 insn = duplicate_insn_chain (BB_HEADER (bb), insn, loop, id);
4431 if (insn)
4432 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4435 if (BB_FOOTER (bb))
4437 insn = BB_FOOTER (bb);
4438 while (NEXT_INSN (insn))
4439 insn = NEXT_INSN (insn);
4440 insn = duplicate_insn_chain (BB_FOOTER (bb), insn, loop, id);
4441 if (insn)
4442 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4445 return new_bb;
4449 /* Main entry point to this module - initialize the datastructures for
4450 CFG layout changes. It keeps LOOPS up-to-date if not null.
4452 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4454 void
4455 cfg_layout_initialize (int flags)
4457 rtx_insn_list *x;
4458 basic_block bb;
4460 /* Once bb partitioning is complete, cfg layout mode should not be
4461 re-entered. Entering cfg layout mode may require fixups. As an
4462 example, if edge forwarding performed when optimizing the cfg
4463 layout required moving a block from the hot to the cold
4464 section. This would create an illegal partitioning unless some
4465 manual fixup was performed. */
4466 gcc_assert (!crtl->bb_reorder_complete || !crtl->has_bb_partition);
4468 initialize_original_copy_tables ();
4470 cfg_layout_rtl_register_cfg_hooks ();
4472 record_effective_endpoints ();
4474 /* Make sure that the targets of non local gotos are marked. */
4475 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4477 bb = BLOCK_FOR_INSN (x->insn ());
4478 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4481 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4484 /* Splits superblocks. */
4485 void
4486 break_superblocks (void)
4488 bool need = false;
4489 basic_block bb;
4491 auto_sbitmap superblocks (last_basic_block_for_fn (cfun));
4492 bitmap_clear (superblocks);
4494 FOR_EACH_BB_FN (bb, cfun)
4495 if (bb->flags & BB_SUPERBLOCK)
4497 bb->flags &= ~BB_SUPERBLOCK;
4498 bitmap_set_bit (superblocks, bb->index);
4499 need = true;
4502 if (need)
4504 rebuild_jump_labels (get_insns ());
4505 find_many_sub_basic_blocks (superblocks);
4509 /* Finalize the changes: reorder insn list according to the sequence specified
4510 by aux pointers, enter compensation code, rebuild scope forest. */
4512 void
4513 cfg_layout_finalize (void)
4515 free_dominance_info (CDI_DOMINATORS);
4516 force_one_exit_fallthru ();
4517 rtl_register_cfg_hooks ();
4518 if (reload_completed && !targetm.have_epilogue ())
4519 fixup_fallthru_exit_predecessor ();
4520 fixup_reorder_chain ();
4522 rebuild_jump_labels (get_insns ());
4523 delete_dead_jumptables ();
4525 if (flag_checking)
4526 verify_insn_chain ();
4527 checking_verify_flow_info ();
4531 /* Same as split_block but update cfg_layout structures. */
4533 static basic_block
4534 cfg_layout_split_block (basic_block bb, void *insnp)
4536 rtx insn = (rtx) insnp;
4537 basic_block new_bb = rtl_split_block (bb, insn);
4539 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4540 BB_FOOTER (bb) = NULL;
4542 return new_bb;
4545 /* Redirect Edge to DEST. */
4546 static edge
4547 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4549 basic_block src = e->src;
4550 edge ret;
4552 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4553 return NULL;
4555 if (e->dest == dest)
4556 return e;
4558 if (e->flags & EDGE_CROSSING
4559 && BB_PARTITION (e->src) == BB_PARTITION (dest)
4560 && simplejump_p (BB_END (src)))
4562 if (dump_file)
4563 fprintf (dump_file,
4564 "Removing crossing jump while redirecting edge form %i to %i\n",
4565 e->src->index, dest->index);
4566 delete_insn (BB_END (src));
4567 remove_barriers_from_footer (src);
4568 e->flags |= EDGE_FALLTHRU;
4571 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4572 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4574 df_set_bb_dirty (src);
4575 return ret;
4578 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4579 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4581 if (dump_file)
4582 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4583 e->src->index, dest->index);
4585 df_set_bb_dirty (e->src);
4586 redirect_edge_succ (e, dest);
4587 return e;
4590 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4591 in the case the basic block appears to be in sequence. Avoid this
4592 transformation. */
4594 if (e->flags & EDGE_FALLTHRU)
4596 /* Redirect any branch edges unified with the fallthru one. */
4597 if (JUMP_P (BB_END (src))
4598 && label_is_jump_target_p (BB_HEAD (e->dest),
4599 BB_END (src)))
4601 edge redirected;
4603 if (dump_file)
4604 fprintf (dump_file, "Fallthru edge unified with branch "
4605 "%i->%i redirected to %i\n",
4606 e->src->index, e->dest->index, dest->index);
4607 e->flags &= ~EDGE_FALLTHRU;
4608 redirected = redirect_branch_edge (e, dest);
4609 gcc_assert (redirected);
4610 redirected->flags |= EDGE_FALLTHRU;
4611 df_set_bb_dirty (redirected->src);
4612 return redirected;
4614 /* In case we are redirecting fallthru edge to the branch edge
4615 of conditional jump, remove it. */
4616 if (EDGE_COUNT (src->succs) == 2)
4618 /* Find the edge that is different from E. */
4619 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4621 if (s->dest == dest
4622 && any_condjump_p (BB_END (src))
4623 && onlyjump_p (BB_END (src)))
4624 delete_insn (BB_END (src));
4626 if (dump_file)
4627 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4628 e->src->index, e->dest->index, dest->index);
4629 ret = redirect_edge_succ_nodup (e, dest);
4631 else
4632 ret = redirect_branch_edge (e, dest);
4634 if (!ret)
4635 return NULL;
4637 fixup_partition_crossing (ret);
4638 /* We don't want simplejumps in the insn stream during cfglayout. */
4639 gcc_assert (!simplejump_p (BB_END (src)) || CROSSING_JUMP_P (BB_END (src)));
4641 df_set_bb_dirty (src);
4642 return ret;
4645 /* Simple wrapper as we always can redirect fallthru edges. */
4646 static basic_block
4647 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4649 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4651 gcc_assert (redirected);
4652 return NULL;
4655 /* Same as delete_basic_block but update cfg_layout structures. */
4657 static void
4658 cfg_layout_delete_block (basic_block bb)
4660 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4661 rtx_insn **to;
4663 if (BB_HEADER (bb))
4665 next = BB_HEAD (bb);
4666 if (prev)
4667 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4668 else
4669 set_first_insn (BB_HEADER (bb));
4670 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4671 insn = BB_HEADER (bb);
4672 while (NEXT_INSN (insn))
4673 insn = NEXT_INSN (insn);
4674 SET_NEXT_INSN (insn) = next;
4675 SET_PREV_INSN (next) = insn;
4677 next = NEXT_INSN (BB_END (bb));
4678 if (BB_FOOTER (bb))
4680 insn = BB_FOOTER (bb);
4681 while (insn)
4683 if (BARRIER_P (insn))
4685 if (PREV_INSN (insn))
4686 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4687 else
4688 BB_FOOTER (bb) = NEXT_INSN (insn);
4689 if (NEXT_INSN (insn))
4690 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4692 if (LABEL_P (insn))
4693 break;
4694 insn = NEXT_INSN (insn);
4696 if (BB_FOOTER (bb))
4698 insn = BB_END (bb);
4699 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4700 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4701 while (NEXT_INSN (insn))
4702 insn = NEXT_INSN (insn);
4703 SET_NEXT_INSN (insn) = next;
4704 if (next)
4705 SET_PREV_INSN (next) = insn;
4706 else
4707 set_last_insn (insn);
4710 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4711 to = &BB_HEADER (bb->next_bb);
4712 else
4713 to = &cfg_layout_function_footer;
4715 rtl_delete_block (bb);
4717 if (prev)
4718 prev = NEXT_INSN (prev);
4719 else
4720 prev = get_insns ();
4721 if (next)
4722 next = PREV_INSN (next);
4723 else
4724 next = get_last_insn ();
4726 if (next && NEXT_INSN (next) != prev)
4728 remaints = unlink_insn_chain (prev, next);
4729 insn = remaints;
4730 while (NEXT_INSN (insn))
4731 insn = NEXT_INSN (insn);
4732 SET_NEXT_INSN (insn) = *to;
4733 if (*to)
4734 SET_PREV_INSN (*to) = insn;
4735 *to = remaints;
4739 /* Return true when blocks A and B can be safely merged. */
4741 static bool
4742 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4744 /* If we are partitioning hot/cold basic blocks, we don't want to
4745 mess up unconditional or indirect jumps that cross between hot
4746 and cold sections.
4748 Basic block partitioning may result in some jumps that appear to
4749 be optimizable (or blocks that appear to be mergeable), but which really
4750 must be left untouched (they are required to make it safely across
4751 partition boundaries). See the comments at the top of
4752 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4754 if (BB_PARTITION (a) != BB_PARTITION (b))
4755 return false;
4757 /* Protect the loop latches. */
4758 if (current_loops && b->loop_father->latch == b)
4759 return false;
4761 /* If we would end up moving B's instructions, make sure it doesn't fall
4762 through into the exit block, since we cannot recover from a fallthrough
4763 edge into the exit block occurring in the middle of a function. */
4764 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4766 edge e = find_fallthru_edge (b->succs);
4767 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4768 return false;
4771 /* There must be exactly one edge in between the blocks. */
4772 return (single_succ_p (a)
4773 && single_succ (a) == b
4774 && single_pred_p (b) == 1
4775 && a != b
4776 /* Must be simple edge. */
4777 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4778 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4779 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4780 /* If the jump insn has side effects, we can't kill the edge.
4781 When not optimizing, try_redirect_by_replacing_jump will
4782 not allow us to redirect an edge by replacing a table jump. */
4783 && (!JUMP_P (BB_END (a))
4784 || ((!optimize || reload_completed)
4785 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4788 /* Merge block A and B. The blocks must be mergeable. */
4790 static void
4791 cfg_layout_merge_blocks (basic_block a, basic_block b)
4793 /* If B is a forwarder block whose outgoing edge has no location, we'll
4794 propagate the locus of the edge between A and B onto it. */
4795 const bool forward_edge_locus
4796 = (b->flags & BB_FORWARDER_BLOCK) != 0
4797 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
4798 rtx_insn *insn;
4800 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4802 if (dump_file)
4803 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4804 a->index);
4806 /* If there was a CODE_LABEL beginning B, delete it. */
4807 if (LABEL_P (BB_HEAD (b)))
4809 delete_insn (BB_HEAD (b));
4812 /* We should have fallthru edge in a, or we can do dummy redirection to get
4813 it cleaned up. */
4814 if (JUMP_P (BB_END (a)))
4815 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4816 gcc_assert (!JUMP_P (BB_END (a)));
4818 /* If not optimizing, preserve the locus of the single edge between
4819 blocks A and B if necessary by emitting a nop. */
4820 if (!optimize
4821 && !forward_edge_locus
4822 && !DECL_IGNORED_P (current_function_decl))
4823 emit_nop_for_unique_locus_between (a, b);
4825 /* Move things from b->footer after a->footer. */
4826 if (BB_FOOTER (b))
4828 if (!BB_FOOTER (a))
4829 BB_FOOTER (a) = BB_FOOTER (b);
4830 else
4832 rtx_insn *last = BB_FOOTER (a);
4834 while (NEXT_INSN (last))
4835 last = NEXT_INSN (last);
4836 SET_NEXT_INSN (last) = BB_FOOTER (b);
4837 SET_PREV_INSN (BB_FOOTER (b)) = last;
4839 BB_FOOTER (b) = NULL;
4842 /* Move things from b->header before a->footer.
4843 Note that this may include dead tablejump data, but we don't clean
4844 those up until we go out of cfglayout mode. */
4845 if (BB_HEADER (b))
4847 if (! BB_FOOTER (a))
4848 BB_FOOTER (a) = BB_HEADER (b);
4849 else
4851 rtx_insn *last = BB_HEADER (b);
4853 while (NEXT_INSN (last))
4854 last = NEXT_INSN (last);
4855 SET_NEXT_INSN (last) = BB_FOOTER (a);
4856 SET_PREV_INSN (BB_FOOTER (a)) = last;
4857 BB_FOOTER (a) = BB_HEADER (b);
4859 BB_HEADER (b) = NULL;
4862 /* In the case basic blocks are not adjacent, move them around. */
4863 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4865 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4867 emit_insn_after_noloc (insn, BB_END (a), a);
4869 /* Otherwise just re-associate the instructions. */
4870 else
4872 insn = BB_HEAD (b);
4873 BB_END (a) = BB_END (b);
4876 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4877 We need to explicitly call. */
4878 update_bb_for_insn_chain (insn, BB_END (b), a);
4880 /* Skip possible DELETED_LABEL insn. */
4881 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4882 insn = NEXT_INSN (insn);
4883 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4884 BB_HEAD (b) = BB_END (b) = NULL;
4885 delete_insn (insn);
4887 df_bb_delete (b->index);
4889 if (forward_edge_locus)
4890 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4892 if (dump_file)
4893 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4896 /* Split edge E. */
4898 static basic_block
4899 cfg_layout_split_edge (edge e)
4901 basic_block new_bb =
4902 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4903 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4904 NULL_RTX, e->src);
4906 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4907 BB_COPY_PARTITION (new_bb, e->src);
4908 else
4909 BB_COPY_PARTITION (new_bb, e->dest);
4910 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4911 redirect_edge_and_branch_force (e, new_bb);
4913 return new_bb;
4916 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4918 static void
4919 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4923 /* Return true if BB contains only labels or non-executable
4924 instructions. */
4926 static bool
4927 rtl_block_empty_p (basic_block bb)
4929 rtx_insn *insn;
4931 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4932 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4933 return true;
4935 FOR_BB_INSNS (bb, insn)
4936 if (NONDEBUG_INSN_P (insn)
4937 && (!any_uncondjump_p (insn) || !onlyjump_p (insn)))
4938 return false;
4940 return true;
4943 /* Split a basic block if it ends with a conditional branch and if
4944 the other part of the block is not empty. */
4946 static basic_block
4947 rtl_split_block_before_cond_jump (basic_block bb)
4949 rtx_insn *insn;
4950 rtx_insn *split_point = NULL;
4951 rtx_insn *last = NULL;
4952 bool found_code = false;
4954 FOR_BB_INSNS (bb, insn)
4956 if (any_condjump_p (insn))
4957 split_point = last;
4958 else if (NONDEBUG_INSN_P (insn))
4959 found_code = true;
4960 last = insn;
4963 /* Did not find everything. */
4964 if (found_code && split_point)
4965 return split_block (bb, split_point)->dest;
4966 else
4967 return NULL;
4970 /* Return 1 if BB ends with a call, possibly followed by some
4971 instructions that must stay with the call, 0 otherwise. */
4973 static bool
4974 rtl_block_ends_with_call_p (basic_block bb)
4976 rtx_insn *insn = BB_END (bb);
4978 while (!CALL_P (insn)
4979 && insn != BB_HEAD (bb)
4980 && (keep_with_call_p (insn)
4981 || NOTE_P (insn)
4982 || DEBUG_INSN_P (insn)))
4983 insn = PREV_INSN (insn);
4984 return (CALL_P (insn));
4987 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4989 static bool
4990 rtl_block_ends_with_condjump_p (const_basic_block bb)
4992 return any_condjump_p (BB_END (bb));
4995 /* Return true if we need to add fake edge to exit.
4996 Helper function for rtl_flow_call_edges_add. */
4998 static bool
4999 need_fake_edge_p (const rtx_insn *insn)
5001 if (!INSN_P (insn))
5002 return false;
5004 if ((CALL_P (insn)
5005 && !SIBLING_CALL_P (insn)
5006 && !find_reg_note (insn, REG_NORETURN, NULL)
5007 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
5008 return true;
5010 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5011 && MEM_VOLATILE_P (PATTERN (insn)))
5012 || (GET_CODE (PATTERN (insn)) == PARALLEL
5013 && asm_noperands (insn) != -1
5014 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
5015 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
5018 /* Add fake edges to the function exit for any non constant and non noreturn
5019 calls, volatile inline assembly in the bitmap of blocks specified by
5020 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
5021 that were split.
5023 The goal is to expose cases in which entering a basic block does not imply
5024 that all subsequent instructions must be executed. */
5026 static int
5027 rtl_flow_call_edges_add (sbitmap blocks)
5029 int i;
5030 int blocks_split = 0;
5031 int last_bb = last_basic_block_for_fn (cfun);
5032 bool check_last_block = false;
5034 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
5035 return 0;
5037 if (! blocks)
5038 check_last_block = true;
5039 else
5040 check_last_block = bitmap_bit_p (blocks,
5041 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
5043 /* In the last basic block, before epilogue generation, there will be
5044 a fallthru edge to EXIT. Special care is required if the last insn
5045 of the last basic block is a call because make_edge folds duplicate
5046 edges, which would result in the fallthru edge also being marked
5047 fake, which would result in the fallthru edge being removed by
5048 remove_fake_edges, which would result in an invalid CFG.
5050 Moreover, we can't elide the outgoing fake edge, since the block
5051 profiler needs to take this into account in order to solve the minimal
5052 spanning tree in the case that the call doesn't return.
5054 Handle this by adding a dummy instruction in a new last basic block. */
5055 if (check_last_block)
5057 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
5058 rtx_insn *insn = BB_END (bb);
5060 /* Back up past insns that must be kept in the same block as a call. */
5061 while (insn != BB_HEAD (bb)
5062 && keep_with_call_p (insn))
5063 insn = PREV_INSN (insn);
5065 if (need_fake_edge_p (insn))
5067 edge e;
5069 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5070 if (e)
5072 insert_insn_on_edge (gen_use (const0_rtx), e);
5073 commit_edge_insertions ();
5078 /* Now add fake edges to the function exit for any non constant
5079 calls since there is no way that we can determine if they will
5080 return or not... */
5082 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
5084 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
5085 rtx_insn *insn;
5086 rtx_insn *prev_insn;
5088 if (!bb)
5089 continue;
5091 if (blocks && !bitmap_bit_p (blocks, i))
5092 continue;
5094 for (insn = BB_END (bb); ; insn = prev_insn)
5096 prev_insn = PREV_INSN (insn);
5097 if (need_fake_edge_p (insn))
5099 edge e;
5100 rtx_insn *split_at_insn = insn;
5102 /* Don't split the block between a call and an insn that should
5103 remain in the same block as the call. */
5104 if (CALL_P (insn))
5105 while (split_at_insn != BB_END (bb)
5106 && keep_with_call_p (NEXT_INSN (split_at_insn)))
5107 split_at_insn = NEXT_INSN (split_at_insn);
5109 /* The handling above of the final block before the epilogue
5110 should be enough to verify that there is no edge to the exit
5111 block in CFG already. Calling make_edge in such case would
5112 cause us to mark that edge as fake and remove it later. */
5114 if (flag_checking && split_at_insn == BB_END (bb))
5116 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5117 gcc_assert (e == NULL);
5120 /* Note that the following may create a new basic block
5121 and renumber the existing basic blocks. */
5122 if (split_at_insn != BB_END (bb))
5124 e = split_block (bb, split_at_insn);
5125 if (e)
5126 blocks_split++;
5129 edge ne = make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
5130 ne->probability = profile_probability::guessed_never ();
5133 if (insn == BB_HEAD (bb))
5134 break;
5138 if (blocks_split)
5139 verify_flow_info ();
5141 return blocks_split;
5144 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
5145 the conditional branch target, SECOND_HEAD should be the fall-thru
5146 there is no need to handle this here the loop versioning code handles
5147 this. the reason for SECON_HEAD is that it is needed for condition
5148 in trees, and this should be of the same type since it is a hook. */
5149 static void
5150 rtl_lv_add_condition_to_bb (basic_block first_head ,
5151 basic_block second_head ATTRIBUTE_UNUSED,
5152 basic_block cond_bb, void *comp_rtx)
5154 rtx_code_label *label;
5155 rtx_insn *seq, *jump;
5156 rtx op0 = XEXP ((rtx)comp_rtx, 0);
5157 rtx op1 = XEXP ((rtx)comp_rtx, 1);
5158 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
5159 machine_mode mode;
5162 label = block_label (first_head);
5163 mode = GET_MODE (op0);
5164 if (mode == VOIDmode)
5165 mode = GET_MODE (op1);
5167 start_sequence ();
5168 op0 = force_operand (op0, NULL_RTX);
5169 op1 = force_operand (op1, NULL_RTX);
5170 do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label,
5171 profile_probability::uninitialized ());
5172 jump = get_last_insn ();
5173 JUMP_LABEL (jump) = label;
5174 LABEL_NUSES (label)++;
5175 seq = get_insns ();
5176 end_sequence ();
5178 /* Add the new cond, in the new head. */
5179 emit_insn_after (seq, BB_END (cond_bb));
5183 /* Given a block B with unconditional branch at its end, get the
5184 store the return the branch edge and the fall-thru edge in
5185 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
5186 static void
5187 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
5188 edge *fallthru_edge)
5190 edge e = EDGE_SUCC (b, 0);
5192 if (e->flags & EDGE_FALLTHRU)
5194 *fallthru_edge = e;
5195 *branch_edge = EDGE_SUCC (b, 1);
5197 else
5199 *branch_edge = e;
5200 *fallthru_edge = EDGE_SUCC (b, 1);
5204 void
5205 init_rtl_bb_info (basic_block bb)
5207 gcc_assert (!bb->il.x.rtl);
5208 bb->il.x.head_ = NULL;
5209 bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
5212 static bool
5213 rtl_bb_info_initialized_p (basic_block bb)
5215 return bb->il.x.rtl;
5218 /* Returns true if it is possible to remove edge E by redirecting
5219 it to the destination of the other edge from E->src. */
5221 static bool
5222 rtl_can_remove_branch_p (const_edge e)
5224 const_basic_block src = e->src;
5225 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
5226 const rtx_insn *insn = BB_END (src);
5227 rtx set;
5229 /* The conditions are taken from try_redirect_by_replacing_jump. */
5230 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
5231 return false;
5233 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
5234 return false;
5236 if (BB_PARTITION (src) != BB_PARTITION (target))
5237 return false;
5239 if (!onlyjump_p (insn)
5240 || tablejump_p (insn, NULL, NULL))
5241 return false;
5243 set = single_set (insn);
5244 if (!set || side_effects_p (set))
5245 return false;
5247 return true;
5250 static basic_block
5251 rtl_duplicate_bb (basic_block bb, copy_bb_data *id)
5253 bb = cfg_layout_duplicate_bb (bb, id);
5254 bb->aux = NULL;
5255 return bb;
5258 /* Do book-keeping of basic block BB for the profile consistency checker.
5259 Store the counting in RECORD. */
5260 static void
5261 rtl_account_profile_record (basic_block bb, struct profile_record *record)
5263 rtx_insn *insn;
5264 FOR_BB_INSNS (bb, insn)
5265 if (INSN_P (insn))
5267 record->size += insn_cost (insn, false);
5268 if (bb->count.initialized_p ())
5269 record->time
5270 += insn_cost (insn, true) * bb->count.to_gcov_type ();
5271 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
5272 record->time
5273 += insn_cost (insn, true) * bb->count.to_frequency (cfun);
5277 /* Implementation of CFG manipulation for linearized RTL. */
5278 struct cfg_hooks rtl_cfg_hooks = {
5279 "rtl",
5280 rtl_verify_flow_info,
5281 rtl_dump_bb,
5282 rtl_dump_bb_for_graph,
5283 rtl_create_basic_block,
5284 rtl_redirect_edge_and_branch,
5285 rtl_redirect_edge_and_branch_force,
5286 rtl_can_remove_branch_p,
5287 rtl_delete_block,
5288 rtl_split_block,
5289 rtl_move_block_after,
5290 rtl_can_merge_blocks, /* can_merge_blocks_p */
5291 rtl_merge_blocks,
5292 rtl_predict_edge,
5293 rtl_predicted_by_p,
5294 cfg_layout_can_duplicate_bb_p,
5295 rtl_duplicate_bb,
5296 rtl_split_edge,
5297 rtl_make_forwarder_block,
5298 rtl_tidy_fallthru_edge,
5299 rtl_force_nonfallthru,
5300 rtl_block_ends_with_call_p,
5301 rtl_block_ends_with_condjump_p,
5302 rtl_flow_call_edges_add,
5303 NULL, /* execute_on_growing_pred */
5304 NULL, /* execute_on_shrinking_pred */
5305 NULL, /* duplicate loop for trees */
5306 NULL, /* lv_add_condition_to_bb */
5307 NULL, /* lv_adjust_loop_header_phi*/
5308 NULL, /* extract_cond_bb_edges */
5309 NULL, /* flush_pending_stmts */
5310 rtl_block_empty_p, /* block_empty_p */
5311 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5312 rtl_account_profile_record,
5315 /* Implementation of CFG manipulation for cfg layout RTL, where
5316 basic block connected via fallthru edges does not have to be adjacent.
5317 This representation will hopefully become the default one in future
5318 version of the compiler. */
5320 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5321 "cfglayout mode",
5322 rtl_verify_flow_info_1,
5323 rtl_dump_bb,
5324 rtl_dump_bb_for_graph,
5325 cfg_layout_create_basic_block,
5326 cfg_layout_redirect_edge_and_branch,
5327 cfg_layout_redirect_edge_and_branch_force,
5328 rtl_can_remove_branch_p,
5329 cfg_layout_delete_block,
5330 cfg_layout_split_block,
5331 rtl_move_block_after,
5332 cfg_layout_can_merge_blocks_p,
5333 cfg_layout_merge_blocks,
5334 rtl_predict_edge,
5335 rtl_predicted_by_p,
5336 cfg_layout_can_duplicate_bb_p,
5337 cfg_layout_duplicate_bb,
5338 cfg_layout_split_edge,
5339 rtl_make_forwarder_block,
5340 NULL, /* tidy_fallthru_edge */
5341 rtl_force_nonfallthru,
5342 rtl_block_ends_with_call_p,
5343 rtl_block_ends_with_condjump_p,
5344 rtl_flow_call_edges_add,
5345 NULL, /* execute_on_growing_pred */
5346 NULL, /* execute_on_shrinking_pred */
5347 duplicate_loop_body_to_header_edge, /* duplicate loop for trees */
5348 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5349 NULL, /* lv_adjust_loop_header_phi*/
5350 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5351 NULL, /* flush_pending_stmts */
5352 rtl_block_empty_p, /* block_empty_p */
5353 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5354 rtl_account_profile_record,
5357 #include "gt-cfgrtl.h"
5359 #if __GNUC__ >= 10
5360 # pragma GCC diagnostic pop
5361 #endif