[doc][13/14] Document AArch64 target attributes and pragmas
[official-gcc.git] / gcc / cfgrtl.c
blob15ce8a7aed31f3650dbe9648d0e82a2209d3732a
1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2015 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 "cfghooks.h"
45 #include "tree.h"
46 #include "rtl.h"
47 #include "df.h"
48 #include "alias.h"
49 #include "cfgrtl.h"
50 #include "cfganal.h"
51 #include "cfgbuild.h"
52 #include "cfgcleanup.h"
53 #include "bb-reorder.h"
54 #include "regs.h"
55 #include "flags.h"
56 #include "except.h"
57 #include "rtl-error.h"
58 #include "tm_p.h"
59 #include "insn-attr.h"
60 #include "insn-config.h"
61 #include "expmed.h"
62 #include "dojump.h"
63 #include "explow.h"
64 #include "calls.h"
65 #include "emit-rtl.h"
66 #include "varasm.h"
67 #include "stmt.h"
68 #include "expr.h"
69 #include "target.h"
70 #include "common/common-target.h"
71 #include "cfgloop.h"
72 #include "tree-pass.h"
74 /* Holds the interesting leading and trailing notes for the function.
75 Only applicable if the CFG is in cfglayout mode. */
76 static GTY(()) rtx_insn *cfg_layout_function_footer;
77 static GTY(()) rtx_insn *cfg_layout_function_header;
79 static rtx_insn *skip_insns_after_block (basic_block);
80 static void record_effective_endpoints (void);
81 static void fixup_reorder_chain (void);
83 void verify_insn_chain (void);
84 static void fixup_fallthru_exit_predecessor (void);
85 static int can_delete_note_p (const rtx_note *);
86 static int can_delete_label_p (const rtx_code_label *);
87 static basic_block rtl_split_edge (edge);
88 static bool rtl_move_block_after (basic_block, basic_block);
89 static int rtl_verify_flow_info (void);
90 static basic_block cfg_layout_split_block (basic_block, void *);
91 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
92 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
93 static void cfg_layout_delete_block (basic_block);
94 static void rtl_delete_block (basic_block);
95 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
96 static edge rtl_redirect_edge_and_branch (edge, basic_block);
97 static basic_block rtl_split_block (basic_block, void *);
98 static void rtl_dump_bb (FILE *, basic_block, int, int);
99 static int rtl_verify_flow_info_1 (void);
100 static void rtl_make_forwarder_block (edge);
102 /* Return true if NOTE is not one of the ones that must be kept paired,
103 so that we may simply delete it. */
105 static int
106 can_delete_note_p (const rtx_note *note)
108 switch (NOTE_KIND (note))
110 case NOTE_INSN_DELETED:
111 case NOTE_INSN_BASIC_BLOCK:
112 case NOTE_INSN_EPILOGUE_BEG:
113 return true;
115 default:
116 return false;
120 /* True if a given label can be deleted. */
122 static int
123 can_delete_label_p (const rtx_code_label *label)
125 return (!LABEL_PRESERVE_P (label)
126 /* User declared labels must be preserved. */
127 && LABEL_NAME (label) == 0
128 && !in_insn_list_p (forced_labels, label));
131 /* Delete INSN by patching it out. */
133 void
134 delete_insn (rtx uncast_insn)
136 rtx_insn *insn = as_a <rtx_insn *> (uncast_insn);
137 rtx note;
138 bool really_delete = true;
140 if (LABEL_P (insn))
142 /* Some labels can't be directly removed from the INSN chain, as they
143 might be references via variables, constant pool etc.
144 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
145 if (! can_delete_label_p (as_a <rtx_code_label *> (insn)))
147 const char *name = LABEL_NAME (insn);
148 basic_block bb = BLOCK_FOR_INSN (insn);
149 rtx_insn *bb_note = NEXT_INSN (insn);
151 really_delete = false;
152 PUT_CODE (insn, NOTE);
153 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
154 NOTE_DELETED_LABEL_NAME (insn) = name;
156 /* If the note following the label starts a basic block, and the
157 label is a member of the same basic block, interchange the two. */
158 if (bb_note != NULL_RTX
159 && NOTE_INSN_BASIC_BLOCK_P (bb_note)
160 && bb != NULL
161 && bb == BLOCK_FOR_INSN (bb_note))
163 reorder_insns_nobb (insn, insn, bb_note);
164 BB_HEAD (bb) = bb_note;
165 if (BB_END (bb) == bb_note)
166 BB_END (bb) = insn;
170 remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels);
173 if (really_delete)
175 /* If this insn has already been deleted, something is very wrong. */
176 gcc_assert (!insn->deleted ());
177 if (INSN_P (insn))
178 df_insn_delete (insn);
179 remove_insn (insn);
180 insn->set_deleted ();
183 /* If deleting a jump, decrement the use count of the label. Deleting
184 the label itself should happen in the normal course of block merging. */
185 if (JUMP_P (insn))
187 if (JUMP_LABEL (insn)
188 && LABEL_P (JUMP_LABEL (insn)))
189 LABEL_NUSES (JUMP_LABEL (insn))--;
191 /* If there are more targets, remove them too. */
192 while ((note
193 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
194 && LABEL_P (XEXP (note, 0)))
196 LABEL_NUSES (XEXP (note, 0))--;
197 remove_note (insn, note);
201 /* Also if deleting any insn that references a label as an operand. */
202 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
203 && LABEL_P (XEXP (note, 0)))
205 LABEL_NUSES (XEXP (note, 0))--;
206 remove_note (insn, note);
209 if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
211 rtvec vec = table->get_labels ();
212 int len = GET_NUM_ELEM (vec);
213 int i;
215 for (i = 0; i < len; i++)
217 rtx label = XEXP (RTVEC_ELT (vec, i), 0);
219 /* When deleting code in bulk (e.g. removing many unreachable
220 blocks) we can delete a label that's a target of the vector
221 before deleting the vector itself. */
222 if (!NOTE_P (label))
223 LABEL_NUSES (label)--;
228 /* Like delete_insn but also purge dead edges from BB. */
230 void
231 delete_insn_and_edges (rtx_insn *insn)
233 bool purge = false;
235 if (INSN_P (insn)
236 && BLOCK_FOR_INSN (insn)
237 && BB_END (BLOCK_FOR_INSN (insn)) == insn)
238 purge = true;
239 delete_insn (insn);
240 if (purge)
241 purge_dead_edges (BLOCK_FOR_INSN (insn));
244 /* Unlink a chain of insns between START and FINISH, leaving notes
245 that must be paired. If CLEAR_BB is true, we set bb field for
246 insns that cannot be removed to NULL. */
248 void
249 delete_insn_chain (rtx start, rtx finish, bool clear_bb)
251 rtx_insn *prev, *current;
253 /* Unchain the insns one by one. It would be quicker to delete all of these
254 with a single unchaining, rather than one at a time, but we need to keep
255 the NOTE's. */
256 current = safe_as_a <rtx_insn *> (finish);
257 while (1)
259 prev = PREV_INSN (current);
260 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
262 else
263 delete_insn (current);
265 if (clear_bb && !current->deleted ())
266 set_block_for_insn (current, NULL);
268 if (current == start)
269 break;
270 current = prev;
274 /* Create a new basic block consisting of the instructions between HEAD and END
275 inclusive. This function is designed to allow fast BB construction - reuses
276 the note and basic block struct in BB_NOTE, if any and do not grow
277 BASIC_BLOCK chain and should be used directly only by CFG construction code.
278 END can be NULL in to create new empty basic block before HEAD. Both END
279 and HEAD can be NULL to create basic block at the end of INSN chain.
280 AFTER is the basic block we should be put after. */
282 basic_block
283 create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
284 basic_block after)
286 basic_block bb;
288 if (bb_note
289 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
290 && bb->aux == NULL)
292 /* If we found an existing note, thread it back onto the chain. */
294 rtx_insn *after;
296 if (LABEL_P (head))
297 after = head;
298 else
300 after = PREV_INSN (head);
301 head = bb_note;
304 if (after != bb_note && NEXT_INSN (after) != bb_note)
305 reorder_insns_nobb (bb_note, bb_note, after);
307 else
309 /* Otherwise we must create a note and a basic block structure. */
311 bb = alloc_block ();
313 init_rtl_bb_info (bb);
314 if (!head && !end)
315 head = end = bb_note
316 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
317 else if (LABEL_P (head) && end)
319 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
320 if (head == end)
321 end = bb_note;
323 else
325 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
326 head = bb_note;
327 if (!end)
328 end = head;
331 NOTE_BASIC_BLOCK (bb_note) = bb;
334 /* Always include the bb note in the block. */
335 if (NEXT_INSN (end) == bb_note)
336 end = bb_note;
338 BB_HEAD (bb) = head;
339 BB_END (bb) = end;
340 bb->index = last_basic_block_for_fn (cfun)++;
341 bb->flags = BB_NEW | BB_RTL;
342 link_block (bb, after);
343 SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
344 df_bb_refs_record (bb->index, false);
345 update_bb_for_insn (bb);
346 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
348 /* Tag the block so that we know it has been used when considering
349 other basic block notes. */
350 bb->aux = bb;
352 return bb;
355 /* Create new basic block consisting of instructions in between HEAD and END
356 and place it to the BB chain after block AFTER. END can be NULL to
357 create a new empty basic block before HEAD. Both END and HEAD can be
358 NULL to create basic block at the end of INSN chain. */
360 static basic_block
361 rtl_create_basic_block (void *headp, void *endp, basic_block after)
363 rtx_insn *head = (rtx_insn *) headp;
364 rtx_insn *end = (rtx_insn *) endp;
365 basic_block bb;
367 /* Grow the basic block array if needed. */
368 if ((size_t) last_basic_block_for_fn (cfun)
369 >= basic_block_info_for_fn (cfun)->length ())
371 size_t new_size =
372 (last_basic_block_for_fn (cfun)
373 + (last_basic_block_for_fn (cfun) + 3) / 4);
374 vec_safe_grow_cleared (basic_block_info_for_fn (cfun), new_size);
377 n_basic_blocks_for_fn (cfun)++;
379 bb = create_basic_block_structure (head, end, NULL, after);
380 bb->aux = NULL;
381 return bb;
384 static basic_block
385 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
387 basic_block newbb = rtl_create_basic_block (head, end, after);
389 return newbb;
392 /* Delete the insns in a (non-live) block. We physically delete every
393 non-deleted-note insn, and update the flow graph appropriately.
395 Return nonzero if we deleted an exception handler. */
397 /* ??? Preserving all such notes strikes me as wrong. It would be nice
398 to post-process the stream to remove empty blocks, loops, ranges, etc. */
400 static void
401 rtl_delete_block (basic_block b)
403 rtx_insn *insn, *end;
405 /* If the head of this block is a CODE_LABEL, then it might be the
406 label for an exception handler which can't be reached. We need
407 to remove the label from the exception_handler_label list. */
408 insn = BB_HEAD (b);
410 end = get_last_bb_insn (b);
412 /* Selectively delete the entire chain. */
413 BB_HEAD (b) = NULL;
414 delete_insn_chain (insn, end, true);
417 if (dump_file)
418 fprintf (dump_file, "deleting block %d\n", b->index);
419 df_bb_delete (b->index);
422 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
424 void
425 compute_bb_for_insn (void)
427 basic_block bb;
429 FOR_EACH_BB_FN (bb, cfun)
431 rtx_insn *end = BB_END (bb);
432 rtx_insn *insn;
434 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
436 BLOCK_FOR_INSN (insn) = bb;
437 if (insn == end)
438 break;
443 /* Release the basic_block_for_insn array. */
445 unsigned int
446 free_bb_for_insn (void)
448 rtx_insn *insn;
449 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
450 if (!BARRIER_P (insn))
451 BLOCK_FOR_INSN (insn) = NULL;
452 return 0;
455 namespace {
457 const pass_data pass_data_free_cfg =
459 RTL_PASS, /* type */
460 "*free_cfg", /* name */
461 OPTGROUP_NONE, /* optinfo_flags */
462 TV_NONE, /* tv_id */
463 0, /* properties_required */
464 0, /* properties_provided */
465 PROP_cfg, /* properties_destroyed */
466 0, /* todo_flags_start */
467 0, /* todo_flags_finish */
470 class pass_free_cfg : public rtl_opt_pass
472 public:
473 pass_free_cfg (gcc::context *ctxt)
474 : rtl_opt_pass (pass_data_free_cfg, ctxt)
477 /* opt_pass methods: */
478 virtual unsigned int execute (function *);
480 }; // class pass_free_cfg
482 unsigned int
483 pass_free_cfg::execute (function *)
485 #ifdef DELAY_SLOTS
486 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
487 valid at that point so it would be too late to call df_analyze. */
488 if (optimize > 0 && flag_delayed_branch)
490 df_note_add_problem ();
491 df_analyze ();
493 #endif
495 if (crtl->has_bb_partition)
496 insert_section_boundary_note ();
498 free_bb_for_insn ();
499 return 0;
502 } // anon namespace
504 rtl_opt_pass *
505 make_pass_free_cfg (gcc::context *ctxt)
507 return new pass_free_cfg (ctxt);
510 /* Return RTX to emit after when we want to emit code on the entry of function. */
511 rtx_insn *
512 entry_of_function (void)
514 return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
515 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
518 /* Emit INSN at the entry point of the function, ensuring that it is only
519 executed once per function. */
520 void
521 emit_insn_at_entry (rtx insn)
523 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
524 edge e = ei_safe_edge (ei);
525 gcc_assert (e->flags & EDGE_FALLTHRU);
527 insert_insn_on_edge (insn, e);
528 commit_edge_insertions ();
531 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
532 (or BARRIER if found) and notify df of the bb change.
533 The insn chain range is inclusive
534 (i.e. both BEGIN and END will be updated. */
536 static void
537 update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
539 rtx_insn *insn;
541 end = NEXT_INSN (end);
542 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
543 if (!BARRIER_P (insn))
544 df_insn_change_bb (insn, bb);
547 /* Update BLOCK_FOR_INSN of insns in BB to BB,
548 and notify df of the change. */
550 void
551 update_bb_for_insn (basic_block bb)
553 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
557 /* Like active_insn_p, except keep the return value clobber around
558 even after reload. */
560 static bool
561 flow_active_insn_p (const rtx_insn *insn)
563 if (active_insn_p (insn))
564 return true;
566 /* A clobber of the function return value exists for buggy
567 programs that fail to return a value. Its effect is to
568 keep the return value from being live across the entire
569 function. If we allow it to be skipped, we introduce the
570 possibility for register lifetime confusion. */
571 if (GET_CODE (PATTERN (insn)) == CLOBBER
572 && REG_P (XEXP (PATTERN (insn), 0))
573 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
574 return true;
576 return false;
579 /* Return true if the block has no effect and only forwards control flow to
580 its single destination. */
582 bool
583 contains_no_active_insn_p (const_basic_block bb)
585 rtx_insn *insn;
587 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
588 || !single_succ_p (bb))
589 return false;
591 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
592 if (INSN_P (insn) && flow_active_insn_p (insn))
593 return false;
595 return (!INSN_P (insn)
596 || (JUMP_P (insn) && simplejump_p (insn))
597 || !flow_active_insn_p (insn));
600 /* Likewise, but protect loop latches, headers and preheaders. */
601 /* FIXME: Make this a cfg hook. */
603 bool
604 forwarder_block_p (const_basic_block bb)
606 if (!contains_no_active_insn_p (bb))
607 return false;
609 /* Protect loop latches, headers and preheaders. */
610 if (current_loops)
612 basic_block dest;
613 if (bb->loop_father->header == bb)
614 return false;
615 dest = EDGE_SUCC (bb, 0)->dest;
616 if (dest->loop_father->header == dest)
617 return false;
620 return true;
623 /* Return nonzero if we can reach target from src by falling through. */
624 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
626 bool
627 can_fallthru (basic_block src, basic_block target)
629 rtx_insn *insn = BB_END (src);
630 rtx_insn *insn2;
631 edge e;
632 edge_iterator ei;
634 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
635 return true;
636 if (src->next_bb != target)
637 return false;
639 /* ??? Later we may add code to move jump tables offline. */
640 if (tablejump_p (insn, NULL, NULL))
641 return false;
643 FOR_EACH_EDGE (e, ei, src->succs)
644 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
645 && e->flags & EDGE_FALLTHRU)
646 return false;
648 insn2 = BB_HEAD (target);
649 if (!active_insn_p (insn2))
650 insn2 = next_active_insn (insn2);
652 return next_active_insn (insn) == insn2;
655 /* Return nonzero if we could reach target from src by falling through,
656 if the target was made adjacent. If we already have a fall-through
657 edge to the exit block, we can't do that. */
658 static bool
659 could_fall_through (basic_block src, basic_block target)
661 edge e;
662 edge_iterator ei;
664 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
665 return true;
666 FOR_EACH_EDGE (e, ei, src->succs)
667 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
668 && e->flags & EDGE_FALLTHRU)
669 return 0;
670 return true;
673 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
674 rtx_note *
675 bb_note (basic_block bb)
677 rtx_insn *note;
679 note = BB_HEAD (bb);
680 if (LABEL_P (note))
681 note = NEXT_INSN (note);
683 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
684 return as_a <rtx_note *> (note);
687 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
688 note associated with the BLOCK. */
690 static rtx_insn *
691 first_insn_after_basic_block_note (basic_block block)
693 rtx_insn *insn;
695 /* Get the first instruction in the block. */
696 insn = BB_HEAD (block);
698 if (insn == NULL_RTX)
699 return NULL;
700 if (LABEL_P (insn))
701 insn = NEXT_INSN (insn);
702 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
704 return NEXT_INSN (insn);
707 /* Creates a new basic block just after basic block BB by splitting
708 everything after specified instruction INSNP. */
710 static basic_block
711 rtl_split_block (basic_block bb, void *insnp)
713 basic_block new_bb;
714 rtx_insn *insn = (rtx_insn *) insnp;
715 edge e;
716 edge_iterator ei;
718 if (!insn)
720 insn = first_insn_after_basic_block_note (bb);
722 if (insn)
724 rtx_insn *next = insn;
726 insn = PREV_INSN (insn);
728 /* If the block contains only debug insns, insn would have
729 been NULL in a non-debug compilation, and then we'd end
730 up emitting a DELETED note. For -fcompare-debug
731 stability, emit the note too. */
732 if (insn != BB_END (bb)
733 && DEBUG_INSN_P (next)
734 && DEBUG_INSN_P (BB_END (bb)))
736 while (next != BB_END (bb) && DEBUG_INSN_P (next))
737 next = NEXT_INSN (next);
739 if (next == BB_END (bb))
740 emit_note_after (NOTE_INSN_DELETED, next);
743 else
744 insn = get_last_insn ();
747 /* We probably should check type of the insn so that we do not create
748 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
749 bother. */
750 if (insn == BB_END (bb))
751 emit_note_after (NOTE_INSN_DELETED, insn);
753 /* Create the new basic block. */
754 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
755 BB_COPY_PARTITION (new_bb, bb);
756 BB_END (bb) = insn;
758 /* Redirect the outgoing edges. */
759 new_bb->succs = bb->succs;
760 bb->succs = NULL;
761 FOR_EACH_EDGE (e, ei, new_bb->succs)
762 e->src = new_bb;
764 /* The new block starts off being dirty. */
765 df_set_bb_dirty (bb);
766 return new_bb;
769 /* Return true if the single edge between blocks A and B is the only place
770 in RTL which holds some unique locus. */
772 static bool
773 unique_locus_on_edge_between_p (basic_block a, basic_block b)
775 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
776 rtx_insn *insn, *end;
778 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
779 return false;
781 /* First scan block A backward. */
782 insn = BB_END (a);
783 end = PREV_INSN (BB_HEAD (a));
784 while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
785 insn = PREV_INSN (insn);
787 if (insn != end && INSN_LOCATION (insn) == goto_locus)
788 return false;
790 /* Then scan block B forward. */
791 insn = BB_HEAD (b);
792 if (insn)
794 end = NEXT_INSN (BB_END (b));
795 while (insn != end && !NONDEBUG_INSN_P (insn))
796 insn = NEXT_INSN (insn);
798 if (insn != end && INSN_HAS_LOCATION (insn)
799 && INSN_LOCATION (insn) == goto_locus)
800 return false;
803 return true;
806 /* If the single edge between blocks A and B is the only place in RTL which
807 holds some unique locus, emit a nop with that locus between the blocks. */
809 static void
810 emit_nop_for_unique_locus_between (basic_block a, basic_block b)
812 if (!unique_locus_on_edge_between_p (a, b))
813 return;
815 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
816 INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
819 /* Blocks A and B are to be merged into a single block A. The insns
820 are already contiguous. */
822 static void
823 rtl_merge_blocks (basic_block a, basic_block b)
825 rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
826 rtx_insn *del_first = NULL, *del_last = NULL;
827 rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
828 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
829 int b_empty = 0;
831 if (dump_file)
832 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
833 a->index);
835 while (DEBUG_INSN_P (b_end))
836 b_end = PREV_INSN (b_debug_start = b_end);
838 /* If there was a CODE_LABEL beginning B, delete it. */
839 if (LABEL_P (b_head))
841 /* Detect basic blocks with nothing but a label. This can happen
842 in particular at the end of a function. */
843 if (b_head == b_end)
844 b_empty = 1;
846 del_first = del_last = b_head;
847 b_head = NEXT_INSN (b_head);
850 /* Delete the basic block note and handle blocks containing just that
851 note. */
852 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
854 if (b_head == b_end)
855 b_empty = 1;
856 if (! del_last)
857 del_first = b_head;
859 del_last = b_head;
860 b_head = NEXT_INSN (b_head);
863 /* If there was a jump out of A, delete it. */
864 if (JUMP_P (a_end))
866 rtx_insn *prev;
868 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
869 if (!NOTE_P (prev)
870 || NOTE_INSN_BASIC_BLOCK_P (prev)
871 || prev == BB_HEAD (a))
872 break;
874 del_first = a_end;
876 /* If this was a conditional jump, we need to also delete
877 the insn that set cc0. */
878 if (HAVE_cc0 && only_sets_cc0_p (prev))
880 rtx_insn *tmp = prev;
882 prev = prev_nonnote_insn (prev);
883 if (!prev)
884 prev = BB_HEAD (a);
885 del_first = tmp;
888 a_end = PREV_INSN (del_first);
890 else if (BARRIER_P (NEXT_INSN (a_end)))
891 del_first = NEXT_INSN (a_end);
893 /* Delete everything marked above as well as crap that might be
894 hanging out between the two blocks. */
895 BB_END (a) = a_end;
896 BB_HEAD (b) = b_empty ? NULL : b_head;
897 delete_insn_chain (del_first, del_last, true);
899 /* When not optimizing and the edge is the only place in RTL which holds
900 some unique locus, emit a nop with that locus in between. */
901 if (!optimize)
903 emit_nop_for_unique_locus_between (a, b);
904 a_end = BB_END (a);
907 /* Reassociate the insns of B with A. */
908 if (!b_empty)
910 update_bb_for_insn_chain (a_end, b_debug_end, a);
912 BB_END (a) = b_debug_end;
913 BB_HEAD (b) = NULL;
915 else if (b_end != b_debug_end)
917 /* Move any deleted labels and other notes between the end of A
918 and the debug insns that make up B after the debug insns,
919 bringing the debug insns into A while keeping the notes after
920 the end of A. */
921 if (NEXT_INSN (a_end) != b_debug_start)
922 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
923 b_debug_end);
924 update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
925 BB_END (a) = b_debug_end;
928 df_bb_delete (b->index);
930 /* If B was a forwarder block, propagate the locus on the edge. */
931 if (forwarder_p
932 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
933 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
935 if (dump_file)
936 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
940 /* Return true when block A and B can be merged. */
942 static bool
943 rtl_can_merge_blocks (basic_block a, basic_block b)
945 /* If we are partitioning hot/cold basic blocks, we don't want to
946 mess up unconditional or indirect jumps that cross between hot
947 and cold sections.
949 Basic block partitioning may result in some jumps that appear to
950 be optimizable (or blocks that appear to be mergeable), but which really
951 must be left untouched (they are required to make it safely across
952 partition boundaries). See the comments at the top of
953 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
955 if (BB_PARTITION (a) != BB_PARTITION (b))
956 return false;
958 /* Protect the loop latches. */
959 if (current_loops && b->loop_father->latch == b)
960 return false;
962 /* There must be exactly one edge in between the blocks. */
963 return (single_succ_p (a)
964 && single_succ (a) == b
965 && single_pred_p (b)
966 && a != b
967 /* Must be simple edge. */
968 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
969 && a->next_bb == b
970 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
971 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
972 /* If the jump insn has side effects,
973 we can't kill the edge. */
974 && (!JUMP_P (BB_END (a))
975 || (reload_completed
976 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
979 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
980 exist. */
982 rtx_code_label *
983 block_label (basic_block block)
985 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
986 return NULL;
988 if (!LABEL_P (BB_HEAD (block)))
990 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
993 return as_a <rtx_code_label *> (BB_HEAD (block));
996 /* Attempt to perform edge redirection by replacing possibly complex jump
997 instruction by unconditional jump or removing jump completely. This can
998 apply only if all edges now point to the same block. The parameters and
999 return values are equivalent to redirect_edge_and_branch. */
1001 edge
1002 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
1004 basic_block src = e->src;
1005 rtx_insn *insn = BB_END (src), *kill_from;
1006 rtx set;
1007 int fallthru = 0;
1009 /* If we are partitioning hot/cold basic blocks, we don't want to
1010 mess up unconditional or indirect jumps that cross between hot
1011 and cold sections.
1013 Basic block partitioning may result in some jumps that appear to
1014 be optimizable (or blocks that appear to be mergeable), but which really
1015 must be left untouched (they are required to make it safely across
1016 partition boundaries). See the comments at the top of
1017 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1019 if (BB_PARTITION (src) != BB_PARTITION (target))
1020 return NULL;
1022 /* We can replace or remove a complex jump only when we have exactly
1023 two edges. Also, if we have exactly one outgoing edge, we can
1024 redirect that. */
1025 if (EDGE_COUNT (src->succs) >= 3
1026 /* Verify that all targets will be TARGET. Specifically, the
1027 edge that is not E must also go to TARGET. */
1028 || (EDGE_COUNT (src->succs) == 2
1029 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1030 return NULL;
1032 if (!onlyjump_p (insn))
1033 return NULL;
1034 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1035 return NULL;
1037 /* Avoid removing branch with side effects. */
1038 set = single_set (insn);
1039 if (!set || side_effects_p (set))
1040 return NULL;
1042 /* In case we zap a conditional jump, we'll need to kill
1043 the cc0 setter too. */
1044 kill_from = insn;
1045 if (HAVE_cc0 && reg_mentioned_p (cc0_rtx, PATTERN (insn))
1046 && only_sets_cc0_p (PREV_INSN (insn)))
1047 kill_from = PREV_INSN (insn);
1049 /* See if we can create the fallthru edge. */
1050 if (in_cfglayout || can_fallthru (src, target))
1052 if (dump_file)
1053 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1054 fallthru = 1;
1056 /* Selectively unlink whole insn chain. */
1057 if (in_cfglayout)
1059 rtx_insn *insn = BB_FOOTER (src);
1061 delete_insn_chain (kill_from, BB_END (src), false);
1063 /* Remove barriers but keep jumptables. */
1064 while (insn)
1066 if (BARRIER_P (insn))
1068 if (PREV_INSN (insn))
1069 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1070 else
1071 BB_FOOTER (src) = NEXT_INSN (insn);
1072 if (NEXT_INSN (insn))
1073 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1075 if (LABEL_P (insn))
1076 break;
1077 insn = NEXT_INSN (insn);
1080 else
1081 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
1082 false);
1085 /* If this already is simplejump, redirect it. */
1086 else if (simplejump_p (insn))
1088 if (e->dest == target)
1089 return NULL;
1090 if (dump_file)
1091 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1092 INSN_UID (insn), e->dest->index, target->index);
1093 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1094 block_label (target), 0))
1096 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1097 return NULL;
1101 /* Cannot do anything for target exit block. */
1102 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1103 return NULL;
1105 /* Or replace possibly complicated jump insn by simple jump insn. */
1106 else
1108 rtx_code_label *target_label = block_label (target);
1109 rtx_insn *barrier;
1110 rtx label;
1111 rtx_jump_table_data *table;
1113 emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn);
1114 JUMP_LABEL (BB_END (src)) = target_label;
1115 LABEL_NUSES (target_label)++;
1116 if (dump_file)
1117 fprintf (dump_file, "Replacing insn %i by jump %i\n",
1118 INSN_UID (insn), INSN_UID (BB_END (src)));
1121 delete_insn_chain (kill_from, insn, false);
1123 /* Recognize a tablejump that we are converting to a
1124 simple jump and remove its associated CODE_LABEL
1125 and ADDR_VEC or ADDR_DIFF_VEC. */
1126 if (tablejump_p (insn, &label, &table))
1127 delete_insn_chain (label, table, false);
1129 barrier = next_nonnote_insn (BB_END (src));
1130 if (!barrier || !BARRIER_P (barrier))
1131 emit_barrier_after (BB_END (src));
1132 else
1134 if (barrier != NEXT_INSN (BB_END (src)))
1136 /* Move the jump before barrier so that the notes
1137 which originally were or were created before jump table are
1138 inside the basic block. */
1139 rtx_insn *new_insn = BB_END (src);
1141 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1142 PREV_INSN (barrier), src);
1144 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1145 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1147 SET_NEXT_INSN (new_insn) = barrier;
1148 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1150 SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1151 SET_PREV_INSN (barrier) = new_insn;
1156 /* Keep only one edge out and set proper flags. */
1157 if (!single_succ_p (src))
1158 remove_edge (e);
1159 gcc_assert (single_succ_p (src));
1161 e = single_succ_edge (src);
1162 if (fallthru)
1163 e->flags = EDGE_FALLTHRU;
1164 else
1165 e->flags = 0;
1167 e->probability = REG_BR_PROB_BASE;
1168 e->count = src->count;
1170 if (e->dest != target)
1171 redirect_edge_succ (e, target);
1172 return e;
1175 /* Subroutine of redirect_branch_edge that tries to patch the jump
1176 instruction INSN so that it reaches block NEW. Do this
1177 only when it originally reached block OLD. Return true if this
1178 worked or the original target wasn't OLD, return false if redirection
1179 doesn't work. */
1181 static bool
1182 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1184 rtx_jump_table_data *table;
1185 rtx tmp;
1186 /* Recognize a tablejump and adjust all matching cases. */
1187 if (tablejump_p (insn, NULL, &table))
1189 rtvec vec;
1190 int j;
1191 rtx_code_label *new_label = block_label (new_bb);
1193 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1194 return false;
1195 vec = table->get_labels ();
1197 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1198 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1200 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1201 --LABEL_NUSES (old_label);
1202 ++LABEL_NUSES (new_label);
1205 /* Handle casesi dispatch insns. */
1206 if ((tmp = single_set (insn)) != NULL
1207 && SET_DEST (tmp) == pc_rtx
1208 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1209 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1210 && LABEL_REF_LABEL (XEXP (SET_SRC (tmp), 2)) == old_label)
1212 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1213 new_label);
1214 --LABEL_NUSES (old_label);
1215 ++LABEL_NUSES (new_label);
1218 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1220 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1221 rtx note;
1223 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1224 return false;
1225 rtx_code_label *new_label = block_label (new_bb);
1227 for (i = 0; i < n; ++i)
1229 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1230 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1231 if (XEXP (old_ref, 0) == old_label)
1233 ASM_OPERANDS_LABEL (tmp, i)
1234 = gen_rtx_LABEL_REF (Pmode, new_label);
1235 --LABEL_NUSES (old_label);
1236 ++LABEL_NUSES (new_label);
1240 if (JUMP_LABEL (insn) == old_label)
1242 JUMP_LABEL (insn) = new_label;
1243 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1244 if (note)
1245 remove_note (insn, note);
1247 else
1249 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1250 if (note)
1251 remove_note (insn, note);
1252 if (JUMP_LABEL (insn) != new_label
1253 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1254 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1256 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1257 != NULL_RTX)
1258 XEXP (note, 0) = new_label;
1260 else
1262 /* ?? We may play the games with moving the named labels from
1263 one basic block to the other in case only one computed_jump is
1264 available. */
1265 if (computed_jump_p (insn)
1266 /* A return instruction can't be redirected. */
1267 || returnjump_p (insn))
1268 return false;
1270 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1272 /* If the insn doesn't go where we think, we're confused. */
1273 gcc_assert (JUMP_LABEL (insn) == old_label);
1275 /* If the substitution doesn't succeed, die. This can happen
1276 if the back end emitted unrecognizable instructions or if
1277 target is exit block on some arches. */
1278 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1279 block_label (new_bb), 0))
1281 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun));
1282 return false;
1286 return true;
1290 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1291 NULL on failure */
1292 static edge
1293 redirect_branch_edge (edge e, basic_block target)
1295 rtx_insn *old_label = BB_HEAD (e->dest);
1296 basic_block src = e->src;
1297 rtx_insn *insn = BB_END (src);
1299 /* We can only redirect non-fallthru edges of jump insn. */
1300 if (e->flags & EDGE_FALLTHRU)
1301 return NULL;
1302 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1303 return NULL;
1305 if (!currently_expanding_to_rtl)
1307 if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1308 return NULL;
1310 else
1311 /* When expanding this BB might actually contain multiple
1312 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1313 Redirect all of those that match our label. */
1314 FOR_BB_INSNS (src, insn)
1315 if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1316 old_label, target))
1317 return NULL;
1319 if (dump_file)
1320 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1321 e->src->index, e->dest->index, target->index);
1323 if (e->dest != target)
1324 e = redirect_edge_succ_nodup (e, target);
1326 return e;
1329 /* Called when edge E has been redirected to a new destination,
1330 in order to update the region crossing flag on the edge and
1331 jump. */
1333 static void
1334 fixup_partition_crossing (edge e)
1336 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1337 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1338 return;
1339 /* If we redirected an existing edge, it may already be marked
1340 crossing, even though the new src is missing a reg crossing note.
1341 But make sure reg crossing note doesn't already exist before
1342 inserting. */
1343 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1345 e->flags |= EDGE_CROSSING;
1346 if (JUMP_P (BB_END (e->src))
1347 && !CROSSING_JUMP_P (BB_END (e->src)))
1348 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1350 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1352 e->flags &= ~EDGE_CROSSING;
1353 /* Remove the section crossing note from jump at end of
1354 src if it exists, and if no other successors are
1355 still crossing. */
1356 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1358 bool has_crossing_succ = false;
1359 edge e2;
1360 edge_iterator ei;
1361 FOR_EACH_EDGE (e2, ei, e->src->succs)
1363 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1364 if (has_crossing_succ)
1365 break;
1367 if (!has_crossing_succ)
1368 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1373 /* Called when block BB has been reassigned to the cold partition,
1374 because it is now dominated by another cold block,
1375 to ensure that the region crossing attributes are updated. */
1377 static void
1378 fixup_new_cold_bb (basic_block bb)
1380 edge e;
1381 edge_iterator ei;
1383 /* This is called when a hot bb is found to now be dominated
1384 by a cold bb and therefore needs to become cold. Therefore,
1385 its preds will no longer be region crossing. Any non-dominating
1386 preds that were previously hot would also have become cold
1387 in the caller for the same region. Any preds that were previously
1388 region-crossing will be adjusted in fixup_partition_crossing. */
1389 FOR_EACH_EDGE (e, ei, bb->preds)
1391 fixup_partition_crossing (e);
1394 /* Possibly need to make bb's successor edges region crossing,
1395 or remove stale region crossing. */
1396 FOR_EACH_EDGE (e, ei, bb->succs)
1398 /* We can't have fall-through edges across partition boundaries.
1399 Note that force_nonfallthru will do any necessary partition
1400 boundary fixup by calling fixup_partition_crossing itself. */
1401 if ((e->flags & EDGE_FALLTHRU)
1402 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1403 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1404 force_nonfallthru (e);
1405 else
1406 fixup_partition_crossing (e);
1410 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1411 expense of adding new instructions or reordering basic blocks.
1413 Function can be also called with edge destination equivalent to the TARGET.
1414 Then it should try the simplifications and do nothing if none is possible.
1416 Return edge representing the branch if transformation succeeded. Return NULL
1417 on failure.
1418 We still return NULL in case E already destinated TARGET and we didn't
1419 managed to simplify instruction stream. */
1421 static edge
1422 rtl_redirect_edge_and_branch (edge e, basic_block target)
1424 edge ret;
1425 basic_block src = e->src;
1426 basic_block dest = e->dest;
1428 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1429 return NULL;
1431 if (dest == target)
1432 return e;
1434 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1436 df_set_bb_dirty (src);
1437 fixup_partition_crossing (ret);
1438 return ret;
1441 ret = redirect_branch_edge (e, target);
1442 if (!ret)
1443 return NULL;
1445 df_set_bb_dirty (src);
1446 fixup_partition_crossing (ret);
1447 return ret;
1450 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1452 void
1453 emit_barrier_after_bb (basic_block bb)
1455 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1456 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1457 || current_ir_type () == IR_RTL_CFGLAYOUT);
1458 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1460 rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1462 if (BB_FOOTER (bb))
1464 rtx_insn *footer_tail = BB_FOOTER (bb);
1466 while (NEXT_INSN (footer_tail))
1467 footer_tail = NEXT_INSN (footer_tail);
1468 if (!BARRIER_P (footer_tail))
1470 SET_NEXT_INSN (footer_tail) = insn;
1471 SET_PREV_INSN (insn) = footer_tail;
1474 else
1475 BB_FOOTER (bb) = insn;
1479 /* Like force_nonfallthru below, but additionally performs redirection
1480 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1481 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1482 simple_return_rtx, indicating which kind of returnjump to create.
1483 It should be NULL otherwise. */
1485 basic_block
1486 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1488 basic_block jump_block, new_bb = NULL, src = e->src;
1489 rtx note;
1490 edge new_edge;
1491 int abnormal_edge_flags = 0;
1492 bool asm_goto_edge = false;
1493 int loc;
1495 /* In the case the last instruction is conditional jump to the next
1496 instruction, first redirect the jump itself and then continue
1497 by creating a basic block afterwards to redirect fallthru edge. */
1498 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1499 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1500 && any_condjump_p (BB_END (e->src))
1501 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1503 rtx note;
1504 edge b = unchecked_make_edge (e->src, target, 0);
1505 bool redirected;
1507 redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1508 block_label (target), 0);
1509 gcc_assert (redirected);
1511 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1512 if (note)
1514 int prob = XINT (note, 0);
1516 b->probability = prob;
1517 /* Update this to use GCOV_COMPUTE_SCALE. */
1518 b->count = e->count * prob / REG_BR_PROB_BASE;
1519 e->probability -= e->probability;
1520 e->count -= b->count;
1521 if (e->probability < 0)
1522 e->probability = 0;
1523 if (e->count < 0)
1524 e->count = 0;
1528 if (e->flags & EDGE_ABNORMAL)
1530 /* Irritating special case - fallthru edge to the same block as abnormal
1531 edge.
1532 We can't redirect abnormal edge, but we still can split the fallthru
1533 one and create separate abnormal edge to original destination.
1534 This allows bb-reorder to make such edge non-fallthru. */
1535 gcc_assert (e->dest == target);
1536 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1537 e->flags &= EDGE_FALLTHRU;
1539 else
1541 gcc_assert (e->flags & EDGE_FALLTHRU);
1542 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1544 /* We can't redirect the entry block. Create an empty block
1545 at the start of the function which we use to add the new
1546 jump. */
1547 edge tmp;
1548 edge_iterator ei;
1549 bool found = false;
1551 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1552 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1554 /* Change the existing edge's source to be the new block, and add
1555 a new edge from the entry block to the new block. */
1556 e->src = bb;
1557 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1558 (tmp = ei_safe_edge (ei)); )
1560 if (tmp == e)
1562 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1563 found = true;
1564 break;
1566 else
1567 ei_next (&ei);
1570 gcc_assert (found);
1572 vec_safe_push (bb->succs, e);
1573 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1574 EDGE_FALLTHRU);
1578 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1579 don't point to the target or fallthru label. */
1580 if (JUMP_P (BB_END (e->src))
1581 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1582 && (e->flags & EDGE_FALLTHRU)
1583 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1585 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1586 bool adjust_jump_target = false;
1588 for (i = 0; i < n; ++i)
1590 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1592 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1593 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1594 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1595 adjust_jump_target = true;
1597 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1598 asm_goto_edge = true;
1600 if (adjust_jump_target)
1602 rtx_insn *insn = BB_END (e->src);
1603 rtx note;
1604 rtx_insn *old_label = BB_HEAD (e->dest);
1605 rtx_insn *new_label = BB_HEAD (target);
1607 if (JUMP_LABEL (insn) == old_label)
1609 JUMP_LABEL (insn) = new_label;
1610 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1611 if (note)
1612 remove_note (insn, note);
1614 else
1616 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1617 if (note)
1618 remove_note (insn, note);
1619 if (JUMP_LABEL (insn) != new_label
1620 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1621 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1623 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1624 != NULL_RTX)
1625 XEXP (note, 0) = new_label;
1629 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1631 rtx_insn *new_head;
1632 gcov_type count = e->count;
1633 int probability = e->probability;
1634 /* Create the new structures. */
1636 /* If the old block ended with a tablejump, skip its table
1637 by searching forward from there. Otherwise start searching
1638 forward from the last instruction of the old block. */
1639 rtx_jump_table_data *table;
1640 if (tablejump_p (BB_END (e->src), NULL, &table))
1641 new_head = table;
1642 else
1643 new_head = BB_END (e->src);
1644 new_head = NEXT_INSN (new_head);
1646 jump_block = create_basic_block (new_head, NULL, e->src);
1647 jump_block->count = count;
1648 jump_block->frequency = EDGE_FREQUENCY (e);
1650 /* Make sure new block ends up in correct hot/cold section. */
1652 BB_COPY_PARTITION (jump_block, e->src);
1654 /* Wire edge in. */
1655 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1656 new_edge->probability = probability;
1657 new_edge->count = count;
1659 /* Redirect old edge. */
1660 redirect_edge_pred (e, jump_block);
1661 e->probability = REG_BR_PROB_BASE;
1663 /* If e->src was previously region crossing, it no longer is
1664 and the reg crossing note should be removed. */
1665 fixup_partition_crossing (new_edge);
1667 /* If asm goto has any label refs to target's label,
1668 add also edge from asm goto bb to target. */
1669 if (asm_goto_edge)
1671 new_edge->probability /= 2;
1672 new_edge->count /= 2;
1673 jump_block->count /= 2;
1674 jump_block->frequency /= 2;
1675 new_edge = make_edge (new_edge->src, target,
1676 e->flags & ~EDGE_FALLTHRU);
1677 new_edge->probability = probability - probability / 2;
1678 new_edge->count = count - count / 2;
1681 new_bb = jump_block;
1683 else
1684 jump_block = e->src;
1686 loc = e->goto_locus;
1687 e->flags &= ~EDGE_FALLTHRU;
1688 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1690 if (jump_label == ret_rtx)
1691 emit_jump_insn_after_setloc (targetm.gen_return (),
1692 BB_END (jump_block), loc);
1693 else
1695 gcc_assert (jump_label == simple_return_rtx);
1696 emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1697 BB_END (jump_block), loc);
1699 set_return_jump_label (BB_END (jump_block));
1701 else
1703 rtx_code_label *label = block_label (target);
1704 emit_jump_insn_after_setloc (targetm.gen_jump (label),
1705 BB_END (jump_block), loc);
1706 JUMP_LABEL (BB_END (jump_block)) = label;
1707 LABEL_NUSES (label)++;
1710 /* We might be in cfg layout mode, and if so, the following routine will
1711 insert the barrier correctly. */
1712 emit_barrier_after_bb (jump_block);
1713 redirect_edge_succ_nodup (e, target);
1715 if (abnormal_edge_flags)
1716 make_edge (src, target, abnormal_edge_flags);
1718 df_mark_solutions_dirty ();
1719 fixup_partition_crossing (e);
1720 return new_bb;
1723 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1724 (and possibly create new basic block) to make edge non-fallthru.
1725 Return newly created BB or NULL if none. */
1727 static basic_block
1728 rtl_force_nonfallthru (edge e)
1730 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1733 /* Redirect edge even at the expense of creating new jump insn or
1734 basic block. Return new basic block if created, NULL otherwise.
1735 Conversion must be possible. */
1737 static basic_block
1738 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1740 if (redirect_edge_and_branch (e, target)
1741 || e->dest == target)
1742 return NULL;
1744 /* In case the edge redirection failed, try to force it to be non-fallthru
1745 and redirect newly created simplejump. */
1746 df_set_bb_dirty (e->src);
1747 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1750 /* The given edge should potentially be a fallthru edge. If that is in
1751 fact true, delete the jump and barriers that are in the way. */
1753 static void
1754 rtl_tidy_fallthru_edge (edge e)
1756 rtx_insn *q;
1757 basic_block b = e->src, c = b->next_bb;
1759 /* ??? In a late-running flow pass, other folks may have deleted basic
1760 blocks by nopping out blocks, leaving multiple BARRIERs between here
1761 and the target label. They ought to be chastised and fixed.
1763 We can also wind up with a sequence of undeletable labels between
1764 one block and the next.
1766 So search through a sequence of barriers, labels, and notes for
1767 the head of block C and assert that we really do fall through. */
1769 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1770 if (INSN_P (q))
1771 return;
1773 /* Remove what will soon cease being the jump insn from the source block.
1774 If block B consisted only of this single jump, turn it into a deleted
1775 note. */
1776 q = BB_END (b);
1777 if (JUMP_P (q)
1778 && onlyjump_p (q)
1779 && (any_uncondjump_p (q)
1780 || single_succ_p (b)))
1782 rtx label;
1783 rtx_jump_table_data *table;
1785 if (tablejump_p (q, &label, &table))
1787 /* The label is likely mentioned in some instruction before
1788 the tablejump and might not be DCEd, so turn it into
1789 a note instead and move before the tablejump that is going to
1790 be deleted. */
1791 const char *name = LABEL_NAME (label);
1792 PUT_CODE (label, NOTE);
1793 NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1794 NOTE_DELETED_LABEL_NAME (label) = name;
1795 rtx_insn *lab = safe_as_a <rtx_insn *> (label);
1796 reorder_insns (lab, lab, PREV_INSN (q));
1797 delete_insn (table);
1800 /* If this was a conditional jump, we need to also delete
1801 the insn that set cc0. */
1802 if (HAVE_cc0 && any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1803 q = PREV_INSN (q);
1805 q = PREV_INSN (q);
1808 /* Selectively unlink the sequence. */
1809 if (q != PREV_INSN (BB_HEAD (c)))
1810 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1812 e->flags |= EDGE_FALLTHRU;
1815 /* Should move basic block BB after basic block AFTER. NIY. */
1817 static bool
1818 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1819 basic_block after ATTRIBUTE_UNUSED)
1821 return false;
1824 /* Locate the last bb in the same partition as START_BB. */
1826 static basic_block
1827 last_bb_in_partition (basic_block start_bb)
1829 basic_block bb;
1830 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1832 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1833 return bb;
1835 /* Return bb before the exit block. */
1836 return bb->prev_bb;
1839 /* Split a (typically critical) edge. Return the new block.
1840 The edge must not be abnormal.
1842 ??? The code generally expects to be called on critical edges.
1843 The case of a block ending in an unconditional jump to a
1844 block with multiple predecessors is not handled optimally. */
1846 static basic_block
1847 rtl_split_edge (edge edge_in)
1849 basic_block bb, new_bb;
1850 rtx_insn *before;
1852 /* Abnormal edges cannot be split. */
1853 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1855 /* We are going to place the new block in front of edge destination.
1856 Avoid existence of fallthru predecessors. */
1857 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1859 edge e = find_fallthru_edge (edge_in->dest->preds);
1861 if (e)
1862 force_nonfallthru (e);
1865 /* Create the basic block note. */
1866 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1867 before = BB_HEAD (edge_in->dest);
1868 else
1869 before = NULL;
1871 /* If this is a fall through edge to the exit block, the blocks might be
1872 not adjacent, and the right place is after the source. */
1873 if ((edge_in->flags & EDGE_FALLTHRU)
1874 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1876 before = NEXT_INSN (BB_END (edge_in->src));
1877 bb = create_basic_block (before, NULL, edge_in->src);
1878 BB_COPY_PARTITION (bb, edge_in->src);
1880 else
1882 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1884 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1885 BB_COPY_PARTITION (bb, edge_in->dest);
1887 else
1889 basic_block after = edge_in->dest->prev_bb;
1890 /* If this is post-bb reordering, and the edge crosses a partition
1891 boundary, the new block needs to be inserted in the bb chain
1892 at the end of the src partition (since we put the new bb into
1893 that partition, see below). Otherwise we may end up creating
1894 an extra partition crossing in the chain, which is illegal.
1895 It can't go after the src, because src may have a fall-through
1896 to a different block. */
1897 if (crtl->bb_reorder_complete
1898 && (edge_in->flags & EDGE_CROSSING))
1900 after = last_bb_in_partition (edge_in->src);
1901 before = get_last_bb_insn (after);
1902 /* The instruction following the last bb in partition should
1903 be a barrier, since it cannot end in a fall-through. */
1904 gcc_checking_assert (BARRIER_P (before));
1905 before = NEXT_INSN (before);
1907 bb = create_basic_block (before, NULL, after);
1908 /* Put the split bb into the src partition, to avoid creating
1909 a situation where a cold bb dominates a hot bb, in the case
1910 where src is cold and dest is hot. The src will dominate
1911 the new bb (whereas it might not have dominated dest). */
1912 BB_COPY_PARTITION (bb, edge_in->src);
1916 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1918 /* Can't allow a region crossing edge to be fallthrough. */
1919 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1920 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1922 new_bb = force_nonfallthru (single_succ_edge (bb));
1923 gcc_assert (!new_bb);
1926 /* For non-fallthru edges, we must adjust the predecessor's
1927 jump instruction to target our new block. */
1928 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1930 edge redirected = redirect_edge_and_branch (edge_in, bb);
1931 gcc_assert (redirected);
1933 else
1935 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1937 /* For asm goto even splitting of fallthru edge might
1938 need insn patching, as other labels might point to the
1939 old label. */
1940 rtx_insn *last = BB_END (edge_in->src);
1941 if (last
1942 && JUMP_P (last)
1943 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1944 && extract_asm_operands (PATTERN (last)) != NULL_RTX
1945 && patch_jump_insn (last, before, bb))
1946 df_set_bb_dirty (edge_in->src);
1948 redirect_edge_succ (edge_in, bb);
1951 return bb;
1954 /* Queue instructions for insertion on an edge between two basic blocks.
1955 The new instructions and basic blocks (if any) will not appear in the
1956 CFG until commit_edge_insertions is called. */
1958 void
1959 insert_insn_on_edge (rtx pattern, edge e)
1961 /* We cannot insert instructions on an abnormal critical edge.
1962 It will be easier to find the culprit if we die now. */
1963 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1965 if (e->insns.r == NULL_RTX)
1966 start_sequence ();
1967 else
1968 push_to_sequence (e->insns.r);
1970 emit_insn (pattern);
1972 e->insns.r = get_insns ();
1973 end_sequence ();
1976 /* Update the CFG for the instructions queued on edge E. */
1978 void
1979 commit_one_edge_insertion (edge e)
1981 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1982 basic_block bb;
1984 /* Pull the insns off the edge now since the edge might go away. */
1985 insns = e->insns.r;
1986 e->insns.r = NULL;
1988 /* Figure out where to put these insns. If the destination has
1989 one predecessor, insert there. Except for the exit block. */
1990 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1992 bb = e->dest;
1994 /* Get the location correct wrt a code label, and "nice" wrt
1995 a basic block note, and before everything else. */
1996 tmp = BB_HEAD (bb);
1997 if (LABEL_P (tmp))
1998 tmp = NEXT_INSN (tmp);
1999 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
2000 tmp = NEXT_INSN (tmp);
2001 if (tmp == BB_HEAD (bb))
2002 before = tmp;
2003 else if (tmp)
2004 after = PREV_INSN (tmp);
2005 else
2006 after = get_last_insn ();
2009 /* If the source has one successor and the edge is not abnormal,
2010 insert there. Except for the entry block.
2011 Don't do this if the predecessor ends in a jump other than
2012 unconditional simple jump. E.g. for asm goto that points all
2013 its labels at the fallthru basic block, we can't insert instructions
2014 before the asm goto, as the asm goto can have various of side effects,
2015 and can't emit instructions after the asm goto, as it must end
2016 the basic block. */
2017 else if ((e->flags & EDGE_ABNORMAL) == 0
2018 && single_succ_p (e->src)
2019 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2020 && (!JUMP_P (BB_END (e->src))
2021 || simplejump_p (BB_END (e->src))))
2023 bb = e->src;
2025 /* It is possible to have a non-simple jump here. Consider a target
2026 where some forms of unconditional jumps clobber a register. This
2027 happens on the fr30 for example.
2029 We know this block has a single successor, so we can just emit
2030 the queued insns before the jump. */
2031 if (JUMP_P (BB_END (bb)))
2032 before = BB_END (bb);
2033 else
2035 /* We'd better be fallthru, or we've lost track of what's what. */
2036 gcc_assert (e->flags & EDGE_FALLTHRU);
2038 after = BB_END (bb);
2042 /* Otherwise we must split the edge. */
2043 else
2045 bb = split_edge (e);
2047 /* If E crossed a partition boundary, we needed to make bb end in
2048 a region-crossing jump, even though it was originally fallthru. */
2049 if (JUMP_P (BB_END (bb)))
2050 before = BB_END (bb);
2051 else
2052 after = BB_END (bb);
2055 /* Now that we've found the spot, do the insertion. */
2056 if (before)
2058 emit_insn_before_noloc (insns, before, bb);
2059 last = prev_nonnote_insn (before);
2061 else
2062 last = emit_insn_after_noloc (insns, after, bb);
2064 if (returnjump_p (last))
2066 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2067 This is not currently a problem because this only happens
2068 for the (single) epilogue, which already has a fallthru edge
2069 to EXIT. */
2071 e = single_succ_edge (bb);
2072 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2073 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2075 e->flags &= ~EDGE_FALLTHRU;
2076 emit_barrier_after (last);
2078 if (before)
2079 delete_insn (before);
2081 else
2082 gcc_assert (!JUMP_P (last));
2085 /* Update the CFG for all queued instructions. */
2087 void
2088 commit_edge_insertions (void)
2090 basic_block bb;
2092 /* Optimization passes that invoke this routine can cause hot blocks
2093 previously reached by both hot and cold blocks to become dominated only
2094 by cold blocks. This will cause the verification below to fail,
2095 and lead to now cold code in the hot section. In some cases this
2096 may only be visible after newly unreachable blocks are deleted,
2097 which will be done by fixup_partitions. */
2098 fixup_partitions ();
2100 #ifdef ENABLE_CHECKING
2101 verify_flow_info ();
2102 #endif
2104 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2105 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2107 edge e;
2108 edge_iterator ei;
2110 FOR_EACH_EDGE (e, ei, bb->succs)
2111 if (e->insns.r)
2112 commit_one_edge_insertion (e);
2117 /* Print out RTL-specific basic block information (live information
2118 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2119 documented in dumpfile.h. */
2121 static void
2122 rtl_dump_bb (FILE *outf, basic_block bb, int indent, int flags)
2124 rtx_insn *insn;
2125 rtx_insn *last;
2126 char *s_indent;
2128 s_indent = (char *) alloca ((size_t) indent + 1);
2129 memset (s_indent, ' ', (size_t) indent);
2130 s_indent[indent] = '\0';
2132 if (df && (flags & TDF_DETAILS))
2134 df_dump_top (bb, outf);
2135 putc ('\n', outf);
2138 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK)
2139 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
2140 insn = NEXT_INSN (insn))
2142 if (flags & TDF_DETAILS)
2143 df_dump_insn_top (insn, outf);
2144 if (! (flags & TDF_SLIM))
2145 print_rtl_single (outf, insn);
2146 else
2147 dump_insn_slim (outf, insn);
2148 if (flags & TDF_DETAILS)
2149 df_dump_insn_bottom (insn, outf);
2152 if (df && (flags & TDF_DETAILS))
2154 df_dump_bottom (bb, outf);
2155 putc ('\n', outf);
2160 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2161 for the start of each basic block. FLAGS are the TDF_* masks documented
2162 in dumpfile.h. */
2164 void
2165 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, int flags)
2167 const rtx_insn *tmp_rtx;
2168 if (rtx_first == 0)
2169 fprintf (outf, "(nil)\n");
2170 else
2172 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2173 int max_uid = get_max_uid ();
2174 basic_block *start = XCNEWVEC (basic_block, max_uid);
2175 basic_block *end = XCNEWVEC (basic_block, max_uid);
2176 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2177 basic_block bb;
2179 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2180 insns, but the CFG is not maintained so the basic block info
2181 is not reliable. Therefore it's omitted from the dumps. */
2182 if (! (cfun->curr_properties & PROP_cfg))
2183 flags &= ~TDF_BLOCKS;
2185 if (df)
2186 df_dump_start (outf);
2188 if (flags & TDF_BLOCKS)
2190 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2192 rtx_insn *x;
2194 start[INSN_UID (BB_HEAD (bb))] = bb;
2195 end[INSN_UID (BB_END (bb))] = bb;
2196 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2198 enum bb_state state = IN_MULTIPLE_BB;
2200 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2201 state = IN_ONE_BB;
2202 in_bb_p[INSN_UID (x)] = state;
2204 if (x == BB_END (bb))
2205 break;
2210 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
2212 if (flags & TDF_BLOCKS)
2214 bb = start[INSN_UID (tmp_rtx)];
2215 if (bb != NULL)
2217 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, true, false);
2218 if (df && (flags & TDF_DETAILS))
2219 df_dump_top (bb, outf);
2222 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2223 && !NOTE_P (tmp_rtx)
2224 && !BARRIER_P (tmp_rtx))
2225 fprintf (outf, ";; Insn is not within a basic block\n");
2226 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2227 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2230 if (flags & TDF_DETAILS)
2231 df_dump_insn_top (tmp_rtx, outf);
2232 if (! (flags & TDF_SLIM))
2233 print_rtl_single (outf, tmp_rtx);
2234 else
2235 dump_insn_slim (outf, tmp_rtx);
2236 if (flags & TDF_DETAILS)
2237 df_dump_insn_bottom (tmp_rtx, outf);
2239 if (flags & TDF_BLOCKS)
2241 bb = end[INSN_UID (tmp_rtx)];
2242 if (bb != NULL)
2244 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, false, true);
2245 if (df && (flags & TDF_DETAILS))
2246 df_dump_bottom (bb, outf);
2247 putc ('\n', outf);
2252 free (start);
2253 free (end);
2254 free (in_bb_p);
2258 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2260 void
2261 update_br_prob_note (basic_block bb)
2263 rtx note;
2264 if (!JUMP_P (BB_END (bb)))
2265 return;
2266 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2267 if (!note || XINT (note, 0) == BRANCH_EDGE (bb)->probability)
2268 return;
2269 XINT (note, 0) = BRANCH_EDGE (bb)->probability;
2272 /* Get the last insn associated with block BB (that includes barriers and
2273 tablejumps after BB). */
2274 rtx_insn *
2275 get_last_bb_insn (basic_block bb)
2277 rtx_jump_table_data *table;
2278 rtx_insn *tmp;
2279 rtx_insn *end = BB_END (bb);
2281 /* Include any jump table following the basic block. */
2282 if (tablejump_p (end, NULL, &table))
2283 end = table;
2285 /* Include any barriers that may follow the basic block. */
2286 tmp = next_nonnote_insn_bb (end);
2287 while (tmp && BARRIER_P (tmp))
2289 end = tmp;
2290 tmp = next_nonnote_insn_bb (end);
2293 return end;
2296 /* Sanity check partition hotness to ensure that basic blocks in
2297   the cold partition don't dominate basic blocks in the hot partition.
2298 If FLAG_ONLY is true, report violations as errors. Otherwise
2299 re-mark the dominated blocks as cold, since this is run after
2300 cfg optimizations that may make hot blocks previously reached
2301 by both hot and cold blocks now only reachable along cold paths. */
2303 static vec<basic_block>
2304 find_partition_fixes (bool flag_only)
2306 basic_block bb;
2307 vec<basic_block> bbs_in_cold_partition = vNULL;
2308 vec<basic_block> bbs_to_fix = vNULL;
2310 /* Callers check this. */
2311 gcc_checking_assert (crtl->has_bb_partition);
2313 FOR_EACH_BB_FN (bb, cfun)
2314 if ((BB_PARTITION (bb) == BB_COLD_PARTITION))
2315 bbs_in_cold_partition.safe_push (bb);
2317 if (bbs_in_cold_partition.is_empty ())
2318 return vNULL;
2320 bool dom_calculated_here = !dom_info_available_p (CDI_DOMINATORS);
2322 if (dom_calculated_here)
2323 calculate_dominance_info (CDI_DOMINATORS);
2325 while (! bbs_in_cold_partition.is_empty ())
2327 bb = bbs_in_cold_partition.pop ();
2328 /* Any blocks dominated by a block in the cold section
2329 must also be cold. */
2330 basic_block son;
2331 for (son = first_dom_son (CDI_DOMINATORS, bb);
2332 son;
2333 son = next_dom_son (CDI_DOMINATORS, son))
2335 /* If son is not yet cold, then mark it cold here and
2336 enqueue it for further processing. */
2337 if ((BB_PARTITION (son) != BB_COLD_PARTITION))
2339 if (flag_only)
2340 error ("non-cold basic block %d dominated "
2341 "by a block in the cold partition (%d)", son->index, bb->index);
2342 else
2343 BB_SET_PARTITION (son, BB_COLD_PARTITION);
2344 bbs_to_fix.safe_push (son);
2345 bbs_in_cold_partition.safe_push (son);
2350 if (dom_calculated_here)
2351 free_dominance_info (CDI_DOMINATORS);
2353 return bbs_to_fix;
2356 /* Perform cleanup on the hot/cold bb partitioning after optimization
2357 passes that modify the cfg. */
2359 void
2360 fixup_partitions (void)
2362 basic_block bb;
2364 if (!crtl->has_bb_partition)
2365 return;
2367 /* Delete any blocks that became unreachable and weren't
2368 already cleaned up, for example during edge forwarding
2369 and convert_jumps_to_returns. This will expose more
2370 opportunities for fixing the partition boundaries here.
2371 Also, the calculation of the dominance graph during verification
2372 will assert if there are unreachable nodes. */
2373 delete_unreachable_blocks ();
2375 /* If there are partitions, do a sanity check on them: A basic block in
2376   a cold partition cannot dominate a basic block in a hot partition.
2377 Fixup any that now violate this requirement, as a result of edge
2378 forwarding and unreachable block deletion.  */
2379 vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2381 /* Do the partition fixup after all necessary blocks have been converted to
2382 cold, so that we only update the region crossings the minimum number of
2383 places, which can require forcing edges to be non fallthru. */
2384 while (! bbs_to_fix.is_empty ())
2386 bb = bbs_to_fix.pop ();
2387 fixup_new_cold_bb (bb);
2391 /* Verify, in the basic block chain, that there is at most one switch
2392 between hot/cold partitions. This condition will not be true until
2393 after reorder_basic_blocks is called. */
2395 static int
2396 verify_hot_cold_block_grouping (void)
2398 basic_block bb;
2399 int err = 0;
2400 bool switched_sections = false;
2401 int current_partition = BB_UNPARTITIONED;
2403 /* Even after bb reordering is complete, we go into cfglayout mode
2404 again (in compgoto). Ensure we don't call this before going back
2405 into linearized RTL when any layout fixes would have been committed. */
2406 if (!crtl->bb_reorder_complete
2407 || current_ir_type () != IR_RTL_CFGRTL)
2408 return err;
2410 FOR_EACH_BB_FN (bb, cfun)
2412 if (current_partition != BB_UNPARTITIONED
2413 && BB_PARTITION (bb) != current_partition)
2415 if (switched_sections)
2417 error ("multiple hot/cold transitions found (bb %i)",
2418 bb->index);
2419 err = 1;
2421 else
2422 switched_sections = true;
2424 if (!crtl->has_bb_partition)
2425 error ("partition found but function partition flag not set");
2427 current_partition = BB_PARTITION (bb);
2430 return err;
2434 /* Perform several checks on the edges out of each block, such as
2435 the consistency of the branch probabilities, the correctness
2436 of hot/cold partition crossing edges, and the number of expected
2437 successor edges. Also verify that the dominance relationship
2438 between hot/cold blocks is sane. */
2440 static int
2441 rtl_verify_edges (void)
2443 int err = 0;
2444 basic_block bb;
2446 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2448 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2449 int n_eh = 0, n_abnormal = 0;
2450 edge e, fallthru = NULL;
2451 edge_iterator ei;
2452 rtx note;
2453 bool has_crossing_edge = false;
2455 if (JUMP_P (BB_END (bb))
2456 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2457 && EDGE_COUNT (bb->succs) >= 2
2458 && any_condjump_p (BB_END (bb)))
2460 if (XINT (note, 0) != BRANCH_EDGE (bb)->probability
2461 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2463 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2464 XINT (note, 0), BRANCH_EDGE (bb)->probability);
2465 err = 1;
2469 FOR_EACH_EDGE (e, ei, bb->succs)
2471 bool is_crossing;
2473 if (e->flags & EDGE_FALLTHRU)
2474 n_fallthru++, fallthru = e;
2476 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2477 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2478 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2479 has_crossing_edge |= is_crossing;
2480 if (e->flags & EDGE_CROSSING)
2482 if (!is_crossing)
2484 error ("EDGE_CROSSING incorrectly set across same section");
2485 err = 1;
2487 if (e->flags & EDGE_FALLTHRU)
2489 error ("fallthru edge crosses section boundary in bb %i",
2490 e->src->index);
2491 err = 1;
2493 if (e->flags & EDGE_EH)
2495 error ("EH edge crosses section boundary in bb %i",
2496 e->src->index);
2497 err = 1;
2499 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2501 error ("No region crossing jump at section boundary in bb %i",
2502 bb->index);
2503 err = 1;
2506 else if (is_crossing)
2508 error ("EDGE_CROSSING missing across section boundary");
2509 err = 1;
2512 if ((e->flags & ~(EDGE_DFS_BACK
2513 | EDGE_CAN_FALLTHRU
2514 | EDGE_IRREDUCIBLE_LOOP
2515 | EDGE_LOOP_EXIT
2516 | EDGE_CROSSING
2517 | EDGE_PRESERVE)) == 0)
2518 n_branch++;
2520 if (e->flags & EDGE_ABNORMAL_CALL)
2521 n_abnormal_call++;
2523 if (e->flags & EDGE_SIBCALL)
2524 n_sibcall++;
2526 if (e->flags & EDGE_EH)
2527 n_eh++;
2529 if (e->flags & EDGE_ABNORMAL)
2530 n_abnormal++;
2533 if (!has_crossing_edge
2534 && JUMP_P (BB_END (bb))
2535 && CROSSING_JUMP_P (BB_END (bb)))
2537 print_rtl_with_bb (stderr, get_insns (), TDF_RTL | TDF_BLOCKS | TDF_DETAILS);
2538 error ("Region crossing jump across same section in bb %i",
2539 bb->index);
2540 err = 1;
2543 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2545 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2546 err = 1;
2548 if (n_eh > 1)
2550 error ("too many exception handling edges in bb %i", bb->index);
2551 err = 1;
2553 if (n_branch
2554 && (!JUMP_P (BB_END (bb))
2555 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2556 || any_condjump_p (BB_END (bb))))))
2558 error ("too many outgoing branch edges from bb %i", bb->index);
2559 err = 1;
2561 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2563 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2564 err = 1;
2566 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2568 error ("wrong number of branch edges after unconditional jump"
2569 " in bb %i", bb->index);
2570 err = 1;
2572 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2573 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2575 error ("wrong amount of branch edges after conditional jump"
2576 " in bb %i", bb->index);
2577 err = 1;
2579 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2581 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2582 err = 1;
2584 if (n_sibcall && !CALL_P (BB_END (bb)))
2586 error ("sibcall edges for non-call insn in bb %i", bb->index);
2587 err = 1;
2589 if (n_abnormal > n_eh
2590 && !(CALL_P (BB_END (bb))
2591 && n_abnormal == n_abnormal_call + n_sibcall)
2592 && (!JUMP_P (BB_END (bb))
2593 || any_condjump_p (BB_END (bb))
2594 || any_uncondjump_p (BB_END (bb))))
2596 error ("abnormal edges for no purpose in bb %i", bb->index);
2597 err = 1;
2601 /* If there are partitions, do a sanity check on them: A basic block in
2602   a cold partition cannot dominate a basic block in a hot partition.  */
2603 if (crtl->has_bb_partition && !err)
2605 vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2606 err = !bbs_to_fix.is_empty ();
2609 /* Clean up. */
2610 return err;
2613 /* Checks on the instructions within blocks. Currently checks that each
2614 block starts with a basic block note, and that basic block notes and
2615 control flow jumps are not found in the middle of the block. */
2617 static int
2618 rtl_verify_bb_insns (void)
2620 rtx_insn *x;
2621 int err = 0;
2622 basic_block bb;
2624 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2626 /* Now check the header of basic
2627 block. It ought to contain optional CODE_LABEL followed
2628 by NOTE_BASIC_BLOCK. */
2629 x = BB_HEAD (bb);
2630 if (LABEL_P (x))
2632 if (BB_END (bb) == x)
2634 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2635 bb->index);
2636 err = 1;
2639 x = NEXT_INSN (x);
2642 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2644 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2645 bb->index);
2646 err = 1;
2649 if (BB_END (bb) == x)
2650 /* Do checks for empty blocks here. */
2652 else
2653 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2655 if (NOTE_INSN_BASIC_BLOCK_P (x))
2657 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2658 INSN_UID (x), bb->index);
2659 err = 1;
2662 if (x == BB_END (bb))
2663 break;
2665 if (control_flow_insn_p (x))
2667 error ("in basic block %d:", bb->index);
2668 fatal_insn ("flow control insn inside a basic block", x);
2673 /* Clean up. */
2674 return err;
2677 /* Verify that block pointers for instructions in basic blocks, headers and
2678 footers are set appropriately. */
2680 static int
2681 rtl_verify_bb_pointers (void)
2683 int err = 0;
2684 basic_block bb;
2686 /* Check the general integrity of the basic blocks. */
2687 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2689 rtx_insn *insn;
2691 if (!(bb->flags & BB_RTL))
2693 error ("BB_RTL flag not set for block %d", bb->index);
2694 err = 1;
2697 FOR_BB_INSNS (bb, insn)
2698 if (BLOCK_FOR_INSN (insn) != bb)
2700 error ("insn %d basic block pointer is %d, should be %d",
2701 INSN_UID (insn),
2702 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2703 bb->index);
2704 err = 1;
2707 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2708 if (!BARRIER_P (insn)
2709 && BLOCK_FOR_INSN (insn) != NULL)
2711 error ("insn %d in header of bb %d has non-NULL basic block",
2712 INSN_UID (insn), bb->index);
2713 err = 1;
2715 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2716 if (!BARRIER_P (insn)
2717 && BLOCK_FOR_INSN (insn) != NULL)
2719 error ("insn %d in footer of bb %d has non-NULL basic block",
2720 INSN_UID (insn), bb->index);
2721 err = 1;
2725 /* Clean up. */
2726 return err;
2729 /* Verify the CFG and RTL consistency common for both underlying RTL and
2730 cfglayout RTL.
2732 Currently it does following checks:
2734 - overlapping of basic blocks
2735 - insns with wrong BLOCK_FOR_INSN pointers
2736 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2737 - tails of basic blocks (ensure that boundary is necessary)
2738 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2739 and NOTE_INSN_BASIC_BLOCK
2740 - verify that no fall_thru edge crosses hot/cold partition boundaries
2741 - verify that there are no pending RTL branch predictions
2742 - verify that hot blocks are not dominated by cold blocks
2744 In future it can be extended check a lot of other stuff as well
2745 (reachability of basic blocks, life information, etc. etc.). */
2747 static int
2748 rtl_verify_flow_info_1 (void)
2750 int err = 0;
2752 err |= rtl_verify_bb_pointers ();
2754 err |= rtl_verify_bb_insns ();
2756 err |= rtl_verify_edges ();
2758 return err;
2761 /* Walk the instruction chain and verify that bb head/end pointers
2762 are correct, and that instructions are in exactly one bb and have
2763 correct block pointers. */
2765 static int
2766 rtl_verify_bb_insn_chain (void)
2768 basic_block bb;
2769 int err = 0;
2770 rtx_insn *x;
2771 rtx_insn *last_head = get_last_insn ();
2772 basic_block *bb_info;
2773 const int max_uid = get_max_uid ();
2775 bb_info = XCNEWVEC (basic_block, max_uid);
2777 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2779 rtx_insn *head = BB_HEAD (bb);
2780 rtx_insn *end = BB_END (bb);
2782 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2784 /* Verify the end of the basic block is in the INSN chain. */
2785 if (x == end)
2786 break;
2788 /* And that the code outside of basic blocks has NULL bb field. */
2789 if (!BARRIER_P (x)
2790 && BLOCK_FOR_INSN (x) != NULL)
2792 error ("insn %d outside of basic blocks has non-NULL bb field",
2793 INSN_UID (x));
2794 err = 1;
2798 if (!x)
2800 error ("end insn %d for block %d not found in the insn stream",
2801 INSN_UID (end), bb->index);
2802 err = 1;
2805 /* Work backwards from the end to the head of the basic block
2806 to verify the head is in the RTL chain. */
2807 for (; x != NULL_RTX; x = PREV_INSN (x))
2809 /* While walking over the insn chain, verify insns appear
2810 in only one basic block. */
2811 if (bb_info[INSN_UID (x)] != NULL)
2813 error ("insn %d is in multiple basic blocks (%d and %d)",
2814 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2815 err = 1;
2818 bb_info[INSN_UID (x)] = bb;
2820 if (x == head)
2821 break;
2823 if (!x)
2825 error ("head insn %d for block %d not found in the insn stream",
2826 INSN_UID (head), bb->index);
2827 err = 1;
2830 last_head = PREV_INSN (x);
2833 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2835 /* Check that the code before the first basic block has NULL
2836 bb field. */
2837 if (!BARRIER_P (x)
2838 && BLOCK_FOR_INSN (x) != NULL)
2840 error ("insn %d outside of basic blocks has non-NULL bb field",
2841 INSN_UID (x));
2842 err = 1;
2845 free (bb_info);
2847 return err;
2850 /* Verify that fallthru edges point to adjacent blocks in layout order and
2851 that barriers exist after non-fallthru blocks. */
2853 static int
2854 rtl_verify_fallthru (void)
2856 basic_block bb;
2857 int err = 0;
2859 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2861 edge e;
2863 e = find_fallthru_edge (bb->succs);
2864 if (!e)
2866 rtx_insn *insn;
2868 /* Ensure existence of barrier in BB with no fallthru edges. */
2869 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
2871 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
2873 error ("missing barrier after block %i", bb->index);
2874 err = 1;
2875 break;
2877 if (BARRIER_P (insn))
2878 break;
2881 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2882 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2884 rtx_insn *insn;
2886 if (e->src->next_bb != e->dest)
2888 error
2889 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2890 e->src->index, e->dest->index);
2891 err = 1;
2893 else
2894 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2895 insn = NEXT_INSN (insn))
2896 if (BARRIER_P (insn) || INSN_P (insn))
2898 error ("verify_flow_info: Incorrect fallthru %i->%i",
2899 e->src->index, e->dest->index);
2900 fatal_insn ("wrong insn in the fallthru edge", insn);
2901 err = 1;
2906 return err;
2909 /* Verify that blocks are laid out in consecutive order. While walking the
2910 instructions, verify that all expected instructions are inside the basic
2911 blocks, and that all returns are followed by barriers. */
2913 static int
2914 rtl_verify_bb_layout (void)
2916 basic_block bb;
2917 int err = 0;
2918 rtx_insn *x;
2919 int num_bb_notes;
2920 rtx_insn * const rtx_first = get_insns ();
2921 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
2923 num_bb_notes = 0;
2924 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
2926 for (x = rtx_first; x; x = NEXT_INSN (x))
2928 if (NOTE_INSN_BASIC_BLOCK_P (x))
2930 bb = NOTE_BASIC_BLOCK (x);
2932 num_bb_notes++;
2933 if (bb != last_bb_seen->next_bb)
2934 internal_error ("basic blocks not laid down consecutively");
2936 curr_bb = last_bb_seen = bb;
2939 if (!curr_bb)
2941 switch (GET_CODE (x))
2943 case BARRIER:
2944 case NOTE:
2945 break;
2947 case CODE_LABEL:
2948 /* An ADDR_VEC is placed outside any basic block. */
2949 if (NEXT_INSN (x)
2950 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
2951 x = NEXT_INSN (x);
2953 /* But in any case, non-deletable labels can appear anywhere. */
2954 break;
2956 default:
2957 fatal_insn ("insn outside basic block", x);
2961 if (JUMP_P (x)
2962 && returnjump_p (x) && ! condjump_p (x)
2963 && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_insn (x))))
2964 fatal_insn ("return not followed by barrier", x);
2966 if (curr_bb && x == BB_END (curr_bb))
2967 curr_bb = NULL;
2970 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
2971 internal_error
2972 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2973 num_bb_notes, n_basic_blocks_for_fn (cfun));
2975 return err;
2978 /* Verify the CFG and RTL consistency common for both underlying RTL and
2979 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2981 Currently it does following checks:
2982 - all checks of rtl_verify_flow_info_1
2983 - test head/end pointers
2984 - check that blocks are laid out in consecutive order
2985 - check that all insns are in the basic blocks
2986 (except the switch handling code, barriers and notes)
2987 - check that all returns are followed by barriers
2988 - check that all fallthru edge points to the adjacent blocks
2989 - verify that there is a single hot/cold partition boundary after bbro */
2991 static int
2992 rtl_verify_flow_info (void)
2994 int err = 0;
2996 err |= rtl_verify_flow_info_1 ();
2998 err |= rtl_verify_bb_insn_chain ();
3000 err |= rtl_verify_fallthru ();
3002 err |= rtl_verify_bb_layout ();
3004 err |= verify_hot_cold_block_grouping ();
3006 return err;
3009 /* Assume that the preceding pass has possibly eliminated jump instructions
3010 or converted the unconditional jumps. Eliminate the edges from CFG.
3011 Return true if any edges are eliminated. */
3013 bool
3014 purge_dead_edges (basic_block bb)
3016 edge e;
3017 rtx_insn *insn = BB_END (bb);
3018 rtx note;
3019 bool purged = false;
3020 bool found;
3021 edge_iterator ei;
3023 if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb))
3025 insn = PREV_INSN (insn);
3026 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3028 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3029 if (NONJUMP_INSN_P (insn)
3030 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3032 rtx eqnote;
3034 if (! may_trap_p (PATTERN (insn))
3035 || ((eqnote = find_reg_equal_equiv_note (insn))
3036 && ! may_trap_p (XEXP (eqnote, 0))))
3037 remove_note (insn, note);
3040 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3041 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3043 bool remove = false;
3045 /* There are three types of edges we need to handle correctly here: EH
3046 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3047 latter can appear when nonlocal gotos are used. */
3048 if (e->flags & EDGE_ABNORMAL_CALL)
3050 if (!CALL_P (insn))
3051 remove = true;
3052 else if (can_nonlocal_goto (insn))
3054 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3056 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3058 else
3059 remove = true;
3061 else if (e->flags & EDGE_EH)
3062 remove = !can_throw_internal (insn);
3064 if (remove)
3066 remove_edge (e);
3067 df_set_bb_dirty (bb);
3068 purged = true;
3070 else
3071 ei_next (&ei);
3074 if (JUMP_P (insn))
3076 rtx note;
3077 edge b,f;
3078 edge_iterator ei;
3080 /* We do care only about conditional jumps and simplejumps. */
3081 if (!any_condjump_p (insn)
3082 && !returnjump_p (insn)
3083 && !simplejump_p (insn))
3084 return purged;
3086 /* Branch probability/prediction notes are defined only for
3087 condjumps. We've possibly turned condjump into simplejump. */
3088 if (simplejump_p (insn))
3090 note = find_reg_note (insn, REG_BR_PROB, NULL);
3091 if (note)
3092 remove_note (insn, note);
3093 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3094 remove_note (insn, note);
3097 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3099 /* Avoid abnormal flags to leak from computed jumps turned
3100 into simplejumps. */
3102 e->flags &= ~EDGE_ABNORMAL;
3104 /* See if this edge is one we should keep. */
3105 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3106 /* A conditional jump can fall through into the next
3107 block, so we should keep the edge. */
3109 ei_next (&ei);
3110 continue;
3112 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3113 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3114 /* If the destination block is the target of the jump,
3115 keep the edge. */
3117 ei_next (&ei);
3118 continue;
3120 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3121 && returnjump_p (insn))
3122 /* If the destination block is the exit block, and this
3123 instruction is a return, then keep the edge. */
3125 ei_next (&ei);
3126 continue;
3128 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3129 /* Keep the edges that correspond to exceptions thrown by
3130 this instruction and rematerialize the EDGE_ABNORMAL
3131 flag we just cleared above. */
3133 e->flags |= EDGE_ABNORMAL;
3134 ei_next (&ei);
3135 continue;
3138 /* We do not need this edge. */
3139 df_set_bb_dirty (bb);
3140 purged = true;
3141 remove_edge (e);
3144 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3145 return purged;
3147 if (dump_file)
3148 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3150 if (!optimize)
3151 return purged;
3153 /* Redistribute probabilities. */
3154 if (single_succ_p (bb))
3156 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3157 single_succ_edge (bb)->count = bb->count;
3159 else
3161 note = find_reg_note (insn, REG_BR_PROB, NULL);
3162 if (!note)
3163 return purged;
3165 b = BRANCH_EDGE (bb);
3166 f = FALLTHRU_EDGE (bb);
3167 b->probability = XINT (note, 0);
3168 f->probability = REG_BR_PROB_BASE - b->probability;
3169 /* Update these to use GCOV_COMPUTE_SCALE. */
3170 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
3171 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
3174 return purged;
3176 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3178 /* First, there should not be any EH or ABCALL edges resulting
3179 from non-local gotos and the like. If there were, we shouldn't
3180 have created the sibcall in the first place. Second, there
3181 should of course never have been a fallthru edge. */
3182 gcc_assert (single_succ_p (bb));
3183 gcc_assert (single_succ_edge (bb)->flags
3184 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3186 return 0;
3189 /* If we don't see a jump insn, we don't know exactly why the block would
3190 have been broken at this point. Look for a simple, non-fallthru edge,
3191 as these are only created by conditional branches. If we find such an
3192 edge we know that there used to be a jump here and can then safely
3193 remove all non-fallthru edges. */
3194 found = false;
3195 FOR_EACH_EDGE (e, ei, bb->succs)
3196 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3198 found = true;
3199 break;
3202 if (!found)
3203 return purged;
3205 /* Remove all but the fake and fallthru edges. The fake edge may be
3206 the only successor for this block in the case of noreturn
3207 calls. */
3208 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3210 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3212 df_set_bb_dirty (bb);
3213 remove_edge (e);
3214 purged = true;
3216 else
3217 ei_next (&ei);
3220 gcc_assert (single_succ_p (bb));
3222 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3223 single_succ_edge (bb)->count = bb->count;
3225 if (dump_file)
3226 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3227 bb->index);
3228 return purged;
3231 /* Search all basic blocks for potentially dead edges and purge them. Return
3232 true if some edge has been eliminated. */
3234 bool
3235 purge_all_dead_edges (void)
3237 int purged = false;
3238 basic_block bb;
3240 FOR_EACH_BB_FN (bb, cfun)
3242 bool purged_here = purge_dead_edges (bb);
3244 purged |= purged_here;
3247 return purged;
3250 /* This is used by a few passes that emit some instructions after abnormal
3251 calls, moving the basic block's end, while they in fact do want to emit
3252 them on the fallthru edge. Look for abnormal call edges, find backward
3253 the call in the block and insert the instructions on the edge instead.
3255 Similarly, handle instructions throwing exceptions internally.
3257 Return true when instructions have been found and inserted on edges. */
3259 bool
3260 fixup_abnormal_edges (void)
3262 bool inserted = false;
3263 basic_block bb;
3265 FOR_EACH_BB_FN (bb, cfun)
3267 edge e;
3268 edge_iterator ei;
3270 /* Look for cases we are interested in - calls or instructions causing
3271 exceptions. */
3272 FOR_EACH_EDGE (e, ei, bb->succs)
3273 if ((e->flags & EDGE_ABNORMAL_CALL)
3274 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3275 == (EDGE_ABNORMAL | EDGE_EH)))
3276 break;
3278 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3280 rtx_insn *insn;
3282 /* Get past the new insns generated. Allow notes, as the insns
3283 may be already deleted. */
3284 insn = BB_END (bb);
3285 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3286 && !can_throw_internal (insn)
3287 && insn != BB_HEAD (bb))
3288 insn = PREV_INSN (insn);
3290 if (CALL_P (insn) || can_throw_internal (insn))
3292 rtx_insn *stop, *next;
3294 e = find_fallthru_edge (bb->succs);
3296 stop = NEXT_INSN (BB_END (bb));
3297 BB_END (bb) = insn;
3299 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3301 next = NEXT_INSN (insn);
3302 if (INSN_P (insn))
3304 delete_insn (insn);
3306 /* Sometimes there's still the return value USE.
3307 If it's placed after a trapping call (i.e. that
3308 call is the last insn anyway), we have no fallthru
3309 edge. Simply delete this use and don't try to insert
3310 on the non-existent edge. */
3311 if (GET_CODE (PATTERN (insn)) != USE)
3313 /* We're not deleting it, we're moving it. */
3314 insn->set_undeleted ();
3315 SET_PREV_INSN (insn) = NULL_RTX;
3316 SET_NEXT_INSN (insn) = NULL_RTX;
3318 insert_insn_on_edge (insn, e);
3319 inserted = true;
3322 else if (!BARRIER_P (insn))
3323 set_block_for_insn (insn, NULL);
3327 /* It may be that we don't find any trapping insn. In this
3328 case we discovered quite late that the insn that had been
3329 marked as can_throw_internal in fact couldn't trap at all.
3330 So we should in fact delete the EH edges out of the block. */
3331 else
3332 purge_dead_edges (bb);
3336 return inserted;
3339 /* Cut the insns from FIRST to LAST out of the insns stream. */
3341 rtx_insn *
3342 unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3344 rtx_insn *prevfirst = PREV_INSN (first);
3345 rtx_insn *nextlast = NEXT_INSN (last);
3347 SET_PREV_INSN (first) = NULL;
3348 SET_NEXT_INSN (last) = NULL;
3349 if (prevfirst)
3350 SET_NEXT_INSN (prevfirst) = nextlast;
3351 if (nextlast)
3352 SET_PREV_INSN (nextlast) = prevfirst;
3353 else
3354 set_last_insn (prevfirst);
3355 if (!prevfirst)
3356 set_first_insn (nextlast);
3357 return first;
3360 /* Skip over inter-block insns occurring after BB which are typically
3361 associated with BB (e.g., barriers). If there are any such insns,
3362 we return the last one. Otherwise, we return the end of BB. */
3364 static rtx_insn *
3365 skip_insns_after_block (basic_block bb)
3367 rtx_insn *insn, *last_insn, *next_head, *prev;
3369 next_head = NULL;
3370 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3371 next_head = BB_HEAD (bb->next_bb);
3373 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3375 if (insn == next_head)
3376 break;
3378 switch (GET_CODE (insn))
3380 case BARRIER:
3381 last_insn = insn;
3382 continue;
3384 case NOTE:
3385 switch (NOTE_KIND (insn))
3387 case NOTE_INSN_BLOCK_END:
3388 gcc_unreachable ();
3389 continue;
3390 default:
3391 continue;
3392 break;
3394 break;
3396 case CODE_LABEL:
3397 if (NEXT_INSN (insn)
3398 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3400 insn = NEXT_INSN (insn);
3401 last_insn = insn;
3402 continue;
3404 break;
3406 default:
3407 break;
3410 break;
3413 /* It is possible to hit contradictory sequence. For instance:
3415 jump_insn
3416 NOTE_INSN_BLOCK_BEG
3417 barrier
3419 Where barrier belongs to jump_insn, but the note does not. This can be
3420 created by removing the basic block originally following
3421 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3423 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3425 prev = PREV_INSN (insn);
3426 if (NOTE_P (insn))
3427 switch (NOTE_KIND (insn))
3429 case NOTE_INSN_BLOCK_END:
3430 gcc_unreachable ();
3431 break;
3432 case NOTE_INSN_DELETED:
3433 case NOTE_INSN_DELETED_LABEL:
3434 case NOTE_INSN_DELETED_DEBUG_LABEL:
3435 continue;
3436 default:
3437 reorder_insns (insn, insn, last_insn);
3441 return last_insn;
3444 /* Locate or create a label for a given basic block. */
3446 static rtx_insn *
3447 label_for_bb (basic_block bb)
3449 rtx_insn *label = BB_HEAD (bb);
3451 if (!LABEL_P (label))
3453 if (dump_file)
3454 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3456 label = block_label (bb);
3459 return label;
3462 /* Locate the effective beginning and end of the insn chain for each
3463 block, as defined by skip_insns_after_block above. */
3465 static void
3466 record_effective_endpoints (void)
3468 rtx_insn *next_insn;
3469 basic_block bb;
3470 rtx_insn *insn;
3472 for (insn = get_insns ();
3473 insn
3474 && NOTE_P (insn)
3475 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3476 insn = NEXT_INSN (insn))
3477 continue;
3478 /* No basic blocks at all? */
3479 gcc_assert (insn);
3481 if (PREV_INSN (insn))
3482 cfg_layout_function_header =
3483 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3484 else
3485 cfg_layout_function_header = NULL;
3487 next_insn = get_insns ();
3488 FOR_EACH_BB_FN (bb, cfun)
3490 rtx_insn *end;
3492 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3493 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3494 PREV_INSN (BB_HEAD (bb)));
3495 end = skip_insns_after_block (bb);
3496 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3497 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3498 next_insn = NEXT_INSN (BB_END (bb));
3501 cfg_layout_function_footer = next_insn;
3502 if (cfg_layout_function_footer)
3503 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3506 namespace {
3508 const pass_data pass_data_into_cfg_layout_mode =
3510 RTL_PASS, /* type */
3511 "into_cfglayout", /* name */
3512 OPTGROUP_NONE, /* optinfo_flags */
3513 TV_CFG, /* tv_id */
3514 0, /* properties_required */
3515 PROP_cfglayout, /* properties_provided */
3516 0, /* properties_destroyed */
3517 0, /* todo_flags_start */
3518 0, /* todo_flags_finish */
3521 class pass_into_cfg_layout_mode : public rtl_opt_pass
3523 public:
3524 pass_into_cfg_layout_mode (gcc::context *ctxt)
3525 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3528 /* opt_pass methods: */
3529 virtual unsigned int execute (function *)
3531 cfg_layout_initialize (0);
3532 return 0;
3535 }; // class pass_into_cfg_layout_mode
3537 } // anon namespace
3539 rtl_opt_pass *
3540 make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3542 return new pass_into_cfg_layout_mode (ctxt);
3545 namespace {
3547 const pass_data pass_data_outof_cfg_layout_mode =
3549 RTL_PASS, /* type */
3550 "outof_cfglayout", /* name */
3551 OPTGROUP_NONE, /* optinfo_flags */
3552 TV_CFG, /* tv_id */
3553 0, /* properties_required */
3554 0, /* properties_provided */
3555 PROP_cfglayout, /* properties_destroyed */
3556 0, /* todo_flags_start */
3557 0, /* todo_flags_finish */
3560 class pass_outof_cfg_layout_mode : public rtl_opt_pass
3562 public:
3563 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3564 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3567 /* opt_pass methods: */
3568 virtual unsigned int execute (function *);
3570 }; // class pass_outof_cfg_layout_mode
3572 unsigned int
3573 pass_outof_cfg_layout_mode::execute (function *fun)
3575 basic_block bb;
3577 FOR_EACH_BB_FN (bb, fun)
3578 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3579 bb->aux = bb->next_bb;
3581 cfg_layout_finalize ();
3583 return 0;
3586 } // anon namespace
3588 rtl_opt_pass *
3589 make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3591 return new pass_outof_cfg_layout_mode (ctxt);
3595 /* Link the basic blocks in the correct order, compacting the basic
3596 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3597 function also clears the basic block header and footer fields.
3599 This function is usually called after a pass (e.g. tracer) finishes
3600 some transformations while in cfglayout mode. The required sequence
3601 of the basic blocks is in a linked list along the bb->aux field.
3602 This functions re-links the basic block prev_bb and next_bb pointers
3603 accordingly, and it compacts and renumbers the blocks.
3605 FIXME: This currently works only for RTL, but the only RTL-specific
3606 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3607 to GIMPLE a long time ago, but it doesn't relink the basic block
3608 chain. It could do that (to give better initial RTL) if this function
3609 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3611 void
3612 relink_block_chain (bool stay_in_cfglayout_mode)
3614 basic_block bb, prev_bb;
3615 int index;
3617 /* Maybe dump the re-ordered sequence. */
3618 if (dump_file)
3620 fprintf (dump_file, "Reordered sequence:\n");
3621 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3622 NUM_FIXED_BLOCKS;
3624 bb = (basic_block) bb->aux, index++)
3626 fprintf (dump_file, " %i ", index);
3627 if (get_bb_original (bb))
3628 fprintf (dump_file, "duplicate of %i ",
3629 get_bb_original (bb)->index);
3630 else if (forwarder_block_p (bb)
3631 && !LABEL_P (BB_HEAD (bb)))
3632 fprintf (dump_file, "compensation ");
3633 else
3634 fprintf (dump_file, "bb %i ", bb->index);
3635 fprintf (dump_file, " [%i]\n", bb->frequency);
3639 /* Now reorder the blocks. */
3640 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3641 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3642 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3644 bb->prev_bb = prev_bb;
3645 prev_bb->next_bb = bb;
3647 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3648 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3650 /* Then, clean up the aux fields. */
3651 FOR_ALL_BB_FN (bb, cfun)
3653 bb->aux = NULL;
3654 if (!stay_in_cfglayout_mode)
3655 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3658 /* Maybe reset the original copy tables, they are not valid anymore
3659 when we renumber the basic blocks in compact_blocks. If we are
3660 are going out of cfglayout mode, don't re-allocate the tables. */
3661 free_original_copy_tables ();
3662 if (stay_in_cfglayout_mode)
3663 initialize_original_copy_tables ();
3665 /* Finally, put basic_block_info in the new order. */
3666 compact_blocks ();
3670 /* Given a reorder chain, rearrange the code to match. */
3672 static void
3673 fixup_reorder_chain (void)
3675 basic_block bb;
3676 rtx_insn *insn = NULL;
3678 if (cfg_layout_function_header)
3680 set_first_insn (cfg_layout_function_header);
3681 insn = cfg_layout_function_header;
3682 while (NEXT_INSN (insn))
3683 insn = NEXT_INSN (insn);
3686 /* First do the bulk reordering -- rechain the blocks without regard to
3687 the needed changes to jumps and labels. */
3689 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3690 bb->aux)
3692 if (BB_HEADER (bb))
3694 if (insn)
3695 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3696 else
3697 set_first_insn (BB_HEADER (bb));
3698 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3699 insn = BB_HEADER (bb);
3700 while (NEXT_INSN (insn))
3701 insn = NEXT_INSN (insn);
3703 if (insn)
3704 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3705 else
3706 set_first_insn (BB_HEAD (bb));
3707 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3708 insn = BB_END (bb);
3709 if (BB_FOOTER (bb))
3711 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3712 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3713 while (NEXT_INSN (insn))
3714 insn = NEXT_INSN (insn);
3718 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3719 if (cfg_layout_function_footer)
3720 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3722 while (NEXT_INSN (insn))
3723 insn = NEXT_INSN (insn);
3725 set_last_insn (insn);
3726 #ifdef ENABLE_CHECKING
3727 verify_insn_chain ();
3728 #endif
3730 /* Now add jumps and labels as needed to match the blocks new
3731 outgoing edges. */
3733 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3734 bb->aux)
3736 edge e_fall, e_taken, e;
3737 rtx_insn *bb_end_insn;
3738 rtx ret_label = NULL_RTX;
3739 basic_block nb;
3740 edge_iterator ei;
3742 if (EDGE_COUNT (bb->succs) == 0)
3743 continue;
3745 /* Find the old fallthru edge, and another non-EH edge for
3746 a taken jump. */
3747 e_taken = e_fall = NULL;
3749 FOR_EACH_EDGE (e, ei, bb->succs)
3750 if (e->flags & EDGE_FALLTHRU)
3751 e_fall = e;
3752 else if (! (e->flags & EDGE_EH))
3753 e_taken = e;
3755 bb_end_insn = BB_END (bb);
3756 if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
3758 ret_label = JUMP_LABEL (bb_end_jump);
3759 if (any_condjump_p (bb_end_jump))
3761 /* This might happen if the conditional jump has side
3762 effects and could therefore not be optimized away.
3763 Make the basic block to end with a barrier in order
3764 to prevent rtl_verify_flow_info from complaining. */
3765 if (!e_fall)
3767 gcc_assert (!onlyjump_p (bb_end_jump)
3768 || returnjump_p (bb_end_jump)
3769 || (e_taken->flags & EDGE_CROSSING));
3770 emit_barrier_after (bb_end_jump);
3771 continue;
3774 /* If the old fallthru is still next, nothing to do. */
3775 if (bb->aux == e_fall->dest
3776 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3777 continue;
3779 /* The degenerated case of conditional jump jumping to the next
3780 instruction can happen for jumps with side effects. We need
3781 to construct a forwarder block and this will be done just
3782 fine by force_nonfallthru below. */
3783 if (!e_taken)
3786 /* There is another special case: if *neither* block is next,
3787 such as happens at the very end of a function, then we'll
3788 need to add a new unconditional jump. Choose the taken
3789 edge based on known or assumed probability. */
3790 else if (bb->aux != e_taken->dest)
3792 rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
3794 if (note
3795 && XINT (note, 0) < REG_BR_PROB_BASE / 2
3796 && invert_jump (bb_end_jump,
3797 (e_fall->dest
3798 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3799 ? NULL_RTX
3800 : label_for_bb (e_fall->dest)), 0))
3802 e_fall->flags &= ~EDGE_FALLTHRU;
3803 gcc_checking_assert (could_fall_through
3804 (e_taken->src, e_taken->dest));
3805 e_taken->flags |= EDGE_FALLTHRU;
3806 update_br_prob_note (bb);
3807 e = e_fall, e_fall = e_taken, e_taken = e;
3811 /* If the "jumping" edge is a crossing edge, and the fall
3812 through edge is non-crossing, leave things as they are. */
3813 else if ((e_taken->flags & EDGE_CROSSING)
3814 && !(e_fall->flags & EDGE_CROSSING))
3815 continue;
3817 /* Otherwise we can try to invert the jump. This will
3818 basically never fail, however, keep up the pretense. */
3819 else if (invert_jump (bb_end_jump,
3820 (e_fall->dest
3821 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3822 ? NULL_RTX
3823 : label_for_bb (e_fall->dest)), 0))
3825 e_fall->flags &= ~EDGE_FALLTHRU;
3826 gcc_checking_assert (could_fall_through
3827 (e_taken->src, e_taken->dest));
3828 e_taken->flags |= EDGE_FALLTHRU;
3829 update_br_prob_note (bb);
3830 if (LABEL_NUSES (ret_label) == 0
3831 && single_pred_p (e_taken->dest))
3832 delete_insn (ret_label);
3833 continue;
3836 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
3838 /* If the old fallthru is still next or if
3839 asm goto doesn't have a fallthru (e.g. when followed by
3840 __builtin_unreachable ()), nothing to do. */
3841 if (! e_fall
3842 || bb->aux == e_fall->dest
3843 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3844 continue;
3846 /* Otherwise we'll have to use the fallthru fixup below. */
3848 else
3850 /* Otherwise we have some return, switch or computed
3851 jump. In the 99% case, there should not have been a
3852 fallthru edge. */
3853 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
3854 continue;
3857 else
3859 /* No fallthru implies a noreturn function with EH edges, or
3860 something similarly bizarre. In any case, we don't need to
3861 do anything. */
3862 if (! e_fall)
3863 continue;
3865 /* If the fallthru block is still next, nothing to do. */
3866 if (bb->aux == e_fall->dest)
3867 continue;
3869 /* A fallthru to exit block. */
3870 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3871 continue;
3874 /* We got here if we need to add a new jump insn.
3875 Note force_nonfallthru can delete E_FALL and thus we have to
3876 save E_FALL->src prior to the call to force_nonfallthru. */
3877 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
3878 if (nb)
3880 nb->aux = bb->aux;
3881 bb->aux = nb;
3882 /* Don't process this new block. */
3883 bb = nb;
3887 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3889 /* Annoying special case - jump around dead jumptables left in the code. */
3890 FOR_EACH_BB_FN (bb, cfun)
3892 edge e = find_fallthru_edge (bb->succs);
3894 if (e && !can_fallthru (e->src, e->dest))
3895 force_nonfallthru (e);
3898 /* Ensure goto_locus from edges has some instructions with that locus
3899 in RTL. */
3900 if (!optimize)
3901 FOR_EACH_BB_FN (bb, cfun)
3903 edge e;
3904 edge_iterator ei;
3906 FOR_EACH_EDGE (e, ei, bb->succs)
3907 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
3908 && !(e->flags & EDGE_ABNORMAL))
3910 edge e2;
3911 edge_iterator ei2;
3912 basic_block dest, nb;
3913 rtx_insn *end;
3915 insn = BB_END (e->src);
3916 end = PREV_INSN (BB_HEAD (e->src));
3917 while (insn != end
3918 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
3919 insn = PREV_INSN (insn);
3920 if (insn != end
3921 && INSN_LOCATION (insn) == e->goto_locus)
3922 continue;
3923 if (simplejump_p (BB_END (e->src))
3924 && !INSN_HAS_LOCATION (BB_END (e->src)))
3926 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
3927 continue;
3929 dest = e->dest;
3930 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3932 /* Non-fallthru edges to the exit block cannot be split. */
3933 if (!(e->flags & EDGE_FALLTHRU))
3934 continue;
3936 else
3938 insn = BB_HEAD (dest);
3939 end = NEXT_INSN (BB_END (dest));
3940 while (insn != end && !NONDEBUG_INSN_P (insn))
3941 insn = NEXT_INSN (insn);
3942 if (insn != end && INSN_HAS_LOCATION (insn)
3943 && INSN_LOCATION (insn) == e->goto_locus)
3944 continue;
3946 nb = split_edge (e);
3947 if (!INSN_P (BB_END (nb)))
3948 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
3949 nb);
3950 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
3952 /* If there are other incoming edges to the destination block
3953 with the same goto locus, redirect them to the new block as
3954 well, this can prevent other such blocks from being created
3955 in subsequent iterations of the loop. */
3956 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
3957 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
3958 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
3959 && e->goto_locus == e2->goto_locus)
3960 redirect_edge_and_branch (e2, nb);
3961 else
3962 ei_next (&ei2);
3967 /* Perform sanity checks on the insn chain.
3968 1. Check that next/prev pointers are consistent in both the forward and
3969 reverse direction.
3970 2. Count insns in chain, going both directions, and check if equal.
3971 3. Check that get_last_insn () returns the actual end of chain. */
3973 DEBUG_FUNCTION void
3974 verify_insn_chain (void)
3976 rtx_insn *x, *prevx, *nextx;
3977 int insn_cnt1, insn_cnt2;
3979 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
3980 x != 0;
3981 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
3982 gcc_assert (PREV_INSN (x) == prevx);
3984 gcc_assert (prevx == get_last_insn ());
3986 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
3987 x != 0;
3988 nextx = x, insn_cnt2++, x = PREV_INSN (x))
3989 gcc_assert (NEXT_INSN (x) == nextx);
3991 gcc_assert (insn_cnt1 == insn_cnt2);
3994 /* If we have assembler epilogues, the block falling through to exit must
3995 be the last one in the reordered chain when we reach final. Ensure
3996 that this condition is met. */
3997 static void
3998 fixup_fallthru_exit_predecessor (void)
4000 edge e;
4001 basic_block bb = NULL;
4003 /* This transformation is not valid before reload, because we might
4004 separate a call from the instruction that copies the return
4005 value. */
4006 gcc_assert (reload_completed);
4008 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4009 if (e)
4010 bb = e->src;
4012 if (bb && bb->aux)
4014 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4016 /* If the very first block is the one with the fall-through exit
4017 edge, we have to split that block. */
4018 if (c == bb)
4020 bb = split_block_after_labels (bb)->dest;
4021 bb->aux = c->aux;
4022 c->aux = bb;
4023 BB_FOOTER (bb) = BB_FOOTER (c);
4024 BB_FOOTER (c) = NULL;
4027 while (c->aux != bb)
4028 c = (basic_block) c->aux;
4030 c->aux = bb->aux;
4031 while (c->aux)
4032 c = (basic_block) c->aux;
4034 c->aux = bb;
4035 bb->aux = NULL;
4039 /* In case there are more than one fallthru predecessors of exit, force that
4040 there is only one. */
4042 static void
4043 force_one_exit_fallthru (void)
4045 edge e, predecessor = NULL;
4046 bool more = false;
4047 edge_iterator ei;
4048 basic_block forwarder, bb;
4050 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4051 if (e->flags & EDGE_FALLTHRU)
4053 if (predecessor == NULL)
4054 predecessor = e;
4055 else
4057 more = true;
4058 break;
4062 if (!more)
4063 return;
4065 /* Exit has several fallthru predecessors. Create a forwarder block for
4066 them. */
4067 forwarder = split_edge (predecessor);
4068 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4069 (e = ei_safe_edge (ei)); )
4071 if (e->src == forwarder
4072 || !(e->flags & EDGE_FALLTHRU))
4073 ei_next (&ei);
4074 else
4075 redirect_edge_and_branch_force (e, forwarder);
4078 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4079 exit block. */
4080 FOR_EACH_BB_FN (bb, cfun)
4082 if (bb->aux == NULL && bb != forwarder)
4084 bb->aux = forwarder;
4085 break;
4090 /* Return true in case it is possible to duplicate the basic block BB. */
4092 static bool
4093 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4095 /* Do not attempt to duplicate tablejumps, as we need to unshare
4096 the dispatch table. This is difficult to do, as the instructions
4097 computing jump destination may be hoisted outside the basic block. */
4098 if (tablejump_p (BB_END (bb), NULL, NULL))
4099 return false;
4101 /* Do not duplicate blocks containing insns that can't be copied. */
4102 if (targetm.cannot_copy_insn_p)
4104 rtx_insn *insn = BB_HEAD (bb);
4105 while (1)
4107 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4108 return false;
4109 if (insn == BB_END (bb))
4110 break;
4111 insn = NEXT_INSN (insn);
4115 return true;
4118 rtx_insn *
4119 duplicate_insn_chain (rtx_insn *from, rtx_insn *to)
4121 rtx_insn *insn, *next, *copy;
4122 rtx_note *last;
4124 /* Avoid updating of boundaries of previous basic block. The
4125 note will get removed from insn stream in fixup. */
4126 last = emit_note (NOTE_INSN_DELETED);
4128 /* Create copy at the end of INSN chain. The chain will
4129 be reordered later. */
4130 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4132 switch (GET_CODE (insn))
4134 case DEBUG_INSN:
4135 /* Don't duplicate label debug insns. */
4136 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4137 break;
4138 /* FALLTHRU */
4139 case INSN:
4140 case CALL_INSN:
4141 case JUMP_INSN:
4142 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4143 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4144 && ANY_RETURN_P (JUMP_LABEL (insn)))
4145 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4146 maybe_copy_prologue_epilogue_insn (insn, copy);
4147 break;
4149 case JUMP_TABLE_DATA:
4150 /* Avoid copying of dispatch tables. We never duplicate
4151 tablejumps, so this can hit only in case the table got
4152 moved far from original jump.
4153 Avoid copying following barrier as well if any
4154 (and debug insns in between). */
4155 for (next = NEXT_INSN (insn);
4156 next != NEXT_INSN (to);
4157 next = NEXT_INSN (next))
4158 if (!DEBUG_INSN_P (next))
4159 break;
4160 if (next != NEXT_INSN (to) && BARRIER_P (next))
4161 insn = next;
4162 break;
4164 case CODE_LABEL:
4165 break;
4167 case BARRIER:
4168 emit_barrier ();
4169 break;
4171 case NOTE:
4172 switch (NOTE_KIND (insn))
4174 /* In case prologue is empty and function contain label
4175 in first BB, we may want to copy the block. */
4176 case NOTE_INSN_PROLOGUE_END:
4178 case NOTE_INSN_DELETED:
4179 case NOTE_INSN_DELETED_LABEL:
4180 case NOTE_INSN_DELETED_DEBUG_LABEL:
4181 /* No problem to strip these. */
4182 case NOTE_INSN_FUNCTION_BEG:
4183 /* There is always just single entry to function. */
4184 case NOTE_INSN_BASIC_BLOCK:
4185 /* We should only switch text sections once. */
4186 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4187 break;
4189 case NOTE_INSN_EPILOGUE_BEG:
4190 case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4191 emit_note_copy (as_a <rtx_note *> (insn));
4192 break;
4194 default:
4195 /* All other notes should have already been eliminated. */
4196 gcc_unreachable ();
4198 break;
4199 default:
4200 gcc_unreachable ();
4203 insn = NEXT_INSN (last);
4204 delete_insn (last);
4205 return insn;
4208 /* Create a duplicate of the basic block BB. */
4210 static basic_block
4211 cfg_layout_duplicate_bb (basic_block bb)
4213 rtx_insn *insn;
4214 basic_block new_bb;
4216 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
4217 new_bb = create_basic_block (insn,
4218 insn ? get_last_insn () : NULL,
4219 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4221 BB_COPY_PARTITION (new_bb, bb);
4222 if (BB_HEADER (bb))
4224 insn = BB_HEADER (bb);
4225 while (NEXT_INSN (insn))
4226 insn = NEXT_INSN (insn);
4227 insn = duplicate_insn_chain (BB_HEADER (bb), insn);
4228 if (insn)
4229 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4232 if (BB_FOOTER (bb))
4234 insn = BB_FOOTER (bb);
4235 while (NEXT_INSN (insn))
4236 insn = NEXT_INSN (insn);
4237 insn = duplicate_insn_chain (BB_FOOTER (bb), insn);
4238 if (insn)
4239 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4242 return new_bb;
4246 /* Main entry point to this module - initialize the datastructures for
4247 CFG layout changes. It keeps LOOPS up-to-date if not null.
4249 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4251 void
4252 cfg_layout_initialize (unsigned int flags)
4254 rtx_insn_list *x;
4255 basic_block bb;
4257 /* Once bb partitioning is complete, cfg layout mode should not be
4258 re-entered. Entering cfg layout mode may require fixups. As an
4259 example, if edge forwarding performed when optimizing the cfg
4260 layout required moving a block from the hot to the cold
4261 section. This would create an illegal partitioning unless some
4262 manual fixup was performed. */
4263 gcc_assert (!(crtl->bb_reorder_complete
4264 && flag_reorder_blocks_and_partition));
4266 initialize_original_copy_tables ();
4268 cfg_layout_rtl_register_cfg_hooks ();
4270 record_effective_endpoints ();
4272 /* Make sure that the targets of non local gotos are marked. */
4273 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4275 bb = BLOCK_FOR_INSN (x->insn ());
4276 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4279 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4282 /* Splits superblocks. */
4283 void
4284 break_superblocks (void)
4286 sbitmap superblocks;
4287 bool need = false;
4288 basic_block bb;
4290 superblocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
4291 bitmap_clear (superblocks);
4293 FOR_EACH_BB_FN (bb, cfun)
4294 if (bb->flags & BB_SUPERBLOCK)
4296 bb->flags &= ~BB_SUPERBLOCK;
4297 bitmap_set_bit (superblocks, bb->index);
4298 need = true;
4301 if (need)
4303 rebuild_jump_labels (get_insns ());
4304 find_many_sub_basic_blocks (superblocks);
4307 free (superblocks);
4310 /* Finalize the changes: reorder insn list according to the sequence specified
4311 by aux pointers, enter compensation code, rebuild scope forest. */
4313 void
4314 cfg_layout_finalize (void)
4316 #ifdef ENABLE_CHECKING
4317 verify_flow_info ();
4318 #endif
4319 force_one_exit_fallthru ();
4320 rtl_register_cfg_hooks ();
4321 if (reload_completed && !targetm.have_epilogue ())
4322 fixup_fallthru_exit_predecessor ();
4323 fixup_reorder_chain ();
4325 rebuild_jump_labels (get_insns ());
4326 delete_dead_jumptables ();
4328 #ifdef ENABLE_CHECKING
4329 verify_insn_chain ();
4330 verify_flow_info ();
4331 #endif
4335 /* Same as split_block but update cfg_layout structures. */
4337 static basic_block
4338 cfg_layout_split_block (basic_block bb, void *insnp)
4340 rtx insn = (rtx) insnp;
4341 basic_block new_bb = rtl_split_block (bb, insn);
4343 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4344 BB_FOOTER (bb) = NULL;
4346 return new_bb;
4349 /* Redirect Edge to DEST. */
4350 static edge
4351 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4353 basic_block src = e->src;
4354 edge ret;
4356 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4357 return NULL;
4359 if (e->dest == dest)
4360 return e;
4362 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4363 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4365 df_set_bb_dirty (src);
4366 return ret;
4369 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4370 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4372 if (dump_file)
4373 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4374 e->src->index, dest->index);
4376 df_set_bb_dirty (e->src);
4377 redirect_edge_succ (e, dest);
4378 return e;
4381 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4382 in the case the basic block appears to be in sequence. Avoid this
4383 transformation. */
4385 if (e->flags & EDGE_FALLTHRU)
4387 /* Redirect any branch edges unified with the fallthru one. */
4388 if (JUMP_P (BB_END (src))
4389 && label_is_jump_target_p (BB_HEAD (e->dest),
4390 BB_END (src)))
4392 edge redirected;
4394 if (dump_file)
4395 fprintf (dump_file, "Fallthru edge unified with branch "
4396 "%i->%i redirected to %i\n",
4397 e->src->index, e->dest->index, dest->index);
4398 e->flags &= ~EDGE_FALLTHRU;
4399 redirected = redirect_branch_edge (e, dest);
4400 gcc_assert (redirected);
4401 redirected->flags |= EDGE_FALLTHRU;
4402 df_set_bb_dirty (redirected->src);
4403 return redirected;
4405 /* In case we are redirecting fallthru edge to the branch edge
4406 of conditional jump, remove it. */
4407 if (EDGE_COUNT (src->succs) == 2)
4409 /* Find the edge that is different from E. */
4410 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4412 if (s->dest == dest
4413 && any_condjump_p (BB_END (src))
4414 && onlyjump_p (BB_END (src)))
4415 delete_insn (BB_END (src));
4417 if (dump_file)
4418 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4419 e->src->index, e->dest->index, dest->index);
4420 ret = redirect_edge_succ_nodup (e, dest);
4422 else
4423 ret = redirect_branch_edge (e, dest);
4425 /* We don't want simplejumps in the insn stream during cfglayout. */
4426 gcc_assert (!simplejump_p (BB_END (src)));
4428 df_set_bb_dirty (src);
4429 return ret;
4432 /* Simple wrapper as we always can redirect fallthru edges. */
4433 static basic_block
4434 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4436 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4438 gcc_assert (redirected);
4439 return NULL;
4442 /* Same as delete_basic_block but update cfg_layout structures. */
4444 static void
4445 cfg_layout_delete_block (basic_block bb)
4447 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4448 rtx_insn **to;
4450 if (BB_HEADER (bb))
4452 next = BB_HEAD (bb);
4453 if (prev)
4454 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4455 else
4456 set_first_insn (BB_HEADER (bb));
4457 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4458 insn = BB_HEADER (bb);
4459 while (NEXT_INSN (insn))
4460 insn = NEXT_INSN (insn);
4461 SET_NEXT_INSN (insn) = next;
4462 SET_PREV_INSN (next) = insn;
4464 next = NEXT_INSN (BB_END (bb));
4465 if (BB_FOOTER (bb))
4467 insn = BB_FOOTER (bb);
4468 while (insn)
4470 if (BARRIER_P (insn))
4472 if (PREV_INSN (insn))
4473 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4474 else
4475 BB_FOOTER (bb) = NEXT_INSN (insn);
4476 if (NEXT_INSN (insn))
4477 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4479 if (LABEL_P (insn))
4480 break;
4481 insn = NEXT_INSN (insn);
4483 if (BB_FOOTER (bb))
4485 insn = BB_END (bb);
4486 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4487 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4488 while (NEXT_INSN (insn))
4489 insn = NEXT_INSN (insn);
4490 SET_NEXT_INSN (insn) = next;
4491 if (next)
4492 SET_PREV_INSN (next) = insn;
4493 else
4494 set_last_insn (insn);
4497 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4498 to = &BB_HEADER (bb->next_bb);
4499 else
4500 to = &cfg_layout_function_footer;
4502 rtl_delete_block (bb);
4504 if (prev)
4505 prev = NEXT_INSN (prev);
4506 else
4507 prev = get_insns ();
4508 if (next)
4509 next = PREV_INSN (next);
4510 else
4511 next = get_last_insn ();
4513 if (next && NEXT_INSN (next) != prev)
4515 remaints = unlink_insn_chain (prev, next);
4516 insn = remaints;
4517 while (NEXT_INSN (insn))
4518 insn = NEXT_INSN (insn);
4519 SET_NEXT_INSN (insn) = *to;
4520 if (*to)
4521 SET_PREV_INSN (*to) = insn;
4522 *to = remaints;
4526 /* Return true when blocks A and B can be safely merged. */
4528 static bool
4529 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4531 /* If we are partitioning hot/cold basic blocks, we don't want to
4532 mess up unconditional or indirect jumps that cross between hot
4533 and cold sections.
4535 Basic block partitioning may result in some jumps that appear to
4536 be optimizable (or blocks that appear to be mergeable), but which really
4537 must be left untouched (they are required to make it safely across
4538 partition boundaries). See the comments at the top of
4539 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4541 if (BB_PARTITION (a) != BB_PARTITION (b))
4542 return false;
4544 /* Protect the loop latches. */
4545 if (current_loops && b->loop_father->latch == b)
4546 return false;
4548 /* If we would end up moving B's instructions, make sure it doesn't fall
4549 through into the exit block, since we cannot recover from a fallthrough
4550 edge into the exit block occurring in the middle of a function. */
4551 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4553 edge e = find_fallthru_edge (b->succs);
4554 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4555 return false;
4558 /* There must be exactly one edge in between the blocks. */
4559 return (single_succ_p (a)
4560 && single_succ (a) == b
4561 && single_pred_p (b) == 1
4562 && a != b
4563 /* Must be simple edge. */
4564 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4565 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4566 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4567 /* If the jump insn has side effects, we can't kill the edge.
4568 When not optimizing, try_redirect_by_replacing_jump will
4569 not allow us to redirect an edge by replacing a table jump. */
4570 && (!JUMP_P (BB_END (a))
4571 || ((!optimize || reload_completed)
4572 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4575 /* Merge block A and B. The blocks must be mergeable. */
4577 static void
4578 cfg_layout_merge_blocks (basic_block a, basic_block b)
4580 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
4581 rtx_insn *insn;
4583 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4585 if (dump_file)
4586 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4587 a->index);
4589 /* If there was a CODE_LABEL beginning B, delete it. */
4590 if (LABEL_P (BB_HEAD (b)))
4592 delete_insn (BB_HEAD (b));
4595 /* We should have fallthru edge in a, or we can do dummy redirection to get
4596 it cleaned up. */
4597 if (JUMP_P (BB_END (a)))
4598 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4599 gcc_assert (!JUMP_P (BB_END (a)));
4601 /* When not optimizing and the edge is the only place in RTL which holds
4602 some unique locus, emit a nop with that locus in between. */
4603 if (!optimize)
4604 emit_nop_for_unique_locus_between (a, b);
4606 /* Move things from b->footer after a->footer. */
4607 if (BB_FOOTER (b))
4609 if (!BB_FOOTER (a))
4610 BB_FOOTER (a) = BB_FOOTER (b);
4611 else
4613 rtx_insn *last = BB_FOOTER (a);
4615 while (NEXT_INSN (last))
4616 last = NEXT_INSN (last);
4617 SET_NEXT_INSN (last) = BB_FOOTER (b);
4618 SET_PREV_INSN (BB_FOOTER (b)) = last;
4620 BB_FOOTER (b) = NULL;
4623 /* Move things from b->header before a->footer.
4624 Note that this may include dead tablejump data, but we don't clean
4625 those up until we go out of cfglayout mode. */
4626 if (BB_HEADER (b))
4628 if (! BB_FOOTER (a))
4629 BB_FOOTER (a) = BB_HEADER (b);
4630 else
4632 rtx_insn *last = BB_HEADER (b);
4634 while (NEXT_INSN (last))
4635 last = NEXT_INSN (last);
4636 SET_NEXT_INSN (last) = BB_FOOTER (a);
4637 SET_PREV_INSN (BB_FOOTER (a)) = last;
4638 BB_FOOTER (a) = BB_HEADER (b);
4640 BB_HEADER (b) = NULL;
4643 /* In the case basic blocks are not adjacent, move them around. */
4644 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4646 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4648 emit_insn_after_noloc (insn, BB_END (a), a);
4650 /* Otherwise just re-associate the instructions. */
4651 else
4653 insn = BB_HEAD (b);
4654 BB_END (a) = BB_END (b);
4657 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4658 We need to explicitly call. */
4659 update_bb_for_insn_chain (insn, BB_END (b), a);
4661 /* Skip possible DELETED_LABEL insn. */
4662 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4663 insn = NEXT_INSN (insn);
4664 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4665 BB_HEAD (b) = BB_END (b) = NULL;
4666 delete_insn (insn);
4668 df_bb_delete (b->index);
4670 /* If B was a forwarder block, propagate the locus on the edge. */
4671 if (forwarder_p
4672 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
4673 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4675 if (dump_file)
4676 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4679 /* Split edge E. */
4681 static basic_block
4682 cfg_layout_split_edge (edge e)
4684 basic_block new_bb =
4685 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4686 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4687 NULL_RTX, e->src);
4689 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4690 BB_COPY_PARTITION (new_bb, e->src);
4691 else
4692 BB_COPY_PARTITION (new_bb, e->dest);
4693 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4694 redirect_edge_and_branch_force (e, new_bb);
4696 return new_bb;
4699 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4701 static void
4702 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4706 /* Return true if BB contains only labels or non-executable
4707 instructions. */
4709 static bool
4710 rtl_block_empty_p (basic_block bb)
4712 rtx_insn *insn;
4714 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4715 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4716 return true;
4718 FOR_BB_INSNS (bb, insn)
4719 if (NONDEBUG_INSN_P (insn) && !any_uncondjump_p (insn))
4720 return false;
4722 return true;
4725 /* Split a basic block if it ends with a conditional branch and if
4726 the other part of the block is not empty. */
4728 static basic_block
4729 rtl_split_block_before_cond_jump (basic_block bb)
4731 rtx_insn *insn;
4732 rtx_insn *split_point = NULL;
4733 rtx_insn *last = NULL;
4734 bool found_code = false;
4736 FOR_BB_INSNS (bb, insn)
4738 if (any_condjump_p (insn))
4739 split_point = last;
4740 else if (NONDEBUG_INSN_P (insn))
4741 found_code = true;
4742 last = insn;
4745 /* Did not find everything. */
4746 if (found_code && split_point)
4747 return split_block (bb, split_point)->dest;
4748 else
4749 return NULL;
4752 /* Return 1 if BB ends with a call, possibly followed by some
4753 instructions that must stay with the call, 0 otherwise. */
4755 static bool
4756 rtl_block_ends_with_call_p (basic_block bb)
4758 rtx_insn *insn = BB_END (bb);
4760 while (!CALL_P (insn)
4761 && insn != BB_HEAD (bb)
4762 && (keep_with_call_p (insn)
4763 || NOTE_P (insn)
4764 || DEBUG_INSN_P (insn)))
4765 insn = PREV_INSN (insn);
4766 return (CALL_P (insn));
4769 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4771 static bool
4772 rtl_block_ends_with_condjump_p (const_basic_block bb)
4774 return any_condjump_p (BB_END (bb));
4777 /* Return true if we need to add fake edge to exit.
4778 Helper function for rtl_flow_call_edges_add. */
4780 static bool
4781 need_fake_edge_p (const rtx_insn *insn)
4783 if (!INSN_P (insn))
4784 return false;
4786 if ((CALL_P (insn)
4787 && !SIBLING_CALL_P (insn)
4788 && !find_reg_note (insn, REG_NORETURN, NULL)
4789 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
4790 return true;
4792 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
4793 && MEM_VOLATILE_P (PATTERN (insn)))
4794 || (GET_CODE (PATTERN (insn)) == PARALLEL
4795 && asm_noperands (insn) != -1
4796 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
4797 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
4800 /* Add fake edges to the function exit for any non constant and non noreturn
4801 calls, volatile inline assembly in the bitmap of blocks specified by
4802 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4803 that were split.
4805 The goal is to expose cases in which entering a basic block does not imply
4806 that all subsequent instructions must be executed. */
4808 static int
4809 rtl_flow_call_edges_add (sbitmap blocks)
4811 int i;
4812 int blocks_split = 0;
4813 int last_bb = last_basic_block_for_fn (cfun);
4814 bool check_last_block = false;
4816 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
4817 return 0;
4819 if (! blocks)
4820 check_last_block = true;
4821 else
4822 check_last_block = bitmap_bit_p (blocks,
4823 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
4825 /* In the last basic block, before epilogue generation, there will be
4826 a fallthru edge to EXIT. Special care is required if the last insn
4827 of the last basic block is a call because make_edge folds duplicate
4828 edges, which would result in the fallthru edge also being marked
4829 fake, which would result in the fallthru edge being removed by
4830 remove_fake_edges, which would result in an invalid CFG.
4832 Moreover, we can't elide the outgoing fake edge, since the block
4833 profiler needs to take this into account in order to solve the minimal
4834 spanning tree in the case that the call doesn't return.
4836 Handle this by adding a dummy instruction in a new last basic block. */
4837 if (check_last_block)
4839 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
4840 rtx_insn *insn = BB_END (bb);
4842 /* Back up past insns that must be kept in the same block as a call. */
4843 while (insn != BB_HEAD (bb)
4844 && keep_with_call_p (insn))
4845 insn = PREV_INSN (insn);
4847 if (need_fake_edge_p (insn))
4849 edge e;
4851 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4852 if (e)
4854 insert_insn_on_edge (gen_use (const0_rtx), e);
4855 commit_edge_insertions ();
4860 /* Now add fake edges to the function exit for any non constant
4861 calls since there is no way that we can determine if they will
4862 return or not... */
4864 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
4866 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
4867 rtx_insn *insn;
4868 rtx_insn *prev_insn;
4870 if (!bb)
4871 continue;
4873 if (blocks && !bitmap_bit_p (blocks, i))
4874 continue;
4876 for (insn = BB_END (bb); ; insn = prev_insn)
4878 prev_insn = PREV_INSN (insn);
4879 if (need_fake_edge_p (insn))
4881 edge e;
4882 rtx_insn *split_at_insn = insn;
4884 /* Don't split the block between a call and an insn that should
4885 remain in the same block as the call. */
4886 if (CALL_P (insn))
4887 while (split_at_insn != BB_END (bb)
4888 && keep_with_call_p (NEXT_INSN (split_at_insn)))
4889 split_at_insn = NEXT_INSN (split_at_insn);
4891 /* The handling above of the final block before the epilogue
4892 should be enough to verify that there is no edge to the exit
4893 block in CFG already. Calling make_edge in such case would
4894 cause us to mark that edge as fake and remove it later. */
4896 #ifdef ENABLE_CHECKING
4897 if (split_at_insn == BB_END (bb))
4899 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4900 gcc_assert (e == NULL);
4902 #endif
4904 /* Note that the following may create a new basic block
4905 and renumber the existing basic blocks. */
4906 if (split_at_insn != BB_END (bb))
4908 e = split_block (bb, split_at_insn);
4909 if (e)
4910 blocks_split++;
4913 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
4916 if (insn == BB_HEAD (bb))
4917 break;
4921 if (blocks_split)
4922 verify_flow_info ();
4924 return blocks_split;
4927 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4928 the conditional branch target, SECOND_HEAD should be the fall-thru
4929 there is no need to handle this here the loop versioning code handles
4930 this. the reason for SECON_HEAD is that it is needed for condition
4931 in trees, and this should be of the same type since it is a hook. */
4932 static void
4933 rtl_lv_add_condition_to_bb (basic_block first_head ,
4934 basic_block second_head ATTRIBUTE_UNUSED,
4935 basic_block cond_bb, void *comp_rtx)
4937 rtx_code_label *label;
4938 rtx_insn *seq, *jump;
4939 rtx op0 = XEXP ((rtx)comp_rtx, 0);
4940 rtx op1 = XEXP ((rtx)comp_rtx, 1);
4941 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
4942 machine_mode mode;
4945 label = block_label (first_head);
4946 mode = GET_MODE (op0);
4947 if (mode == VOIDmode)
4948 mode = GET_MODE (op1);
4950 start_sequence ();
4951 op0 = force_operand (op0, NULL_RTX);
4952 op1 = force_operand (op1, NULL_RTX);
4953 do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label, -1);
4954 jump = get_last_insn ();
4955 JUMP_LABEL (jump) = label;
4956 LABEL_NUSES (label)++;
4957 seq = get_insns ();
4958 end_sequence ();
4960 /* Add the new cond, in the new head. */
4961 emit_insn_after (seq, BB_END (cond_bb));
4965 /* Given a block B with unconditional branch at its end, get the
4966 store the return the branch edge and the fall-thru edge in
4967 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4968 static void
4969 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
4970 edge *fallthru_edge)
4972 edge e = EDGE_SUCC (b, 0);
4974 if (e->flags & EDGE_FALLTHRU)
4976 *fallthru_edge = e;
4977 *branch_edge = EDGE_SUCC (b, 1);
4979 else
4981 *branch_edge = e;
4982 *fallthru_edge = EDGE_SUCC (b, 1);
4986 void
4987 init_rtl_bb_info (basic_block bb)
4989 gcc_assert (!bb->il.x.rtl);
4990 bb->il.x.head_ = NULL;
4991 bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
4994 /* Returns true if it is possible to remove edge E by redirecting
4995 it to the destination of the other edge from E->src. */
4997 static bool
4998 rtl_can_remove_branch_p (const_edge e)
5000 const_basic_block src = e->src;
5001 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
5002 const rtx_insn *insn = BB_END (src);
5003 rtx set;
5005 /* The conditions are taken from try_redirect_by_replacing_jump. */
5006 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
5007 return false;
5009 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
5010 return false;
5012 if (BB_PARTITION (src) != BB_PARTITION (target))
5013 return false;
5015 if (!onlyjump_p (insn)
5016 || tablejump_p (insn, NULL, NULL))
5017 return false;
5019 set = single_set (insn);
5020 if (!set || side_effects_p (set))
5021 return false;
5023 return true;
5026 static basic_block
5027 rtl_duplicate_bb (basic_block bb)
5029 bb = cfg_layout_duplicate_bb (bb);
5030 bb->aux = NULL;
5031 return bb;
5034 /* Do book-keeping of basic block BB for the profile consistency checker.
5035 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5036 then do post-pass accounting. Store the counting in RECORD. */
5037 static void
5038 rtl_account_profile_record (basic_block bb, int after_pass,
5039 struct profile_record *record)
5041 rtx_insn *insn;
5042 FOR_BB_INSNS (bb, insn)
5043 if (INSN_P (insn))
5045 record->size[after_pass]
5046 += insn_rtx_cost (PATTERN (insn), false);
5047 if (profile_status_for_fn (cfun) == PROFILE_READ)
5048 record->time[after_pass]
5049 += insn_rtx_cost (PATTERN (insn), true) * bb->count;
5050 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
5051 record->time[after_pass]
5052 += insn_rtx_cost (PATTERN (insn), true) * bb->frequency;
5056 /* Implementation of CFG manipulation for linearized RTL. */
5057 struct cfg_hooks rtl_cfg_hooks = {
5058 "rtl",
5059 rtl_verify_flow_info,
5060 rtl_dump_bb,
5061 rtl_dump_bb_for_graph,
5062 rtl_create_basic_block,
5063 rtl_redirect_edge_and_branch,
5064 rtl_redirect_edge_and_branch_force,
5065 rtl_can_remove_branch_p,
5066 rtl_delete_block,
5067 rtl_split_block,
5068 rtl_move_block_after,
5069 rtl_can_merge_blocks, /* can_merge_blocks_p */
5070 rtl_merge_blocks,
5071 rtl_predict_edge,
5072 rtl_predicted_by_p,
5073 cfg_layout_can_duplicate_bb_p,
5074 rtl_duplicate_bb,
5075 rtl_split_edge,
5076 rtl_make_forwarder_block,
5077 rtl_tidy_fallthru_edge,
5078 rtl_force_nonfallthru,
5079 rtl_block_ends_with_call_p,
5080 rtl_block_ends_with_condjump_p,
5081 rtl_flow_call_edges_add,
5082 NULL, /* execute_on_growing_pred */
5083 NULL, /* execute_on_shrinking_pred */
5084 NULL, /* duplicate loop for trees */
5085 NULL, /* lv_add_condition_to_bb */
5086 NULL, /* lv_adjust_loop_header_phi*/
5087 NULL, /* extract_cond_bb_edges */
5088 NULL, /* flush_pending_stmts */
5089 rtl_block_empty_p, /* block_empty_p */
5090 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5091 rtl_account_profile_record,
5094 /* Implementation of CFG manipulation for cfg layout RTL, where
5095 basic block connected via fallthru edges does not have to be adjacent.
5096 This representation will hopefully become the default one in future
5097 version of the compiler. */
5099 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5100 "cfglayout mode",
5101 rtl_verify_flow_info_1,
5102 rtl_dump_bb,
5103 rtl_dump_bb_for_graph,
5104 cfg_layout_create_basic_block,
5105 cfg_layout_redirect_edge_and_branch,
5106 cfg_layout_redirect_edge_and_branch_force,
5107 rtl_can_remove_branch_p,
5108 cfg_layout_delete_block,
5109 cfg_layout_split_block,
5110 rtl_move_block_after,
5111 cfg_layout_can_merge_blocks_p,
5112 cfg_layout_merge_blocks,
5113 rtl_predict_edge,
5114 rtl_predicted_by_p,
5115 cfg_layout_can_duplicate_bb_p,
5116 cfg_layout_duplicate_bb,
5117 cfg_layout_split_edge,
5118 rtl_make_forwarder_block,
5119 NULL, /* tidy_fallthru_edge */
5120 rtl_force_nonfallthru,
5121 rtl_block_ends_with_call_p,
5122 rtl_block_ends_with_condjump_p,
5123 rtl_flow_call_edges_add,
5124 NULL, /* execute_on_growing_pred */
5125 NULL, /* execute_on_shrinking_pred */
5126 duplicate_loop_to_header_edge, /* duplicate loop for trees */
5127 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5128 NULL, /* lv_adjust_loop_header_phi*/
5129 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5130 NULL, /* flush_pending_stmts */
5131 rtl_block_empty_p, /* block_empty_p */
5132 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5133 rtl_account_profile_record,
5136 #include "gt-cfgrtl.h"