c, c++: attribute format on a ctor with a vbase [PR101833, PR47634]
[official-gcc.git] / gcc / cfgrtl.cc
blob74ea14efc61539495449c1ddb499d804ca8cb763
1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2022 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"
66 #include "profile.h"
67 #include "sreal.h"
69 /* Disable warnings about missing quoting in GCC diagnostics. */
70 #if __GNUC__ >= 10
71 # pragma GCC diagnostic push
72 # pragma GCC diagnostic ignored "-Wformat-diag"
73 #endif
75 /* Holds the interesting leading and trailing notes for the function.
76 Only applicable if the CFG is in cfglayout mode. */
77 static GTY(()) rtx_insn *cfg_layout_function_footer;
78 static GTY(()) rtx_insn *cfg_layout_function_header;
80 static rtx_insn *skip_insns_after_block (basic_block);
81 static void record_effective_endpoints (void);
82 static void fixup_reorder_chain (void);
84 void verify_insn_chain (void);
85 static void fixup_fallthru_exit_predecessor (void);
86 static int can_delete_note_p (const rtx_note *);
87 static int can_delete_label_p (const rtx_code_label *);
88 static basic_block rtl_split_edge (edge);
89 static bool rtl_move_block_after (basic_block, basic_block);
90 static int rtl_verify_flow_info (void);
91 static basic_block cfg_layout_split_block (basic_block, void *);
92 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
93 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
94 static void cfg_layout_delete_block (basic_block);
95 static void rtl_delete_block (basic_block);
96 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
97 static edge rtl_redirect_edge_and_branch (edge, basic_block);
98 static basic_block rtl_split_block (basic_block, void *);
99 static void rtl_dump_bb (FILE *, basic_block, int, dump_flags_t);
100 static int rtl_verify_flow_info_1 (void);
101 static void rtl_make_forwarder_block (edge);
102 static bool rtl_bb_info_initialized_p (basic_block bb);
104 /* Return true if NOTE is not one of the ones that must be kept paired,
105 so that we may simply delete it. */
107 static int
108 can_delete_note_p (const rtx_note *note)
110 switch (NOTE_KIND (note))
112 case NOTE_INSN_DELETED:
113 case NOTE_INSN_BASIC_BLOCK:
114 case NOTE_INSN_EPILOGUE_BEG:
115 return true;
117 default:
118 return false;
122 /* True if a given label can be deleted. */
124 static int
125 can_delete_label_p (const rtx_code_label *label)
127 return (!LABEL_PRESERVE_P (label)
128 /* User declared labels must be preserved. */
129 && LABEL_NAME (label) == 0
130 && !vec_safe_contains<rtx_insn *> (forced_labels,
131 const_cast<rtx_code_label *> (label)));
134 /* Delete INSN by patching it out. */
136 void
137 delete_insn (rtx_insn *insn)
139 rtx note;
140 bool really_delete = true;
142 if (LABEL_P (insn))
144 /* Some labels can't be directly removed from the INSN chain, as they
145 might be references via variables, constant pool etc.
146 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
147 if (! can_delete_label_p (as_a <rtx_code_label *> (insn)))
149 const char *name = LABEL_NAME (insn);
150 basic_block bb = BLOCK_FOR_INSN (insn);
151 rtx_insn *bb_note = NEXT_INSN (insn);
153 really_delete = false;
154 PUT_CODE (insn, NOTE);
155 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
156 NOTE_DELETED_LABEL_NAME (insn) = name;
158 /* If the note following the label starts a basic block, and the
159 label is a member of the same basic block, interchange the two. */
160 if (bb_note != NULL_RTX
161 && NOTE_INSN_BASIC_BLOCK_P (bb_note)
162 && bb != NULL
163 && bb == BLOCK_FOR_INSN (bb_note))
165 reorder_insns_nobb (insn, insn, bb_note);
166 BB_HEAD (bb) = bb_note;
167 if (BB_END (bb) == bb_note)
168 BB_END (bb) = insn;
172 remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels);
175 if (really_delete)
177 /* If this insn has already been deleted, something is very wrong. */
178 gcc_assert (!insn->deleted ());
179 if (INSN_P (insn))
180 df_insn_delete (insn);
181 remove_insn (insn);
182 insn->set_deleted ();
185 /* If deleting a jump, decrement the use count of the label. Deleting
186 the label itself should happen in the normal course of block merging. */
187 if (JUMP_P (insn))
189 if (JUMP_LABEL (insn)
190 && LABEL_P (JUMP_LABEL (insn)))
191 LABEL_NUSES (JUMP_LABEL (insn))--;
193 /* If there are more targets, remove them too. */
194 while ((note
195 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
196 && LABEL_P (XEXP (note, 0)))
198 LABEL_NUSES (XEXP (note, 0))--;
199 remove_note (insn, note);
203 /* Also if deleting any insn that references a label as an operand. */
204 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
205 && LABEL_P (XEXP (note, 0)))
207 LABEL_NUSES (XEXP (note, 0))--;
208 remove_note (insn, note);
211 if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
213 rtvec vec = table->get_labels ();
214 int len = GET_NUM_ELEM (vec);
215 int i;
217 for (i = 0; i < len; i++)
219 rtx label = XEXP (RTVEC_ELT (vec, i), 0);
221 /* When deleting code in bulk (e.g. removing many unreachable
222 blocks) we can delete a label that's a target of the vector
223 before deleting the vector itself. */
224 if (!NOTE_P (label))
225 LABEL_NUSES (label)--;
230 /* Like delete_insn but also purge dead edges from BB.
231 Return true if any edges are eliminated. */
233 bool
234 delete_insn_and_edges (rtx_insn *insn)
236 bool purge = false;
238 if (INSN_P (insn) && BLOCK_FOR_INSN (insn))
240 basic_block bb = BLOCK_FOR_INSN (insn);
241 if (BB_END (bb) == insn)
242 purge = true;
243 else if (DEBUG_INSN_P (BB_END (bb)))
244 for (rtx_insn *dinsn = NEXT_INSN (insn);
245 DEBUG_INSN_P (dinsn); dinsn = NEXT_INSN (dinsn))
246 if (BB_END (bb) == dinsn)
248 purge = true;
249 break;
252 delete_insn (insn);
253 if (purge)
254 return purge_dead_edges (BLOCK_FOR_INSN (insn));
255 return false;
258 /* Unlink a chain of insns between START and FINISH, leaving notes
259 that must be paired. If CLEAR_BB is true, we set bb field for
260 insns that cannot be removed to NULL. */
262 void
263 delete_insn_chain (rtx start, rtx_insn *finish, bool clear_bb)
265 /* Unchain the insns one by one. It would be quicker to delete all of these
266 with a single unchaining, rather than one at a time, but we need to keep
267 the NOTE's. */
268 rtx_insn *current = finish;
269 while (1)
271 rtx_insn *prev = PREV_INSN (current);
272 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
274 else
275 delete_insn (current);
277 if (clear_bb && !current->deleted ())
278 set_block_for_insn (current, NULL);
280 if (current == start)
281 break;
282 current = prev;
286 /* Create a new basic block consisting of the instructions between HEAD and END
287 inclusive. This function is designed to allow fast BB construction - reuses
288 the note and basic block struct in BB_NOTE, if any and do not grow
289 BASIC_BLOCK chain and should be used directly only by CFG construction code.
290 END can be NULL in to create new empty basic block before HEAD. Both END
291 and HEAD can be NULL to create basic block at the end of INSN chain.
292 AFTER is the basic block we should be put after. */
294 basic_block
295 create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
296 basic_block after)
298 basic_block bb;
300 if (bb_note
301 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
302 && bb->aux == NULL)
304 /* If we found an existing note, thread it back onto the chain. */
306 rtx_insn *after;
308 if (LABEL_P (head))
309 after = head;
310 else
312 after = PREV_INSN (head);
313 head = bb_note;
316 if (after != bb_note && NEXT_INSN (after) != bb_note)
317 reorder_insns_nobb (bb_note, bb_note, after);
319 else
321 /* Otherwise we must create a note and a basic block structure. */
323 bb = alloc_block ();
325 init_rtl_bb_info (bb);
326 if (!head && !end)
327 head = end = bb_note
328 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
329 else if (LABEL_P (head) && end)
331 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
332 if (head == end)
333 end = bb_note;
335 else
337 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
338 head = bb_note;
339 if (!end)
340 end = head;
343 NOTE_BASIC_BLOCK (bb_note) = bb;
346 /* Always include the bb note in the block. */
347 if (NEXT_INSN (end) == bb_note)
348 end = bb_note;
350 BB_HEAD (bb) = head;
351 BB_END (bb) = end;
352 bb->index = last_basic_block_for_fn (cfun)++;
353 bb->flags = BB_NEW | BB_RTL;
354 link_block (bb, after);
355 SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
356 df_bb_refs_record (bb->index, false);
357 update_bb_for_insn (bb);
358 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
360 /* Tag the block so that we know it has been used when considering
361 other basic block notes. */
362 bb->aux = bb;
364 return bb;
367 /* Create new basic block consisting of instructions in between HEAD and END
368 and place it to the BB chain after block AFTER. END can be NULL to
369 create a new empty basic block before HEAD. Both END and HEAD can be
370 NULL to create basic block at the end of INSN chain. */
372 static basic_block
373 rtl_create_basic_block (void *headp, void *endp, basic_block after)
375 rtx_insn *head = (rtx_insn *) headp;
376 rtx_insn *end = (rtx_insn *) endp;
377 basic_block bb;
379 /* Grow the basic block array if needed. */
380 if ((size_t) last_basic_block_for_fn (cfun)
381 >= basic_block_info_for_fn (cfun)->length ())
382 vec_safe_grow_cleared (basic_block_info_for_fn (cfun),
383 last_basic_block_for_fn (cfun) + 1);
385 n_basic_blocks_for_fn (cfun)++;
387 bb = create_basic_block_structure (head, end, NULL, after);
388 bb->aux = NULL;
389 return bb;
392 static basic_block
393 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
395 basic_block newbb = rtl_create_basic_block (head, end, after);
397 return newbb;
400 /* Delete the insns in a (non-live) block. We physically delete every
401 non-deleted-note insn, and update the flow graph appropriately.
403 Return nonzero if we deleted an exception handler. */
405 /* ??? Preserving all such notes strikes me as wrong. It would be nice
406 to post-process the stream to remove empty blocks, loops, ranges, etc. */
408 static void
409 rtl_delete_block (basic_block b)
411 rtx_insn *insn, *end;
413 /* If the head of this block is a CODE_LABEL, then it might be the
414 label for an exception handler which can't be reached. We need
415 to remove the label from the exception_handler_label list. */
416 insn = BB_HEAD (b);
418 end = get_last_bb_insn (b);
420 /* Selectively delete the entire chain. */
421 BB_HEAD (b) = NULL;
422 delete_insn_chain (insn, end, true);
425 if (dump_file)
426 fprintf (dump_file, "deleting block %d\n", b->index);
427 df_bb_delete (b->index);
430 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
432 void
433 compute_bb_for_insn (void)
435 basic_block bb;
437 FOR_EACH_BB_FN (bb, cfun)
439 rtx_insn *end = BB_END (bb);
440 rtx_insn *insn;
442 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
444 BLOCK_FOR_INSN (insn) = bb;
445 if (insn == end)
446 break;
451 /* Release the basic_block_for_insn array. */
453 unsigned int
454 free_bb_for_insn (void)
456 rtx_insn *insn;
457 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
458 if (!BARRIER_P (insn))
459 BLOCK_FOR_INSN (insn) = NULL;
460 return 0;
463 namespace {
465 const pass_data pass_data_free_cfg =
467 RTL_PASS, /* type */
468 "*free_cfg", /* name */
469 OPTGROUP_NONE, /* optinfo_flags */
470 TV_NONE, /* tv_id */
471 0, /* properties_required */
472 0, /* properties_provided */
473 PROP_cfg, /* properties_destroyed */
474 0, /* todo_flags_start */
475 0, /* todo_flags_finish */
478 class pass_free_cfg : public rtl_opt_pass
480 public:
481 pass_free_cfg (gcc::context *ctxt)
482 : rtl_opt_pass (pass_data_free_cfg, ctxt)
485 /* opt_pass methods: */
486 virtual unsigned int execute (function *);
488 }; // class pass_free_cfg
490 unsigned int
491 pass_free_cfg::execute (function *)
493 /* The resource.cc machinery uses DF but the CFG isn't guaranteed to be
494 valid at that point so it would be too late to call df_analyze. */
495 if (DELAY_SLOTS && optimize > 0 && flag_delayed_branch)
497 df_note_add_problem ();
498 df_analyze ();
501 if (crtl->has_bb_partition)
502 insert_section_boundary_note ();
504 free_bb_for_insn ();
505 return 0;
508 } // anon namespace
510 rtl_opt_pass *
511 make_pass_free_cfg (gcc::context *ctxt)
513 return new pass_free_cfg (ctxt);
516 /* Return RTX to emit after when we want to emit code on the entry of function. */
517 rtx_insn *
518 entry_of_function (void)
520 return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
521 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
524 /* Emit INSN at the entry point of the function, ensuring that it is only
525 executed once per function. */
526 void
527 emit_insn_at_entry (rtx insn)
529 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
530 edge e = ei_safe_edge (ei);
531 gcc_assert (e->flags & EDGE_FALLTHRU);
533 insert_insn_on_edge (insn, e);
534 commit_edge_insertions ();
537 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
538 (or BARRIER if found) and notify df of the bb change.
539 The insn chain range is inclusive
540 (i.e. both BEGIN and END will be updated. */
542 static void
543 update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
545 rtx_insn *insn;
547 end = NEXT_INSN (end);
548 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
549 if (!BARRIER_P (insn))
550 df_insn_change_bb (insn, bb);
553 /* Update BLOCK_FOR_INSN of insns in BB to BB,
554 and notify df of the change. */
556 void
557 update_bb_for_insn (basic_block bb)
559 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
563 /* Like active_insn_p, except keep the return value use or clobber around
564 even after reload. */
566 static bool
567 flow_active_insn_p (const rtx_insn *insn)
569 if (active_insn_p (insn))
570 return true;
572 /* A clobber of the function return value exists for buggy
573 programs that fail to return a value. Its effect is to
574 keep the return value from being live across the entire
575 function. If we allow it to be skipped, we introduce the
576 possibility for register lifetime confusion.
577 Similarly, keep a USE of the function return value, otherwise
578 the USE is dropped and we could fail to thread jump if USE
579 appears on some paths and not on others, see PR90257. */
580 if ((GET_CODE (PATTERN (insn)) == CLOBBER
581 || GET_CODE (PATTERN (insn)) == USE)
582 && REG_P (XEXP (PATTERN (insn), 0))
583 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
584 return true;
586 return false;
589 /* Return true if the block has no effect and only forwards control flow to
590 its single destination. */
592 bool
593 contains_no_active_insn_p (const_basic_block bb)
595 rtx_insn *insn;
597 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
598 || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
599 || !single_succ_p (bb)
600 || (single_succ_edge (bb)->flags & EDGE_FAKE) != 0)
601 return false;
603 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
604 if (INSN_P (insn) && flow_active_insn_p (insn))
605 return false;
607 return (!INSN_P (insn)
608 || (JUMP_P (insn) && simplejump_p (insn))
609 || !flow_active_insn_p (insn));
612 /* Likewise, but protect loop latches, headers and preheaders. */
613 /* FIXME: Make this a cfg hook. */
615 bool
616 forwarder_block_p (const_basic_block bb)
618 if (!contains_no_active_insn_p (bb))
619 return false;
621 /* Protect loop latches, headers and preheaders. */
622 if (current_loops)
624 basic_block dest;
625 if (bb->loop_father->header == bb)
626 return false;
627 dest = EDGE_SUCC (bb, 0)->dest;
628 if (dest->loop_father->header == dest)
629 return false;
632 return true;
635 /* Return nonzero if we can reach target from src by falling through. */
636 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
638 bool
639 can_fallthru (basic_block src, basic_block target)
641 rtx_insn *insn = BB_END (src);
642 rtx_insn *insn2;
643 edge e;
644 edge_iterator ei;
646 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
647 return true;
648 if (src->next_bb != target)
649 return false;
651 /* ??? Later we may add code to move jump tables offline. */
652 if (tablejump_p (insn, NULL, NULL))
653 return false;
655 FOR_EACH_EDGE (e, ei, src->succs)
656 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
657 && e->flags & EDGE_FALLTHRU)
658 return false;
660 insn2 = BB_HEAD (target);
661 if (!active_insn_p (insn2))
662 insn2 = next_active_insn (insn2);
664 return next_active_insn (insn) == insn2;
667 /* Return nonzero if we could reach target from src by falling through,
668 if the target was made adjacent. If we already have a fall-through
669 edge to the exit block, we can't do that. */
670 static bool
671 could_fall_through (basic_block src, basic_block target)
673 edge e;
674 edge_iterator ei;
676 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
677 return true;
678 FOR_EACH_EDGE (e, ei, src->succs)
679 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
680 && e->flags & EDGE_FALLTHRU)
681 return 0;
682 return true;
685 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
686 rtx_note *
687 bb_note (basic_block bb)
689 rtx_insn *note;
691 note = BB_HEAD (bb);
692 if (LABEL_P (note))
693 note = NEXT_INSN (note);
695 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
696 return as_a <rtx_note *> (note);
699 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
700 note associated with the BLOCK. */
702 static rtx_insn *
703 first_insn_after_basic_block_note (basic_block block)
705 rtx_insn *insn;
707 /* Get the first instruction in the block. */
708 insn = BB_HEAD (block);
710 if (insn == NULL_RTX)
711 return NULL;
712 if (LABEL_P (insn))
713 insn = NEXT_INSN (insn);
714 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
716 return NEXT_INSN (insn);
719 /* Creates a new basic block just after basic block BB by splitting
720 everything after specified instruction INSNP. */
722 static basic_block
723 rtl_split_block (basic_block bb, void *insnp)
725 basic_block new_bb;
726 rtx_insn *insn = (rtx_insn *) insnp;
727 edge e;
728 edge_iterator ei;
730 if (!insn)
732 insn = first_insn_after_basic_block_note (bb);
734 if (insn)
736 rtx_insn *next = insn;
738 insn = PREV_INSN (insn);
740 /* If the block contains only debug insns, insn would have
741 been NULL in a non-debug compilation, and then we'd end
742 up emitting a DELETED note. For -fcompare-debug
743 stability, emit the note too. */
744 if (insn != BB_END (bb)
745 && DEBUG_INSN_P (next)
746 && DEBUG_INSN_P (BB_END (bb)))
748 while (next != BB_END (bb) && DEBUG_INSN_P (next))
749 next = NEXT_INSN (next);
751 if (next == BB_END (bb))
752 emit_note_after (NOTE_INSN_DELETED, next);
755 else
756 insn = get_last_insn ();
759 /* We probably should check type of the insn so that we do not create
760 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
761 bother. */
762 if (insn == BB_END (bb))
763 emit_note_after (NOTE_INSN_DELETED, insn);
765 /* Create the new basic block. */
766 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
767 BB_COPY_PARTITION (new_bb, bb);
768 BB_END (bb) = insn;
770 /* Redirect the outgoing edges. */
771 new_bb->succs = bb->succs;
772 bb->succs = NULL;
773 FOR_EACH_EDGE (e, ei, new_bb->succs)
774 e->src = new_bb;
776 /* The new block starts off being dirty. */
777 df_set_bb_dirty (bb);
778 return new_bb;
781 /* Return true if LOC1 and LOC2 are equivalent for
782 unique_locus_on_edge_between_p purposes. */
784 static bool
785 loc_equal (location_t loc1, location_t loc2)
787 if (loc1 == loc2)
788 return true;
790 expanded_location loce1 = expand_location (loc1);
791 expanded_location loce2 = expand_location (loc2);
793 if (loce1.line != loce2.line
794 || loce1.column != loce2.column
795 || loce1.data != loce2.data)
796 return false;
797 if (loce1.file == loce2.file)
798 return true;
799 return (loce1.file != NULL
800 && loce2.file != NULL
801 && filename_cmp (loce1.file, loce2.file) == 0);
804 /* Return true if the single edge between blocks A and B is the only place
805 in RTL which holds some unique locus. */
807 static bool
808 unique_locus_on_edge_between_p (basic_block a, basic_block b)
810 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
811 rtx_insn *insn, *end;
813 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
814 return false;
816 /* First scan block A backward. */
817 insn = BB_END (a);
818 end = PREV_INSN (BB_HEAD (a));
819 while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
820 insn = PREV_INSN (insn);
822 if (insn != end && loc_equal (INSN_LOCATION (insn), goto_locus))
823 return false;
825 /* Then scan block B forward. */
826 insn = BB_HEAD (b);
827 if (insn)
829 end = NEXT_INSN (BB_END (b));
830 while (insn != end && !NONDEBUG_INSN_P (insn))
831 insn = NEXT_INSN (insn);
833 if (insn != end && INSN_HAS_LOCATION (insn)
834 && loc_equal (INSN_LOCATION (insn), goto_locus))
835 return false;
838 return true;
841 /* If the single edge between blocks A and B is the only place in RTL which
842 holds some unique locus, emit a nop with that locus between the blocks. */
844 static void
845 emit_nop_for_unique_locus_between (basic_block a, basic_block b)
847 if (!unique_locus_on_edge_between_p (a, b))
848 return;
850 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
851 INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
854 /* Blocks A and B are to be merged into a single block A. The insns
855 are already contiguous. */
857 static void
858 rtl_merge_blocks (basic_block a, basic_block b)
860 /* If B is a forwarder block whose outgoing edge has no location, we'll
861 propagate the locus of the edge between A and B onto it. */
862 const bool forward_edge_locus
863 = (b->flags & BB_FORWARDER_BLOCK) != 0
864 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
865 rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
866 rtx_insn *del_first = NULL, *del_last = NULL;
867 rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
868 int b_empty = 0;
870 if (dump_file)
871 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
872 a->index);
874 while (DEBUG_INSN_P (b_end))
875 b_end = PREV_INSN (b_debug_start = b_end);
877 /* If there was a CODE_LABEL beginning B, delete it. */
878 if (LABEL_P (b_head))
880 /* Detect basic blocks with nothing but a label. This can happen
881 in particular at the end of a function. */
882 if (b_head == b_end)
883 b_empty = 1;
885 del_first = del_last = b_head;
886 b_head = NEXT_INSN (b_head);
889 /* Delete the basic block note and handle blocks containing just that
890 note. */
891 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
893 if (b_head == b_end)
894 b_empty = 1;
895 if (! del_last)
896 del_first = b_head;
898 del_last = b_head;
899 b_head = NEXT_INSN (b_head);
902 /* If there was a jump out of A, delete it. */
903 if (JUMP_P (a_end))
905 rtx_insn *prev;
907 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
908 if (!NOTE_P (prev)
909 || NOTE_INSN_BASIC_BLOCK_P (prev)
910 || prev == BB_HEAD (a))
911 break;
913 del_first = a_end;
915 a_end = PREV_INSN (del_first);
917 else if (BARRIER_P (NEXT_INSN (a_end)))
918 del_first = NEXT_INSN (a_end);
920 /* Delete everything marked above as well as crap that might be
921 hanging out between the two blocks. */
922 BB_END (a) = a_end;
923 BB_HEAD (b) = b_empty ? NULL : b_head;
924 delete_insn_chain (del_first, del_last, true);
926 /* If not optimizing, preserve the locus of the single edge between
927 blocks A and B if necessary by emitting a nop. */
928 if (!optimize
929 && !forward_edge_locus
930 && !DECL_IGNORED_P (current_function_decl))
932 emit_nop_for_unique_locus_between (a, b);
933 a_end = BB_END (a);
936 /* Reassociate the insns of B with A. */
937 if (!b_empty)
939 update_bb_for_insn_chain (a_end, b_debug_end, a);
941 BB_END (a) = b_debug_end;
942 BB_HEAD (b) = NULL;
944 else if (b_end != b_debug_end)
946 /* Move any deleted labels and other notes between the end of A
947 and the debug insns that make up B after the debug insns,
948 bringing the debug insns into A while keeping the notes after
949 the end of A. */
950 if (NEXT_INSN (a_end) != b_debug_start)
951 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
952 b_debug_end);
953 update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
954 BB_END (a) = b_debug_end;
957 df_bb_delete (b->index);
959 if (forward_edge_locus)
960 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
962 if (dump_file)
963 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
967 /* Return true when block A and B can be merged. */
969 static bool
970 rtl_can_merge_blocks (basic_block a, basic_block b)
972 /* If we are partitioning hot/cold basic blocks, we don't want to
973 mess up unconditional or indirect jumps that cross between hot
974 and cold sections.
976 Basic block partitioning may result in some jumps that appear to
977 be optimizable (or blocks that appear to be mergeable), but which really
978 must be left untouched (they are required to make it safely across
979 partition boundaries). See the comments at the top of
980 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
982 if (BB_PARTITION (a) != BB_PARTITION (b))
983 return false;
985 /* Protect the loop latches. */
986 if (current_loops && b->loop_father->latch == b)
987 return false;
989 /* There must be exactly one edge in between the blocks. */
990 return (single_succ_p (a)
991 && single_succ (a) == b
992 && single_pred_p (b)
993 && a != b
994 /* Must be simple edge. */
995 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
996 && a->next_bb == b
997 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
998 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
999 /* If the jump insn has side effects,
1000 we can't kill the edge. */
1001 && (!JUMP_P (BB_END (a))
1002 || (reload_completed
1003 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
1006 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
1007 exist. */
1009 rtx_code_label *
1010 block_label (basic_block block)
1012 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
1013 return NULL;
1015 if (!LABEL_P (BB_HEAD (block)))
1017 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
1020 return as_a <rtx_code_label *> (BB_HEAD (block));
1023 /* Remove all barriers from BB_FOOTER of a BB. */
1025 static void
1026 remove_barriers_from_footer (basic_block bb)
1028 rtx_insn *insn = BB_FOOTER (bb);
1030 /* Remove barriers but keep jumptables. */
1031 while (insn)
1033 if (BARRIER_P (insn))
1035 if (PREV_INSN (insn))
1036 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1037 else
1038 BB_FOOTER (bb) = NEXT_INSN (insn);
1039 if (NEXT_INSN (insn))
1040 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1042 if (LABEL_P (insn))
1043 return;
1044 insn = NEXT_INSN (insn);
1048 /* Attempt to perform edge redirection by replacing possibly complex jump
1049 instruction by unconditional jump or removing jump completely. This can
1050 apply only if all edges now point to the same block. The parameters and
1051 return values are equivalent to redirect_edge_and_branch. */
1053 edge
1054 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
1056 basic_block src = e->src;
1057 rtx_insn *insn = BB_END (src);
1058 rtx set;
1059 int fallthru = 0;
1061 /* If we are partitioning hot/cold basic blocks, we don't want to
1062 mess up unconditional or indirect jumps that cross between hot
1063 and cold sections.
1065 Basic block partitioning may result in some jumps that appear to
1066 be optimizable (or blocks that appear to be mergeable), but which really
1067 must be left untouched (they are required to make it safely across
1068 partition boundaries). See the comments at the top of
1069 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
1071 if (BB_PARTITION (src) != BB_PARTITION (target))
1072 return NULL;
1074 /* We can replace or remove a complex jump only when we have exactly
1075 two edges. Also, if we have exactly one outgoing edge, we can
1076 redirect that. */
1077 if (EDGE_COUNT (src->succs) >= 3
1078 /* Verify that all targets will be TARGET. Specifically, the
1079 edge that is not E must also go to TARGET. */
1080 || (EDGE_COUNT (src->succs) == 2
1081 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1082 return NULL;
1084 if (!onlyjump_p (insn))
1085 return NULL;
1086 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1087 return NULL;
1089 /* Avoid removing branch with side effects. */
1090 set = single_set (insn);
1091 if (!set || side_effects_p (set))
1092 return NULL;
1094 /* See if we can create the fallthru edge. */
1095 if (in_cfglayout || can_fallthru (src, target))
1097 if (dump_file)
1098 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1099 fallthru = 1;
1101 /* Selectively unlink whole insn chain. */
1102 if (in_cfglayout)
1104 delete_insn_chain (insn, BB_END (src), false);
1105 remove_barriers_from_footer (src);
1107 else
1108 delete_insn_chain (insn, PREV_INSN (BB_HEAD (target)), false);
1111 /* If this already is simplejump, redirect it. */
1112 else if (simplejump_p (insn))
1114 if (e->dest == target)
1115 return NULL;
1116 if (dump_file)
1117 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1118 INSN_UID (insn), e->dest->index, target->index);
1119 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1120 block_label (target), 0))
1122 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1123 return NULL;
1127 /* Cannot do anything for target exit block. */
1128 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1129 return NULL;
1131 /* Or replace possibly complicated jump insn by simple jump insn. */
1132 else
1134 rtx_code_label *target_label = block_label (target);
1135 rtx_insn *barrier;
1136 rtx_insn *label;
1137 rtx_jump_table_data *table;
1139 emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn);
1140 JUMP_LABEL (BB_END (src)) = target_label;
1141 LABEL_NUSES (target_label)++;
1142 if (dump_file)
1143 fprintf (dump_file, "Replacing insn %i by jump %i\n",
1144 INSN_UID (insn), INSN_UID (BB_END (src)));
1147 delete_insn_chain (insn, insn, false);
1149 /* Recognize a tablejump that we are converting to a
1150 simple jump and remove its associated CODE_LABEL
1151 and ADDR_VEC or ADDR_DIFF_VEC. */
1152 if (tablejump_p (insn, &label, &table))
1153 delete_insn_chain (label, table, false);
1155 barrier = next_nonnote_nondebug_insn (BB_END (src));
1156 if (!barrier || !BARRIER_P (barrier))
1157 emit_barrier_after (BB_END (src));
1158 else
1160 if (barrier != NEXT_INSN (BB_END (src)))
1162 /* Move the jump before barrier so that the notes
1163 which originally were or were created before jump table are
1164 inside the basic block. */
1165 rtx_insn *new_insn = BB_END (src);
1167 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1168 PREV_INSN (barrier), src);
1170 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1171 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1173 SET_NEXT_INSN (new_insn) = barrier;
1174 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1176 SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1177 SET_PREV_INSN (barrier) = new_insn;
1182 /* Keep only one edge out and set proper flags. */
1183 if (!single_succ_p (src))
1184 remove_edge (e);
1185 gcc_assert (single_succ_p (src));
1187 e = single_succ_edge (src);
1188 if (fallthru)
1189 e->flags = EDGE_FALLTHRU;
1190 else
1191 e->flags = 0;
1193 e->probability = profile_probability::always ();
1195 if (e->dest != target)
1196 redirect_edge_succ (e, target);
1197 return e;
1200 /* Subroutine of redirect_branch_edge that tries to patch the jump
1201 instruction INSN so that it reaches block NEW. Do this
1202 only when it originally reached block OLD. Return true if this
1203 worked or the original target wasn't OLD, return false if redirection
1204 doesn't work. */
1206 static bool
1207 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1209 rtx_jump_table_data *table;
1210 rtx tmp;
1211 /* Recognize a tablejump and adjust all matching cases. */
1212 if (tablejump_p (insn, NULL, &table))
1214 rtvec vec;
1215 int j;
1216 rtx_code_label *new_label = block_label (new_bb);
1218 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1219 return false;
1220 vec = table->get_labels ();
1222 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1223 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1225 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1226 --LABEL_NUSES (old_label);
1227 ++LABEL_NUSES (new_label);
1230 /* Handle casesi dispatch insns. */
1231 if ((tmp = tablejump_casesi_pattern (insn)) != NULL_RTX
1232 && label_ref_label (XEXP (SET_SRC (tmp), 2)) == old_label)
1234 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1235 new_label);
1236 --LABEL_NUSES (old_label);
1237 ++LABEL_NUSES (new_label);
1240 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1242 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1243 rtx note;
1245 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1246 return false;
1247 rtx_code_label *new_label = block_label (new_bb);
1249 for (i = 0; i < n; ++i)
1251 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1252 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1253 if (XEXP (old_ref, 0) == old_label)
1255 ASM_OPERANDS_LABEL (tmp, i)
1256 = gen_rtx_LABEL_REF (Pmode, new_label);
1257 --LABEL_NUSES (old_label);
1258 ++LABEL_NUSES (new_label);
1262 if (JUMP_LABEL (insn) == old_label)
1264 JUMP_LABEL (insn) = new_label;
1265 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1266 if (note)
1267 remove_note (insn, note);
1269 else
1271 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1272 if (note)
1273 remove_note (insn, note);
1274 if (JUMP_LABEL (insn) != new_label
1275 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1276 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1278 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1279 != NULL_RTX)
1280 XEXP (note, 0) = new_label;
1282 else
1284 /* ?? We may play the games with moving the named labels from
1285 one basic block to the other in case only one computed_jump is
1286 available. */
1287 if (computed_jump_p (insn)
1288 /* A return instruction can't be redirected. */
1289 || returnjump_p (insn))
1290 return false;
1292 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1294 /* If the insn doesn't go where we think, we're confused. */
1295 gcc_assert (JUMP_LABEL (insn) == old_label);
1297 /* If the substitution doesn't succeed, die. This can happen
1298 if the back end emitted unrecognizable instructions or if
1299 target is exit block on some arches. Or for crossing
1300 jumps. */
1301 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1302 block_label (new_bb), 0))
1304 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
1305 || CROSSING_JUMP_P (insn));
1306 return false;
1310 return true;
1314 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1315 NULL on failure */
1316 static edge
1317 redirect_branch_edge (edge e, basic_block target)
1319 rtx_insn *old_label = BB_HEAD (e->dest);
1320 basic_block src = e->src;
1321 rtx_insn *insn = BB_END (src);
1323 /* We can only redirect non-fallthru edges of jump insn. */
1324 if (e->flags & EDGE_FALLTHRU)
1325 return NULL;
1326 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1327 return NULL;
1329 if (!currently_expanding_to_rtl)
1331 if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1332 return NULL;
1334 else
1335 /* When expanding this BB might actually contain multiple
1336 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1337 Redirect all of those that match our label. */
1338 FOR_BB_INSNS (src, insn)
1339 if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1340 old_label, target))
1341 return NULL;
1343 if (dump_file)
1344 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1345 e->src->index, e->dest->index, target->index);
1347 if (e->dest != target)
1348 e = redirect_edge_succ_nodup (e, target);
1350 return e;
1353 /* Called when edge E has been redirected to a new destination,
1354 in order to update the region crossing flag on the edge and
1355 jump. */
1357 static void
1358 fixup_partition_crossing (edge e)
1360 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1361 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1362 return;
1363 /* If we redirected an existing edge, it may already be marked
1364 crossing, even though the new src is missing a reg crossing note.
1365 But make sure reg crossing note doesn't already exist before
1366 inserting. */
1367 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1369 e->flags |= EDGE_CROSSING;
1370 if (JUMP_P (BB_END (e->src)))
1371 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1373 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1375 e->flags &= ~EDGE_CROSSING;
1376 /* Remove the section crossing note from jump at end of
1377 src if it exists, and if no other successors are
1378 still crossing. */
1379 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1381 bool has_crossing_succ = false;
1382 edge e2;
1383 edge_iterator ei;
1384 FOR_EACH_EDGE (e2, ei, e->src->succs)
1386 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1387 if (has_crossing_succ)
1388 break;
1390 if (!has_crossing_succ)
1391 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1396 /* Called when block BB has been reassigned to the cold partition,
1397 because it is now dominated by another cold block,
1398 to ensure that the region crossing attributes are updated. */
1400 static void
1401 fixup_new_cold_bb (basic_block bb)
1403 edge e;
1404 edge_iterator ei;
1406 /* This is called when a hot bb is found to now be dominated
1407 by a cold bb and therefore needs to become cold. Therefore,
1408 its preds will no longer be region crossing. Any non-dominating
1409 preds that were previously hot would also have become cold
1410 in the caller for the same region. Any preds that were previously
1411 region-crossing will be adjusted in fixup_partition_crossing. */
1412 FOR_EACH_EDGE (e, ei, bb->preds)
1414 fixup_partition_crossing (e);
1417 /* Possibly need to make bb's successor edges region crossing,
1418 or remove stale region crossing. */
1419 FOR_EACH_EDGE (e, ei, bb->succs)
1421 /* We can't have fall-through edges across partition boundaries.
1422 Note that force_nonfallthru will do any necessary partition
1423 boundary fixup by calling fixup_partition_crossing itself. */
1424 if ((e->flags & EDGE_FALLTHRU)
1425 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1426 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1427 force_nonfallthru (e);
1428 else
1429 fixup_partition_crossing (e);
1433 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1434 expense of adding new instructions or reordering basic blocks.
1436 Function can be also called with edge destination equivalent to the TARGET.
1437 Then it should try the simplifications and do nothing if none is possible.
1439 Return edge representing the branch if transformation succeeded. Return NULL
1440 on failure.
1441 We still return NULL in case E already destinated TARGET and we didn't
1442 managed to simplify instruction stream. */
1444 static edge
1445 rtl_redirect_edge_and_branch (edge e, basic_block target)
1447 edge ret;
1448 basic_block src = e->src;
1449 basic_block dest = e->dest;
1451 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1452 return NULL;
1454 if (dest == target)
1455 return e;
1457 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1459 df_set_bb_dirty (src);
1460 fixup_partition_crossing (ret);
1461 return ret;
1464 ret = redirect_branch_edge (e, target);
1465 if (!ret)
1466 return NULL;
1468 df_set_bb_dirty (src);
1469 fixup_partition_crossing (ret);
1470 return ret;
1473 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1475 void
1476 emit_barrier_after_bb (basic_block bb)
1478 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1479 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1480 || current_ir_type () == IR_RTL_CFGLAYOUT);
1481 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1483 rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1485 if (BB_FOOTER (bb))
1487 rtx_insn *footer_tail = BB_FOOTER (bb);
1489 while (NEXT_INSN (footer_tail))
1490 footer_tail = NEXT_INSN (footer_tail);
1491 if (!BARRIER_P (footer_tail))
1493 SET_NEXT_INSN (footer_tail) = insn;
1494 SET_PREV_INSN (insn) = footer_tail;
1497 else
1498 BB_FOOTER (bb) = insn;
1502 /* Like force_nonfallthru below, but additionally performs redirection
1503 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1504 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1505 simple_return_rtx, indicating which kind of returnjump to create.
1506 It should be NULL otherwise. */
1508 basic_block
1509 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1511 basic_block jump_block, new_bb = NULL, src = e->src;
1512 rtx note;
1513 edge new_edge;
1514 int abnormal_edge_flags = 0;
1515 bool asm_goto_edge = false;
1516 int loc;
1518 /* In the case the last instruction is conditional jump to the next
1519 instruction, first redirect the jump itself and then continue
1520 by creating a basic block afterwards to redirect fallthru edge. */
1521 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1522 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1523 && any_condjump_p (BB_END (e->src))
1524 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1526 rtx note;
1527 edge b = unchecked_make_edge (e->src, target, 0);
1528 bool redirected;
1530 redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1531 block_label (target), 0);
1532 gcc_assert (redirected);
1534 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1535 if (note)
1537 int prob = XINT (note, 0);
1539 b->probability = profile_probability::from_reg_br_prob_note (prob);
1540 e->probability -= e->probability;
1544 if (e->flags & EDGE_ABNORMAL)
1546 /* Irritating special case - fallthru edge to the same block as abnormal
1547 edge.
1548 We can't redirect abnormal edge, but we still can split the fallthru
1549 one and create separate abnormal edge to original destination.
1550 This allows bb-reorder to make such edge non-fallthru. */
1551 gcc_assert (e->dest == target);
1552 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1553 e->flags &= EDGE_FALLTHRU;
1555 else
1557 gcc_assert (e->flags & EDGE_FALLTHRU);
1558 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1560 /* We can't redirect the entry block. Create an empty block
1561 at the start of the function which we use to add the new
1562 jump. */
1563 edge tmp;
1564 edge_iterator ei;
1565 bool found = false;
1567 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1568 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1569 bb->count = ENTRY_BLOCK_PTR_FOR_FN (cfun)->count;
1571 /* Make sure new block ends up in correct hot/cold section. */
1572 BB_COPY_PARTITION (bb, e->dest);
1574 /* Change the existing edge's source to be the new block, and add
1575 a new edge from the entry block to the new block. */
1576 e->src = bb;
1577 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1578 (tmp = ei_safe_edge (ei)); )
1580 if (tmp == e)
1582 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1583 found = true;
1584 break;
1586 else
1587 ei_next (&ei);
1590 gcc_assert (found);
1592 vec_safe_push (bb->succs, e);
1593 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1594 EDGE_FALLTHRU);
1598 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1599 don't point to the target or fallthru label. */
1600 if (JUMP_P (BB_END (e->src))
1601 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1602 && (e->flags & EDGE_FALLTHRU)
1603 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1605 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1606 bool adjust_jump_target = false;
1608 for (i = 0; i < n; ++i)
1610 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1612 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1613 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1614 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1615 adjust_jump_target = true;
1617 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1618 asm_goto_edge = true;
1620 if (adjust_jump_target)
1622 rtx_insn *insn = BB_END (e->src);
1623 rtx note;
1624 rtx_insn *old_label = BB_HEAD (e->dest);
1625 rtx_insn *new_label = BB_HEAD (target);
1627 if (JUMP_LABEL (insn) == old_label)
1629 JUMP_LABEL (insn) = new_label;
1630 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1631 if (note)
1632 remove_note (insn, note);
1634 else
1636 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1637 if (note)
1638 remove_note (insn, note);
1639 if (JUMP_LABEL (insn) != new_label
1640 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1641 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1643 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1644 != NULL_RTX)
1645 XEXP (note, 0) = new_label;
1649 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1651 rtx_insn *new_head;
1652 profile_count count = e->count ();
1653 profile_probability probability = e->probability;
1654 /* Create the new structures. */
1656 /* If the old block ended with a tablejump, skip its table
1657 by searching forward from there. Otherwise start searching
1658 forward from the last instruction of the old block. */
1659 rtx_jump_table_data *table;
1660 if (tablejump_p (BB_END (e->src), NULL, &table))
1661 new_head = table;
1662 else
1663 new_head = BB_END (e->src);
1664 new_head = NEXT_INSN (new_head);
1666 jump_block = create_basic_block (new_head, NULL, e->src);
1667 jump_block->count = count;
1669 /* Make sure new block ends up in correct hot/cold section. */
1671 BB_COPY_PARTITION (jump_block, e->src);
1673 /* Wire edge in. */
1674 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1675 new_edge->probability = probability;
1677 /* Redirect old edge. */
1678 redirect_edge_pred (e, jump_block);
1679 e->probability = profile_probability::always ();
1681 /* If e->src was previously region crossing, it no longer is
1682 and the reg crossing note should be removed. */
1683 fixup_partition_crossing (new_edge);
1685 /* If asm goto has any label refs to target's label,
1686 add also edge from asm goto bb to target. */
1687 if (asm_goto_edge)
1689 new_edge->probability = new_edge->probability.apply_scale (1, 2);
1690 jump_block->count = jump_block->count.apply_scale (1, 2);
1691 edge new_edge2 = make_edge (new_edge->src, target,
1692 e->flags & ~EDGE_FALLTHRU);
1693 new_edge2->probability = probability - new_edge->probability;
1696 new_bb = jump_block;
1698 else
1699 jump_block = e->src;
1701 loc = e->goto_locus;
1702 e->flags &= ~EDGE_FALLTHRU;
1703 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1705 if (jump_label == ret_rtx)
1706 emit_jump_insn_after_setloc (targetm.gen_return (),
1707 BB_END (jump_block), loc);
1708 else
1710 gcc_assert (jump_label == simple_return_rtx);
1711 emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1712 BB_END (jump_block), loc);
1714 set_return_jump_label (BB_END (jump_block));
1716 else
1718 rtx_code_label *label = block_label (target);
1719 emit_jump_insn_after_setloc (targetm.gen_jump (label),
1720 BB_END (jump_block), loc);
1721 JUMP_LABEL (BB_END (jump_block)) = label;
1722 LABEL_NUSES (label)++;
1725 /* We might be in cfg layout mode, and if so, the following routine will
1726 insert the barrier correctly. */
1727 emit_barrier_after_bb (jump_block);
1728 redirect_edge_succ_nodup (e, target);
1730 if (abnormal_edge_flags)
1731 make_edge (src, target, abnormal_edge_flags);
1733 df_mark_solutions_dirty ();
1734 fixup_partition_crossing (e);
1735 return new_bb;
1738 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1739 (and possibly create new basic block) to make edge non-fallthru.
1740 Return newly created BB or NULL if none. */
1742 static basic_block
1743 rtl_force_nonfallthru (edge e)
1745 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1748 /* Redirect edge even at the expense of creating new jump insn or
1749 basic block. Return new basic block if created, NULL otherwise.
1750 Conversion must be possible. */
1752 static basic_block
1753 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1755 if (redirect_edge_and_branch (e, target)
1756 || e->dest == target)
1757 return NULL;
1759 /* In case the edge redirection failed, try to force it to be non-fallthru
1760 and redirect newly created simplejump. */
1761 df_set_bb_dirty (e->src);
1762 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1765 /* The given edge should potentially be a fallthru edge. If that is in
1766 fact true, delete the jump and barriers that are in the way. */
1768 static void
1769 rtl_tidy_fallthru_edge (edge e)
1771 rtx_insn *q;
1772 basic_block b = e->src, c = b->next_bb;
1774 /* ??? In a late-running flow pass, other folks may have deleted basic
1775 blocks by nopping out blocks, leaving multiple BARRIERs between here
1776 and the target label. They ought to be chastised and fixed.
1778 We can also wind up with a sequence of undeletable labels between
1779 one block and the next.
1781 So search through a sequence of barriers, labels, and notes for
1782 the head of block C and assert that we really do fall through. */
1784 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1785 if (NONDEBUG_INSN_P (q))
1786 return;
1788 /* Remove what will soon cease being the jump insn from the source block.
1789 If block B consisted only of this single jump, turn it into a deleted
1790 note. */
1791 q = BB_END (b);
1792 if (JUMP_P (q)
1793 && onlyjump_p (q)
1794 && (any_uncondjump_p (q)
1795 || single_succ_p (b)))
1797 rtx_insn *label;
1798 rtx_jump_table_data *table;
1800 if (tablejump_p (q, &label, &table))
1802 /* The label is likely mentioned in some instruction before
1803 the tablejump and might not be DCEd, so turn it into
1804 a note instead and move before the tablejump that is going to
1805 be deleted. */
1806 const char *name = LABEL_NAME (label);
1807 PUT_CODE (label, NOTE);
1808 NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1809 NOTE_DELETED_LABEL_NAME (label) = name;
1810 reorder_insns (label, label, PREV_INSN (q));
1811 delete_insn (table);
1814 q = PREV_INSN (q);
1816 /* Unconditional jumps with side-effects (i.e. which we can't just delete
1817 together with the barrier) should never have a fallthru edge. */
1818 else if (JUMP_P (q) && any_uncondjump_p (q))
1819 return;
1821 /* Selectively unlink the sequence. */
1822 if (q != PREV_INSN (BB_HEAD (c)))
1823 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1825 e->flags |= EDGE_FALLTHRU;
1828 /* Should move basic block BB after basic block AFTER. NIY. */
1830 static bool
1831 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1832 basic_block after ATTRIBUTE_UNUSED)
1834 return false;
1837 /* Locate the last bb in the same partition as START_BB. */
1839 static basic_block
1840 last_bb_in_partition (basic_block start_bb)
1842 basic_block bb;
1843 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1845 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1846 return bb;
1848 /* Return bb before the exit block. */
1849 return bb->prev_bb;
1852 /* Split a (typically critical) edge. Return the new block.
1853 The edge must not be abnormal.
1855 ??? The code generally expects to be called on critical edges.
1856 The case of a block ending in an unconditional jump to a
1857 block with multiple predecessors is not handled optimally. */
1859 static basic_block
1860 rtl_split_edge (edge edge_in)
1862 basic_block bb, new_bb;
1863 rtx_insn *before;
1865 /* Abnormal edges cannot be split. */
1866 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1868 /* We are going to place the new block in front of edge destination.
1869 Avoid existence of fallthru predecessors. */
1870 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1872 edge e = find_fallthru_edge (edge_in->dest->preds);
1874 if (e)
1875 force_nonfallthru (e);
1878 /* Create the basic block note. */
1879 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1880 before = BB_HEAD (edge_in->dest);
1881 else
1882 before = NULL;
1884 /* If this is a fall through edge to the exit block, the blocks might be
1885 not adjacent, and the right place is after the source. */
1886 if ((edge_in->flags & EDGE_FALLTHRU)
1887 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1889 before = NEXT_INSN (BB_END (edge_in->src));
1890 bb = create_basic_block (before, NULL, edge_in->src);
1891 BB_COPY_PARTITION (bb, edge_in->src);
1893 else
1895 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1897 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1898 BB_COPY_PARTITION (bb, edge_in->dest);
1900 else
1902 basic_block after = edge_in->dest->prev_bb;
1903 /* If this is post-bb reordering, and the edge crosses a partition
1904 boundary, the new block needs to be inserted in the bb chain
1905 at the end of the src partition (since we put the new bb into
1906 that partition, see below). Otherwise we may end up creating
1907 an extra partition crossing in the chain, which is illegal.
1908 It can't go after the src, because src may have a fall-through
1909 to a different block. */
1910 if (crtl->bb_reorder_complete
1911 && (edge_in->flags & EDGE_CROSSING))
1913 after = last_bb_in_partition (edge_in->src);
1914 before = get_last_bb_insn (after);
1915 /* The instruction following the last bb in partition should
1916 be a barrier, since it cannot end in a fall-through. */
1917 gcc_checking_assert (BARRIER_P (before));
1918 before = NEXT_INSN (before);
1920 bb = create_basic_block (before, NULL, after);
1921 /* Put the split bb into the src partition, to avoid creating
1922 a situation where a cold bb dominates a hot bb, in the case
1923 where src is cold and dest is hot. The src will dominate
1924 the new bb (whereas it might not have dominated dest). */
1925 BB_COPY_PARTITION (bb, edge_in->src);
1929 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1931 /* Can't allow a region crossing edge to be fallthrough. */
1932 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1933 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1935 new_bb = force_nonfallthru (single_succ_edge (bb));
1936 gcc_assert (!new_bb);
1939 /* For non-fallthru edges, we must adjust the predecessor's
1940 jump instruction to target our new block. */
1941 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1943 edge redirected = redirect_edge_and_branch (edge_in, bb);
1944 gcc_assert (redirected);
1946 else
1948 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1950 /* For asm goto even splitting of fallthru edge might
1951 need insn patching, as other labels might point to the
1952 old label. */
1953 rtx_insn *last = BB_END (edge_in->src);
1954 if (last
1955 && JUMP_P (last)
1956 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1957 && (extract_asm_operands (PATTERN (last))
1958 || JUMP_LABEL (last) == before)
1959 && patch_jump_insn (last, before, bb))
1960 df_set_bb_dirty (edge_in->src);
1962 redirect_edge_succ (edge_in, bb);
1965 return bb;
1968 /* Queue instructions for insertion on an edge between two basic blocks.
1969 The new instructions and basic blocks (if any) will not appear in the
1970 CFG until commit_edge_insertions is called. */
1972 void
1973 insert_insn_on_edge (rtx pattern, edge e)
1975 /* We cannot insert instructions on an abnormal critical edge.
1976 It will be easier to find the culprit if we die now. */
1977 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1979 if (e->insns.r == NULL_RTX)
1980 start_sequence ();
1981 else
1982 push_to_sequence (e->insns.r);
1984 emit_insn (pattern);
1986 e->insns.r = get_insns ();
1987 end_sequence ();
1990 /* Update the CFG for the instructions queued on edge E. */
1992 void
1993 commit_one_edge_insertion (edge e)
1995 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1996 basic_block bb;
1998 /* Pull the insns off the edge now since the edge might go away. */
1999 insns = e->insns.r;
2000 e->insns.r = NULL;
2002 /* Figure out where to put these insns. If the destination has
2003 one predecessor, insert there. Except for the exit block. */
2004 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2006 bb = e->dest;
2008 /* Get the location correct wrt a code label, and "nice" wrt
2009 a basic block note, and before everything else. */
2010 tmp = BB_HEAD (bb);
2011 if (LABEL_P (tmp))
2012 tmp = NEXT_INSN (tmp);
2013 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
2014 tmp = NEXT_INSN (tmp);
2015 if (tmp == BB_HEAD (bb))
2016 before = tmp;
2017 else if (tmp)
2018 after = PREV_INSN (tmp);
2019 else
2020 after = get_last_insn ();
2023 /* If the source has one successor and the edge is not abnormal,
2024 insert there. Except for the entry block.
2025 Don't do this if the predecessor ends in a jump other than
2026 unconditional simple jump. E.g. for asm goto that points all
2027 its labels at the fallthru basic block, we can't insert instructions
2028 before the asm goto, as the asm goto can have various of side effects,
2029 and can't emit instructions after the asm goto, as it must end
2030 the basic block. */
2031 else if ((e->flags & EDGE_ABNORMAL) == 0
2032 && single_succ_p (e->src)
2033 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2034 && (!JUMP_P (BB_END (e->src))
2035 || simplejump_p (BB_END (e->src))))
2037 bb = e->src;
2039 /* It is possible to have a non-simple jump here. Consider a target
2040 where some forms of unconditional jumps clobber a register. This
2041 happens on the fr30 for example.
2043 We know this block has a single successor, so we can just emit
2044 the queued insns before the jump. */
2045 if (JUMP_P (BB_END (bb)))
2046 before = BB_END (bb);
2047 else
2049 /* We'd better be fallthru, or we've lost track of what's what. */
2050 gcc_assert (e->flags & EDGE_FALLTHRU);
2052 after = BB_END (bb);
2056 /* Otherwise we must split the edge. */
2057 else
2059 bb = split_edge (e);
2061 /* If E crossed a partition boundary, we needed to make bb end in
2062 a region-crossing jump, even though it was originally fallthru. */
2063 if (JUMP_P (BB_END (bb)))
2064 before = BB_END (bb);
2065 else
2066 after = BB_END (bb);
2069 /* Now that we've found the spot, do the insertion. */
2070 if (before)
2072 emit_insn_before_noloc (insns, before, bb);
2073 last = prev_nonnote_insn (before);
2075 else
2076 last = emit_insn_after_noloc (insns, after, bb);
2078 if (returnjump_p (last))
2080 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2081 This is not currently a problem because this only happens
2082 for the (single) epilogue, which already has a fallthru edge
2083 to EXIT. */
2085 e = single_succ_edge (bb);
2086 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2087 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2089 e->flags &= ~EDGE_FALLTHRU;
2090 emit_barrier_after (last);
2092 if (before)
2093 delete_insn (before);
2095 else
2096 gcc_assert (!JUMP_P (last));
2099 /* Update the CFG for all queued instructions. */
2101 void
2102 commit_edge_insertions (void)
2104 basic_block bb;
2106 /* Optimization passes that invoke this routine can cause hot blocks
2107 previously reached by both hot and cold blocks to become dominated only
2108 by cold blocks. This will cause the verification below to fail,
2109 and lead to now cold code in the hot section. In some cases this
2110 may only be visible after newly unreachable blocks are deleted,
2111 which will be done by fixup_partitions. */
2112 fixup_partitions ();
2114 if (!currently_expanding_to_rtl)
2115 checking_verify_flow_info ();
2117 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2118 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2120 edge e;
2121 edge_iterator ei;
2123 FOR_EACH_EDGE (e, ei, bb->succs)
2124 if (e->insns.r)
2126 if (currently_expanding_to_rtl)
2127 rebuild_jump_labels_chain (e->insns.r);
2128 commit_one_edge_insertion (e);
2134 /* Print out RTL-specific basic block information (live information
2135 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2136 documented in dumpfile.h. */
2138 static void
2139 rtl_dump_bb (FILE *outf, basic_block bb, int indent, dump_flags_t flags)
2141 char *s_indent;
2143 s_indent = (char *) alloca ((size_t) indent + 1);
2144 memset (s_indent, ' ', (size_t) indent);
2145 s_indent[indent] = '\0';
2147 if (df && (flags & TDF_DETAILS))
2149 df_dump_top (bb, outf);
2150 putc ('\n', outf);
2153 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK
2154 && rtl_bb_info_initialized_p (bb))
2156 rtx_insn *last = BB_END (bb);
2157 if (last)
2158 last = NEXT_INSN (last);
2159 for (rtx_insn *insn = BB_HEAD (bb); insn != last; insn = NEXT_INSN (insn))
2161 if (flags & TDF_DETAILS)
2162 df_dump_insn_top (insn, outf);
2163 if (! (flags & TDF_SLIM))
2164 print_rtl_single (outf, insn);
2165 else
2166 dump_insn_slim (outf, insn);
2167 if (flags & TDF_DETAILS)
2168 df_dump_insn_bottom (insn, outf);
2172 if (df && (flags & TDF_DETAILS))
2174 df_dump_bottom (bb, outf);
2175 putc ('\n', outf);
2180 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2181 for the start of each basic block. FLAGS are the TDF_* masks documented
2182 in dumpfile.h. */
2184 void
2185 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, dump_flags_t flags)
2187 const rtx_insn *tmp_rtx;
2188 if (rtx_first == 0)
2189 fprintf (outf, "(nil)\n");
2190 else
2192 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2193 int max_uid = get_max_uid ();
2194 basic_block *start = XCNEWVEC (basic_block, max_uid);
2195 basic_block *end = XCNEWVEC (basic_block, max_uid);
2196 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2197 basic_block bb;
2199 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2200 insns, but the CFG is not maintained so the basic block info
2201 is not reliable. Therefore it's omitted from the dumps. */
2202 if (! (cfun->curr_properties & PROP_cfg))
2203 flags &= ~TDF_BLOCKS;
2205 if (df)
2206 df_dump_start (outf);
2208 if (cfun->curr_properties & PROP_cfg)
2210 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2212 rtx_insn *x;
2214 start[INSN_UID (BB_HEAD (bb))] = bb;
2215 end[INSN_UID (BB_END (bb))] = bb;
2216 if (flags & TDF_BLOCKS)
2218 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2220 enum bb_state state = IN_MULTIPLE_BB;
2222 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2223 state = IN_ONE_BB;
2224 in_bb_p[INSN_UID (x)] = state;
2226 if (x == BB_END (bb))
2227 break;
2233 for (tmp_rtx = rtx_first; tmp_rtx != NULL; tmp_rtx = NEXT_INSN (tmp_rtx))
2235 if (flags & TDF_BLOCKS)
2237 bb = start[INSN_UID (tmp_rtx)];
2238 if (bb != NULL)
2240 dump_bb_info (outf, bb, 0, dump_flags, true, false);
2241 if (df && (flags & TDF_DETAILS))
2242 df_dump_top (bb, outf);
2245 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2246 && !NOTE_P (tmp_rtx)
2247 && !BARRIER_P (tmp_rtx))
2248 fprintf (outf, ";; Insn is not within a basic block\n");
2249 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2250 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2253 if (flags & TDF_DETAILS)
2254 df_dump_insn_top (tmp_rtx, outf);
2255 if (! (flags & TDF_SLIM))
2256 print_rtl_single (outf, tmp_rtx);
2257 else
2258 dump_insn_slim (outf, tmp_rtx);
2259 if (flags & TDF_DETAILS)
2260 df_dump_insn_bottom (tmp_rtx, outf);
2262 bb = end[INSN_UID (tmp_rtx)];
2263 if (bb != NULL)
2265 if (flags & TDF_BLOCKS)
2267 dump_bb_info (outf, bb, 0, dump_flags, false, true);
2268 if (df && (flags & TDF_DETAILS))
2269 df_dump_bottom (bb, outf);
2270 putc ('\n', outf);
2272 /* Emit a hint if the fallthrough target of current basic block
2273 isn't the one placed right next. */
2274 else if (EDGE_COUNT (bb->succs) > 0)
2276 gcc_assert (BB_END (bb) == tmp_rtx);
2277 const rtx_insn *ninsn = NEXT_INSN (tmp_rtx);
2278 /* Bypass intervening deleted-insn notes and debug insns. */
2279 while (ninsn
2280 && !NONDEBUG_INSN_P (ninsn)
2281 && !start[INSN_UID (ninsn)])
2282 ninsn = NEXT_INSN (ninsn);
2283 edge e = find_fallthru_edge (bb->succs);
2284 if (e && ninsn)
2286 basic_block dest = e->dest;
2287 if (start[INSN_UID (ninsn)] != dest)
2288 fprintf (outf, "%s ; pc falls through to BB %d\n",
2289 print_rtx_head, dest->index);
2295 free (start);
2296 free (end);
2297 free (in_bb_p);
2301 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2303 void
2304 update_br_prob_note (basic_block bb)
2306 rtx note;
2307 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2308 if (!JUMP_P (BB_END (bb)) || !BRANCH_EDGE (bb)->probability.initialized_p ())
2310 if (note)
2312 rtx *note_link, this_rtx;
2314 note_link = &REG_NOTES (BB_END (bb));
2315 for (this_rtx = *note_link; this_rtx; this_rtx = XEXP (this_rtx, 1))
2316 if (this_rtx == note)
2318 *note_link = XEXP (this_rtx, 1);
2319 break;
2322 return;
2324 if (!note
2325 || XINT (note, 0) == BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ())
2326 return;
2327 XINT (note, 0) = BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ();
2330 /* Get the last insn associated with block BB (that includes barriers and
2331 tablejumps after BB). */
2332 rtx_insn *
2333 get_last_bb_insn (basic_block bb)
2335 rtx_jump_table_data *table;
2336 rtx_insn *tmp;
2337 rtx_insn *end = BB_END (bb);
2339 /* Include any jump table following the basic block. */
2340 if (tablejump_p (end, NULL, &table))
2341 end = table;
2343 /* Include any barriers that may follow the basic block. */
2344 tmp = next_nonnote_nondebug_insn_bb (end);
2345 while (tmp && BARRIER_P (tmp))
2347 end = tmp;
2348 tmp = next_nonnote_nondebug_insn_bb (end);
2351 return end;
2354 /* Add all BBs reachable from entry via hot paths into the SET. */
2356 void
2357 find_bbs_reachable_by_hot_paths (hash_set<basic_block> *set)
2359 auto_vec<basic_block, 64> worklist;
2361 set->add (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2362 worklist.safe_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
2364 while (worklist.length () > 0)
2366 basic_block bb = worklist.pop ();
2367 edge_iterator ei;
2368 edge e;
2370 FOR_EACH_EDGE (e, ei, bb->succs)
2371 if (BB_PARTITION (e->dest) != BB_COLD_PARTITION
2372 && !set->add (e->dest))
2373 worklist.safe_push (e->dest);
2377 /* Sanity check partition hotness to ensure that basic blocks in
2378   the cold partition don't dominate basic blocks in the hot partition.
2379 If FLAG_ONLY is true, report violations as errors. Otherwise
2380 re-mark the dominated blocks as cold, since this is run after
2381 cfg optimizations that may make hot blocks previously reached
2382 by both hot and cold blocks now only reachable along cold paths. */
2384 static auto_vec<basic_block>
2385 find_partition_fixes (bool flag_only)
2387 basic_block bb;
2388 auto_vec<basic_block> bbs_to_fix;
2389 hash_set<basic_block> set;
2391 /* Callers check this. */
2392 gcc_checking_assert (crtl->has_bb_partition);
2394 find_bbs_reachable_by_hot_paths (&set);
2396 FOR_EACH_BB_FN (bb, cfun)
2397 if (!set.contains (bb)
2398 && BB_PARTITION (bb) != BB_COLD_PARTITION)
2400 if (flag_only)
2401 error ("non-cold basic block %d reachable only "
2402 "by paths crossing the cold partition", bb->index);
2403 else
2404 BB_SET_PARTITION (bb, BB_COLD_PARTITION);
2405 bbs_to_fix.safe_push (bb);
2408 return bbs_to_fix;
2411 /* Perform cleanup on the hot/cold bb partitioning after optimization
2412 passes that modify the cfg. */
2414 void
2415 fixup_partitions (void)
2417 if (!crtl->has_bb_partition)
2418 return;
2420 /* Delete any blocks that became unreachable and weren't
2421 already cleaned up, for example during edge forwarding
2422 and convert_jumps_to_returns. This will expose more
2423 opportunities for fixing the partition boundaries here.
2424 Also, the calculation of the dominance graph during verification
2425 will assert if there are unreachable nodes. */
2426 delete_unreachable_blocks ();
2428 /* If there are partitions, do a sanity check on them: A basic block in
2429   a cold partition cannot dominate a basic block in a hot partition.
2430 Fixup any that now violate this requirement, as a result of edge
2431 forwarding and unreachable block deletion.  */
2432 auto_vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2434 /* Do the partition fixup after all necessary blocks have been converted to
2435 cold, so that we only update the region crossings the minimum number of
2436 places, which can require forcing edges to be non fallthru. */
2437 if (! bbs_to_fix.is_empty ())
2441 basic_block bb = bbs_to_fix.pop ();
2442 fixup_new_cold_bb (bb);
2444 while (! bbs_to_fix.is_empty ());
2446 /* Fix up hot cold block grouping if needed. */
2447 if (crtl->bb_reorder_complete && current_ir_type () == IR_RTL_CFGRTL)
2449 basic_block bb, first = NULL, second = NULL;
2450 int current_partition = BB_UNPARTITIONED;
2452 FOR_EACH_BB_FN (bb, cfun)
2454 if (current_partition != BB_UNPARTITIONED
2455 && BB_PARTITION (bb) != current_partition)
2457 if (first == NULL)
2458 first = bb;
2459 else if (second == NULL)
2460 second = bb;
2461 else
2463 /* If we switch partitions for the 3rd, 5th etc. time,
2464 move bbs first (inclusive) .. second (exclusive) right
2465 before bb. */
2466 basic_block prev_first = first->prev_bb;
2467 basic_block prev_second = second->prev_bb;
2468 basic_block prev_bb = bb->prev_bb;
2469 prev_first->next_bb = second;
2470 second->prev_bb = prev_first;
2471 prev_second->next_bb = bb;
2472 bb->prev_bb = prev_second;
2473 prev_bb->next_bb = first;
2474 first->prev_bb = prev_bb;
2475 rtx_insn *prev_first_insn = PREV_INSN (BB_HEAD (first));
2476 rtx_insn *prev_second_insn
2477 = PREV_INSN (BB_HEAD (second));
2478 rtx_insn *prev_bb_insn = PREV_INSN (BB_HEAD (bb));
2479 SET_NEXT_INSN (prev_first_insn) = BB_HEAD (second);
2480 SET_PREV_INSN (BB_HEAD (second)) = prev_first_insn;
2481 SET_NEXT_INSN (prev_second_insn) = BB_HEAD (bb);
2482 SET_PREV_INSN (BB_HEAD (bb)) = prev_second_insn;
2483 SET_NEXT_INSN (prev_bb_insn) = BB_HEAD (first);
2484 SET_PREV_INSN (BB_HEAD (first)) = prev_bb_insn;
2485 second = NULL;
2488 current_partition = BB_PARTITION (bb);
2490 gcc_assert (!second);
2495 /* Verify, in the basic block chain, that there is at most one switch
2496 between hot/cold partitions. This condition will not be true until
2497 after reorder_basic_blocks is called. */
2499 static int
2500 verify_hot_cold_block_grouping (void)
2502 basic_block bb;
2503 int err = 0;
2504 bool switched_sections = false;
2505 int current_partition = BB_UNPARTITIONED;
2507 /* Even after bb reordering is complete, we go into cfglayout mode
2508 again (in compgoto). Ensure we don't call this before going back
2509 into linearized RTL when any layout fixes would have been committed. */
2510 if (!crtl->bb_reorder_complete
2511 || current_ir_type () != IR_RTL_CFGRTL)
2512 return err;
2514 FOR_EACH_BB_FN (bb, cfun)
2516 if (current_partition != BB_UNPARTITIONED
2517 && BB_PARTITION (bb) != current_partition)
2519 if (switched_sections)
2521 error ("multiple hot/cold transitions found (bb %i)",
2522 bb->index);
2523 err = 1;
2525 else
2526 switched_sections = true;
2528 if (!crtl->has_bb_partition)
2529 error ("partition found but function partition flag not set");
2531 current_partition = BB_PARTITION (bb);
2534 return err;
2538 /* Perform several checks on the edges out of each block, such as
2539 the consistency of the branch probabilities, the correctness
2540 of hot/cold partition crossing edges, and the number of expected
2541 successor edges. Also verify that the dominance relationship
2542 between hot/cold blocks is sane. */
2544 static int
2545 rtl_verify_edges (void)
2547 int err = 0;
2548 basic_block bb;
2550 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2552 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2553 int n_eh = 0, n_abnormal = 0;
2554 edge e, fallthru = NULL;
2555 edge_iterator ei;
2556 rtx note;
2557 bool has_crossing_edge = false;
2559 if (JUMP_P (BB_END (bb))
2560 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2561 && EDGE_COUNT (bb->succs) >= 2
2562 && any_condjump_p (BB_END (bb)))
2564 if (!BRANCH_EDGE (bb)->probability.initialized_p ())
2566 if (profile_status_for_fn (cfun) != PROFILE_ABSENT)
2568 error ("verify_flow_info: "
2569 "REG_BR_PROB is set but cfg probability is not");
2570 err = 1;
2573 else if (XINT (note, 0)
2574 != BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ()
2575 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2577 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2578 XINT (note, 0),
2579 BRANCH_EDGE (bb)->probability.to_reg_br_prob_note ());
2580 err = 1;
2584 FOR_EACH_EDGE (e, ei, bb->succs)
2586 bool is_crossing;
2588 if (e->flags & EDGE_FALLTHRU)
2589 n_fallthru++, fallthru = e;
2591 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2592 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2593 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2594 has_crossing_edge |= is_crossing;
2595 if (e->flags & EDGE_CROSSING)
2597 if (!is_crossing)
2599 error ("EDGE_CROSSING incorrectly set across same section");
2600 err = 1;
2602 if (e->flags & EDGE_FALLTHRU)
2604 error ("fallthru edge crosses section boundary in bb %i",
2605 e->src->index);
2606 err = 1;
2608 if (e->flags & EDGE_EH)
2610 error ("EH edge crosses section boundary in bb %i",
2611 e->src->index);
2612 err = 1;
2614 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2616 error ("No region crossing jump at section boundary in bb %i",
2617 bb->index);
2618 err = 1;
2621 else if (is_crossing)
2623 error ("EDGE_CROSSING missing across section boundary");
2624 err = 1;
2627 if ((e->flags & ~(EDGE_DFS_BACK
2628 | EDGE_CAN_FALLTHRU
2629 | EDGE_IRREDUCIBLE_LOOP
2630 | EDGE_LOOP_EXIT
2631 | EDGE_CROSSING
2632 | EDGE_PRESERVE)) == 0)
2633 n_branch++;
2635 if (e->flags & EDGE_ABNORMAL_CALL)
2636 n_abnormal_call++;
2638 if (e->flags & EDGE_SIBCALL)
2639 n_sibcall++;
2641 if (e->flags & EDGE_EH)
2642 n_eh++;
2644 if (e->flags & EDGE_ABNORMAL)
2645 n_abnormal++;
2648 if (!has_crossing_edge
2649 && JUMP_P (BB_END (bb))
2650 && CROSSING_JUMP_P (BB_END (bb)))
2652 print_rtl_with_bb (stderr, get_insns (), TDF_BLOCKS | TDF_DETAILS);
2653 error ("Region crossing jump across same section in bb %i",
2654 bb->index);
2655 err = 1;
2658 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2660 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2661 err = 1;
2663 if (n_eh > 1)
2665 error ("too many exception handling edges in bb %i", bb->index);
2666 err = 1;
2668 if (n_branch
2669 && (!JUMP_P (BB_END (bb))
2670 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2671 || any_condjump_p (BB_END (bb))))))
2673 error ("too many outgoing branch edges from bb %i", bb->index);
2674 err = 1;
2676 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2678 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2679 err = 1;
2681 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2683 error ("wrong number of branch edges after unconditional jump"
2684 " in bb %i", bb->index);
2685 err = 1;
2687 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2688 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2690 error ("wrong amount of branch edges after conditional jump"
2691 " in bb %i", bb->index);
2692 err = 1;
2694 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2696 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2697 err = 1;
2699 if (n_sibcall && !CALL_P (BB_END (bb)))
2701 error ("sibcall edges for non-call insn in bb %i", bb->index);
2702 err = 1;
2704 if (n_abnormal > n_eh
2705 && !(CALL_P (BB_END (bb))
2706 && n_abnormal == n_abnormal_call + n_sibcall)
2707 && (!JUMP_P (BB_END (bb))
2708 || any_condjump_p (BB_END (bb))
2709 || any_uncondjump_p (BB_END (bb))))
2711 error ("abnormal edges for no purpose in bb %i", bb->index);
2712 err = 1;
2715 int has_eh = -1;
2716 FOR_EACH_EDGE (e, ei, bb->preds)
2718 if (has_eh == -1)
2719 has_eh = (e->flags & EDGE_EH);
2720 if ((e->flags & EDGE_EH) == has_eh)
2721 continue;
2722 error ("EH incoming edge mixed with non-EH incoming edges "
2723 "in bb %i", bb->index);
2724 err = 1;
2725 break;
2729 /* If there are partitions, do a sanity check on them: A basic block in
2730   a cold partition cannot dominate a basic block in a hot partition.  */
2731 if (crtl->has_bb_partition && !err
2732 && current_ir_type () == IR_RTL_CFGLAYOUT)
2734 auto_vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2735 err = !bbs_to_fix.is_empty ();
2738 /* Clean up. */
2739 return err;
2742 /* Checks on the instructions within blocks. Currently checks that each
2743 block starts with a basic block note, and that basic block notes and
2744 control flow jumps are not found in the middle of the block. */
2746 static int
2747 rtl_verify_bb_insns (void)
2749 rtx_insn *x;
2750 int err = 0;
2751 basic_block bb;
2753 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2755 /* Now check the header of basic
2756 block. It ought to contain optional CODE_LABEL followed
2757 by NOTE_BASIC_BLOCK. */
2758 x = BB_HEAD (bb);
2759 if (LABEL_P (x))
2761 if (BB_END (bb) == x)
2763 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2764 bb->index);
2765 err = 1;
2768 x = NEXT_INSN (x);
2771 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2773 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2774 bb->index);
2775 err = 1;
2778 if (BB_END (bb) == x)
2779 /* Do checks for empty blocks here. */
2781 else
2782 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2784 if (NOTE_INSN_BASIC_BLOCK_P (x))
2786 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2787 INSN_UID (x), bb->index);
2788 err = 1;
2791 if (x == BB_END (bb))
2792 break;
2794 if (control_flow_insn_p (x))
2796 error ("in basic block %d:", bb->index);
2797 fatal_insn ("flow control insn inside a basic block", x);
2802 /* Clean up. */
2803 return err;
2806 /* Verify that block pointers for instructions in basic blocks, headers and
2807 footers are set appropriately. */
2809 static int
2810 rtl_verify_bb_pointers (void)
2812 int err = 0;
2813 basic_block bb;
2815 /* Check the general integrity of the basic blocks. */
2816 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2818 rtx_insn *insn;
2820 if (!(bb->flags & BB_RTL))
2822 error ("BB_RTL flag not set for block %d", bb->index);
2823 err = 1;
2826 FOR_BB_INSNS (bb, insn)
2827 if (BLOCK_FOR_INSN (insn) != bb)
2829 error ("insn %d basic block pointer is %d, should be %d",
2830 INSN_UID (insn),
2831 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2832 bb->index);
2833 err = 1;
2836 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2837 if (!BARRIER_P (insn)
2838 && BLOCK_FOR_INSN (insn) != NULL)
2840 error ("insn %d in header of bb %d has non-NULL basic block",
2841 INSN_UID (insn), bb->index);
2842 err = 1;
2844 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2845 if (!BARRIER_P (insn)
2846 && BLOCK_FOR_INSN (insn) != NULL)
2848 error ("insn %d in footer of bb %d has non-NULL basic block",
2849 INSN_UID (insn), bb->index);
2850 err = 1;
2854 /* Clean up. */
2855 return err;
2858 /* Verify the CFG and RTL consistency common for both underlying RTL and
2859 cfglayout RTL.
2861 Currently it does following checks:
2863 - overlapping of basic blocks
2864 - insns with wrong BLOCK_FOR_INSN pointers
2865 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2866 - tails of basic blocks (ensure that boundary is necessary)
2867 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2868 and NOTE_INSN_BASIC_BLOCK
2869 - verify that no fall_thru edge crosses hot/cold partition boundaries
2870 - verify that there are no pending RTL branch predictions
2871 - verify that hot blocks are not dominated by cold blocks
2873 In future it can be extended check a lot of other stuff as well
2874 (reachability of basic blocks, life information, etc. etc.). */
2876 static int
2877 rtl_verify_flow_info_1 (void)
2879 int err = 0;
2881 err |= rtl_verify_bb_pointers ();
2883 err |= rtl_verify_bb_insns ();
2885 err |= rtl_verify_edges ();
2887 return err;
2890 /* Walk the instruction chain and verify that bb head/end pointers
2891 are correct, and that instructions are in exactly one bb and have
2892 correct block pointers. */
2894 static int
2895 rtl_verify_bb_insn_chain (void)
2897 basic_block bb;
2898 int err = 0;
2899 rtx_insn *x;
2900 rtx_insn *last_head = get_last_insn ();
2901 basic_block *bb_info;
2902 const int max_uid = get_max_uid ();
2904 bb_info = XCNEWVEC (basic_block, max_uid);
2906 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2908 rtx_insn *head = BB_HEAD (bb);
2909 rtx_insn *end = BB_END (bb);
2911 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2913 /* Verify the end of the basic block is in the INSN chain. */
2914 if (x == end)
2915 break;
2917 /* And that the code outside of basic blocks has NULL bb field. */
2918 if (!BARRIER_P (x)
2919 && BLOCK_FOR_INSN (x) != NULL)
2921 error ("insn %d outside of basic blocks has non-NULL bb field",
2922 INSN_UID (x));
2923 err = 1;
2927 if (!x)
2929 error ("end insn %d for block %d not found in the insn stream",
2930 INSN_UID (end), bb->index);
2931 err = 1;
2934 /* Work backwards from the end to the head of the basic block
2935 to verify the head is in the RTL chain. */
2936 for (; x != NULL_RTX; x = PREV_INSN (x))
2938 /* While walking over the insn chain, verify insns appear
2939 in only one basic block. */
2940 if (bb_info[INSN_UID (x)] != NULL)
2942 error ("insn %d is in multiple basic blocks (%d and %d)",
2943 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2944 err = 1;
2947 bb_info[INSN_UID (x)] = bb;
2949 if (x == head)
2950 break;
2952 if (!x)
2954 error ("head insn %d for block %d not found in the insn stream",
2955 INSN_UID (head), bb->index);
2956 err = 1;
2959 last_head = PREV_INSN (x);
2962 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2964 /* Check that the code before the first basic block has NULL
2965 bb field. */
2966 if (!BARRIER_P (x)
2967 && BLOCK_FOR_INSN (x) != NULL)
2969 error ("insn %d outside of basic blocks has non-NULL bb field",
2970 INSN_UID (x));
2971 err = 1;
2974 free (bb_info);
2976 return err;
2979 /* Verify that fallthru edges point to adjacent blocks in layout order and
2980 that barriers exist after non-fallthru blocks. */
2982 static int
2983 rtl_verify_fallthru (void)
2985 basic_block bb;
2986 int err = 0;
2988 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2990 edge e;
2992 e = find_fallthru_edge (bb->succs);
2993 if (!e)
2995 rtx_insn *insn;
2997 /* Ensure existence of barrier in BB with no fallthru edges. */
2998 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
3000 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
3002 error ("missing barrier after block %i", bb->index);
3003 err = 1;
3004 break;
3006 if (BARRIER_P (insn))
3007 break;
3010 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
3011 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
3013 rtx_insn *insn;
3015 if (e->src->next_bb != e->dest)
3017 error
3018 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
3019 e->src->index, e->dest->index);
3020 err = 1;
3022 else
3023 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
3024 insn = NEXT_INSN (insn))
3025 if (BARRIER_P (insn) || NONDEBUG_INSN_P (insn))
3027 error ("verify_flow_info: Incorrect fallthru %i->%i",
3028 e->src->index, e->dest->index);
3029 error ("wrong insn in the fallthru edge");
3030 debug_rtx (insn);
3031 err = 1;
3036 return err;
3039 /* Verify that blocks are laid out in consecutive order. While walking the
3040 instructions, verify that all expected instructions are inside the basic
3041 blocks, and that all returns are followed by barriers. */
3043 static int
3044 rtl_verify_bb_layout (void)
3046 basic_block bb;
3047 int err = 0;
3048 rtx_insn *x, *y;
3049 int num_bb_notes;
3050 rtx_insn * const rtx_first = get_insns ();
3051 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
3053 num_bb_notes = 0;
3055 for (x = rtx_first; x; x = NEXT_INSN (x))
3057 if (NOTE_INSN_BASIC_BLOCK_P (x))
3059 bb = NOTE_BASIC_BLOCK (x);
3061 num_bb_notes++;
3062 if (bb != last_bb_seen->next_bb)
3063 internal_error ("basic blocks not laid down consecutively");
3065 curr_bb = last_bb_seen = bb;
3068 if (!curr_bb)
3070 switch (GET_CODE (x))
3072 case BARRIER:
3073 case NOTE:
3074 break;
3076 case CODE_LABEL:
3077 /* An ADDR_VEC is placed outside any basic block. */
3078 if (NEXT_INSN (x)
3079 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
3080 x = NEXT_INSN (x);
3082 /* But in any case, non-deletable labels can appear anywhere. */
3083 break;
3085 default:
3086 fatal_insn ("insn outside basic block", x);
3090 if (JUMP_P (x)
3091 && returnjump_p (x) && ! condjump_p (x)
3092 && ! ((y = next_nonnote_nondebug_insn (x))
3093 && BARRIER_P (y)))
3094 fatal_insn ("return not followed by barrier", x);
3096 if (curr_bb && x == BB_END (curr_bb))
3097 curr_bb = NULL;
3100 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
3101 internal_error
3102 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
3103 num_bb_notes, n_basic_blocks_for_fn (cfun));
3105 return err;
3108 /* Verify the CFG and RTL consistency common for both underlying RTL and
3109 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
3111 Currently it does following checks:
3112 - all checks of rtl_verify_flow_info_1
3113 - test head/end pointers
3114 - check that blocks are laid out in consecutive order
3115 - check that all insns are in the basic blocks
3116 (except the switch handling code, barriers and notes)
3117 - check that all returns are followed by barriers
3118 - check that all fallthru edge points to the adjacent blocks
3119 - verify that there is a single hot/cold partition boundary after bbro */
3121 static int
3122 rtl_verify_flow_info (void)
3124 int err = 0;
3126 err |= rtl_verify_flow_info_1 ();
3128 err |= rtl_verify_bb_insn_chain ();
3130 err |= rtl_verify_fallthru ();
3132 err |= rtl_verify_bb_layout ();
3134 err |= verify_hot_cold_block_grouping ();
3136 return err;
3139 /* Assume that the preceding pass has possibly eliminated jump instructions
3140 or converted the unconditional jumps. Eliminate the edges from CFG.
3141 Return true if any edges are eliminated. */
3143 bool
3144 purge_dead_edges (basic_block bb)
3146 edge e;
3147 rtx_insn *insn = BB_END (bb);
3148 rtx note;
3149 bool purged = false;
3150 bool found;
3151 edge_iterator ei;
3153 if ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb))
3155 insn = PREV_INSN (insn);
3156 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3158 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3159 if (NONJUMP_INSN_P (insn)
3160 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3162 rtx eqnote;
3164 if (! may_trap_p (PATTERN (insn))
3165 || ((eqnote = find_reg_equal_equiv_note (insn))
3166 && ! may_trap_p (XEXP (eqnote, 0))))
3167 remove_note (insn, note);
3170 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3171 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3173 bool remove = false;
3175 /* There are three types of edges we need to handle correctly here: EH
3176 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3177 latter can appear when nonlocal gotos are used. */
3178 if (e->flags & EDGE_ABNORMAL_CALL)
3180 if (!CALL_P (insn))
3181 remove = true;
3182 else if (can_nonlocal_goto (insn))
3184 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3186 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3188 else
3189 remove = true;
3191 else if (e->flags & EDGE_EH)
3192 remove = !can_throw_internal (insn);
3194 if (remove)
3196 remove_edge (e);
3197 df_set_bb_dirty (bb);
3198 purged = true;
3200 else
3201 ei_next (&ei);
3204 if (JUMP_P (insn))
3206 rtx note;
3207 edge b,f;
3208 edge_iterator ei;
3210 /* We do care only about conditional jumps and simplejumps. */
3211 if (!any_condjump_p (insn)
3212 && !returnjump_p (insn)
3213 && !simplejump_p (insn))
3214 return purged;
3216 /* Branch probability/prediction notes are defined only for
3217 condjumps. We've possibly turned condjump into simplejump. */
3218 if (simplejump_p (insn))
3220 note = find_reg_note (insn, REG_BR_PROB, NULL);
3221 if (note)
3222 remove_note (insn, note);
3223 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3224 remove_note (insn, note);
3227 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3229 /* Avoid abnormal flags to leak from computed jumps turned
3230 into simplejumps. */
3232 e->flags &= ~EDGE_ABNORMAL;
3234 /* See if this edge is one we should keep. */
3235 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3236 /* A conditional jump can fall through into the next
3237 block, so we should keep the edge. */
3239 ei_next (&ei);
3240 continue;
3242 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3243 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3244 /* If the destination block is the target of the jump,
3245 keep the edge. */
3247 ei_next (&ei);
3248 continue;
3250 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3251 && returnjump_p (insn))
3252 /* If the destination block is the exit block, and this
3253 instruction is a return, then keep the edge. */
3255 ei_next (&ei);
3256 continue;
3258 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3259 /* Keep the edges that correspond to exceptions thrown by
3260 this instruction and rematerialize the EDGE_ABNORMAL
3261 flag we just cleared above. */
3263 e->flags |= EDGE_ABNORMAL;
3264 ei_next (&ei);
3265 continue;
3268 /* We do not need this edge. */
3269 df_set_bb_dirty (bb);
3270 purged = true;
3271 remove_edge (e);
3274 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3275 return purged;
3277 if (dump_file)
3278 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3280 if (!optimize)
3281 return purged;
3283 /* Redistribute probabilities. */
3284 if (single_succ_p (bb))
3286 single_succ_edge (bb)->probability = profile_probability::always ();
3288 else
3290 note = find_reg_note (insn, REG_BR_PROB, NULL);
3291 if (!note)
3292 return purged;
3294 b = BRANCH_EDGE (bb);
3295 f = FALLTHRU_EDGE (bb);
3296 b->probability = profile_probability::from_reg_br_prob_note
3297 (XINT (note, 0));
3298 f->probability = b->probability.invert ();
3301 return purged;
3303 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3305 /* First, there should not be any EH or ABCALL edges resulting
3306 from non-local gotos and the like. If there were, we shouldn't
3307 have created the sibcall in the first place. Second, there
3308 should of course never have been a fallthru edge. */
3309 gcc_assert (single_succ_p (bb));
3310 gcc_assert (single_succ_edge (bb)->flags
3311 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3313 return 0;
3316 /* If we don't see a jump insn, we don't know exactly why the block would
3317 have been broken at this point. Look for a simple, non-fallthru edge,
3318 as these are only created by conditional branches. If we find such an
3319 edge we know that there used to be a jump here and can then safely
3320 remove all non-fallthru edges. */
3321 found = false;
3322 FOR_EACH_EDGE (e, ei, bb->succs)
3323 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3325 found = true;
3326 break;
3329 if (!found)
3330 return purged;
3332 /* Remove all but the fake and fallthru edges. The fake edge may be
3333 the only successor for this block in the case of noreturn
3334 calls. */
3335 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3337 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3339 df_set_bb_dirty (bb);
3340 remove_edge (e);
3341 purged = true;
3343 else
3344 ei_next (&ei);
3347 gcc_assert (single_succ_p (bb));
3349 single_succ_edge (bb)->probability = profile_probability::always ();
3351 if (dump_file)
3352 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3353 bb->index);
3354 return purged;
3357 /* Search all basic blocks for potentially dead edges and purge them. Return
3358 true if some edge has been eliminated. */
3360 bool
3361 purge_all_dead_edges (void)
3363 int purged = false;
3364 basic_block bb;
3366 FOR_EACH_BB_FN (bb, cfun)
3368 bool purged_here = purge_dead_edges (bb);
3370 purged |= purged_here;
3373 return purged;
3376 /* This is used by a few passes that emit some instructions after abnormal
3377 calls, moving the basic block's end, while they in fact do want to emit
3378 them on the fallthru edge. Look for abnormal call edges, find backward
3379 the call in the block and insert the instructions on the edge instead.
3381 Similarly, handle instructions throwing exceptions internally.
3383 Return true when instructions have been found and inserted on edges. */
3385 bool
3386 fixup_abnormal_edges (void)
3388 bool inserted = false;
3389 basic_block bb;
3391 FOR_EACH_BB_FN (bb, cfun)
3393 edge e;
3394 edge_iterator ei;
3396 /* Look for cases we are interested in - calls or instructions causing
3397 exceptions. */
3398 FOR_EACH_EDGE (e, ei, bb->succs)
3399 if ((e->flags & EDGE_ABNORMAL_CALL)
3400 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3401 == (EDGE_ABNORMAL | EDGE_EH)))
3402 break;
3404 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3406 rtx_insn *insn;
3408 /* Get past the new insns generated. Allow notes, as the insns
3409 may be already deleted. */
3410 insn = BB_END (bb);
3411 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3412 && !can_throw_internal (insn)
3413 && insn != BB_HEAD (bb))
3414 insn = PREV_INSN (insn);
3416 if (CALL_P (insn) || can_throw_internal (insn))
3418 rtx_insn *stop, *next;
3420 e = find_fallthru_edge (bb->succs);
3422 stop = NEXT_INSN (BB_END (bb));
3423 BB_END (bb) = insn;
3425 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3427 next = NEXT_INSN (insn);
3428 if (INSN_P (insn))
3430 delete_insn (insn);
3432 /* Sometimes there's still the return value USE.
3433 If it's placed after a trapping call (i.e. that
3434 call is the last insn anyway), we have no fallthru
3435 edge. Simply delete this use and don't try to insert
3436 on the non-existent edge.
3437 Similarly, sometimes a call that can throw is
3438 followed in the source with __builtin_unreachable (),
3439 meaning that there is UB if the call returns rather
3440 than throws. If there weren't any instructions
3441 following such calls before, supposedly even the ones
3442 we've deleted aren't significant and can be
3443 removed. */
3444 if (e)
3446 /* We're not deleting it, we're moving it. */
3447 insn->set_undeleted ();
3448 SET_PREV_INSN (insn) = NULL_RTX;
3449 SET_NEXT_INSN (insn) = NULL_RTX;
3451 insert_insn_on_edge (insn, e);
3452 inserted = true;
3455 else if (!BARRIER_P (insn))
3456 set_block_for_insn (insn, NULL);
3460 /* It may be that we don't find any trapping insn. In this
3461 case we discovered quite late that the insn that had been
3462 marked as can_throw_internal in fact couldn't trap at all.
3463 So we should in fact delete the EH edges out of the block. */
3464 else
3465 purge_dead_edges (bb);
3469 return inserted;
3472 /* Delete the unconditional jump INSN and adjust the CFG correspondingly.
3473 Note that the INSN should be deleted *after* removing dead edges, so
3474 that the kept edge is the fallthrough edge for a (set (pc) (pc))
3475 but not for a (set (pc) (label_ref FOO)). */
3477 void
3478 update_cfg_for_uncondjump (rtx_insn *insn)
3480 basic_block bb = BLOCK_FOR_INSN (insn);
3481 gcc_assert (BB_END (bb) == insn);
3483 purge_dead_edges (bb);
3485 if (current_ir_type () != IR_RTL_CFGLAYOUT)
3487 if (!find_fallthru_edge (bb->succs))
3489 auto barrier = next_nonnote_nondebug_insn (insn);
3490 if (!barrier || !BARRIER_P (barrier))
3491 emit_barrier_after (insn);
3493 return;
3496 delete_insn (insn);
3497 if (EDGE_COUNT (bb->succs) == 1)
3499 rtx_insn *insn;
3501 single_succ_edge (bb)->flags |= EDGE_FALLTHRU;
3503 /* Remove barriers from the footer if there are any. */
3504 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
3505 if (BARRIER_P (insn))
3507 if (PREV_INSN (insn))
3508 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
3509 else
3510 BB_FOOTER (bb) = NEXT_INSN (insn);
3511 if (NEXT_INSN (insn))
3512 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
3514 else if (LABEL_P (insn))
3515 break;
3519 /* Cut the insns from FIRST to LAST out of the insns stream. */
3521 rtx_insn *
3522 unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3524 rtx_insn *prevfirst = PREV_INSN (first);
3525 rtx_insn *nextlast = NEXT_INSN (last);
3527 SET_PREV_INSN (first) = NULL;
3528 SET_NEXT_INSN (last) = NULL;
3529 if (prevfirst)
3530 SET_NEXT_INSN (prevfirst) = nextlast;
3531 if (nextlast)
3532 SET_PREV_INSN (nextlast) = prevfirst;
3533 else
3534 set_last_insn (prevfirst);
3535 if (!prevfirst)
3536 set_first_insn (nextlast);
3537 return first;
3540 /* Skip over inter-block insns occurring after BB which are typically
3541 associated with BB (e.g., barriers). If there are any such insns,
3542 we return the last one. Otherwise, we return the end of BB. */
3544 static rtx_insn *
3545 skip_insns_after_block (basic_block bb)
3547 rtx_insn *insn, *last_insn, *next_head, *prev;
3549 next_head = NULL;
3550 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3551 next_head = BB_HEAD (bb->next_bb);
3553 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3555 if (insn == next_head)
3556 break;
3558 switch (GET_CODE (insn))
3560 case BARRIER:
3561 last_insn = insn;
3562 continue;
3564 case NOTE:
3565 gcc_assert (NOTE_KIND (insn) != NOTE_INSN_BLOCK_END);
3566 continue;
3568 case CODE_LABEL:
3569 if (NEXT_INSN (insn)
3570 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3572 insn = NEXT_INSN (insn);
3573 last_insn = insn;
3574 continue;
3576 break;
3578 default:
3579 break;
3582 break;
3585 /* It is possible to hit contradictory sequence. For instance:
3587 jump_insn
3588 NOTE_INSN_BLOCK_BEG
3589 barrier
3591 Where barrier belongs to jump_insn, but the note does not. This can be
3592 created by removing the basic block originally following
3593 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3595 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3597 prev = PREV_INSN (insn);
3598 if (NOTE_P (insn))
3599 switch (NOTE_KIND (insn))
3601 case NOTE_INSN_BLOCK_END:
3602 gcc_unreachable ();
3603 break;
3604 case NOTE_INSN_DELETED:
3605 case NOTE_INSN_DELETED_LABEL:
3606 case NOTE_INSN_DELETED_DEBUG_LABEL:
3607 continue;
3608 default:
3609 reorder_insns (insn, insn, last_insn);
3613 return last_insn;
3616 /* Locate or create a label for a given basic block. */
3618 static rtx_insn *
3619 label_for_bb (basic_block bb)
3621 rtx_insn *label = BB_HEAD (bb);
3623 if (!LABEL_P (label))
3625 if (dump_file)
3626 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3628 label = block_label (bb);
3631 return label;
3634 /* Locate the effective beginning and end of the insn chain for each
3635 block, as defined by skip_insns_after_block above. */
3637 static void
3638 record_effective_endpoints (void)
3640 rtx_insn *next_insn;
3641 basic_block bb;
3642 rtx_insn *insn;
3644 for (insn = get_insns ();
3645 insn
3646 && NOTE_P (insn)
3647 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3648 insn = NEXT_INSN (insn))
3649 continue;
3650 /* No basic blocks at all? */
3651 gcc_assert (insn);
3653 if (PREV_INSN (insn))
3654 cfg_layout_function_header =
3655 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3656 else
3657 cfg_layout_function_header = NULL;
3659 next_insn = get_insns ();
3660 FOR_EACH_BB_FN (bb, cfun)
3662 rtx_insn *end;
3664 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3665 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3666 PREV_INSN (BB_HEAD (bb)));
3667 end = skip_insns_after_block (bb);
3668 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3669 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3670 next_insn = NEXT_INSN (BB_END (bb));
3673 cfg_layout_function_footer = next_insn;
3674 if (cfg_layout_function_footer)
3675 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3678 namespace {
3680 const pass_data pass_data_into_cfg_layout_mode =
3682 RTL_PASS, /* type */
3683 "into_cfglayout", /* name */
3684 OPTGROUP_NONE, /* optinfo_flags */
3685 TV_CFG, /* tv_id */
3686 0, /* properties_required */
3687 PROP_cfglayout, /* properties_provided */
3688 0, /* properties_destroyed */
3689 0, /* todo_flags_start */
3690 0, /* todo_flags_finish */
3693 class pass_into_cfg_layout_mode : public rtl_opt_pass
3695 public:
3696 pass_into_cfg_layout_mode (gcc::context *ctxt)
3697 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3700 /* opt_pass methods: */
3701 virtual unsigned int execute (function *)
3703 cfg_layout_initialize (0);
3704 return 0;
3707 }; // class pass_into_cfg_layout_mode
3709 } // anon namespace
3711 rtl_opt_pass *
3712 make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3714 return new pass_into_cfg_layout_mode (ctxt);
3717 namespace {
3719 const pass_data pass_data_outof_cfg_layout_mode =
3721 RTL_PASS, /* type */
3722 "outof_cfglayout", /* name */
3723 OPTGROUP_NONE, /* optinfo_flags */
3724 TV_CFG, /* tv_id */
3725 0, /* properties_required */
3726 0, /* properties_provided */
3727 PROP_cfglayout, /* properties_destroyed */
3728 0, /* todo_flags_start */
3729 0, /* todo_flags_finish */
3732 class pass_outof_cfg_layout_mode : public rtl_opt_pass
3734 public:
3735 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3736 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3739 /* opt_pass methods: */
3740 virtual unsigned int execute (function *);
3742 }; // class pass_outof_cfg_layout_mode
3744 unsigned int
3745 pass_outof_cfg_layout_mode::execute (function *fun)
3747 basic_block bb;
3749 FOR_EACH_BB_FN (bb, fun)
3750 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3751 bb->aux = bb->next_bb;
3753 cfg_layout_finalize ();
3755 return 0;
3758 } // anon namespace
3760 rtl_opt_pass *
3761 make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3763 return new pass_outof_cfg_layout_mode (ctxt);
3767 /* Link the basic blocks in the correct order, compacting the basic
3768 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3769 function also clears the basic block header and footer fields.
3771 This function is usually called after a pass (e.g. tracer) finishes
3772 some transformations while in cfglayout mode. The required sequence
3773 of the basic blocks is in a linked list along the bb->aux field.
3774 This functions re-links the basic block prev_bb and next_bb pointers
3775 accordingly, and it compacts and renumbers the blocks.
3777 FIXME: This currently works only for RTL, but the only RTL-specific
3778 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3779 to GIMPLE a long time ago, but it doesn't relink the basic block
3780 chain. It could do that (to give better initial RTL) if this function
3781 is made IR-agnostic (and moved to cfganal.cc or cfg.cc while at it). */
3783 void
3784 relink_block_chain (bool stay_in_cfglayout_mode)
3786 basic_block bb, prev_bb;
3787 int index;
3789 /* Maybe dump the re-ordered sequence. */
3790 if (dump_file)
3792 fprintf (dump_file, "Reordered sequence:\n");
3793 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3794 NUM_FIXED_BLOCKS;
3796 bb = (basic_block) bb->aux, index++)
3798 fprintf (dump_file, " %i ", index);
3799 if (get_bb_original (bb))
3800 fprintf (dump_file, "duplicate of %i\n",
3801 get_bb_original (bb)->index);
3802 else if (forwarder_block_p (bb)
3803 && !LABEL_P (BB_HEAD (bb)))
3804 fprintf (dump_file, "compensation\n");
3805 else
3806 fprintf (dump_file, "bb %i\n", bb->index);
3810 /* Now reorder the blocks. */
3811 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3812 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3813 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3815 bb->prev_bb = prev_bb;
3816 prev_bb->next_bb = bb;
3818 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3819 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3821 /* Then, clean up the aux fields. */
3822 FOR_ALL_BB_FN (bb, cfun)
3824 bb->aux = NULL;
3825 if (!stay_in_cfglayout_mode)
3826 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3829 /* Maybe reset the original copy tables, they are not valid anymore
3830 when we renumber the basic blocks in compact_blocks. If we are
3831 are going out of cfglayout mode, don't re-allocate the tables. */
3832 if (original_copy_tables_initialized_p ())
3833 free_original_copy_tables ();
3834 if (stay_in_cfglayout_mode)
3835 initialize_original_copy_tables ();
3837 /* Finally, put basic_block_info in the new order. */
3838 compact_blocks ();
3842 /* Given a reorder chain, rearrange the code to match. */
3844 static void
3845 fixup_reorder_chain (void)
3847 basic_block bb;
3848 rtx_insn *insn = NULL;
3850 if (cfg_layout_function_header)
3852 set_first_insn (cfg_layout_function_header);
3853 insn = cfg_layout_function_header;
3854 while (NEXT_INSN (insn))
3855 insn = NEXT_INSN (insn);
3858 /* First do the bulk reordering -- rechain the blocks without regard to
3859 the needed changes to jumps and labels. */
3861 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3862 bb->aux)
3864 if (BB_HEADER (bb))
3866 if (insn)
3867 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3868 else
3869 set_first_insn (BB_HEADER (bb));
3870 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3871 insn = BB_HEADER (bb);
3872 while (NEXT_INSN (insn))
3873 insn = NEXT_INSN (insn);
3875 if (insn)
3876 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3877 else
3878 set_first_insn (BB_HEAD (bb));
3879 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3880 insn = BB_END (bb);
3881 if (BB_FOOTER (bb))
3883 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3884 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3885 while (NEXT_INSN (insn))
3886 insn = NEXT_INSN (insn);
3890 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3891 if (cfg_layout_function_footer)
3892 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3894 while (NEXT_INSN (insn))
3895 insn = NEXT_INSN (insn);
3897 set_last_insn (insn);
3898 if (flag_checking)
3899 verify_insn_chain ();
3901 /* Now add jumps and labels as needed to match the blocks new
3902 outgoing edges. */
3904 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3905 bb->aux)
3907 edge e_fall, e_taken, e;
3908 rtx_insn *bb_end_insn;
3909 rtx ret_label = NULL_RTX;
3910 basic_block nb;
3911 edge_iterator ei;
3913 if (EDGE_COUNT (bb->succs) == 0)
3914 continue;
3916 /* Find the old fallthru edge, and another non-EH edge for
3917 a taken jump. */
3918 e_taken = e_fall = NULL;
3920 FOR_EACH_EDGE (e, ei, bb->succs)
3921 if (e->flags & EDGE_FALLTHRU)
3922 e_fall = e;
3923 else if (! (e->flags & EDGE_EH))
3924 e_taken = e;
3926 bb_end_insn = BB_END (bb);
3927 if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
3929 ret_label = JUMP_LABEL (bb_end_jump);
3930 if (any_condjump_p (bb_end_jump))
3932 /* This might happen if the conditional jump has side
3933 effects and could therefore not be optimized away.
3934 Make the basic block to end with a barrier in order
3935 to prevent rtl_verify_flow_info from complaining. */
3936 if (!e_fall)
3938 gcc_assert (!onlyjump_p (bb_end_jump)
3939 || returnjump_p (bb_end_jump)
3940 || (e_taken->flags & EDGE_CROSSING));
3941 emit_barrier_after (bb_end_jump);
3942 continue;
3945 /* If the old fallthru is still next, nothing to do. */
3946 if (bb->aux == e_fall->dest
3947 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3948 continue;
3950 /* The degenerated case of conditional jump jumping to the next
3951 instruction can happen for jumps with side effects. We need
3952 to construct a forwarder block and this will be done just
3953 fine by force_nonfallthru below. */
3954 if (!e_taken)
3957 /* There is another special case: if *neither* block is next,
3958 such as happens at the very end of a function, then we'll
3959 need to add a new unconditional jump. Choose the taken
3960 edge based on known or assumed probability. */
3961 else if (bb->aux != e_taken->dest)
3963 rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
3965 if (note
3966 && profile_probability::from_reg_br_prob_note
3967 (XINT (note, 0)) < profile_probability::even ()
3968 && invert_jump (bb_end_jump,
3969 (e_fall->dest
3970 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3971 ? NULL_RTX
3972 : label_for_bb (e_fall->dest)), 0))
3974 e_fall->flags &= ~EDGE_FALLTHRU;
3975 gcc_checking_assert (could_fall_through
3976 (e_taken->src, e_taken->dest));
3977 e_taken->flags |= EDGE_FALLTHRU;
3978 update_br_prob_note (bb);
3979 e = e_fall, e_fall = e_taken, e_taken = e;
3983 /* If the "jumping" edge is a crossing edge, and the fall
3984 through edge is non-crossing, leave things as they are. */
3985 else if ((e_taken->flags & EDGE_CROSSING)
3986 && !(e_fall->flags & EDGE_CROSSING))
3987 continue;
3989 /* Otherwise we can try to invert the jump. This will
3990 basically never fail, however, keep up the pretense. */
3991 else if (invert_jump (bb_end_jump,
3992 (e_fall->dest
3993 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3994 ? NULL_RTX
3995 : label_for_bb (e_fall->dest)), 0))
3997 e_fall->flags &= ~EDGE_FALLTHRU;
3998 gcc_checking_assert (could_fall_through
3999 (e_taken->src, e_taken->dest));
4000 e_taken->flags |= EDGE_FALLTHRU;
4001 update_br_prob_note (bb);
4002 if (LABEL_NUSES (ret_label) == 0
4003 && single_pred_p (e_taken->dest))
4004 delete_insn (as_a<rtx_insn *> (ret_label));
4005 continue;
4008 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
4010 /* If the old fallthru is still next or if
4011 asm goto doesn't have a fallthru (e.g. when followed by
4012 __builtin_unreachable ()), nothing to do. */
4013 if (! e_fall
4014 || bb->aux == e_fall->dest
4015 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4016 continue;
4018 /* Otherwise we'll have to use the fallthru fixup below. */
4020 else
4022 /* Otherwise we have some return, switch or computed
4023 jump. In the 99% case, there should not have been a
4024 fallthru edge. */
4025 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
4026 continue;
4029 else
4031 /* No fallthru implies a noreturn function with EH edges, or
4032 something similarly bizarre. In any case, we don't need to
4033 do anything. */
4034 if (! e_fall)
4035 continue;
4037 /* If the fallthru block is still next, nothing to do. */
4038 if (bb->aux == e_fall->dest)
4039 continue;
4041 /* A fallthru to exit block. */
4042 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4043 continue;
4046 /* We got here if we need to add a new jump insn.
4047 Note force_nonfallthru can delete E_FALL and thus we have to
4048 save E_FALL->src prior to the call to force_nonfallthru. */
4049 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
4050 if (nb)
4052 nb->aux = bb->aux;
4053 bb->aux = nb;
4054 /* Don't process this new block. */
4055 bb = nb;
4059 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
4061 /* Annoying special case - jump around dead jumptables left in the code. */
4062 FOR_EACH_BB_FN (bb, cfun)
4064 edge e = find_fallthru_edge (bb->succs);
4066 if (e && !can_fallthru (e->src, e->dest))
4067 force_nonfallthru (e);
4070 /* Ensure goto_locus from edges has some instructions with that locus in RTL
4071 when not optimizing. */
4072 if (!optimize && !DECL_IGNORED_P (current_function_decl))
4073 FOR_EACH_BB_FN (bb, cfun)
4075 edge e;
4076 edge_iterator ei;
4078 FOR_EACH_EDGE (e, ei, bb->succs)
4079 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
4080 && !(e->flags & EDGE_ABNORMAL))
4082 edge e2;
4083 edge_iterator ei2;
4084 basic_block dest, nb;
4085 rtx_insn *end;
4087 insn = BB_END (e->src);
4088 end = PREV_INSN (BB_HEAD (e->src));
4089 while (insn != end
4090 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
4091 insn = PREV_INSN (insn);
4092 if (insn != end
4093 && loc_equal (INSN_LOCATION (insn), e->goto_locus))
4094 continue;
4095 if (simplejump_p (BB_END (e->src))
4096 && !INSN_HAS_LOCATION (BB_END (e->src)))
4098 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
4099 continue;
4101 dest = e->dest;
4102 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4104 /* Non-fallthru edges to the exit block cannot be split. */
4105 if (!(e->flags & EDGE_FALLTHRU))
4106 continue;
4108 else
4110 insn = BB_HEAD (dest);
4111 end = NEXT_INSN (BB_END (dest));
4112 while (insn != end && !NONDEBUG_INSN_P (insn))
4113 insn = NEXT_INSN (insn);
4114 if (insn != end && INSN_HAS_LOCATION (insn)
4115 && loc_equal (INSN_LOCATION (insn), e->goto_locus))
4116 continue;
4118 nb = split_edge (e);
4119 if (!INSN_P (BB_END (nb)))
4120 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
4121 nb);
4122 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
4124 /* If there are other incoming edges to the destination block
4125 with the same goto locus, redirect them to the new block as
4126 well, this can prevent other such blocks from being created
4127 in subsequent iterations of the loop. */
4128 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
4129 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
4130 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
4131 && e->goto_locus == e2->goto_locus)
4132 redirect_edge_and_branch (e2, nb);
4133 else
4134 ei_next (&ei2);
4139 /* Perform sanity checks on the insn chain.
4140 1. Check that next/prev pointers are consistent in both the forward and
4141 reverse direction.
4142 2. Count insns in chain, going both directions, and check if equal.
4143 3. Check that get_last_insn () returns the actual end of chain. */
4145 DEBUG_FUNCTION void
4146 verify_insn_chain (void)
4148 rtx_insn *x, *prevx, *nextx;
4149 int insn_cnt1, insn_cnt2;
4151 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
4152 x != 0;
4153 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
4154 gcc_assert (PREV_INSN (x) == prevx);
4156 gcc_assert (prevx == get_last_insn ());
4158 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
4159 x != 0;
4160 nextx = x, insn_cnt2++, x = PREV_INSN (x))
4161 gcc_assert (NEXT_INSN (x) == nextx);
4163 gcc_assert (insn_cnt1 == insn_cnt2);
4166 /* If we have assembler epilogues, the block falling through to exit must
4167 be the last one in the reordered chain when we reach final. Ensure
4168 that this condition is met. */
4169 static void
4170 fixup_fallthru_exit_predecessor (void)
4172 edge e;
4173 basic_block bb = NULL;
4175 /* This transformation is not valid before reload, because we might
4176 separate a call from the instruction that copies the return
4177 value. */
4178 gcc_assert (reload_completed);
4180 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4181 if (e)
4182 bb = e->src;
4184 if (bb && bb->aux)
4186 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4188 /* If the very first block is the one with the fall-through exit
4189 edge, we have to split that block. */
4190 if (c == bb)
4192 bb = split_block_after_labels (bb)->dest;
4193 bb->aux = c->aux;
4194 c->aux = bb;
4195 BB_FOOTER (bb) = BB_FOOTER (c);
4196 BB_FOOTER (c) = NULL;
4199 while (c->aux != bb)
4200 c = (basic_block) c->aux;
4202 c->aux = bb->aux;
4203 while (c->aux)
4204 c = (basic_block) c->aux;
4206 c->aux = bb;
4207 bb->aux = NULL;
4211 /* In case there are more than one fallthru predecessors of exit, force that
4212 there is only one. */
4214 static void
4215 force_one_exit_fallthru (void)
4217 edge e, predecessor = NULL;
4218 bool more = false;
4219 edge_iterator ei;
4220 basic_block forwarder, bb;
4222 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4223 if (e->flags & EDGE_FALLTHRU)
4225 if (predecessor == NULL)
4226 predecessor = e;
4227 else
4229 more = true;
4230 break;
4234 if (!more)
4235 return;
4237 /* Exit has several fallthru predecessors. Create a forwarder block for
4238 them. */
4239 forwarder = split_edge (predecessor);
4240 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4241 (e = ei_safe_edge (ei)); )
4243 if (e->src == forwarder
4244 || !(e->flags & EDGE_FALLTHRU))
4245 ei_next (&ei);
4246 else
4247 redirect_edge_and_branch_force (e, forwarder);
4250 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4251 exit block. */
4252 FOR_EACH_BB_FN (bb, cfun)
4254 if (bb->aux == NULL && bb != forwarder)
4256 bb->aux = forwarder;
4257 break;
4262 /* Return true in case it is possible to duplicate the basic block BB. */
4264 static bool
4265 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4267 /* Do not attempt to duplicate tablejumps, as we need to unshare
4268 the dispatch table. This is difficult to do, as the instructions
4269 computing jump destination may be hoisted outside the basic block. */
4270 if (tablejump_p (BB_END (bb), NULL, NULL))
4271 return false;
4273 /* Do not duplicate blocks containing insns that can't be copied. */
4274 if (targetm.cannot_copy_insn_p)
4276 rtx_insn *insn = BB_HEAD (bb);
4277 while (1)
4279 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4280 return false;
4281 if (insn == BB_END (bb))
4282 break;
4283 insn = NEXT_INSN (insn);
4287 return true;
4290 rtx_insn *
4291 duplicate_insn_chain (rtx_insn *from, rtx_insn *to,
4292 class loop *loop, copy_bb_data *id)
4294 rtx_insn *insn, *next, *copy;
4295 rtx_note *last;
4297 /* Avoid updating of boundaries of previous basic block. The
4298 note will get removed from insn stream in fixup. */
4299 last = emit_note (NOTE_INSN_DELETED);
4301 /* Create copy at the end of INSN chain. The chain will
4302 be reordered later. */
4303 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4305 switch (GET_CODE (insn))
4307 case DEBUG_INSN:
4308 /* Don't duplicate label debug insns. */
4309 if (DEBUG_BIND_INSN_P (insn)
4310 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4311 break;
4312 /* FALLTHRU */
4313 case INSN:
4314 case CALL_INSN:
4315 case JUMP_INSN:
4316 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4317 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4318 && ANY_RETURN_P (JUMP_LABEL (insn)))
4319 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4320 maybe_copy_prologue_epilogue_insn (insn, copy);
4321 /* If requested remap dependence info of cliques brought in
4322 via inlining. */
4323 if (id)
4325 subrtx_iterator::array_type array;
4326 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), ALL)
4327 if (MEM_P (*iter) && MEM_EXPR (*iter))
4329 tree op = MEM_EXPR (*iter);
4330 if (TREE_CODE (op) == WITH_SIZE_EXPR)
4331 op = TREE_OPERAND (op, 0);
4332 while (handled_component_p (op))
4333 op = TREE_OPERAND (op, 0);
4334 if ((TREE_CODE (op) == MEM_REF
4335 || TREE_CODE (op) == TARGET_MEM_REF)
4336 && MR_DEPENDENCE_CLIQUE (op) > 1
4337 && (!loop
4338 || (MR_DEPENDENCE_CLIQUE (op)
4339 != loop->owned_clique)))
4341 if (!id->dependence_map)
4342 id->dependence_map = new hash_map<dependence_hash,
4343 unsigned short>;
4344 bool existed;
4345 unsigned short &newc = id->dependence_map->get_or_insert
4346 (MR_DEPENDENCE_CLIQUE (op), &existed);
4347 if (!existed)
4349 gcc_assert
4350 (MR_DEPENDENCE_CLIQUE (op) <= cfun->last_clique);
4351 newc = ++cfun->last_clique;
4353 /* We cannot adjust MR_DEPENDENCE_CLIQUE in-place
4354 since MEM_EXPR is shared so make a copy and
4355 walk to the subtree again. */
4356 tree new_expr = unshare_expr (MEM_EXPR (*iter));
4357 if (TREE_CODE (new_expr) == WITH_SIZE_EXPR)
4358 new_expr = TREE_OPERAND (new_expr, 0);
4359 while (handled_component_p (new_expr))
4360 new_expr = TREE_OPERAND (new_expr, 0);
4361 MR_DEPENDENCE_CLIQUE (new_expr) = newc;
4362 set_mem_expr (const_cast <rtx> (*iter), new_expr);
4366 break;
4368 case JUMP_TABLE_DATA:
4369 /* Avoid copying of dispatch tables. We never duplicate
4370 tablejumps, so this can hit only in case the table got
4371 moved far from original jump.
4372 Avoid copying following barrier as well if any
4373 (and debug insns in between). */
4374 for (next = NEXT_INSN (insn);
4375 next != NEXT_INSN (to);
4376 next = NEXT_INSN (next))
4377 if (!DEBUG_INSN_P (next))
4378 break;
4379 if (next != NEXT_INSN (to) && BARRIER_P (next))
4380 insn = next;
4381 break;
4383 case CODE_LABEL:
4384 break;
4386 case BARRIER:
4387 emit_barrier ();
4388 break;
4390 case NOTE:
4391 switch (NOTE_KIND (insn))
4393 /* In case prologue is empty and function contain label
4394 in first BB, we may want to copy the block. */
4395 case NOTE_INSN_PROLOGUE_END:
4397 case NOTE_INSN_DELETED:
4398 case NOTE_INSN_DELETED_LABEL:
4399 case NOTE_INSN_DELETED_DEBUG_LABEL:
4400 /* No problem to strip these. */
4401 case NOTE_INSN_FUNCTION_BEG:
4402 /* There is always just single entry to function. */
4403 case NOTE_INSN_BASIC_BLOCK:
4404 /* We should only switch text sections once. */
4405 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4406 break;
4408 case NOTE_INSN_EPILOGUE_BEG:
4409 case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4410 emit_note_copy (as_a <rtx_note *> (insn));
4411 break;
4413 default:
4414 /* All other notes should have already been eliminated. */
4415 gcc_unreachable ();
4417 break;
4418 default:
4419 gcc_unreachable ();
4422 insn = NEXT_INSN (last);
4423 delete_insn (last);
4424 return insn;
4427 /* Create a duplicate of the basic block BB. */
4429 static basic_block
4430 cfg_layout_duplicate_bb (basic_block bb, copy_bb_data *id)
4432 rtx_insn *insn;
4433 basic_block new_bb;
4435 class loop *loop = (id && current_loops) ? bb->loop_father : NULL;
4437 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb), loop, id);
4438 new_bb = create_basic_block (insn,
4439 insn ? get_last_insn () : NULL,
4440 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4442 BB_COPY_PARTITION (new_bb, bb);
4443 if (BB_HEADER (bb))
4445 insn = BB_HEADER (bb);
4446 while (NEXT_INSN (insn))
4447 insn = NEXT_INSN (insn);
4448 insn = duplicate_insn_chain (BB_HEADER (bb), insn, loop, id);
4449 if (insn)
4450 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4453 if (BB_FOOTER (bb))
4455 insn = BB_FOOTER (bb);
4456 while (NEXT_INSN (insn))
4457 insn = NEXT_INSN (insn);
4458 insn = duplicate_insn_chain (BB_FOOTER (bb), insn, loop, id);
4459 if (insn)
4460 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4463 return new_bb;
4467 /* Main entry point to this module - initialize the datastructures for
4468 CFG layout changes. It keeps LOOPS up-to-date if not null.
4470 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4472 void
4473 cfg_layout_initialize (int flags)
4475 rtx_insn_list *x;
4476 basic_block bb;
4478 /* Once bb partitioning is complete, cfg layout mode should not be
4479 re-entered. Entering cfg layout mode may require fixups. As an
4480 example, if edge forwarding performed when optimizing the cfg
4481 layout required moving a block from the hot to the cold
4482 section. This would create an illegal partitioning unless some
4483 manual fixup was performed. */
4484 gcc_assert (!crtl->bb_reorder_complete || !crtl->has_bb_partition);
4486 initialize_original_copy_tables ();
4488 cfg_layout_rtl_register_cfg_hooks ();
4490 record_effective_endpoints ();
4492 /* Make sure that the targets of non local gotos are marked. */
4493 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4495 bb = BLOCK_FOR_INSN (x->insn ());
4496 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4499 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4502 /* Splits superblocks. */
4503 void
4504 break_superblocks (void)
4506 bool need = false;
4507 basic_block bb;
4509 auto_sbitmap superblocks (last_basic_block_for_fn (cfun));
4510 bitmap_clear (superblocks);
4512 FOR_EACH_BB_FN (bb, cfun)
4513 if (bb->flags & BB_SUPERBLOCK)
4515 bb->flags &= ~BB_SUPERBLOCK;
4516 bitmap_set_bit (superblocks, bb->index);
4517 need = true;
4520 if (need)
4522 rebuild_jump_labels (get_insns ());
4523 find_many_sub_basic_blocks (superblocks);
4527 /* Finalize the changes: reorder insn list according to the sequence specified
4528 by aux pointers, enter compensation code, rebuild scope forest. */
4530 void
4531 cfg_layout_finalize (void)
4533 free_dominance_info (CDI_DOMINATORS);
4534 force_one_exit_fallthru ();
4535 rtl_register_cfg_hooks ();
4536 if (reload_completed && !targetm.have_epilogue ())
4537 fixup_fallthru_exit_predecessor ();
4538 fixup_reorder_chain ();
4540 rebuild_jump_labels (get_insns ());
4541 delete_dead_jumptables ();
4543 if (flag_checking)
4544 verify_insn_chain ();
4545 checking_verify_flow_info ();
4549 /* Same as split_block but update cfg_layout structures. */
4551 static basic_block
4552 cfg_layout_split_block (basic_block bb, void *insnp)
4554 rtx insn = (rtx) insnp;
4555 basic_block new_bb = rtl_split_block (bb, insn);
4557 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4558 BB_FOOTER (bb) = NULL;
4560 return new_bb;
4563 /* Redirect Edge to DEST. */
4564 static edge
4565 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4567 basic_block src = e->src;
4568 edge ret;
4570 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4571 return NULL;
4573 if (e->dest == dest)
4574 return e;
4576 if (e->flags & EDGE_CROSSING
4577 && BB_PARTITION (e->src) == BB_PARTITION (dest)
4578 && simplejump_p (BB_END (src)))
4580 if (dump_file)
4581 fprintf (dump_file,
4582 "Removing crossing jump while redirecting edge form %i to %i\n",
4583 e->src->index, dest->index);
4584 delete_insn (BB_END (src));
4585 remove_barriers_from_footer (src);
4586 e->flags |= EDGE_FALLTHRU;
4589 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4590 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4592 df_set_bb_dirty (src);
4593 return ret;
4596 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4597 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4599 if (dump_file)
4600 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4601 e->src->index, dest->index);
4603 df_set_bb_dirty (e->src);
4604 redirect_edge_succ (e, dest);
4605 return e;
4608 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4609 in the case the basic block appears to be in sequence. Avoid this
4610 transformation. */
4612 if (e->flags & EDGE_FALLTHRU)
4614 /* Redirect any branch edges unified with the fallthru one. */
4615 if (JUMP_P (BB_END (src))
4616 && label_is_jump_target_p (BB_HEAD (e->dest),
4617 BB_END (src)))
4619 edge redirected;
4621 if (dump_file)
4622 fprintf (dump_file, "Fallthru edge unified with branch "
4623 "%i->%i redirected to %i\n",
4624 e->src->index, e->dest->index, dest->index);
4625 e->flags &= ~EDGE_FALLTHRU;
4626 redirected = redirect_branch_edge (e, dest);
4627 gcc_assert (redirected);
4628 redirected->flags |= EDGE_FALLTHRU;
4629 df_set_bb_dirty (redirected->src);
4630 return redirected;
4632 /* In case we are redirecting fallthru edge to the branch edge
4633 of conditional jump, remove it. */
4634 if (EDGE_COUNT (src->succs) == 2)
4636 /* Find the edge that is different from E. */
4637 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4639 if (s->dest == dest
4640 && any_condjump_p (BB_END (src))
4641 && onlyjump_p (BB_END (src)))
4642 delete_insn (BB_END (src));
4644 if (dump_file)
4645 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4646 e->src->index, e->dest->index, dest->index);
4647 ret = redirect_edge_succ_nodup (e, dest);
4649 else
4650 ret = redirect_branch_edge (e, dest);
4652 if (!ret)
4653 return NULL;
4655 fixup_partition_crossing (ret);
4656 /* We don't want simplejumps in the insn stream during cfglayout. */
4657 gcc_assert (!simplejump_p (BB_END (src)) || CROSSING_JUMP_P (BB_END (src)));
4659 df_set_bb_dirty (src);
4660 return ret;
4663 /* Simple wrapper as we always can redirect fallthru edges. */
4664 static basic_block
4665 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4667 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4669 gcc_assert (redirected);
4670 return NULL;
4673 /* Same as delete_basic_block but update cfg_layout structures. */
4675 static void
4676 cfg_layout_delete_block (basic_block bb)
4678 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4679 rtx_insn **to;
4681 if (BB_HEADER (bb))
4683 next = BB_HEAD (bb);
4684 if (prev)
4685 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4686 else
4687 set_first_insn (BB_HEADER (bb));
4688 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4689 insn = BB_HEADER (bb);
4690 while (NEXT_INSN (insn))
4691 insn = NEXT_INSN (insn);
4692 SET_NEXT_INSN (insn) = next;
4693 SET_PREV_INSN (next) = insn;
4695 next = NEXT_INSN (BB_END (bb));
4696 if (BB_FOOTER (bb))
4698 insn = BB_FOOTER (bb);
4699 while (insn)
4701 if (BARRIER_P (insn))
4703 if (PREV_INSN (insn))
4704 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4705 else
4706 BB_FOOTER (bb) = NEXT_INSN (insn);
4707 if (NEXT_INSN (insn))
4708 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4710 if (LABEL_P (insn))
4711 break;
4712 insn = NEXT_INSN (insn);
4714 if (BB_FOOTER (bb))
4716 insn = BB_END (bb);
4717 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4718 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4719 while (NEXT_INSN (insn))
4720 insn = NEXT_INSN (insn);
4721 SET_NEXT_INSN (insn) = next;
4722 if (next)
4723 SET_PREV_INSN (next) = insn;
4724 else
4725 set_last_insn (insn);
4728 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4729 to = &BB_HEADER (bb->next_bb);
4730 else
4731 to = &cfg_layout_function_footer;
4733 rtl_delete_block (bb);
4735 if (prev)
4736 prev = NEXT_INSN (prev);
4737 else
4738 prev = get_insns ();
4739 if (next)
4740 next = PREV_INSN (next);
4741 else
4742 next = get_last_insn ();
4744 if (next && NEXT_INSN (next) != prev)
4746 remaints = unlink_insn_chain (prev, next);
4747 insn = remaints;
4748 while (NEXT_INSN (insn))
4749 insn = NEXT_INSN (insn);
4750 SET_NEXT_INSN (insn) = *to;
4751 if (*to)
4752 SET_PREV_INSN (*to) = insn;
4753 *to = remaints;
4757 /* Return true when blocks A and B can be safely merged. */
4759 static bool
4760 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4762 /* If we are partitioning hot/cold basic blocks, we don't want to
4763 mess up unconditional or indirect jumps that cross between hot
4764 and cold sections.
4766 Basic block partitioning may result in some jumps that appear to
4767 be optimizable (or blocks that appear to be mergeable), but which really
4768 must be left untouched (they are required to make it safely across
4769 partition boundaries). See the comments at the top of
4770 bb-reorder.cc:partition_hot_cold_basic_blocks for complete details. */
4772 if (BB_PARTITION (a) != BB_PARTITION (b))
4773 return false;
4775 /* Protect the loop latches. */
4776 if (current_loops && b->loop_father->latch == b)
4777 return false;
4779 /* If we would end up moving B's instructions, make sure it doesn't fall
4780 through into the exit block, since we cannot recover from a fallthrough
4781 edge into the exit block occurring in the middle of a function. */
4782 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4784 edge e = find_fallthru_edge (b->succs);
4785 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4786 return false;
4789 /* There must be exactly one edge in between the blocks. */
4790 return (single_succ_p (a)
4791 && single_succ (a) == b
4792 && single_pred_p (b) == 1
4793 && a != b
4794 /* Must be simple edge. */
4795 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4796 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4797 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4798 /* If the jump insn has side effects, we can't kill the edge.
4799 When not optimizing, try_redirect_by_replacing_jump will
4800 not allow us to redirect an edge by replacing a table jump. */
4801 && (!JUMP_P (BB_END (a))
4802 || ((!optimize || reload_completed)
4803 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4806 /* Merge block A and B. The blocks must be mergeable. */
4808 static void
4809 cfg_layout_merge_blocks (basic_block a, basic_block b)
4811 /* If B is a forwarder block whose outgoing edge has no location, we'll
4812 propagate the locus of the edge between A and B onto it. */
4813 const bool forward_edge_locus
4814 = (b->flags & BB_FORWARDER_BLOCK) != 0
4815 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION;
4816 rtx_insn *insn;
4818 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4820 if (dump_file)
4821 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4822 a->index);
4824 /* If there was a CODE_LABEL beginning B, delete it. */
4825 if (LABEL_P (BB_HEAD (b)))
4827 delete_insn (BB_HEAD (b));
4830 /* We should have fallthru edge in a, or we can do dummy redirection to get
4831 it cleaned up. */
4832 if (JUMP_P (BB_END (a)))
4833 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4834 gcc_assert (!JUMP_P (BB_END (a)));
4836 /* If not optimizing, preserve the locus of the single edge between
4837 blocks A and B if necessary by emitting a nop. */
4838 if (!optimize
4839 && !forward_edge_locus
4840 && !DECL_IGNORED_P (current_function_decl))
4841 emit_nop_for_unique_locus_between (a, b);
4843 /* Move things from b->footer after a->footer. */
4844 if (BB_FOOTER (b))
4846 if (!BB_FOOTER (a))
4847 BB_FOOTER (a) = BB_FOOTER (b);
4848 else
4850 rtx_insn *last = BB_FOOTER (a);
4852 while (NEXT_INSN (last))
4853 last = NEXT_INSN (last);
4854 SET_NEXT_INSN (last) = BB_FOOTER (b);
4855 SET_PREV_INSN (BB_FOOTER (b)) = last;
4857 BB_FOOTER (b) = NULL;
4860 /* Move things from b->header before a->footer.
4861 Note that this may include dead tablejump data, but we don't clean
4862 those up until we go out of cfglayout mode. */
4863 if (BB_HEADER (b))
4865 if (! BB_FOOTER (a))
4866 BB_FOOTER (a) = BB_HEADER (b);
4867 else
4869 rtx_insn *last = BB_HEADER (b);
4871 while (NEXT_INSN (last))
4872 last = NEXT_INSN (last);
4873 SET_NEXT_INSN (last) = BB_FOOTER (a);
4874 SET_PREV_INSN (BB_FOOTER (a)) = last;
4875 BB_FOOTER (a) = BB_HEADER (b);
4877 BB_HEADER (b) = NULL;
4880 /* In the case basic blocks are not adjacent, move them around. */
4881 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4883 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4885 emit_insn_after_noloc (insn, BB_END (a), a);
4887 /* Otherwise just re-associate the instructions. */
4888 else
4890 insn = BB_HEAD (b);
4891 BB_END (a) = BB_END (b);
4894 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4895 We need to explicitly call. */
4896 update_bb_for_insn_chain (insn, BB_END (b), a);
4898 /* Skip possible DELETED_LABEL insn. */
4899 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4900 insn = NEXT_INSN (insn);
4901 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4902 BB_HEAD (b) = BB_END (b) = NULL;
4903 delete_insn (insn);
4905 df_bb_delete (b->index);
4907 if (forward_edge_locus)
4908 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4910 if (dump_file)
4911 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4914 /* Split edge E. */
4916 static basic_block
4917 cfg_layout_split_edge (edge e)
4919 basic_block new_bb =
4920 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4921 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4922 NULL_RTX, e->src);
4924 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4925 BB_COPY_PARTITION (new_bb, e->src);
4926 else
4927 BB_COPY_PARTITION (new_bb, e->dest);
4928 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4929 redirect_edge_and_branch_force (e, new_bb);
4931 return new_bb;
4934 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4936 static void
4937 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4941 /* Return true if BB contains only labels or non-executable
4942 instructions. */
4944 static bool
4945 rtl_block_empty_p (basic_block bb)
4947 rtx_insn *insn;
4949 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4950 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4951 return true;
4953 FOR_BB_INSNS (bb, insn)
4954 if (NONDEBUG_INSN_P (insn)
4955 && (!any_uncondjump_p (insn) || !onlyjump_p (insn)))
4956 return false;
4958 return true;
4961 /* Split a basic block if it ends with a conditional branch and if
4962 the other part of the block is not empty. */
4964 static basic_block
4965 rtl_split_block_before_cond_jump (basic_block bb)
4967 rtx_insn *insn;
4968 rtx_insn *split_point = NULL;
4969 rtx_insn *last = NULL;
4970 bool found_code = false;
4972 FOR_BB_INSNS (bb, insn)
4974 if (any_condjump_p (insn))
4975 split_point = last;
4976 else if (NONDEBUG_INSN_P (insn))
4977 found_code = true;
4978 last = insn;
4981 /* Did not find everything. */
4982 if (found_code && split_point)
4983 return split_block (bb, split_point)->dest;
4984 else
4985 return NULL;
4988 /* Return 1 if BB ends with a call, possibly followed by some
4989 instructions that must stay with the call, 0 otherwise. */
4991 static bool
4992 rtl_block_ends_with_call_p (basic_block bb)
4994 rtx_insn *insn = BB_END (bb);
4996 while (!CALL_P (insn)
4997 && insn != BB_HEAD (bb)
4998 && (keep_with_call_p (insn)
4999 || NOTE_P (insn)
5000 || DEBUG_INSN_P (insn)))
5001 insn = PREV_INSN (insn);
5002 return (CALL_P (insn));
5005 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
5007 static bool
5008 rtl_block_ends_with_condjump_p (const_basic_block bb)
5010 return any_condjump_p (BB_END (bb));
5013 /* Return true if we need to add fake edge to exit.
5014 Helper function for rtl_flow_call_edges_add. */
5016 static bool
5017 need_fake_edge_p (const rtx_insn *insn)
5019 if (!INSN_P (insn))
5020 return false;
5022 if ((CALL_P (insn)
5023 && !SIBLING_CALL_P (insn)
5024 && !find_reg_note (insn, REG_NORETURN, NULL)
5025 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
5026 return true;
5028 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
5029 && MEM_VOLATILE_P (PATTERN (insn)))
5030 || (GET_CODE (PATTERN (insn)) == PARALLEL
5031 && asm_noperands (insn) != -1
5032 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
5033 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
5036 /* Add fake edges to the function exit for any non constant and non noreturn
5037 calls, volatile inline assembly in the bitmap of blocks specified by
5038 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
5039 that were split.
5041 The goal is to expose cases in which entering a basic block does not imply
5042 that all subsequent instructions must be executed. */
5044 static int
5045 rtl_flow_call_edges_add (sbitmap blocks)
5047 int i;
5048 int blocks_split = 0;
5049 int last_bb = last_basic_block_for_fn (cfun);
5050 bool check_last_block = false;
5052 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
5053 return 0;
5055 if (! blocks)
5056 check_last_block = true;
5057 else
5058 check_last_block = bitmap_bit_p (blocks,
5059 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
5061 /* In the last basic block, before epilogue generation, there will be
5062 a fallthru edge to EXIT. Special care is required if the last insn
5063 of the last basic block is a call because make_edge folds duplicate
5064 edges, which would result in the fallthru edge also being marked
5065 fake, which would result in the fallthru edge being removed by
5066 remove_fake_edges, which would result in an invalid CFG.
5068 Moreover, we can't elide the outgoing fake edge, since the block
5069 profiler needs to take this into account in order to solve the minimal
5070 spanning tree in the case that the call doesn't return.
5072 Handle this by adding a dummy instruction in a new last basic block. */
5073 if (check_last_block)
5075 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
5076 rtx_insn *insn = BB_END (bb);
5078 /* Back up past insns that must be kept in the same block as a call. */
5079 while (insn != BB_HEAD (bb)
5080 && keep_with_call_p (insn))
5081 insn = PREV_INSN (insn);
5083 if (need_fake_edge_p (insn))
5085 edge e;
5087 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5088 if (e)
5090 insert_insn_on_edge (gen_use (const0_rtx), e);
5091 commit_edge_insertions ();
5096 /* Now add fake edges to the function exit for any non constant
5097 calls since there is no way that we can determine if they will
5098 return or not... */
5100 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
5102 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
5103 rtx_insn *insn;
5104 rtx_insn *prev_insn;
5106 if (!bb)
5107 continue;
5109 if (blocks && !bitmap_bit_p (blocks, i))
5110 continue;
5112 for (insn = BB_END (bb); ; insn = prev_insn)
5114 prev_insn = PREV_INSN (insn);
5115 if (need_fake_edge_p (insn))
5117 edge e;
5118 rtx_insn *split_at_insn = insn;
5120 /* Don't split the block between a call and an insn that should
5121 remain in the same block as the call. */
5122 if (CALL_P (insn))
5123 while (split_at_insn != BB_END (bb)
5124 && keep_with_call_p (NEXT_INSN (split_at_insn)))
5125 split_at_insn = NEXT_INSN (split_at_insn);
5127 /* The handling above of the final block before the epilogue
5128 should be enough to verify that there is no edge to the exit
5129 block in CFG already. Calling make_edge in such case would
5130 cause us to mark that edge as fake and remove it later. */
5132 if (flag_checking && split_at_insn == BB_END (bb))
5134 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
5135 gcc_assert (e == NULL);
5138 /* Note that the following may create a new basic block
5139 and renumber the existing basic blocks. */
5140 if (split_at_insn != BB_END (bb))
5142 e = split_block (bb, split_at_insn);
5143 if (e)
5144 blocks_split++;
5147 edge ne = make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
5148 ne->probability = profile_probability::guessed_never ();
5151 if (insn == BB_HEAD (bb))
5152 break;
5156 if (blocks_split)
5157 verify_flow_info ();
5159 return blocks_split;
5162 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
5163 the conditional branch target, SECOND_HEAD should be the fall-thru
5164 there is no need to handle this here the loop versioning code handles
5165 this. the reason for SECON_HEAD is that it is needed for condition
5166 in trees, and this should be of the same type since it is a hook. */
5167 static void
5168 rtl_lv_add_condition_to_bb (basic_block first_head ,
5169 basic_block second_head ATTRIBUTE_UNUSED,
5170 basic_block cond_bb, void *comp_rtx)
5172 rtx_code_label *label;
5173 rtx_insn *seq, *jump;
5174 rtx op0 = XEXP ((rtx)comp_rtx, 0);
5175 rtx op1 = XEXP ((rtx)comp_rtx, 1);
5176 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
5177 machine_mode mode;
5180 label = block_label (first_head);
5181 mode = GET_MODE (op0);
5182 if (mode == VOIDmode)
5183 mode = GET_MODE (op1);
5185 start_sequence ();
5186 op0 = force_operand (op0, NULL_RTX);
5187 op1 = force_operand (op1, NULL_RTX);
5188 do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label,
5189 profile_probability::uninitialized ());
5190 jump = get_last_insn ();
5191 JUMP_LABEL (jump) = label;
5192 LABEL_NUSES (label)++;
5193 seq = get_insns ();
5194 end_sequence ();
5196 /* Add the new cond, in the new head. */
5197 emit_insn_after (seq, BB_END (cond_bb));
5201 /* Given a block B with unconditional branch at its end, get the
5202 store the return the branch edge and the fall-thru edge in
5203 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
5204 static void
5205 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
5206 edge *fallthru_edge)
5208 edge e = EDGE_SUCC (b, 0);
5210 if (e->flags & EDGE_FALLTHRU)
5212 *fallthru_edge = e;
5213 *branch_edge = EDGE_SUCC (b, 1);
5215 else
5217 *branch_edge = e;
5218 *fallthru_edge = EDGE_SUCC (b, 1);
5222 void
5223 init_rtl_bb_info (basic_block bb)
5225 gcc_assert (!bb->il.x.rtl);
5226 bb->il.x.head_ = NULL;
5227 bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
5230 static bool
5231 rtl_bb_info_initialized_p (basic_block bb)
5233 return bb->il.x.rtl;
5236 /* Returns true if it is possible to remove edge E by redirecting
5237 it to the destination of the other edge from E->src. */
5239 static bool
5240 rtl_can_remove_branch_p (const_edge e)
5242 const_basic_block src = e->src;
5243 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
5244 const rtx_insn *insn = BB_END (src);
5245 rtx set;
5247 /* The conditions are taken from try_redirect_by_replacing_jump. */
5248 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
5249 return false;
5251 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
5252 return false;
5254 if (BB_PARTITION (src) != BB_PARTITION (target))
5255 return false;
5257 if (!onlyjump_p (insn)
5258 || tablejump_p (insn, NULL, NULL))
5259 return false;
5261 set = single_set (insn);
5262 if (!set || side_effects_p (set))
5263 return false;
5265 return true;
5268 static basic_block
5269 rtl_duplicate_bb (basic_block bb, copy_bb_data *id)
5271 bb = cfg_layout_duplicate_bb (bb, id);
5272 bb->aux = NULL;
5273 return bb;
5276 /* Do book-keeping of basic block BB for the profile consistency checker.
5277 Store the counting in RECORD. */
5278 static void
5279 rtl_account_profile_record (basic_block bb, struct profile_record *record)
5281 rtx_insn *insn;
5282 FOR_BB_INSNS (bb, insn)
5283 if (INSN_P (insn))
5285 record->size += insn_cost (insn, false);
5286 if (profile_info)
5288 if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().initialized_p ()
5289 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.ipa ().nonzero_p ()
5290 && bb->count.ipa ().initialized_p ())
5291 record->time
5292 += insn_cost (insn, true) * bb->count.ipa ().to_gcov_type ();
5294 else if (bb->count.initialized_p ()
5295 && ENTRY_BLOCK_PTR_FOR_FN (cfun)->count.initialized_p ())
5296 record->time
5297 += insn_cost (insn, true)
5298 * bb->count.to_sreal_scale
5299 (ENTRY_BLOCK_PTR_FOR_FN (cfun)->count).to_double ();
5300 else
5301 record->time += insn_cost (insn, true);
5305 /* Implementation of CFG manipulation for linearized RTL. */
5306 struct cfg_hooks rtl_cfg_hooks = {
5307 "rtl",
5308 rtl_verify_flow_info,
5309 rtl_dump_bb,
5310 rtl_dump_bb_for_graph,
5311 rtl_create_basic_block,
5312 rtl_redirect_edge_and_branch,
5313 rtl_redirect_edge_and_branch_force,
5314 rtl_can_remove_branch_p,
5315 rtl_delete_block,
5316 rtl_split_block,
5317 rtl_move_block_after,
5318 rtl_can_merge_blocks, /* can_merge_blocks_p */
5319 rtl_merge_blocks,
5320 rtl_predict_edge,
5321 rtl_predicted_by_p,
5322 cfg_layout_can_duplicate_bb_p,
5323 rtl_duplicate_bb,
5324 rtl_split_edge,
5325 rtl_make_forwarder_block,
5326 rtl_tidy_fallthru_edge,
5327 rtl_force_nonfallthru,
5328 rtl_block_ends_with_call_p,
5329 rtl_block_ends_with_condjump_p,
5330 rtl_flow_call_edges_add,
5331 NULL, /* execute_on_growing_pred */
5332 NULL, /* execute_on_shrinking_pred */
5333 NULL, /* duplicate loop for trees */
5334 NULL, /* lv_add_condition_to_bb */
5335 NULL, /* lv_adjust_loop_header_phi*/
5336 NULL, /* extract_cond_bb_edges */
5337 NULL, /* flush_pending_stmts */
5338 rtl_block_empty_p, /* block_empty_p */
5339 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5340 rtl_account_profile_record,
5343 /* Implementation of CFG manipulation for cfg layout RTL, where
5344 basic block connected via fallthru edges does not have to be adjacent.
5345 This representation will hopefully become the default one in future
5346 version of the compiler. */
5348 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5349 "cfglayout mode",
5350 rtl_verify_flow_info_1,
5351 rtl_dump_bb,
5352 rtl_dump_bb_for_graph,
5353 cfg_layout_create_basic_block,
5354 cfg_layout_redirect_edge_and_branch,
5355 cfg_layout_redirect_edge_and_branch_force,
5356 rtl_can_remove_branch_p,
5357 cfg_layout_delete_block,
5358 cfg_layout_split_block,
5359 rtl_move_block_after,
5360 cfg_layout_can_merge_blocks_p,
5361 cfg_layout_merge_blocks,
5362 rtl_predict_edge,
5363 rtl_predicted_by_p,
5364 cfg_layout_can_duplicate_bb_p,
5365 cfg_layout_duplicate_bb,
5366 cfg_layout_split_edge,
5367 rtl_make_forwarder_block,
5368 NULL, /* tidy_fallthru_edge */
5369 rtl_force_nonfallthru,
5370 rtl_block_ends_with_call_p,
5371 rtl_block_ends_with_condjump_p,
5372 rtl_flow_call_edges_add,
5373 NULL, /* execute_on_growing_pred */
5374 NULL, /* execute_on_shrinking_pred */
5375 duplicate_loop_body_to_header_edge, /* duplicate loop for trees */
5376 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5377 NULL, /* lv_adjust_loop_header_phi*/
5378 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5379 NULL, /* flush_pending_stmts */
5380 rtl_block_empty_p, /* block_empty_p */
5381 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5382 rtl_account_profile_record,
5385 #include "gt-cfgrtl.h"
5387 #if __GNUC__ >= 10
5388 # pragma GCC diagnostic pop
5389 #endif