* tree.h (TYPE_OVERFLOW_SANITIZED): Define.
[official-gcc.git] / gcc / cfgrtl.c
blobf6eb2072d11b4fac507b610bcd1f6e2b5ec62e94
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 "predict.h"
47 #include "vec.h"
48 #include "hashtab.h"
49 #include "hash-set.h"
50 #include "machmode.h"
51 #include "input.h"
52 #include "function.h"
53 #include "dominance.h"
54 #include "cfg.h"
55 #include "cfgrtl.h"
56 #include "cfganal.h"
57 #include "cfgbuild.h"
58 #include "cfgcleanup.h"
59 #include "basic-block.h"
60 #include "bb-reorder.h"
61 #include "regs.h"
62 #include "flags.h"
63 #include "except.h"
64 #include "rtl-error.h"
65 #include "tm_p.h"
66 #include "obstack.h"
67 #include "insn-attr.h"
68 #include "insn-config.h"
69 #include "expr.h"
70 #include "target.h"
71 #include "common/common-target.h"
72 #include "cfgloop.h"
73 #include "ggc.h"
74 #include "tree-pass.h"
75 #include "df.h"
77 /* Holds the interesting leading and trailing notes for the function.
78 Only applicable if the CFG is in cfglayout mode. */
79 static GTY(()) rtx_insn *cfg_layout_function_footer;
80 static GTY(()) rtx_insn *cfg_layout_function_header;
82 static rtx_insn *skip_insns_after_block (basic_block);
83 static void record_effective_endpoints (void);
84 static rtx label_for_bb (basic_block);
85 static void fixup_reorder_chain (void);
87 void verify_insn_chain (void);
88 static void fixup_fallthru_exit_predecessor (void);
89 static int can_delete_note_p (const rtx_note *);
90 static int can_delete_label_p (const rtx_code_label *);
91 static basic_block rtl_split_edge (edge);
92 static bool rtl_move_block_after (basic_block, basic_block);
93 static int rtl_verify_flow_info (void);
94 static basic_block cfg_layout_split_block (basic_block, void *);
95 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
96 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
97 static void cfg_layout_delete_block (basic_block);
98 static void rtl_delete_block (basic_block);
99 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
100 static edge rtl_redirect_edge_and_branch (edge, basic_block);
101 static basic_block rtl_split_block (basic_block, void *);
102 static void rtl_dump_bb (FILE *, basic_block, int, int);
103 static int rtl_verify_flow_info_1 (void);
104 static void rtl_make_forwarder_block (edge);
106 /* Return true if NOTE is not one of the ones that must be kept paired,
107 so that we may simply delete it. */
109 static int
110 can_delete_note_p (const rtx_note *note)
112 switch (NOTE_KIND (note))
114 case NOTE_INSN_DELETED:
115 case NOTE_INSN_BASIC_BLOCK:
116 case NOTE_INSN_EPILOGUE_BEG:
117 return true;
119 default:
120 return false;
124 /* True if a given label can be deleted. */
126 static int
127 can_delete_label_p (const rtx_code_label *label)
129 return (!LABEL_PRESERVE_P (label)
130 /* User declared labels must be preserved. */
131 && LABEL_NAME (label) == 0
132 && !in_expr_list_p (forced_labels, label));
135 /* Delete INSN by patching it out. */
137 void
138 delete_insn (rtx uncast_insn)
140 rtx_insn *insn = as_a <rtx_insn *> (uncast_insn);
141 rtx note;
142 bool really_delete = true;
144 if (LABEL_P (insn))
146 /* Some labels can't be directly removed from the INSN chain, as they
147 might be references via variables, constant pool etc.
148 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
149 if (! can_delete_label_p (as_a <rtx_code_label *> (insn)))
151 const char *name = LABEL_NAME (insn);
152 basic_block bb = BLOCK_FOR_INSN (insn);
153 rtx_insn *bb_note = NEXT_INSN (insn);
155 really_delete = false;
156 PUT_CODE (insn, NOTE);
157 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
158 NOTE_DELETED_LABEL_NAME (insn) = name;
160 /* If the note following the label starts a basic block, and the
161 label is a member of the same basic block, interchange the two. */
162 if (bb_note != NULL_RTX
163 && NOTE_INSN_BASIC_BLOCK_P (bb_note)
164 && bb != NULL
165 && bb == BLOCK_FOR_INSN (bb_note))
167 reorder_insns_nobb (insn, insn, bb_note);
168 BB_HEAD (bb) = bb_note;
169 if (BB_END (bb) == bb_note)
170 BB_END (bb) = insn;
174 remove_node_from_insn_list (insn, &nonlocal_goto_handler_labels);
177 if (really_delete)
179 /* If this insn has already been deleted, something is very wrong. */
180 gcc_assert (!insn->deleted ());
181 if (INSN_P (insn))
182 df_insn_delete (insn);
183 remove_insn (insn);
184 insn->set_deleted ();
187 /* If deleting a jump, decrement the use count of the label. Deleting
188 the label itself should happen in the normal course of block merging. */
189 if (JUMP_P (insn))
191 if (JUMP_LABEL (insn)
192 && LABEL_P (JUMP_LABEL (insn)))
193 LABEL_NUSES (JUMP_LABEL (insn))--;
195 /* If there are more targets, remove them too. */
196 while ((note
197 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
198 && LABEL_P (XEXP (note, 0)))
200 LABEL_NUSES (XEXP (note, 0))--;
201 remove_note (insn, note);
205 /* Also if deleting any insn that references a label as an operand. */
206 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
207 && LABEL_P (XEXP (note, 0)))
209 LABEL_NUSES (XEXP (note, 0))--;
210 remove_note (insn, note);
213 if (rtx_jump_table_data *table = dyn_cast <rtx_jump_table_data *> (insn))
215 rtvec vec = table->get_labels ();
216 int len = GET_NUM_ELEM (vec);
217 int i;
219 for (i = 0; i < len; i++)
221 rtx label = XEXP (RTVEC_ELT (vec, i), 0);
223 /* When deleting code in bulk (e.g. removing many unreachable
224 blocks) we can delete a label that's a target of the vector
225 before deleting the vector itself. */
226 if (!NOTE_P (label))
227 LABEL_NUSES (label)--;
232 /* Like delete_insn but also purge dead edges from BB. */
234 void
235 delete_insn_and_edges (rtx_insn *insn)
237 bool purge = false;
239 if (INSN_P (insn)
240 && BLOCK_FOR_INSN (insn)
241 && BB_END (BLOCK_FOR_INSN (insn)) == insn)
242 purge = true;
243 delete_insn (insn);
244 if (purge)
245 purge_dead_edges (BLOCK_FOR_INSN (insn));
248 /* Unlink a chain of insns between START and FINISH, leaving notes
249 that must be paired. If CLEAR_BB is true, we set bb field for
250 insns that cannot be removed to NULL. */
252 void
253 delete_insn_chain (rtx start, rtx finish, bool clear_bb)
255 rtx_insn *prev, *current;
257 /* Unchain the insns one by one. It would be quicker to delete all of these
258 with a single unchaining, rather than one at a time, but we need to keep
259 the NOTE's. */
260 current = safe_as_a <rtx_insn *> (finish);
261 while (1)
263 prev = PREV_INSN (current);
264 if (NOTE_P (current) && !can_delete_note_p (as_a <rtx_note *> (current)))
266 else
267 delete_insn (current);
269 if (clear_bb && !current->deleted ())
270 set_block_for_insn (current, NULL);
272 if (current == start)
273 break;
274 current = prev;
278 /* Create a new basic block consisting of the instructions between HEAD and END
279 inclusive. This function is designed to allow fast BB construction - reuses
280 the note and basic block struct in BB_NOTE, if any and do not grow
281 BASIC_BLOCK chain and should be used directly only by CFG construction code.
282 END can be NULL in to create new empty basic block before HEAD. Both END
283 and HEAD can be NULL to create basic block at the end of INSN chain.
284 AFTER is the basic block we should be put after. */
286 basic_block
287 create_basic_block_structure (rtx_insn *head, rtx_insn *end, rtx_note *bb_note,
288 basic_block after)
290 basic_block bb;
292 if (bb_note
293 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
294 && bb->aux == NULL)
296 /* If we found an existing note, thread it back onto the chain. */
298 rtx_insn *after;
300 if (LABEL_P (head))
301 after = head;
302 else
304 after = PREV_INSN (head);
305 head = bb_note;
308 if (after != bb_note && NEXT_INSN (after) != bb_note)
309 reorder_insns_nobb (bb_note, bb_note, after);
311 else
313 /* Otherwise we must create a note and a basic block structure. */
315 bb = alloc_block ();
317 init_rtl_bb_info (bb);
318 if (!head && !end)
319 head = end = bb_note
320 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
321 else if (LABEL_P (head) && end)
323 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
324 if (head == end)
325 end = bb_note;
327 else
329 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
330 head = bb_note;
331 if (!end)
332 end = head;
335 NOTE_BASIC_BLOCK (bb_note) = bb;
338 /* Always include the bb note in the block. */
339 if (NEXT_INSN (end) == bb_note)
340 end = bb_note;
342 BB_HEAD (bb) = head;
343 BB_END (bb) = end;
344 bb->index = last_basic_block_for_fn (cfun)++;
345 bb->flags = BB_NEW | BB_RTL;
346 link_block (bb, after);
347 SET_BASIC_BLOCK_FOR_FN (cfun, bb->index, bb);
348 df_bb_refs_record (bb->index, false);
349 update_bb_for_insn (bb);
350 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
352 /* Tag the block so that we know it has been used when considering
353 other basic block notes. */
354 bb->aux = bb;
356 return bb;
359 /* Create new basic block consisting of instructions in between HEAD and END
360 and place it to the BB chain after block AFTER. END can be NULL to
361 create a new empty basic block before HEAD. Both END and HEAD can be
362 NULL to create basic block at the end of INSN chain. */
364 static basic_block
365 rtl_create_basic_block (void *headp, void *endp, basic_block after)
367 rtx_insn *head = (rtx_insn *) headp;
368 rtx_insn *end = (rtx_insn *) endp;
369 basic_block bb;
371 /* Grow the basic block array if needed. */
372 if ((size_t) last_basic_block_for_fn (cfun)
373 >= basic_block_info_for_fn (cfun)->length ())
375 size_t new_size =
376 (last_basic_block_for_fn (cfun)
377 + (last_basic_block_for_fn (cfun) + 3) / 4);
378 vec_safe_grow_cleared (basic_block_info_for_fn (cfun), new_size);
381 n_basic_blocks_for_fn (cfun)++;
383 bb = create_basic_block_structure (head, end, NULL, after);
384 bb->aux = NULL;
385 return bb;
388 static basic_block
389 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
391 basic_block newbb = rtl_create_basic_block (head, end, after);
393 return newbb;
396 /* Delete the insns in a (non-live) block. We physically delete every
397 non-deleted-note insn, and update the flow graph appropriately.
399 Return nonzero if we deleted an exception handler. */
401 /* ??? Preserving all such notes strikes me as wrong. It would be nice
402 to post-process the stream to remove empty blocks, loops, ranges, etc. */
404 static void
405 rtl_delete_block (basic_block b)
407 rtx_insn *insn, *end;
409 /* If the head of this block is a CODE_LABEL, then it might be the
410 label for an exception handler which can't be reached. We need
411 to remove the label from the exception_handler_label list. */
412 insn = BB_HEAD (b);
414 end = get_last_bb_insn (b);
416 /* Selectively delete the entire chain. */
417 BB_HEAD (b) = NULL;
418 delete_insn_chain (insn, end, true);
421 if (dump_file)
422 fprintf (dump_file, "deleting block %d\n", b->index);
423 df_bb_delete (b->index);
426 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
428 void
429 compute_bb_for_insn (void)
431 basic_block bb;
433 FOR_EACH_BB_FN (bb, cfun)
435 rtx_insn *end = BB_END (bb);
436 rtx_insn *insn;
438 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
440 BLOCK_FOR_INSN (insn) = bb;
441 if (insn == end)
442 break;
447 /* Release the basic_block_for_insn array. */
449 unsigned int
450 free_bb_for_insn (void)
452 rtx_insn *insn;
453 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
454 if (!BARRIER_P (insn))
455 BLOCK_FOR_INSN (insn) = NULL;
456 return 0;
459 namespace {
461 const pass_data pass_data_free_cfg =
463 RTL_PASS, /* type */
464 "*free_cfg", /* name */
465 OPTGROUP_NONE, /* optinfo_flags */
466 TV_NONE, /* tv_id */
467 0, /* properties_required */
468 0, /* properties_provided */
469 PROP_cfg, /* properties_destroyed */
470 0, /* todo_flags_start */
471 0, /* todo_flags_finish */
474 class pass_free_cfg : public rtl_opt_pass
476 public:
477 pass_free_cfg (gcc::context *ctxt)
478 : rtl_opt_pass (pass_data_free_cfg, ctxt)
481 /* opt_pass methods: */
482 virtual unsigned int execute (function *);
484 }; // class pass_free_cfg
486 unsigned int
487 pass_free_cfg::execute (function *)
489 #ifdef DELAY_SLOTS
490 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
491 valid at that point so it would be too late to call df_analyze. */
492 if (optimize > 0 && flag_delayed_branch)
494 df_note_add_problem ();
495 df_analyze ();
497 #endif
499 if (crtl->has_bb_partition)
500 insert_section_boundary_note ();
502 free_bb_for_insn ();
503 return 0;
506 } // anon namespace
508 rtl_opt_pass *
509 make_pass_free_cfg (gcc::context *ctxt)
511 return new pass_free_cfg (ctxt);
514 /* Return RTX to emit after when we want to emit code on the entry of function. */
515 rtx_insn *
516 entry_of_function (void)
518 return (n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS ?
519 BB_HEAD (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb) : get_insns ());
522 /* Emit INSN at the entry point of the function, ensuring that it is only
523 executed once per function. */
524 void
525 emit_insn_at_entry (rtx insn)
527 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
528 edge e = ei_safe_edge (ei);
529 gcc_assert (e->flags & EDGE_FALLTHRU);
531 insert_insn_on_edge (insn, e);
532 commit_edge_insertions ();
535 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
536 (or BARRIER if found) and notify df of the bb change.
537 The insn chain range is inclusive
538 (i.e. both BEGIN and END will be updated. */
540 static void
541 update_bb_for_insn_chain (rtx_insn *begin, rtx_insn *end, basic_block bb)
543 rtx_insn *insn;
545 end = NEXT_INSN (end);
546 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
547 if (!BARRIER_P (insn))
548 df_insn_change_bb (insn, bb);
551 /* Update BLOCK_FOR_INSN of insns in BB to BB,
552 and notify df of the change. */
554 void
555 update_bb_for_insn (basic_block bb)
557 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
561 /* Like active_insn_p, except keep the return value clobber around
562 even after reload. */
564 static bool
565 flow_active_insn_p (const rtx_insn *insn)
567 if (active_insn_p (insn))
568 return true;
570 /* A clobber of the function return value exists for buggy
571 programs that fail to return a value. Its effect is to
572 keep the return value from being live across the entire
573 function. If we allow it to be skipped, we introduce the
574 possibility for register lifetime confusion. */
575 if (GET_CODE (PATTERN (insn)) == CLOBBER
576 && REG_P (XEXP (PATTERN (insn), 0))
577 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
578 return true;
580 return false;
583 /* Return true if the block has no effect and only forwards control flow to
584 its single destination. */
586 bool
587 contains_no_active_insn_p (const_basic_block bb)
589 rtx_insn *insn;
591 if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun) || bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
592 || !single_succ_p (bb))
593 return false;
595 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
596 if (INSN_P (insn) && flow_active_insn_p (insn))
597 return false;
599 return (!INSN_P (insn)
600 || (JUMP_P (insn) && simplejump_p (insn))
601 || !flow_active_insn_p (insn));
604 /* Likewise, but protect loop latches, headers and preheaders. */
605 /* FIXME: Make this a cfg hook. */
607 bool
608 forwarder_block_p (const_basic_block bb)
610 if (!contains_no_active_insn_p (bb))
611 return false;
613 /* Protect loop latches, headers and preheaders. */
614 if (current_loops)
616 basic_block dest;
617 if (bb->loop_father->header == bb)
618 return false;
619 dest = EDGE_SUCC (bb, 0)->dest;
620 if (dest->loop_father->header == dest)
621 return false;
624 return true;
627 /* Return nonzero if we can reach target from src by falling through. */
628 /* FIXME: Make this a cfg hook, the result is only valid in cfgrtl mode. */
630 bool
631 can_fallthru (basic_block src, basic_block target)
633 rtx_insn *insn = BB_END (src);
634 rtx_insn *insn2;
635 edge e;
636 edge_iterator ei;
638 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
639 return true;
640 if (src->next_bb != target)
641 return false;
643 /* ??? Later we may add code to move jump tables offline. */
644 if (tablejump_p (insn, NULL, NULL))
645 return false;
647 FOR_EACH_EDGE (e, ei, src->succs)
648 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
649 && e->flags & EDGE_FALLTHRU)
650 return false;
652 insn2 = BB_HEAD (target);
653 if (!active_insn_p (insn2))
654 insn2 = next_active_insn (insn2);
656 return next_active_insn (insn) == insn2;
659 /* Return nonzero if we could reach target from src by falling through,
660 if the target was made adjacent. If we already have a fall-through
661 edge to the exit block, we can't do that. */
662 static bool
663 could_fall_through (basic_block src, basic_block target)
665 edge e;
666 edge_iterator ei;
668 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
669 return true;
670 FOR_EACH_EDGE (e, ei, src->succs)
671 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
672 && e->flags & EDGE_FALLTHRU)
673 return 0;
674 return true;
677 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
678 rtx_note *
679 bb_note (basic_block bb)
681 rtx_insn *note;
683 note = BB_HEAD (bb);
684 if (LABEL_P (note))
685 note = NEXT_INSN (note);
687 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
688 return as_a <rtx_note *> (note);
691 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
692 note associated with the BLOCK. */
694 static rtx_insn *
695 first_insn_after_basic_block_note (basic_block block)
697 rtx_insn *insn;
699 /* Get the first instruction in the block. */
700 insn = BB_HEAD (block);
702 if (insn == NULL_RTX)
703 return NULL;
704 if (LABEL_P (insn))
705 insn = NEXT_INSN (insn);
706 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
708 return NEXT_INSN (insn);
711 /* Creates a new basic block just after basic block BB by splitting
712 everything after specified instruction INSNP. */
714 static basic_block
715 rtl_split_block (basic_block bb, void *insnp)
717 basic_block new_bb;
718 rtx_insn *insn = (rtx_insn *) insnp;
719 edge e;
720 edge_iterator ei;
722 if (!insn)
724 insn = first_insn_after_basic_block_note (bb);
726 if (insn)
728 rtx_insn *next = insn;
730 insn = PREV_INSN (insn);
732 /* If the block contains only debug insns, insn would have
733 been NULL in a non-debug compilation, and then we'd end
734 up emitting a DELETED note. For -fcompare-debug
735 stability, emit the note too. */
736 if (insn != BB_END (bb)
737 && DEBUG_INSN_P (next)
738 && DEBUG_INSN_P (BB_END (bb)))
740 while (next != BB_END (bb) && DEBUG_INSN_P (next))
741 next = NEXT_INSN (next);
743 if (next == BB_END (bb))
744 emit_note_after (NOTE_INSN_DELETED, next);
747 else
748 insn = get_last_insn ();
751 /* We probably should check type of the insn so that we do not create
752 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
753 bother. */
754 if (insn == BB_END (bb))
755 emit_note_after (NOTE_INSN_DELETED, insn);
757 /* Create the new basic block. */
758 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
759 BB_COPY_PARTITION (new_bb, bb);
760 BB_END (bb) = insn;
762 /* Redirect the outgoing edges. */
763 new_bb->succs = bb->succs;
764 bb->succs = NULL;
765 FOR_EACH_EDGE (e, ei, new_bb->succs)
766 e->src = new_bb;
768 /* The new block starts off being dirty. */
769 df_set_bb_dirty (bb);
770 return new_bb;
773 /* Return true if the single edge between blocks A and B is the only place
774 in RTL which holds some unique locus. */
776 static bool
777 unique_locus_on_edge_between_p (basic_block a, basic_block b)
779 const location_t goto_locus = EDGE_SUCC (a, 0)->goto_locus;
780 rtx_insn *insn, *end;
782 if (LOCATION_LOCUS (goto_locus) == UNKNOWN_LOCATION)
783 return false;
785 /* First scan block A backward. */
786 insn = BB_END (a);
787 end = PREV_INSN (BB_HEAD (a));
788 while (insn != end && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
789 insn = PREV_INSN (insn);
791 if (insn != end && INSN_LOCATION (insn) == goto_locus)
792 return false;
794 /* Then scan block B forward. */
795 insn = BB_HEAD (b);
796 if (insn)
798 end = NEXT_INSN (BB_END (b));
799 while (insn != end && !NONDEBUG_INSN_P (insn))
800 insn = NEXT_INSN (insn);
802 if (insn != end && INSN_HAS_LOCATION (insn)
803 && INSN_LOCATION (insn) == goto_locus)
804 return false;
807 return true;
810 /* If the single edge between blocks A and B is the only place in RTL which
811 holds some unique locus, emit a nop with that locus between the blocks. */
813 static void
814 emit_nop_for_unique_locus_between (basic_block a, basic_block b)
816 if (!unique_locus_on_edge_between_p (a, b))
817 return;
819 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
820 INSN_LOCATION (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
823 /* Blocks A and B are to be merged into a single block A. The insns
824 are already contiguous. */
826 static void
827 rtl_merge_blocks (basic_block a, basic_block b)
829 rtx_insn *b_head = BB_HEAD (b), *b_end = BB_END (b), *a_end = BB_END (a);
830 rtx_insn *del_first = NULL, *del_last = NULL;
831 rtx_insn *b_debug_start = b_end, *b_debug_end = b_end;
832 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
833 int b_empty = 0;
835 if (dump_file)
836 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
837 a->index);
839 while (DEBUG_INSN_P (b_end))
840 b_end = PREV_INSN (b_debug_start = b_end);
842 /* If there was a CODE_LABEL beginning B, delete it. */
843 if (LABEL_P (b_head))
845 /* Detect basic blocks with nothing but a label. This can happen
846 in particular at the end of a function. */
847 if (b_head == b_end)
848 b_empty = 1;
850 del_first = del_last = b_head;
851 b_head = NEXT_INSN (b_head);
854 /* Delete the basic block note and handle blocks containing just that
855 note. */
856 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
858 if (b_head == b_end)
859 b_empty = 1;
860 if (! del_last)
861 del_first = b_head;
863 del_last = b_head;
864 b_head = NEXT_INSN (b_head);
867 /* If there was a jump out of A, delete it. */
868 if (JUMP_P (a_end))
870 rtx_insn *prev;
872 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
873 if (!NOTE_P (prev)
874 || NOTE_INSN_BASIC_BLOCK_P (prev)
875 || prev == BB_HEAD (a))
876 break;
878 del_first = a_end;
880 #ifdef HAVE_cc0
881 /* If this was a conditional jump, we need to also delete
882 the insn that set cc0. */
883 if (only_sets_cc0_p (prev))
885 rtx_insn *tmp = prev;
887 prev = prev_nonnote_insn (prev);
888 if (!prev)
889 prev = BB_HEAD (a);
890 del_first = tmp;
892 #endif
894 a_end = PREV_INSN (del_first);
896 else if (BARRIER_P (NEXT_INSN (a_end)))
897 del_first = NEXT_INSN (a_end);
899 /* Delete everything marked above as well as crap that might be
900 hanging out between the two blocks. */
901 BB_END (a) = a_end;
902 BB_HEAD (b) = b_empty ? NULL : b_head;
903 delete_insn_chain (del_first, del_last, true);
905 /* When not optimizing and the edge is the only place in RTL which holds
906 some unique locus, emit a nop with that locus in between. */
907 if (!optimize)
909 emit_nop_for_unique_locus_between (a, b);
910 a_end = BB_END (a);
913 /* Reassociate the insns of B with A. */
914 if (!b_empty)
916 update_bb_for_insn_chain (a_end, b_debug_end, a);
918 BB_END (a) = b_debug_end;
919 BB_HEAD (b) = NULL;
921 else if (b_end != b_debug_end)
923 /* Move any deleted labels and other notes between the end of A
924 and the debug insns that make up B after the debug insns,
925 bringing the debug insns into A while keeping the notes after
926 the end of A. */
927 if (NEXT_INSN (a_end) != b_debug_start)
928 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
929 b_debug_end);
930 update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
931 BB_END (a) = b_debug_end;
934 df_bb_delete (b->index);
936 /* If B was a forwarder block, propagate the locus on the edge. */
937 if (forwarder_p
938 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
939 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
941 if (dump_file)
942 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
946 /* Return true when block A and B can be merged. */
948 static bool
949 rtl_can_merge_blocks (basic_block a, basic_block b)
951 /* If we are partitioning hot/cold basic blocks, we don't want to
952 mess up unconditional or indirect jumps that cross between hot
953 and cold sections.
955 Basic block partitioning may result in some jumps that appear to
956 be optimizable (or blocks that appear to be mergeable), but which really
957 must be left untouched (they are required to make it safely across
958 partition boundaries). See the comments at the top of
959 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
961 if (BB_PARTITION (a) != BB_PARTITION (b))
962 return false;
964 /* Protect the loop latches. */
965 if (current_loops && b->loop_father->latch == b)
966 return false;
968 /* There must be exactly one edge in between the blocks. */
969 return (single_succ_p (a)
970 && single_succ (a) == b
971 && single_pred_p (b)
972 && a != b
973 /* Must be simple edge. */
974 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
975 && a->next_bb == b
976 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
977 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
978 /* If the jump insn has side effects,
979 we can't kill the edge. */
980 && (!JUMP_P (BB_END (a))
981 || (reload_completed
982 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
985 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
986 exist. */
989 block_label (basic_block block)
991 if (block == EXIT_BLOCK_PTR_FOR_FN (cfun))
992 return NULL_RTX;
994 if (!LABEL_P (BB_HEAD (block)))
996 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
999 return BB_HEAD (block);
1002 /* Attempt to perform edge redirection by replacing possibly complex jump
1003 instruction by unconditional jump or removing jump completely. This can
1004 apply only if all edges now point to the same block. The parameters and
1005 return values are equivalent to redirect_edge_and_branch. */
1007 edge
1008 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
1010 basic_block src = e->src;
1011 rtx_insn *insn = BB_END (src), *kill_from;
1012 rtx set;
1013 int fallthru = 0;
1015 /* If we are partitioning hot/cold basic blocks, we don't want to
1016 mess up unconditional or indirect jumps that cross between hot
1017 and cold sections.
1019 Basic block partitioning may result in some jumps that appear to
1020 be optimizable (or blocks that appear to be mergeable), but which really
1021 must be left untouched (they are required to make it safely across
1022 partition boundaries). See the comments at the top of
1023 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
1025 if (BB_PARTITION (src) != BB_PARTITION (target))
1026 return NULL;
1028 /* We can replace or remove a complex jump only when we have exactly
1029 two edges. Also, if we have exactly one outgoing edge, we can
1030 redirect that. */
1031 if (EDGE_COUNT (src->succs) >= 3
1032 /* Verify that all targets will be TARGET. Specifically, the
1033 edge that is not E must also go to TARGET. */
1034 || (EDGE_COUNT (src->succs) == 2
1035 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
1036 return NULL;
1038 if (!onlyjump_p (insn))
1039 return NULL;
1040 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
1041 return NULL;
1043 /* Avoid removing branch with side effects. */
1044 set = single_set (insn);
1045 if (!set || side_effects_p (set))
1046 return NULL;
1048 /* In case we zap a conditional jump, we'll need to kill
1049 the cc0 setter too. */
1050 kill_from = insn;
1051 #ifdef HAVE_cc0
1052 if (reg_mentioned_p (cc0_rtx, PATTERN (insn))
1053 && only_sets_cc0_p (PREV_INSN (insn)))
1054 kill_from = PREV_INSN (insn);
1055 #endif
1057 /* See if we can create the fallthru edge. */
1058 if (in_cfglayout || can_fallthru (src, target))
1060 if (dump_file)
1061 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1062 fallthru = 1;
1064 /* Selectively unlink whole insn chain. */
1065 if (in_cfglayout)
1067 rtx_insn *insn = BB_FOOTER (src);
1069 delete_insn_chain (kill_from, BB_END (src), false);
1071 /* Remove barriers but keep jumptables. */
1072 while (insn)
1074 if (BARRIER_P (insn))
1076 if (PREV_INSN (insn))
1077 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1078 else
1079 BB_FOOTER (src) = NEXT_INSN (insn);
1080 if (NEXT_INSN (insn))
1081 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1083 if (LABEL_P (insn))
1084 break;
1085 insn = NEXT_INSN (insn);
1088 else
1089 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
1090 false);
1093 /* If this already is simplejump, redirect it. */
1094 else if (simplejump_p (insn))
1096 if (e->dest == target)
1097 return NULL;
1098 if (dump_file)
1099 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1100 INSN_UID (insn), e->dest->index, target->index);
1101 if (!redirect_jump (insn, block_label (target), 0))
1103 gcc_assert (target == EXIT_BLOCK_PTR_FOR_FN (cfun));
1104 return NULL;
1108 /* Cannot do anything for target exit block. */
1109 else if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1110 return NULL;
1112 /* Or replace possibly complicated jump insn by simple jump insn. */
1113 else
1115 rtx target_label = block_label (target);
1116 rtx_insn *barrier;
1117 rtx label;
1118 rtx_jump_table_data *table;
1120 emit_jump_insn_after_noloc (gen_jump (target_label), insn);
1121 JUMP_LABEL (BB_END (src)) = target_label;
1122 LABEL_NUSES (target_label)++;
1123 if (dump_file)
1124 fprintf (dump_file, "Replacing insn %i by jump %i\n",
1125 INSN_UID (insn), INSN_UID (BB_END (src)));
1128 delete_insn_chain (kill_from, insn, false);
1130 /* Recognize a tablejump that we are converting to a
1131 simple jump and remove its associated CODE_LABEL
1132 and ADDR_VEC or ADDR_DIFF_VEC. */
1133 if (tablejump_p (insn, &label, &table))
1134 delete_insn_chain (label, table, false);
1136 barrier = next_nonnote_insn (BB_END (src));
1137 if (!barrier || !BARRIER_P (barrier))
1138 emit_barrier_after (BB_END (src));
1139 else
1141 if (barrier != NEXT_INSN (BB_END (src)))
1143 /* Move the jump before barrier so that the notes
1144 which originally were or were created before jump table are
1145 inside the basic block. */
1146 rtx_insn *new_insn = BB_END (src);
1148 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1149 PREV_INSN (barrier), src);
1151 SET_NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1152 SET_PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1154 SET_NEXT_INSN (new_insn) = barrier;
1155 SET_NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1157 SET_PREV_INSN (new_insn) = PREV_INSN (barrier);
1158 SET_PREV_INSN (barrier) = new_insn;
1163 /* Keep only one edge out and set proper flags. */
1164 if (!single_succ_p (src))
1165 remove_edge (e);
1166 gcc_assert (single_succ_p (src));
1168 e = single_succ_edge (src);
1169 if (fallthru)
1170 e->flags = EDGE_FALLTHRU;
1171 else
1172 e->flags = 0;
1174 e->probability = REG_BR_PROB_BASE;
1175 e->count = src->count;
1177 if (e->dest != target)
1178 redirect_edge_succ (e, target);
1179 return e;
1182 /* Subroutine of redirect_branch_edge that tries to patch the jump
1183 instruction INSN so that it reaches block NEW. Do this
1184 only when it originally reached block OLD. Return true if this
1185 worked or the original target wasn't OLD, return false if redirection
1186 doesn't work. */
1188 static bool
1189 patch_jump_insn (rtx_insn *insn, rtx_insn *old_label, basic_block new_bb)
1191 rtx_jump_table_data *table;
1192 rtx tmp;
1193 /* Recognize a tablejump and adjust all matching cases. */
1194 if (tablejump_p (insn, NULL, &table))
1196 rtvec vec;
1197 int j;
1198 rtx new_label = block_label (new_bb);
1200 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1201 return false;
1202 vec = table->get_labels ();
1204 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1205 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1207 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1208 --LABEL_NUSES (old_label);
1209 ++LABEL_NUSES (new_label);
1212 /* Handle casesi dispatch insns. */
1213 if ((tmp = single_set (insn)) != NULL
1214 && SET_DEST (tmp) == pc_rtx
1215 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1216 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1217 && LABEL_REF_LABEL (XEXP (SET_SRC (tmp), 2)) == old_label)
1219 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1220 new_label);
1221 --LABEL_NUSES (old_label);
1222 ++LABEL_NUSES (new_label);
1225 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1227 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1228 rtx new_label, note;
1230 if (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
1231 return false;
1232 new_label = block_label (new_bb);
1234 for (i = 0; i < n; ++i)
1236 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1237 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1238 if (XEXP (old_ref, 0) == old_label)
1240 ASM_OPERANDS_LABEL (tmp, i)
1241 = gen_rtx_LABEL_REF (Pmode, new_label);
1242 --LABEL_NUSES (old_label);
1243 ++LABEL_NUSES (new_label);
1247 if (JUMP_LABEL (insn) == old_label)
1249 JUMP_LABEL (insn) = new_label;
1250 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1251 if (note)
1252 remove_note (insn, note);
1254 else
1256 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1257 if (note)
1258 remove_note (insn, note);
1259 if (JUMP_LABEL (insn) != new_label
1260 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1261 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1263 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1264 != NULL_RTX)
1265 XEXP (note, 0) = new_label;
1267 else
1269 /* ?? We may play the games with moving the named labels from
1270 one basic block to the other in case only one computed_jump is
1271 available. */
1272 if (computed_jump_p (insn)
1273 /* A return instruction can't be redirected. */
1274 || returnjump_p (insn))
1275 return false;
1277 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1279 /* If the insn doesn't go where we think, we're confused. */
1280 gcc_assert (JUMP_LABEL (insn) == old_label);
1282 /* If the substitution doesn't succeed, die. This can happen
1283 if the back end emitted unrecognizable instructions or if
1284 target is exit block on some arches. */
1285 if (!redirect_jump (insn, block_label (new_bb), 0))
1287 gcc_assert (new_bb == EXIT_BLOCK_PTR_FOR_FN (cfun));
1288 return false;
1292 return true;
1296 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1297 NULL on failure */
1298 static edge
1299 redirect_branch_edge (edge e, basic_block target)
1301 rtx_insn *old_label = BB_HEAD (e->dest);
1302 basic_block src = e->src;
1303 rtx_insn *insn = BB_END (src);
1305 /* We can only redirect non-fallthru edges of jump insn. */
1306 if (e->flags & EDGE_FALLTHRU)
1307 return NULL;
1308 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1309 return NULL;
1311 if (!currently_expanding_to_rtl)
1313 if (!patch_jump_insn (insn, old_label, target))
1314 return NULL;
1316 else
1317 /* When expanding this BB might actually contain multiple
1318 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1319 Redirect all of those that match our label. */
1320 FOR_BB_INSNS (src, insn)
1321 if (JUMP_P (insn) && !patch_jump_insn (insn, old_label, target))
1322 return NULL;
1324 if (dump_file)
1325 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1326 e->src->index, e->dest->index, target->index);
1328 if (e->dest != target)
1329 e = redirect_edge_succ_nodup (e, target);
1331 return e;
1334 /* Called when edge E has been redirected to a new destination,
1335 in order to update the region crossing flag on the edge and
1336 jump. */
1338 static void
1339 fixup_partition_crossing (edge e)
1341 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun) || e->dest
1342 == EXIT_BLOCK_PTR_FOR_FN (cfun))
1343 return;
1344 /* If we redirected an existing edge, it may already be marked
1345 crossing, even though the new src is missing a reg crossing note.
1346 But make sure reg crossing note doesn't already exist before
1347 inserting. */
1348 if (BB_PARTITION (e->src) != BB_PARTITION (e->dest))
1350 e->flags |= EDGE_CROSSING;
1351 if (JUMP_P (BB_END (e->src))
1352 && !CROSSING_JUMP_P (BB_END (e->src)))
1353 CROSSING_JUMP_P (BB_END (e->src)) = 1;
1355 else if (BB_PARTITION (e->src) == BB_PARTITION (e->dest))
1357 e->flags &= ~EDGE_CROSSING;
1358 /* Remove the section crossing note from jump at end of
1359 src if it exists, and if no other successors are
1360 still crossing. */
1361 if (JUMP_P (BB_END (e->src)) && CROSSING_JUMP_P (BB_END (e->src)))
1363 bool has_crossing_succ = false;
1364 edge e2;
1365 edge_iterator ei;
1366 FOR_EACH_EDGE (e2, ei, e->src->succs)
1368 has_crossing_succ |= (e2->flags & EDGE_CROSSING);
1369 if (has_crossing_succ)
1370 break;
1372 if (!has_crossing_succ)
1373 CROSSING_JUMP_P (BB_END (e->src)) = 0;
1378 /* Called when block BB has been reassigned to the cold partition,
1379 because it is now dominated by another cold block,
1380 to ensure that the region crossing attributes are updated. */
1382 static void
1383 fixup_new_cold_bb (basic_block bb)
1385 edge e;
1386 edge_iterator ei;
1388 /* This is called when a hot bb is found to now be dominated
1389 by a cold bb and therefore needs to become cold. Therefore,
1390 its preds will no longer be region crossing. Any non-dominating
1391 preds that were previously hot would also have become cold
1392 in the caller for the same region. Any preds that were previously
1393 region-crossing will be adjusted in fixup_partition_crossing. */
1394 FOR_EACH_EDGE (e, ei, bb->preds)
1396 fixup_partition_crossing (e);
1399 /* Possibly need to make bb's successor edges region crossing,
1400 or remove stale region crossing. */
1401 FOR_EACH_EDGE (e, ei, bb->succs)
1403 /* We can't have fall-through edges across partition boundaries.
1404 Note that force_nonfallthru will do any necessary partition
1405 boundary fixup by calling fixup_partition_crossing itself. */
1406 if ((e->flags & EDGE_FALLTHRU)
1407 && BB_PARTITION (bb) != BB_PARTITION (e->dest)
1408 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1409 force_nonfallthru (e);
1410 else
1411 fixup_partition_crossing (e);
1415 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1416 expense of adding new instructions or reordering basic blocks.
1418 Function can be also called with edge destination equivalent to the TARGET.
1419 Then it should try the simplifications and do nothing if none is possible.
1421 Return edge representing the branch if transformation succeeded. Return NULL
1422 on failure.
1423 We still return NULL in case E already destinated TARGET and we didn't
1424 managed to simplify instruction stream. */
1426 static edge
1427 rtl_redirect_edge_and_branch (edge e, basic_block target)
1429 edge ret;
1430 basic_block src = e->src;
1431 basic_block dest = e->dest;
1433 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1434 return NULL;
1436 if (dest == target)
1437 return e;
1439 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1441 df_set_bb_dirty (src);
1442 fixup_partition_crossing (ret);
1443 return ret;
1446 ret = redirect_branch_edge (e, target);
1447 if (!ret)
1448 return NULL;
1450 df_set_bb_dirty (src);
1451 fixup_partition_crossing (ret);
1452 return ret;
1455 /* Emit a barrier after BB, into the footer if we are in CFGLAYOUT mode. */
1457 void
1458 emit_barrier_after_bb (basic_block bb)
1460 rtx_barrier *barrier = emit_barrier_after (BB_END (bb));
1461 gcc_assert (current_ir_type () == IR_RTL_CFGRTL
1462 || current_ir_type () == IR_RTL_CFGLAYOUT);
1463 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1464 BB_FOOTER (bb) = unlink_insn_chain (barrier, barrier);
1467 /* Like force_nonfallthru below, but additionally performs redirection
1468 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1469 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1470 simple_return_rtx, indicating which kind of returnjump to create.
1471 It should be NULL otherwise. */
1473 basic_block
1474 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1476 basic_block jump_block, new_bb = NULL, src = e->src;
1477 rtx note;
1478 edge new_edge;
1479 int abnormal_edge_flags = 0;
1480 bool asm_goto_edge = false;
1481 int loc;
1483 /* In the case the last instruction is conditional jump to the next
1484 instruction, first redirect the jump itself and then continue
1485 by creating a basic block afterwards to redirect fallthru edge. */
1486 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1487 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1488 && any_condjump_p (BB_END (e->src))
1489 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1491 rtx note;
1492 edge b = unchecked_make_edge (e->src, target, 0);
1493 bool redirected;
1495 redirected = redirect_jump (BB_END (e->src), block_label (target), 0);
1496 gcc_assert (redirected);
1498 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1499 if (note)
1501 int prob = XINT (note, 0);
1503 b->probability = prob;
1504 /* Update this to use GCOV_COMPUTE_SCALE. */
1505 b->count = e->count * prob / REG_BR_PROB_BASE;
1506 e->probability -= e->probability;
1507 e->count -= b->count;
1508 if (e->probability < 0)
1509 e->probability = 0;
1510 if (e->count < 0)
1511 e->count = 0;
1515 if (e->flags & EDGE_ABNORMAL)
1517 /* Irritating special case - fallthru edge to the same block as abnormal
1518 edge.
1519 We can't redirect abnormal edge, but we still can split the fallthru
1520 one and create separate abnormal edge to original destination.
1521 This allows bb-reorder to make such edge non-fallthru. */
1522 gcc_assert (e->dest == target);
1523 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1524 e->flags &= EDGE_FALLTHRU;
1526 else
1528 gcc_assert (e->flags & EDGE_FALLTHRU);
1529 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1531 /* We can't redirect the entry block. Create an empty block
1532 at the start of the function which we use to add the new
1533 jump. */
1534 edge tmp;
1535 edge_iterator ei;
1536 bool found = false;
1538 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL,
1539 ENTRY_BLOCK_PTR_FOR_FN (cfun));
1541 /* Change the existing edge's source to be the new block, and add
1542 a new edge from the entry block to the new block. */
1543 e->src = bb;
1544 for (ei = ei_start (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs);
1545 (tmp = ei_safe_edge (ei)); )
1547 if (tmp == e)
1549 ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs->unordered_remove (ei.index);
1550 found = true;
1551 break;
1553 else
1554 ei_next (&ei);
1557 gcc_assert (found);
1559 vec_safe_push (bb->succs, e);
1560 make_single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun), bb,
1561 EDGE_FALLTHRU);
1565 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1566 don't point to the target or fallthru label. */
1567 if (JUMP_P (BB_END (e->src))
1568 && target != EXIT_BLOCK_PTR_FOR_FN (cfun)
1569 && (e->flags & EDGE_FALLTHRU)
1570 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1572 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1573 bool adjust_jump_target = false;
1575 for (i = 0; i < n; ++i)
1577 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1579 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))--;
1580 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1581 LABEL_NUSES (XEXP (ASM_OPERANDS_LABEL (note, i), 0))++;
1582 adjust_jump_target = true;
1584 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1585 asm_goto_edge = true;
1587 if (adjust_jump_target)
1589 rtx_insn *insn = BB_END (e->src);
1590 rtx note;
1591 rtx_insn *old_label = BB_HEAD (e->dest);
1592 rtx_insn *new_label = BB_HEAD (target);
1594 if (JUMP_LABEL (insn) == old_label)
1596 JUMP_LABEL (insn) = new_label;
1597 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1598 if (note)
1599 remove_note (insn, note);
1601 else
1603 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1604 if (note)
1605 remove_note (insn, note);
1606 if (JUMP_LABEL (insn) != new_label
1607 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1608 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1610 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1611 != NULL_RTX)
1612 XEXP (note, 0) = new_label;
1616 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1618 rtx_insn *new_head;
1619 gcov_type count = e->count;
1620 int probability = e->probability;
1621 /* Create the new structures. */
1623 /* If the old block ended with a tablejump, skip its table
1624 by searching forward from there. Otherwise start searching
1625 forward from the last instruction of the old block. */
1626 rtx_jump_table_data *table;
1627 if (tablejump_p (BB_END (e->src), NULL, &table))
1628 new_head = table;
1629 else
1630 new_head = BB_END (e->src);
1631 new_head = NEXT_INSN (new_head);
1633 jump_block = create_basic_block (new_head, NULL, e->src);
1634 jump_block->count = count;
1635 jump_block->frequency = EDGE_FREQUENCY (e);
1637 /* Make sure new block ends up in correct hot/cold section. */
1639 BB_COPY_PARTITION (jump_block, e->src);
1641 /* Wire edge in. */
1642 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1643 new_edge->probability = probability;
1644 new_edge->count = count;
1646 /* Redirect old edge. */
1647 redirect_edge_pred (e, jump_block);
1648 e->probability = REG_BR_PROB_BASE;
1650 /* If e->src was previously region crossing, it no longer is
1651 and the reg crossing note should be removed. */
1652 fixup_partition_crossing (new_edge);
1654 /* If asm goto has any label refs to target's label,
1655 add also edge from asm goto bb to target. */
1656 if (asm_goto_edge)
1658 new_edge->probability /= 2;
1659 new_edge->count /= 2;
1660 jump_block->count /= 2;
1661 jump_block->frequency /= 2;
1662 new_edge = make_edge (new_edge->src, target,
1663 e->flags & ~EDGE_FALLTHRU);
1664 new_edge->probability = probability - probability / 2;
1665 new_edge->count = count - count / 2;
1668 new_bb = jump_block;
1670 else
1671 jump_block = e->src;
1673 loc = e->goto_locus;
1674 e->flags &= ~EDGE_FALLTHRU;
1675 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
1677 if (jump_label == ret_rtx)
1679 #ifdef HAVE_return
1680 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block), loc);
1681 #else
1682 gcc_unreachable ();
1683 #endif
1685 else
1687 gcc_assert (jump_label == simple_return_rtx);
1688 #ifdef HAVE_simple_return
1689 emit_jump_insn_after_setloc (gen_simple_return (),
1690 BB_END (jump_block), loc);
1691 #else
1692 gcc_unreachable ();
1693 #endif
1695 set_return_jump_label (BB_END (jump_block));
1697 else
1699 rtx label = block_label (target);
1700 emit_jump_insn_after_setloc (gen_jump (label), BB_END (jump_block), loc);
1701 JUMP_LABEL (BB_END (jump_block)) = label;
1702 LABEL_NUSES (label)++;
1705 /* We might be in cfg layout mode, and if so, the following routine will
1706 insert the barrier correctly. */
1707 emit_barrier_after_bb (jump_block);
1708 redirect_edge_succ_nodup (e, target);
1710 if (abnormal_edge_flags)
1711 make_edge (src, target, abnormal_edge_flags);
1713 df_mark_solutions_dirty ();
1714 fixup_partition_crossing (e);
1715 return new_bb;
1718 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1719 (and possibly create new basic block) to make edge non-fallthru.
1720 Return newly created BB or NULL if none. */
1722 static basic_block
1723 rtl_force_nonfallthru (edge e)
1725 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1728 /* Redirect edge even at the expense of creating new jump insn or
1729 basic block. Return new basic block if created, NULL otherwise.
1730 Conversion must be possible. */
1732 static basic_block
1733 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1735 if (redirect_edge_and_branch (e, target)
1736 || e->dest == target)
1737 return NULL;
1739 /* In case the edge redirection failed, try to force it to be non-fallthru
1740 and redirect newly created simplejump. */
1741 df_set_bb_dirty (e->src);
1742 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1745 /* The given edge should potentially be a fallthru edge. If that is in
1746 fact true, delete the jump and barriers that are in the way. */
1748 static void
1749 rtl_tidy_fallthru_edge (edge e)
1751 rtx_insn *q;
1752 basic_block b = e->src, c = b->next_bb;
1754 /* ??? In a late-running flow pass, other folks may have deleted basic
1755 blocks by nopping out blocks, leaving multiple BARRIERs between here
1756 and the target label. They ought to be chastised and fixed.
1758 We can also wind up with a sequence of undeletable labels between
1759 one block and the next.
1761 So search through a sequence of barriers, labels, and notes for
1762 the head of block C and assert that we really do fall through. */
1764 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1765 if (INSN_P (q))
1766 return;
1768 /* Remove what will soon cease being the jump insn from the source block.
1769 If block B consisted only of this single jump, turn it into a deleted
1770 note. */
1771 q = BB_END (b);
1772 if (JUMP_P (q)
1773 && onlyjump_p (q)
1774 && (any_uncondjump_p (q)
1775 || single_succ_p (b)))
1777 #ifdef HAVE_cc0
1778 /* If this was a conditional jump, we need to also delete
1779 the insn that set cc0. */
1780 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1781 q = PREV_INSN (q);
1782 #endif
1784 q = PREV_INSN (q);
1787 /* Selectively unlink the sequence. */
1788 if (q != PREV_INSN (BB_HEAD (c)))
1789 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1791 e->flags |= EDGE_FALLTHRU;
1794 /* Should move basic block BB after basic block AFTER. NIY. */
1796 static bool
1797 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1798 basic_block after ATTRIBUTE_UNUSED)
1800 return false;
1803 /* Locate the last bb in the same partition as START_BB. */
1805 static basic_block
1806 last_bb_in_partition (basic_block start_bb)
1808 basic_block bb;
1809 FOR_BB_BETWEEN (bb, start_bb, EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
1811 if (BB_PARTITION (start_bb) != BB_PARTITION (bb->next_bb))
1812 return bb;
1814 /* Return bb before the exit block. */
1815 return bb->prev_bb;
1818 /* Split a (typically critical) edge. Return the new block.
1819 The edge must not be abnormal.
1821 ??? The code generally expects to be called on critical edges.
1822 The case of a block ending in an unconditional jump to a
1823 block with multiple predecessors is not handled optimally. */
1825 static basic_block
1826 rtl_split_edge (edge edge_in)
1828 basic_block bb, new_bb;
1829 rtx_insn *before;
1831 /* Abnormal edges cannot be split. */
1832 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1834 /* We are going to place the new block in front of edge destination.
1835 Avoid existence of fallthru predecessors. */
1836 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1838 edge e = find_fallthru_edge (edge_in->dest->preds);
1840 if (e)
1841 force_nonfallthru (e);
1844 /* Create the basic block note. */
1845 if (edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1846 before = BB_HEAD (edge_in->dest);
1847 else
1848 before = NULL;
1850 /* If this is a fall through edge to the exit block, the blocks might be
1851 not adjacent, and the right place is after the source. */
1852 if ((edge_in->flags & EDGE_FALLTHRU)
1853 && edge_in->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
1855 before = NEXT_INSN (BB_END (edge_in->src));
1856 bb = create_basic_block (before, NULL, edge_in->src);
1857 BB_COPY_PARTITION (bb, edge_in->src);
1859 else
1861 if (edge_in->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1863 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1864 BB_COPY_PARTITION (bb, edge_in->dest);
1866 else
1868 basic_block after = edge_in->dest->prev_bb;
1869 /* If this is post-bb reordering, and the edge crosses a partition
1870 boundary, the new block needs to be inserted in the bb chain
1871 at the end of the src partition (since we put the new bb into
1872 that partition, see below). Otherwise we may end up creating
1873 an extra partition crossing in the chain, which is illegal.
1874 It can't go after the src, because src may have a fall-through
1875 to a different block. */
1876 if (crtl->bb_reorder_complete
1877 && (edge_in->flags & EDGE_CROSSING))
1879 after = last_bb_in_partition (edge_in->src);
1880 before = NEXT_INSN (BB_END (after));
1881 /* The instruction following the last bb in partition should
1882 be a barrier, since it cannot end in a fall-through. */
1883 gcc_checking_assert (BARRIER_P (before));
1884 before = NEXT_INSN (before);
1886 bb = create_basic_block (before, NULL, after);
1887 /* Put the split bb into the src partition, to avoid creating
1888 a situation where a cold bb dominates a hot bb, in the case
1889 where src is cold and dest is hot. The src will dominate
1890 the new bb (whereas it might not have dominated dest). */
1891 BB_COPY_PARTITION (bb, edge_in->src);
1895 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1897 /* Can't allow a region crossing edge to be fallthrough. */
1898 if (BB_PARTITION (bb) != BB_PARTITION (edge_in->dest)
1899 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1901 new_bb = force_nonfallthru (single_succ_edge (bb));
1902 gcc_assert (!new_bb);
1905 /* For non-fallthru edges, we must adjust the predecessor's
1906 jump instruction to target our new block. */
1907 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1909 edge redirected = redirect_edge_and_branch (edge_in, bb);
1910 gcc_assert (redirected);
1912 else
1914 if (edge_in->src != ENTRY_BLOCK_PTR_FOR_FN (cfun))
1916 /* For asm goto even splitting of fallthru edge might
1917 need insn patching, as other labels might point to the
1918 old label. */
1919 rtx_insn *last = BB_END (edge_in->src);
1920 if (last
1921 && JUMP_P (last)
1922 && edge_in->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
1923 && extract_asm_operands (PATTERN (last)) != NULL_RTX
1924 && patch_jump_insn (last, before, bb))
1925 df_set_bb_dirty (edge_in->src);
1927 redirect_edge_succ (edge_in, bb);
1930 return bb;
1933 /* Queue instructions for insertion on an edge between two basic blocks.
1934 The new instructions and basic blocks (if any) will not appear in the
1935 CFG until commit_edge_insertions is called. */
1937 void
1938 insert_insn_on_edge (rtx pattern, edge e)
1940 /* We cannot insert instructions on an abnormal critical edge.
1941 It will be easier to find the culprit if we die now. */
1942 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1944 if (e->insns.r == NULL_RTX)
1945 start_sequence ();
1946 else
1947 push_to_sequence (e->insns.r);
1949 emit_insn (pattern);
1951 e->insns.r = get_insns ();
1952 end_sequence ();
1955 /* Update the CFG for the instructions queued on edge E. */
1957 void
1958 commit_one_edge_insertion (edge e)
1960 rtx_insn *before = NULL, *after = NULL, *insns, *tmp, *last;
1961 basic_block bb;
1963 /* Pull the insns off the edge now since the edge might go away. */
1964 insns = e->insns.r;
1965 e->insns.r = NULL;
1967 /* Figure out where to put these insns. If the destination has
1968 one predecessor, insert there. Except for the exit block. */
1969 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1971 bb = e->dest;
1973 /* Get the location correct wrt a code label, and "nice" wrt
1974 a basic block note, and before everything else. */
1975 tmp = BB_HEAD (bb);
1976 if (LABEL_P (tmp))
1977 tmp = NEXT_INSN (tmp);
1978 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1979 tmp = NEXT_INSN (tmp);
1980 if (tmp == BB_HEAD (bb))
1981 before = tmp;
1982 else if (tmp)
1983 after = PREV_INSN (tmp);
1984 else
1985 after = get_last_insn ();
1988 /* If the source has one successor and the edge is not abnormal,
1989 insert there. Except for the entry block.
1990 Don't do this if the predecessor ends in a jump other than
1991 unconditional simple jump. E.g. for asm goto that points all
1992 its labels at the fallthru basic block, we can't insert instructions
1993 before the asm goto, as the asm goto can have various of side effects,
1994 and can't emit instructions after the asm goto, as it must end
1995 the basic block. */
1996 else if ((e->flags & EDGE_ABNORMAL) == 0
1997 && single_succ_p (e->src)
1998 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
1999 && (!JUMP_P (BB_END (e->src))
2000 || simplejump_p (BB_END (e->src))))
2002 bb = e->src;
2004 /* It is possible to have a non-simple jump here. Consider a target
2005 where some forms of unconditional jumps clobber a register. This
2006 happens on the fr30 for example.
2008 We know this block has a single successor, so we can just emit
2009 the queued insns before the jump. */
2010 if (JUMP_P (BB_END (bb)))
2011 before = BB_END (bb);
2012 else
2014 /* We'd better be fallthru, or we've lost track of what's what. */
2015 gcc_assert (e->flags & EDGE_FALLTHRU);
2017 after = BB_END (bb);
2021 /* Otherwise we must split the edge. */
2022 else
2024 bb = split_edge (e);
2026 /* If E crossed a partition boundary, we needed to make bb end in
2027 a region-crossing jump, even though it was originally fallthru. */
2028 if (JUMP_P (BB_END (bb)))
2029 before = BB_END (bb);
2030 else
2031 after = BB_END (bb);
2034 /* Now that we've found the spot, do the insertion. */
2035 if (before)
2037 emit_insn_before_noloc (insns, before, bb);
2038 last = prev_nonnote_insn (before);
2040 else
2041 last = emit_insn_after_noloc (insns, after, bb);
2043 if (returnjump_p (last))
2045 /* ??? Remove all outgoing edges from BB and add one for EXIT.
2046 This is not currently a problem because this only happens
2047 for the (single) epilogue, which already has a fallthru edge
2048 to EXIT. */
2050 e = single_succ_edge (bb);
2051 gcc_assert (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
2052 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
2054 e->flags &= ~EDGE_FALLTHRU;
2055 emit_barrier_after (last);
2057 if (before)
2058 delete_insn (before);
2060 else
2061 gcc_assert (!JUMP_P (last));
2064 /* Update the CFG for all queued instructions. */
2066 void
2067 commit_edge_insertions (void)
2069 basic_block bb;
2071 /* Optimization passes that invoke this routine can cause hot blocks
2072 previously reached by both hot and cold blocks to become dominated only
2073 by cold blocks. This will cause the verification below to fail,
2074 and lead to now cold code in the hot section. In some cases this
2075 may only be visible after newly unreachable blocks are deleted,
2076 which will be done by fixup_partitions. */
2077 fixup_partitions ();
2079 #ifdef ENABLE_CHECKING
2080 verify_flow_info ();
2081 #endif
2083 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
2084 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
2086 edge e;
2087 edge_iterator ei;
2089 FOR_EACH_EDGE (e, ei, bb->succs)
2090 if (e->insns.r)
2091 commit_one_edge_insertion (e);
2096 /* Print out RTL-specific basic block information (live information
2097 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
2098 documented in dumpfile.h. */
2100 static void
2101 rtl_dump_bb (FILE *outf, basic_block bb, int indent, int flags)
2103 rtx_insn *insn;
2104 rtx_insn *last;
2105 char *s_indent;
2107 s_indent = (char *) alloca ((size_t) indent + 1);
2108 memset (s_indent, ' ', (size_t) indent);
2109 s_indent[indent] = '\0';
2111 if (df && (flags & TDF_DETAILS))
2113 df_dump_top (bb, outf);
2114 putc ('\n', outf);
2117 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK)
2118 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
2119 insn = NEXT_INSN (insn))
2121 if (flags & TDF_DETAILS)
2122 df_dump_insn_top (insn, outf);
2123 if (! (flags & TDF_SLIM))
2124 print_rtl_single (outf, insn);
2125 else
2126 dump_insn_slim (outf, insn);
2127 if (flags & TDF_DETAILS)
2128 df_dump_insn_bottom (insn, outf);
2131 if (df && (flags & TDF_DETAILS))
2133 df_dump_bottom (bb, outf);
2134 putc ('\n', outf);
2139 /* Like dump_function_to_file, but for RTL. Print out dataflow information
2140 for the start of each basic block. FLAGS are the TDF_* masks documented
2141 in dumpfile.h. */
2143 void
2144 print_rtl_with_bb (FILE *outf, const rtx_insn *rtx_first, int flags)
2146 const rtx_insn *tmp_rtx;
2147 if (rtx_first == 0)
2148 fprintf (outf, "(nil)\n");
2149 else
2151 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
2152 int max_uid = get_max_uid ();
2153 basic_block *start = XCNEWVEC (basic_block, max_uid);
2154 basic_block *end = XCNEWVEC (basic_block, max_uid);
2155 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
2156 basic_block bb;
2158 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
2159 insns, but the CFG is not maintained so the basic block info
2160 is not reliable. Therefore it's omitted from the dumps. */
2161 if (! (cfun->curr_properties & PROP_cfg))
2162 flags &= ~TDF_BLOCKS;
2164 if (df)
2165 df_dump_start (outf);
2167 if (flags & TDF_BLOCKS)
2169 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2171 rtx_insn *x;
2173 start[INSN_UID (BB_HEAD (bb))] = bb;
2174 end[INSN_UID (BB_END (bb))] = bb;
2175 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
2177 enum bb_state state = IN_MULTIPLE_BB;
2179 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
2180 state = IN_ONE_BB;
2181 in_bb_p[INSN_UID (x)] = state;
2183 if (x == BB_END (bb))
2184 break;
2189 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
2191 if (flags & TDF_BLOCKS)
2193 bb = start[INSN_UID (tmp_rtx)];
2194 if (bb != NULL)
2196 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, true, false);
2197 if (df && (flags & TDF_DETAILS))
2198 df_dump_top (bb, outf);
2201 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
2202 && !NOTE_P (tmp_rtx)
2203 && !BARRIER_P (tmp_rtx))
2204 fprintf (outf, ";; Insn is not within a basic block\n");
2205 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
2206 fprintf (outf, ";; Insn is in multiple basic blocks\n");
2209 if (flags & TDF_DETAILS)
2210 df_dump_insn_top (tmp_rtx, outf);
2211 if (! (flags & TDF_SLIM))
2212 print_rtl_single (outf, tmp_rtx);
2213 else
2214 dump_insn_slim (outf, tmp_rtx);
2215 if (flags & TDF_DETAILS)
2216 df_dump_insn_bottom (tmp_rtx, outf);
2218 if (flags & TDF_BLOCKS)
2220 bb = end[INSN_UID (tmp_rtx)];
2221 if (bb != NULL)
2223 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, false, true);
2224 if (df && (flags & TDF_DETAILS))
2225 df_dump_bottom (bb, outf);
2226 putc ('\n', outf);
2231 free (start);
2232 free (end);
2233 free (in_bb_p);
2237 /* Update the branch probability of BB if a REG_BR_PROB is present. */
2239 void
2240 update_br_prob_note (basic_block bb)
2242 rtx note;
2243 if (!JUMP_P (BB_END (bb)))
2244 return;
2245 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
2246 if (!note || XINT (note, 0) == BRANCH_EDGE (bb)->probability)
2247 return;
2248 XINT (note, 0) = BRANCH_EDGE (bb)->probability;
2251 /* Get the last insn associated with block BB (that includes barriers and
2252 tablejumps after BB). */
2253 rtx_insn *
2254 get_last_bb_insn (basic_block bb)
2256 rtx_jump_table_data *table;
2257 rtx_insn *tmp;
2258 rtx_insn *end = BB_END (bb);
2260 /* Include any jump table following the basic block. */
2261 if (tablejump_p (end, NULL, &table))
2262 end = table;
2264 /* Include any barriers that may follow the basic block. */
2265 tmp = next_nonnote_insn_bb (end);
2266 while (tmp && BARRIER_P (tmp))
2268 end = tmp;
2269 tmp = next_nonnote_insn_bb (end);
2272 return end;
2275 /* Sanity check partition hotness to ensure that basic blocks in
2276   the cold partition don't dominate basic blocks in the hot partition.
2277 If FLAG_ONLY is true, report violations as errors. Otherwise
2278 re-mark the dominated blocks as cold, since this is run after
2279 cfg optimizations that may make hot blocks previously reached
2280 by both hot and cold blocks now only reachable along cold paths. */
2282 static vec<basic_block>
2283 find_partition_fixes (bool flag_only)
2285 basic_block bb;
2286 vec<basic_block> bbs_in_cold_partition = vNULL;
2287 vec<basic_block> bbs_to_fix = vNULL;
2289 /* Callers check this. */
2290 gcc_checking_assert (crtl->has_bb_partition);
2292 FOR_EACH_BB_FN (bb, cfun)
2293 if ((BB_PARTITION (bb) == BB_COLD_PARTITION))
2294 bbs_in_cold_partition.safe_push (bb);
2296 if (bbs_in_cold_partition.is_empty ())
2297 return vNULL;
2299 bool dom_calculated_here = !dom_info_available_p (CDI_DOMINATORS);
2301 if (dom_calculated_here)
2302 calculate_dominance_info (CDI_DOMINATORS);
2304 while (! bbs_in_cold_partition.is_empty ())
2306 bb = bbs_in_cold_partition.pop ();
2307 /* Any blocks dominated by a block in the cold section
2308 must also be cold. */
2309 basic_block son;
2310 for (son = first_dom_son (CDI_DOMINATORS, bb);
2311 son;
2312 son = next_dom_son (CDI_DOMINATORS, son))
2314 /* If son is not yet cold, then mark it cold here and
2315 enqueue it for further processing. */
2316 if ((BB_PARTITION (son) != BB_COLD_PARTITION))
2318 if (flag_only)
2319 error ("non-cold basic block %d dominated "
2320 "by a block in the cold partition (%d)", son->index, bb->index);
2321 else
2322 BB_SET_PARTITION (son, BB_COLD_PARTITION);
2323 bbs_to_fix.safe_push (son);
2324 bbs_in_cold_partition.safe_push (son);
2329 if (dom_calculated_here)
2330 free_dominance_info (CDI_DOMINATORS);
2332 return bbs_to_fix;
2335 /* Perform cleanup on the hot/cold bb partitioning after optimization
2336 passes that modify the cfg. */
2338 void
2339 fixup_partitions (void)
2341 basic_block bb;
2343 if (!crtl->has_bb_partition)
2344 return;
2346 /* Delete any blocks that became unreachable and weren't
2347 already cleaned up, for example during edge forwarding
2348 and convert_jumps_to_returns. This will expose more
2349 opportunities for fixing the partition boundaries here.
2350 Also, the calculation of the dominance graph during verification
2351 will assert if there are unreachable nodes. */
2352 delete_unreachable_blocks ();
2354 /* If there are partitions, do a sanity check on them: A basic block in
2355   a cold partition cannot dominate a basic block in a hot partition.
2356 Fixup any that now violate this requirement, as a result of edge
2357 forwarding and unreachable block deletion.  */
2358 vec<basic_block> bbs_to_fix = find_partition_fixes (false);
2360 /* Do the partition fixup after all necessary blocks have been converted to
2361 cold, so that we only update the region crossings the minimum number of
2362 places, which can require forcing edges to be non fallthru. */
2363 while (! bbs_to_fix.is_empty ())
2365 bb = bbs_to_fix.pop ();
2366 fixup_new_cold_bb (bb);
2370 /* Verify, in the basic block chain, that there is at most one switch
2371 between hot/cold partitions. This condition will not be true until
2372 after reorder_basic_blocks is called. */
2374 static int
2375 verify_hot_cold_block_grouping (void)
2377 basic_block bb;
2378 int err = 0;
2379 bool switched_sections = false;
2380 int current_partition = BB_UNPARTITIONED;
2382 /* Even after bb reordering is complete, we go into cfglayout mode
2383 again (in compgoto). Ensure we don't call this before going back
2384 into linearized RTL when any layout fixes would have been committed. */
2385 if (!crtl->bb_reorder_complete
2386 || current_ir_type () != IR_RTL_CFGRTL)
2387 return err;
2389 FOR_EACH_BB_FN (bb, cfun)
2391 if (current_partition != BB_UNPARTITIONED
2392 && BB_PARTITION (bb) != current_partition)
2394 if (switched_sections)
2396 error ("multiple hot/cold transitions found (bb %i)",
2397 bb->index);
2398 err = 1;
2400 else
2401 switched_sections = true;
2403 if (!crtl->has_bb_partition)
2404 error ("partition found but function partition flag not set");
2406 current_partition = BB_PARTITION (bb);
2409 return err;
2413 /* Perform several checks on the edges out of each block, such as
2414 the consistency of the branch probabilities, the correctness
2415 of hot/cold partition crossing edges, and the number of expected
2416 successor edges. Also verify that the dominance relationship
2417 between hot/cold blocks is sane. */
2419 static int
2420 rtl_verify_edges (void)
2422 int err = 0;
2423 basic_block bb;
2425 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2427 int n_fallthru = 0, n_branch = 0, n_abnormal_call = 0, n_sibcall = 0;
2428 int n_eh = 0, n_abnormal = 0;
2429 edge e, fallthru = NULL;
2430 edge_iterator ei;
2431 rtx note;
2432 bool has_crossing_edge = false;
2434 if (JUMP_P (BB_END (bb))
2435 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2436 && EDGE_COUNT (bb->succs) >= 2
2437 && any_condjump_p (BB_END (bb)))
2439 if (XINT (note, 0) != BRANCH_EDGE (bb)->probability
2440 && profile_status_for_fn (cfun) != PROFILE_ABSENT)
2442 error ("verify_flow_info: REG_BR_PROB does not match cfg %i %i",
2443 XINT (note, 0), BRANCH_EDGE (bb)->probability);
2444 err = 1;
2448 FOR_EACH_EDGE (e, ei, bb->succs)
2450 bool is_crossing;
2452 if (e->flags & EDGE_FALLTHRU)
2453 n_fallthru++, fallthru = e;
2455 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2456 && e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2457 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun));
2458 has_crossing_edge |= is_crossing;
2459 if (e->flags & EDGE_CROSSING)
2461 if (!is_crossing)
2463 error ("EDGE_CROSSING incorrectly set across same section");
2464 err = 1;
2466 if (e->flags & EDGE_FALLTHRU)
2468 error ("fallthru edge crosses section boundary in bb %i",
2469 e->src->index);
2470 err = 1;
2472 if (e->flags & EDGE_EH)
2474 error ("EH edge crosses section boundary in bb %i",
2475 e->src->index);
2476 err = 1;
2478 if (JUMP_P (BB_END (bb)) && !CROSSING_JUMP_P (BB_END (bb)))
2480 error ("No region crossing jump at section boundary in bb %i",
2481 bb->index);
2482 err = 1;
2485 else if (is_crossing)
2487 error ("EDGE_CROSSING missing across section boundary");
2488 err = 1;
2491 if ((e->flags & ~(EDGE_DFS_BACK
2492 | EDGE_CAN_FALLTHRU
2493 | EDGE_IRREDUCIBLE_LOOP
2494 | EDGE_LOOP_EXIT
2495 | EDGE_CROSSING
2496 | EDGE_PRESERVE)) == 0)
2497 n_branch++;
2499 if (e->flags & EDGE_ABNORMAL_CALL)
2500 n_abnormal_call++;
2502 if (e->flags & EDGE_SIBCALL)
2503 n_sibcall++;
2505 if (e->flags & EDGE_EH)
2506 n_eh++;
2508 if (e->flags & EDGE_ABNORMAL)
2509 n_abnormal++;
2512 if (!has_crossing_edge
2513 && JUMP_P (BB_END (bb))
2514 && CROSSING_JUMP_P (BB_END (bb)))
2516 print_rtl_with_bb (stderr, get_insns (), TDF_RTL | TDF_BLOCKS | TDF_DETAILS);
2517 error ("Region crossing jump across same section in bb %i",
2518 bb->index);
2519 err = 1;
2522 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2524 error ("missing REG_EH_REGION note at the end of bb %i", bb->index);
2525 err = 1;
2527 if (n_eh > 1)
2529 error ("too many exception handling edges in bb %i", bb->index);
2530 err = 1;
2532 if (n_branch
2533 && (!JUMP_P (BB_END (bb))
2534 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2535 || any_condjump_p (BB_END (bb))))))
2537 error ("too many outgoing branch edges from bb %i", bb->index);
2538 err = 1;
2540 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2542 error ("fallthru edge after unconditional jump in bb %i", bb->index);
2543 err = 1;
2545 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2547 error ("wrong number of branch edges after unconditional jump"
2548 " in bb %i", bb->index);
2549 err = 1;
2551 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2552 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2554 error ("wrong amount of branch edges after conditional jump"
2555 " in bb %i", bb->index);
2556 err = 1;
2558 if (n_abnormal_call && !CALL_P (BB_END (bb)))
2560 error ("abnormal call edges for non-call insn in bb %i", bb->index);
2561 err = 1;
2563 if (n_sibcall && !CALL_P (BB_END (bb)))
2565 error ("sibcall edges for non-call insn in bb %i", bb->index);
2566 err = 1;
2568 if (n_abnormal > n_eh
2569 && !(CALL_P (BB_END (bb))
2570 && n_abnormal == n_abnormal_call + n_sibcall)
2571 && (!JUMP_P (BB_END (bb))
2572 || any_condjump_p (BB_END (bb))
2573 || any_uncondjump_p (BB_END (bb))))
2575 error ("abnormal edges for no purpose in bb %i", bb->index);
2576 err = 1;
2580 /* If there are partitions, do a sanity check on them: A basic block in
2581   a cold partition cannot dominate a basic block in a hot partition.  */
2582 if (crtl->has_bb_partition && !err)
2584 vec<basic_block> bbs_to_fix = find_partition_fixes (true);
2585 err = !bbs_to_fix.is_empty ();
2588 /* Clean up. */
2589 return err;
2592 /* Checks on the instructions within blocks. Currently checks that each
2593 block starts with a basic block note, and that basic block notes and
2594 control flow jumps are not found in the middle of the block. */
2596 static int
2597 rtl_verify_bb_insns (void)
2599 rtx_insn *x;
2600 int err = 0;
2601 basic_block bb;
2603 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2605 /* Now check the header of basic
2606 block. It ought to contain optional CODE_LABEL followed
2607 by NOTE_BASIC_BLOCK. */
2608 x = BB_HEAD (bb);
2609 if (LABEL_P (x))
2611 if (BB_END (bb) == x)
2613 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2614 bb->index);
2615 err = 1;
2618 x = NEXT_INSN (x);
2621 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2623 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2624 bb->index);
2625 err = 1;
2628 if (BB_END (bb) == x)
2629 /* Do checks for empty blocks here. */
2631 else
2632 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2634 if (NOTE_INSN_BASIC_BLOCK_P (x))
2636 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2637 INSN_UID (x), bb->index);
2638 err = 1;
2641 if (x == BB_END (bb))
2642 break;
2644 if (control_flow_insn_p (x))
2646 error ("in basic block %d:", bb->index);
2647 fatal_insn ("flow control insn inside a basic block", x);
2652 /* Clean up. */
2653 return err;
2656 /* Verify that block pointers for instructions in basic blocks, headers and
2657 footers are set appropriately. */
2659 static int
2660 rtl_verify_bb_pointers (void)
2662 int err = 0;
2663 basic_block bb;
2665 /* Check the general integrity of the basic blocks. */
2666 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2668 rtx_insn *insn;
2670 if (!(bb->flags & BB_RTL))
2672 error ("BB_RTL flag not set for block %d", bb->index);
2673 err = 1;
2676 FOR_BB_INSNS (bb, insn)
2677 if (BLOCK_FOR_INSN (insn) != bb)
2679 error ("insn %d basic block pointer is %d, should be %d",
2680 INSN_UID (insn),
2681 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2682 bb->index);
2683 err = 1;
2686 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2687 if (!BARRIER_P (insn)
2688 && BLOCK_FOR_INSN (insn) != NULL)
2690 error ("insn %d in header of bb %d has non-NULL basic block",
2691 INSN_UID (insn), bb->index);
2692 err = 1;
2694 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2695 if (!BARRIER_P (insn)
2696 && BLOCK_FOR_INSN (insn) != NULL)
2698 error ("insn %d in footer of bb %d has non-NULL basic block",
2699 INSN_UID (insn), bb->index);
2700 err = 1;
2704 /* Clean up. */
2705 return err;
2708 /* Verify the CFG and RTL consistency common for both underlying RTL and
2709 cfglayout RTL.
2711 Currently it does following checks:
2713 - overlapping of basic blocks
2714 - insns with wrong BLOCK_FOR_INSN pointers
2715 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2716 - tails of basic blocks (ensure that boundary is necessary)
2717 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2718 and NOTE_INSN_BASIC_BLOCK
2719 - verify that no fall_thru edge crosses hot/cold partition boundaries
2720 - verify that there are no pending RTL branch predictions
2721 - verify that hot blocks are not dominated by cold blocks
2723 In future it can be extended check a lot of other stuff as well
2724 (reachability of basic blocks, life information, etc. etc.). */
2726 static int
2727 rtl_verify_flow_info_1 (void)
2729 int err = 0;
2731 err |= rtl_verify_bb_pointers ();
2733 err |= rtl_verify_bb_insns ();
2735 err |= rtl_verify_edges ();
2737 return err;
2740 /* Walk the instruction chain and verify that bb head/end pointers
2741 are correct, and that instructions are in exactly one bb and have
2742 correct block pointers. */
2744 static int
2745 rtl_verify_bb_insn_chain (void)
2747 basic_block bb;
2748 int err = 0;
2749 rtx_insn *x;
2750 rtx_insn *last_head = get_last_insn ();
2751 basic_block *bb_info;
2752 const int max_uid = get_max_uid ();
2754 bb_info = XCNEWVEC (basic_block, max_uid);
2756 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2758 rtx_insn *head = BB_HEAD (bb);
2759 rtx_insn *end = BB_END (bb);
2761 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2763 /* Verify the end of the basic block is in the INSN chain. */
2764 if (x == end)
2765 break;
2767 /* And that the code outside of basic blocks has NULL bb field. */
2768 if (!BARRIER_P (x)
2769 && BLOCK_FOR_INSN (x) != NULL)
2771 error ("insn %d outside of basic blocks has non-NULL bb field",
2772 INSN_UID (x));
2773 err = 1;
2777 if (!x)
2779 error ("end insn %d for block %d not found in the insn stream",
2780 INSN_UID (end), bb->index);
2781 err = 1;
2784 /* Work backwards from the end to the head of the basic block
2785 to verify the head is in the RTL chain. */
2786 for (; x != NULL_RTX; x = PREV_INSN (x))
2788 /* While walking over the insn chain, verify insns appear
2789 in only one basic block. */
2790 if (bb_info[INSN_UID (x)] != NULL)
2792 error ("insn %d is in multiple basic blocks (%d and %d)",
2793 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2794 err = 1;
2797 bb_info[INSN_UID (x)] = bb;
2799 if (x == head)
2800 break;
2802 if (!x)
2804 error ("head insn %d for block %d not found in the insn stream",
2805 INSN_UID (head), bb->index);
2806 err = 1;
2809 last_head = PREV_INSN (x);
2812 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2814 /* Check that the code before the first basic block has NULL
2815 bb field. */
2816 if (!BARRIER_P (x)
2817 && BLOCK_FOR_INSN (x) != NULL)
2819 error ("insn %d outside of basic blocks has non-NULL bb field",
2820 INSN_UID (x));
2821 err = 1;
2824 free (bb_info);
2826 return err;
2829 /* Verify that fallthru edges point to adjacent blocks in layout order and
2830 that barriers exist after non-fallthru blocks. */
2832 static int
2833 rtl_verify_fallthru (void)
2835 basic_block bb;
2836 int err = 0;
2838 FOR_EACH_BB_REVERSE_FN (bb, cfun)
2840 edge e;
2842 e = find_fallthru_edge (bb->succs);
2843 if (!e)
2845 rtx_insn *insn;
2847 /* Ensure existence of barrier in BB with no fallthru edges. */
2848 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
2850 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
2852 error ("missing barrier after block %i", bb->index);
2853 err = 1;
2854 break;
2856 if (BARRIER_P (insn))
2857 break;
2860 else if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
2861 && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2863 rtx_insn *insn;
2865 if (e->src->next_bb != e->dest)
2867 error
2868 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2869 e->src->index, e->dest->index);
2870 err = 1;
2872 else
2873 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2874 insn = NEXT_INSN (insn))
2875 if (BARRIER_P (insn) || INSN_P (insn))
2877 error ("verify_flow_info: Incorrect fallthru %i->%i",
2878 e->src->index, e->dest->index);
2879 fatal_insn ("wrong insn in the fallthru edge", insn);
2880 err = 1;
2885 return err;
2888 /* Verify that blocks are laid out in consecutive order. While walking the
2889 instructions, verify that all expected instructions are inside the basic
2890 blocks, and that all returns are followed by barriers. */
2892 static int
2893 rtl_verify_bb_layout (void)
2895 basic_block bb;
2896 int err = 0;
2897 rtx_insn *x;
2898 int num_bb_notes;
2899 rtx_insn * const rtx_first = get_insns ();
2900 basic_block last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun), curr_bb = NULL;
2902 num_bb_notes = 0;
2903 last_bb_seen = ENTRY_BLOCK_PTR_FOR_FN (cfun);
2905 for (x = rtx_first; x; x = NEXT_INSN (x))
2907 if (NOTE_INSN_BASIC_BLOCK_P (x))
2909 bb = NOTE_BASIC_BLOCK (x);
2911 num_bb_notes++;
2912 if (bb != last_bb_seen->next_bb)
2913 internal_error ("basic blocks not laid down consecutively");
2915 curr_bb = last_bb_seen = bb;
2918 if (!curr_bb)
2920 switch (GET_CODE (x))
2922 case BARRIER:
2923 case NOTE:
2924 break;
2926 case CODE_LABEL:
2927 /* An ADDR_VEC is placed outside any basic block. */
2928 if (NEXT_INSN (x)
2929 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
2930 x = NEXT_INSN (x);
2932 /* But in any case, non-deletable labels can appear anywhere. */
2933 break;
2935 default:
2936 fatal_insn ("insn outside basic block", x);
2940 if (JUMP_P (x)
2941 && returnjump_p (x) && ! condjump_p (x)
2942 && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_insn (x))))
2943 fatal_insn ("return not followed by barrier", x);
2945 if (curr_bb && x == BB_END (curr_bb))
2946 curr_bb = NULL;
2949 if (num_bb_notes != n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS)
2950 internal_error
2951 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2952 num_bb_notes, n_basic_blocks_for_fn (cfun));
2954 return err;
2957 /* Verify the CFG and RTL consistency common for both underlying RTL and
2958 cfglayout RTL, plus consistency checks specific to linearized RTL mode.
2960 Currently it does following checks:
2961 - all checks of rtl_verify_flow_info_1
2962 - test head/end pointers
2963 - check that blocks are laid out in consecutive order
2964 - check that all insns are in the basic blocks
2965 (except the switch handling code, barriers and notes)
2966 - check that all returns are followed by barriers
2967 - check that all fallthru edge points to the adjacent blocks
2968 - verify that there is a single hot/cold partition boundary after bbro */
2970 static int
2971 rtl_verify_flow_info (void)
2973 int err = 0;
2975 err |= rtl_verify_flow_info_1 ();
2977 err |= rtl_verify_bb_insn_chain ();
2979 err |= rtl_verify_fallthru ();
2981 err |= rtl_verify_bb_layout ();
2983 err |= verify_hot_cold_block_grouping ();
2985 return err;
2988 /* Assume that the preceding pass has possibly eliminated jump instructions
2989 or converted the unconditional jumps. Eliminate the edges from CFG.
2990 Return true if any edges are eliminated. */
2992 bool
2993 purge_dead_edges (basic_block bb)
2995 edge e;
2996 rtx_insn *insn = BB_END (bb);
2997 rtx note;
2998 bool purged = false;
2999 bool found;
3000 edge_iterator ei;
3002 if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb))
3004 insn = PREV_INSN (insn);
3005 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
3007 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
3008 if (NONJUMP_INSN_P (insn)
3009 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
3011 rtx eqnote;
3013 if (! may_trap_p (PATTERN (insn))
3014 || ((eqnote = find_reg_equal_equiv_note (insn))
3015 && ! may_trap_p (XEXP (eqnote, 0))))
3016 remove_note (insn, note);
3019 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
3020 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3022 bool remove = false;
3024 /* There are three types of edges we need to handle correctly here: EH
3025 edges, abnormal call EH edges, and abnormal call non-EH edges. The
3026 latter can appear when nonlocal gotos are used. */
3027 if (e->flags & EDGE_ABNORMAL_CALL)
3029 if (!CALL_P (insn))
3030 remove = true;
3031 else if (can_nonlocal_goto (insn))
3033 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3035 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
3037 else
3038 remove = true;
3040 else if (e->flags & EDGE_EH)
3041 remove = !can_throw_internal (insn);
3043 if (remove)
3045 remove_edge (e);
3046 df_set_bb_dirty (bb);
3047 purged = true;
3049 else
3050 ei_next (&ei);
3053 if (JUMP_P (insn))
3055 rtx note;
3056 edge b,f;
3057 edge_iterator ei;
3059 /* We do care only about conditional jumps and simplejumps. */
3060 if (!any_condjump_p (insn)
3061 && !returnjump_p (insn)
3062 && !simplejump_p (insn))
3063 return purged;
3065 /* Branch probability/prediction notes are defined only for
3066 condjumps. We've possibly turned condjump into simplejump. */
3067 if (simplejump_p (insn))
3069 note = find_reg_note (insn, REG_BR_PROB, NULL);
3070 if (note)
3071 remove_note (insn, note);
3072 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
3073 remove_note (insn, note);
3076 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3078 /* Avoid abnormal flags to leak from computed jumps turned
3079 into simplejumps. */
3081 e->flags &= ~EDGE_ABNORMAL;
3083 /* See if this edge is one we should keep. */
3084 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
3085 /* A conditional jump can fall through into the next
3086 block, so we should keep the edge. */
3088 ei_next (&ei);
3089 continue;
3091 else if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
3092 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
3093 /* If the destination block is the target of the jump,
3094 keep the edge. */
3096 ei_next (&ei);
3097 continue;
3099 else if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun)
3100 && returnjump_p (insn))
3101 /* If the destination block is the exit block, and this
3102 instruction is a return, then keep the edge. */
3104 ei_next (&ei);
3105 continue;
3107 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
3108 /* Keep the edges that correspond to exceptions thrown by
3109 this instruction and rematerialize the EDGE_ABNORMAL
3110 flag we just cleared above. */
3112 e->flags |= EDGE_ABNORMAL;
3113 ei_next (&ei);
3114 continue;
3117 /* We do not need this edge. */
3118 df_set_bb_dirty (bb);
3119 purged = true;
3120 remove_edge (e);
3123 if (EDGE_COUNT (bb->succs) == 0 || !purged)
3124 return purged;
3126 if (dump_file)
3127 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
3129 if (!optimize)
3130 return purged;
3132 /* Redistribute probabilities. */
3133 if (single_succ_p (bb))
3135 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3136 single_succ_edge (bb)->count = bb->count;
3138 else
3140 note = find_reg_note (insn, REG_BR_PROB, NULL);
3141 if (!note)
3142 return purged;
3144 b = BRANCH_EDGE (bb);
3145 f = FALLTHRU_EDGE (bb);
3146 b->probability = XINT (note, 0);
3147 f->probability = REG_BR_PROB_BASE - b->probability;
3148 /* Update these to use GCOV_COMPUTE_SCALE. */
3149 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
3150 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
3153 return purged;
3155 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
3157 /* First, there should not be any EH or ABCALL edges resulting
3158 from non-local gotos and the like. If there were, we shouldn't
3159 have created the sibcall in the first place. Second, there
3160 should of course never have been a fallthru edge. */
3161 gcc_assert (single_succ_p (bb));
3162 gcc_assert (single_succ_edge (bb)->flags
3163 == (EDGE_SIBCALL | EDGE_ABNORMAL));
3165 return 0;
3168 /* If we don't see a jump insn, we don't know exactly why the block would
3169 have been broken at this point. Look for a simple, non-fallthru edge,
3170 as these are only created by conditional branches. If we find such an
3171 edge we know that there used to be a jump here and can then safely
3172 remove all non-fallthru edges. */
3173 found = false;
3174 FOR_EACH_EDGE (e, ei, bb->succs)
3175 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
3177 found = true;
3178 break;
3181 if (!found)
3182 return purged;
3184 /* Remove all but the fake and fallthru edges. The fake edge may be
3185 the only successor for this block in the case of noreturn
3186 calls. */
3187 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
3189 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
3191 df_set_bb_dirty (bb);
3192 remove_edge (e);
3193 purged = true;
3195 else
3196 ei_next (&ei);
3199 gcc_assert (single_succ_p (bb));
3201 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
3202 single_succ_edge (bb)->count = bb->count;
3204 if (dump_file)
3205 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
3206 bb->index);
3207 return purged;
3210 /* Search all basic blocks for potentially dead edges and purge them. Return
3211 true if some edge has been eliminated. */
3213 bool
3214 purge_all_dead_edges (void)
3216 int purged = false;
3217 basic_block bb;
3219 FOR_EACH_BB_FN (bb, cfun)
3221 bool purged_here = purge_dead_edges (bb);
3223 purged |= purged_here;
3226 return purged;
3229 /* This is used by a few passes that emit some instructions after abnormal
3230 calls, moving the basic block's end, while they in fact do want to emit
3231 them on the fallthru edge. Look for abnormal call edges, find backward
3232 the call in the block and insert the instructions on the edge instead.
3234 Similarly, handle instructions throwing exceptions internally.
3236 Return true when instructions have been found and inserted on edges. */
3238 bool
3239 fixup_abnormal_edges (void)
3241 bool inserted = false;
3242 basic_block bb;
3244 FOR_EACH_BB_FN (bb, cfun)
3246 edge e;
3247 edge_iterator ei;
3249 /* Look for cases we are interested in - calls or instructions causing
3250 exceptions. */
3251 FOR_EACH_EDGE (e, ei, bb->succs)
3252 if ((e->flags & EDGE_ABNORMAL_CALL)
3253 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
3254 == (EDGE_ABNORMAL | EDGE_EH)))
3255 break;
3257 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
3259 rtx_insn *insn;
3261 /* Get past the new insns generated. Allow notes, as the insns
3262 may be already deleted. */
3263 insn = BB_END (bb);
3264 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
3265 && !can_throw_internal (insn)
3266 && insn != BB_HEAD (bb))
3267 insn = PREV_INSN (insn);
3269 if (CALL_P (insn) || can_throw_internal (insn))
3271 rtx_insn *stop, *next;
3273 e = find_fallthru_edge (bb->succs);
3275 stop = NEXT_INSN (BB_END (bb));
3276 BB_END (bb) = insn;
3278 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
3280 next = NEXT_INSN (insn);
3281 if (INSN_P (insn))
3283 delete_insn (insn);
3285 /* Sometimes there's still the return value USE.
3286 If it's placed after a trapping call (i.e. that
3287 call is the last insn anyway), we have no fallthru
3288 edge. Simply delete this use and don't try to insert
3289 on the non-existent edge. */
3290 if (GET_CODE (PATTERN (insn)) != USE)
3292 /* We're not deleting it, we're moving it. */
3293 insn->set_undeleted ();
3294 SET_PREV_INSN (insn) = NULL_RTX;
3295 SET_NEXT_INSN (insn) = NULL_RTX;
3297 insert_insn_on_edge (insn, e);
3298 inserted = true;
3301 else if (!BARRIER_P (insn))
3302 set_block_for_insn (insn, NULL);
3306 /* It may be that we don't find any trapping insn. In this
3307 case we discovered quite late that the insn that had been
3308 marked as can_throw_internal in fact couldn't trap at all.
3309 So we should in fact delete the EH edges out of the block. */
3310 else
3311 purge_dead_edges (bb);
3315 return inserted;
3318 /* Cut the insns from FIRST to LAST out of the insns stream. */
3320 rtx_insn *
3321 unlink_insn_chain (rtx_insn *first, rtx_insn *last)
3323 rtx_insn *prevfirst = PREV_INSN (first);
3324 rtx_insn *nextlast = NEXT_INSN (last);
3326 SET_PREV_INSN (first) = NULL;
3327 SET_NEXT_INSN (last) = NULL;
3328 if (prevfirst)
3329 SET_NEXT_INSN (prevfirst) = nextlast;
3330 if (nextlast)
3331 SET_PREV_INSN (nextlast) = prevfirst;
3332 else
3333 set_last_insn (prevfirst);
3334 if (!prevfirst)
3335 set_first_insn (nextlast);
3336 return first;
3339 /* Skip over inter-block insns occurring after BB which are typically
3340 associated with BB (e.g., barriers). If there are any such insns,
3341 we return the last one. Otherwise, we return the end of BB. */
3343 static rtx_insn *
3344 skip_insns_after_block (basic_block bb)
3346 rtx_insn *insn, *last_insn, *next_head, *prev;
3348 next_head = NULL;
3349 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3350 next_head = BB_HEAD (bb->next_bb);
3352 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
3354 if (insn == next_head)
3355 break;
3357 switch (GET_CODE (insn))
3359 case BARRIER:
3360 last_insn = insn;
3361 continue;
3363 case NOTE:
3364 switch (NOTE_KIND (insn))
3366 case NOTE_INSN_BLOCK_END:
3367 gcc_unreachable ();
3368 continue;
3369 default:
3370 continue;
3371 break;
3373 break;
3375 case CODE_LABEL:
3376 if (NEXT_INSN (insn)
3377 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
3379 insn = NEXT_INSN (insn);
3380 last_insn = insn;
3381 continue;
3383 break;
3385 default:
3386 break;
3389 break;
3392 /* It is possible to hit contradictory sequence. For instance:
3394 jump_insn
3395 NOTE_INSN_BLOCK_BEG
3396 barrier
3398 Where barrier belongs to jump_insn, but the note does not. This can be
3399 created by removing the basic block originally following
3400 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
3402 for (insn = last_insn; insn != BB_END (bb); insn = prev)
3404 prev = PREV_INSN (insn);
3405 if (NOTE_P (insn))
3406 switch (NOTE_KIND (insn))
3408 case NOTE_INSN_BLOCK_END:
3409 gcc_unreachable ();
3410 break;
3411 case NOTE_INSN_DELETED:
3412 case NOTE_INSN_DELETED_LABEL:
3413 case NOTE_INSN_DELETED_DEBUG_LABEL:
3414 continue;
3415 default:
3416 reorder_insns (insn, insn, last_insn);
3420 return last_insn;
3423 /* Locate or create a label for a given basic block. */
3425 static rtx
3426 label_for_bb (basic_block bb)
3428 rtx label = BB_HEAD (bb);
3430 if (!LABEL_P (label))
3432 if (dump_file)
3433 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
3435 label = block_label (bb);
3438 return label;
3441 /* Locate the effective beginning and end of the insn chain for each
3442 block, as defined by skip_insns_after_block above. */
3444 static void
3445 record_effective_endpoints (void)
3447 rtx_insn *next_insn;
3448 basic_block bb;
3449 rtx_insn *insn;
3451 for (insn = get_insns ();
3452 insn
3453 && NOTE_P (insn)
3454 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
3455 insn = NEXT_INSN (insn))
3456 continue;
3457 /* No basic blocks at all? */
3458 gcc_assert (insn);
3460 if (PREV_INSN (insn))
3461 cfg_layout_function_header =
3462 unlink_insn_chain (get_insns (), PREV_INSN (insn));
3463 else
3464 cfg_layout_function_header = NULL;
3466 next_insn = get_insns ();
3467 FOR_EACH_BB_FN (bb, cfun)
3469 rtx_insn *end;
3471 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
3472 BB_HEADER (bb) = unlink_insn_chain (next_insn,
3473 PREV_INSN (BB_HEAD (bb)));
3474 end = skip_insns_after_block (bb);
3475 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
3476 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
3477 next_insn = NEXT_INSN (BB_END (bb));
3480 cfg_layout_function_footer = next_insn;
3481 if (cfg_layout_function_footer)
3482 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
3485 namespace {
3487 const pass_data pass_data_into_cfg_layout_mode =
3489 RTL_PASS, /* type */
3490 "into_cfglayout", /* name */
3491 OPTGROUP_NONE, /* optinfo_flags */
3492 TV_CFG, /* tv_id */
3493 0, /* properties_required */
3494 PROP_cfglayout, /* properties_provided */
3495 0, /* properties_destroyed */
3496 0, /* todo_flags_start */
3497 0, /* todo_flags_finish */
3500 class pass_into_cfg_layout_mode : public rtl_opt_pass
3502 public:
3503 pass_into_cfg_layout_mode (gcc::context *ctxt)
3504 : rtl_opt_pass (pass_data_into_cfg_layout_mode, ctxt)
3507 /* opt_pass methods: */
3508 virtual unsigned int execute (function *)
3510 cfg_layout_initialize (0);
3511 return 0;
3514 }; // class pass_into_cfg_layout_mode
3516 } // anon namespace
3518 rtl_opt_pass *
3519 make_pass_into_cfg_layout_mode (gcc::context *ctxt)
3521 return new pass_into_cfg_layout_mode (ctxt);
3524 namespace {
3526 const pass_data pass_data_outof_cfg_layout_mode =
3528 RTL_PASS, /* type */
3529 "outof_cfglayout", /* name */
3530 OPTGROUP_NONE, /* optinfo_flags */
3531 TV_CFG, /* tv_id */
3532 0, /* properties_required */
3533 0, /* properties_provided */
3534 PROP_cfglayout, /* properties_destroyed */
3535 0, /* todo_flags_start */
3536 0, /* todo_flags_finish */
3539 class pass_outof_cfg_layout_mode : public rtl_opt_pass
3541 public:
3542 pass_outof_cfg_layout_mode (gcc::context *ctxt)
3543 : rtl_opt_pass (pass_data_outof_cfg_layout_mode, ctxt)
3546 /* opt_pass methods: */
3547 virtual unsigned int execute (function *);
3549 }; // class pass_outof_cfg_layout_mode
3551 unsigned int
3552 pass_outof_cfg_layout_mode::execute (function *fun)
3554 basic_block bb;
3556 FOR_EACH_BB_FN (bb, fun)
3557 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (fun))
3558 bb->aux = bb->next_bb;
3560 cfg_layout_finalize ();
3562 return 0;
3565 } // anon namespace
3567 rtl_opt_pass *
3568 make_pass_outof_cfg_layout_mode (gcc::context *ctxt)
3570 return new pass_outof_cfg_layout_mode (ctxt);
3574 /* Link the basic blocks in the correct order, compacting the basic
3575 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3576 function also clears the basic block header and footer fields.
3578 This function is usually called after a pass (e.g. tracer) finishes
3579 some transformations while in cfglayout mode. The required sequence
3580 of the basic blocks is in a linked list along the bb->aux field.
3581 This functions re-links the basic block prev_bb and next_bb pointers
3582 accordingly, and it compacts and renumbers the blocks.
3584 FIXME: This currently works only for RTL, but the only RTL-specific
3585 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3586 to GIMPLE a long time ago, but it doesn't relink the basic block
3587 chain. It could do that (to give better initial RTL) if this function
3588 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3590 void
3591 relink_block_chain (bool stay_in_cfglayout_mode)
3593 basic_block bb, prev_bb;
3594 int index;
3596 /* Maybe dump the re-ordered sequence. */
3597 if (dump_file)
3599 fprintf (dump_file, "Reordered sequence:\n");
3600 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb, index =
3601 NUM_FIXED_BLOCKS;
3603 bb = (basic_block) bb->aux, index++)
3605 fprintf (dump_file, " %i ", index);
3606 if (get_bb_original (bb))
3607 fprintf (dump_file, "duplicate of %i ",
3608 get_bb_original (bb)->index);
3609 else if (forwarder_block_p (bb)
3610 && !LABEL_P (BB_HEAD (bb)))
3611 fprintf (dump_file, "compensation ");
3612 else
3613 fprintf (dump_file, "bb %i ", bb->index);
3614 fprintf (dump_file, " [%i]\n", bb->frequency);
3618 /* Now reorder the blocks. */
3619 prev_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
3620 bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3621 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3623 bb->prev_bb = prev_bb;
3624 prev_bb->next_bb = bb;
3626 prev_bb->next_bb = EXIT_BLOCK_PTR_FOR_FN (cfun);
3627 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb = prev_bb;
3629 /* Then, clean up the aux fields. */
3630 FOR_ALL_BB_FN (bb, cfun)
3632 bb->aux = NULL;
3633 if (!stay_in_cfglayout_mode)
3634 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3637 /* Maybe reset the original copy tables, they are not valid anymore
3638 when we renumber the basic blocks in compact_blocks. If we are
3639 are going out of cfglayout mode, don't re-allocate the tables. */
3640 free_original_copy_tables ();
3641 if (stay_in_cfglayout_mode)
3642 initialize_original_copy_tables ();
3644 /* Finally, put basic_block_info in the new order. */
3645 compact_blocks ();
3649 /* Given a reorder chain, rearrange the code to match. */
3651 static void
3652 fixup_reorder_chain (void)
3654 basic_block bb;
3655 rtx_insn *insn = NULL;
3657 if (cfg_layout_function_header)
3659 set_first_insn (cfg_layout_function_header);
3660 insn = cfg_layout_function_header;
3661 while (NEXT_INSN (insn))
3662 insn = NEXT_INSN (insn);
3665 /* First do the bulk reordering -- rechain the blocks without regard to
3666 the needed changes to jumps and labels. */
3668 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb; bb = (basic_block)
3669 bb->aux)
3671 if (BB_HEADER (bb))
3673 if (insn)
3674 SET_NEXT_INSN (insn) = BB_HEADER (bb);
3675 else
3676 set_first_insn (BB_HEADER (bb));
3677 SET_PREV_INSN (BB_HEADER (bb)) = insn;
3678 insn = BB_HEADER (bb);
3679 while (NEXT_INSN (insn))
3680 insn = NEXT_INSN (insn);
3682 if (insn)
3683 SET_NEXT_INSN (insn) = BB_HEAD (bb);
3684 else
3685 set_first_insn (BB_HEAD (bb));
3686 SET_PREV_INSN (BB_HEAD (bb)) = insn;
3687 insn = BB_END (bb);
3688 if (BB_FOOTER (bb))
3690 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
3691 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
3692 while (NEXT_INSN (insn))
3693 insn = NEXT_INSN (insn);
3697 SET_NEXT_INSN (insn) = cfg_layout_function_footer;
3698 if (cfg_layout_function_footer)
3699 SET_PREV_INSN (cfg_layout_function_footer) = insn;
3701 while (NEXT_INSN (insn))
3702 insn = NEXT_INSN (insn);
3704 set_last_insn (insn);
3705 #ifdef ENABLE_CHECKING
3706 verify_insn_chain ();
3707 #endif
3709 /* Now add jumps and labels as needed to match the blocks new
3710 outgoing edges. */
3712 for (bb = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; bb ; bb = (basic_block)
3713 bb->aux)
3715 edge e_fall, e_taken, e;
3716 rtx_insn *bb_end_insn;
3717 rtx ret_label = NULL_RTX;
3718 basic_block nb;
3719 edge_iterator ei;
3721 if (EDGE_COUNT (bb->succs) == 0)
3722 continue;
3724 /* Find the old fallthru edge, and another non-EH edge for
3725 a taken jump. */
3726 e_taken = e_fall = NULL;
3728 FOR_EACH_EDGE (e, ei, bb->succs)
3729 if (e->flags & EDGE_FALLTHRU)
3730 e_fall = e;
3731 else if (! (e->flags & EDGE_EH))
3732 e_taken = e;
3734 bb_end_insn = BB_END (bb);
3735 if (JUMP_P (bb_end_insn))
3737 ret_label = JUMP_LABEL (bb_end_insn);
3738 if (any_condjump_p (bb_end_insn))
3740 /* This might happen if the conditional jump has side
3741 effects and could therefore not be optimized away.
3742 Make the basic block to end with a barrier in order
3743 to prevent rtl_verify_flow_info from complaining. */
3744 if (!e_fall)
3746 gcc_assert (!onlyjump_p (bb_end_insn)
3747 || returnjump_p (bb_end_insn)
3748 || (e_taken->flags & EDGE_CROSSING));
3749 emit_barrier_after (bb_end_insn);
3750 continue;
3753 /* If the old fallthru is still next, nothing to do. */
3754 if (bb->aux == e_fall->dest
3755 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3756 continue;
3758 /* The degenerated case of conditional jump jumping to the next
3759 instruction can happen for jumps with side effects. We need
3760 to construct a forwarder block and this will be done just
3761 fine by force_nonfallthru below. */
3762 if (!e_taken)
3765 /* There is another special case: if *neither* block is next,
3766 such as happens at the very end of a function, then we'll
3767 need to add a new unconditional jump. Choose the taken
3768 edge based on known or assumed probability. */
3769 else if (bb->aux != e_taken->dest)
3771 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
3773 if (note
3774 && XINT (note, 0) < REG_BR_PROB_BASE / 2
3775 && invert_jump (bb_end_insn,
3776 (e_fall->dest
3777 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3778 ? NULL_RTX
3779 : label_for_bb (e_fall->dest)), 0))
3781 e_fall->flags &= ~EDGE_FALLTHRU;
3782 gcc_checking_assert (could_fall_through
3783 (e_taken->src, e_taken->dest));
3784 e_taken->flags |= EDGE_FALLTHRU;
3785 update_br_prob_note (bb);
3786 e = e_fall, e_fall = e_taken, e_taken = e;
3790 /* If the "jumping" edge is a crossing edge, and the fall
3791 through edge is non-crossing, leave things as they are. */
3792 else if ((e_taken->flags & EDGE_CROSSING)
3793 && !(e_fall->flags & EDGE_CROSSING))
3794 continue;
3796 /* Otherwise we can try to invert the jump. This will
3797 basically never fail, however, keep up the pretense. */
3798 else if (invert_jump (bb_end_insn,
3799 (e_fall->dest
3800 == EXIT_BLOCK_PTR_FOR_FN (cfun)
3801 ? NULL_RTX
3802 : label_for_bb (e_fall->dest)), 0))
3804 e_fall->flags &= ~EDGE_FALLTHRU;
3805 gcc_checking_assert (could_fall_through
3806 (e_taken->src, e_taken->dest));
3807 e_taken->flags |= EDGE_FALLTHRU;
3808 update_br_prob_note (bb);
3809 if (LABEL_NUSES (ret_label) == 0
3810 && single_pred_p (e_taken->dest))
3811 delete_insn (ret_label);
3812 continue;
3815 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
3817 /* If the old fallthru is still next or if
3818 asm goto doesn't have a fallthru (e.g. when followed by
3819 __builtin_unreachable ()), nothing to do. */
3820 if (! e_fall
3821 || bb->aux == e_fall->dest
3822 || e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3823 continue;
3825 /* Otherwise we'll have to use the fallthru fixup below. */
3827 else
3829 /* Otherwise we have some return, switch or computed
3830 jump. In the 99% case, there should not have been a
3831 fallthru edge. */
3832 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
3833 continue;
3836 else
3838 /* No fallthru implies a noreturn function with EH edges, or
3839 something similarly bizarre. In any case, we don't need to
3840 do anything. */
3841 if (! e_fall)
3842 continue;
3844 /* If the fallthru block is still next, nothing to do. */
3845 if (bb->aux == e_fall->dest)
3846 continue;
3848 /* A fallthru to exit block. */
3849 if (e_fall->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3850 continue;
3853 /* We got here if we need to add a new jump insn.
3854 Note force_nonfallthru can delete E_FALL and thus we have to
3855 save E_FALL->src prior to the call to force_nonfallthru. */
3856 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
3857 if (nb)
3859 nb->aux = bb->aux;
3860 bb->aux = nb;
3861 /* Don't process this new block. */
3862 bb = nb;
3866 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3868 /* Annoying special case - jump around dead jumptables left in the code. */
3869 FOR_EACH_BB_FN (bb, cfun)
3871 edge e = find_fallthru_edge (bb->succs);
3873 if (e && !can_fallthru (e->src, e->dest))
3874 force_nonfallthru (e);
3877 /* Ensure goto_locus from edges has some instructions with that locus
3878 in RTL. */
3879 if (!optimize)
3880 FOR_EACH_BB_FN (bb, cfun)
3882 edge e;
3883 edge_iterator ei;
3885 FOR_EACH_EDGE (e, ei, bb->succs)
3886 if (LOCATION_LOCUS (e->goto_locus) != UNKNOWN_LOCATION
3887 && !(e->flags & EDGE_ABNORMAL))
3889 edge e2;
3890 edge_iterator ei2;
3891 basic_block dest, nb;
3892 rtx_insn *end;
3894 insn = BB_END (e->src);
3895 end = PREV_INSN (BB_HEAD (e->src));
3896 while (insn != end
3897 && (!NONDEBUG_INSN_P (insn) || !INSN_HAS_LOCATION (insn)))
3898 insn = PREV_INSN (insn);
3899 if (insn != end
3900 && INSN_LOCATION (insn) == e->goto_locus)
3901 continue;
3902 if (simplejump_p (BB_END (e->src))
3903 && !INSN_HAS_LOCATION (BB_END (e->src)))
3905 INSN_LOCATION (BB_END (e->src)) = e->goto_locus;
3906 continue;
3908 dest = e->dest;
3909 if (dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
3911 /* Non-fallthru edges to the exit block cannot be split. */
3912 if (!(e->flags & EDGE_FALLTHRU))
3913 continue;
3915 else
3917 insn = BB_HEAD (dest);
3918 end = NEXT_INSN (BB_END (dest));
3919 while (insn != end && !NONDEBUG_INSN_P (insn))
3920 insn = NEXT_INSN (insn);
3921 if (insn != end && INSN_HAS_LOCATION (insn)
3922 && INSN_LOCATION (insn) == e->goto_locus)
3923 continue;
3925 nb = split_edge (e);
3926 if (!INSN_P (BB_END (nb)))
3927 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
3928 nb);
3929 INSN_LOCATION (BB_END (nb)) = e->goto_locus;
3931 /* If there are other incoming edges to the destination block
3932 with the same goto locus, redirect them to the new block as
3933 well, this can prevent other such blocks from being created
3934 in subsequent iterations of the loop. */
3935 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
3936 if (LOCATION_LOCUS (e2->goto_locus) != UNKNOWN_LOCATION
3937 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
3938 && e->goto_locus == e2->goto_locus)
3939 redirect_edge_and_branch (e2, nb);
3940 else
3941 ei_next (&ei2);
3946 /* Perform sanity checks on the insn chain.
3947 1. Check that next/prev pointers are consistent in both the forward and
3948 reverse direction.
3949 2. Count insns in chain, going both directions, and check if equal.
3950 3. Check that get_last_insn () returns the actual end of chain. */
3952 DEBUG_FUNCTION void
3953 verify_insn_chain (void)
3955 rtx_insn *x, *prevx, *nextx;
3956 int insn_cnt1, insn_cnt2;
3958 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
3959 x != 0;
3960 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
3961 gcc_assert (PREV_INSN (x) == prevx);
3963 gcc_assert (prevx == get_last_insn ());
3965 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
3966 x != 0;
3967 nextx = x, insn_cnt2++, x = PREV_INSN (x))
3968 gcc_assert (NEXT_INSN (x) == nextx);
3970 gcc_assert (insn_cnt1 == insn_cnt2);
3973 /* If we have assembler epilogues, the block falling through to exit must
3974 be the last one in the reordered chain when we reach final. Ensure
3975 that this condition is met. */
3976 static void
3977 fixup_fallthru_exit_predecessor (void)
3979 edge e;
3980 basic_block bb = NULL;
3982 /* This transformation is not valid before reload, because we might
3983 separate a call from the instruction that copies the return
3984 value. */
3985 gcc_assert (reload_completed);
3987 e = find_fallthru_edge (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
3988 if (e)
3989 bb = e->src;
3991 if (bb && bb->aux)
3993 basic_block c = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb;
3995 /* If the very first block is the one with the fall-through exit
3996 edge, we have to split that block. */
3997 if (c == bb)
3999 bb = split_block (bb, NULL)->dest;
4000 bb->aux = c->aux;
4001 c->aux = bb;
4002 BB_FOOTER (bb) = BB_FOOTER (c);
4003 BB_FOOTER (c) = NULL;
4006 while (c->aux != bb)
4007 c = (basic_block) c->aux;
4009 c->aux = bb->aux;
4010 while (c->aux)
4011 c = (basic_block) c->aux;
4013 c->aux = bb;
4014 bb->aux = NULL;
4018 /* In case there are more than one fallthru predecessors of exit, force that
4019 there is only one. */
4021 static void
4022 force_one_exit_fallthru (void)
4024 edge e, predecessor = NULL;
4025 bool more = false;
4026 edge_iterator ei;
4027 basic_block forwarder, bb;
4029 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR_FOR_FN (cfun)->preds)
4030 if (e->flags & EDGE_FALLTHRU)
4032 if (predecessor == NULL)
4033 predecessor = e;
4034 else
4036 more = true;
4037 break;
4041 if (!more)
4042 return;
4044 /* Exit has several fallthru predecessors. Create a forwarder block for
4045 them. */
4046 forwarder = split_edge (predecessor);
4047 for (ei = ei_start (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds);
4048 (e = ei_safe_edge (ei)); )
4050 if (e->src == forwarder
4051 || !(e->flags & EDGE_FALLTHRU))
4052 ei_next (&ei);
4053 else
4054 redirect_edge_and_branch_force (e, forwarder);
4057 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
4058 exit block. */
4059 FOR_EACH_BB_FN (bb, cfun)
4061 if (bb->aux == NULL && bb != forwarder)
4063 bb->aux = forwarder;
4064 break;
4069 /* Return true in case it is possible to duplicate the basic block BB. */
4071 static bool
4072 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
4074 /* Do not attempt to duplicate tablejumps, as we need to unshare
4075 the dispatch table. This is difficult to do, as the instructions
4076 computing jump destination may be hoisted outside the basic block. */
4077 if (tablejump_p (BB_END (bb), NULL, NULL))
4078 return false;
4080 /* Do not duplicate blocks containing insns that can't be copied. */
4081 if (targetm.cannot_copy_insn_p)
4083 rtx_insn *insn = BB_HEAD (bb);
4084 while (1)
4086 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
4087 return false;
4088 if (insn == BB_END (bb))
4089 break;
4090 insn = NEXT_INSN (insn);
4094 return true;
4097 rtx_insn *
4098 duplicate_insn_chain (rtx_insn *from, rtx_insn *to)
4100 rtx_insn *insn, *next, *copy;
4101 rtx_note *last;
4103 /* Avoid updating of boundaries of previous basic block. The
4104 note will get removed from insn stream in fixup. */
4105 last = emit_note (NOTE_INSN_DELETED);
4107 /* Create copy at the end of INSN chain. The chain will
4108 be reordered later. */
4109 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
4111 switch (GET_CODE (insn))
4113 case DEBUG_INSN:
4114 /* Don't duplicate label debug insns. */
4115 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
4116 break;
4117 /* FALLTHRU */
4118 case INSN:
4119 case CALL_INSN:
4120 case JUMP_INSN:
4121 copy = emit_copy_of_insn_after (insn, get_last_insn ());
4122 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
4123 && ANY_RETURN_P (JUMP_LABEL (insn)))
4124 JUMP_LABEL (copy) = JUMP_LABEL (insn);
4125 maybe_copy_prologue_epilogue_insn (insn, copy);
4126 break;
4128 case JUMP_TABLE_DATA:
4129 /* Avoid copying of dispatch tables. We never duplicate
4130 tablejumps, so this can hit only in case the table got
4131 moved far from original jump.
4132 Avoid copying following barrier as well if any
4133 (and debug insns in between). */
4134 for (next = NEXT_INSN (insn);
4135 next != NEXT_INSN (to);
4136 next = NEXT_INSN (next))
4137 if (!DEBUG_INSN_P (next))
4138 break;
4139 if (next != NEXT_INSN (to) && BARRIER_P (next))
4140 insn = next;
4141 break;
4143 case CODE_LABEL:
4144 break;
4146 case BARRIER:
4147 emit_barrier ();
4148 break;
4150 case NOTE:
4151 switch (NOTE_KIND (insn))
4153 /* In case prologue is empty and function contain label
4154 in first BB, we may want to copy the block. */
4155 case NOTE_INSN_PROLOGUE_END:
4157 case NOTE_INSN_DELETED:
4158 case NOTE_INSN_DELETED_LABEL:
4159 case NOTE_INSN_DELETED_DEBUG_LABEL:
4160 /* No problem to strip these. */
4161 case NOTE_INSN_FUNCTION_BEG:
4162 /* There is always just single entry to function. */
4163 case NOTE_INSN_BASIC_BLOCK:
4164 /* We should only switch text sections once. */
4165 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
4166 break;
4168 case NOTE_INSN_EPILOGUE_BEG:
4169 emit_note_copy (as_a <rtx_note *> (insn));
4170 break;
4172 default:
4173 /* All other notes should have already been eliminated. */
4174 gcc_unreachable ();
4176 break;
4177 default:
4178 gcc_unreachable ();
4181 insn = NEXT_INSN (last);
4182 delete_insn (last);
4183 return insn;
4186 /* Create a duplicate of the basic block BB. */
4188 static basic_block
4189 cfg_layout_duplicate_bb (basic_block bb)
4191 rtx_insn *insn;
4192 basic_block new_bb;
4194 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
4195 new_bb = create_basic_block (insn,
4196 insn ? get_last_insn () : NULL,
4197 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
4199 BB_COPY_PARTITION (new_bb, bb);
4200 if (BB_HEADER (bb))
4202 insn = BB_HEADER (bb);
4203 while (NEXT_INSN (insn))
4204 insn = NEXT_INSN (insn);
4205 insn = duplicate_insn_chain (BB_HEADER (bb), insn);
4206 if (insn)
4207 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4210 if (BB_FOOTER (bb))
4212 insn = BB_FOOTER (bb);
4213 while (NEXT_INSN (insn))
4214 insn = NEXT_INSN (insn);
4215 insn = duplicate_insn_chain (BB_FOOTER (bb), insn);
4216 if (insn)
4217 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
4220 return new_bb;
4224 /* Main entry point to this module - initialize the datastructures for
4225 CFG layout changes. It keeps LOOPS up-to-date if not null.
4227 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
4229 void
4230 cfg_layout_initialize (unsigned int flags)
4232 rtx_insn_list *x;
4233 basic_block bb;
4235 /* Once bb partitioning is complete, cfg layout mode should not be
4236 re-entered. Entering cfg layout mode may require fixups. As an
4237 example, if edge forwarding performed when optimizing the cfg
4238 layout required moving a block from the hot to the cold
4239 section. This would create an illegal partitioning unless some
4240 manual fixup was performed. */
4241 gcc_assert (!(crtl->bb_reorder_complete
4242 && flag_reorder_blocks_and_partition));
4244 initialize_original_copy_tables ();
4246 cfg_layout_rtl_register_cfg_hooks ();
4248 record_effective_endpoints ();
4250 /* Make sure that the targets of non local gotos are marked. */
4251 for (x = nonlocal_goto_handler_labels; x; x = x->next ())
4253 bb = BLOCK_FOR_INSN (x->insn ());
4254 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
4257 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
4260 /* Splits superblocks. */
4261 void
4262 break_superblocks (void)
4264 sbitmap superblocks;
4265 bool need = false;
4266 basic_block bb;
4268 superblocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
4269 bitmap_clear (superblocks);
4271 FOR_EACH_BB_FN (bb, cfun)
4272 if (bb->flags & BB_SUPERBLOCK)
4274 bb->flags &= ~BB_SUPERBLOCK;
4275 bitmap_set_bit (superblocks, bb->index);
4276 need = true;
4279 if (need)
4281 rebuild_jump_labels (get_insns ());
4282 find_many_sub_basic_blocks (superblocks);
4285 free (superblocks);
4288 /* Finalize the changes: reorder insn list according to the sequence specified
4289 by aux pointers, enter compensation code, rebuild scope forest. */
4291 void
4292 cfg_layout_finalize (void)
4294 #ifdef ENABLE_CHECKING
4295 verify_flow_info ();
4296 #endif
4297 force_one_exit_fallthru ();
4298 rtl_register_cfg_hooks ();
4299 if (reload_completed
4300 #ifdef HAVE_epilogue
4301 && !HAVE_epilogue
4302 #endif
4304 fixup_fallthru_exit_predecessor ();
4305 fixup_reorder_chain ();
4307 rebuild_jump_labels (get_insns ());
4308 delete_dead_jumptables ();
4310 #ifdef ENABLE_CHECKING
4311 verify_insn_chain ();
4312 verify_flow_info ();
4313 #endif
4317 /* Same as split_block but update cfg_layout structures. */
4319 static basic_block
4320 cfg_layout_split_block (basic_block bb, void *insnp)
4322 rtx insn = (rtx) insnp;
4323 basic_block new_bb = rtl_split_block (bb, insn);
4325 BB_FOOTER (new_bb) = BB_FOOTER (bb);
4326 BB_FOOTER (bb) = NULL;
4328 return new_bb;
4331 /* Redirect Edge to DEST. */
4332 static edge
4333 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
4335 basic_block src = e->src;
4336 edge ret;
4338 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4339 return NULL;
4341 if (e->dest == dest)
4342 return e;
4344 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4345 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
4347 df_set_bb_dirty (src);
4348 return ret;
4351 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4352 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
4354 if (dump_file)
4355 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
4356 e->src->index, dest->index);
4358 df_set_bb_dirty (e->src);
4359 redirect_edge_succ (e, dest);
4360 return e;
4363 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
4364 in the case the basic block appears to be in sequence. Avoid this
4365 transformation. */
4367 if (e->flags & EDGE_FALLTHRU)
4369 /* Redirect any branch edges unified with the fallthru one. */
4370 if (JUMP_P (BB_END (src))
4371 && label_is_jump_target_p (BB_HEAD (e->dest),
4372 BB_END (src)))
4374 edge redirected;
4376 if (dump_file)
4377 fprintf (dump_file, "Fallthru edge unified with branch "
4378 "%i->%i redirected to %i\n",
4379 e->src->index, e->dest->index, dest->index);
4380 e->flags &= ~EDGE_FALLTHRU;
4381 redirected = redirect_branch_edge (e, dest);
4382 gcc_assert (redirected);
4383 redirected->flags |= EDGE_FALLTHRU;
4384 df_set_bb_dirty (redirected->src);
4385 return redirected;
4387 /* In case we are redirecting fallthru edge to the branch edge
4388 of conditional jump, remove it. */
4389 if (EDGE_COUNT (src->succs) == 2)
4391 /* Find the edge that is different from E. */
4392 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
4394 if (s->dest == dest
4395 && any_condjump_p (BB_END (src))
4396 && onlyjump_p (BB_END (src)))
4397 delete_insn (BB_END (src));
4399 if (dump_file)
4400 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
4401 e->src->index, e->dest->index, dest->index);
4402 ret = redirect_edge_succ_nodup (e, dest);
4404 else
4405 ret = redirect_branch_edge (e, dest);
4407 /* We don't want simplejumps in the insn stream during cfglayout. */
4408 gcc_assert (!simplejump_p (BB_END (src)));
4410 df_set_bb_dirty (src);
4411 return ret;
4414 /* Simple wrapper as we always can redirect fallthru edges. */
4415 static basic_block
4416 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
4418 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
4420 gcc_assert (redirected);
4421 return NULL;
4424 /* Same as delete_basic_block but update cfg_layout structures. */
4426 static void
4427 cfg_layout_delete_block (basic_block bb)
4429 rtx_insn *insn, *next, *prev = PREV_INSN (BB_HEAD (bb)), *remaints;
4430 rtx_insn **to;
4432 if (BB_HEADER (bb))
4434 next = BB_HEAD (bb);
4435 if (prev)
4436 SET_NEXT_INSN (prev) = BB_HEADER (bb);
4437 else
4438 set_first_insn (BB_HEADER (bb));
4439 SET_PREV_INSN (BB_HEADER (bb)) = prev;
4440 insn = BB_HEADER (bb);
4441 while (NEXT_INSN (insn))
4442 insn = NEXT_INSN (insn);
4443 SET_NEXT_INSN (insn) = next;
4444 SET_PREV_INSN (next) = insn;
4446 next = NEXT_INSN (BB_END (bb));
4447 if (BB_FOOTER (bb))
4449 insn = BB_FOOTER (bb);
4450 while (insn)
4452 if (BARRIER_P (insn))
4454 if (PREV_INSN (insn))
4455 SET_NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
4456 else
4457 BB_FOOTER (bb) = NEXT_INSN (insn);
4458 if (NEXT_INSN (insn))
4459 SET_PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
4461 if (LABEL_P (insn))
4462 break;
4463 insn = NEXT_INSN (insn);
4465 if (BB_FOOTER (bb))
4467 insn = BB_END (bb);
4468 SET_NEXT_INSN (insn) = BB_FOOTER (bb);
4469 SET_PREV_INSN (BB_FOOTER (bb)) = insn;
4470 while (NEXT_INSN (insn))
4471 insn = NEXT_INSN (insn);
4472 SET_NEXT_INSN (insn) = next;
4473 if (next)
4474 SET_PREV_INSN (next) = insn;
4475 else
4476 set_last_insn (insn);
4479 if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
4480 to = &BB_HEADER (bb->next_bb);
4481 else
4482 to = &cfg_layout_function_footer;
4484 rtl_delete_block (bb);
4486 if (prev)
4487 prev = NEXT_INSN (prev);
4488 else
4489 prev = get_insns ();
4490 if (next)
4491 next = PREV_INSN (next);
4492 else
4493 next = get_last_insn ();
4495 if (next && NEXT_INSN (next) != prev)
4497 remaints = unlink_insn_chain (prev, next);
4498 insn = remaints;
4499 while (NEXT_INSN (insn))
4500 insn = NEXT_INSN (insn);
4501 SET_NEXT_INSN (insn) = *to;
4502 if (*to)
4503 SET_PREV_INSN (*to) = insn;
4504 *to = remaints;
4508 /* Return true when blocks A and B can be safely merged. */
4510 static bool
4511 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
4513 /* If we are partitioning hot/cold basic blocks, we don't want to
4514 mess up unconditional or indirect jumps that cross between hot
4515 and cold sections.
4517 Basic block partitioning may result in some jumps that appear to
4518 be optimizable (or blocks that appear to be mergeable), but which really
4519 must be left untouched (they are required to make it safely across
4520 partition boundaries). See the comments at the top of
4521 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
4523 if (BB_PARTITION (a) != BB_PARTITION (b))
4524 return false;
4526 /* Protect the loop latches. */
4527 if (current_loops && b->loop_father->latch == b)
4528 return false;
4530 /* If we would end up moving B's instructions, make sure it doesn't fall
4531 through into the exit block, since we cannot recover from a fallthrough
4532 edge into the exit block occurring in the middle of a function. */
4533 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4535 edge e = find_fallthru_edge (b->succs);
4536 if (e && e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4537 return false;
4540 /* There must be exactly one edge in between the blocks. */
4541 return (single_succ_p (a)
4542 && single_succ (a) == b
4543 && single_pred_p (b) == 1
4544 && a != b
4545 /* Must be simple edge. */
4546 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
4547 && a != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4548 && b != EXIT_BLOCK_PTR_FOR_FN (cfun)
4549 /* If the jump insn has side effects, we can't kill the edge.
4550 When not optimizing, try_redirect_by_replacing_jump will
4551 not allow us to redirect an edge by replacing a table jump. */
4552 && (!JUMP_P (BB_END (a))
4553 || ((!optimize || reload_completed)
4554 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
4557 /* Merge block A and B. The blocks must be mergeable. */
4559 static void
4560 cfg_layout_merge_blocks (basic_block a, basic_block b)
4562 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
4563 rtx_insn *insn;
4565 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4567 if (dump_file)
4568 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4569 a->index);
4571 /* If there was a CODE_LABEL beginning B, delete it. */
4572 if (LABEL_P (BB_HEAD (b)))
4574 delete_insn (BB_HEAD (b));
4577 /* We should have fallthru edge in a, or we can do dummy redirection to get
4578 it cleaned up. */
4579 if (JUMP_P (BB_END (a)))
4580 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4581 gcc_assert (!JUMP_P (BB_END (a)));
4583 /* When not optimizing and the edge is the only place in RTL which holds
4584 some unique locus, emit a nop with that locus in between. */
4585 if (!optimize)
4586 emit_nop_for_unique_locus_between (a, b);
4588 /* Move things from b->footer after a->footer. */
4589 if (BB_FOOTER (b))
4591 if (!BB_FOOTER (a))
4592 BB_FOOTER (a) = BB_FOOTER (b);
4593 else
4595 rtx_insn *last = BB_FOOTER (a);
4597 while (NEXT_INSN (last))
4598 last = NEXT_INSN (last);
4599 SET_NEXT_INSN (last) = BB_FOOTER (b);
4600 SET_PREV_INSN (BB_FOOTER (b)) = last;
4602 BB_FOOTER (b) = NULL;
4605 /* Move things from b->header before a->footer.
4606 Note that this may include dead tablejump data, but we don't clean
4607 those up until we go out of cfglayout mode. */
4608 if (BB_HEADER (b))
4610 if (! BB_FOOTER (a))
4611 BB_FOOTER (a) = BB_HEADER (b);
4612 else
4614 rtx_insn *last = BB_HEADER (b);
4616 while (NEXT_INSN (last))
4617 last = NEXT_INSN (last);
4618 SET_NEXT_INSN (last) = BB_FOOTER (a);
4619 SET_PREV_INSN (BB_FOOTER (a)) = last;
4620 BB_FOOTER (a) = BB_HEADER (b);
4622 BB_HEADER (b) = NULL;
4625 /* In the case basic blocks are not adjacent, move them around. */
4626 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4628 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4630 emit_insn_after_noloc (insn, BB_END (a), a);
4632 /* Otherwise just re-associate the instructions. */
4633 else
4635 insn = BB_HEAD (b);
4636 BB_END (a) = BB_END (b);
4639 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4640 We need to explicitly call. */
4641 update_bb_for_insn_chain (insn, BB_END (b), a);
4643 /* Skip possible DELETED_LABEL insn. */
4644 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4645 insn = NEXT_INSN (insn);
4646 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4647 BB_HEAD (b) = BB_END (b) = NULL;
4648 delete_insn (insn);
4650 df_bb_delete (b->index);
4652 /* If B was a forwarder block, propagate the locus on the edge. */
4653 if (forwarder_p
4654 && LOCATION_LOCUS (EDGE_SUCC (b, 0)->goto_locus) == UNKNOWN_LOCATION)
4655 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4657 if (dump_file)
4658 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4661 /* Split edge E. */
4663 static basic_block
4664 cfg_layout_split_edge (edge e)
4666 basic_block new_bb =
4667 create_basic_block (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
4668 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4669 NULL_RTX, e->src);
4671 if (e->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
4672 BB_COPY_PARTITION (new_bb, e->src);
4673 else
4674 BB_COPY_PARTITION (new_bb, e->dest);
4675 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4676 redirect_edge_and_branch_force (e, new_bb);
4678 return new_bb;
4681 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4683 static void
4684 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4688 /* Return true if BB contains only labels or non-executable
4689 instructions. */
4691 static bool
4692 rtl_block_empty_p (basic_block bb)
4694 rtx_insn *insn;
4696 if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun)
4697 || bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
4698 return true;
4700 FOR_BB_INSNS (bb, insn)
4701 if (NONDEBUG_INSN_P (insn) && !any_uncondjump_p (insn))
4702 return false;
4704 return true;
4707 /* Split a basic block if it ends with a conditional branch and if
4708 the other part of the block is not empty. */
4710 static basic_block
4711 rtl_split_block_before_cond_jump (basic_block bb)
4713 rtx_insn *insn;
4714 rtx_insn *split_point = NULL;
4715 rtx_insn *last = NULL;
4716 bool found_code = false;
4718 FOR_BB_INSNS (bb, insn)
4720 if (any_condjump_p (insn))
4721 split_point = last;
4722 else if (NONDEBUG_INSN_P (insn))
4723 found_code = true;
4724 last = insn;
4727 /* Did not find everything. */
4728 if (found_code && split_point)
4729 return split_block (bb, split_point)->dest;
4730 else
4731 return NULL;
4734 /* Return 1 if BB ends with a call, possibly followed by some
4735 instructions that must stay with the call, 0 otherwise. */
4737 static bool
4738 rtl_block_ends_with_call_p (basic_block bb)
4740 rtx_insn *insn = BB_END (bb);
4742 while (!CALL_P (insn)
4743 && insn != BB_HEAD (bb)
4744 && (keep_with_call_p (insn)
4745 || NOTE_P (insn)
4746 || DEBUG_INSN_P (insn)))
4747 insn = PREV_INSN (insn);
4748 return (CALL_P (insn));
4751 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4753 static bool
4754 rtl_block_ends_with_condjump_p (const_basic_block bb)
4756 return any_condjump_p (BB_END (bb));
4759 /* Return true if we need to add fake edge to exit.
4760 Helper function for rtl_flow_call_edges_add. */
4762 static bool
4763 need_fake_edge_p (const rtx_insn *insn)
4765 if (!INSN_P (insn))
4766 return false;
4768 if ((CALL_P (insn)
4769 && !SIBLING_CALL_P (insn)
4770 && !find_reg_note (insn, REG_NORETURN, NULL)
4771 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
4772 return true;
4774 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
4775 && MEM_VOLATILE_P (PATTERN (insn)))
4776 || (GET_CODE (PATTERN (insn)) == PARALLEL
4777 && asm_noperands (insn) != -1
4778 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
4779 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
4782 /* Add fake edges to the function exit for any non constant and non noreturn
4783 calls, volatile inline assembly in the bitmap of blocks specified by
4784 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4785 that were split.
4787 The goal is to expose cases in which entering a basic block does not imply
4788 that all subsequent instructions must be executed. */
4790 static int
4791 rtl_flow_call_edges_add (sbitmap blocks)
4793 int i;
4794 int blocks_split = 0;
4795 int last_bb = last_basic_block_for_fn (cfun);
4796 bool check_last_block = false;
4798 if (n_basic_blocks_for_fn (cfun) == NUM_FIXED_BLOCKS)
4799 return 0;
4801 if (! blocks)
4802 check_last_block = true;
4803 else
4804 check_last_block = bitmap_bit_p (blocks,
4805 EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb->index);
4807 /* In the last basic block, before epilogue generation, there will be
4808 a fallthru edge to EXIT. Special care is required if the last insn
4809 of the last basic block is a call because make_edge folds duplicate
4810 edges, which would result in the fallthru edge also being marked
4811 fake, which would result in the fallthru edge being removed by
4812 remove_fake_edges, which would result in an invalid CFG.
4814 Moreover, we can't elide the outgoing fake edge, since the block
4815 profiler needs to take this into account in order to solve the minimal
4816 spanning tree in the case that the call doesn't return.
4818 Handle this by adding a dummy instruction in a new last basic block. */
4819 if (check_last_block)
4821 basic_block bb = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
4822 rtx_insn *insn = BB_END (bb);
4824 /* Back up past insns that must be kept in the same block as a call. */
4825 while (insn != BB_HEAD (bb)
4826 && keep_with_call_p (insn))
4827 insn = PREV_INSN (insn);
4829 if (need_fake_edge_p (insn))
4831 edge e;
4833 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4834 if (e)
4836 insert_insn_on_edge (gen_use (const0_rtx), e);
4837 commit_edge_insertions ();
4842 /* Now add fake edges to the function exit for any non constant
4843 calls since there is no way that we can determine if they will
4844 return or not... */
4846 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
4848 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
4849 rtx_insn *insn;
4850 rtx_insn *prev_insn;
4852 if (!bb)
4853 continue;
4855 if (blocks && !bitmap_bit_p (blocks, i))
4856 continue;
4858 for (insn = BB_END (bb); ; insn = prev_insn)
4860 prev_insn = PREV_INSN (insn);
4861 if (need_fake_edge_p (insn))
4863 edge e;
4864 rtx_insn *split_at_insn = insn;
4866 /* Don't split the block between a call and an insn that should
4867 remain in the same block as the call. */
4868 if (CALL_P (insn))
4869 while (split_at_insn != BB_END (bb)
4870 && keep_with_call_p (NEXT_INSN (split_at_insn)))
4871 split_at_insn = NEXT_INSN (split_at_insn);
4873 /* The handling above of the final block before the epilogue
4874 should be enough to verify that there is no edge to the exit
4875 block in CFG already. Calling make_edge in such case would
4876 cause us to mark that edge as fake and remove it later. */
4878 #ifdef ENABLE_CHECKING
4879 if (split_at_insn == BB_END (bb))
4881 e = find_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun));
4882 gcc_assert (e == NULL);
4884 #endif
4886 /* Note that the following may create a new basic block
4887 and renumber the existing basic blocks. */
4888 if (split_at_insn != BB_END (bb))
4890 e = split_block (bb, split_at_insn);
4891 if (e)
4892 blocks_split++;
4895 make_edge (bb, EXIT_BLOCK_PTR_FOR_FN (cfun), EDGE_FAKE);
4898 if (insn == BB_HEAD (bb))
4899 break;
4903 if (blocks_split)
4904 verify_flow_info ();
4906 return blocks_split;
4909 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4910 the conditional branch target, SECOND_HEAD should be the fall-thru
4911 there is no need to handle this here the loop versioning code handles
4912 this. the reason for SECON_HEAD is that it is needed for condition
4913 in trees, and this should be of the same type since it is a hook. */
4914 static void
4915 rtl_lv_add_condition_to_bb (basic_block first_head ,
4916 basic_block second_head ATTRIBUTE_UNUSED,
4917 basic_block cond_bb, void *comp_rtx)
4919 rtx label;
4920 rtx_insn *seq, *jump;
4921 rtx op0 = XEXP ((rtx)comp_rtx, 0);
4922 rtx op1 = XEXP ((rtx)comp_rtx, 1);
4923 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
4924 machine_mode mode;
4927 label = block_label (first_head);
4928 mode = GET_MODE (op0);
4929 if (mode == VOIDmode)
4930 mode = GET_MODE (op1);
4932 start_sequence ();
4933 op0 = force_operand (op0, NULL_RTX);
4934 op1 = force_operand (op1, NULL_RTX);
4935 do_compare_rtx_and_jump (op0, op1, comp, 0,
4936 mode, NULL_RTX, NULL_RTX, label, -1);
4937 jump = get_last_insn ();
4938 JUMP_LABEL (jump) = label;
4939 LABEL_NUSES (label)++;
4940 seq = get_insns ();
4941 end_sequence ();
4943 /* Add the new cond, in the new head. */
4944 emit_insn_after (seq, BB_END (cond_bb));
4948 /* Given a block B with unconditional branch at its end, get the
4949 store the return the branch edge and the fall-thru edge in
4950 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4951 static void
4952 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
4953 edge *fallthru_edge)
4955 edge e = EDGE_SUCC (b, 0);
4957 if (e->flags & EDGE_FALLTHRU)
4959 *fallthru_edge = e;
4960 *branch_edge = EDGE_SUCC (b, 1);
4962 else
4964 *branch_edge = e;
4965 *fallthru_edge = EDGE_SUCC (b, 1);
4969 void
4970 init_rtl_bb_info (basic_block bb)
4972 gcc_assert (!bb->il.x.rtl);
4973 bb->il.x.head_ = NULL;
4974 bb->il.x.rtl = ggc_cleared_alloc<rtl_bb_info> ();
4977 /* Returns true if it is possible to remove edge E by redirecting
4978 it to the destination of the other edge from E->src. */
4980 static bool
4981 rtl_can_remove_branch_p (const_edge e)
4983 const_basic_block src = e->src;
4984 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
4985 const rtx_insn *insn = BB_END (src);
4986 rtx set;
4988 /* The conditions are taken from try_redirect_by_replacing_jump. */
4989 if (target == EXIT_BLOCK_PTR_FOR_FN (cfun))
4990 return false;
4992 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4993 return false;
4995 if (BB_PARTITION (src) != BB_PARTITION (target))
4996 return false;
4998 if (!onlyjump_p (insn)
4999 || tablejump_p (insn, NULL, NULL))
5000 return false;
5002 set = single_set (insn);
5003 if (!set || side_effects_p (set))
5004 return false;
5006 return true;
5009 static basic_block
5010 rtl_duplicate_bb (basic_block bb)
5012 bb = cfg_layout_duplicate_bb (bb);
5013 bb->aux = NULL;
5014 return bb;
5017 /* Do book-keeping of basic block BB for the profile consistency checker.
5018 If AFTER_PASS is 0, do pre-pass accounting, or if AFTER_PASS is 1
5019 then do post-pass accounting. Store the counting in RECORD. */
5020 static void
5021 rtl_account_profile_record (basic_block bb, int after_pass,
5022 struct profile_record *record)
5024 rtx_insn *insn;
5025 FOR_BB_INSNS (bb, insn)
5026 if (INSN_P (insn))
5028 record->size[after_pass]
5029 += insn_rtx_cost (PATTERN (insn), false);
5030 if (profile_status_for_fn (cfun) == PROFILE_READ)
5031 record->time[after_pass]
5032 += insn_rtx_cost (PATTERN (insn), true) * bb->count;
5033 else if (profile_status_for_fn (cfun) == PROFILE_GUESSED)
5034 record->time[after_pass]
5035 += insn_rtx_cost (PATTERN (insn), true) * bb->frequency;
5039 /* Implementation of CFG manipulation for linearized RTL. */
5040 struct cfg_hooks rtl_cfg_hooks = {
5041 "rtl",
5042 rtl_verify_flow_info,
5043 rtl_dump_bb,
5044 rtl_dump_bb_for_graph,
5045 rtl_create_basic_block,
5046 rtl_redirect_edge_and_branch,
5047 rtl_redirect_edge_and_branch_force,
5048 rtl_can_remove_branch_p,
5049 rtl_delete_block,
5050 rtl_split_block,
5051 rtl_move_block_after,
5052 rtl_can_merge_blocks, /* can_merge_blocks_p */
5053 rtl_merge_blocks,
5054 rtl_predict_edge,
5055 rtl_predicted_by_p,
5056 cfg_layout_can_duplicate_bb_p,
5057 rtl_duplicate_bb,
5058 rtl_split_edge,
5059 rtl_make_forwarder_block,
5060 rtl_tidy_fallthru_edge,
5061 rtl_force_nonfallthru,
5062 rtl_block_ends_with_call_p,
5063 rtl_block_ends_with_condjump_p,
5064 rtl_flow_call_edges_add,
5065 NULL, /* execute_on_growing_pred */
5066 NULL, /* execute_on_shrinking_pred */
5067 NULL, /* duplicate loop for trees */
5068 NULL, /* lv_add_condition_to_bb */
5069 NULL, /* lv_adjust_loop_header_phi*/
5070 NULL, /* extract_cond_bb_edges */
5071 NULL, /* flush_pending_stmts */
5072 rtl_block_empty_p, /* block_empty_p */
5073 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5074 rtl_account_profile_record,
5077 /* Implementation of CFG manipulation for cfg layout RTL, where
5078 basic block connected via fallthru edges does not have to be adjacent.
5079 This representation will hopefully become the default one in future
5080 version of the compiler. */
5082 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
5083 "cfglayout mode",
5084 rtl_verify_flow_info_1,
5085 rtl_dump_bb,
5086 rtl_dump_bb_for_graph,
5087 cfg_layout_create_basic_block,
5088 cfg_layout_redirect_edge_and_branch,
5089 cfg_layout_redirect_edge_and_branch_force,
5090 rtl_can_remove_branch_p,
5091 cfg_layout_delete_block,
5092 cfg_layout_split_block,
5093 rtl_move_block_after,
5094 cfg_layout_can_merge_blocks_p,
5095 cfg_layout_merge_blocks,
5096 rtl_predict_edge,
5097 rtl_predicted_by_p,
5098 cfg_layout_can_duplicate_bb_p,
5099 cfg_layout_duplicate_bb,
5100 cfg_layout_split_edge,
5101 rtl_make_forwarder_block,
5102 NULL, /* tidy_fallthru_edge */
5103 rtl_force_nonfallthru,
5104 rtl_block_ends_with_call_p,
5105 rtl_block_ends_with_condjump_p,
5106 rtl_flow_call_edges_add,
5107 NULL, /* execute_on_growing_pred */
5108 NULL, /* execute_on_shrinking_pred */
5109 duplicate_loop_to_header_edge, /* duplicate loop for trees */
5110 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
5111 NULL, /* lv_adjust_loop_header_phi*/
5112 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
5113 NULL, /* flush_pending_stmts */
5114 rtl_block_empty_p, /* block_empty_p */
5115 rtl_split_block_before_cond_jump, /* split_block_before_cond_jump */
5116 rtl_account_profile_record,
5119 #include "gt-cfgrtl.h"