gcc/
[official-gcc.git] / gcc / cfgrtl.c
blob9707c1f5f4dc45f261a859f29145231871525ddf
1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987-2014 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 "tree.h"
45 #include "hard-reg-set.h"
46 #include "basic-block.h"
47 #include "bb-reorder.h"
48 #include "regs.h"
49 #include "flags.h"
50 #include "function.h"
51 #include "except.h"
52 #include "rtl-error.h"
53 #include "tm_p.h"
54 #include "obstack.h"
55 #include "insn-attr.h"
56 #include "insn-config.h"
57 #include "expr.h"
58 #include "target.h"
59 #include "common/common-target.h"
60 #include "cfgloop.h"
61 #include "ggc.h"
62 #include "tree-pass.h"
63 #include "df.h"
65 /* Holds the interesting leading and trailing notes for the function.
66 Only applicable if the CFG is in cfglayout mode. */
67 static GTY(()) rtx_insn *cfg_layout_function_footer;
68 static GTY(()) rtx_insn *cfg_layout_function_header;
70 static rtx_insn *skip_insns_after_block (basic_block);
71 static void record_effective_endpoints (void);
72 static rtx label_for_bb (basic_block);
73 static void fixup_reorder_chain (void);
75 void verify_insn_chain (void);
76 static void fixup_fallthru_exit_predecessor (void);
77 static int can_delete_note_p (const rtx_note *);
78 static int can_delete_label_p (const rtx_code_label *);
79 static basic_block rtl_split_edge (edge);
80 static bool rtl_move_block_after (basic_block, basic_block);
81 static int rtl_verify_flow_info (void);
82 static basic_block cfg_layout_split_block (basic_block, void *);
83 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
84 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
85 static void cfg_layout_delete_block (basic_block);
86 static void rtl_delete_block (basic_block);
87 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
88 static edge rtl_redirect_edge_and_branch (edge, basic_block);
89 static basic_block rtl_split_block (basic_block, void *);
90 static void rtl_dump_bb (FILE *, basic_block, int, int);
91 static int rtl_verify_flow_info_1 (void);
92 static void rtl_make_forwarder_block (edge);
94 /* Return true if NOTE is not one of the ones that must be kept paired,
95 so that we may simply delete it. */
97 static int
98 can_delete_note_p (const rtx_note *note)
100 switch (NOTE_KIND (note))
102 case NOTE_INSN_DELETED:
103 case NOTE_INSN_BASIC_BLOCK:
104 case NOTE_INSN_EPILOGUE_BEG:
105 return true;
107 default:
108 return false;
112 /* True if a given label can be deleted. */
114 static int
115 can_delete_label_p (const rtx_code_label *label)
117 return (!LABEL_PRESERVE_P (label)
118 /* User declared labels must be preserved. */
119 && LABEL_NAME (label) == 0
120 && !in_expr_list_p (forced_labels, label));
123 /* Delete INSN by patching it out. */
125 void
126 delete_insn (rtx uncast_insn)
128 rtx_insn *insn = as_a <rtx_insn *> (uncast_insn);
129 rtx note;
130 bool really_delete = true;
132 if (LABEL_P (insn))
134 /* Some labels can't be directly removed from the INSN chain, as they
135 might be references via variables, constant pool etc.
136 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
137 if (! can_delete_label_p (as_a <rtx_code_label *> (insn)))
139 const char *name = LABEL_NAME (insn);
140 basic_block bb = BLOCK_FOR_INSN (insn);
141 rtx_insn *bb_note = NEXT_INSN (insn);
143 really_delete = false;
144 PUT_CODE (insn, NOTE);
145 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
146 NOTE_DELETED_LABEL_NAME (insn) = name;
148 /* If the note following the label starts a basic block, and the
149 label is a member of the same basic block, interchange the two. */
150 if (bb_note != NULL_RTX
151 && NOTE_INSN_BASIC_BLOCK_P (bb_note)
152 && bb != NULL
153 && bb == BLOCK_FOR_INSN (bb_note))
155 reorder_insns_nobb (insn, insn, bb_note);
156 BB_HEAD (bb) = bb_note;
157 if (BB_END (bb) == bb_note)
158 BB_END (bb) = insn;
162 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
165 if (really_delete)
167 /* If this insn has already been deleted, something is very wrong. */
168 gcc_assert (!INSN_DELETED_P (insn));
169 if (INSN_P (insn))
170 df_insn_delete (insn);
171 remove_insn (insn);
172 INSN_DELETED_P (insn) = 1;
175 /* If deleting a jump, decrement the use count of the label. Deleting
176 the label itself should happen in the normal course of block merging. */
177 if (JUMP_P (insn))
179 if (JUMP_LABEL (insn)
180 && LABEL_P (JUMP_LABEL (insn)))
181 LABEL_NUSES (JUMP_LABEL (insn))--;
183 /* If there are more targets, remove them too. */
184 while ((note
185 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
186 && LABEL_P (XEXP (note, 0)))
188 LABEL_NUSES (XEXP (note, 0))--;
189 remove_note (insn, note);
193 /* Also if deleting any insn that references a label as an operand. */
194 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
195 && LABEL_P (XEXP (note, 0)))
197 LABEL_NUSES (XEXP (note, 0))--;
198 remove_note (insn, note);
201 if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
203 rtvec vec = table->get_labels ();
204 int len = GET_NUM_ELEM (vec);
205 int i;
207 for (i = 0; i < len; i++)
209 rtx label = XEXP (RTVEC_ELT (vec, i), 0);
211 /* When deleting code in bulk (e.g. removing many unreachable
212 blocks) we can delete a label that's a target of the vector
213 before deleting the vector itself. */
214 if (!NOTE_P (label))
215 LABEL_NUSES (label)--;
220 /* Like delete_insn but also purge dead edges from BB. */
222 void
223 delete_insn_and_edges (rtx_insn *insn)
225 bool purge = false;
227 if (INSN_P (insn)
228 && BLOCK_FOR_INSN (insn)
229 && BB_END (BLOCK_FOR_INSN (insn)) == insn)
230 purge = true;
231 delete_insn (insn);
232 if (purge)
233 purge_dead_edges (BLOCK_FOR_INSN (insn));
236 /* Unlink a chain of insns between START and FINISH, leaving notes
237 that must be paired. If CLEAR_BB is true, we set bb field for
238 insns that cannot be removed to NULL. */
240 void
241 delete_insn_chain (rtx start, rtx finish, bool clear_bb)
243 rtx_insn *prev, *current;
245 /* Unchain the insns one by one. It would be quicker to delete all of these
246 with a single unchaining, rather than one at a time, but we need to keep
247 the NOTE's. */
248 current = safe_as_a <rtx_insn *> (finish);
249 while (1)
251 prev = PREV_INSN (current);
252 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
254 else
255 delete_insn (current);
257 if (clear_bb && !INSN_DELETED_P (current))
258 set_block_for_insn (current, NULL);
260 if (current == start)
261 break;
262 current = prev;
266 /* Create a new basic block consisting of the instructions between HEAD and END
267 inclusive. This function is designed to allow fast BB construction - reuses
268 the note and basic block struct in BB_NOTE, if any and do not grow
269 BASIC_BLOCK chain and should be used directly only by CFG construction code.
270 END can be NULL in to create new empty basic block before HEAD. Both END
271 and HEAD can be NULL to create basic block at the end of INSN chain.
272 AFTER is the basic block we should be put after. */
274 basic_block
275 create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
276 basic_block after)
278 basic_block bb;
280 if (bb_note
281 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
282 && bb->aux == NULL)
284 /* If we found an existing note, thread it back onto the chain. */
286 rtx_insn *after;
288 if (LABEL_P (head))
289 after = head;
290 else
292 after = PREV_INSN (head);
293 head = bb_note;
296 if (after != bb_note && NEXT_INSN (after) != bb_note)
297 reorder_insns_nobb (bb_note, bb_note, after);
299 else
301 /* Otherwise we must create a note and a basic block structure. */
303 bb = alloc_block ();
305 init_rtl_bb_info (bb);
306 if (!head && !end)
307 head = end = bb_note
308 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
309 else if (LABEL_P (head) && end)
311 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
312 if (head == end)
313 end = bb_note;
315 else
317 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
318 head = bb_note;
319 if (!end)
320 end = head;
323 NOTE_BASIC_BLOCK (bb_note) = bb;
326 /* Always include the bb note in the block. */
327 if (NEXT_INSN (end) == bb_note)
328 end = bb_note;
330 BB_HEAD (bb) = head;
331 BB_END (bb) = end;
332 bb->index = last_basic_block_for_fn (cfun)++;
333 bb->flags = BB_NEW | BB_RTL;
334 link_block (bb, after);
335 SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
336 df_bb_refs_record (bb->index, false);
337 update_bb_for_insn (bb);
338 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
340 /* Tag the block so that we know it has been used when considering
341 other basic block notes. */
342 bb->aux = bb;
344 return bb;
347 /* Create new basic block consisting of instructions in between HEAD and END
348 and place it to the BB chain after block AFTER. END can be NULL to
349 create a new empty basic block before HEAD. Both END and HEAD can be
350 NULL to create basic block at the end of INSN chain. */
352 static basic_block
353 rtl_create_basic_block (void *headp, void *endp, basic_block after)
355 rtx_insn *head = (rtx_insn *) headp;
356 rtx_insn *end = (rtx_insn *) endp;
357 basic_block bb;
359 /* Grow the basic block array if needed. */
360 if ((size_t) last_basic_block_for_fn (cfun)
361 >= basic_block_info_for_fn (cfun)->length ())
363 size_t new_size =
364 (last_basic_block_for_fn (cfun)
365 + (last_basic_block_for_fn (cfun) + 3) / 4);
366 vec_safe_grow_cleared (basic_block_info_for_fn (cfun), new_size);
369 n_basic_blocks_for_fn (cfun)++;
371 bb = create_basic_block_structure (head, end, NULL, after);
372 bb->aux = NULL;
373 return bb;
376 static basic_block
377 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
379 basic_block newbb = rtl_create_basic_block (head, end, after);
381 return newbb;
384 /* Delete the insns in a (non-live) block. We physically delete every
385 non-deleted-note insn, and update the flow graph appropriately.
387 Return nonzero if we deleted an exception handler. */
389 /* ??? Preserving all such notes strikes me as wrong. It would be nice
390 to post-process the stream to remove empty blocks, loops, ranges, etc. */
392 static void
393 rtl_delete_block (basic_block b)
395 rtx_insn *insn, *end;
397 /* If the head of this block is a CODE_LABEL, then it might be the
398 label for an exception handler which can't be reached. We need
399 to remove the label from the exception_handler_label list. */
400 insn = BB_HEAD (b);
402 end = get_last_bb_insn (b);
404 /* Selectively delete the entire chain. */
405 BB_HEAD (b) = NULL;
406 delete_insn_chain (insn, end, true);
409 if (dump_file)
410 fprintf (dump_file, "deleting block %d\n", b->index);
411 df_bb_delete (b->index);
414 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
416 void
417 compute_bb_for_insn (void)
419 basic_block bb;
421 FOR_EACH_BB_FN (bb, cfun)
423 rtx_insn *end = BB_END (bb);
424 rtx_insn *insn;
426 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
428 BLOCK_FOR_INSN (insn) = bb;
429 if (insn == end)
430 break;
435 /* Release the basic_block_for_insn array. */
437 unsigned int
438 free_bb_for_insn (void)
440 rtx_insn *insn;
441 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
442 if (!BARRIER_P (insn))
443 BLOCK_FOR_INSN (insn) = NULL;
444 return 0;
447 namespace {
449 const pass_data pass_data_free_cfg =
451 RTL_PASS, /* type */
452 "*free_cfg", /* name */
453 OPTGROUP_NONE, /* optinfo_flags */
454 TV_NONE, /* tv_id */
455 0, /* properties_required */
456 0, /* properties_provided */
457 PROP_cfg, /* properties_destroyed */
458 0, /* todo_flags_start */
459 0, /* todo_flags_finish */
462 class pass_free_cfg : public rtl_opt_pass
464 public:
465 pass_free_cfg (gcc::context *ctxt)
466 : rtl_opt_pass (pass_data_free_cfg, ctxt)
469 /* opt_pass methods: */
470 virtual unsigned int execute (function *);
472 }; // class pass_free_cfg
474 unsigned int
475 pass_free_cfg::execute (function *)
477 #ifdef DELAY_SLOTS
478 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
479 valid at that point so it would be too late to call df_analyze. */
480 if (optimize > 0 && flag_delayed_branch)
482 df_note_add_problem ();
483 df_analyze ();
485 #endif
487 if (crtl->has_bb_partition)
488 insert_section_boundary_note ();
490 free_bb_for_insn ();
491 return 0;
494 } // anon namespace
496 rtl_opt_pass *
497 make_pass_free_cfg (gcc::context *ctxt)
499 return new pass_free_cfg (ctxt);
502 /* Return RTX to emit after when we want to emit code on the entry of function. */
503 rtx_insn *
504 entry_of_function (void)
506 return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
507 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
510 /* Emit INSN at the entry point of the function, ensuring that it is only
511 executed once per function. */
512 void
513 emit_insn_at_entry (rtx insn)
515 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
516 edge e = ei_safe_edge (ei);
517 gcc_assert (e->flags & EDGE_FALLTHRU);
519 insert_insn_on_edge (insn, e);
520 commit_edge_insertions ();
523 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
524 (or BARRIER if found) and notify df of the bb change.
525 The insn chain range is inclusive
526 (i.e. both BEGIN and END will be updated. */
528 static void
529 update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
531 rtx_insn *insn;
533 end = NEXT_INSN (end);
534 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
535 if (!BARRIER_P (insn))
536 df_insn_change_bb (insn, bb);
539 /* Update BLOCK_FOR_INSN of insns in BB to BB,
540 and notify df of the change. */
542 void
543 update_bb_for_insn (basic_block bb)
545 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
549 /* Like active_insn_p, except keep the return value clobber around
550 even after reload. */
552 static bool
553 flow_active_insn_p (const rtx_insn *insn)
555 if (active_insn_p (insn))
556 return true;
558 /* A clobber of the function return value exists for buggy
559 programs that fail to return a value. Its effect is to
560 keep the return value from being live across the entire
561 function. If we allow it to be skipped, we introduce the
562 possibility for register lifetime confusion. */
563 if (GET_CODE (PATTERN (insn)) == CLOBBER
564 && REG_P (XEXP (PATTERN (insn), 0))
565 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
566 return true;
568 return false;
571 /* Return true if the block has no effect and only forwards control flow to
572 its single destination. */
574 bool
575 contains_no_active_insn_p (const_basic_block bb)
577 rtx_insn *insn;
579 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
580 || !single_succ_p (bb))
581 return false;
583 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
584 if (INSN_P (insn) && flow_active_insn_p (insn))
585 return false;
587 return (!INSN_P (insn)
588 || (JUMP_P (insn) && simplejump_p (insn))
589 || !flow_active_insn_p (insn));
592 /* Likewise, but protect loop latches, headers and preheaders. */
593 /* FIXME: Make this a cfg hook. */
595 bool
596 forwarder_block_p (const_basic_block bb)
598 if (!contains_no_active_insn_p (bb))
599 return false;
601 /* Protect loop latches, headers and preheaders. */
602 if (current_loops)
604 basic_block dest;
605 if (bb->loop_father->header == bb)
606 return false;
607 dest = EDGE_SUCC (bb, 0)->dest;
608 if (dest->loop_father->header == dest)
609 return false;
612 return true;
615 /* Return nonzero if we can reach target from src by falling through. */
616 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
618 bool
619 can_fallthru (basic_block src, basic_block target)
621 rtx_insn *insn = BB_END (src);
622 rtx_insn *insn2;
623 edge e;
624 edge_iterator ei;
626 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
627 return true;
628 if (src->next_bb != target)
629 return false;
631 /* ??? Later we may add code to move jump tables offline. */
632 if (tablejump_p (insn, NULL, NULL))
633 return false;
635 FOR_EACH_EDGE (e, ei, src->succs)
636 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
637 && e->flags & EDGE_FALLTHRU)
638 return false;
640 insn2 = BB_HEAD (target);
641 if (!active_insn_p (insn2))
642 insn2 = next_active_insn (insn2);
644 return next_active_insn (insn) == insn2;
647 /* Return nonzero if we could reach target from src by falling through,
648 if the target was made adjacent. If we already have a fall-through
649 edge to the exit block, we can't do that. */
650 static bool
651 could_fall_through (basic_block src, basic_block target)
653 edge e;
654 edge_iterator ei;
656 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
657 return true;
658 FOR_EACH_EDGE (e, ei, src->succs)
659 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
660 && e->flags & EDGE_FALLTHRU)
661 return 0;
662 return true;
665 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
666 rtx_note *
667 bb_note (basic_block bb)
669 rtx_insn *note;
671 note = BB_HEAD (bb);
672 if (LABEL_P (note))
673 note = NEXT_INSN (note);
675 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
676 return as_a <rtx_note *> (note);
679 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
680 note associated with the BLOCK. */
682 static rtx_insn *
683 first_insn_after_basic_block_note (basic_block block)
685 rtx_insn *insn;
687 /* Get the first instruction in the block. */
688 insn = BB_HEAD (block);
690 if (insn == NULL_RTX)
691 return NULL;
692 if (LABEL_P (insn))
693 insn = NEXT_INSN (insn);
694 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
696 return NEXT_INSN (insn);
699 /* Creates a new basic block just after basic block B by splitting
700 everything after specified instruction I. */
702 static basic_block
703 rtl_split_block (basic_block bb, void *insnp)
705 basic_block new_bb;
706 rtx_insn *insn = (rtx_insn *) insnp;
707 edge e;
708 edge_iterator ei;
710 if (!insn)
712 insn = first_insn_after_basic_block_note (bb);
714 if (insn)
716 rtx_insn *next = insn;
718 insn = PREV_INSN (insn);
720 /* If the block contains only debug insns, insn would have
721 been NULL in a non-debug compilation, and then we'd end
722 up emitting a DELETED note. For -fcompare-debug
723 stability, emit the note too. */
724 if (insn != BB_END (bb)
725 && DEBUG_INSN_P (next)
726 && DEBUG_INSN_P (BB_END (bb)))
728 while (next != BB_END (bb) && DEBUG_INSN_P (next))
729 next = NEXT_INSN (next);
731 if (next == BB_END (bb))
732 emit_note_after (NOTE_INSN_DELETED, next);
735 else
736 insn = get_last_insn ();
739 /* We probably should check type of the insn so that we do not create
740 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
741 bother. */
742 if (insn == BB_END (bb))
743 emit_note_after (NOTE_INSN_DELETED, insn);
745 /* Create the new basic block. */
746 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
747 BB_COPY_PARTITION (new_bb, bb);
748 BB_END (bb) = insn;
750 /* Redirect the outgoing edges. */
751 new_bb->succs = bb->succs;
752 bb->succs = NULL;
753 FOR_EACH_EDGE (e, ei, new_bb->succs)
754 e->src = new_bb;
756 /* The new block starts off being dirty. */
757 df_set_bb_dirty (bb);
758 return new_bb;
761 /* Return true if the single edge between blocks A and B is the only place
762 in RTL which holds some unique locus. */
764 static bool
765 unique_locus_on_edge_between_p (basic_block a, basic_block b)
767 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
768 rtx_insn *insn, *end;
770 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
771 return false;
773 /* First scan block A backward. */
774 insn = BB_END (a);
775 end = PREV_INSN (BB_HEAD (a));
776 while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
777 insn = PREV_INSN (insn);
779 if (insn != end && INSN_LOCATION (insn) == goto_locus)
780 return false;
782 /* Then scan block B forward. */
783 insn = BB_HEAD (b);
784 if (insn)
786 end = NEXT_INSN (BB_END (b));
787 while (insn != end && !NONDEBUG_INSN_P (insn))
788 insn = NEXT_INSN (insn);
790 if (insn != end && INSN_HAS_LOCATION (insn)
791 && INSN_LOCATION (insn) == goto_locus)
792 return false;
795 return true;
798 /* If the single edge between blocks A and B is the only place in RTL which
799 holds some unique locus, emit a nop with that locus between the blocks. */
801 static void
802 emit_nop_for_unique_locus_between (basic_block a, basic_block b)
804 if (!unique_locus_on_edge_between_p (a, b))
805 return;
807 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
808 INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
811 /* Blocks A and B are to be merged into a single block A. The insns
812 are already contiguous. */
814 static void
815 rtl_merge_blocks (basic_block a, basic_block b)
817 rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
818 rtx_insn *del_first = NULL, *del_last = NULL;
819 rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
820 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
821 int b_empty = 0;
823 if (dump_file)
824 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
825 a->index);
827 while (DEBUG_INSN_P (b_end))
828 b_end = PREV_INSN (b_debug_start = b_end);
830 /* If there was a CODE_LABEL beginning B, delete it. */
831 if (LABEL_P (b_head))
833 /* Detect basic blocks with nothing but a label. This can happen
834 in particular at the end of a function. */
835 if (b_head == b_end)
836 b_empty = 1;
838 del_first = del_last = b_head;
839 b_head = NEXT_INSN (b_head);
842 /* Delete the basic block note and handle blocks containing just that
843 note. */
844 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
846 if (b_head == b_end)
847 b_empty = 1;
848 if (! del_last)
849 del_first = b_head;
851 del_last = b_head;
852 b_head = NEXT_INSN (b_head);
855 /* If there was a jump out of A, delete it. */
856 if (JUMP_P (a_end))
858 rtx_insn *prev;
860 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
861 if (!NOTE_P (prev)
862 || NOTE_INSN_BASIC_BLOCK_P (prev)
863 || prev == BB_HEAD (a))
864 break;
866 del_first = a_end;
868 #ifdef HAVE_cc0
869 /* If this was a conditional jump, we need to also delete
870 the insn that set cc0. */
871 if (only_sets_cc0_p (prev))
873 rtx_insn *tmp = prev;
875 prev = prev_nonnote_insn (prev);
876 if (!prev)
877 prev = BB_HEAD (a);
878 del_first = tmp;
880 #endif
882 a_end = PREV_INSN (del_first);
884 else if (BARRIER_P (NEXT_INSN (a_end)))
885 del_first = NEXT_INSN (a_end);
887 /* Delete everything marked above as well as crap that might be
888 hanging out between the two blocks. */
889 BB_END (a) = a_end;
890 BB_HEAD (b) = b_empty ? NULL : b_head;
891 delete_insn_chain (del_first, del_last, true);
893 /* When not optimizing and the edge is the only place in RTL which holds
894 some unique locus, emit a nop with that locus in between. */
895 if (!optimize)
897 emit_nop_for_unique_locus_between (a, b);
898 a_end = BB_END (a);
901 /* Reassociate the insns of B with A. */
902 if (!b_empty)
904 update_bb_for_insn_chain (a_end, b_debug_end, a);
906 BB_END (a) = b_debug_end;
907 BB_HEAD (b) = NULL;
909 else if (b_end != b_debug_end)
911 /* Move any deleted labels and other notes between the end of A
912 and the debug insns that make up B after the debug insns,
913 bringing the debug insns into A while keeping the notes after
914 the end of A. */
915 if (NEXT_INSN (a_end) != b_debug_start)
916 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
917 b_debug_end);
918 update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
919 BB_END (a) = b_debug_end;
922 df_bb_delete (b->index);
924 /* If B was a forwarder block, propagate the locus on the edge. */
925 if (forwarder_p
926 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
927 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
929 if (dump_file)
930 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
934 /* Return true when block A and B can be merged. */
936 static bool
937 rtl_can_merge_blocks (basic_block a, basic_block b)
939 /* If we are partitioning hot/cold basic blocks, we don't want to
940 mess up unconditional or indirect jumps that cross between hot
941 and cold sections.
943 Basic block partitioning may result in some jumps that appear to
944 be optimizable (or blocks that appear to be mergeable), but which really
945 must be left untouched (they are required to make it safely across
946 partition boundaries). See the comments at the top of
947 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
949 if (BB_PARTITION (a) != BB_PARTITION (b))
950 return false;
952 /* Protect the loop latches. */
953 if (current_loops && b->loop_father->latch == b)
954 return false;
956 /* There must be exactly one edge in between the blocks. */
957 return (single_succ_p (a)
958 && single_succ (a) == b
959 && single_pred_p (b)
960 && a != b
961 /* Must be simple edge. */
962 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
963 && a->next_bb == b
964 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
965 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
966 /* If the jump insn has side effects,
967 we can't kill the edge. */
968 && (!JUMP_P (BB_END (a))
969 || (reload_completed
970 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
973 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
974 exist. */
977 block_label (basic_block block)
979 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
980 return NULL_RTX;
982 if (!LABEL_P (BB_HEAD (block)))
984 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
987 return BB_HEAD (block);
990 /* Attempt to perform edge redirection by replacing possibly complex jump
991 instruction by unconditional jump or removing jump completely. This can
992 apply only if all edges now point to the same block. The parameters and
993 return values are equivalent to redirect_edge_and_branch. */
995 edge
996 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
998 basic_block src = e->src;
999 rtx_insn *insn = BB_END (src), *kill_from;
1000 rtx set;
1001 int fallthru = 0;
1003 /* If we are partitioning hot/cold basic blocks, we don't want to
1004 mess up unconditional or indirect jumps that cross between hot
1005 and cold sections.
1007 Basic block partitioning may result in some jumps that appear to
1008 be optimizable (or blocks that appear to be mergeable), but which really
1009 must be left untouched (they are required to make it safely across
1010 partition boundaries). See the comments at the top of
1011 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1013 if (BB_PARTITION (src) != BB_PARTITION (target))
1014 return NULL;
1016 /* We can replace or remove a complex jump only when we have exactly
1017 two edges. Also, if we have exactly one outgoing edge, we can
1018 redirect that. */
1019 if (EDGE_COUNT (src->succs) >= 3
1020 /* Verify that all targets will be TARGET. Specifically, the
1021 edge that is not E must also go to TARGET. */
1022 || (EDGE_COUNT (src->succs) == 2
1023 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1024 return NULL;
1026 if (!onlyjump_p (insn))
1027 return NULL;
1028 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1029 return NULL;
1031 /* Avoid removing branch with side effects. */
1032 set = single_set (insn);
1033 if (!set || side_effects_p (set))
1034 return NULL;
1036 /* In case we zap a conditional jump, we'll need to kill
1037 the cc0 setter too. */
1038 kill_from = insn;
1039 #ifdef HAVE_cc0
1040 if (reg_mentioned_p (cc0_rtx, PATTERN (insn))
1041 && only_sets_cc0_p (PREV_INSN (insn)))
1042 kill_from = PREV_INSN (insn);
1043 #endif
1045 /* See if we can create the fallthru edge. */
1046 if (in_cfglayout || can_fallthru (src, target))
1048 if (dump_file)
1049 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1050 fallthru = 1;
1052 /* Selectively unlink whole insn chain. */
1053 if (in_cfglayout)
1055 rtx_insn *insn = BB_FOOTER (src);
1057 delete_insn_chain (kill_from, BB_END (src), false);
1059 /* Remove barriers but keep jumptables. */
1060 while (insn)
1062 if (BARRIER_P (insn))
1064 if (PREV_INSN (insn))
1065 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1066 else
1067 BB_FOOTER (src) = NEXT_INSN (insn);
1068 if (NEXT_INSN (insn))
1069 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1071 if (LABEL_P (insn))
1072 break;
1073 insn = NEXT_INSN (insn);
1076 else
1077 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
1078 false);
1081 /* If this already is simplejump, redirect it. */
1082 else if (simplejump_p (insn))
1084 if (e->dest == target)
1085 return NULL;
1086 if (dump_file)
1087 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1088 INSN_UID (insn), e->dest->index, target->index);
1089 if (!redirect_jump (insn, block_label (target), 0))
1091 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1092 return NULL;
1096 /* Cannot do anything for target exit block. */
1097 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1098 return NULL;
1100 /* Or replace possibly complicated jump insn by simple jump insn. */
1101 else
1103 rtx target_label = block_label (target);
1104 rtx_insn *barrier;
1105 rtx label;
1106 rtx_jump_table_data *table;
1108 emit_jump_insn_after_noloc (gen_jump (target_label), insn);
1109 JUMP_LABEL (BB_END (src)) = target_label;
1110 LABEL_NUSES (target_label)++;
1111 if (dump_file)
1112 fprintf (dump_file, "Replacing insn %i by jump %i\n",
1113 INSN_UID (insn), INSN_UID (BB_END (src)));
1116 delete_insn_chain (kill_from, insn, false);
1118 /* Recognize a tablejump that we are converting to a
1119 simple jump and remove its associated CODE_LABEL
1120 and ADDR_VEC or ADDR_DIFF_VEC. */
1121 if (tablejump_p (insn, &label, &table))
1122 delete_insn_chain (label, table, false);
1124 barrier = next_nonnote_insn (BB_END (src));
1125 if (!barrier || !BARRIER_P (barrier))
1126 emit_barrier_after (BB_END (src));
1127 else
1129 if (barrier != NEXT_INSN (BB_END (src)))
1131 /* Move the jump before barrier so that the notes
1132 which originally were or were created before jump table are
1133 inside the basic block. */
1134 rtx_insn *new_insn = BB_END (src);
1136 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1137 PREV_INSN (barrier), src);
1139 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1140 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1142 SET_NEXT_INSN (new_insn) = barrier;
1143 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1145 SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1146 SET_PREV_INSN (barrier) = new_insn;
1151 /* Keep only one edge out and set proper flags. */
1152 if (!single_succ_p (src))
1153 remove_edge (e);
1154 gcc_assert (single_succ_p (src));
1156 e = single_succ_edge (src);
1157 if (fallthru)
1158 e->flags = EDGE_FALLTHRU;
1159 else
1160 e->flags = 0;
1162 e->probability = REG_BR_PROB_BASE;
1163 e->count = src->count;
1165 if (e->dest != target)
1166 redirect_edge_succ (e, target);
1167 return e;
1170 /* Subroutine of redirect_branch_edge that tries to patch the jump
1171 instruction INSN so that it reaches block NEW. Do this
1172 only when it originally reached block OLD. Return true if this
1173 worked or the original target wasn't OLD, return false if redirection
1174 doesn't work. */
1176 static bool
1177 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1179 rtx_jump_table_data *table;
1180 rtx tmp;
1181 /* Recognize a tablejump and adjust all matching cases. */
1182 if (tablejump_p (insn, NULL, &table))
1184 rtvec vec;
1185 int j;
1186 rtx new_label = block_label (new_bb);
1188 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1189 return false;
1190 vec = table->get_labels ();
1192 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1193 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1195 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1196 --LABEL_NUSES (old_label);
1197 ++LABEL_NUSES (new_label);
1200 /* Handle casesi dispatch insns. */
1201 if ((tmp = single_set (insn)) != NULL
1202 && SET_DEST (tmp) == pc_rtx
1203 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1204 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1205 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1207 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1208 new_label);
1209 --LABEL_NUSES (old_label);
1210 ++LABEL_NUSES (new_label);
1213 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1215 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1216 rtx new_label, note;
1218 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1219 return false;
1220 new_label = block_label (new_bb);
1222 for (i = 0; i < n; ++i)
1224 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1225 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1226 if (XEXP (old_ref, 0) == old_label)
1228 ASM_OPERANDS_LABEL (tmp, i)
1229 = gen_rtx_LABEL_REF (Pmode, new_label);
1230 --LABEL_NUSES (old_label);
1231 ++LABEL_NUSES (new_label);
1235 if (JUMP_LABEL (insn) == old_label)
1237 JUMP_LABEL (insn) = new_label;
1238 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1239 if (note)
1240 remove_note (insn, note);
1242 else
1244 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1245 if (note)
1246 remove_note (insn, note);
1247 if (JUMP_LABEL (insn) != new_label
1248 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1249 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1251 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1252 != NULL_RTX)
1253 XEXP (note, 0) = new_label;
1255 else
1257 /* ?? We may play the games with moving the named labels from
1258 one basic block to the other in case only one computed_jump is
1259 available. */
1260 if (computed_jump_p (insn)
1261 /* A return instruction can't be redirected. */
1262 || returnjump_p (insn))
1263 return false;
1265 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1267 /* If the insn doesn't go where we think, we're confused. */
1268 gcc_assert (JUMP_LABEL (insn) == old_label);
1270 /* If the substitution doesn't succeed, die. This can happen
1271 if the back end emitted unrecognizable instructions or if
1272 target is exit block on some arches. */
1273 if (!redirect_jump (insn, block_label (new_bb), 0))
1275 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun));
1276 return false;
1280 return true;
1284 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1285 NULL on failure */
1286 static edge
1287 redirect_branch_edge (edge e, basic_block target)
1289 rtx_insn *old_label = BB_HEAD (e->dest);
1290 basic_block src = e->src;
1291 rtx_insn *insn = BB_END (src);
1293 /* We can only redirect non-fallthru edges of jump insn. */
1294 if (e->flags & EDGE_FALLTHRU)
1295 return NULL;
1296 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1297 return NULL;
1299 if (!currently_expanding_to_rtl)
1301 if (!patch_jump_insn (insn, old_label, target))
1302 return NULL;
1304 else
1305 /* When expanding this BB might actually contain multiple
1306 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1307 Redirect all of those that match our label. */
1308 FOR_BB_INSNS (src, insn)
1309 if (JUMP_P (insn) && !patch_jump_insn (insn, old_label, target))
1310 return NULL;
1312 if (dump_file)
1313 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1314 e->src->index, e->dest->index, target->index);
1316 if (e->dest != target)
1317 e = redirect_edge_succ_nodup (e, target);
1319 return e;
1322 /* Called when edge E has been redirected to a new destination,
1323 in order to update the region crossing flag on the edge and
1324 jump. */
1326 static void
1327 fixup_partition_crossing (edge e)
1329 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1330 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1331 return;
1332 /* If we redirected an existing edge, it may already be marked
1333 crossing, even though the new src is missing a reg crossing note.
1334 But make sure reg crossing note doesn't already exist before
1335 inserting. */
1336 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1338 e->flags |= EDGE_CROSSING;
1339 if (JUMP_P (BB_END (e->src))
1340 && !CROSSING_JUMP_P (BB_END (e->src)))
1341 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1343 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1345 e->flags &= ~EDGE_CROSSING;
1346 /* Remove the section crossing note from jump at end of
1347 src if it exists, and if no other successors are
1348 still crossing. */
1349 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1351 bool has_crossing_succ = false;
1352 edge e2;
1353 edge_iterator ei;
1354 FOR_EACH_EDGE (e2, ei, e->src->succs)
1356 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1357 if (has_crossing_succ)
1358 break;
1360 if (!has_crossing_succ)
1361 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1366 /* Called when block BB has been reassigned to the cold partition,
1367 because it is now dominated by another cold block,
1368 to ensure that the region crossing attributes are updated. */
1370 static void
1371 fixup_new_cold_bb (basic_block bb)
1373 edge e;
1374 edge_iterator ei;
1376 /* This is called when a hot bb is found to now be dominated
1377 by a cold bb and therefore needs to become cold. Therefore,
1378 its preds will no longer be region crossing. Any non-dominating
1379 preds that were previously hot would also have become cold
1380 in the caller for the same region. Any preds that were previously
1381 region-crossing will be adjusted in fixup_partition_crossing. */
1382 FOR_EACH_EDGE (e, ei, bb->preds)
1384 fixup_partition_crossing (e);
1387 /* Possibly need to make bb's successor edges region crossing,
1388 or remove stale region crossing. */
1389 FOR_EACH_EDGE (e, ei, bb->succs)
1391 /* We can't have fall-through edges across partition boundaries.
1392 Note that force_nonfallthru will do any necessary partition
1393 boundary fixup by calling fixup_partition_crossing itself. */
1394 if ((e->flags & EDGE_FALLTHRU)
1395 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1396 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1397 force_nonfallthru (e);
1398 else
1399 fixup_partition_crossing (e);
1403 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1404 expense of adding new instructions or reordering basic blocks.
1406 Function can be also called with edge destination equivalent to the TARGET.
1407 Then it should try the simplifications and do nothing if none is possible.
1409 Return edge representing the branch if transformation succeeded. Return NULL
1410 on failure.
1411 We still return NULL in case E already destinated TARGET and we didn't
1412 managed to simplify instruction stream. */
1414 static edge
1415 rtl_redirect_edge_and_branch (edge e, basic_block target)
1417 edge ret;
1418 basic_block src = e->src;
1419 basic_block dest = e->dest;
1421 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1422 return NULL;
1424 if (dest == target)
1425 return e;
1427 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1429 df_set_bb_dirty (src);
1430 fixup_partition_crossing (ret);
1431 return ret;
1434 ret = redirect_branch_edge (e, target);
1435 if (!ret)
1436 return NULL;
1438 df_set_bb_dirty (src);
1439 fixup_partition_crossing (ret);
1440 return ret;
1443 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1445 void
1446 emit_barrier_after_bb (basic_block bb)
1448 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1449 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1450 || current_ir_type () == IR_RTL_CFGLAYOUT);
1451 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1452 BB_FOOTER (bb) = unlink_insn_chain (barrier, barrier);
1455 /* Like force_nonfallthru below, but additionally performs redirection
1456 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1457 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1458 simple_return_rtx, indicating which kind of returnjump to create.
1459 It should be NULL otherwise. */
1461 basic_block
1462 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1464 basic_block jump_block, new_bb = NULL, src = e->src;
1465 rtx note;
1466 edge new_edge;
1467 int abnormal_edge_flags = 0;
1468 bool asm_goto_edge = false;
1469 int loc;
1471 /* In the case the last instruction is conditional jump to the next
1472 instruction, first redirect the jump itself and then continue
1473 by creating a basic block afterwards to redirect fallthru edge. */
1474 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1475 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1476 && any_condjump_p (BB_END (e->src))
1477 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1479 rtx note;
1480 edge b = unchecked_make_edge (e->src, target, 0);
1481 bool redirected;
1483 redirected = redirect_jump (BB_END (e->src), block_label (target), 0);
1484 gcc_assert (redirected);
1486 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1487 if (note)
1489 int prob = XINT (note, 0);
1491 b->probability = prob;
1492 /* Update this to use GCOV_COMPUTE_SCALE. */
1493 b->count = e->count * prob / REG_BR_PROB_BASE;
1494 e->probability -= e->probability;
1495 e->count -= b->count;
1496 if (e->probability < 0)
1497 e->probability = 0;
1498 if (e->count < 0)
1499 e->count = 0;
1503 if (e->flags & EDGE_ABNORMAL)
1505 /* Irritating special case - fallthru edge to the same block as abnormal
1506 edge.
1507 We can't redirect abnormal edge, but we still can split the fallthru
1508 one and create separate abnormal edge to original destination.
1509 This allows bb-reorder to make such edge non-fallthru. */
1510 gcc_assert (e->dest == target);
1511 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1512 e->flags &= EDGE_FALLTHRU;
1514 else
1516 gcc_assert (e->flags & EDGE_FALLTHRU);
1517 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1519 /* We can't redirect the entry block. Create an empty block
1520 at the start of the function which we use to add the new
1521 jump. */
1522 edge tmp;
1523 edge_iterator ei;
1524 bool found = false;
1526 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1527 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1529 /* Change the existing edge's source to be the new block, and add
1530 a new edge from the entry block to the new block. */
1531 e->src = bb;
1532 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1533 (tmp = ei_safe_edge (ei)); )
1535 if (tmp == e)
1537 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1538 found = true;
1539 break;
1541 else
1542 ei_next (&ei);
1545 gcc_assert (found);
1547 vec_safe_push (bb->succs, e);
1548 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1549 EDGE_FALLTHRU);
1553 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1554 don't point to the target or fallthru label. */
1555 if (JUMP_P (BB_END (e->src))
1556 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1557 && (e->flags & EDGE_FALLTHRU)
1558 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1560 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1561 bool adjust_jump_target = false;
1563 for (i = 0; i < n; ++i)
1565 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1567 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1568 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1569 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1570 adjust_jump_target = true;
1572 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1573 asm_goto_edge = true;
1575 if (adjust_jump_target)
1577 rtx_insn *insn = BB_END (e->src);
1578 rtx note;
1579 rtx_insn *old_label = BB_HEAD (e->dest);
1580 rtx_insn *new_label = BB_HEAD (target);
1582 if (JUMP_LABEL (insn) == old_label)
1584 JUMP_LABEL (insn) = new_label;
1585 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1586 if (note)
1587 remove_note (insn, note);
1589 else
1591 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1592 if (note)
1593 remove_note (insn, note);
1594 if (JUMP_LABEL (insn) != new_label
1595 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1596 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1598 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1599 != NULL_RTX)
1600 XEXP (note, 0) = new_label;
1604 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1606 gcov_type count = e->count;
1607 int probability = e->probability;
1608 /* Create the new structures. */
1610 /* If the old block ended with a tablejump, skip its table
1611 by searching forward from there. Otherwise start searching
1612 forward from the last instruction of the old block. */
1613 rtx_jump_table_data *table;
1614 if (tablejump_p (BB_END (e->src), NULL, &table))
1615 note = table;
1616 else
1617 note = BB_END (e->src);
1618 note = NEXT_INSN (note);
1620 jump_block = create_basic_block (note, NULL, e->src);
1621 jump_block->count = count;
1622 jump_block->frequency = EDGE_FREQUENCY (e);
1624 /* Make sure new block ends up in correct hot/cold section. */
1626 BB_COPY_PARTITION (jump_block, e->src);
1628 /* Wire edge in. */
1629 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1630 new_edge->probability = probability;
1631 new_edge->count = count;
1633 /* Redirect old edge. */
1634 redirect_edge_pred (e, jump_block);
1635 e->probability = REG_BR_PROB_BASE;
1637 /* If e->src was previously region crossing, it no longer is
1638 and the reg crossing note should be removed. */
1639 fixup_partition_crossing (new_edge);
1641 /* If asm goto has any label refs to target's label,
1642 add also edge from asm goto bb to target. */
1643 if (asm_goto_edge)
1645 new_edge->probability /= 2;
1646 new_edge->count /= 2;
1647 jump_block->count /= 2;
1648 jump_block->frequency /= 2;
1649 new_edge = make_edge (new_edge->src, target,
1650 e->flags & ~EDGE_FALLTHRU);
1651 new_edge->probability = probability - probability / 2;
1652 new_edge->count = count - count / 2;
1655 new_bb = jump_block;
1657 else
1658 jump_block = e->src;
1660 loc = e->goto_locus;
1661 e->flags &= ~EDGE_FALLTHRU;
1662 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1664 if (jump_label == ret_rtx)
1666 #ifdef HAVE_return
1667 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block), loc);
1668 #else
1669 gcc_unreachable ();
1670 #endif
1672 else
1674 gcc_assert (jump_label == simple_return_rtx);
1675 #ifdef HAVE_simple_return
1676 emit_jump_insn_after_setloc (gen_simple_return (),
1677 BB_END (jump_block), loc);
1678 #else
1679 gcc_unreachable ();
1680 #endif
1682 set_return_jump_label (BB_END (jump_block));
1684 else
1686 rtx label = block_label (target);
1687 emit_jump_insn_after_setloc (gen_jump (label), BB_END (jump_block), loc);
1688 JUMP_LABEL (BB_END (jump_block)) = label;
1689 LABEL_NUSES (label)++;
1692 /* We might be in cfg layout mode, and if so, the following routine will
1693 insert the barrier correctly. */
1694 emit_barrier_after_bb (jump_block);
1695 redirect_edge_succ_nodup (e, target);
1697 if (abnormal_edge_flags)
1698 make_edge (src, target, abnormal_edge_flags);
1700 df_mark_solutions_dirty ();
1701 fixup_partition_crossing (e);
1702 return new_bb;
1705 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1706 (and possibly create new basic block) to make edge non-fallthru.
1707 Return newly created BB or NULL if none. */
1709 static basic_block
1710 rtl_force_nonfallthru (edge e)
1712 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1715 /* Redirect edge even at the expense of creating new jump insn or
1716 basic block. Return new basic block if created, NULL otherwise.
1717 Conversion must be possible. */
1719 static basic_block
1720 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1722 if (redirect_edge_and_branch (e, target)
1723 || e->dest == target)
1724 return NULL;
1726 /* In case the edge redirection failed, try to force it to be non-fallthru
1727 and redirect newly created simplejump. */
1728 df_set_bb_dirty (e->src);
1729 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1732 /* The given edge should potentially be a fallthru edge. If that is in
1733 fact true, delete the jump and barriers that are in the way. */
1735 static void
1736 rtl_tidy_fallthru_edge (edge e)
1738 rtx_insn *q;
1739 basic_block b = e->src, c = b->next_bb;
1741 /* ??? In a late-running flow pass, other folks may have deleted basic
1742 blocks by nopping out blocks, leaving multiple BARRIERs between here
1743 and the target label. They ought to be chastised and fixed.
1745 We can also wind up with a sequence of undeletable labels between
1746 one block and the next.
1748 So search through a sequence of barriers, labels, and notes for
1749 the head of block C and assert that we really do fall through. */
1751 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1752 if (INSN_P (q))
1753 return;
1755 /* Remove what will soon cease being the jump insn from the source block.
1756 If block B consisted only of this single jump, turn it into a deleted
1757 note. */
1758 q = BB_END (b);
1759 if (JUMP_P (q)
1760 && onlyjump_p (q)
1761 && (any_uncondjump_p (q)
1762 || single_succ_p (b)))
1764 #ifdef HAVE_cc0
1765 /* If this was a conditional jump, we need to also delete
1766 the insn that set cc0. */
1767 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1768 q = PREV_INSN (q);
1769 #endif
1771 q = PREV_INSN (q);
1774 /* Selectively unlink the sequence. */
1775 if (q != PREV_INSN (BB_HEAD (c)))
1776 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1778 e->flags |= EDGE_FALLTHRU;
1781 /* Should move basic block BB after basic block AFTER. NIY. */
1783 static bool
1784 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1785 basic_block after ATTRIBUTE_UNUSED)
1787 return false;
1790 /* Locate the last bb in the same partition as START_BB. */
1792 static basic_block
1793 last_bb_in_partition (basic_block start_bb)
1795 basic_block bb;
1796 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1798 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1799 return bb;
1801 /* Return bb before the exit block. */
1802 return bb->prev_bb;
1805 /* Split a (typically critical) edge. Return the new block.
1806 The edge must not be abnormal.
1808 ??? The code generally expects to be called on critical edges.
1809 The case of a block ending in an unconditional jump to a
1810 block with multiple predecessors is not handled optimally. */
1812 static basic_block
1813 rtl_split_edge (edge edge_in)
1815 basic_block bb, new_bb;
1816 rtx_insn *before;
1818 /* Abnormal edges cannot be split. */
1819 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1821 /* We are going to place the new block in front of edge destination.
1822 Avoid existence of fallthru predecessors. */
1823 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1825 edge e = find_fallthru_edge (edge_in->dest->preds);
1827 if (e)
1828 force_nonfallthru (e);
1831 /* Create the basic block note. */
1832 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1833 before = BB_HEAD (edge_in->dest);
1834 else
1835 before = NULL;
1837 /* If this is a fall through edge to the exit block, the blocks might be
1838 not adjacent, and the right place is after the source. */
1839 if ((edge_in->flags & EDGE_FALLTHRU)
1840 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1842 before = NEXT_INSN (BB_END (edge_in->src));
1843 bb = create_basic_block (before, NULL, edge_in->src);
1844 BB_COPY_PARTITION (bb, edge_in->src);
1846 else
1848 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1850 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1851 BB_COPY_PARTITION (bb, edge_in->dest);
1853 else
1855 basic_block after = edge_in->dest->prev_bb;
1856 /* If this is post-bb reordering, and the edge crosses a partition
1857 boundary, the new block needs to be inserted in the bb chain
1858 at the end of the src partition (since we put the new bb into
1859 that partition, see below). Otherwise we may end up creating
1860 an extra partition crossing in the chain, which is illegal.
1861 It can't go after the src, because src may have a fall-through
1862 to a different block. */
1863 if (crtl->bb_reorder_complete
1864 && (edge_in->flags & EDGE_CROSSING))
1866 after = last_bb_in_partition (edge_in->src);
1867 before = NEXT_INSN (BB_END (after));
1868 /* The instruction following the last bb in partition should
1869 be a barrier, since it cannot end in a fall-through. */
1870 gcc_checking_assert (BARRIER_P (before));
1871 before = NEXT_INSN (before);
1873 bb = create_basic_block (before, NULL, after);
1874 /* Put the split bb into the src partition, to avoid creating
1875 a situation where a cold bb dominates a hot bb, in the case
1876 where src is cold and dest is hot. The src will dominate
1877 the new bb (whereas it might not have dominated dest). */
1878 BB_COPY_PARTITION (bb, edge_in->src);
1882 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1884 /* Can't allow a region crossing edge to be fallthrough. */
1885 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1886 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1888 new_bb = force_nonfallthru (single_succ_edge (bb));
1889 gcc_assert (!new_bb);
1892 /* For non-fallthru edges, we must adjust the predecessor's
1893 jump instruction to target our new block. */
1894 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1896 edge redirected = redirect_edge_and_branch (edge_in, bb);
1897 gcc_assert (redirected);
1899 else
1901 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1903 /* For asm goto even splitting of fallthru edge might
1904 need insn patching, as other labels might point to the
1905 old label. */
1906 rtx_insn *last = BB_END (edge_in->src);
1907 if (last
1908 && JUMP_P (last)
1909 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1910 && extract_asm_operands (PATTERN (last)) != NULL_RTX
1911 && patch_jump_insn (last, before, bb))
1912 df_set_bb_dirty (edge_in->src);
1914 redirect_edge_succ (edge_in, bb);
1917 return bb;
1920 /* Queue instructions for insertion on an edge between two basic blocks.
1921 The new instructions and basic blocks (if any) will not appear in the
1922 CFG until commit_edge_insertions is called. */
1924 void
1925 insert_insn_on_edge (rtx pattern, edge e)
1927 /* We cannot insert instructions on an abnormal critical edge.
1928 It will be easier to find the culprit if we die now. */
1929 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1931 if (e->insns.r == NULL_RTX)
1932 start_sequence ();
1933 else
1934 push_to_sequence (e->insns.r);
1936 emit_insn (pattern);
1938 e->insns.r = get_insns ();
1939 end_sequence ();
1942 /* Update the CFG for the instructions queued on edge E. */
1944 void
1945 commit_one_edge_insertion (edge e)
1947 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1948 basic_block bb;
1950 /* Pull the insns off the edge now since the edge might go away. */
1951 insns = e->insns.r;
1952 e->insns.r = NULL;
1954 /* Figure out where to put these insns. If the destination has
1955 one predecessor, insert there. Except for the exit block. */
1956 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1958 bb = e->dest;
1960 /* Get the location correct wrt a code label, and "nice" wrt
1961 a basic block note, and before everything else. */
1962 tmp = BB_HEAD (bb);
1963 if (LABEL_P (tmp))
1964 tmp = NEXT_INSN (tmp);
1965 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1966 tmp = NEXT_INSN (tmp);
1967 if (tmp == BB_HEAD (bb))
1968 before = tmp;
1969 else if (tmp)
1970 after = PREV_INSN (tmp);
1971 else
1972 after = get_last_insn ();
1975 /* If the source has one successor and the edge is not abnormal,
1976 insert there. Except for the entry block.
1977 Don't do this if the predecessor ends in a jump other than
1978 unconditional simple jump. E.g. for asm goto that points all
1979 its labels at the fallthru basic block, we can't insert instructions
1980 before the asm goto, as the asm goto can have various of side effects,
1981 and can't emit instructions after the asm goto, as it must end
1982 the basic block. */
1983 else if ((e->flags & EDGE_ABNORMAL) == 0
1984 && single_succ_p (e->src)
1985 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1986 && (!JUMP_P (BB_END (e->src))
1987 || simplejump_p (BB_END (e->src))))
1989 bb = e->src;
1991 /* It is possible to have a non-simple jump here. Consider a target
1992 where some forms of unconditional jumps clobber a register. This
1993 happens on the fr30 for example.
1995 We know this block has a single successor, so we can just emit
1996 the queued insns before the jump. */
1997 if (JUMP_P (BB_END (bb)))
1998 before = BB_END (bb);
1999 else
2001 /* We'd better be fallthru, or we've lost track of what's what. */
2002 gcc_assert (e->flags & EDGE_FALLTHRU);
2004 after = BB_END (bb);
2008 /* Otherwise we must split the edge. */
2009 else
2011 bb = split_edge (e);
2013 /* If E crossed a partition boundary, we needed to make bb end in
2014 a region-crossing jump, even though it was originally fallthru. */
2015 if (JUMP_P (BB_END (bb)))
2016 before = BB_END (bb);
2017 else
2018 after = BB_END (bb);
2021 /* Now that we've found the spot, do the insertion. */
2022 if (before)
2024 emit_insn_before_noloc (insns, before, bb);
2025 last = prev_nonnote_insn (before);
2027 else
2028 last = emit_insn_after_noloc (insns, after, bb);
2030 if (returnjump_p (last))
2032 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2033 This is not currently a problem because this only happens
2034 for the (single) epilogue, which already has a fallthru edge
2035 to EXIT. */
2037 e = single_succ_edge (bb);
2038 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2039 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2041 e->flags &= ~EDGE_FALLTHRU;
2042 emit_barrier_after (last);
2044 if (before)
2045 delete_insn (before);
2047 else
2048 gcc_assert (!JUMP_P (last));
2051 /* Update the CFG for all queued instructions. */
2053 void
2054 commit_edge_insertions (void)
2056 basic_block bb;
2058 /* Optimization passes that invoke this routine can cause hot blocks
2059 previously reached by both hot and cold blocks to become dominated only
2060 by cold blocks. This will cause the verification below to fail,
2061 and lead to now cold code in the hot section. In some cases this
2062 may only be visible after newly unreachable blocks are deleted,
2063 which will be done by fixup_partitions. */
2064 fixup_partitions ();
2066 #ifdef ENABLE_CHECKING
2067 verify_flow_info ();
2068 #endif
2070 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2071 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2073 edge e;
2074 edge_iterator ei;
2076 FOR_EACH_EDGE (e, ei, bb->succs)
2077 if (e->insns.r)
2078 commit_one_edge_insertion (e);
2083 /* Print out RTL-specific basic block information (live information
2084 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2085 documented in dumpfile.h. */
2087 static void
2088 rtl_dump_bb (FILE *outf, basic_block bb, int indent, int flags)
2090 rtx_insn *insn;
2091 rtx_insn *last;
2092 char *s_indent;
2094 s_indent = (char *) alloca ((size_t) indent + 1);
2095 memset (s_indent, ' ', (size_t) indent);
2096 s_indent[indent] = '\0';
2098 if (df && (flags & TDF_DETAILS))
2100 df_dump_top (bb, outf);
2101 putc ('\n', outf);
2104 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK)
2105 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
2106 insn = NEXT_INSN (insn))
2108 if (flags & TDF_DETAILS)
2109 df_dump_insn_top (insn, outf);
2110 if (! (flags & TDF_SLIM))
2111 print_rtl_single (outf, insn);
2112 else
2113 dump_insn_slim (outf, insn);
2114 if (flags & TDF_DETAILS)
2115 df_dump_insn_bottom (insn, outf);
2118 if (df && (flags & TDF_DETAILS))
2120 df_dump_bottom (bb, outf);
2121 putc ('\n', outf);
2126 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2127 for the start of each basic block. FLAGS are the TDF_* masks documented
2128 in dumpfile.h. */
2130 void
2131 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, int flags)
2133 const rtx_insn *tmp_rtx;
2134 if (rtx_first == 0)
2135 fprintf (outf, "(nil)\n");
2136 else
2138 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2139 int max_uid = get_max_uid ();
2140 basic_block *start = XCNEWVEC (basic_block, max_uid);
2141 basic_block *end = XCNEWVEC (basic_block, max_uid);
2142 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2143 basic_block bb;
2145 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2146 insns, but the CFG is not maintained so the basic block info
2147 is not reliable. Therefore it's omitted from the dumps. */
2148 if (! (cfun->curr_properties & PROP_cfg))
2149 flags &= ~TDF_BLOCKS;
2151 if (df)
2152 df_dump_start (outf);
2154 if (flags & TDF_BLOCKS)
2156 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2158 rtx_insn *x;
2160 start[INSN_UID (BB_HEAD (bb))] = bb;
2161 end[INSN_UID (BB_END (bb))] = bb;
2162 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2164 enum bb_state state = IN_MULTIPLE_BB;
2166 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2167 state = IN_ONE_BB;
2168 in_bb_p[INSN_UID (x)] = state;
2170 if (x == BB_END (bb))
2171 break;
2176 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
2178 if (flags & TDF_BLOCKS)
2180 bb = start[INSN_UID (tmp_rtx)];
2181 if (bb != NULL)
2183 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, true, false);
2184 if (df && (flags & TDF_DETAILS))
2185 df_dump_top (bb, outf);
2188 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2189 && !NOTE_P (tmp_rtx)
2190 && !BARRIER_P (tmp_rtx))
2191 fprintf (outf, ";; Insn is not within a basic block\n");
2192 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2193 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2196 if (flags & TDF_DETAILS)
2197 df_dump_insn_top (tmp_rtx, outf);
2198 if (! (flags & TDF_SLIM))
2199 print_rtl_single (outf, tmp_rtx);
2200 else
2201 dump_insn_slim (outf, tmp_rtx);
2202 if (flags & TDF_DETAILS)
2203 df_dump_insn_bottom (tmp_rtx, outf);
2205 if (flags & TDF_BLOCKS)
2207 bb = end[INSN_UID (tmp_rtx)];
2208 if (bb != NULL)
2210 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, false, true);
2211 if (df && (flags & TDF_DETAILS))
2212 df_dump_bottom (bb, outf);
2213 putc ('\n', outf);
2218 free (start);
2219 free (end);
2220 free (in_bb_p);
2224 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2226 void
2227 update_br_prob_note (basic_block bb)
2229 rtx note;
2230 if (!JUMP_P (BB_END (bb)))
2231 return;
2232 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2233 if (!note || XINT (note, 0) == BRANCH_EDGE (bb)->probability)
2234 return;
2235 XINT (note, 0) = BRANCH_EDGE (bb)->probability;
2238 /* Get the last insn associated with block BB (that includes barriers and
2239 tablejumps after BB). */
2240 rtx_insn *
2241 get_last_bb_insn (basic_block bb)
2243 rtx_jump_table_data *table;
2244 rtx_insn *tmp;
2245 rtx_insn *end = BB_END (bb);
2247 /* Include any jump table following the basic block. */
2248 if (tablejump_p (end, NULL, &table))
2249 end = table;
2251 /* Include any barriers that may follow the basic block. */
2252 tmp = next_nonnote_insn_bb (end);
2253 while (tmp && BARRIER_P (tmp))
2255 end = tmp;
2256 tmp = next_nonnote_insn_bb (end);
2259 return end;
2262 /* Sanity check partition hotness to ensure that basic blocks in
2263   the cold partition don't dominate basic blocks in the hot partition.
2264 If FLAG_ONLY is true, report violations as errors. Otherwise
2265 re-mark the dominated blocks as cold, since this is run after
2266 cfg optimizations that may make hot blocks previously reached
2267 by both hot and cold blocks now only reachable along cold paths. */
2269 static vec<basic_block>
2270 find_partition_fixes (bool flag_only)
2272 basic_block bb;
2273 vec<basic_block> bbs_in_cold_partition = vNULL;
2274 vec<basic_block> bbs_to_fix = vNULL;
2276 /* Callers check this. */
2277 gcc_checking_assert (crtl->has_bb_partition);
2279 FOR_EACH_BB_FN (bb, cfun)
2280 if ((BB_PARTITION (bb) == BB_COLD_PARTITION))
2281 bbs_in_cold_partition.safe_push (bb);
2283 if (bbs_in_cold_partition.is_empty ())
2284 return vNULL;
2286 bool dom_calculated_here = !dom_info_available_p (CDI_DOMINATORS);
2288 if (dom_calculated_here)
2289 calculate_dominance_info (CDI_DOMINATORS);
2291 while (! bbs_in_cold_partition.is_empty ())
2293 bb = bbs_in_cold_partition.pop ();
2294 /* Any blocks dominated by a block in the cold section
2295 must also be cold. */
2296 basic_block son;
2297 for (son = first_dom_son (CDI_DOMINATORS, bb);
2298 son;
2299 son = next_dom_son (CDI_DOMINATORS, son))
2301 /* If son is not yet cold, then mark it cold here and
2302 enqueue it for further processing. */
2303 if ((BB_PARTITION (son) != BB_COLD_PARTITION))
2305 if (flag_only)
2306 error ("non-cold basic block %d dominated "
2307 "by a block in the cold partition (%d)", son->index, bb->index);
2308 else
2309 BB_SET_PARTITION (son, BB_COLD_PARTITION);
2310 bbs_to_fix.safe_push (son);
2311 bbs_in_cold_partition.safe_push (son);
2316 if (dom_calculated_here)
2317 free_dominance_info (CDI_DOMINATORS);
2319 return bbs_to_fix;
2322 /* Perform cleanup on the hot/cold bb partitioning after optimization
2323 passes that modify the cfg. */
2325 void
2326 fixup_partitions (void)
2328 basic_block bb;
2330 if (!crtl->has_bb_partition)
2331 return;
2333 /* Delete any blocks that became unreachable and weren't
2334 already cleaned up, for example during edge forwarding
2335 and convert_jumps_to_returns. This will expose more
2336 opportunities for fixing the partition boundaries here.
2337 Also, the calculation of the dominance graph during verification
2338 will assert if there are unreachable nodes. */
2339 delete_unreachable_blocks ();
2341 /* If there are partitions, do a sanity check on them: A basic block in
2342   a cold partition cannot dominate a basic block in a hot partition.
2343 Fixup any that now violate this requirement, as a result of edge
2344 forwarding and unreachable block deletion.  */
2345 vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2347 /* Do the partition fixup after all necessary blocks have been converted to
2348 cold, so that we only update the region crossings the minimum number of
2349 places, which can require forcing edges to be non fallthru. */
2350 while (! bbs_to_fix.is_empty ())
2352 bb = bbs_to_fix.pop ();
2353 fixup_new_cold_bb (bb);
2357 /* Verify, in the basic block chain, that there is at most one switch
2358 between hot/cold partitions. This condition will not be true until
2359 after reorder_basic_blocks is called. */
2361 static int
2362 verify_hot_cold_block_grouping (void)
2364 basic_block bb;
2365 int err = 0;
2366 bool switched_sections = false;
2367 int current_partition = BB_UNPARTITIONED;
2369 /* Even after bb reordering is complete, we go into cfglayout mode
2370 again (in compgoto). Ensure we don't call this before going back
2371 into linearized RTL when any layout fixes would have been committed. */
2372 if (!crtl->bb_reorder_complete
2373 || current_ir_type () != IR_RTL_CFGRTL)
2374 return err;
2376 FOR_EACH_BB_FN (bb, cfun)
2378 if (current_partition != BB_UNPARTITIONED
2379 && BB_PARTITION (bb) != current_partition)
2381 if (switched_sections)
2383 error ("multiple hot/cold transitions found (bb %i)",
2384 bb->index);
2385 err = 1;
2387 else
2388 switched_sections = true;
2390 if (!crtl->has_bb_partition)
2391 error ("partition found but function partition flag not set");
2393 current_partition = BB_PARTITION (bb);
2396 return err;
2400 /* Perform several checks on the edges out of each block, such as
2401 the consistency of the branch probabilities, the correctness
2402 of hot/cold partition crossing edges, and the number of expected
2403 successor edges. Also verify that the dominance relationship
2404 between hot/cold blocks is sane. */
2406 static int
2407 rtl_verify_edges (void)
2409 int err = 0;
2410 basic_block bb;
2412 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2414 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2415 int n_eh = 0, n_abnormal = 0;
2416 edge e, fallthru = NULL;
2417 edge_iterator ei;
2418 rtx note;
2419 bool has_crossing_edge = false;
2421 if (JUMP_P (BB_END (bb))
2422 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2423 && EDGE_COUNT (bb->succs) >= 2
2424 && any_condjump_p (BB_END (bb)))
2426 if (XINT (note, 0) != BRANCH_EDGE (bb)->probability
2427 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2429 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2430 XINT (note, 0), BRANCH_EDGE (bb)->probability);
2431 err = 1;
2435 FOR_EACH_EDGE (e, ei, bb->succs)
2437 bool is_crossing;
2439 if (e->flags & EDGE_FALLTHRU)
2440 n_fallthru++, fallthru = e;
2442 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2443 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2444 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2445 has_crossing_edge |= is_crossing;
2446 if (e->flags & EDGE_CROSSING)
2448 if (!is_crossing)
2450 error ("EDGE_CROSSING incorrectly set across same section");
2451 err = 1;
2453 if (e->flags & EDGE_FALLTHRU)
2455 error ("fallthru edge crosses section boundary in bb %i",
2456 e->src->index);
2457 err = 1;
2459 if (e->flags & EDGE_EH)
2461 error ("EH edge crosses section boundary in bb %i",
2462 e->src->index);
2463 err = 1;
2465 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2467 error ("No region crossing jump at section boundary in bb %i",
2468 bb->index);
2469 err = 1;
2472 else if (is_crossing)
2474 error ("EDGE_CROSSING missing across section boundary");
2475 err = 1;
2478 if ((e->flags & ~(EDGE_DFS_BACK
2479 | EDGE_CAN_FALLTHRU
2480 | EDGE_IRREDUCIBLE_LOOP
2481 | EDGE_LOOP_EXIT
2482 | EDGE_CROSSING
2483 | EDGE_PRESERVE)) == 0)
2484 n_branch++;
2486 if (e->flags & EDGE_ABNORMAL_CALL)
2487 n_abnormal_call++;
2489 if (e->flags & EDGE_SIBCALL)
2490 n_sibcall++;
2492 if (e->flags & EDGE_EH)
2493 n_eh++;
2495 if (e->flags & EDGE_ABNORMAL)
2496 n_abnormal++;
2499 if (!has_crossing_edge
2500 && JUMP_P (BB_END (bb))
2501 && CROSSING_JUMP_P (BB_END (bb)))
2503 print_rtl_with_bb (stderr, get_insns (), TDF_RTL | TDF_BLOCKS | TDF_DETAILS);
2504 error ("Region crossing jump across same section in bb %i",
2505 bb->index);
2506 err = 1;
2509 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2511 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2512 err = 1;
2514 if (n_eh > 1)
2516 error ("too many exception handling edges in bb %i", bb->index);
2517 err = 1;
2519 if (n_branch
2520 && (!JUMP_P (BB_END (bb))
2521 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2522 || any_condjump_p (BB_END (bb))))))
2524 error ("too many outgoing branch edges from bb %i", bb->index);
2525 err = 1;
2527 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2529 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2530 err = 1;
2532 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2534 error ("wrong number of branch edges after unconditional jump"
2535 " in bb %i", bb->index);
2536 err = 1;
2538 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2539 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2541 error ("wrong amount of branch edges after conditional jump"
2542 " in bb %i", bb->index);
2543 err = 1;
2545 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2547 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2548 err = 1;
2550 if (n_sibcall && !CALL_P (BB_END (bb)))
2552 error ("sibcall edges for non-call insn in bb %i", bb->index);
2553 err = 1;
2555 if (n_abnormal > n_eh
2556 && !(CALL_P (BB_END (bb))
2557 && n_abnormal == n_abnormal_call + n_sibcall)
2558 && (!JUMP_P (BB_END (bb))
2559 || any_condjump_p (BB_END (bb))
2560 || any_uncondjump_p (BB_END (bb))))
2562 error ("abnormal edges for no purpose in bb %i", bb->index);
2563 err = 1;
2567 /* If there are partitions, do a sanity check on them: A basic block in
2568   a cold partition cannot dominate a basic block in a hot partition.  */
2569 if (crtl->has_bb_partition && !err)
2571 vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2572 err = !bbs_to_fix.is_empty ();
2575 /* Clean up. */
2576 return err;
2579 /* Checks on the instructions within blocks. Currently checks that each
2580 block starts with a basic block note, and that basic block notes and
2581 control flow jumps are not found in the middle of the block. */
2583 static int
2584 rtl_verify_bb_insns (void)
2586 rtx_insn *x;
2587 int err = 0;
2588 basic_block bb;
2590 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2592 /* Now check the header of basic
2593 block. It ought to contain optional CODE_LABEL followed
2594 by NOTE_BASIC_BLOCK. */
2595 x = BB_HEAD (bb);
2596 if (LABEL_P (x))
2598 if (BB_END (bb) == x)
2600 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2601 bb->index);
2602 err = 1;
2605 x = NEXT_INSN (x);
2608 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2610 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2611 bb->index);
2612 err = 1;
2615 if (BB_END (bb) == x)
2616 /* Do checks for empty blocks here. */
2618 else
2619 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2621 if (NOTE_INSN_BASIC_BLOCK_P (x))
2623 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2624 INSN_UID (x), bb->index);
2625 err = 1;
2628 if (x == BB_END (bb))
2629 break;
2631 if (control_flow_insn_p (x))
2633 error ("in basic block %d:", bb->index);
2634 fatal_insn ("flow control insn inside a basic block", x);
2639 /* Clean up. */
2640 return err;
2643 /* Verify that block pointers for instructions in basic blocks, headers and
2644 footers are set appropriately. */
2646 static int
2647 rtl_verify_bb_pointers (void)
2649 int err = 0;
2650 basic_block bb;
2652 /* Check the general integrity of the basic blocks. */
2653 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2655 rtx_insn *insn;
2657 if (!(bb->flags & BB_RTL))
2659 error ("BB_RTL flag not set for block %d", bb->index);
2660 err = 1;
2663 FOR_BB_INSNS (bb, insn)
2664 if (BLOCK_FOR_INSN (insn) != bb)
2666 error ("insn %d basic block pointer is %d, should be %d",
2667 INSN_UID (insn),
2668 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2669 bb->index);
2670 err = 1;
2673 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2674 if (!BARRIER_P (insn)
2675 && BLOCK_FOR_INSN (insn) != NULL)
2677 error ("insn %d in header of bb %d has non-NULL basic block",
2678 INSN_UID (insn), bb->index);
2679 err = 1;
2681 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2682 if (!BARRIER_P (insn)
2683 && BLOCK_FOR_INSN (insn) != NULL)
2685 error ("insn %d in footer of bb %d has non-NULL basic block",
2686 INSN_UID (insn), bb->index);
2687 err = 1;
2691 /* Clean up. */
2692 return err;
2695 /* Verify the CFG and RTL consistency common for both underlying RTL and
2696 cfglayout RTL.
2698 Currently it does following checks:
2700 - overlapping of basic blocks
2701 - insns with wrong BLOCK_FOR_INSN pointers
2702 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2703 - tails of basic blocks (ensure that boundary is necessary)
2704 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2705 and NOTE_INSN_BASIC_BLOCK
2706 - verify that no fall_thru edge crosses hot/cold partition boundaries
2707 - verify that there are no pending RTL branch predictions
2708 - verify that hot blocks are not dominated by cold blocks
2710 In future it can be extended check a lot of other stuff as well
2711 (reachability of basic blocks, life information, etc. etc.). */
2713 static int
2714 rtl_verify_flow_info_1 (void)
2716 int err = 0;
2718 err |= rtl_verify_bb_pointers ();
2720 err |= rtl_verify_bb_insns ();
2722 err |= rtl_verify_edges ();
2724 return err;
2727 /* Walk the instruction chain and verify that bb head/end pointers
2728 are correct, and that instructions are in exactly one bb and have
2729 correct block pointers. */
2731 static int
2732 rtl_verify_bb_insn_chain (void)
2734 basic_block bb;
2735 int err = 0;
2736 rtx_insn *x;
2737 rtx_insn *last_head = get_last_insn ();
2738 basic_block *bb_info;
2739 const int max_uid = get_max_uid ();
2741 bb_info = XCNEWVEC (basic_block, max_uid);
2743 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2745 rtx_insn *head = BB_HEAD (bb);
2746 rtx_insn *end = BB_END (bb);
2748 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2750 /* Verify the end of the basic block is in the INSN chain. */
2751 if (x == end)
2752 break;
2754 /* And that the code outside of basic blocks has NULL bb field. */
2755 if (!BARRIER_P (x)
2756 && BLOCK_FOR_INSN (x) != NULL)
2758 error ("insn %d outside of basic blocks has non-NULL bb field",
2759 INSN_UID (x));
2760 err = 1;
2764 if (!x)
2766 error ("end insn %d for block %d not found in the insn stream",
2767 INSN_UID (end), bb->index);
2768 err = 1;
2771 /* Work backwards from the end to the head of the basic block
2772 to verify the head is in the RTL chain. */
2773 for (; x != NULL_RTX; x = PREV_INSN (x))
2775 /* While walking over the insn chain, verify insns appear
2776 in only one basic block. */
2777 if (bb_info[INSN_UID (x)] != NULL)
2779 error ("insn %d is in multiple basic blocks (%d and %d)",
2780 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2781 err = 1;
2784 bb_info[INSN_UID (x)] = bb;
2786 if (x == head)
2787 break;
2789 if (!x)
2791 error ("head insn %d for block %d not found in the insn stream",
2792 INSN_UID (head), bb->index);
2793 err = 1;
2796 last_head = PREV_INSN (x);
2799 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2801 /* Check that the code before the first basic block has NULL
2802 bb field. */
2803 if (!BARRIER_P (x)
2804 && BLOCK_FOR_INSN (x) != NULL)
2806 error ("insn %d outside of basic blocks has non-NULL bb field",
2807 INSN_UID (x));
2808 err = 1;
2811 free (bb_info);
2813 return err;
2816 /* Verify that fallthru edges point to adjacent blocks in layout order and
2817 that barriers exist after non-fallthru blocks. */
2819 static int
2820 rtl_verify_fallthru (void)
2822 basic_block bb;
2823 int err = 0;
2825 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2827 edge e;
2829 e = find_fallthru_edge (bb->succs);
2830 if (!e)
2832 rtx_insn *insn;
2834 /* Ensure existence of barrier in BB with no fallthru edges. */
2835 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
2837 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
2839 error ("missing barrier after block %i", bb->index);
2840 err = 1;
2841 break;
2843 if (BARRIER_P (insn))
2844 break;
2847 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2848 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2850 rtx_insn *insn;
2852 if (e->src->next_bb != e->dest)
2854 error
2855 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2856 e->src->index, e->dest->index);
2857 err = 1;
2859 else
2860 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2861 insn = NEXT_INSN (insn))
2862 if (BARRIER_P (insn) || INSN_P (insn))
2864 error ("verify_flow_info: Incorrect fallthru %i->%i",
2865 e->src->index, e->dest->index);
2866 fatal_insn ("wrong insn in the fallthru edge", insn);
2867 err = 1;
2872 return err;
2875 /* Verify that blocks are laid out in consecutive order. While walking the
2876 instructions, verify that all expected instructions are inside the basic
2877 blocks, and that all returns are followed by barriers. */
2879 static int
2880 rtl_verify_bb_layout (void)
2882 basic_block bb;
2883 int err = 0;
2884 rtx_insn *x;
2885 int num_bb_notes;
2886 rtx_insn * const rtx_first = get_insns ();
2887 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
2889 num_bb_notes = 0;
2890 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
2892 for (x = rtx_first; x; x = NEXT_INSN (x))
2894 if (NOTE_INSN_BASIC_BLOCK_P (x))
2896 bb = NOTE_BASIC_BLOCK (x);
2898 num_bb_notes++;
2899 if (bb != last_bb_seen->next_bb)
2900 internal_error ("basic blocks not laid down consecutively");
2902 curr_bb = last_bb_seen = bb;
2905 if (!curr_bb)
2907 switch (GET_CODE (x))
2909 case BARRIER:
2910 case NOTE:
2911 break;
2913 case CODE_LABEL:
2914 /* An ADDR_VEC is placed outside any basic block. */
2915 if (NEXT_INSN (x)
2916 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
2917 x = NEXT_INSN (x);
2919 /* But in any case, non-deletable labels can appear anywhere. */
2920 break;
2922 default:
2923 fatal_insn ("insn outside basic block", x);
2927 if (JUMP_P (x)
2928 && returnjump_p (x) && ! condjump_p (x)
2929 && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_insn (x))))
2930 fatal_insn ("return not followed by barrier", x);
2932 if (curr_bb && x == BB_END (curr_bb))
2933 curr_bb = NULL;
2936 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
2937 internal_error
2938 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2939 num_bb_notes, n_basic_blocks_for_fn (cfun));
2941 return err;
2944 /* Verify the CFG and RTL consistency common for both underlying RTL and
2945 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2947 Currently it does following checks:
2948 - all checks of rtl_verify_flow_info_1
2949 - test head/end pointers
2950 - check that blocks are laid out in consecutive order
2951 - check that all insns are in the basic blocks
2952 (except the switch handling code, barriers and notes)
2953 - check that all returns are followed by barriers
2954 - check that all fallthru edge points to the adjacent blocks
2955 - verify that there is a single hot/cold partition boundary after bbro */
2957 static int
2958 rtl_verify_flow_info (void)
2960 int err = 0;
2962 err |= rtl_verify_flow_info_1 ();
2964 err |= rtl_verify_bb_insn_chain ();
2966 err |= rtl_verify_fallthru ();
2968 err |= rtl_verify_bb_layout ();
2970 err |= verify_hot_cold_block_grouping ();
2972 return err;
2975 /* Assume that the preceding pass has possibly eliminated jump instructions
2976 or converted the unconditional jumps. Eliminate the edges from CFG.
2977 Return true if any edges are eliminated. */
2979 bool
2980 purge_dead_edges (basic_block bb)
2982 edge e;
2983 rtx_insn *insn = BB_END (bb);
2984 rtx note;
2985 bool purged = false;
2986 bool found;
2987 edge_iterator ei;
2989 if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb))
2991 insn = PREV_INSN (insn);
2992 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
2994 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2995 if (NONJUMP_INSN_P (insn)
2996 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
2998 rtx eqnote;
3000 if (! may_trap_p (PATTERN (insn))
3001 || ((eqnote = find_reg_equal_equiv_note (insn))
3002 && ! may_trap_p (XEXP (eqnote, 0))))
3003 remove_note (insn, note);
3006 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3007 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3009 bool remove = false;
3011 /* There are three types of edges we need to handle correctly here: EH
3012 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3013 latter can appear when nonlocal gotos are used. */
3014 if (e->flags & EDGE_ABNORMAL_CALL)
3016 if (!CALL_P (insn))
3017 remove = true;
3018 else if (can_nonlocal_goto (insn))
3020 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3022 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3024 else
3025 remove = true;
3027 else if (e->flags & EDGE_EH)
3028 remove = !can_throw_internal (insn);
3030 if (remove)
3032 remove_edge (e);
3033 df_set_bb_dirty (bb);
3034 purged = true;
3036 else
3037 ei_next (&ei);
3040 if (JUMP_P (insn))
3042 rtx note;
3043 edge b,f;
3044 edge_iterator ei;
3046 /* We do care only about conditional jumps and simplejumps. */
3047 if (!any_condjump_p (insn)
3048 && !returnjump_p (insn)
3049 && !simplejump_p (insn))
3050 return purged;
3052 /* Branch probability/prediction notes are defined only for
3053 condjumps. We've possibly turned condjump into simplejump. */
3054 if (simplejump_p (insn))
3056 note = find_reg_note (insn, REG_BR_PROB, NULL);
3057 if (note)
3058 remove_note (insn, note);
3059 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3060 remove_note (insn, note);
3063 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3065 /* Avoid abnormal flags to leak from computed jumps turned
3066 into simplejumps. */
3068 e->flags &= ~EDGE_ABNORMAL;
3070 /* See if this edge is one we should keep. */
3071 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3072 /* A conditional jump can fall through into the next
3073 block, so we should keep the edge. */
3075 ei_next (&ei);
3076 continue;
3078 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3079 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3080 /* If the destination block is the target of the jump,
3081 keep the edge. */
3083 ei_next (&ei);
3084 continue;
3086 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3087 && returnjump_p (insn))
3088 /* If the destination block is the exit block, and this
3089 instruction is a return, then keep the edge. */
3091 ei_next (&ei);
3092 continue;
3094 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3095 /* Keep the edges that correspond to exceptions thrown by
3096 this instruction and rematerialize the EDGE_ABNORMAL
3097 flag we just cleared above. */
3099 e->flags |= EDGE_ABNORMAL;
3100 ei_next (&ei);
3101 continue;
3104 /* We do not need this edge. */
3105 df_set_bb_dirty (bb);
3106 purged = true;
3107 remove_edge (e);
3110 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3111 return purged;
3113 if (dump_file)
3114 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3116 if (!optimize)
3117 return purged;
3119 /* Redistribute probabilities. */
3120 if (single_succ_p (bb))
3122 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3123 single_succ_edge (bb)->count = bb->count;
3125 else
3127 note = find_reg_note (insn, REG_BR_PROB, NULL);
3128 if (!note)
3129 return purged;
3131 b = BRANCH_EDGE (bb);
3132 f = FALLTHRU_EDGE (bb);
3133 b->probability = XINT (note, 0);
3134 f->probability = REG_BR_PROB_BASE - b->probability;
3135 /* Update these to use GCOV_COMPUTE_SCALE. */
3136 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
3137 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
3140 return purged;
3142 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3144 /* First, there should not be any EH or ABCALL edges resulting
3145 from non-local gotos and the like. If there were, we shouldn't
3146 have created the sibcall in the first place. Second, there
3147 should of course never have been a fallthru edge. */
3148 gcc_assert (single_succ_p (bb));
3149 gcc_assert (single_succ_edge (bb)->flags
3150 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3152 return 0;
3155 /* If we don't see a jump insn, we don't know exactly why the block would
3156 have been broken at this point. Look for a simple, non-fallthru edge,
3157 as these are only created by conditional branches. If we find such an
3158 edge we know that there used to be a jump here and can then safely
3159 remove all non-fallthru edges. */
3160 found = false;
3161 FOR_EACH_EDGE (e, ei, bb->succs)
3162 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3164 found = true;
3165 break;
3168 if (!found)
3169 return purged;
3171 /* Remove all but the fake and fallthru edges. The fake edge may be
3172 the only successor for this block in the case of noreturn
3173 calls. */
3174 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3176 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3178 df_set_bb_dirty (bb);
3179 remove_edge (e);
3180 purged = true;
3182 else
3183 ei_next (&ei);
3186 gcc_assert (single_succ_p (bb));
3188 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3189 single_succ_edge (bb)->count = bb->count;
3191 if (dump_file)
3192 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3193 bb->index);
3194 return purged;
3197 /* Search all basic blocks for potentially dead edges and purge them. Return
3198 true if some edge has been eliminated. */
3200 bool
3201 purge_all_dead_edges (void)
3203 int purged = false;
3204 basic_block bb;
3206 FOR_EACH_BB_FN (bb, cfun)
3208 bool purged_here = purge_dead_edges (bb);
3210 purged |= purged_here;
3213 return purged;
3216 /* This is used by a few passes that emit some instructions after abnormal
3217 calls, moving the basic block's end, while they in fact do want to emit
3218 them on the fallthru edge. Look for abnormal call edges, find backward
3219 the call in the block and insert the instructions on the edge instead.
3221 Similarly, handle instructions throwing exceptions internally.
3223 Return true when instructions have been found and inserted on edges. */
3225 bool
3226 fixup_abnormal_edges (void)
3228 bool inserted = false;
3229 basic_block bb;
3231 FOR_EACH_BB_FN (bb, cfun)
3233 edge e;
3234 edge_iterator ei;
3236 /* Look for cases we are interested in - calls or instructions causing
3237 exceptions. */
3238 FOR_EACH_EDGE (e, ei, bb->succs)
3239 if ((e->flags & EDGE_ABNORMAL_CALL)
3240 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3241 == (EDGE_ABNORMAL | EDGE_EH)))
3242 break;
3244 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3246 rtx_insn *insn;
3248 /* Get past the new insns generated. Allow notes, as the insns
3249 may be already deleted. */
3250 insn = BB_END (bb);
3251 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3252 && !can_throw_internal (insn)
3253 && insn != BB_HEAD (bb))
3254 insn = PREV_INSN (insn);
3256 if (CALL_P (insn) || can_throw_internal (insn))
3258 rtx_insn *stop, *next;
3260 e = find_fallthru_edge (bb->succs);
3262 stop = NEXT_INSN (BB_END (bb));
3263 BB_END (bb) = insn;
3265 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3267 next = NEXT_INSN (insn);
3268 if (INSN_P (insn))
3270 delete_insn (insn);
3272 /* Sometimes there's still the return value USE.
3273 If it's placed after a trapping call (i.e. that
3274 call is the last insn anyway), we have no fallthru
3275 edge. Simply delete this use and don't try to insert
3276 on the non-existent edge. */
3277 if (GET_CODE (PATTERN (insn)) != USE)
3279 /* We're not deleting it, we're moving it. */
3280 INSN_DELETED_P (insn) = 0;
3281 SET_PREV_INSN (insn) = NULL_RTX;
3282 SET_NEXT_INSN (insn) = NULL_RTX;
3284 insert_insn_on_edge (insn, e);
3285 inserted = true;
3288 else if (!BARRIER_P (insn))
3289 set_block_for_insn (insn, NULL);
3293 /* It may be that we don't find any trapping insn. In this
3294 case we discovered quite late that the insn that had been
3295 marked as can_throw_internal in fact couldn't trap at all.
3296 So we should in fact delete the EH edges out of the block. */
3297 else
3298 purge_dead_edges (bb);
3302 return inserted;
3305 /* Cut the insns from FIRST to LAST out of the insns stream. */
3307 rtx_insn *
3308 unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3310 rtx_insn *prevfirst = PREV_INSN (first);
3311 rtx_insn *nextlast = NEXT_INSN (last);
3313 SET_PREV_INSN (first) = NULL;
3314 SET_NEXT_INSN (last) = NULL;
3315 if (prevfirst)
3316 SET_NEXT_INSN (prevfirst) = nextlast;
3317 if (nextlast)
3318 SET_PREV_INSN (nextlast) = prevfirst;
3319 else
3320 set_last_insn (prevfirst);
3321 if (!prevfirst)
3322 set_first_insn (nextlast);
3323 return first;
3326 /* Skip over inter-block insns occurring after BB which are typically
3327 associated with BB (e.g., barriers). If there are any such insns,
3328 we return the last one. Otherwise, we return the end of BB. */
3330 static rtx_insn *
3331 skip_insns_after_block (basic_block bb)
3333 rtx_insn *insn, *last_insn, *next_head, *prev;
3335 next_head = NULL;
3336 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3337 next_head = BB_HEAD (bb->next_bb);
3339 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3341 if (insn == next_head)
3342 break;
3344 switch (GET_CODE (insn))
3346 case BARRIER:
3347 last_insn = insn;
3348 continue;
3350 case NOTE:
3351 switch (NOTE_KIND (insn))
3353 case NOTE_INSN_BLOCK_END:
3354 gcc_unreachable ();
3355 continue;
3356 default:
3357 continue;
3358 break;
3360 break;
3362 case CODE_LABEL:
3363 if (NEXT_INSN (insn)
3364 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3366 insn = NEXT_INSN (insn);
3367 last_insn = insn;
3368 continue;
3370 break;
3372 default:
3373 break;
3376 break;
3379 /* It is possible to hit contradictory sequence. For instance:
3381 jump_insn
3382 NOTE_INSN_BLOCK_BEG
3383 barrier
3385 Where barrier belongs to jump_insn, but the note does not. This can be
3386 created by removing the basic block originally following
3387 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3389 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3391 prev = PREV_INSN (insn);
3392 if (NOTE_P (insn))
3393 switch (NOTE_KIND (insn))
3395 case NOTE_INSN_BLOCK_END:
3396 gcc_unreachable ();
3397 break;
3398 case NOTE_INSN_DELETED:
3399 case NOTE_INSN_DELETED_LABEL:
3400 case NOTE_INSN_DELETED_DEBUG_LABEL:
3401 continue;
3402 default:
3403 reorder_insns (insn, insn, last_insn);
3407 return last_insn;
3410 /* Locate or create a label for a given basic block. */
3412 static rtx
3413 label_for_bb (basic_block bb)
3415 rtx label = BB_HEAD (bb);
3417 if (!LABEL_P (label))
3419 if (dump_file)
3420 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3422 label = block_label (bb);
3425 return label;
3428 /* Locate the effective beginning and end of the insn chain for each
3429 block, as defined by skip_insns_after_block above. */
3431 static void
3432 record_effective_endpoints (void)
3434 rtx_insn *next_insn;
3435 basic_block bb;
3436 rtx_insn *insn;
3438 for (insn = get_insns ();
3439 insn
3440 && NOTE_P (insn)
3441 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3442 insn = NEXT_INSN (insn))
3443 continue;
3444 /* No basic blocks at all? */
3445 gcc_assert (insn);
3447 if (PREV_INSN (insn))
3448 cfg_layout_function_header =
3449 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3450 else
3451 cfg_layout_function_header = NULL;
3453 next_insn = get_insns ();
3454 FOR_EACH_BB_FN (bb, cfun)
3456 rtx_insn *end;
3458 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3459 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3460 PREV_INSN (BB_HEAD (bb)));
3461 end = skip_insns_after_block (bb);
3462 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3463 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3464 next_insn = NEXT_INSN (BB_END (bb));
3467 cfg_layout_function_footer = next_insn;
3468 if (cfg_layout_function_footer)
3469 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3472 namespace {
3474 const pass_data pass_data_into_cfg_layout_mode =
3476 RTL_PASS, /* type */
3477 "into_cfglayout", /* name */
3478 OPTGROUP_NONE, /* optinfo_flags */
3479 TV_CFG, /* tv_id */
3480 0, /* properties_required */
3481 PROP_cfglayout, /* properties_provided */
3482 0, /* properties_destroyed */
3483 0, /* todo_flags_start */
3484 0, /* todo_flags_finish */
3487 class pass_into_cfg_layout_mode : public rtl_opt_pass
3489 public:
3490 pass_into_cfg_layout_mode (gcc::context *ctxt)
3491 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3494 /* opt_pass methods: */
3495 virtual unsigned int execute (function *)
3497 cfg_layout_initialize (0);
3498 return 0;
3501 }; // class pass_into_cfg_layout_mode
3503 } // anon namespace
3505 rtl_opt_pass *
3506 make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3508 return new pass_into_cfg_layout_mode (ctxt);
3511 namespace {
3513 const pass_data pass_data_outof_cfg_layout_mode =
3515 RTL_PASS, /* type */
3516 "outof_cfglayout", /* name */
3517 OPTGROUP_NONE, /* optinfo_flags */
3518 TV_CFG, /* tv_id */
3519 0, /* properties_required */
3520 0, /* properties_provided */
3521 PROP_cfglayout, /* properties_destroyed */
3522 0, /* todo_flags_start */
3523 0, /* todo_flags_finish */
3526 class pass_outof_cfg_layout_mode : public rtl_opt_pass
3528 public:
3529 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3530 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3533 /* opt_pass methods: */
3534 virtual unsigned int execute (function *);
3536 }; // class pass_outof_cfg_layout_mode
3538 unsigned int
3539 pass_outof_cfg_layout_mode::execute (function *fun)
3541 basic_block bb;
3543 FOR_EACH_BB_FN (bb, fun)
3544 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3545 bb->aux = bb->next_bb;
3547 cfg_layout_finalize ();
3549 return 0;
3552 } // anon namespace
3554 rtl_opt_pass *
3555 make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3557 return new pass_outof_cfg_layout_mode (ctxt);
3561 /* Link the basic blocks in the correct order, compacting the basic
3562 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3563 function also clears the basic block header and footer fields.
3565 This function is usually called after a pass (e.g. tracer) finishes
3566 some transformations while in cfglayout mode. The required sequence
3567 of the basic blocks is in a linked list along the bb->aux field.
3568 This functions re-links the basic block prev_bb and next_bb pointers
3569 accordingly, and it compacts and renumbers the blocks.
3571 FIXME: This currently works only for RTL, but the only RTL-specific
3572 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3573 to GIMPLE a long time ago, but it doesn't relink the basic block
3574 chain. It could do that (to give better initial RTL) if this function
3575 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3577 void
3578 relink_block_chain (bool stay_in_cfglayout_mode)
3580 basic_block bb, prev_bb;
3581 int index;
3583 /* Maybe dump the re-ordered sequence. */
3584 if (dump_file)
3586 fprintf (dump_file, "Reordered sequence:\n");
3587 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3588 NUM_FIXED_BLOCKS;
3590 bb = (basic_block) bb->aux, index++)
3592 fprintf (dump_file, " %i ", index);
3593 if (get_bb_original (bb))
3594 fprintf (dump_file, "duplicate of %i ",
3595 get_bb_original (bb)->index);
3596 else if (forwarder_block_p (bb)
3597 && !LABEL_P (BB_HEAD (bb)))
3598 fprintf (dump_file, "compensation ");
3599 else
3600 fprintf (dump_file, "bb %i ", bb->index);
3601 fprintf (dump_file, " [%i]\n", bb->frequency);
3605 /* Now reorder the blocks. */
3606 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3607 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3608 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3610 bb->prev_bb = prev_bb;
3611 prev_bb->next_bb = bb;
3613 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3614 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3616 /* Then, clean up the aux fields. */
3617 FOR_ALL_BB_FN (bb, cfun)
3619 bb->aux = NULL;
3620 if (!stay_in_cfglayout_mode)
3621 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3624 /* Maybe reset the original copy tables, they are not valid anymore
3625 when we renumber the basic blocks in compact_blocks. If we are
3626 are going out of cfglayout mode, don't re-allocate the tables. */
3627 free_original_copy_tables ();
3628 if (stay_in_cfglayout_mode)
3629 initialize_original_copy_tables ();
3631 /* Finally, put basic_block_info in the new order. */
3632 compact_blocks ();
3636 /* Given a reorder chain, rearrange the code to match. */
3638 static void
3639 fixup_reorder_chain (void)
3641 basic_block bb;
3642 rtx_insn *insn = NULL;
3644 if (cfg_layout_function_header)
3646 set_first_insn (cfg_layout_function_header);
3647 insn = cfg_layout_function_header;
3648 while (NEXT_INSN (insn))
3649 insn = NEXT_INSN (insn);
3652 /* First do the bulk reordering -- rechain the blocks without regard to
3653 the needed changes to jumps and labels. */
3655 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3656 bb->aux)
3658 if (BB_HEADER (bb))
3660 if (insn)
3661 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3662 else
3663 set_first_insn (BB_HEADER (bb));
3664 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3665 insn = BB_HEADER (bb);
3666 while (NEXT_INSN (insn))
3667 insn = NEXT_INSN (insn);
3669 if (insn)
3670 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3671 else
3672 set_first_insn (BB_HEAD (bb));
3673 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3674 insn = BB_END (bb);
3675 if (BB_FOOTER (bb))
3677 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3678 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3679 while (NEXT_INSN (insn))
3680 insn = NEXT_INSN (insn);
3684 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3685 if (cfg_layout_function_footer)
3686 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3688 while (NEXT_INSN (insn))
3689 insn = NEXT_INSN (insn);
3691 set_last_insn (insn);
3692 #ifdef ENABLE_CHECKING
3693 verify_insn_chain ();
3694 #endif
3696 /* Now add jumps and labels as needed to match the blocks new
3697 outgoing edges. */
3699 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3700 bb->aux)
3702 edge e_fall, e_taken, e;
3703 rtx_insn *bb_end_insn;
3704 rtx ret_label = NULL_RTX;
3705 basic_block nb;
3706 edge_iterator ei;
3708 if (EDGE_COUNT (bb->succs) == 0)
3709 continue;
3711 /* Find the old fallthru edge, and another non-EH edge for
3712 a taken jump. */
3713 e_taken = e_fall = NULL;
3715 FOR_EACH_EDGE (e, ei, bb->succs)
3716 if (e->flags & EDGE_FALLTHRU)
3717 e_fall = e;
3718 else if (! (e->flags & EDGE_EH))
3719 e_taken = e;
3721 bb_end_insn = BB_END (bb);
3722 if (JUMP_P (bb_end_insn))
3724 ret_label = JUMP_LABEL (bb_end_insn);
3725 if (any_condjump_p (bb_end_insn))
3727 /* This might happen if the conditional jump has side
3728 effects and could therefore not be optimized away.
3729 Make the basic block to end with a barrier in order
3730 to prevent rtl_verify_flow_info from complaining. */
3731 if (!e_fall)
3733 gcc_assert (!onlyjump_p (bb_end_insn)
3734 || returnjump_p (bb_end_insn)
3735 || (e_taken->flags & EDGE_CROSSING));
3736 emit_barrier_after (bb_end_insn);
3737 continue;
3740 /* If the old fallthru is still next, nothing to do. */
3741 if (bb->aux == e_fall->dest
3742 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3743 continue;
3745 /* The degenerated case of conditional jump jumping to the next
3746 instruction can happen for jumps with side effects. We need
3747 to construct a forwarder block and this will be done just
3748 fine by force_nonfallthru below. */
3749 if (!e_taken)
3752 /* There is another special case: if *neither* block is next,
3753 such as happens at the very end of a function, then we'll
3754 need to add a new unconditional jump. Choose the taken
3755 edge based on known or assumed probability. */
3756 else if (bb->aux != e_taken->dest)
3758 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
3760 if (note
3761 && XINT (note, 0) < REG_BR_PROB_BASE / 2
3762 && invert_jump (bb_end_insn,
3763 (e_fall->dest
3764 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3765 ? NULL_RTX
3766 : label_for_bb (e_fall->dest)), 0))
3768 e_fall->flags &= ~EDGE_FALLTHRU;
3769 gcc_checking_assert (could_fall_through
3770 (e_taken->src, e_taken->dest));
3771 e_taken->flags |= EDGE_FALLTHRU;
3772 update_br_prob_note (bb);
3773 e = e_fall, e_fall = e_taken, e_taken = e;
3777 /* If the "jumping" edge is a crossing edge, and the fall
3778 through edge is non-crossing, leave things as they are. */
3779 else if ((e_taken->flags & EDGE_CROSSING)
3780 && !(e_fall->flags & EDGE_CROSSING))
3781 continue;
3783 /* Otherwise we can try to invert the jump. This will
3784 basically never fail, however, keep up the pretense. */
3785 else if (invert_jump (bb_end_insn,
3786 (e_fall->dest
3787 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3788 ? NULL_RTX
3789 : label_for_bb (e_fall->dest)), 0))
3791 e_fall->flags &= ~EDGE_FALLTHRU;
3792 gcc_checking_assert (could_fall_through
3793 (e_taken->src, e_taken->dest));
3794 e_taken->flags |= EDGE_FALLTHRU;
3795 update_br_prob_note (bb);
3796 if (LABEL_NUSES (ret_label) == 0
3797 && single_pred_p (e_taken->dest))
3798 delete_insn (ret_label);
3799 continue;
3802 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
3804 /* If the old fallthru is still next or if
3805 asm goto doesn't have a fallthru (e.g. when followed by
3806 __builtin_unreachable ()), nothing to do. */
3807 if (! e_fall
3808 || bb->aux == e_fall->dest
3809 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3810 continue;
3812 /* Otherwise we'll have to use the fallthru fixup below. */
3814 else
3816 /* Otherwise we have some return, switch or computed
3817 jump. In the 99% case, there should not have been a
3818 fallthru edge. */
3819 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
3820 continue;
3823 else
3825 /* No fallthru implies a noreturn function with EH edges, or
3826 something similarly bizarre. In any case, we don't need to
3827 do anything. */
3828 if (! e_fall)
3829 continue;
3831 /* If the fallthru block is still next, nothing to do. */
3832 if (bb->aux == e_fall->dest)
3833 continue;
3835 /* A fallthru to exit block. */
3836 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3837 continue;
3840 /* We got here if we need to add a new jump insn.
3841 Note force_nonfallthru can delete E_FALL and thus we have to
3842 save E_FALL->src prior to the call to force_nonfallthru. */
3843 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
3844 if (nb)
3846 nb->aux = bb->aux;
3847 bb->aux = nb;
3848 /* Don't process this new block. */
3849 bb = nb;
3853 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3855 /* Annoying special case - jump around dead jumptables left in the code. */
3856 FOR_EACH_BB_FN (bb, cfun)
3858 edge e = find_fallthru_edge (bb->succs);
3860 if (e && !can_fallthru (e->src, e->dest))
3861 force_nonfallthru (e);
3864 /* Ensure goto_locus from edges has some instructions with that locus
3865 in RTL. */
3866 if (!optimize)
3867 FOR_EACH_BB_FN (bb, cfun)
3869 edge e;
3870 edge_iterator ei;
3872 FOR_EACH_EDGE (e, ei, bb->succs)
3873 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
3874 && !(e->flags & EDGE_ABNORMAL))
3876 edge e2;
3877 edge_iterator ei2;
3878 basic_block dest, nb;
3879 rtx_insn *end;
3881 insn = BB_END (e->src);
3882 end = PREV_INSN (BB_HEAD (e->src));
3883 while (insn != end
3884 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
3885 insn = PREV_INSN (insn);
3886 if (insn != end
3887 && INSN_LOCATION (insn) == e->goto_locus)
3888 continue;
3889 if (simplejump_p (BB_END (e->src))
3890 && !INSN_HAS_LOCATION (BB_END (e->src)))
3892 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
3893 continue;
3895 dest = e->dest;
3896 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3898 /* Non-fallthru edges to the exit block cannot be split. */
3899 if (!(e->flags & EDGE_FALLTHRU))
3900 continue;
3902 else
3904 insn = BB_HEAD (dest);
3905 end = NEXT_INSN (BB_END (dest));
3906 while (insn != end && !NONDEBUG_INSN_P (insn))
3907 insn = NEXT_INSN (insn);
3908 if (insn != end && INSN_HAS_LOCATION (insn)
3909 && INSN_LOCATION (insn) == e->goto_locus)
3910 continue;
3912 nb = split_edge (e);
3913 if (!INSN_P (BB_END (nb)))
3914 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
3915 nb);
3916 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
3918 /* If there are other incoming edges to the destination block
3919 with the same goto locus, redirect them to the new block as
3920 well, this can prevent other such blocks from being created
3921 in subsequent iterations of the loop. */
3922 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
3923 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
3924 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
3925 && e->goto_locus == e2->goto_locus)
3926 redirect_edge_and_branch (e2, nb);
3927 else
3928 ei_next (&ei2);
3933 /* Perform sanity checks on the insn chain.
3934 1. Check that next/prev pointers are consistent in both the forward and
3935 reverse direction.
3936 2. Count insns in chain, going both directions, and check if equal.
3937 3. Check that get_last_insn () returns the actual end of chain. */
3939 DEBUG_FUNCTION void
3940 verify_insn_chain (void)
3942 rtx_insn *x, *prevx, *nextx;
3943 int insn_cnt1, insn_cnt2;
3945 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
3946 x != 0;
3947 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
3948 gcc_assert (PREV_INSN (x) == prevx);
3950 gcc_assert (prevx == get_last_insn ());
3952 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
3953 x != 0;
3954 nextx = x, insn_cnt2++, x = PREV_INSN (x))
3955 gcc_assert (NEXT_INSN (x) == nextx);
3957 gcc_assert (insn_cnt1 == insn_cnt2);
3960 /* If we have assembler epilogues, the block falling through to exit must
3961 be the last one in the reordered chain when we reach final. Ensure
3962 that this condition is met. */
3963 static void
3964 fixup_fallthru_exit_predecessor (void)
3966 edge e;
3967 basic_block bb = NULL;
3969 /* This transformation is not valid before reload, because we might
3970 separate a call from the instruction that copies the return
3971 value. */
3972 gcc_assert (reload_completed);
3974 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
3975 if (e)
3976 bb = e->src;
3978 if (bb && bb->aux)
3980 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3982 /* If the very first block is the one with the fall-through exit
3983 edge, we have to split that block. */
3984 if (c == bb)
3986 bb = split_block (bb, NULL)->dest;
3987 bb->aux = c->aux;
3988 c->aux = bb;
3989 BB_FOOTER (bb) = BB_FOOTER (c);
3990 BB_FOOTER (c) = NULL;
3993 while (c->aux != bb)
3994 c = (basic_block) c->aux;
3996 c->aux = bb->aux;
3997 while (c->aux)
3998 c = (basic_block) c->aux;
4000 c->aux = bb;
4001 bb->aux = NULL;
4005 /* In case there are more than one fallthru predecessors of exit, force that
4006 there is only one. */
4008 static void
4009 force_one_exit_fallthru (void)
4011 edge e, predecessor = NULL;
4012 bool more = false;
4013 edge_iterator ei;
4014 basic_block forwarder, bb;
4016 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4017 if (e->flags & EDGE_FALLTHRU)
4019 if (predecessor == NULL)
4020 predecessor = e;
4021 else
4023 more = true;
4024 break;
4028 if (!more)
4029 return;
4031 /* Exit has several fallthru predecessors. Create a forwarder block for
4032 them. */
4033 forwarder = split_edge (predecessor);
4034 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4035 (e = ei_safe_edge (ei)); )
4037 if (e->src == forwarder
4038 || !(e->flags & EDGE_FALLTHRU))
4039 ei_next (&ei);
4040 else
4041 redirect_edge_and_branch_force (e, forwarder);
4044 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4045 exit block. */
4046 FOR_EACH_BB_FN (bb, cfun)
4048 if (bb->aux == NULL && bb != forwarder)
4050 bb->aux = forwarder;
4051 break;
4056 /* Return true in case it is possible to duplicate the basic block BB. */
4058 static bool
4059 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4061 /* Do not attempt to duplicate tablejumps, as we need to unshare
4062 the dispatch table. This is difficult to do, as the instructions
4063 computing jump destination may be hoisted outside the basic block. */
4064 if (tablejump_p (BB_END (bb), NULL, NULL))
4065 return false;
4067 /* Do not duplicate blocks containing insns that can't be copied. */
4068 if (targetm.cannot_copy_insn_p)
4070 rtx_insn *insn = BB_HEAD (bb);
4071 while (1)
4073 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4074 return false;
4075 if (insn == BB_END (bb))
4076 break;
4077 insn = NEXT_INSN (insn);
4081 return true;
4084 rtx_insn *
4085 duplicate_insn_chain (rtx_insn *from, rtx_insn *to)
4087 rtx_insn *insn, *next, *copy;
4088 rtx_note *last;
4090 /* Avoid updating of boundaries of previous basic block. The
4091 note will get removed from insn stream in fixup. */
4092 last = emit_note (NOTE_INSN_DELETED);
4094 /* Create copy at the end of INSN chain. The chain will
4095 be reordered later. */
4096 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4098 switch (GET_CODE (insn))
4100 case DEBUG_INSN:
4101 /* Don't duplicate label debug insns. */
4102 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4103 break;
4104 /* FALLTHRU */
4105 case INSN:
4106 case CALL_INSN:
4107 case JUMP_INSN:
4108 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4109 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4110 && ANY_RETURN_P (JUMP_LABEL (insn)))
4111 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4112 maybe_copy_prologue_epilogue_insn (insn, copy);
4113 break;
4115 case JUMP_TABLE_DATA:
4116 /* Avoid copying of dispatch tables. We never duplicate
4117 tablejumps, so this can hit only in case the table got
4118 moved far from original jump.
4119 Avoid copying following barrier as well if any
4120 (and debug insns in between). */
4121 for (next = NEXT_INSN (insn);
4122 next != NEXT_INSN (to);
4123 next = NEXT_INSN (next))
4124 if (!DEBUG_INSN_P (next))
4125 break;
4126 if (next != NEXT_INSN (to) && BARRIER_P (next))
4127 insn = next;
4128 break;
4130 case CODE_LABEL:
4131 break;
4133 case BARRIER:
4134 emit_barrier ();
4135 break;
4137 case NOTE:
4138 switch (NOTE_KIND (insn))
4140 /* In case prologue is empty and function contain label
4141 in first BB, we may want to copy the block. */
4142 case NOTE_INSN_PROLOGUE_END:
4144 case NOTE_INSN_DELETED:
4145 case NOTE_INSN_DELETED_LABEL:
4146 case NOTE_INSN_DELETED_DEBUG_LABEL:
4147 /* No problem to strip these. */
4148 case NOTE_INSN_FUNCTION_BEG:
4149 /* There is always just single entry to function. */
4150 case NOTE_INSN_BASIC_BLOCK:
4151 /* We should only switch text sections once. */
4152 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4153 break;
4155 case NOTE_INSN_EPILOGUE_BEG:
4156 emit_note_copy (as_a <rtx_note *> (insn));
4157 break;
4159 default:
4160 /* All other notes should have already been eliminated. */
4161 gcc_unreachable ();
4163 break;
4164 default:
4165 gcc_unreachable ();
4168 insn = NEXT_INSN (last);
4169 delete_insn (last);
4170 return insn;
4173 /* Create a duplicate of the basic block BB. */
4175 static basic_block
4176 cfg_layout_duplicate_bb (basic_block bb)
4178 rtx_insn *insn;
4179 basic_block new_bb;
4181 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
4182 new_bb = create_basic_block (insn,
4183 insn ? get_last_insn () : NULL,
4184 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4186 BB_COPY_PARTITION (new_bb, bb);
4187 if (BB_HEADER (bb))
4189 insn = BB_HEADER (bb);
4190 while (NEXT_INSN (insn))
4191 insn = NEXT_INSN (insn);
4192 insn = duplicate_insn_chain (BB_HEADER (bb), insn);
4193 if (insn)
4194 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4197 if (BB_FOOTER (bb))
4199 insn = BB_FOOTER (bb);
4200 while (NEXT_INSN (insn))
4201 insn = NEXT_INSN (insn);
4202 insn = duplicate_insn_chain (BB_FOOTER (bb), insn);
4203 if (insn)
4204 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4207 return new_bb;
4211 /* Main entry point to this module - initialize the datastructures for
4212 CFG layout changes. It keeps LOOPS up-to-date if not null.
4214 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4216 void
4217 cfg_layout_initialize (unsigned int flags)
4219 rtx_expr_list *x;
4220 basic_block bb;
4222 /* Once bb partitioning is complete, cfg layout mode should not be
4223 re-entered. Entering cfg layout mode may require fixups. As an
4224 example, if edge forwarding performed when optimizing the cfg
4225 layout required moving a block from the hot to the cold
4226 section. This would create an illegal partitioning unless some
4227 manual fixup was performed. */
4228 gcc_assert (!(crtl->bb_reorder_complete
4229 && flag_reorder_blocks_and_partition));
4231 initialize_original_copy_tables ();
4233 cfg_layout_rtl_register_cfg_hooks ();
4235 record_effective_endpoints ();
4237 /* Make sure that the targets of non local gotos are marked. */
4238 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4240 bb = BLOCK_FOR_INSN (x->element ());
4241 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4244 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4247 /* Splits superblocks. */
4248 void
4249 break_superblocks (void)
4251 sbitmap superblocks;
4252 bool need = false;
4253 basic_block bb;
4255 superblocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
4256 bitmap_clear (superblocks);
4258 FOR_EACH_BB_FN (bb, cfun)
4259 if (bb->flags & BB_SUPERBLOCK)
4261 bb->flags &= ~BB_SUPERBLOCK;
4262 bitmap_set_bit (superblocks, bb->index);
4263 need = true;
4266 if (need)
4268 rebuild_jump_labels (get_insns ());
4269 find_many_sub_basic_blocks (superblocks);
4272 free (superblocks);
4275 /* Finalize the changes: reorder insn list according to the sequence specified
4276 by aux pointers, enter compensation code, rebuild scope forest. */
4278 void
4279 cfg_layout_finalize (void)
4281 #ifdef ENABLE_CHECKING
4282 verify_flow_info ();
4283 #endif
4284 force_one_exit_fallthru ();
4285 rtl_register_cfg_hooks ();
4286 if (reload_completed
4287 #ifdef HAVE_epilogue
4288 && !HAVE_epilogue
4289 #endif
4291 fixup_fallthru_exit_predecessor ();
4292 fixup_reorder_chain ();
4294 rebuild_jump_labels (get_insns ());
4295 delete_dead_jumptables ();
4297 #ifdef ENABLE_CHECKING
4298 verify_insn_chain ();
4299 verify_flow_info ();
4300 #endif
4304 /* Same as split_block but update cfg_layout structures. */
4306 static basic_block
4307 cfg_layout_split_block (basic_block bb, void *insnp)
4309 rtx insn = (rtx) insnp;
4310 basic_block new_bb = rtl_split_block (bb, insn);
4312 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4313 BB_FOOTER (bb) = NULL;
4315 return new_bb;
4318 /* Redirect Edge to DEST. */
4319 static edge
4320 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4322 basic_block src = e->src;
4323 edge ret;
4325 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4326 return NULL;
4328 if (e->dest == dest)
4329 return e;
4331 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4332 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4334 df_set_bb_dirty (src);
4335 return ret;
4338 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4339 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4341 if (dump_file)
4342 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4343 e->src->index, dest->index);
4345 df_set_bb_dirty (e->src);
4346 redirect_edge_succ (e, dest);
4347 return e;
4350 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4351 in the case the basic block appears to be in sequence. Avoid this
4352 transformation. */
4354 if (e->flags & EDGE_FALLTHRU)
4356 /* Redirect any branch edges unified with the fallthru one. */
4357 if (JUMP_P (BB_END (src))
4358 && label_is_jump_target_p (BB_HEAD (e->dest),
4359 BB_END (src)))
4361 edge redirected;
4363 if (dump_file)
4364 fprintf (dump_file, "Fallthru edge unified with branch "
4365 "%i->%i redirected to %i\n",
4366 e->src->index, e->dest->index, dest->index);
4367 e->flags &= ~EDGE_FALLTHRU;
4368 redirected = redirect_branch_edge (e, dest);
4369 gcc_assert (redirected);
4370 redirected->flags |= EDGE_FALLTHRU;
4371 df_set_bb_dirty (redirected->src);
4372 return redirected;
4374 /* In case we are redirecting fallthru edge to the branch edge
4375 of conditional jump, remove it. */
4376 if (EDGE_COUNT (src->succs) == 2)
4378 /* Find the edge that is different from E. */
4379 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4381 if (s->dest == dest
4382 && any_condjump_p (BB_END (src))
4383 && onlyjump_p (BB_END (src)))
4384 delete_insn (BB_END (src));
4386 if (dump_file)
4387 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4388 e->src->index, e->dest->index, dest->index);
4389 ret = redirect_edge_succ_nodup (e, dest);
4391 else
4392 ret = redirect_branch_edge (e, dest);
4394 /* We don't want simplejumps in the insn stream during cfglayout. */
4395 gcc_assert (!simplejump_p (BB_END (src)));
4397 df_set_bb_dirty (src);
4398 return ret;
4401 /* Simple wrapper as we always can redirect fallthru edges. */
4402 static basic_block
4403 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4405 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4407 gcc_assert (redirected);
4408 return NULL;
4411 /* Same as delete_basic_block but update cfg_layout structures. */
4413 static void
4414 cfg_layout_delete_block (basic_block bb)
4416 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4417 rtx_insn **to;
4419 if (BB_HEADER (bb))
4421 next = BB_HEAD (bb);
4422 if (prev)
4423 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4424 else
4425 set_first_insn (BB_HEADER (bb));
4426 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4427 insn = BB_HEADER (bb);
4428 while (NEXT_INSN (insn))
4429 insn = NEXT_INSN (insn);
4430 SET_NEXT_INSN (insn) = next;
4431 SET_PREV_INSN (next) = insn;
4433 next = NEXT_INSN (BB_END (bb));
4434 if (BB_FOOTER (bb))
4436 insn = BB_FOOTER (bb);
4437 while (insn)
4439 if (BARRIER_P (insn))
4441 if (PREV_INSN (insn))
4442 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4443 else
4444 BB_FOOTER (bb) = NEXT_INSN (insn);
4445 if (NEXT_INSN (insn))
4446 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4448 if (LABEL_P (insn))
4449 break;
4450 insn = NEXT_INSN (insn);
4452 if (BB_FOOTER (bb))
4454 insn = BB_END (bb);
4455 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4456 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4457 while (NEXT_INSN (insn))
4458 insn = NEXT_INSN (insn);
4459 SET_NEXT_INSN (insn) = next;
4460 if (next)
4461 SET_PREV_INSN (next) = insn;
4462 else
4463 set_last_insn (insn);
4466 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4467 to = &BB_HEADER (bb->next_bb);
4468 else
4469 to = &cfg_layout_function_footer;
4471 rtl_delete_block (bb);
4473 if (prev)
4474 prev = NEXT_INSN (prev);
4475 else
4476 prev = get_insns ();
4477 if (next)
4478 next = PREV_INSN (next);
4479 else
4480 next = get_last_insn ();
4482 if (next && NEXT_INSN (next) != prev)
4484 remaints = unlink_insn_chain (prev, next);
4485 insn = remaints;
4486 while (NEXT_INSN (insn))
4487 insn = NEXT_INSN (insn);
4488 SET_NEXT_INSN (insn) = *to;
4489 if (*to)
4490 SET_PREV_INSN (*to) = insn;
4491 *to = remaints;
4495 /* Return true when blocks A and B can be safely merged. */
4497 static bool
4498 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4500 /* If we are partitioning hot/cold basic blocks, we don't want to
4501 mess up unconditional or indirect jumps that cross between hot
4502 and cold sections.
4504 Basic block partitioning may result in some jumps that appear to
4505 be optimizable (or blocks that appear to be mergeable), but which really
4506 must be left untouched (they are required to make it safely across
4507 partition boundaries). See the comments at the top of
4508 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4510 if (BB_PARTITION (a) != BB_PARTITION (b))
4511 return false;
4513 /* Protect the loop latches. */
4514 if (current_loops && b->loop_father->latch == b)
4515 return false;
4517 /* If we would end up moving B's instructions, make sure it doesn't fall
4518 through into the exit block, since we cannot recover from a fallthrough
4519 edge into the exit block occurring in the middle of a function. */
4520 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4522 edge e = find_fallthru_edge (b->succs);
4523 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4524 return false;
4527 /* There must be exactly one edge in between the blocks. */
4528 return (single_succ_p (a)
4529 && single_succ (a) == b
4530 && single_pred_p (b) == 1
4531 && a != b
4532 /* Must be simple edge. */
4533 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4534 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4535 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4536 /* If the jump insn has side effects, we can't kill the edge.
4537 When not optimizing, try_redirect_by_replacing_jump will
4538 not allow us to redirect an edge by replacing a table jump. */
4539 && (!JUMP_P (BB_END (a))
4540 || ((!optimize || reload_completed)
4541 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4544 /* Merge block A and B. The blocks must be mergeable. */
4546 static void
4547 cfg_layout_merge_blocks (basic_block a, basic_block b)
4549 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
4550 rtx_insn *insn;
4552 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4554 if (dump_file)
4555 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4556 a->index);
4558 /* If there was a CODE_LABEL beginning B, delete it. */
4559 if (LABEL_P (BB_HEAD (b)))
4561 delete_insn (BB_HEAD (b));
4564 /* We should have fallthru edge in a, or we can do dummy redirection to get
4565 it cleaned up. */
4566 if (JUMP_P (BB_END (a)))
4567 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4568 gcc_assert (!JUMP_P (BB_END (a)));
4570 /* When not optimizing and the edge is the only place in RTL which holds
4571 some unique locus, emit a nop with that locus in between. */
4572 if (!optimize)
4573 emit_nop_for_unique_locus_between (a, b);
4575 /* Move things from b->footer after a->footer. */
4576 if (BB_FOOTER (b))
4578 if (!BB_FOOTER (a))
4579 BB_FOOTER (a) = BB_FOOTER (b);
4580 else
4582 rtx_insn *last = BB_FOOTER (a);
4584 while (NEXT_INSN (last))
4585 last = NEXT_INSN (last);
4586 SET_NEXT_INSN (last) = BB_FOOTER (b);
4587 SET_PREV_INSN (BB_FOOTER (b)) = last;
4589 BB_FOOTER (b) = NULL;
4592 /* Move things from b->header before a->footer.
4593 Note that this may include dead tablejump data, but we don't clean
4594 those up until we go out of cfglayout mode. */
4595 if (BB_HEADER (b))
4597 if (! BB_FOOTER (a))
4598 BB_FOOTER (a) = BB_HEADER (b);
4599 else
4601 rtx_insn *last = BB_HEADER (b);
4603 while (NEXT_INSN (last))
4604 last = NEXT_INSN (last);
4605 SET_NEXT_INSN (last) = BB_FOOTER (a);
4606 SET_PREV_INSN (BB_FOOTER (a)) = last;
4607 BB_FOOTER (a) = BB_HEADER (b);
4609 BB_HEADER (b) = NULL;
4612 /* In the case basic blocks are not adjacent, move them around. */
4613 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4615 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4617 emit_insn_after_noloc (insn, BB_END (a), a);
4619 /* Otherwise just re-associate the instructions. */
4620 else
4622 insn = BB_HEAD (b);
4623 BB_END (a) = BB_END (b);
4626 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4627 We need to explicitly call. */
4628 update_bb_for_insn_chain (insn, BB_END (b), a);
4630 /* Skip possible DELETED_LABEL insn. */
4631 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4632 insn = NEXT_INSN (insn);
4633 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4634 BB_HEAD (b) = BB_END (b) = NULL;
4635 delete_insn (insn);
4637 df_bb_delete (b->index);
4639 /* If B was a forwarder block, propagate the locus on the edge. */
4640 if (forwarder_p
4641 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
4642 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4644 if (dump_file)
4645 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4648 /* Split edge E. */
4650 static basic_block
4651 cfg_layout_split_edge (edge e)
4653 basic_block new_bb =
4654 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4655 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4656 NULL_RTX, e->src);
4658 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4659 BB_COPY_PARTITION (new_bb, e->src);
4660 else
4661 BB_COPY_PARTITION (new_bb, e->dest);
4662 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4663 redirect_edge_and_branch_force (e, new_bb);
4665 return new_bb;
4668 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4670 static void
4671 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4675 /* Return true if BB contains only labels or non-executable
4676 instructions. */
4678 static bool
4679 rtl_block_empty_p (basic_block bb)
4681 rtx_insn *insn;
4683 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4684 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4685 return true;
4687 FOR_BB_INSNS (bb, insn)
4688 if (NONDEBUG_INSN_P (insn) && !any_uncondjump_p (insn))
4689 return false;
4691 return true;
4694 /* Split a basic block if it ends with a conditional branch and if
4695 the other part of the block is not empty. */
4697 static basic_block
4698 rtl_split_block_before_cond_jump (basic_block bb)
4700 rtx_insn *insn;
4701 rtx_insn *split_point = NULL;
4702 rtx_insn *last = NULL;
4703 bool found_code = false;
4705 FOR_BB_INSNS (bb, insn)
4707 if (any_condjump_p (insn))
4708 split_point = last;
4709 else if (NONDEBUG_INSN_P (insn))
4710 found_code = true;
4711 last = insn;
4714 /* Did not find everything. */
4715 if (found_code && split_point)
4716 return split_block (bb, split_point)->dest;
4717 else
4718 return NULL;
4721 /* Return 1 if BB ends with a call, possibly followed by some
4722 instructions that must stay with the call, 0 otherwise. */
4724 static bool
4725 rtl_block_ends_with_call_p (basic_block bb)
4727 rtx_insn *insn = BB_END (bb);
4729 while (!CALL_P (insn)
4730 && insn != BB_HEAD (bb)
4731 && (keep_with_call_p (insn)
4732 || NOTE_P (insn)
4733 || DEBUG_INSN_P (insn)))
4734 insn = PREV_INSN (insn);
4735 return (CALL_P (insn));
4738 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4740 static bool
4741 rtl_block_ends_with_condjump_p (const_basic_block bb)
4743 return any_condjump_p (BB_END (bb));
4746 /* Return true if we need to add fake edge to exit.
4747 Helper function for rtl_flow_call_edges_add. */
4749 static bool
4750 need_fake_edge_p (const rtx_insn *insn)
4752 if (!INSN_P (insn))
4753 return false;
4755 if ((CALL_P (insn)
4756 && !SIBLING_CALL_P (insn)
4757 && !find_reg_note (insn, REG_NORETURN, NULL)
4758 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
4759 return true;
4761 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
4762 && MEM_VOLATILE_P (PATTERN (insn)))
4763 || (GET_CODE (PATTERN (insn)) == PARALLEL
4764 && asm_noperands (insn) != -1
4765 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
4766 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
4769 /* Add fake edges to the function exit for any non constant and non noreturn
4770 calls, volatile inline assembly in the bitmap of blocks specified by
4771 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4772 that were split.
4774 The goal is to expose cases in which entering a basic block does not imply
4775 that all subsequent instructions must be executed. */
4777 static int
4778 rtl_flow_call_edges_add (sbitmap blocks)
4780 int i;
4781 int blocks_split = 0;
4782 int last_bb = last_basic_block_for_fn (cfun);
4783 bool check_last_block = false;
4785 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
4786 return 0;
4788 if (! blocks)
4789 check_last_block = true;
4790 else
4791 check_last_block = bitmap_bit_p (blocks,
4792 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
4794 /* In the last basic block, before epilogue generation, there will be
4795 a fallthru edge to EXIT. Special care is required if the last insn
4796 of the last basic block is a call because make_edge folds duplicate
4797 edges, which would result in the fallthru edge also being marked
4798 fake, which would result in the fallthru edge being removed by
4799 remove_fake_edges, which would result in an invalid CFG.
4801 Moreover, we can't elide the outgoing fake edge, since the block
4802 profiler needs to take this into account in order to solve the minimal
4803 spanning tree in the case that the call doesn't return.
4805 Handle this by adding a dummy instruction in a new last basic block. */
4806 if (check_last_block)
4808 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
4809 rtx_insn *insn = BB_END (bb);
4811 /* Back up past insns that must be kept in the same block as a call. */
4812 while (insn != BB_HEAD (bb)
4813 && keep_with_call_p (insn))
4814 insn = PREV_INSN (insn);
4816 if (need_fake_edge_p (insn))
4818 edge e;
4820 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4821 if (e)
4823 insert_insn_on_edge (gen_use (const0_rtx), e);
4824 commit_edge_insertions ();
4829 /* Now add fake edges to the function exit for any non constant
4830 calls since there is no way that we can determine if they will
4831 return or not... */
4833 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
4835 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
4836 rtx_insn *insn;
4837 rtx_insn *prev_insn;
4839 if (!bb)
4840 continue;
4842 if (blocks && !bitmap_bit_p (blocks, i))
4843 continue;
4845 for (insn = BB_END (bb); ; insn = prev_insn)
4847 prev_insn = PREV_INSN (insn);
4848 if (need_fake_edge_p (insn))
4850 edge e;
4851 rtx_insn *split_at_insn = insn;
4853 /* Don't split the block between a call and an insn that should
4854 remain in the same block as the call. */
4855 if (CALL_P (insn))
4856 while (split_at_insn != BB_END (bb)
4857 && keep_with_call_p (NEXT_INSN (split_at_insn)))
4858 split_at_insn = NEXT_INSN (split_at_insn);
4860 /* The handling above of the final block before the epilogue
4861 should be enough to verify that there is no edge to the exit
4862 block in CFG already. Calling make_edge in such case would
4863 cause us to mark that edge as fake and remove it later. */
4865 #ifdef ENABLE_CHECKING
4866 if (split_at_insn == BB_END (bb))
4868 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4869 gcc_assert (e == NULL);
4871 #endif
4873 /* Note that the following may create a new basic block
4874 and renumber the existing basic blocks. */
4875 if (split_at_insn != BB_END (bb))
4877 e = split_block (bb, split_at_insn);
4878 if (e)
4879 blocks_split++;
4882 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
4885 if (insn == BB_HEAD (bb))
4886 break;
4890 if (blocks_split)
4891 verify_flow_info ();
4893 return blocks_split;
4896 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4897 the conditional branch target, SECOND_HEAD should be the fall-thru
4898 there is no need to handle this here the loop versioning code handles
4899 this. the reason for SECON_HEAD is that it is needed for condition
4900 in trees, and this should be of the same type since it is a hook. */
4901 static void
4902 rtl_lv_add_condition_to_bb (basic_block first_head ,
4903 basic_block second_head ATTRIBUTE_UNUSED,
4904 basic_block cond_bb, void *comp_rtx)
4906 rtx label;
4907 rtx_insn *seq, *jump;
4908 rtx op0 = XEXP ((rtx)comp_rtx, 0);
4909 rtx op1 = XEXP ((rtx)comp_rtx, 1);
4910 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
4911 enum machine_mode mode;
4914 label = block_label (first_head);
4915 mode = GET_MODE (op0);
4916 if (mode == VOIDmode)
4917 mode = GET_MODE (op1);
4919 start_sequence ();
4920 op0 = force_operand (op0, NULL_RTX);
4921 op1 = force_operand (op1, NULL_RTX);
4922 do_compare_rtx_and_jump (op0, op1, comp, 0,
4923 mode, NULL_RTX, NULL_RTX, label, -1);
4924 jump = get_last_insn ();
4925 JUMP_LABEL (jump) = label;
4926 LABEL_NUSES (label)++;
4927 seq = get_insns ();
4928 end_sequence ();
4930 /* Add the new cond , in the new head. */
4931 emit_insn_after (seq, BB_END (cond_bb));
4935 /* Given a block B with unconditional branch at its end, get the
4936 store the return the branch edge and the fall-thru edge in
4937 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4938 static void
4939 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
4940 edge *fallthru_edge)
4942 edge e = EDGE_SUCC (b, 0);
4944 if (e->flags & EDGE_FALLTHRU)
4946 *fallthru_edge = e;
4947 *branch_edge = EDGE_SUCC (b, 1);
4949 else
4951 *branch_edge = e;
4952 *fallthru_edge = EDGE_SUCC (b, 1);
4956 void
4957 init_rtl_bb_info (basic_block bb)
4959 gcc_assert (!bb->il.x.rtl);
4960 bb->il.x.head_ = NULL;
4961 bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
4964 /* Returns true if it is possible to remove edge E by redirecting
4965 it to the destination of the other edge from E->src. */
4967 static bool
4968 rtl_can_remove_branch_p (const_edge e)
4970 const_basic_block src = e->src;
4971 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
4972 const rtx_insn *insn = BB_END (src);
4973 rtx set;
4975 /* The conditions are taken from try_redirect_by_replacing_jump. */
4976 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
4977 return false;
4979 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4980 return false;
4982 if (BB_PARTITION (src) != BB_PARTITION (target))
4983 return false;
4985 if (!onlyjump_p (insn)
4986 || tablejump_p (insn, NULL, NULL))
4987 return false;
4989 set = single_set (insn);
4990 if (!set || side_effects_p (set))
4991 return false;
4993 return true;
4996 static basic_block
4997 rtl_duplicate_bb (basic_block bb)
4999 bb = cfg_layout_duplicate_bb (bb);
5000 bb->aux = NULL;
5001 return bb;
5004 /* Do book-keeping of basic block BB for the profile consistency checker.
5005 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5006 then do post-pass accounting. Store the counting in RECORD. */
5007 static void
5008 rtl_account_profile_record (basic_block bb, int after_pass,
5009 struct profile_record *record)
5011 rtx_insn *insn;
5012 FOR_BB_INSNS (bb, insn)
5013 if (INSN_P (insn))
5015 record->size[after_pass]
5016 += insn_rtx_cost (PATTERN (insn), false);
5017 if (profile_status_for_fn (cfun) == PROFILE_READ)
5018 record->time[after_pass]
5019 += insn_rtx_cost (PATTERN (insn), true) * bb->count;
5020 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
5021 record->time[after_pass]
5022 += insn_rtx_cost (PATTERN (insn), true) * bb->frequency;
5026 /* Implementation of CFG manipulation for linearized RTL. */
5027 struct cfg_hooks rtl_cfg_hooks = {
5028 "rtl",
5029 rtl_verify_flow_info,
5030 rtl_dump_bb,
5031 rtl_dump_bb_for_graph,
5032 rtl_create_basic_block,
5033 rtl_redirect_edge_and_branch,
5034 rtl_redirect_edge_and_branch_force,
5035 rtl_can_remove_branch_p,
5036 rtl_delete_block,
5037 rtl_split_block,
5038 rtl_move_block_after,
5039 rtl_can_merge_blocks, /* can_merge_blocks_p */
5040 rtl_merge_blocks,
5041 rtl_predict_edge,
5042 rtl_predicted_by_p,
5043 cfg_layout_can_duplicate_bb_p,
5044 rtl_duplicate_bb,
5045 rtl_split_edge,
5046 rtl_make_forwarder_block,
5047 rtl_tidy_fallthru_edge,
5048 rtl_force_nonfallthru,
5049 rtl_block_ends_with_call_p,
5050 rtl_block_ends_with_condjump_p,
5051 rtl_flow_call_edges_add,
5052 NULL, /* execute_on_growing_pred */
5053 NULL, /* execute_on_shrinking_pred */
5054 NULL, /* duplicate loop for trees */
5055 NULL, /* lv_add_condition_to_bb */
5056 NULL, /* lv_adjust_loop_header_phi*/
5057 NULL, /* extract_cond_bb_edges */
5058 NULL, /* flush_pending_stmts */
5059 rtl_block_empty_p, /* block_empty_p */
5060 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5061 rtl_account_profile_record,
5064 /* Implementation of CFG manipulation for cfg layout RTL, where
5065 basic block connected via fallthru edges does not have to be adjacent.
5066 This representation will hopefully become the default one in future
5067 version of the compiler. */
5069 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5070 "cfglayout mode",
5071 rtl_verify_flow_info_1,
5072 rtl_dump_bb,
5073 rtl_dump_bb_for_graph,
5074 cfg_layout_create_basic_block,
5075 cfg_layout_redirect_edge_and_branch,
5076 cfg_layout_redirect_edge_and_branch_force,
5077 rtl_can_remove_branch_p,
5078 cfg_layout_delete_block,
5079 cfg_layout_split_block,
5080 rtl_move_block_after,
5081 cfg_layout_can_merge_blocks_p,
5082 cfg_layout_merge_blocks,
5083 rtl_predict_edge,
5084 rtl_predicted_by_p,
5085 cfg_layout_can_duplicate_bb_p,
5086 cfg_layout_duplicate_bb,
5087 cfg_layout_split_edge,
5088 rtl_make_forwarder_block,
5089 NULL, /* tidy_fallthru_edge */
5090 rtl_force_nonfallthru,
5091 rtl_block_ends_with_call_p,
5092 rtl_block_ends_with_condjump_p,
5093 rtl_flow_call_edges_add,
5094 NULL, /* execute_on_growing_pred */
5095 NULL, /* execute_on_shrinking_pred */
5096 duplicate_loop_to_header_edge, /* duplicate loop for trees */
5097 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5098 NULL, /* lv_adjust_loop_header_phi*/
5099 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5100 NULL, /* flush_pending_stmts */
5101 rtl_block_empty_p, /* block_empty_p */
5102 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5103 rtl_account_profile_record,
5106 #include "gt-cfgrtl.h"