gcc/
[official-gcc.git] / gcc / cfgrtl.c
blob4a711b3aa4f715a20356264aeef379c1cedeabe6
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 "tm.h"
44 #include "alias.h"
45 #include "symtab.h"
46 #include "tree.h"
47 #include "hard-reg-set.h"
48 #include "predict.h"
49 #include "function.h"
50 #include "dominance.h"
51 #include "cfg.h"
52 #include "cfgrtl.h"
53 #include "cfganal.h"
54 #include "cfgbuild.h"
55 #include "cfgcleanup.h"
56 #include "basic-block.h"
57 #include "bb-reorder.h"
58 #include "regs.h"
59 #include "flags.h"
60 #include "except.h"
61 #include "rtl-error.h"
62 #include "tm_p.h"
63 #include "obstack.h"
64 #include "insn-attr.h"
65 #include "insn-config.h"
66 #include "rtl.h"
67 #include "expmed.h"
68 #include "dojump.h"
69 #include "explow.h"
70 #include "calls.h"
71 #include "emit-rtl.h"
72 #include "varasm.h"
73 #include "stmt.h"
74 #include "expr.h"
75 #include "target.h"
76 #include "common/common-target.h"
77 #include "cfgloop.h"
78 #include "tree-pass.h"
79 #include "df.h"
81 /* Holds the interesting leading and trailing notes for the function.
82 Only applicable if the CFG is in cfglayout mode. */
83 static GTY(()) rtx_insn *cfg_layout_function_footer;
84 static GTY(()) rtx_insn *cfg_layout_function_header;
86 static rtx_insn *skip_insns_after_block (basic_block);
87 static void record_effective_endpoints (void);
88 static void fixup_reorder_chain (void);
90 void verify_insn_chain (void);
91 static void fixup_fallthru_exit_predecessor (void);
92 static int can_delete_note_p (const rtx_note *);
93 static int can_delete_label_p (const rtx_code_label *);
94 static basic_block rtl_split_edge (edge);
95 static bool rtl_move_block_after (basic_block, basic_block);
96 static int rtl_verify_flow_info (void);
97 static basic_block cfg_layout_split_block (basic_block, void *);
98 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
99 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
100 static void cfg_layout_delete_block (basic_block);
101 static void rtl_delete_block (basic_block);
102 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
103 static edge rtl_redirect_edge_and_branch (edge, basic_block);
104 static basic_block rtl_split_block (basic_block, void *);
105 static void rtl_dump_bb (FILE *, basic_block, int, int);
106 static int rtl_verify_flow_info_1 (void);
107 static void rtl_make_forwarder_block (edge);
109 /* Return true if NOTE is not one of the ones that must be kept paired,
110 so that we may simply delete it. */
112 static int
113 can_delete_note_p (const rtx_note *note)
115 switch (NOTE_KIND (note))
117 case NOTE_INSN_DELETED:
118 case NOTE_INSN_BASIC_BLOCK:
119 case NOTE_INSN_EPILOGUE_BEG:
120 return true;
122 default:
123 return false;
127 /* True if a given label can be deleted. */
129 static int
130 can_delete_label_p (const rtx_code_label *label)
132 return (!LABEL_PRESERVE_P (label)
133 /* User declared labels must be preserved. */
134 && LABEL_NAME (label) == 0
135 && !in_insn_list_p (forced_labels, label));
138 /* Delete INSN by patching it out. */
140 void
141 delete_insn (rtx uncast_insn)
143 rtx_insn *insn = as_a <rtx_insn *> (uncast_insn);
144 rtx note;
145 bool really_delete = true;
147 if (LABEL_P (insn))
149 /* Some labels can't be directly removed from the INSN chain, as they
150 might be references via variables, constant pool etc.
151 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
152 if (! can_delete_label_p (as_a <rtx_code_label *> (insn)))
154 const char *name = LABEL_NAME (insn);
155 basic_block bb = BLOCK_FOR_INSN (insn);
156 rtx_insn *bb_note = NEXT_INSN (insn);
158 really_delete = false;
159 PUT_CODE (insn, NOTE);
160 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
161 NOTE_DELETED_LABEL_NAME (insn) = name;
163 /* If the note following the label starts a basic block, and the
164 label is a member of the same basic block, interchange the two. */
165 if (bb_note != NULL_RTX
166 && NOTE_INSN_BASIC_BLOCK_P (bb_note)
167 && bb != NULL
168 && bb == BLOCK_FOR_INSN (bb_note))
170 reorder_insns_nobb (insn, insn, bb_note);
171 BB_HEAD (bb) = bb_note;
172 if (BB_END (bb) == bb_note)
173 BB_END (bb) = insn;
177 remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels);
180 if (really_delete)
182 /* If this insn has already been deleted, something is very wrong. */
183 gcc_assert (!insn->deleted ());
184 if (INSN_P (insn))
185 df_insn_delete (insn);
186 remove_insn (insn);
187 insn->set_deleted ();
190 /* If deleting a jump, decrement the use count of the label. Deleting
191 the label itself should happen in the normal course of block merging. */
192 if (JUMP_P (insn))
194 if (JUMP_LABEL (insn)
195 && LABEL_P (JUMP_LABEL (insn)))
196 LABEL_NUSES (JUMP_LABEL (insn))--;
198 /* If there are more targets, remove them too. */
199 while ((note
200 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
201 && LABEL_P (XEXP (note, 0)))
203 LABEL_NUSES (XEXP (note, 0))--;
204 remove_note (insn, note);
208 /* Also if deleting any insn that references a label as an operand. */
209 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
210 && LABEL_P (XEXP (note, 0)))
212 LABEL_NUSES (XEXP (note, 0))--;
213 remove_note (insn, note);
216 if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
218 rtvec vec = table->get_labels ();
219 int len = GET_NUM_ELEM (vec);
220 int i;
222 for (i = 0; i < len; i++)
224 rtx label = XEXP (RTVEC_ELT (vec, i), 0);
226 /* When deleting code in bulk (e.g. removing many unreachable
227 blocks) we can delete a label that's a target of the vector
228 before deleting the vector itself. */
229 if (!NOTE_P (label))
230 LABEL_NUSES (label)--;
235 /* Like delete_insn but also purge dead edges from BB. */
237 void
238 delete_insn_and_edges (rtx_insn *insn)
240 bool purge = false;
242 if (INSN_P (insn)
243 && BLOCK_FOR_INSN (insn)
244 && BB_END (BLOCK_FOR_INSN (insn)) == insn)
245 purge = true;
246 delete_insn (insn);
247 if (purge)
248 purge_dead_edges (BLOCK_FOR_INSN (insn));
251 /* Unlink a chain of insns between START and FINISH, leaving notes
252 that must be paired. If CLEAR_BB is true, we set bb field for
253 insns that cannot be removed to NULL. */
255 void
256 delete_insn_chain (rtx start, rtx finish, bool clear_bb)
258 rtx_insn *prev, *current;
260 /* Unchain the insns one by one. It would be quicker to delete all of these
261 with a single unchaining, rather than one at a time, but we need to keep
262 the NOTE's. */
263 current = safe_as_a <rtx_insn *> (finish);
264 while (1)
266 prev = PREV_INSN (current);
267 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
269 else
270 delete_insn (current);
272 if (clear_bb && !current->deleted ())
273 set_block_for_insn (current, NULL);
275 if (current == start)
276 break;
277 current = prev;
281 /* Create a new basic block consisting of the instructions between HEAD and END
282 inclusive. This function is designed to allow fast BB construction - reuses
283 the note and basic block struct in BB_NOTE, if any and do not grow
284 BASIC_BLOCK chain and should be used directly only by CFG construction code.
285 END can be NULL in to create new empty basic block before HEAD. Both END
286 and HEAD can be NULL to create basic block at the end of INSN chain.
287 AFTER is the basic block we should be put after. */
289 basic_block
290 create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
291 basic_block after)
293 basic_block bb;
295 if (bb_note
296 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
297 && bb->aux == NULL)
299 /* If we found an existing note, thread it back onto the chain. */
301 rtx_insn *after;
303 if (LABEL_P (head))
304 after = head;
305 else
307 after = PREV_INSN (head);
308 head = bb_note;
311 if (after != bb_note && NEXT_INSN (after) != bb_note)
312 reorder_insns_nobb (bb_note, bb_note, after);
314 else
316 /* Otherwise we must create a note and a basic block structure. */
318 bb = alloc_block ();
320 init_rtl_bb_info (bb);
321 if (!head && !end)
322 head = end = bb_note
323 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
324 else if (LABEL_P (head) && end)
326 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
327 if (head == end)
328 end = bb_note;
330 else
332 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
333 head = bb_note;
334 if (!end)
335 end = head;
338 NOTE_BASIC_BLOCK (bb_note) = bb;
341 /* Always include the bb note in the block. */
342 if (NEXT_INSN (end) == bb_note)
343 end = bb_note;
345 BB_HEAD (bb) = head;
346 BB_END (bb) = end;
347 bb->index = last_basic_block_for_fn (cfun)++;
348 bb->flags = BB_NEW | BB_RTL;
349 link_block (bb, after);
350 SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
351 df_bb_refs_record (bb->index, false);
352 update_bb_for_insn (bb);
353 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
355 /* Tag the block so that we know it has been used when considering
356 other basic block notes. */
357 bb->aux = bb;
359 return bb;
362 /* Create new basic block consisting of instructions in between HEAD and END
363 and place it to the BB chain after block AFTER. END can be NULL to
364 create a new empty basic block before HEAD. Both END and HEAD can be
365 NULL to create basic block at the end of INSN chain. */
367 static basic_block
368 rtl_create_basic_block (void *headp, void *endp, basic_block after)
370 rtx_insn *head = (rtx_insn *) headp;
371 rtx_insn *end = (rtx_insn *) endp;
372 basic_block bb;
374 /* Grow the basic block array if needed. */
375 if ((size_t) last_basic_block_for_fn (cfun)
376 >= basic_block_info_for_fn (cfun)->length ())
378 size_t new_size =
379 (last_basic_block_for_fn (cfun)
380 + (last_basic_block_for_fn (cfun) + 3) / 4);
381 vec_safe_grow_cleared (basic_block_info_for_fn (cfun), new_size);
384 n_basic_blocks_for_fn (cfun)++;
386 bb = create_basic_block_structure (head, end, NULL, after);
387 bb->aux = NULL;
388 return bb;
391 static basic_block
392 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
394 basic_block newbb = rtl_create_basic_block (head, end, after);
396 return newbb;
399 /* Delete the insns in a (non-live) block. We physically delete every
400 non-deleted-note insn, and update the flow graph appropriately.
402 Return nonzero if we deleted an exception handler. */
404 /* ??? Preserving all such notes strikes me as wrong. It would be nice
405 to post-process the stream to remove empty blocks, loops, ranges, etc. */
407 static void
408 rtl_delete_block (basic_block b)
410 rtx_insn *insn, *end;
412 /* If the head of this block is a CODE_LABEL, then it might be the
413 label for an exception handler which can't be reached. We need
414 to remove the label from the exception_handler_label list. */
415 insn = BB_HEAD (b);
417 end = get_last_bb_insn (b);
419 /* Selectively delete the entire chain. */
420 BB_HEAD (b) = NULL;
421 delete_insn_chain (insn, end, true);
424 if (dump_file)
425 fprintf (dump_file, "deleting block %d\n", b->index);
426 df_bb_delete (b->index);
429 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
431 void
432 compute_bb_for_insn (void)
434 basic_block bb;
436 FOR_EACH_BB_FN (bb, cfun)
438 rtx_insn *end = BB_END (bb);
439 rtx_insn *insn;
441 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
443 BLOCK_FOR_INSN (insn) = bb;
444 if (insn == end)
445 break;
450 /* Release the basic_block_for_insn array. */
452 unsigned int
453 free_bb_for_insn (void)
455 rtx_insn *insn;
456 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
457 if (!BARRIER_P (insn))
458 BLOCK_FOR_INSN (insn) = NULL;
459 return 0;
462 namespace {
464 const pass_data pass_data_free_cfg =
466 RTL_PASS, /* type */
467 "*free_cfg", /* name */
468 OPTGROUP_NONE, /* optinfo_flags */
469 TV_NONE, /* tv_id */
470 0, /* properties_required */
471 0, /* properties_provided */
472 PROP_cfg, /* properties_destroyed */
473 0, /* todo_flags_start */
474 0, /* todo_flags_finish */
477 class pass_free_cfg : public rtl_opt_pass
479 public:
480 pass_free_cfg (gcc::context *ctxt)
481 : rtl_opt_pass (pass_data_free_cfg, ctxt)
484 /* opt_pass methods: */
485 virtual unsigned int execute (function *);
487 }; // class pass_free_cfg
489 unsigned int
490 pass_free_cfg::execute (function *)
492 #ifdef DELAY_SLOTS
493 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
494 valid at that point so it would be too late to call df_analyze. */
495 if (optimize > 0 && flag_delayed_branch)
497 df_note_add_problem ();
498 df_analyze ();
500 #endif
502 if (crtl->has_bb_partition)
503 insert_section_boundary_note ();
505 free_bb_for_insn ();
506 return 0;
509 } // anon namespace
511 rtl_opt_pass *
512 make_pass_free_cfg (gcc::context *ctxt)
514 return new pass_free_cfg (ctxt);
517 /* Return RTX to emit after when we want to emit code on the entry of function. */
518 rtx_insn *
519 entry_of_function (void)
521 return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
522 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
525 /* Emit INSN at the entry point of the function, ensuring that it is only
526 executed once per function. */
527 void
528 emit_insn_at_entry (rtx insn)
530 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
531 edge e = ei_safe_edge (ei);
532 gcc_assert (e->flags & EDGE_FALLTHRU);
534 insert_insn_on_edge (insn, e);
535 commit_edge_insertions ();
538 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
539 (or BARRIER if found) and notify df of the bb change.
540 The insn chain range is inclusive
541 (i.e. both BEGIN and END will be updated. */
543 static void
544 update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
546 rtx_insn *insn;
548 end = NEXT_INSN (end);
549 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
550 if (!BARRIER_P (insn))
551 df_insn_change_bb (insn, bb);
554 /* Update BLOCK_FOR_INSN of insns in BB to BB,
555 and notify df of the change. */
557 void
558 update_bb_for_insn (basic_block bb)
560 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
564 /* Like active_insn_p, except keep the return value clobber around
565 even after reload. */
567 static bool
568 flow_active_insn_p (const rtx_insn *insn)
570 if (active_insn_p (insn))
571 return true;
573 /* A clobber of the function return value exists for buggy
574 programs that fail to return a value. Its effect is to
575 keep the return value from being live across the entire
576 function. If we allow it to be skipped, we introduce the
577 possibility for register lifetime confusion. */
578 if (GET_CODE (PATTERN (insn)) == CLOBBER
579 && REG_P (XEXP (PATTERN (insn), 0))
580 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
581 return true;
583 return false;
586 /* Return true if the block has no effect and only forwards control flow to
587 its single destination. */
589 bool
590 contains_no_active_insn_p (const_basic_block bb)
592 rtx_insn *insn;
594 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
595 || !single_succ_p (bb))
596 return false;
598 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
599 if (INSN_P (insn) && flow_active_insn_p (insn))
600 return false;
602 return (!INSN_P (insn)
603 || (JUMP_P (insn) && simplejump_p (insn))
604 || !flow_active_insn_p (insn));
607 /* Likewise, but protect loop latches, headers and preheaders. */
608 /* FIXME: Make this a cfg hook. */
610 bool
611 forwarder_block_p (const_basic_block bb)
613 if (!contains_no_active_insn_p (bb))
614 return false;
616 /* Protect loop latches, headers and preheaders. */
617 if (current_loops)
619 basic_block dest;
620 if (bb->loop_father->header == bb)
621 return false;
622 dest = EDGE_SUCC (bb, 0)->dest;
623 if (dest->loop_father->header == dest)
624 return false;
627 return true;
630 /* Return nonzero if we can reach target from src by falling through. */
631 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
633 bool
634 can_fallthru (basic_block src, basic_block target)
636 rtx_insn *insn = BB_END (src);
637 rtx_insn *insn2;
638 edge e;
639 edge_iterator ei;
641 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
642 return true;
643 if (src->next_bb != target)
644 return false;
646 /* ??? Later we may add code to move jump tables offline. */
647 if (tablejump_p (insn, NULL, NULL))
648 return false;
650 FOR_EACH_EDGE (e, ei, src->succs)
651 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
652 && e->flags & EDGE_FALLTHRU)
653 return false;
655 insn2 = BB_HEAD (target);
656 if (!active_insn_p (insn2))
657 insn2 = next_active_insn (insn2);
659 return next_active_insn (insn) == insn2;
662 /* Return nonzero if we could reach target from src by falling through,
663 if the target was made adjacent. If we already have a fall-through
664 edge to the exit block, we can't do that. */
665 static bool
666 could_fall_through (basic_block src, basic_block target)
668 edge e;
669 edge_iterator ei;
671 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
672 return true;
673 FOR_EACH_EDGE (e, ei, src->succs)
674 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
675 && e->flags & EDGE_FALLTHRU)
676 return 0;
677 return true;
680 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
681 rtx_note *
682 bb_note (basic_block bb)
684 rtx_insn *note;
686 note = BB_HEAD (bb);
687 if (LABEL_P (note))
688 note = NEXT_INSN (note);
690 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
691 return as_a <rtx_note *> (note);
694 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
695 note associated with the BLOCK. */
697 static rtx_insn *
698 first_insn_after_basic_block_note (basic_block block)
700 rtx_insn *insn;
702 /* Get the first instruction in the block. */
703 insn = BB_HEAD (block);
705 if (insn == NULL_RTX)
706 return NULL;
707 if (LABEL_P (insn))
708 insn = NEXT_INSN (insn);
709 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
711 return NEXT_INSN (insn);
714 /* Creates a new basic block just after basic block BB by splitting
715 everything after specified instruction INSNP. */
717 static basic_block
718 rtl_split_block (basic_block bb, void *insnp)
720 basic_block new_bb;
721 rtx_insn *insn = (rtx_insn *) insnp;
722 edge e;
723 edge_iterator ei;
725 if (!insn)
727 insn = first_insn_after_basic_block_note (bb);
729 if (insn)
731 rtx_insn *next = insn;
733 insn = PREV_INSN (insn);
735 /* If the block contains only debug insns, insn would have
736 been NULL in a non-debug compilation, and then we'd end
737 up emitting a DELETED note. For -fcompare-debug
738 stability, emit the note too. */
739 if (insn != BB_END (bb)
740 && DEBUG_INSN_P (next)
741 && DEBUG_INSN_P (BB_END (bb)))
743 while (next != BB_END (bb) && DEBUG_INSN_P (next))
744 next = NEXT_INSN (next);
746 if (next == BB_END (bb))
747 emit_note_after (NOTE_INSN_DELETED, next);
750 else
751 insn = get_last_insn ();
754 /* We probably should check type of the insn so that we do not create
755 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
756 bother. */
757 if (insn == BB_END (bb))
758 emit_note_after (NOTE_INSN_DELETED, insn);
760 /* Create the new basic block. */
761 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
762 BB_COPY_PARTITION (new_bb, bb);
763 BB_END (bb) = insn;
765 /* Redirect the outgoing edges. */
766 new_bb->succs = bb->succs;
767 bb->succs = NULL;
768 FOR_EACH_EDGE (e, ei, new_bb->succs)
769 e->src = new_bb;
771 /* The new block starts off being dirty. */
772 df_set_bb_dirty (bb);
773 return new_bb;
776 /* Return true if the single edge between blocks A and B is the only place
777 in RTL which holds some unique locus. */
779 static bool
780 unique_locus_on_edge_between_p (basic_block a, basic_block b)
782 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
783 rtx_insn *insn, *end;
785 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
786 return false;
788 /* First scan block A backward. */
789 insn = BB_END (a);
790 end = PREV_INSN (BB_HEAD (a));
791 while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
792 insn = PREV_INSN (insn);
794 if (insn != end && INSN_LOCATION (insn) == goto_locus)
795 return false;
797 /* Then scan block B forward. */
798 insn = BB_HEAD (b);
799 if (insn)
801 end = NEXT_INSN (BB_END (b));
802 while (insn != end && !NONDEBUG_INSN_P (insn))
803 insn = NEXT_INSN (insn);
805 if (insn != end && INSN_HAS_LOCATION (insn)
806 && INSN_LOCATION (insn) == goto_locus)
807 return false;
810 return true;
813 /* If the single edge between blocks A and B is the only place in RTL which
814 holds some unique locus, emit a nop with that locus between the blocks. */
816 static void
817 emit_nop_for_unique_locus_between (basic_block a, basic_block b)
819 if (!unique_locus_on_edge_between_p (a, b))
820 return;
822 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
823 INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
826 /* Blocks A and B are to be merged into a single block A. The insns
827 are already contiguous. */
829 static void
830 rtl_merge_blocks (basic_block a, basic_block b)
832 rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
833 rtx_insn *del_first = NULL, *del_last = NULL;
834 rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
835 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
836 int b_empty = 0;
838 if (dump_file)
839 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
840 a->index);
842 while (DEBUG_INSN_P (b_end))
843 b_end = PREV_INSN (b_debug_start = b_end);
845 /* If there was a CODE_LABEL beginning B, delete it. */
846 if (LABEL_P (b_head))
848 /* Detect basic blocks with nothing but a label. This can happen
849 in particular at the end of a function. */
850 if (b_head == b_end)
851 b_empty = 1;
853 del_first = del_last = b_head;
854 b_head = NEXT_INSN (b_head);
857 /* Delete the basic block note and handle blocks containing just that
858 note. */
859 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
861 if (b_head == b_end)
862 b_empty = 1;
863 if (! del_last)
864 del_first = b_head;
866 del_last = b_head;
867 b_head = NEXT_INSN (b_head);
870 /* If there was a jump out of A, delete it. */
871 if (JUMP_P (a_end))
873 rtx_insn *prev;
875 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
876 if (!NOTE_P (prev)
877 || NOTE_INSN_BASIC_BLOCK_P (prev)
878 || prev == BB_HEAD (a))
879 break;
881 del_first = a_end;
883 /* If this was a conditional jump, we need to also delete
884 the insn that set cc0. */
885 if (HAVE_cc0 && only_sets_cc0_p (prev))
887 rtx_insn *tmp = prev;
889 prev = prev_nonnote_insn (prev);
890 if (!prev)
891 prev = BB_HEAD (a);
892 del_first = tmp;
895 a_end = PREV_INSN (del_first);
897 else if (BARRIER_P (NEXT_INSN (a_end)))
898 del_first = NEXT_INSN (a_end);
900 /* Delete everything marked above as well as crap that might be
901 hanging out between the two blocks. */
902 BB_END (a) = a_end;
903 BB_HEAD (b) = b_empty ? NULL : b_head;
904 delete_insn_chain (del_first, del_last, true);
906 /* When not optimizing and the edge is the only place in RTL which holds
907 some unique locus, emit a nop with that locus in between. */
908 if (!optimize)
910 emit_nop_for_unique_locus_between (a, b);
911 a_end = BB_END (a);
914 /* Reassociate the insns of B with A. */
915 if (!b_empty)
917 update_bb_for_insn_chain (a_end, b_debug_end, a);
919 BB_END (a) = b_debug_end;
920 BB_HEAD (b) = NULL;
922 else if (b_end != b_debug_end)
924 /* Move any deleted labels and other notes between the end of A
925 and the debug insns that make up B after the debug insns,
926 bringing the debug insns into A while keeping the notes after
927 the end of A. */
928 if (NEXT_INSN (a_end) != b_debug_start)
929 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
930 b_debug_end);
931 update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
932 BB_END (a) = b_debug_end;
935 df_bb_delete (b->index);
937 /* If B was a forwarder block, propagate the locus on the edge. */
938 if (forwarder_p
939 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
940 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
942 if (dump_file)
943 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
947 /* Return true when block A and B can be merged. */
949 static bool
950 rtl_can_merge_blocks (basic_block a, basic_block b)
952 /* If we are partitioning hot/cold basic blocks, we don't want to
953 mess up unconditional or indirect jumps that cross between hot
954 and cold sections.
956 Basic block partitioning may result in some jumps that appear to
957 be optimizable (or blocks that appear to be mergeable), but which really
958 must be left untouched (they are required to make it safely across
959 partition boundaries). See the comments at the top of
960 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
962 if (BB_PARTITION (a) != BB_PARTITION (b))
963 return false;
965 /* Protect the loop latches. */
966 if (current_loops && b->loop_father->latch == b)
967 return false;
969 /* There must be exactly one edge in between the blocks. */
970 return (single_succ_p (a)
971 && single_succ (a) == b
972 && single_pred_p (b)
973 && a != b
974 /* Must be simple edge. */
975 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
976 && a->next_bb == b
977 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
978 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
979 /* If the jump insn has side effects,
980 we can't kill the edge. */
981 && (!JUMP_P (BB_END (a))
982 || (reload_completed
983 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
986 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
987 exist. */
989 rtx_code_label *
990 block_label (basic_block block)
992 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
993 return NULL;
995 if (!LABEL_P (BB_HEAD (block)))
997 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
1000 return as_a <rtx_code_label *> (BB_HEAD (block));
1003 /* Attempt to perform edge redirection by replacing possibly complex jump
1004 instruction by unconditional jump or removing jump completely. This can
1005 apply only if all edges now point to the same block. The parameters and
1006 return values are equivalent to redirect_edge_and_branch. */
1008 edge
1009 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
1011 basic_block src = e->src;
1012 rtx_insn *insn = BB_END (src), *kill_from;
1013 rtx set;
1014 int fallthru = 0;
1016 /* If we are partitioning hot/cold basic blocks, we don't want to
1017 mess up unconditional or indirect jumps that cross between hot
1018 and cold sections.
1020 Basic block partitioning may result in some jumps that appear to
1021 be optimizable (or blocks that appear to be mergeable), but which really
1022 must be left untouched (they are required to make it safely across
1023 partition boundaries). See the comments at the top of
1024 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1026 if (BB_PARTITION (src) != BB_PARTITION (target))
1027 return NULL;
1029 /* We can replace or remove a complex jump only when we have exactly
1030 two edges. Also, if we have exactly one outgoing edge, we can
1031 redirect that. */
1032 if (EDGE_COUNT (src->succs) >= 3
1033 /* Verify that all targets will be TARGET. Specifically, the
1034 edge that is not E must also go to TARGET. */
1035 || (EDGE_COUNT (src->succs) == 2
1036 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1037 return NULL;
1039 if (!onlyjump_p (insn))
1040 return NULL;
1041 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1042 return NULL;
1044 /* Avoid removing branch with side effects. */
1045 set = single_set (insn);
1046 if (!set || side_effects_p (set))
1047 return NULL;
1049 /* In case we zap a conditional jump, we'll need to kill
1050 the cc0 setter too. */
1051 kill_from = insn;
1052 if (HAVE_cc0 && reg_mentioned_p (cc0_rtx, PATTERN (insn))
1053 && only_sets_cc0_p (PREV_INSN (insn)))
1054 kill_from = PREV_INSN (insn);
1056 /* See if we can create the fallthru edge. */
1057 if (in_cfglayout || can_fallthru (src, target))
1059 if (dump_file)
1060 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1061 fallthru = 1;
1063 /* Selectively unlink whole insn chain. */
1064 if (in_cfglayout)
1066 rtx_insn *insn = BB_FOOTER (src);
1068 delete_insn_chain (kill_from, BB_END (src), false);
1070 /* Remove barriers but keep jumptables. */
1071 while (insn)
1073 if (BARRIER_P (insn))
1075 if (PREV_INSN (insn))
1076 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1077 else
1078 BB_FOOTER (src) = NEXT_INSN (insn);
1079 if (NEXT_INSN (insn))
1080 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1082 if (LABEL_P (insn))
1083 break;
1084 insn = NEXT_INSN (insn);
1087 else
1088 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
1089 false);
1092 /* If this already is simplejump, redirect it. */
1093 else if (simplejump_p (insn))
1095 if (e->dest == target)
1096 return NULL;
1097 if (dump_file)
1098 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1099 INSN_UID (insn), e->dest->index, target->index);
1100 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1101 block_label (target), 0))
1103 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1104 return NULL;
1108 /* Cannot do anything for target exit block. */
1109 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1110 return NULL;
1112 /* Or replace possibly complicated jump insn by simple jump insn. */
1113 else
1115 rtx_code_label *target_label = block_label (target);
1116 rtx_insn *barrier;
1117 rtx label;
1118 rtx_jump_table_data *table;
1120 emit_jump_insn_after_noloc (targetm.gen_jump (target_label), insn);
1121 JUMP_LABEL (BB_END (src)) = target_label;
1122 LABEL_NUSES (target_label)++;
1123 if (dump_file)
1124 fprintf (dump_file, "Replacing insn %i by jump %i\n",
1125 INSN_UID (insn), INSN_UID (BB_END (src)));
1128 delete_insn_chain (kill_from, insn, false);
1130 /* Recognize a tablejump that we are converting to a
1131 simple jump and remove its associated CODE_LABEL
1132 and ADDR_VEC or ADDR_DIFF_VEC. */
1133 if (tablejump_p (insn, &label, &table))
1134 delete_insn_chain (label, table, false);
1136 barrier = next_nonnote_insn (BB_END (src));
1137 if (!barrier || !BARRIER_P (barrier))
1138 emit_barrier_after (BB_END (src));
1139 else
1141 if (barrier != NEXT_INSN (BB_END (src)))
1143 /* Move the jump before barrier so that the notes
1144 which originally were or were created before jump table are
1145 inside the basic block. */
1146 rtx_insn *new_insn = BB_END (src);
1148 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1149 PREV_INSN (barrier), src);
1151 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1152 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1154 SET_NEXT_INSN (new_insn) = barrier;
1155 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1157 SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1158 SET_PREV_INSN (barrier) = new_insn;
1163 /* Keep only one edge out and set proper flags. */
1164 if (!single_succ_p (src))
1165 remove_edge (e);
1166 gcc_assert (single_succ_p (src));
1168 e = single_succ_edge (src);
1169 if (fallthru)
1170 e->flags = EDGE_FALLTHRU;
1171 else
1172 e->flags = 0;
1174 e->probability = REG_BR_PROB_BASE;
1175 e->count = src->count;
1177 if (e->dest != target)
1178 redirect_edge_succ (e, target);
1179 return e;
1182 /* Subroutine of redirect_branch_edge that tries to patch the jump
1183 instruction INSN so that it reaches block NEW. Do this
1184 only when it originally reached block OLD. Return true if this
1185 worked or the original target wasn't OLD, return false if redirection
1186 doesn't work. */
1188 static bool
1189 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1191 rtx_jump_table_data *table;
1192 rtx tmp;
1193 /* Recognize a tablejump and adjust all matching cases. */
1194 if (tablejump_p (insn, NULL, &table))
1196 rtvec vec;
1197 int j;
1198 rtx_code_label *new_label = block_label (new_bb);
1200 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1201 return false;
1202 vec = table->get_labels ();
1204 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1205 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1207 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1208 --LABEL_NUSES (old_label);
1209 ++LABEL_NUSES (new_label);
1212 /* Handle casesi dispatch insns. */
1213 if ((tmp = single_set (insn)) != NULL
1214 && SET_DEST (tmp) == pc_rtx
1215 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1216 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1217 && LABEL_REF_LABEL (XEXP (SET_SRC (tmp), 2)) == old_label)
1219 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1220 new_label);
1221 --LABEL_NUSES (old_label);
1222 ++LABEL_NUSES (new_label);
1225 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1227 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1228 rtx note;
1230 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1231 return false;
1232 rtx_code_label *new_label = block_label (new_bb);
1234 for (i = 0; i < n; ++i)
1236 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1237 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1238 if (XEXP (old_ref, 0) == old_label)
1240 ASM_OPERANDS_LABEL (tmp, i)
1241 = gen_rtx_LABEL_REF (Pmode, new_label);
1242 --LABEL_NUSES (old_label);
1243 ++LABEL_NUSES (new_label);
1247 if (JUMP_LABEL (insn) == old_label)
1249 JUMP_LABEL (insn) = new_label;
1250 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1251 if (note)
1252 remove_note (insn, note);
1254 else
1256 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1257 if (note)
1258 remove_note (insn, note);
1259 if (JUMP_LABEL (insn) != new_label
1260 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1261 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1263 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1264 != NULL_RTX)
1265 XEXP (note, 0) = new_label;
1267 else
1269 /* ?? We may play the games with moving the named labels from
1270 one basic block to the other in case only one computed_jump is
1271 available. */
1272 if (computed_jump_p (insn)
1273 /* A return instruction can't be redirected. */
1274 || returnjump_p (insn))
1275 return false;
1277 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1279 /* If the insn doesn't go where we think, we're confused. */
1280 gcc_assert (JUMP_LABEL (insn) == old_label);
1282 /* If the substitution doesn't succeed, die. This can happen
1283 if the back end emitted unrecognizable instructions or if
1284 target is exit block on some arches. */
1285 if (!redirect_jump (as_a <rtx_jump_insn *> (insn),
1286 block_label (new_bb), 0))
1288 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun));
1289 return false;
1293 return true;
1297 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1298 NULL on failure */
1299 static edge
1300 redirect_branch_edge (edge e, basic_block target)
1302 rtx_insn *old_label = BB_HEAD (e->dest);
1303 basic_block src = e->src;
1304 rtx_insn *insn = BB_END (src);
1306 /* We can only redirect non-fallthru edges of jump insn. */
1307 if (e->flags & EDGE_FALLTHRU)
1308 return NULL;
1309 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1310 return NULL;
1312 if (!currently_expanding_to_rtl)
1314 if (!patch_jump_insn (as_a <rtx_jump_insn *> (insn), old_label, target))
1315 return NULL;
1317 else
1318 /* When expanding this BB might actually contain multiple
1319 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1320 Redirect all of those that match our label. */
1321 FOR_BB_INSNS (src, insn)
1322 if (JUMP_P (insn) && !patch_jump_insn (as_a <rtx_jump_insn *> (insn),
1323 old_label, target))
1324 return NULL;
1326 if (dump_file)
1327 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1328 e->src->index, e->dest->index, target->index);
1330 if (e->dest != target)
1331 e = redirect_edge_succ_nodup (e, target);
1333 return e;
1336 /* Called when edge E has been redirected to a new destination,
1337 in order to update the region crossing flag on the edge and
1338 jump. */
1340 static void
1341 fixup_partition_crossing (edge e)
1343 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1344 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1345 return;
1346 /* If we redirected an existing edge, it may already be marked
1347 crossing, even though the new src is missing a reg crossing note.
1348 But make sure reg crossing note doesn't already exist before
1349 inserting. */
1350 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1352 e->flags |= EDGE_CROSSING;
1353 if (JUMP_P (BB_END (e->src))
1354 && !CROSSING_JUMP_P (BB_END (e->src)))
1355 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1357 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1359 e->flags &= ~EDGE_CROSSING;
1360 /* Remove the section crossing note from jump at end of
1361 src if it exists, and if no other successors are
1362 still crossing. */
1363 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1365 bool has_crossing_succ = false;
1366 edge e2;
1367 edge_iterator ei;
1368 FOR_EACH_EDGE (e2, ei, e->src->succs)
1370 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1371 if (has_crossing_succ)
1372 break;
1374 if (!has_crossing_succ)
1375 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1380 /* Called when block BB has been reassigned to the cold partition,
1381 because it is now dominated by another cold block,
1382 to ensure that the region crossing attributes are updated. */
1384 static void
1385 fixup_new_cold_bb (basic_block bb)
1387 edge e;
1388 edge_iterator ei;
1390 /* This is called when a hot bb is found to now be dominated
1391 by a cold bb and therefore needs to become cold. Therefore,
1392 its preds will no longer be region crossing. Any non-dominating
1393 preds that were previously hot would also have become cold
1394 in the caller for the same region. Any preds that were previously
1395 region-crossing will be adjusted in fixup_partition_crossing. */
1396 FOR_EACH_EDGE (e, ei, bb->preds)
1398 fixup_partition_crossing (e);
1401 /* Possibly need to make bb's successor edges region crossing,
1402 or remove stale region crossing. */
1403 FOR_EACH_EDGE (e, ei, bb->succs)
1405 /* We can't have fall-through edges across partition boundaries.
1406 Note that force_nonfallthru will do any necessary partition
1407 boundary fixup by calling fixup_partition_crossing itself. */
1408 if ((e->flags & EDGE_FALLTHRU)
1409 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1410 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1411 force_nonfallthru (e);
1412 else
1413 fixup_partition_crossing (e);
1417 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1418 expense of adding new instructions or reordering basic blocks.
1420 Function can be also called with edge destination equivalent to the TARGET.
1421 Then it should try the simplifications and do nothing if none is possible.
1423 Return edge representing the branch if transformation succeeded. Return NULL
1424 on failure.
1425 We still return NULL in case E already destinated TARGET and we didn't
1426 managed to simplify instruction stream. */
1428 static edge
1429 rtl_redirect_edge_and_branch (edge e, basic_block target)
1431 edge ret;
1432 basic_block src = e->src;
1433 basic_block dest = e->dest;
1435 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1436 return NULL;
1438 if (dest == target)
1439 return e;
1441 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1443 df_set_bb_dirty (src);
1444 fixup_partition_crossing (ret);
1445 return ret;
1448 ret = redirect_branch_edge (e, target);
1449 if (!ret)
1450 return NULL;
1452 df_set_bb_dirty (src);
1453 fixup_partition_crossing (ret);
1454 return ret;
1457 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1459 void
1460 emit_barrier_after_bb (basic_block bb)
1462 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1463 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1464 || current_ir_type () == IR_RTL_CFGLAYOUT);
1465 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1467 rtx_insn *insn = unlink_insn_chain (barrier, barrier);
1469 if (BB_FOOTER (bb))
1471 rtx_insn *footer_tail = BB_FOOTER (bb);
1473 while (NEXT_INSN (footer_tail))
1474 footer_tail = NEXT_INSN (footer_tail);
1475 if (!BARRIER_P (footer_tail))
1477 SET_NEXT_INSN (footer_tail) = insn;
1478 SET_PREV_INSN (insn) = footer_tail;
1481 else
1482 BB_FOOTER (bb) = insn;
1486 /* Like force_nonfallthru below, but additionally performs redirection
1487 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1488 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1489 simple_return_rtx, indicating which kind of returnjump to create.
1490 It should be NULL otherwise. */
1492 basic_block
1493 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1495 basic_block jump_block, new_bb = NULL, src = e->src;
1496 rtx note;
1497 edge new_edge;
1498 int abnormal_edge_flags = 0;
1499 bool asm_goto_edge = false;
1500 int loc;
1502 /* In the case the last instruction is conditional jump to the next
1503 instruction, first redirect the jump itself and then continue
1504 by creating a basic block afterwards to redirect fallthru edge. */
1505 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1506 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1507 && any_condjump_p (BB_END (e->src))
1508 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1510 rtx note;
1511 edge b = unchecked_make_edge (e->src, target, 0);
1512 bool redirected;
1514 redirected = redirect_jump (as_a <rtx_jump_insn *> (BB_END (e->src)),
1515 block_label (target), 0);
1516 gcc_assert (redirected);
1518 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1519 if (note)
1521 int prob = XINT (note, 0);
1523 b->probability = prob;
1524 /* Update this to use GCOV_COMPUTE_SCALE. */
1525 b->count = e->count * prob / REG_BR_PROB_BASE;
1526 e->probability -= e->probability;
1527 e->count -= b->count;
1528 if (e->probability < 0)
1529 e->probability = 0;
1530 if (e->count < 0)
1531 e->count = 0;
1535 if (e->flags & EDGE_ABNORMAL)
1537 /* Irritating special case - fallthru edge to the same block as abnormal
1538 edge.
1539 We can't redirect abnormal edge, but we still can split the fallthru
1540 one and create separate abnormal edge to original destination.
1541 This allows bb-reorder to make such edge non-fallthru. */
1542 gcc_assert (e->dest == target);
1543 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1544 e->flags &= EDGE_FALLTHRU;
1546 else
1548 gcc_assert (e->flags & EDGE_FALLTHRU);
1549 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1551 /* We can't redirect the entry block. Create an empty block
1552 at the start of the function which we use to add the new
1553 jump. */
1554 edge tmp;
1555 edge_iterator ei;
1556 bool found = false;
1558 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1559 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1561 /* Change the existing edge's source to be the new block, and add
1562 a new edge from the entry block to the new block. */
1563 e->src = bb;
1564 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1565 (tmp = ei_safe_edge (ei)); )
1567 if (tmp == e)
1569 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1570 found = true;
1571 break;
1573 else
1574 ei_next (&ei);
1577 gcc_assert (found);
1579 vec_safe_push (bb->succs, e);
1580 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1581 EDGE_FALLTHRU);
1585 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1586 don't point to the target or fallthru label. */
1587 if (JUMP_P (BB_END (e->src))
1588 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1589 && (e->flags & EDGE_FALLTHRU)
1590 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1592 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1593 bool adjust_jump_target = false;
1595 for (i = 0; i < n; ++i)
1597 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1599 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1600 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1601 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1602 adjust_jump_target = true;
1604 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1605 asm_goto_edge = true;
1607 if (adjust_jump_target)
1609 rtx_insn *insn = BB_END (e->src);
1610 rtx note;
1611 rtx_insn *old_label = BB_HEAD (e->dest);
1612 rtx_insn *new_label = BB_HEAD (target);
1614 if (JUMP_LABEL (insn) == old_label)
1616 JUMP_LABEL (insn) = new_label;
1617 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1618 if (note)
1619 remove_note (insn, note);
1621 else
1623 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1624 if (note)
1625 remove_note (insn, note);
1626 if (JUMP_LABEL (insn) != new_label
1627 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1628 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1630 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1631 != NULL_RTX)
1632 XEXP (note, 0) = new_label;
1636 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1638 rtx_insn *new_head;
1639 gcov_type count = e->count;
1640 int probability = e->probability;
1641 /* Create the new structures. */
1643 /* If the old block ended with a tablejump, skip its table
1644 by searching forward from there. Otherwise start searching
1645 forward from the last instruction of the old block. */
1646 rtx_jump_table_data *table;
1647 if (tablejump_p (BB_END (e->src), NULL, &table))
1648 new_head = table;
1649 else
1650 new_head = BB_END (e->src);
1651 new_head = NEXT_INSN (new_head);
1653 jump_block = create_basic_block (new_head, NULL, e->src);
1654 jump_block->count = count;
1655 jump_block->frequency = EDGE_FREQUENCY (e);
1657 /* Make sure new block ends up in correct hot/cold section. */
1659 BB_COPY_PARTITION (jump_block, e->src);
1661 /* Wire edge in. */
1662 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1663 new_edge->probability = probability;
1664 new_edge->count = count;
1666 /* Redirect old edge. */
1667 redirect_edge_pred (e, jump_block);
1668 e->probability = REG_BR_PROB_BASE;
1670 /* If e->src was previously region crossing, it no longer is
1671 and the reg crossing note should be removed. */
1672 fixup_partition_crossing (new_edge);
1674 /* If asm goto has any label refs to target's label,
1675 add also edge from asm goto bb to target. */
1676 if (asm_goto_edge)
1678 new_edge->probability /= 2;
1679 new_edge->count /= 2;
1680 jump_block->count /= 2;
1681 jump_block->frequency /= 2;
1682 new_edge = make_edge (new_edge->src, target,
1683 e->flags & ~EDGE_FALLTHRU);
1684 new_edge->probability = probability - probability / 2;
1685 new_edge->count = count - count / 2;
1688 new_bb = jump_block;
1690 else
1691 jump_block = e->src;
1693 loc = e->goto_locus;
1694 e->flags &= ~EDGE_FALLTHRU;
1695 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1697 if (jump_label == ret_rtx)
1698 emit_jump_insn_after_setloc (targetm.gen_return (),
1699 BB_END (jump_block), loc);
1700 else
1702 gcc_assert (jump_label == simple_return_rtx);
1703 emit_jump_insn_after_setloc (targetm.gen_simple_return (),
1704 BB_END (jump_block), loc);
1706 set_return_jump_label (BB_END (jump_block));
1708 else
1710 rtx_code_label *label = block_label (target);
1711 emit_jump_insn_after_setloc (targetm.gen_jump (label),
1712 BB_END (jump_block), loc);
1713 JUMP_LABEL (BB_END (jump_block)) = label;
1714 LABEL_NUSES (label)++;
1717 /* We might be in cfg layout mode, and if so, the following routine will
1718 insert the barrier correctly. */
1719 emit_barrier_after_bb (jump_block);
1720 redirect_edge_succ_nodup (e, target);
1722 if (abnormal_edge_flags)
1723 make_edge (src, target, abnormal_edge_flags);
1725 df_mark_solutions_dirty ();
1726 fixup_partition_crossing (e);
1727 return new_bb;
1730 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1731 (and possibly create new basic block) to make edge non-fallthru.
1732 Return newly created BB or NULL if none. */
1734 static basic_block
1735 rtl_force_nonfallthru (edge e)
1737 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1740 /* Redirect edge even at the expense of creating new jump insn or
1741 basic block. Return new basic block if created, NULL otherwise.
1742 Conversion must be possible. */
1744 static basic_block
1745 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1747 if (redirect_edge_and_branch (e, target)
1748 || e->dest == target)
1749 return NULL;
1751 /* In case the edge redirection failed, try to force it to be non-fallthru
1752 and redirect newly created simplejump. */
1753 df_set_bb_dirty (e->src);
1754 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1757 /* The given edge should potentially be a fallthru edge. If that is in
1758 fact true, delete the jump and barriers that are in the way. */
1760 static void
1761 rtl_tidy_fallthru_edge (edge e)
1763 rtx_insn *q;
1764 basic_block b = e->src, c = b->next_bb;
1766 /* ??? In a late-running flow pass, other folks may have deleted basic
1767 blocks by nopping out blocks, leaving multiple BARRIERs between here
1768 and the target label. They ought to be chastised and fixed.
1770 We can also wind up with a sequence of undeletable labels between
1771 one block and the next.
1773 So search through a sequence of barriers, labels, and notes for
1774 the head of block C and assert that we really do fall through. */
1776 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1777 if (INSN_P (q))
1778 return;
1780 /* Remove what will soon cease being the jump insn from the source block.
1781 If block B consisted only of this single jump, turn it into a deleted
1782 note. */
1783 q = BB_END (b);
1784 if (JUMP_P (q)
1785 && onlyjump_p (q)
1786 && (any_uncondjump_p (q)
1787 || single_succ_p (b)))
1789 rtx label;
1790 rtx_jump_table_data *table;
1792 if (tablejump_p (q, &label, &table))
1794 /* The label is likely mentioned in some instruction before
1795 the tablejump and might not be DCEd, so turn it into
1796 a note instead and move before the tablejump that is going to
1797 be deleted. */
1798 const char *name = LABEL_NAME (label);
1799 PUT_CODE (label, NOTE);
1800 NOTE_KIND (label) = NOTE_INSN_DELETED_LABEL;
1801 NOTE_DELETED_LABEL_NAME (label) = name;
1802 rtx_insn *lab = safe_as_a <rtx_insn *> (label);
1803 reorder_insns (lab, lab, PREV_INSN (q));
1804 delete_insn (table);
1807 /* If this was a conditional jump, we need to also delete
1808 the insn that set cc0. */
1809 if (HAVE_cc0 && any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1810 q = PREV_INSN (q);
1812 q = PREV_INSN (q);
1815 /* Selectively unlink the sequence. */
1816 if (q != PREV_INSN (BB_HEAD (c)))
1817 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1819 e->flags |= EDGE_FALLTHRU;
1822 /* Should move basic block BB after basic block AFTER. NIY. */
1824 static bool
1825 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1826 basic_block after ATTRIBUTE_UNUSED)
1828 return false;
1831 /* Locate the last bb in the same partition as START_BB. */
1833 static basic_block
1834 last_bb_in_partition (basic_block start_bb)
1836 basic_block bb;
1837 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1839 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1840 return bb;
1842 /* Return bb before the exit block. */
1843 return bb->prev_bb;
1846 /* Split a (typically critical) edge. Return the new block.
1847 The edge must not be abnormal.
1849 ??? The code generally expects to be called on critical edges.
1850 The case of a block ending in an unconditional jump to a
1851 block with multiple predecessors is not handled optimally. */
1853 static basic_block
1854 rtl_split_edge (edge edge_in)
1856 basic_block bb, new_bb;
1857 rtx_insn *before;
1859 /* Abnormal edges cannot be split. */
1860 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1862 /* We are going to place the new block in front of edge destination.
1863 Avoid existence of fallthru predecessors. */
1864 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1866 edge e = find_fallthru_edge (edge_in->dest->preds);
1868 if (e)
1869 force_nonfallthru (e);
1872 /* Create the basic block note. */
1873 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1874 before = BB_HEAD (edge_in->dest);
1875 else
1876 before = NULL;
1878 /* If this is a fall through edge to the exit block, the blocks might be
1879 not adjacent, and the right place is after the source. */
1880 if ((edge_in->flags & EDGE_FALLTHRU)
1881 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1883 before = NEXT_INSN (BB_END (edge_in->src));
1884 bb = create_basic_block (before, NULL, edge_in->src);
1885 BB_COPY_PARTITION (bb, edge_in->src);
1887 else
1889 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1891 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1892 BB_COPY_PARTITION (bb, edge_in->dest);
1894 else
1896 basic_block after = edge_in->dest->prev_bb;
1897 /* If this is post-bb reordering, and the edge crosses a partition
1898 boundary, the new block needs to be inserted in the bb chain
1899 at the end of the src partition (since we put the new bb into
1900 that partition, see below). Otherwise we may end up creating
1901 an extra partition crossing in the chain, which is illegal.
1902 It can't go after the src, because src may have a fall-through
1903 to a different block. */
1904 if (crtl->bb_reorder_complete
1905 && (edge_in->flags & EDGE_CROSSING))
1907 after = last_bb_in_partition (edge_in->src);
1908 before = get_last_bb_insn (after);
1909 /* The instruction following the last bb in partition should
1910 be a barrier, since it cannot end in a fall-through. */
1911 gcc_checking_assert (BARRIER_P (before));
1912 before = NEXT_INSN (before);
1914 bb = create_basic_block (before, NULL, after);
1915 /* Put the split bb into the src partition, to avoid creating
1916 a situation where a cold bb dominates a hot bb, in the case
1917 where src is cold and dest is hot. The src will dominate
1918 the new bb (whereas it might not have dominated dest). */
1919 BB_COPY_PARTITION (bb, edge_in->src);
1923 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1925 /* Can't allow a region crossing edge to be fallthrough. */
1926 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1927 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1929 new_bb = force_nonfallthru (single_succ_edge (bb));
1930 gcc_assert (!new_bb);
1933 /* For non-fallthru edges, we must adjust the predecessor's
1934 jump instruction to target our new block. */
1935 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1937 edge redirected = redirect_edge_and_branch (edge_in, bb);
1938 gcc_assert (redirected);
1940 else
1942 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1944 /* For asm goto even splitting of fallthru edge might
1945 need insn patching, as other labels might point to the
1946 old label. */
1947 rtx_insn *last = BB_END (edge_in->src);
1948 if (last
1949 && JUMP_P (last)
1950 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1951 && extract_asm_operands (PATTERN (last)) != NULL_RTX
1952 && patch_jump_insn (last, before, bb))
1953 df_set_bb_dirty (edge_in->src);
1955 redirect_edge_succ (edge_in, bb);
1958 return bb;
1961 /* Queue instructions for insertion on an edge between two basic blocks.
1962 The new instructions and basic blocks (if any) will not appear in the
1963 CFG until commit_edge_insertions is called. */
1965 void
1966 insert_insn_on_edge (rtx pattern, edge e)
1968 /* We cannot insert instructions on an abnormal critical edge.
1969 It will be easier to find the culprit if we die now. */
1970 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1972 if (e->insns.r == NULL_RTX)
1973 start_sequence ();
1974 else
1975 push_to_sequence (e->insns.r);
1977 emit_insn (pattern);
1979 e->insns.r = get_insns ();
1980 end_sequence ();
1983 /* Update the CFG for the instructions queued on edge E. */
1985 void
1986 commit_one_edge_insertion (edge e)
1988 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1989 basic_block bb;
1991 /* Pull the insns off the edge now since the edge might go away. */
1992 insns = e->insns.r;
1993 e->insns.r = NULL;
1995 /* Figure out where to put these insns. If the destination has
1996 one predecessor, insert there. Except for the exit block. */
1997 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1999 bb = e->dest;
2001 /* Get the location correct wrt a code label, and "nice" wrt
2002 a basic block note, and before everything else. */
2003 tmp = BB_HEAD (bb);
2004 if (LABEL_P (tmp))
2005 tmp = NEXT_INSN (tmp);
2006 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
2007 tmp = NEXT_INSN (tmp);
2008 if (tmp == BB_HEAD (bb))
2009 before = tmp;
2010 else if (tmp)
2011 after = PREV_INSN (tmp);
2012 else
2013 after = get_last_insn ();
2016 /* If the source has one successor and the edge is not abnormal,
2017 insert there. Except for the entry block.
2018 Don't do this if the predecessor ends in a jump other than
2019 unconditional simple jump. E.g. for asm goto that points all
2020 its labels at the fallthru basic block, we can't insert instructions
2021 before the asm goto, as the asm goto can have various of side effects,
2022 and can't emit instructions after the asm goto, as it must end
2023 the basic block. */
2024 else if ((e->flags & EDGE_ABNORMAL) == 0
2025 && single_succ_p (e->src)
2026 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2027 && (!JUMP_P (BB_END (e->src))
2028 || simplejump_p (BB_END (e->src))))
2030 bb = e->src;
2032 /* It is possible to have a non-simple jump here. Consider a target
2033 where some forms of unconditional jumps clobber a register. This
2034 happens on the fr30 for example.
2036 We know this block has a single successor, so we can just emit
2037 the queued insns before the jump. */
2038 if (JUMP_P (BB_END (bb)))
2039 before = BB_END (bb);
2040 else
2042 /* We'd better be fallthru, or we've lost track of what's what. */
2043 gcc_assert (e->flags & EDGE_FALLTHRU);
2045 after = BB_END (bb);
2049 /* Otherwise we must split the edge. */
2050 else
2052 bb = split_edge (e);
2054 /* If E crossed a partition boundary, we needed to make bb end in
2055 a region-crossing jump, even though it was originally fallthru. */
2056 if (JUMP_P (BB_END (bb)))
2057 before = BB_END (bb);
2058 else
2059 after = BB_END (bb);
2062 /* Now that we've found the spot, do the insertion. */
2063 if (before)
2065 emit_insn_before_noloc (insns, before, bb);
2066 last = prev_nonnote_insn (before);
2068 else
2069 last = emit_insn_after_noloc (insns, after, bb);
2071 if (returnjump_p (last))
2073 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2074 This is not currently a problem because this only happens
2075 for the (single) epilogue, which already has a fallthru edge
2076 to EXIT. */
2078 e = single_succ_edge (bb);
2079 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2080 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2082 e->flags &= ~EDGE_FALLTHRU;
2083 emit_barrier_after (last);
2085 if (before)
2086 delete_insn (before);
2088 else
2089 gcc_assert (!JUMP_P (last));
2092 /* Update the CFG for all queued instructions. */
2094 void
2095 commit_edge_insertions (void)
2097 basic_block bb;
2099 /* Optimization passes that invoke this routine can cause hot blocks
2100 previously reached by both hot and cold blocks to become dominated only
2101 by cold blocks. This will cause the verification below to fail,
2102 and lead to now cold code in the hot section. In some cases this
2103 may only be visible after newly unreachable blocks are deleted,
2104 which will be done by fixup_partitions. */
2105 fixup_partitions ();
2107 #ifdef ENABLE_CHECKING
2108 verify_flow_info ();
2109 #endif
2111 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2112 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2114 edge e;
2115 edge_iterator ei;
2117 FOR_EACH_EDGE (e, ei, bb->succs)
2118 if (e->insns.r)
2119 commit_one_edge_insertion (e);
2124 /* Print out RTL-specific basic block information (live information
2125 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2126 documented in dumpfile.h. */
2128 static void
2129 rtl_dump_bb (FILE *outf, basic_block bb, int indent, int flags)
2131 rtx_insn *insn;
2132 rtx_insn *last;
2133 char *s_indent;
2135 s_indent = (char *) alloca ((size_t) indent + 1);
2136 memset (s_indent, ' ', (size_t) indent);
2137 s_indent[indent] = '\0';
2139 if (df && (flags & TDF_DETAILS))
2141 df_dump_top (bb, outf);
2142 putc ('\n', outf);
2145 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK)
2146 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
2147 insn = NEXT_INSN (insn))
2149 if (flags & TDF_DETAILS)
2150 df_dump_insn_top (insn, outf);
2151 if (! (flags & TDF_SLIM))
2152 print_rtl_single (outf, insn);
2153 else
2154 dump_insn_slim (outf, insn);
2155 if (flags & TDF_DETAILS)
2156 df_dump_insn_bottom (insn, outf);
2159 if (df && (flags & TDF_DETAILS))
2161 df_dump_bottom (bb, outf);
2162 putc ('\n', outf);
2167 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2168 for the start of each basic block. FLAGS are the TDF_* masks documented
2169 in dumpfile.h. */
2171 void
2172 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, int flags)
2174 const rtx_insn *tmp_rtx;
2175 if (rtx_first == 0)
2176 fprintf (outf, "(nil)\n");
2177 else
2179 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2180 int max_uid = get_max_uid ();
2181 basic_block *start = XCNEWVEC (basic_block, max_uid);
2182 basic_block *end = XCNEWVEC (basic_block, max_uid);
2183 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2184 basic_block bb;
2186 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2187 insns, but the CFG is not maintained so the basic block info
2188 is not reliable. Therefore it's omitted from the dumps. */
2189 if (! (cfun->curr_properties & PROP_cfg))
2190 flags &= ~TDF_BLOCKS;
2192 if (df)
2193 df_dump_start (outf);
2195 if (flags & TDF_BLOCKS)
2197 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2199 rtx_insn *x;
2201 start[INSN_UID (BB_HEAD (bb))] = bb;
2202 end[INSN_UID (BB_END (bb))] = bb;
2203 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2205 enum bb_state state = IN_MULTIPLE_BB;
2207 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2208 state = IN_ONE_BB;
2209 in_bb_p[INSN_UID (x)] = state;
2211 if (x == BB_END (bb))
2212 break;
2217 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
2219 if (flags & TDF_BLOCKS)
2221 bb = start[INSN_UID (tmp_rtx)];
2222 if (bb != NULL)
2224 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, true, false);
2225 if (df && (flags & TDF_DETAILS))
2226 df_dump_top (bb, outf);
2229 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2230 && !NOTE_P (tmp_rtx)
2231 && !BARRIER_P (tmp_rtx))
2232 fprintf (outf, ";; Insn is not within a basic block\n");
2233 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2234 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2237 if (flags & TDF_DETAILS)
2238 df_dump_insn_top (tmp_rtx, outf);
2239 if (! (flags & TDF_SLIM))
2240 print_rtl_single (outf, tmp_rtx);
2241 else
2242 dump_insn_slim (outf, tmp_rtx);
2243 if (flags & TDF_DETAILS)
2244 df_dump_insn_bottom (tmp_rtx, outf);
2246 if (flags & TDF_BLOCKS)
2248 bb = end[INSN_UID (tmp_rtx)];
2249 if (bb != NULL)
2251 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, false, true);
2252 if (df && (flags & TDF_DETAILS))
2253 df_dump_bottom (bb, outf);
2254 putc ('\n', outf);
2259 free (start);
2260 free (end);
2261 free (in_bb_p);
2265 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2267 void
2268 update_br_prob_note (basic_block bb)
2270 rtx note;
2271 if (!JUMP_P (BB_END (bb)))
2272 return;
2273 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2274 if (!note || XINT (note, 0) == BRANCH_EDGE (bb)->probability)
2275 return;
2276 XINT (note, 0) = BRANCH_EDGE (bb)->probability;
2279 /* Get the last insn associated with block BB (that includes barriers and
2280 tablejumps after BB). */
2281 rtx_insn *
2282 get_last_bb_insn (basic_block bb)
2284 rtx_jump_table_data *table;
2285 rtx_insn *tmp;
2286 rtx_insn *end = BB_END (bb);
2288 /* Include any jump table following the basic block. */
2289 if (tablejump_p (end, NULL, &table))
2290 end = table;
2292 /* Include any barriers that may follow the basic block. */
2293 tmp = next_nonnote_insn_bb (end);
2294 while (tmp && BARRIER_P (tmp))
2296 end = tmp;
2297 tmp = next_nonnote_insn_bb (end);
2300 return end;
2303 /* Sanity check partition hotness to ensure that basic blocks in
2304   the cold partition don't dominate basic blocks in the hot partition.
2305 If FLAG_ONLY is true, report violations as errors. Otherwise
2306 re-mark the dominated blocks as cold, since this is run after
2307 cfg optimizations that may make hot blocks previously reached
2308 by both hot and cold blocks now only reachable along cold paths. */
2310 static vec<basic_block>
2311 find_partition_fixes (bool flag_only)
2313 basic_block bb;
2314 vec<basic_block> bbs_in_cold_partition = vNULL;
2315 vec<basic_block> bbs_to_fix = vNULL;
2317 /* Callers check this. */
2318 gcc_checking_assert (crtl->has_bb_partition);
2320 FOR_EACH_BB_FN (bb, cfun)
2321 if ((BB_PARTITION (bb) == BB_COLD_PARTITION))
2322 bbs_in_cold_partition.safe_push (bb);
2324 if (bbs_in_cold_partition.is_empty ())
2325 return vNULL;
2327 bool dom_calculated_here = !dom_info_available_p (CDI_DOMINATORS);
2329 if (dom_calculated_here)
2330 calculate_dominance_info (CDI_DOMINATORS);
2332 while (! bbs_in_cold_partition.is_empty ())
2334 bb = bbs_in_cold_partition.pop ();
2335 /* Any blocks dominated by a block in the cold section
2336 must also be cold. */
2337 basic_block son;
2338 for (son = first_dom_son (CDI_DOMINATORS, bb);
2339 son;
2340 son = next_dom_son (CDI_DOMINATORS, son))
2342 /* If son is not yet cold, then mark it cold here and
2343 enqueue it for further processing. */
2344 if ((BB_PARTITION (son) != BB_COLD_PARTITION))
2346 if (flag_only)
2347 error ("non-cold basic block %d dominated "
2348 "by a block in the cold partition (%d)", son->index, bb->index);
2349 else
2350 BB_SET_PARTITION (son, BB_COLD_PARTITION);
2351 bbs_to_fix.safe_push (son);
2352 bbs_in_cold_partition.safe_push (son);
2357 if (dom_calculated_here)
2358 free_dominance_info (CDI_DOMINATORS);
2360 return bbs_to_fix;
2363 /* Perform cleanup on the hot/cold bb partitioning after optimization
2364 passes that modify the cfg. */
2366 void
2367 fixup_partitions (void)
2369 basic_block bb;
2371 if (!crtl->has_bb_partition)
2372 return;
2374 /* Delete any blocks that became unreachable and weren't
2375 already cleaned up, for example during edge forwarding
2376 and convert_jumps_to_returns. This will expose more
2377 opportunities for fixing the partition boundaries here.
2378 Also, the calculation of the dominance graph during verification
2379 will assert if there are unreachable nodes. */
2380 delete_unreachable_blocks ();
2382 /* If there are partitions, do a sanity check on them: A basic block in
2383   a cold partition cannot dominate a basic block in a hot partition.
2384 Fixup any that now violate this requirement, as a result of edge
2385 forwarding and unreachable block deletion.  */
2386 vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2388 /* Do the partition fixup after all necessary blocks have been converted to
2389 cold, so that we only update the region crossings the minimum number of
2390 places, which can require forcing edges to be non fallthru. */
2391 while (! bbs_to_fix.is_empty ())
2393 bb = bbs_to_fix.pop ();
2394 fixup_new_cold_bb (bb);
2398 /* Verify, in the basic block chain, that there is at most one switch
2399 between hot/cold partitions. This condition will not be true until
2400 after reorder_basic_blocks is called. */
2402 static int
2403 verify_hot_cold_block_grouping (void)
2405 basic_block bb;
2406 int err = 0;
2407 bool switched_sections = false;
2408 int current_partition = BB_UNPARTITIONED;
2410 /* Even after bb reordering is complete, we go into cfglayout mode
2411 again (in compgoto). Ensure we don't call this before going back
2412 into linearized RTL when any layout fixes would have been committed. */
2413 if (!crtl->bb_reorder_complete
2414 || current_ir_type () != IR_RTL_CFGRTL)
2415 return err;
2417 FOR_EACH_BB_FN (bb, cfun)
2419 if (current_partition != BB_UNPARTITIONED
2420 && BB_PARTITION (bb) != current_partition)
2422 if (switched_sections)
2424 error ("multiple hot/cold transitions found (bb %i)",
2425 bb->index);
2426 err = 1;
2428 else
2429 switched_sections = true;
2431 if (!crtl->has_bb_partition)
2432 error ("partition found but function partition flag not set");
2434 current_partition = BB_PARTITION (bb);
2437 return err;
2441 /* Perform several checks on the edges out of each block, such as
2442 the consistency of the branch probabilities, the correctness
2443 of hot/cold partition crossing edges, and the number of expected
2444 successor edges. Also verify that the dominance relationship
2445 between hot/cold blocks is sane. */
2447 static int
2448 rtl_verify_edges (void)
2450 int err = 0;
2451 basic_block bb;
2453 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2455 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2456 int n_eh = 0, n_abnormal = 0;
2457 edge e, fallthru = NULL;
2458 edge_iterator ei;
2459 rtx note;
2460 bool has_crossing_edge = false;
2462 if (JUMP_P (BB_END (bb))
2463 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2464 && EDGE_COUNT (bb->succs) >= 2
2465 && any_condjump_p (BB_END (bb)))
2467 if (XINT (note, 0) != BRANCH_EDGE (bb)->probability
2468 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2470 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2471 XINT (note, 0), BRANCH_EDGE (bb)->probability);
2472 err = 1;
2476 FOR_EACH_EDGE (e, ei, bb->succs)
2478 bool is_crossing;
2480 if (e->flags & EDGE_FALLTHRU)
2481 n_fallthru++, fallthru = e;
2483 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2484 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2485 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2486 has_crossing_edge |= is_crossing;
2487 if (e->flags & EDGE_CROSSING)
2489 if (!is_crossing)
2491 error ("EDGE_CROSSING incorrectly set across same section");
2492 err = 1;
2494 if (e->flags & EDGE_FALLTHRU)
2496 error ("fallthru edge crosses section boundary in bb %i",
2497 e->src->index);
2498 err = 1;
2500 if (e->flags & EDGE_EH)
2502 error ("EH edge crosses section boundary in bb %i",
2503 e->src->index);
2504 err = 1;
2506 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2508 error ("No region crossing jump at section boundary in bb %i",
2509 bb->index);
2510 err = 1;
2513 else if (is_crossing)
2515 error ("EDGE_CROSSING missing across section boundary");
2516 err = 1;
2519 if ((e->flags & ~(EDGE_DFS_BACK
2520 | EDGE_CAN_FALLTHRU
2521 | EDGE_IRREDUCIBLE_LOOP
2522 | EDGE_LOOP_EXIT
2523 | EDGE_CROSSING
2524 | EDGE_PRESERVE)) == 0)
2525 n_branch++;
2527 if (e->flags & EDGE_ABNORMAL_CALL)
2528 n_abnormal_call++;
2530 if (e->flags & EDGE_SIBCALL)
2531 n_sibcall++;
2533 if (e->flags & EDGE_EH)
2534 n_eh++;
2536 if (e->flags & EDGE_ABNORMAL)
2537 n_abnormal++;
2540 if (!has_crossing_edge
2541 && JUMP_P (BB_END (bb))
2542 && CROSSING_JUMP_P (BB_END (bb)))
2544 print_rtl_with_bb (stderr, get_insns (), TDF_RTL | TDF_BLOCKS | TDF_DETAILS);
2545 error ("Region crossing jump across same section in bb %i",
2546 bb->index);
2547 err = 1;
2550 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2552 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2553 err = 1;
2555 if (n_eh > 1)
2557 error ("too many exception handling edges in bb %i", bb->index);
2558 err = 1;
2560 if (n_branch
2561 && (!JUMP_P (BB_END (bb))
2562 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2563 || any_condjump_p (BB_END (bb))))))
2565 error ("too many outgoing branch edges from bb %i", bb->index);
2566 err = 1;
2568 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2570 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2571 err = 1;
2573 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2575 error ("wrong number of branch edges after unconditional jump"
2576 " in bb %i", bb->index);
2577 err = 1;
2579 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2580 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2582 error ("wrong amount of branch edges after conditional jump"
2583 " in bb %i", bb->index);
2584 err = 1;
2586 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2588 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2589 err = 1;
2591 if (n_sibcall && !CALL_P (BB_END (bb)))
2593 error ("sibcall edges for non-call insn in bb %i", bb->index);
2594 err = 1;
2596 if (n_abnormal > n_eh
2597 && !(CALL_P (BB_END (bb))
2598 && n_abnormal == n_abnormal_call + n_sibcall)
2599 && (!JUMP_P (BB_END (bb))
2600 || any_condjump_p (BB_END (bb))
2601 || any_uncondjump_p (BB_END (bb))))
2603 error ("abnormal edges for no purpose in bb %i", bb->index);
2604 err = 1;
2608 /* If there are partitions, do a sanity check on them: A basic block in
2609   a cold partition cannot dominate a basic block in a hot partition.  */
2610 if (crtl->has_bb_partition && !err)
2612 vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2613 err = !bbs_to_fix.is_empty ();
2616 /* Clean up. */
2617 return err;
2620 /* Checks on the instructions within blocks. Currently checks that each
2621 block starts with a basic block note, and that basic block notes and
2622 control flow jumps are not found in the middle of the block. */
2624 static int
2625 rtl_verify_bb_insns (void)
2627 rtx_insn *x;
2628 int err = 0;
2629 basic_block bb;
2631 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2633 /* Now check the header of basic
2634 block. It ought to contain optional CODE_LABEL followed
2635 by NOTE_BASIC_BLOCK. */
2636 x = BB_HEAD (bb);
2637 if (LABEL_P (x))
2639 if (BB_END (bb) == x)
2641 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2642 bb->index);
2643 err = 1;
2646 x = NEXT_INSN (x);
2649 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2651 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2652 bb->index);
2653 err = 1;
2656 if (BB_END (bb) == x)
2657 /* Do checks for empty blocks here. */
2659 else
2660 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2662 if (NOTE_INSN_BASIC_BLOCK_P (x))
2664 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2665 INSN_UID (x), bb->index);
2666 err = 1;
2669 if (x == BB_END (bb))
2670 break;
2672 if (control_flow_insn_p (x))
2674 error ("in basic block %d:", bb->index);
2675 fatal_insn ("flow control insn inside a basic block", x);
2680 /* Clean up. */
2681 return err;
2684 /* Verify that block pointers for instructions in basic blocks, headers and
2685 footers are set appropriately. */
2687 static int
2688 rtl_verify_bb_pointers (void)
2690 int err = 0;
2691 basic_block bb;
2693 /* Check the general integrity of the basic blocks. */
2694 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2696 rtx_insn *insn;
2698 if (!(bb->flags & BB_RTL))
2700 error ("BB_RTL flag not set for block %d", bb->index);
2701 err = 1;
2704 FOR_BB_INSNS (bb, insn)
2705 if (BLOCK_FOR_INSN (insn) != bb)
2707 error ("insn %d basic block pointer is %d, should be %d",
2708 INSN_UID (insn),
2709 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2710 bb->index);
2711 err = 1;
2714 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2715 if (!BARRIER_P (insn)
2716 && BLOCK_FOR_INSN (insn) != NULL)
2718 error ("insn %d in header of bb %d has non-NULL basic block",
2719 INSN_UID (insn), bb->index);
2720 err = 1;
2722 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2723 if (!BARRIER_P (insn)
2724 && BLOCK_FOR_INSN (insn) != NULL)
2726 error ("insn %d in footer of bb %d has non-NULL basic block",
2727 INSN_UID (insn), bb->index);
2728 err = 1;
2732 /* Clean up. */
2733 return err;
2736 /* Verify the CFG and RTL consistency common for both underlying RTL and
2737 cfglayout RTL.
2739 Currently it does following checks:
2741 - overlapping of basic blocks
2742 - insns with wrong BLOCK_FOR_INSN pointers
2743 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2744 - tails of basic blocks (ensure that boundary is necessary)
2745 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2746 and NOTE_INSN_BASIC_BLOCK
2747 - verify that no fall_thru edge crosses hot/cold partition boundaries
2748 - verify that there are no pending RTL branch predictions
2749 - verify that hot blocks are not dominated by cold blocks
2751 In future it can be extended check a lot of other stuff as well
2752 (reachability of basic blocks, life information, etc. etc.). */
2754 static int
2755 rtl_verify_flow_info_1 (void)
2757 int err = 0;
2759 err |= rtl_verify_bb_pointers ();
2761 err |= rtl_verify_bb_insns ();
2763 err |= rtl_verify_edges ();
2765 return err;
2768 /* Walk the instruction chain and verify that bb head/end pointers
2769 are correct, and that instructions are in exactly one bb and have
2770 correct block pointers. */
2772 static int
2773 rtl_verify_bb_insn_chain (void)
2775 basic_block bb;
2776 int err = 0;
2777 rtx_insn *x;
2778 rtx_insn *last_head = get_last_insn ();
2779 basic_block *bb_info;
2780 const int max_uid = get_max_uid ();
2782 bb_info = XCNEWVEC (basic_block, max_uid);
2784 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2786 rtx_insn *head = BB_HEAD (bb);
2787 rtx_insn *end = BB_END (bb);
2789 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2791 /* Verify the end of the basic block is in the INSN chain. */
2792 if (x == end)
2793 break;
2795 /* And that the code outside of basic blocks has NULL bb field. */
2796 if (!BARRIER_P (x)
2797 && BLOCK_FOR_INSN (x) != NULL)
2799 error ("insn %d outside of basic blocks has non-NULL bb field",
2800 INSN_UID (x));
2801 err = 1;
2805 if (!x)
2807 error ("end insn %d for block %d not found in the insn stream",
2808 INSN_UID (end), bb->index);
2809 err = 1;
2812 /* Work backwards from the end to the head of the basic block
2813 to verify the head is in the RTL chain. */
2814 for (; x != NULL_RTX; x = PREV_INSN (x))
2816 /* While walking over the insn chain, verify insns appear
2817 in only one basic block. */
2818 if (bb_info[INSN_UID (x)] != NULL)
2820 error ("insn %d is in multiple basic blocks (%d and %d)",
2821 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2822 err = 1;
2825 bb_info[INSN_UID (x)] = bb;
2827 if (x == head)
2828 break;
2830 if (!x)
2832 error ("head insn %d for block %d not found in the insn stream",
2833 INSN_UID (head), bb->index);
2834 err = 1;
2837 last_head = PREV_INSN (x);
2840 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2842 /* Check that the code before the first basic block has NULL
2843 bb field. */
2844 if (!BARRIER_P (x)
2845 && BLOCK_FOR_INSN (x) != NULL)
2847 error ("insn %d outside of basic blocks has non-NULL bb field",
2848 INSN_UID (x));
2849 err = 1;
2852 free (bb_info);
2854 return err;
2857 /* Verify that fallthru edges point to adjacent blocks in layout order and
2858 that barriers exist after non-fallthru blocks. */
2860 static int
2861 rtl_verify_fallthru (void)
2863 basic_block bb;
2864 int err = 0;
2866 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2868 edge e;
2870 e = find_fallthru_edge (bb->succs);
2871 if (!e)
2873 rtx_insn *insn;
2875 /* Ensure existence of barrier in BB with no fallthru edges. */
2876 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
2878 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
2880 error ("missing barrier after block %i", bb->index);
2881 err = 1;
2882 break;
2884 if (BARRIER_P (insn))
2885 break;
2888 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2889 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2891 rtx_insn *insn;
2893 if (e->src->next_bb != e->dest)
2895 error
2896 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2897 e->src->index, e->dest->index);
2898 err = 1;
2900 else
2901 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2902 insn = NEXT_INSN (insn))
2903 if (BARRIER_P (insn) || INSN_P (insn))
2905 error ("verify_flow_info: Incorrect fallthru %i->%i",
2906 e->src->index, e->dest->index);
2907 fatal_insn ("wrong insn in the fallthru edge", insn);
2908 err = 1;
2913 return err;
2916 /* Verify that blocks are laid out in consecutive order. While walking the
2917 instructions, verify that all expected instructions are inside the basic
2918 blocks, and that all returns are followed by barriers. */
2920 static int
2921 rtl_verify_bb_layout (void)
2923 basic_block bb;
2924 int err = 0;
2925 rtx_insn *x;
2926 int num_bb_notes;
2927 rtx_insn * const rtx_first = get_insns ();
2928 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
2930 num_bb_notes = 0;
2931 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
2933 for (x = rtx_first; x; x = NEXT_INSN (x))
2935 if (NOTE_INSN_BASIC_BLOCK_P (x))
2937 bb = NOTE_BASIC_BLOCK (x);
2939 num_bb_notes++;
2940 if (bb != last_bb_seen->next_bb)
2941 internal_error ("basic blocks not laid down consecutively");
2943 curr_bb = last_bb_seen = bb;
2946 if (!curr_bb)
2948 switch (GET_CODE (x))
2950 case BARRIER:
2951 case NOTE:
2952 break;
2954 case CODE_LABEL:
2955 /* An ADDR_VEC is placed outside any basic block. */
2956 if (NEXT_INSN (x)
2957 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
2958 x = NEXT_INSN (x);
2960 /* But in any case, non-deletable labels can appear anywhere. */
2961 break;
2963 default:
2964 fatal_insn ("insn outside basic block", x);
2968 if (JUMP_P (x)
2969 && returnjump_p (x) && ! condjump_p (x)
2970 && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_insn (x))))
2971 fatal_insn ("return not followed by barrier", x);
2973 if (curr_bb && x == BB_END (curr_bb))
2974 curr_bb = NULL;
2977 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
2978 internal_error
2979 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2980 num_bb_notes, n_basic_blocks_for_fn (cfun));
2982 return err;
2985 /* Verify the CFG and RTL consistency common for both underlying RTL and
2986 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2988 Currently it does following checks:
2989 - all checks of rtl_verify_flow_info_1
2990 - test head/end pointers
2991 - check that blocks are laid out in consecutive order
2992 - check that all insns are in the basic blocks
2993 (except the switch handling code, barriers and notes)
2994 - check that all returns are followed by barriers
2995 - check that all fallthru edge points to the adjacent blocks
2996 - verify that there is a single hot/cold partition boundary after bbro */
2998 static int
2999 rtl_verify_flow_info (void)
3001 int err = 0;
3003 err |= rtl_verify_flow_info_1 ();
3005 err |= rtl_verify_bb_insn_chain ();
3007 err |= rtl_verify_fallthru ();
3009 err |= rtl_verify_bb_layout ();
3011 err |= verify_hot_cold_block_grouping ();
3013 return err;
3016 /* Assume that the preceding pass has possibly eliminated jump instructions
3017 or converted the unconditional jumps. Eliminate the edges from CFG.
3018 Return true if any edges are eliminated. */
3020 bool
3021 purge_dead_edges (basic_block bb)
3023 edge e;
3024 rtx_insn *insn = BB_END (bb);
3025 rtx note;
3026 bool purged = false;
3027 bool found;
3028 edge_iterator ei;
3030 if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb))
3032 insn = PREV_INSN (insn);
3033 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3035 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3036 if (NONJUMP_INSN_P (insn)
3037 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3039 rtx eqnote;
3041 if (! may_trap_p (PATTERN (insn))
3042 || ((eqnote = find_reg_equal_equiv_note (insn))
3043 && ! may_trap_p (XEXP (eqnote, 0))))
3044 remove_note (insn, note);
3047 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3048 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3050 bool remove = false;
3052 /* There are three types of edges we need to handle correctly here: EH
3053 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3054 latter can appear when nonlocal gotos are used. */
3055 if (e->flags & EDGE_ABNORMAL_CALL)
3057 if (!CALL_P (insn))
3058 remove = true;
3059 else if (can_nonlocal_goto (insn))
3061 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3063 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3065 else
3066 remove = true;
3068 else if (e->flags & EDGE_EH)
3069 remove = !can_throw_internal (insn);
3071 if (remove)
3073 remove_edge (e);
3074 df_set_bb_dirty (bb);
3075 purged = true;
3077 else
3078 ei_next (&ei);
3081 if (JUMP_P (insn))
3083 rtx note;
3084 edge b,f;
3085 edge_iterator ei;
3087 /* We do care only about conditional jumps and simplejumps. */
3088 if (!any_condjump_p (insn)
3089 && !returnjump_p (insn)
3090 && !simplejump_p (insn))
3091 return purged;
3093 /* Branch probability/prediction notes are defined only for
3094 condjumps. We've possibly turned condjump into simplejump. */
3095 if (simplejump_p (insn))
3097 note = find_reg_note (insn, REG_BR_PROB, NULL);
3098 if (note)
3099 remove_note (insn, note);
3100 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3101 remove_note (insn, note);
3104 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3106 /* Avoid abnormal flags to leak from computed jumps turned
3107 into simplejumps. */
3109 e->flags &= ~EDGE_ABNORMAL;
3111 /* See if this edge is one we should keep. */
3112 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3113 /* A conditional jump can fall through into the next
3114 block, so we should keep the edge. */
3116 ei_next (&ei);
3117 continue;
3119 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3120 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3121 /* If the destination block is the target of the jump,
3122 keep the edge. */
3124 ei_next (&ei);
3125 continue;
3127 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3128 && returnjump_p (insn))
3129 /* If the destination block is the exit block, and this
3130 instruction is a return, then keep the edge. */
3132 ei_next (&ei);
3133 continue;
3135 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3136 /* Keep the edges that correspond to exceptions thrown by
3137 this instruction and rematerialize the EDGE_ABNORMAL
3138 flag we just cleared above. */
3140 e->flags |= EDGE_ABNORMAL;
3141 ei_next (&ei);
3142 continue;
3145 /* We do not need this edge. */
3146 df_set_bb_dirty (bb);
3147 purged = true;
3148 remove_edge (e);
3151 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3152 return purged;
3154 if (dump_file)
3155 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3157 if (!optimize)
3158 return purged;
3160 /* Redistribute probabilities. */
3161 if (single_succ_p (bb))
3163 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3164 single_succ_edge (bb)->count = bb->count;
3166 else
3168 note = find_reg_note (insn, REG_BR_PROB, NULL);
3169 if (!note)
3170 return purged;
3172 b = BRANCH_EDGE (bb);
3173 f = FALLTHRU_EDGE (bb);
3174 b->probability = XINT (note, 0);
3175 f->probability = REG_BR_PROB_BASE - b->probability;
3176 /* Update these to use GCOV_COMPUTE_SCALE. */
3177 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
3178 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
3181 return purged;
3183 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3185 /* First, there should not be any EH or ABCALL edges resulting
3186 from non-local gotos and the like. If there were, we shouldn't
3187 have created the sibcall in the first place. Second, there
3188 should of course never have been a fallthru edge. */
3189 gcc_assert (single_succ_p (bb));
3190 gcc_assert (single_succ_edge (bb)->flags
3191 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3193 return 0;
3196 /* If we don't see a jump insn, we don't know exactly why the block would
3197 have been broken at this point. Look for a simple, non-fallthru edge,
3198 as these are only created by conditional branches. If we find such an
3199 edge we know that there used to be a jump here and can then safely
3200 remove all non-fallthru edges. */
3201 found = false;
3202 FOR_EACH_EDGE (e, ei, bb->succs)
3203 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3205 found = true;
3206 break;
3209 if (!found)
3210 return purged;
3212 /* Remove all but the fake and fallthru edges. The fake edge may be
3213 the only successor for this block in the case of noreturn
3214 calls. */
3215 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3217 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3219 df_set_bb_dirty (bb);
3220 remove_edge (e);
3221 purged = true;
3223 else
3224 ei_next (&ei);
3227 gcc_assert (single_succ_p (bb));
3229 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3230 single_succ_edge (bb)->count = bb->count;
3232 if (dump_file)
3233 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3234 bb->index);
3235 return purged;
3238 /* Search all basic blocks for potentially dead edges and purge them. Return
3239 true if some edge has been eliminated. */
3241 bool
3242 purge_all_dead_edges (void)
3244 int purged = false;
3245 basic_block bb;
3247 FOR_EACH_BB_FN (bb, cfun)
3249 bool purged_here = purge_dead_edges (bb);
3251 purged |= purged_here;
3254 return purged;
3257 /* This is used by a few passes that emit some instructions after abnormal
3258 calls, moving the basic block's end, while they in fact do want to emit
3259 them on the fallthru edge. Look for abnormal call edges, find backward
3260 the call in the block and insert the instructions on the edge instead.
3262 Similarly, handle instructions throwing exceptions internally.
3264 Return true when instructions have been found and inserted on edges. */
3266 bool
3267 fixup_abnormal_edges (void)
3269 bool inserted = false;
3270 basic_block bb;
3272 FOR_EACH_BB_FN (bb, cfun)
3274 edge e;
3275 edge_iterator ei;
3277 /* Look for cases we are interested in - calls or instructions causing
3278 exceptions. */
3279 FOR_EACH_EDGE (e, ei, bb->succs)
3280 if ((e->flags & EDGE_ABNORMAL_CALL)
3281 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3282 == (EDGE_ABNORMAL | EDGE_EH)))
3283 break;
3285 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3287 rtx_insn *insn;
3289 /* Get past the new insns generated. Allow notes, as the insns
3290 may be already deleted. */
3291 insn = BB_END (bb);
3292 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3293 && !can_throw_internal (insn)
3294 && insn != BB_HEAD (bb))
3295 insn = PREV_INSN (insn);
3297 if (CALL_P (insn) || can_throw_internal (insn))
3299 rtx_insn *stop, *next;
3301 e = find_fallthru_edge (bb->succs);
3303 stop = NEXT_INSN (BB_END (bb));
3304 BB_END (bb) = insn;
3306 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3308 next = NEXT_INSN (insn);
3309 if (INSN_P (insn))
3311 delete_insn (insn);
3313 /* Sometimes there's still the return value USE.
3314 If it's placed after a trapping call (i.e. that
3315 call is the last insn anyway), we have no fallthru
3316 edge. Simply delete this use and don't try to insert
3317 on the non-existent edge. */
3318 if (GET_CODE (PATTERN (insn)) != USE)
3320 /* We're not deleting it, we're moving it. */
3321 insn->set_undeleted ();
3322 SET_PREV_INSN (insn) = NULL_RTX;
3323 SET_NEXT_INSN (insn) = NULL_RTX;
3325 insert_insn_on_edge (insn, e);
3326 inserted = true;
3329 else if (!BARRIER_P (insn))
3330 set_block_for_insn (insn, NULL);
3334 /* It may be that we don't find any trapping insn. In this
3335 case we discovered quite late that the insn that had been
3336 marked as can_throw_internal in fact couldn't trap at all.
3337 So we should in fact delete the EH edges out of the block. */
3338 else
3339 purge_dead_edges (bb);
3343 return inserted;
3346 /* Cut the insns from FIRST to LAST out of the insns stream. */
3348 rtx_insn *
3349 unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3351 rtx_insn *prevfirst = PREV_INSN (first);
3352 rtx_insn *nextlast = NEXT_INSN (last);
3354 SET_PREV_INSN (first) = NULL;
3355 SET_NEXT_INSN (last) = NULL;
3356 if (prevfirst)
3357 SET_NEXT_INSN (prevfirst) = nextlast;
3358 if (nextlast)
3359 SET_PREV_INSN (nextlast) = prevfirst;
3360 else
3361 set_last_insn (prevfirst);
3362 if (!prevfirst)
3363 set_first_insn (nextlast);
3364 return first;
3367 /* Skip over inter-block insns occurring after BB which are typically
3368 associated with BB (e.g., barriers). If there are any such insns,
3369 we return the last one. Otherwise, we return the end of BB. */
3371 static rtx_insn *
3372 skip_insns_after_block (basic_block bb)
3374 rtx_insn *insn, *last_insn, *next_head, *prev;
3376 next_head = NULL;
3377 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3378 next_head = BB_HEAD (bb->next_bb);
3380 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3382 if (insn == next_head)
3383 break;
3385 switch (GET_CODE (insn))
3387 case BARRIER:
3388 last_insn = insn;
3389 continue;
3391 case NOTE:
3392 switch (NOTE_KIND (insn))
3394 case NOTE_INSN_BLOCK_END:
3395 gcc_unreachable ();
3396 continue;
3397 default:
3398 continue;
3399 break;
3401 break;
3403 case CODE_LABEL:
3404 if (NEXT_INSN (insn)
3405 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3407 insn = NEXT_INSN (insn);
3408 last_insn = insn;
3409 continue;
3411 break;
3413 default:
3414 break;
3417 break;
3420 /* It is possible to hit contradictory sequence. For instance:
3422 jump_insn
3423 NOTE_INSN_BLOCK_BEG
3424 barrier
3426 Where barrier belongs to jump_insn, but the note does not. This can be
3427 created by removing the basic block originally following
3428 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3430 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3432 prev = PREV_INSN (insn);
3433 if (NOTE_P (insn))
3434 switch (NOTE_KIND (insn))
3436 case NOTE_INSN_BLOCK_END:
3437 gcc_unreachable ();
3438 break;
3439 case NOTE_INSN_DELETED:
3440 case NOTE_INSN_DELETED_LABEL:
3441 case NOTE_INSN_DELETED_DEBUG_LABEL:
3442 continue;
3443 default:
3444 reorder_insns (insn, insn, last_insn);
3448 return last_insn;
3451 /* Locate or create a label for a given basic block. */
3453 static rtx_insn *
3454 label_for_bb (basic_block bb)
3456 rtx_insn *label = BB_HEAD (bb);
3458 if (!LABEL_P (label))
3460 if (dump_file)
3461 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3463 label = block_label (bb);
3466 return label;
3469 /* Locate the effective beginning and end of the insn chain for each
3470 block, as defined by skip_insns_after_block above. */
3472 static void
3473 record_effective_endpoints (void)
3475 rtx_insn *next_insn;
3476 basic_block bb;
3477 rtx_insn *insn;
3479 for (insn = get_insns ();
3480 insn
3481 && NOTE_P (insn)
3482 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3483 insn = NEXT_INSN (insn))
3484 continue;
3485 /* No basic blocks at all? */
3486 gcc_assert (insn);
3488 if (PREV_INSN (insn))
3489 cfg_layout_function_header =
3490 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3491 else
3492 cfg_layout_function_header = NULL;
3494 next_insn = get_insns ();
3495 FOR_EACH_BB_FN (bb, cfun)
3497 rtx_insn *end;
3499 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3500 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3501 PREV_INSN (BB_HEAD (bb)));
3502 end = skip_insns_after_block (bb);
3503 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3504 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3505 next_insn = NEXT_INSN (BB_END (bb));
3508 cfg_layout_function_footer = next_insn;
3509 if (cfg_layout_function_footer)
3510 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3513 namespace {
3515 const pass_data pass_data_into_cfg_layout_mode =
3517 RTL_PASS, /* type */
3518 "into_cfglayout", /* name */
3519 OPTGROUP_NONE, /* optinfo_flags */
3520 TV_CFG, /* tv_id */
3521 0, /* properties_required */
3522 PROP_cfglayout, /* properties_provided */
3523 0, /* properties_destroyed */
3524 0, /* todo_flags_start */
3525 0, /* todo_flags_finish */
3528 class pass_into_cfg_layout_mode : public rtl_opt_pass
3530 public:
3531 pass_into_cfg_layout_mode (gcc::context *ctxt)
3532 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3535 /* opt_pass methods: */
3536 virtual unsigned int execute (function *)
3538 cfg_layout_initialize (0);
3539 return 0;
3542 }; // class pass_into_cfg_layout_mode
3544 } // anon namespace
3546 rtl_opt_pass *
3547 make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3549 return new pass_into_cfg_layout_mode (ctxt);
3552 namespace {
3554 const pass_data pass_data_outof_cfg_layout_mode =
3556 RTL_PASS, /* type */
3557 "outof_cfglayout", /* name */
3558 OPTGROUP_NONE, /* optinfo_flags */
3559 TV_CFG, /* tv_id */
3560 0, /* properties_required */
3561 0, /* properties_provided */
3562 PROP_cfglayout, /* properties_destroyed */
3563 0, /* todo_flags_start */
3564 0, /* todo_flags_finish */
3567 class pass_outof_cfg_layout_mode : public rtl_opt_pass
3569 public:
3570 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3571 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3574 /* opt_pass methods: */
3575 virtual unsigned int execute (function *);
3577 }; // class pass_outof_cfg_layout_mode
3579 unsigned int
3580 pass_outof_cfg_layout_mode::execute (function *fun)
3582 basic_block bb;
3584 FOR_EACH_BB_FN (bb, fun)
3585 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3586 bb->aux = bb->next_bb;
3588 cfg_layout_finalize ();
3590 return 0;
3593 } // anon namespace
3595 rtl_opt_pass *
3596 make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3598 return new pass_outof_cfg_layout_mode (ctxt);
3602 /* Link the basic blocks in the correct order, compacting the basic
3603 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3604 function also clears the basic block header and footer fields.
3606 This function is usually called after a pass (e.g. tracer) finishes
3607 some transformations while in cfglayout mode. The required sequence
3608 of the basic blocks is in a linked list along the bb->aux field.
3609 This functions re-links the basic block prev_bb and next_bb pointers
3610 accordingly, and it compacts and renumbers the blocks.
3612 FIXME: This currently works only for RTL, but the only RTL-specific
3613 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3614 to GIMPLE a long time ago, but it doesn't relink the basic block
3615 chain. It could do that (to give better initial RTL) if this function
3616 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3618 void
3619 relink_block_chain (bool stay_in_cfglayout_mode)
3621 basic_block bb, prev_bb;
3622 int index;
3624 /* Maybe dump the re-ordered sequence. */
3625 if (dump_file)
3627 fprintf (dump_file, "Reordered sequence:\n");
3628 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3629 NUM_FIXED_BLOCKS;
3631 bb = (basic_block) bb->aux, index++)
3633 fprintf (dump_file, " %i ", index);
3634 if (get_bb_original (bb))
3635 fprintf (dump_file, "duplicate of %i ",
3636 get_bb_original (bb)->index);
3637 else if (forwarder_block_p (bb)
3638 && !LABEL_P (BB_HEAD (bb)))
3639 fprintf (dump_file, "compensation ");
3640 else
3641 fprintf (dump_file, "bb %i ", bb->index);
3642 fprintf (dump_file, " [%i]\n", bb->frequency);
3646 /* Now reorder the blocks. */
3647 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3648 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3649 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3651 bb->prev_bb = prev_bb;
3652 prev_bb->next_bb = bb;
3654 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3655 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3657 /* Then, clean up the aux fields. */
3658 FOR_ALL_BB_FN (bb, cfun)
3660 bb->aux = NULL;
3661 if (!stay_in_cfglayout_mode)
3662 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3665 /* Maybe reset the original copy tables, they are not valid anymore
3666 when we renumber the basic blocks in compact_blocks. If we are
3667 are going out of cfglayout mode, don't re-allocate the tables. */
3668 free_original_copy_tables ();
3669 if (stay_in_cfglayout_mode)
3670 initialize_original_copy_tables ();
3672 /* Finally, put basic_block_info in the new order. */
3673 compact_blocks ();
3677 /* Given a reorder chain, rearrange the code to match. */
3679 static void
3680 fixup_reorder_chain (void)
3682 basic_block bb;
3683 rtx_insn *insn = NULL;
3685 if (cfg_layout_function_header)
3687 set_first_insn (cfg_layout_function_header);
3688 insn = cfg_layout_function_header;
3689 while (NEXT_INSN (insn))
3690 insn = NEXT_INSN (insn);
3693 /* First do the bulk reordering -- rechain the blocks without regard to
3694 the needed changes to jumps and labels. */
3696 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3697 bb->aux)
3699 if (BB_HEADER (bb))
3701 if (insn)
3702 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3703 else
3704 set_first_insn (BB_HEADER (bb));
3705 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3706 insn = BB_HEADER (bb);
3707 while (NEXT_INSN (insn))
3708 insn = NEXT_INSN (insn);
3710 if (insn)
3711 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3712 else
3713 set_first_insn (BB_HEAD (bb));
3714 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3715 insn = BB_END (bb);
3716 if (BB_FOOTER (bb))
3718 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3719 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3720 while (NEXT_INSN (insn))
3721 insn = NEXT_INSN (insn);
3725 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3726 if (cfg_layout_function_footer)
3727 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3729 while (NEXT_INSN (insn))
3730 insn = NEXT_INSN (insn);
3732 set_last_insn (insn);
3733 #ifdef ENABLE_CHECKING
3734 verify_insn_chain ();
3735 #endif
3737 /* Now add jumps and labels as needed to match the blocks new
3738 outgoing edges. */
3740 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3741 bb->aux)
3743 edge e_fall, e_taken, e;
3744 rtx_insn *bb_end_insn;
3745 rtx ret_label = NULL_RTX;
3746 basic_block nb;
3747 edge_iterator ei;
3749 if (EDGE_COUNT (bb->succs) == 0)
3750 continue;
3752 /* Find the old fallthru edge, and another non-EH edge for
3753 a taken jump. */
3754 e_taken = e_fall = NULL;
3756 FOR_EACH_EDGE (e, ei, bb->succs)
3757 if (e->flags & EDGE_FALLTHRU)
3758 e_fall = e;
3759 else if (! (e->flags & EDGE_EH))
3760 e_taken = e;
3762 bb_end_insn = BB_END (bb);
3763 if (rtx_jump_insn *bb_end_jump = dyn_cast <rtx_jump_insn *> (bb_end_insn))
3765 ret_label = JUMP_LABEL (bb_end_jump);
3766 if (any_condjump_p (bb_end_jump))
3768 /* This might happen if the conditional jump has side
3769 effects and could therefore not be optimized away.
3770 Make the basic block to end with a barrier in order
3771 to prevent rtl_verify_flow_info from complaining. */
3772 if (!e_fall)
3774 gcc_assert (!onlyjump_p (bb_end_jump)
3775 || returnjump_p (bb_end_jump)
3776 || (e_taken->flags & EDGE_CROSSING));
3777 emit_barrier_after (bb_end_jump);
3778 continue;
3781 /* If the old fallthru is still next, nothing to do. */
3782 if (bb->aux == e_fall->dest
3783 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3784 continue;
3786 /* The degenerated case of conditional jump jumping to the next
3787 instruction can happen for jumps with side effects. We need
3788 to construct a forwarder block and this will be done just
3789 fine by force_nonfallthru below. */
3790 if (!e_taken)
3793 /* There is another special case: if *neither* block is next,
3794 such as happens at the very end of a function, then we'll
3795 need to add a new unconditional jump. Choose the taken
3796 edge based on known or assumed probability. */
3797 else if (bb->aux != e_taken->dest)
3799 rtx note = find_reg_note (bb_end_jump, REG_BR_PROB, 0);
3801 if (note
3802 && XINT (note, 0) < REG_BR_PROB_BASE / 2
3803 && invert_jump (bb_end_jump,
3804 (e_fall->dest
3805 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3806 ? NULL_RTX
3807 : label_for_bb (e_fall->dest)), 0))
3809 e_fall->flags &= ~EDGE_FALLTHRU;
3810 gcc_checking_assert (could_fall_through
3811 (e_taken->src, e_taken->dest));
3812 e_taken->flags |= EDGE_FALLTHRU;
3813 update_br_prob_note (bb);
3814 e = e_fall, e_fall = e_taken, e_taken = e;
3818 /* If the "jumping" edge is a crossing edge, and the fall
3819 through edge is non-crossing, leave things as they are. */
3820 else if ((e_taken->flags & EDGE_CROSSING)
3821 && !(e_fall->flags & EDGE_CROSSING))
3822 continue;
3824 /* Otherwise we can try to invert the jump. This will
3825 basically never fail, however, keep up the pretense. */
3826 else if (invert_jump (bb_end_jump,
3827 (e_fall->dest
3828 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3829 ? NULL_RTX
3830 : label_for_bb (e_fall->dest)), 0))
3832 e_fall->flags &= ~EDGE_FALLTHRU;
3833 gcc_checking_assert (could_fall_through
3834 (e_taken->src, e_taken->dest));
3835 e_taken->flags |= EDGE_FALLTHRU;
3836 update_br_prob_note (bb);
3837 if (LABEL_NUSES (ret_label) == 0
3838 && single_pred_p (e_taken->dest))
3839 delete_insn (ret_label);
3840 continue;
3843 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
3845 /* If the old fallthru is still next or if
3846 asm goto doesn't have a fallthru (e.g. when followed by
3847 __builtin_unreachable ()), nothing to do. */
3848 if (! e_fall
3849 || bb->aux == e_fall->dest
3850 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3851 continue;
3853 /* Otherwise we'll have to use the fallthru fixup below. */
3855 else
3857 /* Otherwise we have some return, switch or computed
3858 jump. In the 99% case, there should not have been a
3859 fallthru edge. */
3860 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
3861 continue;
3864 else
3866 /* No fallthru implies a noreturn function with EH edges, or
3867 something similarly bizarre. In any case, we don't need to
3868 do anything. */
3869 if (! e_fall)
3870 continue;
3872 /* If the fallthru block is still next, nothing to do. */
3873 if (bb->aux == e_fall->dest)
3874 continue;
3876 /* A fallthru to exit block. */
3877 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3878 continue;
3881 /* We got here if we need to add a new jump insn.
3882 Note force_nonfallthru can delete E_FALL and thus we have to
3883 save E_FALL->src prior to the call to force_nonfallthru. */
3884 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
3885 if (nb)
3887 nb->aux = bb->aux;
3888 bb->aux = nb;
3889 /* Don't process this new block. */
3890 bb = nb;
3894 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3896 /* Annoying special case - jump around dead jumptables left in the code. */
3897 FOR_EACH_BB_FN (bb, cfun)
3899 edge e = find_fallthru_edge (bb->succs);
3901 if (e && !can_fallthru (e->src, e->dest))
3902 force_nonfallthru (e);
3905 /* Ensure goto_locus from edges has some instructions with that locus
3906 in RTL. */
3907 if (!optimize)
3908 FOR_EACH_BB_FN (bb, cfun)
3910 edge e;
3911 edge_iterator ei;
3913 FOR_EACH_EDGE (e, ei, bb->succs)
3914 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
3915 && !(e->flags & EDGE_ABNORMAL))
3917 edge e2;
3918 edge_iterator ei2;
3919 basic_block dest, nb;
3920 rtx_insn *end;
3922 insn = BB_END (e->src);
3923 end = PREV_INSN (BB_HEAD (e->src));
3924 while (insn != end
3925 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
3926 insn = PREV_INSN (insn);
3927 if (insn != end
3928 && INSN_LOCATION (insn) == e->goto_locus)
3929 continue;
3930 if (simplejump_p (BB_END (e->src))
3931 && !INSN_HAS_LOCATION (BB_END (e->src)))
3933 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
3934 continue;
3936 dest = e->dest;
3937 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3939 /* Non-fallthru edges to the exit block cannot be split. */
3940 if (!(e->flags & EDGE_FALLTHRU))
3941 continue;
3943 else
3945 insn = BB_HEAD (dest);
3946 end = NEXT_INSN (BB_END (dest));
3947 while (insn != end && !NONDEBUG_INSN_P (insn))
3948 insn = NEXT_INSN (insn);
3949 if (insn != end && INSN_HAS_LOCATION (insn)
3950 && INSN_LOCATION (insn) == e->goto_locus)
3951 continue;
3953 nb = split_edge (e);
3954 if (!INSN_P (BB_END (nb)))
3955 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
3956 nb);
3957 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
3959 /* If there are other incoming edges to the destination block
3960 with the same goto locus, redirect them to the new block as
3961 well, this can prevent other such blocks from being created
3962 in subsequent iterations of the loop. */
3963 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
3964 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
3965 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
3966 && e->goto_locus == e2->goto_locus)
3967 redirect_edge_and_branch (e2, nb);
3968 else
3969 ei_next (&ei2);
3974 /* Perform sanity checks on the insn chain.
3975 1. Check that next/prev pointers are consistent in both the forward and
3976 reverse direction.
3977 2. Count insns in chain, going both directions, and check if equal.
3978 3. Check that get_last_insn () returns the actual end of chain. */
3980 DEBUG_FUNCTION void
3981 verify_insn_chain (void)
3983 rtx_insn *x, *prevx, *nextx;
3984 int insn_cnt1, insn_cnt2;
3986 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
3987 x != 0;
3988 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
3989 gcc_assert (PREV_INSN (x) == prevx);
3991 gcc_assert (prevx == get_last_insn ());
3993 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
3994 x != 0;
3995 nextx = x, insn_cnt2++, x = PREV_INSN (x))
3996 gcc_assert (NEXT_INSN (x) == nextx);
3998 gcc_assert (insn_cnt1 == insn_cnt2);
4001 /* If we have assembler epilogues, the block falling through to exit must
4002 be the last one in the reordered chain when we reach final. Ensure
4003 that this condition is met. */
4004 static void
4005 fixup_fallthru_exit_predecessor (void)
4007 edge e;
4008 basic_block bb = NULL;
4010 /* This transformation is not valid before reload, because we might
4011 separate a call from the instruction that copies the return
4012 value. */
4013 gcc_assert (reload_completed);
4015 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4016 if (e)
4017 bb = e->src;
4019 if (bb && bb->aux)
4021 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
4023 /* If the very first block is the one with the fall-through exit
4024 edge, we have to split that block. */
4025 if (c == bb)
4027 bb = split_block_after_labels (bb)->dest;
4028 bb->aux = c->aux;
4029 c->aux = bb;
4030 BB_FOOTER (bb) = BB_FOOTER (c);
4031 BB_FOOTER (c) = NULL;
4034 while (c->aux != bb)
4035 c = (basic_block) c->aux;
4037 c->aux = bb->aux;
4038 while (c->aux)
4039 c = (basic_block) c->aux;
4041 c->aux = bb;
4042 bb->aux = NULL;
4046 /* In case there are more than one fallthru predecessors of exit, force that
4047 there is only one. */
4049 static void
4050 force_one_exit_fallthru (void)
4052 edge e, predecessor = NULL;
4053 bool more = false;
4054 edge_iterator ei;
4055 basic_block forwarder, bb;
4057 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4058 if (e->flags & EDGE_FALLTHRU)
4060 if (predecessor == NULL)
4061 predecessor = e;
4062 else
4064 more = true;
4065 break;
4069 if (!more)
4070 return;
4072 /* Exit has several fallthru predecessors. Create a forwarder block for
4073 them. */
4074 forwarder = split_edge (predecessor);
4075 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4076 (e = ei_safe_edge (ei)); )
4078 if (e->src == forwarder
4079 || !(e->flags & EDGE_FALLTHRU))
4080 ei_next (&ei);
4081 else
4082 redirect_edge_and_branch_force (e, forwarder);
4085 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4086 exit block. */
4087 FOR_EACH_BB_FN (bb, cfun)
4089 if (bb->aux == NULL && bb != forwarder)
4091 bb->aux = forwarder;
4092 break;
4097 /* Return true in case it is possible to duplicate the basic block BB. */
4099 static bool
4100 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4102 /* Do not attempt to duplicate tablejumps, as we need to unshare
4103 the dispatch table. This is difficult to do, as the instructions
4104 computing jump destination may be hoisted outside the basic block. */
4105 if (tablejump_p (BB_END (bb), NULL, NULL))
4106 return false;
4108 /* Do not duplicate blocks containing insns that can't be copied. */
4109 if (targetm.cannot_copy_insn_p)
4111 rtx_insn *insn = BB_HEAD (bb);
4112 while (1)
4114 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4115 return false;
4116 if (insn == BB_END (bb))
4117 break;
4118 insn = NEXT_INSN (insn);
4122 return true;
4125 rtx_insn *
4126 duplicate_insn_chain (rtx_insn *from, rtx_insn *to)
4128 rtx_insn *insn, *next, *copy;
4129 rtx_note *last;
4131 /* Avoid updating of boundaries of previous basic block. The
4132 note will get removed from insn stream in fixup. */
4133 last = emit_note (NOTE_INSN_DELETED);
4135 /* Create copy at the end of INSN chain. The chain will
4136 be reordered later. */
4137 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4139 switch (GET_CODE (insn))
4141 case DEBUG_INSN:
4142 /* Don't duplicate label debug insns. */
4143 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4144 break;
4145 /* FALLTHRU */
4146 case INSN:
4147 case CALL_INSN:
4148 case JUMP_INSN:
4149 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4150 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4151 && ANY_RETURN_P (JUMP_LABEL (insn)))
4152 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4153 maybe_copy_prologue_epilogue_insn (insn, copy);
4154 break;
4156 case JUMP_TABLE_DATA:
4157 /* Avoid copying of dispatch tables. We never duplicate
4158 tablejumps, so this can hit only in case the table got
4159 moved far from original jump.
4160 Avoid copying following barrier as well if any
4161 (and debug insns in between). */
4162 for (next = NEXT_INSN (insn);
4163 next != NEXT_INSN (to);
4164 next = NEXT_INSN (next))
4165 if (!DEBUG_INSN_P (next))
4166 break;
4167 if (next != NEXT_INSN (to) && BARRIER_P (next))
4168 insn = next;
4169 break;
4171 case CODE_LABEL:
4172 break;
4174 case BARRIER:
4175 emit_barrier ();
4176 break;
4178 case NOTE:
4179 switch (NOTE_KIND (insn))
4181 /* In case prologue is empty and function contain label
4182 in first BB, we may want to copy the block. */
4183 case NOTE_INSN_PROLOGUE_END:
4185 case NOTE_INSN_DELETED:
4186 case NOTE_INSN_DELETED_LABEL:
4187 case NOTE_INSN_DELETED_DEBUG_LABEL:
4188 /* No problem to strip these. */
4189 case NOTE_INSN_FUNCTION_BEG:
4190 /* There is always just single entry to function. */
4191 case NOTE_INSN_BASIC_BLOCK:
4192 /* We should only switch text sections once. */
4193 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4194 break;
4196 case NOTE_INSN_EPILOGUE_BEG:
4197 case NOTE_INSN_UPDATE_SJLJ_CONTEXT:
4198 emit_note_copy (as_a <rtx_note *> (insn));
4199 break;
4201 default:
4202 /* All other notes should have already been eliminated. */
4203 gcc_unreachable ();
4205 break;
4206 default:
4207 gcc_unreachable ();
4210 insn = NEXT_INSN (last);
4211 delete_insn (last);
4212 return insn;
4215 /* Create a duplicate of the basic block BB. */
4217 static basic_block
4218 cfg_layout_duplicate_bb (basic_block bb)
4220 rtx_insn *insn;
4221 basic_block new_bb;
4223 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
4224 new_bb = create_basic_block (insn,
4225 insn ? get_last_insn () : NULL,
4226 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4228 BB_COPY_PARTITION (new_bb, bb);
4229 if (BB_HEADER (bb))
4231 insn = BB_HEADER (bb);
4232 while (NEXT_INSN (insn))
4233 insn = NEXT_INSN (insn);
4234 insn = duplicate_insn_chain (BB_HEADER (bb), insn);
4235 if (insn)
4236 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4239 if (BB_FOOTER (bb))
4241 insn = BB_FOOTER (bb);
4242 while (NEXT_INSN (insn))
4243 insn = NEXT_INSN (insn);
4244 insn = duplicate_insn_chain (BB_FOOTER (bb), insn);
4245 if (insn)
4246 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4249 return new_bb;
4253 /* Main entry point to this module - initialize the datastructures for
4254 CFG layout changes. It keeps LOOPS up-to-date if not null.
4256 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4258 void
4259 cfg_layout_initialize (unsigned int flags)
4261 rtx_insn_list *x;
4262 basic_block bb;
4264 /* Once bb partitioning is complete, cfg layout mode should not be
4265 re-entered. Entering cfg layout mode may require fixups. As an
4266 example, if edge forwarding performed when optimizing the cfg
4267 layout required moving a block from the hot to the cold
4268 section. This would create an illegal partitioning unless some
4269 manual fixup was performed. */
4270 gcc_assert (!(crtl->bb_reorder_complete
4271 && flag_reorder_blocks_and_partition));
4273 initialize_original_copy_tables ();
4275 cfg_layout_rtl_register_cfg_hooks ();
4277 record_effective_endpoints ();
4279 /* Make sure that the targets of non local gotos are marked. */
4280 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4282 bb = BLOCK_FOR_INSN (x->insn ());
4283 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4286 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4289 /* Splits superblocks. */
4290 void
4291 break_superblocks (void)
4293 sbitmap superblocks;
4294 bool need = false;
4295 basic_block bb;
4297 superblocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
4298 bitmap_clear (superblocks);
4300 FOR_EACH_BB_FN (bb, cfun)
4301 if (bb->flags & BB_SUPERBLOCK)
4303 bb->flags &= ~BB_SUPERBLOCK;
4304 bitmap_set_bit (superblocks, bb->index);
4305 need = true;
4308 if (need)
4310 rebuild_jump_labels (get_insns ());
4311 find_many_sub_basic_blocks (superblocks);
4314 free (superblocks);
4317 /* Finalize the changes: reorder insn list according to the sequence specified
4318 by aux pointers, enter compensation code, rebuild scope forest. */
4320 void
4321 cfg_layout_finalize (void)
4323 #ifdef ENABLE_CHECKING
4324 verify_flow_info ();
4325 #endif
4326 force_one_exit_fallthru ();
4327 rtl_register_cfg_hooks ();
4328 if (reload_completed && !targetm.have_epilogue ())
4329 fixup_fallthru_exit_predecessor ();
4330 fixup_reorder_chain ();
4332 rebuild_jump_labels (get_insns ());
4333 delete_dead_jumptables ();
4335 #ifdef ENABLE_CHECKING
4336 verify_insn_chain ();
4337 verify_flow_info ();
4338 #endif
4342 /* Same as split_block but update cfg_layout structures. */
4344 static basic_block
4345 cfg_layout_split_block (basic_block bb, void *insnp)
4347 rtx insn = (rtx) insnp;
4348 basic_block new_bb = rtl_split_block (bb, insn);
4350 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4351 BB_FOOTER (bb) = NULL;
4353 return new_bb;
4356 /* Redirect Edge to DEST. */
4357 static edge
4358 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4360 basic_block src = e->src;
4361 edge ret;
4363 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4364 return NULL;
4366 if (e->dest == dest)
4367 return e;
4369 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4370 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4372 df_set_bb_dirty (src);
4373 return ret;
4376 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4377 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4379 if (dump_file)
4380 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4381 e->src->index, dest->index);
4383 df_set_bb_dirty (e->src);
4384 redirect_edge_succ (e, dest);
4385 return e;
4388 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4389 in the case the basic block appears to be in sequence. Avoid this
4390 transformation. */
4392 if (e->flags & EDGE_FALLTHRU)
4394 /* Redirect any branch edges unified with the fallthru one. */
4395 if (JUMP_P (BB_END (src))
4396 && label_is_jump_target_p (BB_HEAD (e->dest),
4397 BB_END (src)))
4399 edge redirected;
4401 if (dump_file)
4402 fprintf (dump_file, "Fallthru edge unified with branch "
4403 "%i->%i redirected to %i\n",
4404 e->src->index, e->dest->index, dest->index);
4405 e->flags &= ~EDGE_FALLTHRU;
4406 redirected = redirect_branch_edge (e, dest);
4407 gcc_assert (redirected);
4408 redirected->flags |= EDGE_FALLTHRU;
4409 df_set_bb_dirty (redirected->src);
4410 return redirected;
4412 /* In case we are redirecting fallthru edge to the branch edge
4413 of conditional jump, remove it. */
4414 if (EDGE_COUNT (src->succs) == 2)
4416 /* Find the edge that is different from E. */
4417 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4419 if (s->dest == dest
4420 && any_condjump_p (BB_END (src))
4421 && onlyjump_p (BB_END (src)))
4422 delete_insn (BB_END (src));
4424 if (dump_file)
4425 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4426 e->src->index, e->dest->index, dest->index);
4427 ret = redirect_edge_succ_nodup (e, dest);
4429 else
4430 ret = redirect_branch_edge (e, dest);
4432 /* We don't want simplejumps in the insn stream during cfglayout. */
4433 gcc_assert (!simplejump_p (BB_END (src)));
4435 df_set_bb_dirty (src);
4436 return ret;
4439 /* Simple wrapper as we always can redirect fallthru edges. */
4440 static basic_block
4441 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4443 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4445 gcc_assert (redirected);
4446 return NULL;
4449 /* Same as delete_basic_block but update cfg_layout structures. */
4451 static void
4452 cfg_layout_delete_block (basic_block bb)
4454 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4455 rtx_insn **to;
4457 if (BB_HEADER (bb))
4459 next = BB_HEAD (bb);
4460 if (prev)
4461 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4462 else
4463 set_first_insn (BB_HEADER (bb));
4464 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4465 insn = BB_HEADER (bb);
4466 while (NEXT_INSN (insn))
4467 insn = NEXT_INSN (insn);
4468 SET_NEXT_INSN (insn) = next;
4469 SET_PREV_INSN (next) = insn;
4471 next = NEXT_INSN (BB_END (bb));
4472 if (BB_FOOTER (bb))
4474 insn = BB_FOOTER (bb);
4475 while (insn)
4477 if (BARRIER_P (insn))
4479 if (PREV_INSN (insn))
4480 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4481 else
4482 BB_FOOTER (bb) = NEXT_INSN (insn);
4483 if (NEXT_INSN (insn))
4484 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4486 if (LABEL_P (insn))
4487 break;
4488 insn = NEXT_INSN (insn);
4490 if (BB_FOOTER (bb))
4492 insn = BB_END (bb);
4493 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4494 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4495 while (NEXT_INSN (insn))
4496 insn = NEXT_INSN (insn);
4497 SET_NEXT_INSN (insn) = next;
4498 if (next)
4499 SET_PREV_INSN (next) = insn;
4500 else
4501 set_last_insn (insn);
4504 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4505 to = &BB_HEADER (bb->next_bb);
4506 else
4507 to = &cfg_layout_function_footer;
4509 rtl_delete_block (bb);
4511 if (prev)
4512 prev = NEXT_INSN (prev);
4513 else
4514 prev = get_insns ();
4515 if (next)
4516 next = PREV_INSN (next);
4517 else
4518 next = get_last_insn ();
4520 if (next && NEXT_INSN (next) != prev)
4522 remaints = unlink_insn_chain (prev, next);
4523 insn = remaints;
4524 while (NEXT_INSN (insn))
4525 insn = NEXT_INSN (insn);
4526 SET_NEXT_INSN (insn) = *to;
4527 if (*to)
4528 SET_PREV_INSN (*to) = insn;
4529 *to = remaints;
4533 /* Return true when blocks A and B can be safely merged. */
4535 static bool
4536 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4538 /* If we are partitioning hot/cold basic blocks, we don't want to
4539 mess up unconditional or indirect jumps that cross between hot
4540 and cold sections.
4542 Basic block partitioning may result in some jumps that appear to
4543 be optimizable (or blocks that appear to be mergeable), but which really
4544 must be left untouched (they are required to make it safely across
4545 partition boundaries). See the comments at the top of
4546 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4548 if (BB_PARTITION (a) != BB_PARTITION (b))
4549 return false;
4551 /* Protect the loop latches. */
4552 if (current_loops && b->loop_father->latch == b)
4553 return false;
4555 /* If we would end up moving B's instructions, make sure it doesn't fall
4556 through into the exit block, since we cannot recover from a fallthrough
4557 edge into the exit block occurring in the middle of a function. */
4558 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4560 edge e = find_fallthru_edge (b->succs);
4561 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4562 return false;
4565 /* There must be exactly one edge in between the blocks. */
4566 return (single_succ_p (a)
4567 && single_succ (a) == b
4568 && single_pred_p (b) == 1
4569 && a != b
4570 /* Must be simple edge. */
4571 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4572 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4573 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4574 /* If the jump insn has side effects, we can't kill the edge.
4575 When not optimizing, try_redirect_by_replacing_jump will
4576 not allow us to redirect an edge by replacing a table jump. */
4577 && (!JUMP_P (BB_END (a))
4578 || ((!optimize || reload_completed)
4579 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4582 /* Merge block A and B. The blocks must be mergeable. */
4584 static void
4585 cfg_layout_merge_blocks (basic_block a, basic_block b)
4587 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
4588 rtx_insn *insn;
4590 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4592 if (dump_file)
4593 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4594 a->index);
4596 /* If there was a CODE_LABEL beginning B, delete it. */
4597 if (LABEL_P (BB_HEAD (b)))
4599 delete_insn (BB_HEAD (b));
4602 /* We should have fallthru edge in a, or we can do dummy redirection to get
4603 it cleaned up. */
4604 if (JUMP_P (BB_END (a)))
4605 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4606 gcc_assert (!JUMP_P (BB_END (a)));
4608 /* When not optimizing and the edge is the only place in RTL which holds
4609 some unique locus, emit a nop with that locus in between. */
4610 if (!optimize)
4611 emit_nop_for_unique_locus_between (a, b);
4613 /* Move things from b->footer after a->footer. */
4614 if (BB_FOOTER (b))
4616 if (!BB_FOOTER (a))
4617 BB_FOOTER (a) = BB_FOOTER (b);
4618 else
4620 rtx_insn *last = BB_FOOTER (a);
4622 while (NEXT_INSN (last))
4623 last = NEXT_INSN (last);
4624 SET_NEXT_INSN (last) = BB_FOOTER (b);
4625 SET_PREV_INSN (BB_FOOTER (b)) = last;
4627 BB_FOOTER (b) = NULL;
4630 /* Move things from b->header before a->footer.
4631 Note that this may include dead tablejump data, but we don't clean
4632 those up until we go out of cfglayout mode. */
4633 if (BB_HEADER (b))
4635 if (! BB_FOOTER (a))
4636 BB_FOOTER (a) = BB_HEADER (b);
4637 else
4639 rtx_insn *last = BB_HEADER (b);
4641 while (NEXT_INSN (last))
4642 last = NEXT_INSN (last);
4643 SET_NEXT_INSN (last) = BB_FOOTER (a);
4644 SET_PREV_INSN (BB_FOOTER (a)) = last;
4645 BB_FOOTER (a) = BB_HEADER (b);
4647 BB_HEADER (b) = NULL;
4650 /* In the case basic blocks are not adjacent, move them around. */
4651 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4653 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4655 emit_insn_after_noloc (insn, BB_END (a), a);
4657 /* Otherwise just re-associate the instructions. */
4658 else
4660 insn = BB_HEAD (b);
4661 BB_END (a) = BB_END (b);
4664 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4665 We need to explicitly call. */
4666 update_bb_for_insn_chain (insn, BB_END (b), a);
4668 /* Skip possible DELETED_LABEL insn. */
4669 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4670 insn = NEXT_INSN (insn);
4671 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4672 BB_HEAD (b) = BB_END (b) = NULL;
4673 delete_insn (insn);
4675 df_bb_delete (b->index);
4677 /* If B was a forwarder block, propagate the locus on the edge. */
4678 if (forwarder_p
4679 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
4680 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4682 if (dump_file)
4683 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4686 /* Split edge E. */
4688 static basic_block
4689 cfg_layout_split_edge (edge e)
4691 basic_block new_bb =
4692 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4693 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4694 NULL_RTX, e->src);
4696 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4697 BB_COPY_PARTITION (new_bb, e->src);
4698 else
4699 BB_COPY_PARTITION (new_bb, e->dest);
4700 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4701 redirect_edge_and_branch_force (e, new_bb);
4703 return new_bb;
4706 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4708 static void
4709 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4713 /* Return true if BB contains only labels or non-executable
4714 instructions. */
4716 static bool
4717 rtl_block_empty_p (basic_block bb)
4719 rtx_insn *insn;
4721 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4722 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4723 return true;
4725 FOR_BB_INSNS (bb, insn)
4726 if (NONDEBUG_INSN_P (insn) && !any_uncondjump_p (insn))
4727 return false;
4729 return true;
4732 /* Split a basic block if it ends with a conditional branch and if
4733 the other part of the block is not empty. */
4735 static basic_block
4736 rtl_split_block_before_cond_jump (basic_block bb)
4738 rtx_insn *insn;
4739 rtx_insn *split_point = NULL;
4740 rtx_insn *last = NULL;
4741 bool found_code = false;
4743 FOR_BB_INSNS (bb, insn)
4745 if (any_condjump_p (insn))
4746 split_point = last;
4747 else if (NONDEBUG_INSN_P (insn))
4748 found_code = true;
4749 last = insn;
4752 /* Did not find everything. */
4753 if (found_code && split_point)
4754 return split_block (bb, split_point)->dest;
4755 else
4756 return NULL;
4759 /* Return 1 if BB ends with a call, possibly followed by some
4760 instructions that must stay with the call, 0 otherwise. */
4762 static bool
4763 rtl_block_ends_with_call_p (basic_block bb)
4765 rtx_insn *insn = BB_END (bb);
4767 while (!CALL_P (insn)
4768 && insn != BB_HEAD (bb)
4769 && (keep_with_call_p (insn)
4770 || NOTE_P (insn)
4771 || DEBUG_INSN_P (insn)))
4772 insn = PREV_INSN (insn);
4773 return (CALL_P (insn));
4776 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4778 static bool
4779 rtl_block_ends_with_condjump_p (const_basic_block bb)
4781 return any_condjump_p (BB_END (bb));
4784 /* Return true if we need to add fake edge to exit.
4785 Helper function for rtl_flow_call_edges_add. */
4787 static bool
4788 need_fake_edge_p (const rtx_insn *insn)
4790 if (!INSN_P (insn))
4791 return false;
4793 if ((CALL_P (insn)
4794 && !SIBLING_CALL_P (insn)
4795 && !find_reg_note (insn, REG_NORETURN, NULL)
4796 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
4797 return true;
4799 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
4800 && MEM_VOLATILE_P (PATTERN (insn)))
4801 || (GET_CODE (PATTERN (insn)) == PARALLEL
4802 && asm_noperands (insn) != -1
4803 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
4804 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
4807 /* Add fake edges to the function exit for any non constant and non noreturn
4808 calls, volatile inline assembly in the bitmap of blocks specified by
4809 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4810 that were split.
4812 The goal is to expose cases in which entering a basic block does not imply
4813 that all subsequent instructions must be executed. */
4815 static int
4816 rtl_flow_call_edges_add (sbitmap blocks)
4818 int i;
4819 int blocks_split = 0;
4820 int last_bb = last_basic_block_for_fn (cfun);
4821 bool check_last_block = false;
4823 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
4824 return 0;
4826 if (! blocks)
4827 check_last_block = true;
4828 else
4829 check_last_block = bitmap_bit_p (blocks,
4830 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
4832 /* In the last basic block, before epilogue generation, there will be
4833 a fallthru edge to EXIT. Special care is required if the last insn
4834 of the last basic block is a call because make_edge folds duplicate
4835 edges, which would result in the fallthru edge also being marked
4836 fake, which would result in the fallthru edge being removed by
4837 remove_fake_edges, which would result in an invalid CFG.
4839 Moreover, we can't elide the outgoing fake edge, since the block
4840 profiler needs to take this into account in order to solve the minimal
4841 spanning tree in the case that the call doesn't return.
4843 Handle this by adding a dummy instruction in a new last basic block. */
4844 if (check_last_block)
4846 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
4847 rtx_insn *insn = BB_END (bb);
4849 /* Back up past insns that must be kept in the same block as a call. */
4850 while (insn != BB_HEAD (bb)
4851 && keep_with_call_p (insn))
4852 insn = PREV_INSN (insn);
4854 if (need_fake_edge_p (insn))
4856 edge e;
4858 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4859 if (e)
4861 insert_insn_on_edge (gen_use (const0_rtx), e);
4862 commit_edge_insertions ();
4867 /* Now add fake edges to the function exit for any non constant
4868 calls since there is no way that we can determine if they will
4869 return or not... */
4871 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
4873 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
4874 rtx_insn *insn;
4875 rtx_insn *prev_insn;
4877 if (!bb)
4878 continue;
4880 if (blocks && !bitmap_bit_p (blocks, i))
4881 continue;
4883 for (insn = BB_END (bb); ; insn = prev_insn)
4885 prev_insn = PREV_INSN (insn);
4886 if (need_fake_edge_p (insn))
4888 edge e;
4889 rtx_insn *split_at_insn = insn;
4891 /* Don't split the block between a call and an insn that should
4892 remain in the same block as the call. */
4893 if (CALL_P (insn))
4894 while (split_at_insn != BB_END (bb)
4895 && keep_with_call_p (NEXT_INSN (split_at_insn)))
4896 split_at_insn = NEXT_INSN (split_at_insn);
4898 /* The handling above of the final block before the epilogue
4899 should be enough to verify that there is no edge to the exit
4900 block in CFG already. Calling make_edge in such case would
4901 cause us to mark that edge as fake and remove it later. */
4903 #ifdef ENABLE_CHECKING
4904 if (split_at_insn == BB_END (bb))
4906 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4907 gcc_assert (e == NULL);
4909 #endif
4911 /* Note that the following may create a new basic block
4912 and renumber the existing basic blocks. */
4913 if (split_at_insn != BB_END (bb))
4915 e = split_block (bb, split_at_insn);
4916 if (e)
4917 blocks_split++;
4920 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
4923 if (insn == BB_HEAD (bb))
4924 break;
4928 if (blocks_split)
4929 verify_flow_info ();
4931 return blocks_split;
4934 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4935 the conditional branch target, SECOND_HEAD should be the fall-thru
4936 there is no need to handle this here the loop versioning code handles
4937 this. the reason for SECON_HEAD is that it is needed for condition
4938 in trees, and this should be of the same type since it is a hook. */
4939 static void
4940 rtl_lv_add_condition_to_bb (basic_block first_head ,
4941 basic_block second_head ATTRIBUTE_UNUSED,
4942 basic_block cond_bb, void *comp_rtx)
4944 rtx_code_label *label;
4945 rtx_insn *seq, *jump;
4946 rtx op0 = XEXP ((rtx)comp_rtx, 0);
4947 rtx op1 = XEXP ((rtx)comp_rtx, 1);
4948 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
4949 machine_mode mode;
4952 label = block_label (first_head);
4953 mode = GET_MODE (op0);
4954 if (mode == VOIDmode)
4955 mode = GET_MODE (op1);
4957 start_sequence ();
4958 op0 = force_operand (op0, NULL_RTX);
4959 op1 = force_operand (op1, NULL_RTX);
4960 do_compare_rtx_and_jump (op0, op1, comp, 0, mode, NULL_RTX, NULL, label, -1);
4961 jump = get_last_insn ();
4962 JUMP_LABEL (jump) = label;
4963 LABEL_NUSES (label)++;
4964 seq = get_insns ();
4965 end_sequence ();
4967 /* Add the new cond, in the new head. */
4968 emit_insn_after (seq, BB_END (cond_bb));
4972 /* Given a block B with unconditional branch at its end, get the
4973 store the return the branch edge and the fall-thru edge in
4974 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4975 static void
4976 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
4977 edge *fallthru_edge)
4979 edge e = EDGE_SUCC (b, 0);
4981 if (e->flags & EDGE_FALLTHRU)
4983 *fallthru_edge = e;
4984 *branch_edge = EDGE_SUCC (b, 1);
4986 else
4988 *branch_edge = e;
4989 *fallthru_edge = EDGE_SUCC (b, 1);
4993 void
4994 init_rtl_bb_info (basic_block bb)
4996 gcc_assert (!bb->il.x.rtl);
4997 bb->il.x.head_ = NULL;
4998 bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
5001 /* Returns true if it is possible to remove edge E by redirecting
5002 it to the destination of the other edge from E->src. */
5004 static bool
5005 rtl_can_remove_branch_p (const_edge e)
5007 const_basic_block src = e->src;
5008 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
5009 const rtx_insn *insn = BB_END (src);
5010 rtx set;
5012 /* The conditions are taken from try_redirect_by_replacing_jump. */
5013 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
5014 return false;
5016 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
5017 return false;
5019 if (BB_PARTITION (src) != BB_PARTITION (target))
5020 return false;
5022 if (!onlyjump_p (insn)
5023 || tablejump_p (insn, NULL, NULL))
5024 return false;
5026 set = single_set (insn);
5027 if (!set || side_effects_p (set))
5028 return false;
5030 return true;
5033 static basic_block
5034 rtl_duplicate_bb (basic_block bb)
5036 bb = cfg_layout_duplicate_bb (bb);
5037 bb->aux = NULL;
5038 return bb;
5041 /* Do book-keeping of basic block BB for the profile consistency checker.
5042 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5043 then do post-pass accounting. Store the counting in RECORD. */
5044 static void
5045 rtl_account_profile_record (basic_block bb, int after_pass,
5046 struct profile_record *record)
5048 rtx_insn *insn;
5049 FOR_BB_INSNS (bb, insn)
5050 if (INSN_P (insn))
5052 record->size[after_pass]
5053 += insn_rtx_cost (PATTERN (insn), false);
5054 if (profile_status_for_fn (cfun) == PROFILE_READ)
5055 record->time[after_pass]
5056 += insn_rtx_cost (PATTERN (insn), true) * bb->count;
5057 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
5058 record->time[after_pass]
5059 += insn_rtx_cost (PATTERN (insn), true) * bb->frequency;
5063 /* Implementation of CFG manipulation for linearized RTL. */
5064 struct cfg_hooks rtl_cfg_hooks = {
5065 "rtl",
5066 rtl_verify_flow_info,
5067 rtl_dump_bb,
5068 rtl_dump_bb_for_graph,
5069 rtl_create_basic_block,
5070 rtl_redirect_edge_and_branch,
5071 rtl_redirect_edge_and_branch_force,
5072 rtl_can_remove_branch_p,
5073 rtl_delete_block,
5074 rtl_split_block,
5075 rtl_move_block_after,
5076 rtl_can_merge_blocks, /* can_merge_blocks_p */
5077 rtl_merge_blocks,
5078 rtl_predict_edge,
5079 rtl_predicted_by_p,
5080 cfg_layout_can_duplicate_bb_p,
5081 rtl_duplicate_bb,
5082 rtl_split_edge,
5083 rtl_make_forwarder_block,
5084 rtl_tidy_fallthru_edge,
5085 rtl_force_nonfallthru,
5086 rtl_block_ends_with_call_p,
5087 rtl_block_ends_with_condjump_p,
5088 rtl_flow_call_edges_add,
5089 NULL, /* execute_on_growing_pred */
5090 NULL, /* execute_on_shrinking_pred */
5091 NULL, /* duplicate loop for trees */
5092 NULL, /* lv_add_condition_to_bb */
5093 NULL, /* lv_adjust_loop_header_phi*/
5094 NULL, /* extract_cond_bb_edges */
5095 NULL, /* flush_pending_stmts */
5096 rtl_block_empty_p, /* block_empty_p */
5097 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5098 rtl_account_profile_record,
5101 /* Implementation of CFG manipulation for cfg layout RTL, where
5102 basic block connected via fallthru edges does not have to be adjacent.
5103 This representation will hopefully become the default one in future
5104 version of the compiler. */
5106 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5107 "cfglayout mode",
5108 rtl_verify_flow_info_1,
5109 rtl_dump_bb,
5110 rtl_dump_bb_for_graph,
5111 cfg_layout_create_basic_block,
5112 cfg_layout_redirect_edge_and_branch,
5113 cfg_layout_redirect_edge_and_branch_force,
5114 rtl_can_remove_branch_p,
5115 cfg_layout_delete_block,
5116 cfg_layout_split_block,
5117 rtl_move_block_after,
5118 cfg_layout_can_merge_blocks_p,
5119 cfg_layout_merge_blocks,
5120 rtl_predict_edge,
5121 rtl_predicted_by_p,
5122 cfg_layout_can_duplicate_bb_p,
5123 cfg_layout_duplicate_bb,
5124 cfg_layout_split_edge,
5125 rtl_make_forwarder_block,
5126 NULL, /* tidy_fallthru_edge */
5127 rtl_force_nonfallthru,
5128 rtl_block_ends_with_call_p,
5129 rtl_block_ends_with_condjump_p,
5130 rtl_flow_call_edges_add,
5131 NULL, /* execute_on_growing_pred */
5132 NULL, /* execute_on_shrinking_pred */
5133 duplicate_loop_to_header_edge, /* duplicate loop for trees */
5134 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5135 NULL, /* lv_adjust_loop_header_phi*/
5136 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5137 NULL, /* flush_pending_stmts */
5138 rtl_block_empty_p, /* block_empty_p */
5139 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5140 rtl_account_profile_record,
5143 #include "gt-cfgrtl.h"