var-tracking.c (vt_add_function_parameter): Adjust for VEC changes.
[official-gcc.git] / gcc / cfgrtl.c
blobc62b5bce33fbe9beb6a80b46496069d68849c43e
1 /* Control flow graph manipulation code for GNU compiler.
2 Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 2011, 2012 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains low level functions to manipulate the CFG and analyze it
23 that are aware of the RTL intermediate language.
25 Available functionality:
26 - Basic CFG/RTL manipulation API documented in cfghooks.h
27 - CFG-aware instruction chain manipulation
28 delete_insn, delete_insn_chain
29 - Edge splitting and committing to edges
30 insert_insn_on_edge, commit_edge_insertions
31 - CFG updating after insn simplification
32 purge_dead_edges, purge_all_dead_edges
33 - CFG fixing after coarse manipulation
34 fixup_abnormal_edges
36 Functions not supposed for generic use:
37 - Infrastructure to determine quickly basic block for insn
38 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
39 - Edge redirection with updating and optimizing of insn chain
40 block_label, tidy_fallthru_edge, force_nonfallthru */
42 #include "config.h"
43 #include "system.h"
44 #include "coretypes.h"
45 #include "tm.h"
46 #include "tree.h"
47 #include "hard-reg-set.h"
48 #include "basic-block.h"
49 #include "regs.h"
50 #include "flags.h"
51 #include "function.h"
52 #include "except.h"
53 #include "rtl-error.h"
54 #include "tm_p.h"
55 #include "obstack.h"
56 #include "insn-attr.h"
57 #include "insn-config.h"
58 #include "expr.h"
59 #include "target.h"
60 #include "common/common-target.h"
61 #include "cfgloop.h"
62 #include "ggc.h"
63 #include "tree-pass.h"
64 #include "df.h"
66 /* Holds the interesting leading and trailing notes for the function.
67 Only applicable if the CFG is in cfglayout mode. */
68 static GTY(()) rtx cfg_layout_function_footer;
69 static GTY(()) rtx cfg_layout_function_header;
71 static rtx skip_insns_after_block (basic_block);
72 static void record_effective_endpoints (void);
73 static rtx label_for_bb (basic_block);
74 static void fixup_reorder_chain (void);
76 void verify_insn_chain (void);
77 static void fixup_fallthru_exit_predecessor (void);
78 static int can_delete_note_p (const_rtx);
79 static int can_delete_label_p (const_rtx);
80 static basic_block rtl_split_edge (edge);
81 static bool rtl_move_block_after (basic_block, basic_block);
82 static int rtl_verify_flow_info (void);
83 static basic_block cfg_layout_split_block (basic_block, void *);
84 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
85 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
86 static void cfg_layout_delete_block (basic_block);
87 static void rtl_delete_block (basic_block);
88 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
89 static edge rtl_redirect_edge_and_branch (edge, basic_block);
90 static basic_block rtl_split_block (basic_block, void *);
91 static void rtl_dump_bb (FILE *, basic_block, int, int);
92 static int rtl_verify_flow_info_1 (void);
93 static void rtl_make_forwarder_block (edge);
95 /* Return true if NOTE is not one of the ones that must be kept paired,
96 so that we may simply delete it. */
98 static int
99 can_delete_note_p (const_rtx note)
101 switch (NOTE_KIND (note))
103 case NOTE_INSN_DELETED:
104 case NOTE_INSN_BASIC_BLOCK:
105 case NOTE_INSN_EPILOGUE_BEG:
106 return true;
108 default:
109 return false;
113 /* True if a given label can be deleted. */
115 static int
116 can_delete_label_p (const_rtx label)
118 return (!LABEL_PRESERVE_P (label)
119 /* User declared labels must be preserved. */
120 && LABEL_NAME (label) == 0
121 && !in_expr_list_p (forced_labels, label));
124 /* Delete INSN by patching it out. */
126 void
127 delete_insn (rtx insn)
129 rtx note;
130 bool really_delete = true;
132 if (LABEL_P (insn))
134 /* Some labels can't be directly removed from the INSN chain, as they
135 might be references via variables, constant pool etc.
136 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
137 if (! can_delete_label_p (insn))
139 const char *name = LABEL_NAME (insn);
140 basic_block bb = BLOCK_FOR_INSN (insn);
141 rtx bb_note = NEXT_INSN (insn);
143 really_delete = false;
144 PUT_CODE (insn, NOTE);
145 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
146 NOTE_DELETED_LABEL_NAME (insn) = name;
148 if (bb_note != NULL_RTX && NOTE_INSN_BASIC_BLOCK_P (bb_note)
149 && BLOCK_FOR_INSN (bb_note) == bb)
151 reorder_insns_nobb (insn, insn, bb_note);
152 BB_HEAD (bb) = bb_note;
153 if (BB_END (bb) == bb_note)
154 BB_END (bb) = insn;
158 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
161 if (really_delete)
163 /* If this insn has already been deleted, something is very wrong. */
164 gcc_assert (!INSN_DELETED_P (insn));
165 remove_insn (insn);
166 INSN_DELETED_P (insn) = 1;
169 /* If deleting a jump, decrement the use count of the label. Deleting
170 the label itself should happen in the normal course of block merging. */
171 if (JUMP_P (insn))
173 if (JUMP_LABEL (insn)
174 && LABEL_P (JUMP_LABEL (insn)))
175 LABEL_NUSES (JUMP_LABEL (insn))--;
177 /* If there are more targets, remove them too. */
178 while ((note
179 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
180 && LABEL_P (XEXP (note, 0)))
182 LABEL_NUSES (XEXP (note, 0))--;
183 remove_note (insn, note);
187 /* Also if deleting any insn that references a label as an operand. */
188 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
189 && LABEL_P (XEXP (note, 0)))
191 LABEL_NUSES (XEXP (note, 0))--;
192 remove_note (insn, note);
195 if (JUMP_TABLE_DATA_P (insn))
197 rtx pat = PATTERN (insn);
198 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
199 int len = XVECLEN (pat, diff_vec_p);
200 int i;
202 for (i = 0; i < len; i++)
204 rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
206 /* When deleting code in bulk (e.g. removing many unreachable
207 blocks) we can delete a label that's a target of the vector
208 before deleting the vector itself. */
209 if (!NOTE_P (label))
210 LABEL_NUSES (label)--;
215 /* Like delete_insn but also purge dead edges from BB. */
217 void
218 delete_insn_and_edges (rtx insn)
220 bool purge = false;
222 if (INSN_P (insn)
223 && BLOCK_FOR_INSN (insn)
224 && BB_END (BLOCK_FOR_INSN (insn)) == insn)
225 purge = true;
226 delete_insn (insn);
227 if (purge)
228 purge_dead_edges (BLOCK_FOR_INSN (insn));
231 /* Unlink a chain of insns between START and FINISH, leaving notes
232 that must be paired. If CLEAR_BB is true, we set bb field for
233 insns that cannot be removed to NULL. */
235 void
236 delete_insn_chain (rtx start, rtx finish, bool clear_bb)
238 rtx prev, current;
240 /* Unchain the insns one by one. It would be quicker to delete all of these
241 with a single unchaining, rather than one at a time, but we need to keep
242 the NOTE's. */
243 current = finish;
244 while (1)
246 prev = PREV_INSN (current);
247 if (NOTE_P (current) && !can_delete_note_p (current))
249 else
250 delete_insn (current);
252 if (clear_bb && !INSN_DELETED_P (current))
253 set_block_for_insn (current, NULL);
255 if (current == start)
256 break;
257 current = prev;
261 /* Create a new basic block consisting of the instructions between HEAD and END
262 inclusive. This function is designed to allow fast BB construction - reuses
263 the note and basic block struct in BB_NOTE, if any and do not grow
264 BASIC_BLOCK chain and should be used directly only by CFG construction code.
265 END can be NULL in to create new empty basic block before HEAD. Both END
266 and HEAD can be NULL to create basic block at the end of INSN chain.
267 AFTER is the basic block we should be put after. */
269 basic_block
270 create_basic_block_structure (rtx head, rtx end, rtx bb_note, basic_block after)
272 basic_block bb;
274 if (bb_note
275 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
276 && bb->aux == NULL)
278 /* If we found an existing note, thread it back onto the chain. */
280 rtx after;
282 if (LABEL_P (head))
283 after = head;
284 else
286 after = PREV_INSN (head);
287 head = bb_note;
290 if (after != bb_note && NEXT_INSN (after) != bb_note)
291 reorder_insns_nobb (bb_note, bb_note, after);
293 else
295 /* Otherwise we must create a note and a basic block structure. */
297 bb = alloc_block ();
299 init_rtl_bb_info (bb);
300 if (!head && !end)
301 head = end = bb_note
302 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
303 else if (LABEL_P (head) && end)
305 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
306 if (head == end)
307 end = bb_note;
309 else
311 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
312 head = bb_note;
313 if (!end)
314 end = head;
317 NOTE_BASIC_BLOCK (bb_note) = bb;
320 /* Always include the bb note in the block. */
321 if (NEXT_INSN (end) == bb_note)
322 end = bb_note;
324 BB_HEAD (bb) = head;
325 BB_END (bb) = end;
326 bb->index = last_basic_block++;
327 bb->flags = BB_NEW | BB_RTL;
328 link_block (bb, after);
329 SET_BASIC_BLOCK (bb->index, bb);
330 df_bb_refs_record (bb->index, false);
331 update_bb_for_insn (bb);
332 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
334 /* Tag the block so that we know it has been used when considering
335 other basic block notes. */
336 bb->aux = bb;
338 return bb;
341 /* Create new basic block consisting of instructions in between HEAD and END
342 and place it to the BB chain after block AFTER. END can be NULL to
343 create a new empty basic block before HEAD. Both END and HEAD can be
344 NULL to create basic block at the end of INSN chain. */
346 static basic_block
347 rtl_create_basic_block (void *headp, void *endp, basic_block after)
349 rtx head = (rtx) headp, end = (rtx) endp;
350 basic_block bb;
352 /* Grow the basic block array if needed. */
353 if ((size_t) last_basic_block >= VEC_length (basic_block, basic_block_info))
355 size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
356 VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
359 n_basic_blocks++;
361 bb = create_basic_block_structure (head, end, NULL, after);
362 bb->aux = NULL;
363 return bb;
366 static basic_block
367 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
369 basic_block newbb = rtl_create_basic_block (head, end, after);
371 return newbb;
374 /* Delete the insns in a (non-live) block. We physically delete every
375 non-deleted-note insn, and update the flow graph appropriately.
377 Return nonzero if we deleted an exception handler. */
379 /* ??? Preserving all such notes strikes me as wrong. It would be nice
380 to post-process the stream to remove empty blocks, loops, ranges, etc. */
382 static void
383 rtl_delete_block (basic_block b)
385 rtx insn, end;
387 /* If the head of this block is a CODE_LABEL, then it might be the
388 label for an exception handler which can't be reached. We need
389 to remove the label from the exception_handler_label list. */
390 insn = BB_HEAD (b);
392 end = get_last_bb_insn (b);
394 /* Selectively delete the entire chain. */
395 BB_HEAD (b) = NULL;
396 delete_insn_chain (insn, end, true);
399 if (dump_file)
400 fprintf (dump_file, "deleting block %d\n", b->index);
401 df_bb_delete (b->index);
404 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
406 void
407 compute_bb_for_insn (void)
409 basic_block bb;
411 FOR_EACH_BB (bb)
413 rtx end = BB_END (bb);
414 rtx insn;
416 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
418 BLOCK_FOR_INSN (insn) = bb;
419 if (insn == end)
420 break;
425 /* Release the basic_block_for_insn array. */
427 unsigned int
428 free_bb_for_insn (void)
430 rtx insn;
431 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
432 if (!BARRIER_P (insn))
433 BLOCK_FOR_INSN (insn) = NULL;
434 return 0;
437 static unsigned int
438 rest_of_pass_free_cfg (void)
440 #ifdef DELAY_SLOTS
441 /* The resource.c machinery uses DF but the CFG isn't guaranteed to be
442 valid at that point so it would be too late to call df_analyze. */
443 if (optimize > 0 && flag_delayed_branch)
445 df_note_add_problem ();
446 df_analyze ();
448 #endif
450 free_bb_for_insn ();
451 return 0;
454 struct rtl_opt_pass pass_free_cfg =
457 RTL_PASS,
458 "*free_cfg", /* name */
459 NULL, /* gate */
460 rest_of_pass_free_cfg, /* execute */
461 NULL, /* sub */
462 NULL, /* next */
463 0, /* static_pass_number */
464 TV_NONE, /* tv_id */
465 0, /* properties_required */
466 0, /* properties_provided */
467 PROP_cfg, /* properties_destroyed */
468 0, /* todo_flags_start */
469 0, /* todo_flags_finish */
473 /* Return RTX to emit after when we want to emit code on the entry of function. */
475 entry_of_function (void)
477 return (n_basic_blocks > NUM_FIXED_BLOCKS ?
478 BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ());
481 /* Emit INSN at the entry point of the function, ensuring that it is only
482 executed once per function. */
483 void
484 emit_insn_at_entry (rtx insn)
486 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR->succs);
487 edge e = ei_safe_edge (ei);
488 gcc_assert (e->flags & EDGE_FALLTHRU);
490 insert_insn_on_edge (insn, e);
491 commit_edge_insertions ();
494 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
495 (or BARRIER if found) and notify df of the bb change.
496 The insn chain range is inclusive
497 (i.e. both BEGIN and END will be updated. */
499 static void
500 update_bb_for_insn_chain (rtx begin, rtx end, basic_block bb)
502 rtx insn;
504 end = NEXT_INSN (end);
505 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
506 if (!BARRIER_P (insn))
507 df_insn_change_bb (insn, bb);
510 /* Update BLOCK_FOR_INSN of insns in BB to BB,
511 and notify df of the change. */
513 void
514 update_bb_for_insn (basic_block bb)
516 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
520 /* Like active_insn_p, except keep the return value clobber around
521 even after reload. */
523 static bool
524 flow_active_insn_p (const_rtx insn)
526 if (active_insn_p (insn))
527 return true;
529 /* A clobber of the function return value exists for buggy
530 programs that fail to return a value. Its effect is to
531 keep the return value from being live across the entire
532 function. If we allow it to be skipped, we introduce the
533 possibility for register lifetime confusion. */
534 if (GET_CODE (PATTERN (insn)) == CLOBBER
535 && REG_P (XEXP (PATTERN (insn), 0))
536 && REG_FUNCTION_VALUE_P (XEXP (PATTERN (insn), 0)))
537 return true;
539 return false;
542 /* Return true if the block has no effect and only forwards control flow to
543 its single destination. */
544 /* FIXME: Make this a cfg hook. */
546 bool
547 forwarder_block_p (const_basic_block bb)
549 rtx insn;
551 if (bb == EXIT_BLOCK_PTR || bb == ENTRY_BLOCK_PTR
552 || !single_succ_p (bb))
553 return false;
555 /* Protect loop latches, headers and preheaders. */
556 if (current_loops)
558 basic_block dest;
559 if (bb->loop_father->header == bb)
560 return false;
561 dest = EDGE_SUCC (bb, 0)->dest;
562 if (dest->loop_father->header == dest)
563 return false;
566 for (insn = BB_HEAD (bb); insn != BB_END (bb); insn = NEXT_INSN (insn))
567 if (INSN_P (insn) && flow_active_insn_p (insn))
568 return false;
570 return (!INSN_P (insn)
571 || (JUMP_P (insn) && simplejump_p (insn))
572 || !flow_active_insn_p (insn));
575 /* Return nonzero if we can reach target from src by falling through. */
576 /* FIXME: Make this a cfg hook. */
578 bool
579 can_fallthru (basic_block src, basic_block target)
581 rtx insn = BB_END (src);
582 rtx insn2;
583 edge e;
584 edge_iterator ei;
586 if (target == EXIT_BLOCK_PTR)
587 return true;
588 if (src->next_bb != target)
589 return 0;
590 FOR_EACH_EDGE (e, ei, src->succs)
591 if (e->dest == EXIT_BLOCK_PTR
592 && e->flags & EDGE_FALLTHRU)
593 return 0;
595 insn2 = BB_HEAD (target);
596 if (insn2 && !active_insn_p (insn2))
597 insn2 = next_active_insn (insn2);
599 /* ??? Later we may add code to move jump tables offline. */
600 return next_active_insn (insn) == insn2;
603 /* Return nonzero if we could reach target from src by falling through,
604 if the target was made adjacent. If we already have a fall-through
605 edge to the exit block, we can't do that. */
606 static bool
607 could_fall_through (basic_block src, basic_block target)
609 edge e;
610 edge_iterator ei;
612 if (target == EXIT_BLOCK_PTR)
613 return true;
614 FOR_EACH_EDGE (e, ei, src->succs)
615 if (e->dest == EXIT_BLOCK_PTR
616 && e->flags & EDGE_FALLTHRU)
617 return 0;
618 return true;
621 /* Return the NOTE_INSN_BASIC_BLOCK of BB. */
623 bb_note (basic_block bb)
625 rtx note;
627 note = BB_HEAD (bb);
628 if (LABEL_P (note))
629 note = NEXT_INSN (note);
631 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (note));
632 return note;
635 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
636 note associated with the BLOCK. */
638 static rtx
639 first_insn_after_basic_block_note (basic_block block)
641 rtx insn;
643 /* Get the first instruction in the block. */
644 insn = BB_HEAD (block);
646 if (insn == NULL_RTX)
647 return NULL_RTX;
648 if (LABEL_P (insn))
649 insn = NEXT_INSN (insn);
650 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
652 return NEXT_INSN (insn);
655 /* Creates a new basic block just after basic block B by splitting
656 everything after specified instruction I. */
658 static basic_block
659 rtl_split_block (basic_block bb, void *insnp)
661 basic_block new_bb;
662 rtx insn = (rtx) insnp;
663 edge e;
664 edge_iterator ei;
666 if (!insn)
668 insn = first_insn_after_basic_block_note (bb);
670 if (insn)
672 rtx next = insn;
674 insn = PREV_INSN (insn);
676 /* If the block contains only debug insns, insn would have
677 been NULL in a non-debug compilation, and then we'd end
678 up emitting a DELETED note. For -fcompare-debug
679 stability, emit the note too. */
680 if (insn != BB_END (bb)
681 && DEBUG_INSN_P (next)
682 && DEBUG_INSN_P (BB_END (bb)))
684 while (next != BB_END (bb) && DEBUG_INSN_P (next))
685 next = NEXT_INSN (next);
687 if (next == BB_END (bb))
688 emit_note_after (NOTE_INSN_DELETED, next);
691 else
692 insn = get_last_insn ();
695 /* We probably should check type of the insn so that we do not create
696 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
697 bother. */
698 if (insn == BB_END (bb))
699 emit_note_after (NOTE_INSN_DELETED, insn);
701 /* Create the new basic block. */
702 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
703 BB_COPY_PARTITION (new_bb, bb);
704 BB_END (bb) = insn;
706 /* Redirect the outgoing edges. */
707 new_bb->succs = bb->succs;
708 bb->succs = NULL;
709 FOR_EACH_EDGE (e, ei, new_bb->succs)
710 e->src = new_bb;
712 /* The new block starts off being dirty. */
713 df_set_bb_dirty (bb);
714 return new_bb;
717 /* Return true if the single edge between blocks A and B is the only place
718 in RTL which holds some unique locus. */
720 static bool
721 unique_locus_on_edge_between_p (basic_block a, basic_block b)
723 const int goto_locus = EDGE_SUCC (a, 0)->goto_locus;
724 rtx insn, end;
726 if (!goto_locus)
727 return false;
729 /* First scan block A backward. */
730 insn = BB_END (a);
731 end = PREV_INSN (BB_HEAD (a));
732 while (insn != end && (!NONDEBUG_INSN_P (insn) || INSN_LOCATOR (insn) == 0))
733 insn = PREV_INSN (insn);
735 if (insn != end && locator_eq (INSN_LOCATOR (insn), goto_locus))
736 return false;
738 /* Then scan block B forward. */
739 insn = BB_HEAD (b);
740 if (insn)
742 end = NEXT_INSN (BB_END (b));
743 while (insn != end && !NONDEBUG_INSN_P (insn))
744 insn = NEXT_INSN (insn);
746 if (insn != end && INSN_LOCATOR (insn) != 0
747 && locator_eq (INSN_LOCATOR (insn), goto_locus))
748 return false;
751 return true;
754 /* If the single edge between blocks A and B is the only place in RTL which
755 holds some unique locus, emit a nop with that locus between the blocks. */
757 static void
758 emit_nop_for_unique_locus_between (basic_block a, basic_block b)
760 if (!unique_locus_on_edge_between_p (a, b))
761 return;
763 BB_END (a) = emit_insn_after_noloc (gen_nop (), BB_END (a), a);
764 INSN_LOCATOR (BB_END (a)) = EDGE_SUCC (a, 0)->goto_locus;
767 /* Blocks A and B are to be merged into a single block A. The insns
768 are already contiguous. */
770 static void
771 rtl_merge_blocks (basic_block a, basic_block b)
773 rtx b_head = BB_HEAD (b), b_end = BB_END (b), a_end = BB_END (a);
774 rtx del_first = NULL_RTX, del_last = NULL_RTX;
775 rtx b_debug_start = b_end, b_debug_end = b_end;
776 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
777 int b_empty = 0;
779 if (dump_file)
780 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
781 a->index);
783 while (DEBUG_INSN_P (b_end))
784 b_end = PREV_INSN (b_debug_start = b_end);
786 /* If there was a CODE_LABEL beginning B, delete it. */
787 if (LABEL_P (b_head))
789 /* Detect basic blocks with nothing but a label. This can happen
790 in particular at the end of a function. */
791 if (b_head == b_end)
792 b_empty = 1;
794 del_first = del_last = b_head;
795 b_head = NEXT_INSN (b_head);
798 /* Delete the basic block note and handle blocks containing just that
799 note. */
800 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
802 if (b_head == b_end)
803 b_empty = 1;
804 if (! del_last)
805 del_first = b_head;
807 del_last = b_head;
808 b_head = NEXT_INSN (b_head);
811 /* If there was a jump out of A, delete it. */
812 if (JUMP_P (a_end))
814 rtx prev;
816 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
817 if (!NOTE_P (prev)
818 || NOTE_INSN_BASIC_BLOCK_P (prev)
819 || prev == BB_HEAD (a))
820 break;
822 del_first = a_end;
824 #ifdef HAVE_cc0
825 /* If this was a conditional jump, we need to also delete
826 the insn that set cc0. */
827 if (only_sets_cc0_p (prev))
829 rtx tmp = prev;
831 prev = prev_nonnote_insn (prev);
832 if (!prev)
833 prev = BB_HEAD (a);
834 del_first = tmp;
836 #endif
838 a_end = PREV_INSN (del_first);
840 else if (BARRIER_P (NEXT_INSN (a_end)))
841 del_first = NEXT_INSN (a_end);
843 /* Delete everything marked above as well as crap that might be
844 hanging out between the two blocks. */
845 BB_END (a) = a_end;
846 BB_HEAD (b) = b_empty ? NULL_RTX : b_head;
847 delete_insn_chain (del_first, del_last, true);
849 /* When not optimizing CFG and the edge is the only place in RTL which holds
850 some unique locus, emit a nop with that locus in between. */
851 if (!optimize)
853 emit_nop_for_unique_locus_between (a, b);
854 a_end = BB_END (a);
857 /* Reassociate the insns of B with A. */
858 if (!b_empty)
860 update_bb_for_insn_chain (a_end, b_debug_end, a);
862 BB_END (a) = b_debug_end;
863 BB_HEAD (b) = NULL_RTX;
865 else if (b_end != b_debug_end)
867 /* Move any deleted labels and other notes between the end of A
868 and the debug insns that make up B after the debug insns,
869 bringing the debug insns into A while keeping the notes after
870 the end of A. */
871 if (NEXT_INSN (a_end) != b_debug_start)
872 reorder_insns_nobb (NEXT_INSN (a_end), PREV_INSN (b_debug_start),
873 b_debug_end);
874 update_bb_for_insn_chain (b_debug_start, b_debug_end, a);
875 BB_END (a) = b_debug_end;
878 df_bb_delete (b->index);
880 /* If B was a forwarder block, propagate the locus on the edge. */
881 if (forwarder_p && !EDGE_SUCC (b, 0)->goto_locus)
882 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
884 if (dump_file)
885 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
889 /* Return true when block A and B can be merged. */
891 static bool
892 rtl_can_merge_blocks (basic_block a, basic_block b)
894 /* If we are partitioning hot/cold basic blocks, we don't want to
895 mess up unconditional or indirect jumps that cross between hot
896 and cold sections.
898 Basic block partitioning may result in some jumps that appear to
899 be optimizable (or blocks that appear to be mergeable), but which really
900 must be left untouched (they are required to make it safely across
901 partition boundaries). See the comments at the top of
902 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
904 if (BB_PARTITION (a) != BB_PARTITION (b))
905 return false;
907 /* Protect the loop latches. */
908 if (current_loops && b->loop_father->latch == b)
909 return false;
911 /* There must be exactly one edge in between the blocks. */
912 return (single_succ_p (a)
913 && single_succ (a) == b
914 && single_pred_p (b)
915 && a != b
916 /* Must be simple edge. */
917 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
918 && a->next_bb == b
919 && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
920 /* If the jump insn has side effects,
921 we can't kill the edge. */
922 && (!JUMP_P (BB_END (a))
923 || (reload_completed
924 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
927 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
928 exist. */
931 block_label (basic_block block)
933 if (block == EXIT_BLOCK_PTR)
934 return NULL_RTX;
936 if (!LABEL_P (BB_HEAD (block)))
938 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
941 return BB_HEAD (block);
944 /* Attempt to perform edge redirection by replacing possibly complex jump
945 instruction by unconditional jump or removing jump completely. This can
946 apply only if all edges now point to the same block. The parameters and
947 return values are equivalent to redirect_edge_and_branch. */
949 edge
950 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
952 basic_block src = e->src;
953 rtx insn = BB_END (src), kill_from;
954 rtx set;
955 int fallthru = 0;
957 /* If we are partitioning hot/cold basic blocks, we don't want to
958 mess up unconditional or indirect jumps that cross between hot
959 and cold sections.
961 Basic block partitioning may result in some jumps that appear to
962 be optimizable (or blocks that appear to be mergeable), but which really
963 must be left untouched (they are required to make it safely across
964 partition boundaries). See the comments at the top of
965 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
967 if (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX)
968 || BB_PARTITION (src) != BB_PARTITION (target))
969 return NULL;
971 /* We can replace or remove a complex jump only when we have exactly
972 two edges. Also, if we have exactly one outgoing edge, we can
973 redirect that. */
974 if (EDGE_COUNT (src->succs) >= 3
975 /* Verify that all targets will be TARGET. Specifically, the
976 edge that is not E must also go to TARGET. */
977 || (EDGE_COUNT (src->succs) == 2
978 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
979 return NULL;
981 if (!onlyjump_p (insn))
982 return NULL;
983 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
984 return NULL;
986 /* Avoid removing branch with side effects. */
987 set = single_set (insn);
988 if (!set || side_effects_p (set))
989 return NULL;
991 /* In case we zap a conditional jump, we'll need to kill
992 the cc0 setter too. */
993 kill_from = insn;
994 #ifdef HAVE_cc0
995 if (reg_mentioned_p (cc0_rtx, PATTERN (insn))
996 && only_sets_cc0_p (PREV_INSN (insn)))
997 kill_from = PREV_INSN (insn);
998 #endif
1000 /* See if we can create the fallthru edge. */
1001 if (in_cfglayout || can_fallthru (src, target))
1003 if (dump_file)
1004 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
1005 fallthru = 1;
1007 /* Selectively unlink whole insn chain. */
1008 if (in_cfglayout)
1010 rtx insn = BB_FOOTER (src);
1012 delete_insn_chain (kill_from, BB_END (src), false);
1014 /* Remove barriers but keep jumptables. */
1015 while (insn)
1017 if (BARRIER_P (insn))
1019 if (PREV_INSN (insn))
1020 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
1021 else
1022 BB_FOOTER (src) = NEXT_INSN (insn);
1023 if (NEXT_INSN (insn))
1024 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
1026 if (LABEL_P (insn))
1027 break;
1028 insn = NEXT_INSN (insn);
1031 else
1032 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
1033 false);
1036 /* If this already is simplejump, redirect it. */
1037 else if (simplejump_p (insn))
1039 if (e->dest == target)
1040 return NULL;
1041 if (dump_file)
1042 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
1043 INSN_UID (insn), e->dest->index, target->index);
1044 if (!redirect_jump (insn, block_label (target), 0))
1046 gcc_assert (target == EXIT_BLOCK_PTR);
1047 return NULL;
1051 /* Cannot do anything for target exit block. */
1052 else if (target == EXIT_BLOCK_PTR)
1053 return NULL;
1055 /* Or replace possibly complicated jump insn by simple jump insn. */
1056 else
1058 rtx target_label = block_label (target);
1059 rtx barrier, label, table;
1061 emit_jump_insn_after_noloc (gen_jump (target_label), insn);
1062 JUMP_LABEL (BB_END (src)) = target_label;
1063 LABEL_NUSES (target_label)++;
1064 if (dump_file)
1065 fprintf (dump_file, "Replacing insn %i by jump %i\n",
1066 INSN_UID (insn), INSN_UID (BB_END (src)));
1069 delete_insn_chain (kill_from, insn, false);
1071 /* Recognize a tablejump that we are converting to a
1072 simple jump and remove its associated CODE_LABEL
1073 and ADDR_VEC or ADDR_DIFF_VEC. */
1074 if (tablejump_p (insn, &label, &table))
1075 delete_insn_chain (label, table, false);
1077 barrier = next_nonnote_insn (BB_END (src));
1078 if (!barrier || !BARRIER_P (barrier))
1079 emit_barrier_after (BB_END (src));
1080 else
1082 if (barrier != NEXT_INSN (BB_END (src)))
1084 /* Move the jump before barrier so that the notes
1085 which originally were or were created before jump table are
1086 inside the basic block. */
1087 rtx new_insn = BB_END (src);
1089 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
1090 PREV_INSN (barrier), src);
1092 NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
1093 PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
1095 NEXT_INSN (new_insn) = barrier;
1096 NEXT_INSN (PREV_INSN (barrier)) = new_insn;
1098 PREV_INSN (new_insn) = PREV_INSN (barrier);
1099 PREV_INSN (barrier) = new_insn;
1104 /* Keep only one edge out and set proper flags. */
1105 if (!single_succ_p (src))
1106 remove_edge (e);
1107 gcc_assert (single_succ_p (src));
1109 e = single_succ_edge (src);
1110 if (fallthru)
1111 e->flags = EDGE_FALLTHRU;
1112 else
1113 e->flags = 0;
1115 e->probability = REG_BR_PROB_BASE;
1116 e->count = src->count;
1118 if (e->dest != target)
1119 redirect_edge_succ (e, target);
1120 return e;
1123 /* Subroutine of redirect_branch_edge that tries to patch the jump
1124 instruction INSN so that it reaches block NEW. Do this
1125 only when it originally reached block OLD. Return true if this
1126 worked or the original target wasn't OLD, return false if redirection
1127 doesn't work. */
1129 static bool
1130 patch_jump_insn (rtx insn, rtx old_label, basic_block new_bb)
1132 rtx tmp;
1133 /* Recognize a tablejump and adjust all matching cases. */
1134 if (tablejump_p (insn, NULL, &tmp))
1136 rtvec vec;
1137 int j;
1138 rtx new_label = block_label (new_bb);
1140 if (new_bb == EXIT_BLOCK_PTR)
1141 return false;
1142 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
1143 vec = XVEC (PATTERN (tmp), 0);
1144 else
1145 vec = XVEC (PATTERN (tmp), 1);
1147 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
1148 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
1150 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
1151 --LABEL_NUSES (old_label);
1152 ++LABEL_NUSES (new_label);
1155 /* Handle casesi dispatch insns. */
1156 if ((tmp = single_set (insn)) != NULL
1157 && SET_DEST (tmp) == pc_rtx
1158 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
1159 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
1160 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
1162 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
1163 new_label);
1164 --LABEL_NUSES (old_label);
1165 ++LABEL_NUSES (new_label);
1168 else if ((tmp = extract_asm_operands (PATTERN (insn))) != NULL)
1170 int i, n = ASM_OPERANDS_LABEL_LENGTH (tmp);
1171 rtx new_label, note;
1173 if (new_bb == EXIT_BLOCK_PTR)
1174 return false;
1175 new_label = block_label (new_bb);
1177 for (i = 0; i < n; ++i)
1179 rtx old_ref = ASM_OPERANDS_LABEL (tmp, i);
1180 gcc_assert (GET_CODE (old_ref) == LABEL_REF);
1181 if (XEXP (old_ref, 0) == old_label)
1183 ASM_OPERANDS_LABEL (tmp, i)
1184 = gen_rtx_LABEL_REF (Pmode, new_label);
1185 --LABEL_NUSES (old_label);
1186 ++LABEL_NUSES (new_label);
1190 if (JUMP_LABEL (insn) == old_label)
1192 JUMP_LABEL (insn) = new_label;
1193 note = find_reg_note (insn, REG_LABEL_TARGET, new_label);
1194 if (note)
1195 remove_note (insn, note);
1197 else
1199 note = find_reg_note (insn, REG_LABEL_TARGET, old_label);
1200 if (note)
1201 remove_note (insn, note);
1202 if (JUMP_LABEL (insn) != new_label
1203 && !find_reg_note (insn, REG_LABEL_TARGET, new_label))
1204 add_reg_note (insn, REG_LABEL_TARGET, new_label);
1206 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, old_label))
1207 != NULL_RTX)
1208 XEXP (note, 0) = new_label;
1210 else
1212 /* ?? We may play the games with moving the named labels from
1213 one basic block to the other in case only one computed_jump is
1214 available. */
1215 if (computed_jump_p (insn)
1216 /* A return instruction can't be redirected. */
1217 || returnjump_p (insn))
1218 return false;
1220 if (!currently_expanding_to_rtl || JUMP_LABEL (insn) == old_label)
1222 /* If the insn doesn't go where we think, we're confused. */
1223 gcc_assert (JUMP_LABEL (insn) == old_label);
1225 /* If the substitution doesn't succeed, die. This can happen
1226 if the back end emitted unrecognizable instructions or if
1227 target is exit block on some arches. */
1228 if (!redirect_jump (insn, block_label (new_bb), 0))
1230 gcc_assert (new_bb == EXIT_BLOCK_PTR);
1231 return false;
1235 return true;
1239 /* Redirect edge representing branch of (un)conditional jump or tablejump,
1240 NULL on failure */
1241 static edge
1242 redirect_branch_edge (edge e, basic_block target)
1244 rtx old_label = BB_HEAD (e->dest);
1245 basic_block src = e->src;
1246 rtx insn = BB_END (src);
1248 /* We can only redirect non-fallthru edges of jump insn. */
1249 if (e->flags & EDGE_FALLTHRU)
1250 return NULL;
1251 else if (!JUMP_P (insn) && !currently_expanding_to_rtl)
1252 return NULL;
1254 if (!currently_expanding_to_rtl)
1256 if (!patch_jump_insn (insn, old_label, target))
1257 return NULL;
1259 else
1260 /* When expanding this BB might actually contain multiple
1261 jumps (i.e. not yet split by find_many_sub_basic_blocks).
1262 Redirect all of those that match our label. */
1263 FOR_BB_INSNS (src, insn)
1264 if (JUMP_P (insn) && !patch_jump_insn (insn, old_label, target))
1265 return NULL;
1267 if (dump_file)
1268 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
1269 e->src->index, e->dest->index, target->index);
1271 if (e->dest != target)
1272 e = redirect_edge_succ_nodup (e, target);
1274 return e;
1277 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
1278 expense of adding new instructions or reordering basic blocks.
1280 Function can be also called with edge destination equivalent to the TARGET.
1281 Then it should try the simplifications and do nothing if none is possible.
1283 Return edge representing the branch if transformation succeeded. Return NULL
1284 on failure.
1285 We still return NULL in case E already destinated TARGET and we didn't
1286 managed to simplify instruction stream. */
1288 static edge
1289 rtl_redirect_edge_and_branch (edge e, basic_block target)
1291 edge ret;
1292 basic_block src = e->src;
1294 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
1295 return NULL;
1297 if (e->dest == target)
1298 return e;
1300 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
1302 df_set_bb_dirty (src);
1303 return ret;
1306 ret = redirect_branch_edge (e, target);
1307 if (!ret)
1308 return NULL;
1310 df_set_bb_dirty (src);
1311 return ret;
1314 /* Like force_nonfallthru below, but additionally performs redirection
1315 Used by redirect_edge_and_branch_force. JUMP_LABEL is used only
1316 when redirecting to the EXIT_BLOCK, it is either ret_rtx or
1317 simple_return_rtx, indicating which kind of returnjump to create.
1318 It should be NULL otherwise. */
1320 basic_block
1321 force_nonfallthru_and_redirect (edge e, basic_block target, rtx jump_label)
1323 basic_block jump_block, new_bb = NULL, src = e->src;
1324 rtx note;
1325 edge new_edge;
1326 int abnormal_edge_flags = 0;
1327 bool asm_goto_edge = false;
1328 int loc;
1330 /* In the case the last instruction is conditional jump to the next
1331 instruction, first redirect the jump itself and then continue
1332 by creating a basic block afterwards to redirect fallthru edge. */
1333 if (e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR
1334 && any_condjump_p (BB_END (e->src))
1335 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1337 rtx note;
1338 edge b = unchecked_make_edge (e->src, target, 0);
1339 bool redirected;
1341 redirected = redirect_jump (BB_END (e->src), block_label (target), 0);
1342 gcc_assert (redirected);
1344 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1345 if (note)
1347 int prob = INTVAL (XEXP (note, 0));
1349 b->probability = prob;
1350 b->count = e->count * prob / REG_BR_PROB_BASE;
1351 e->probability -= e->probability;
1352 e->count -= b->count;
1353 if (e->probability < 0)
1354 e->probability = 0;
1355 if (e->count < 0)
1356 e->count = 0;
1360 if (e->flags & EDGE_ABNORMAL)
1362 /* Irritating special case - fallthru edge to the same block as abnormal
1363 edge.
1364 We can't redirect abnormal edge, but we still can split the fallthru
1365 one and create separate abnormal edge to original destination.
1366 This allows bb-reorder to make such edge non-fallthru. */
1367 gcc_assert (e->dest == target);
1368 abnormal_edge_flags = e->flags & ~EDGE_FALLTHRU;
1369 e->flags &= EDGE_FALLTHRU;
1371 else
1373 gcc_assert (e->flags & EDGE_FALLTHRU);
1374 if (e->src == ENTRY_BLOCK_PTR)
1376 /* We can't redirect the entry block. Create an empty block
1377 at the start of the function which we use to add the new
1378 jump. */
1379 edge tmp;
1380 edge_iterator ei;
1381 bool found = false;
1383 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, ENTRY_BLOCK_PTR);
1385 /* Change the existing edge's source to be the new block, and add
1386 a new edge from the entry block to the new block. */
1387 e->src = bb;
1388 for (ei = ei_start (ENTRY_BLOCK_PTR->succs); (tmp = ei_safe_edge (ei)); )
1390 if (tmp == e)
1392 VEC_unordered_remove (edge, ENTRY_BLOCK_PTR->succs, ei.index);
1393 found = true;
1394 break;
1396 else
1397 ei_next (&ei);
1400 gcc_assert (found);
1402 VEC_safe_push (edge, gc, bb->succs, e);
1403 make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
1407 /* If e->src ends with asm goto, see if any of the ASM_OPERANDS_LABELs
1408 don't point to the target or fallthru label. */
1409 if (JUMP_P (BB_END (e->src))
1410 && target != EXIT_BLOCK_PTR
1411 && (e->flags & EDGE_FALLTHRU)
1412 && (note = extract_asm_operands (PATTERN (BB_END (e->src)))))
1414 int i, n = ASM_OPERANDS_LABEL_LENGTH (note);
1416 for (i = 0; i < n; ++i)
1418 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (e->dest))
1419 XEXP (ASM_OPERANDS_LABEL (note, i), 0) = block_label (target);
1420 if (XEXP (ASM_OPERANDS_LABEL (note, i), 0) == BB_HEAD (target))
1421 asm_goto_edge = true;
1425 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags || asm_goto_edge)
1427 gcov_type count = e->count;
1428 int probability = e->probability;
1429 /* Create the new structures. */
1431 /* If the old block ended with a tablejump, skip its table
1432 by searching forward from there. Otherwise start searching
1433 forward from the last instruction of the old block. */
1434 if (!tablejump_p (BB_END (e->src), NULL, &note))
1435 note = BB_END (e->src);
1436 note = NEXT_INSN (note);
1438 jump_block = create_basic_block (note, NULL, e->src);
1439 jump_block->count = count;
1440 jump_block->frequency = EDGE_FREQUENCY (e);
1442 /* Make sure new block ends up in correct hot/cold section. */
1444 BB_COPY_PARTITION (jump_block, e->src);
1445 if (flag_reorder_blocks_and_partition
1446 && targetm_common.have_named_sections
1447 && JUMP_P (BB_END (jump_block))
1448 && !any_condjump_p (BB_END (jump_block))
1449 && (EDGE_SUCC (jump_block, 0)->flags & EDGE_CROSSING))
1450 add_reg_note (BB_END (jump_block), REG_CROSSING_JUMP, NULL_RTX);
1452 /* Wire edge in. */
1453 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1454 new_edge->probability = probability;
1455 new_edge->count = count;
1457 /* Redirect old edge. */
1458 redirect_edge_pred (e, jump_block);
1459 e->probability = REG_BR_PROB_BASE;
1461 /* If asm goto has any label refs to target's label,
1462 add also edge from asm goto bb to target. */
1463 if (asm_goto_edge)
1465 new_edge->probability /= 2;
1466 new_edge->count /= 2;
1467 jump_block->count /= 2;
1468 jump_block->frequency /= 2;
1469 new_edge = make_edge (new_edge->src, target,
1470 e->flags & ~EDGE_FALLTHRU);
1471 new_edge->probability = probability - probability / 2;
1472 new_edge->count = count - count / 2;
1475 new_bb = jump_block;
1477 else
1478 jump_block = e->src;
1480 if (e->goto_locus && e->goto_block == NULL)
1481 loc = e->goto_locus;
1482 else
1483 loc = 0;
1484 e->flags &= ~EDGE_FALLTHRU;
1485 if (target == EXIT_BLOCK_PTR)
1487 if (jump_label == ret_rtx)
1489 #ifdef HAVE_return
1490 emit_jump_insn_after_setloc (gen_return (), BB_END (jump_block), loc);
1491 #else
1492 gcc_unreachable ();
1493 #endif
1495 else
1497 gcc_assert (jump_label == simple_return_rtx);
1498 #ifdef HAVE_simple_return
1499 emit_jump_insn_after_setloc (gen_simple_return (),
1500 BB_END (jump_block), loc);
1501 #else
1502 gcc_unreachable ();
1503 #endif
1505 set_return_jump_label (BB_END (jump_block));
1507 else
1509 rtx label = block_label (target);
1510 emit_jump_insn_after_setloc (gen_jump (label), BB_END (jump_block), loc);
1511 JUMP_LABEL (BB_END (jump_block)) = label;
1512 LABEL_NUSES (label)++;
1515 emit_barrier_after (BB_END (jump_block));
1516 redirect_edge_succ_nodup (e, target);
1518 if (abnormal_edge_flags)
1519 make_edge (src, target, abnormal_edge_flags);
1521 df_mark_solutions_dirty ();
1522 return new_bb;
1525 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1526 (and possibly create new basic block) to make edge non-fallthru.
1527 Return newly created BB or NULL if none. */
1529 static basic_block
1530 rtl_force_nonfallthru (edge e)
1532 return force_nonfallthru_and_redirect (e, e->dest, NULL_RTX);
1535 /* Redirect edge even at the expense of creating new jump insn or
1536 basic block. Return new basic block if created, NULL otherwise.
1537 Conversion must be possible. */
1539 static basic_block
1540 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1542 if (redirect_edge_and_branch (e, target)
1543 || e->dest == target)
1544 return NULL;
1546 /* In case the edge redirection failed, try to force it to be non-fallthru
1547 and redirect newly created simplejump. */
1548 df_set_bb_dirty (e->src);
1549 return force_nonfallthru_and_redirect (e, target, NULL_RTX);
1552 /* The given edge should potentially be a fallthru edge. If that is in
1553 fact true, delete the jump and barriers that are in the way. */
1555 static void
1556 rtl_tidy_fallthru_edge (edge e)
1558 rtx q;
1559 basic_block b = e->src, c = b->next_bb;
1561 /* ??? In a late-running flow pass, other folks may have deleted basic
1562 blocks by nopping out blocks, leaving multiple BARRIERs between here
1563 and the target label. They ought to be chastised and fixed.
1565 We can also wind up with a sequence of undeletable labels between
1566 one block and the next.
1568 So search through a sequence of barriers, labels, and notes for
1569 the head of block C and assert that we really do fall through. */
1571 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1572 if (INSN_P (q))
1573 return;
1575 /* Remove what will soon cease being the jump insn from the source block.
1576 If block B consisted only of this single jump, turn it into a deleted
1577 note. */
1578 q = BB_END (b);
1579 if (JUMP_P (q)
1580 && onlyjump_p (q)
1581 && (any_uncondjump_p (q)
1582 || single_succ_p (b)))
1584 #ifdef HAVE_cc0
1585 /* If this was a conditional jump, we need to also delete
1586 the insn that set cc0. */
1587 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1588 q = PREV_INSN (q);
1589 #endif
1591 q = PREV_INSN (q);
1594 /* Selectively unlink the sequence. */
1595 if (q != PREV_INSN (BB_HEAD (c)))
1596 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1598 e->flags |= EDGE_FALLTHRU;
1601 /* Should move basic block BB after basic block AFTER. NIY. */
1603 static bool
1604 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1605 basic_block after ATTRIBUTE_UNUSED)
1607 return false;
1610 /* Split a (typically critical) edge. Return the new block.
1611 The edge must not be abnormal.
1613 ??? The code generally expects to be called on critical edges.
1614 The case of a block ending in an unconditional jump to a
1615 block with multiple predecessors is not handled optimally. */
1617 static basic_block
1618 rtl_split_edge (edge edge_in)
1620 basic_block bb;
1621 rtx before;
1623 /* Abnormal edges cannot be split. */
1624 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1626 /* We are going to place the new block in front of edge destination.
1627 Avoid existence of fallthru predecessors. */
1628 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1630 edge e = find_fallthru_edge (edge_in->dest->preds);
1632 if (e)
1633 force_nonfallthru (e);
1636 /* Create the basic block note. */
1637 if (edge_in->dest != EXIT_BLOCK_PTR)
1638 before = BB_HEAD (edge_in->dest);
1639 else
1640 before = NULL_RTX;
1642 /* If this is a fall through edge to the exit block, the blocks might be
1643 not adjacent, and the right place is after the source. */
1644 if ((edge_in->flags & EDGE_FALLTHRU) && edge_in->dest == EXIT_BLOCK_PTR)
1646 before = NEXT_INSN (BB_END (edge_in->src));
1647 bb = create_basic_block (before, NULL, edge_in->src);
1648 BB_COPY_PARTITION (bb, edge_in->src);
1650 else
1652 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1653 /* ??? Why not edge_in->dest->prev_bb here? */
1654 BB_COPY_PARTITION (bb, edge_in->dest);
1657 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1659 /* For non-fallthru edges, we must adjust the predecessor's
1660 jump instruction to target our new block. */
1661 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1663 edge redirected = redirect_edge_and_branch (edge_in, bb);
1664 gcc_assert (redirected);
1666 else
1668 if (edge_in->src != ENTRY_BLOCK_PTR)
1670 /* For asm goto even splitting of fallthru edge might
1671 need insn patching, as other labels might point to the
1672 old label. */
1673 rtx last = BB_END (edge_in->src);
1674 if (last
1675 && JUMP_P (last)
1676 && edge_in->dest != EXIT_BLOCK_PTR
1677 && extract_asm_operands (PATTERN (last)) != NULL_RTX
1678 && patch_jump_insn (last, before, bb))
1679 df_set_bb_dirty (edge_in->src);
1681 redirect_edge_succ (edge_in, bb);
1684 return bb;
1687 /* Queue instructions for insertion on an edge between two basic blocks.
1688 The new instructions and basic blocks (if any) will not appear in the
1689 CFG until commit_edge_insertions is called. */
1691 void
1692 insert_insn_on_edge (rtx pattern, edge e)
1694 /* We cannot insert instructions on an abnormal critical edge.
1695 It will be easier to find the culprit if we die now. */
1696 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1698 if (e->insns.r == NULL_RTX)
1699 start_sequence ();
1700 else
1701 push_to_sequence (e->insns.r);
1703 emit_insn (pattern);
1705 e->insns.r = get_insns ();
1706 end_sequence ();
1709 /* Update the CFG for the instructions queued on edge E. */
1711 void
1712 commit_one_edge_insertion (edge e)
1714 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1715 basic_block bb;
1717 /* Pull the insns off the edge now since the edge might go away. */
1718 insns = e->insns.r;
1719 e->insns.r = NULL_RTX;
1721 /* Figure out where to put these insns. If the destination has
1722 one predecessor, insert there. Except for the exit block. */
1723 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR)
1725 bb = e->dest;
1727 /* Get the location correct wrt a code label, and "nice" wrt
1728 a basic block note, and before everything else. */
1729 tmp = BB_HEAD (bb);
1730 if (LABEL_P (tmp))
1731 tmp = NEXT_INSN (tmp);
1732 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1733 tmp = NEXT_INSN (tmp);
1734 if (tmp == BB_HEAD (bb))
1735 before = tmp;
1736 else if (tmp)
1737 after = PREV_INSN (tmp);
1738 else
1739 after = get_last_insn ();
1742 /* If the source has one successor and the edge is not abnormal,
1743 insert there. Except for the entry block. */
1744 else if ((e->flags & EDGE_ABNORMAL) == 0
1745 && single_succ_p (e->src)
1746 && e->src != ENTRY_BLOCK_PTR)
1748 bb = e->src;
1750 /* It is possible to have a non-simple jump here. Consider a target
1751 where some forms of unconditional jumps clobber a register. This
1752 happens on the fr30 for example.
1754 We know this block has a single successor, so we can just emit
1755 the queued insns before the jump. */
1756 if (JUMP_P (BB_END (bb)))
1757 before = BB_END (bb);
1758 else
1760 /* We'd better be fallthru, or we've lost track of what's what. */
1761 gcc_assert (e->flags & EDGE_FALLTHRU);
1763 after = BB_END (bb);
1767 /* Otherwise we must split the edge. */
1768 else
1770 bb = split_edge (e);
1771 after = BB_END (bb);
1773 if (flag_reorder_blocks_and_partition
1774 && targetm_common.have_named_sections
1775 && e->src != ENTRY_BLOCK_PTR
1776 && BB_PARTITION (e->src) == BB_COLD_PARTITION
1777 && !(e->flags & EDGE_CROSSING)
1778 && JUMP_P (after)
1779 && !any_condjump_p (after)
1780 && (single_succ_edge (bb)->flags & EDGE_CROSSING))
1781 add_reg_note (after, REG_CROSSING_JUMP, NULL_RTX);
1784 /* Now that we've found the spot, do the insertion. */
1785 if (before)
1787 emit_insn_before_noloc (insns, before, bb);
1788 last = prev_nonnote_insn (before);
1790 else
1791 last = emit_insn_after_noloc (insns, after, bb);
1793 if (returnjump_p (last))
1795 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1796 This is not currently a problem because this only happens
1797 for the (single) epilogue, which already has a fallthru edge
1798 to EXIT. */
1800 e = single_succ_edge (bb);
1801 gcc_assert (e->dest == EXIT_BLOCK_PTR
1802 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
1804 e->flags &= ~EDGE_FALLTHRU;
1805 emit_barrier_after (last);
1807 if (before)
1808 delete_insn (before);
1810 else
1811 gcc_assert (!JUMP_P (last));
1814 /* Update the CFG for all queued instructions. */
1816 void
1817 commit_edge_insertions (void)
1819 basic_block bb;
1821 #ifdef ENABLE_CHECKING
1822 verify_flow_info ();
1823 #endif
1825 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1827 edge e;
1828 edge_iterator ei;
1830 FOR_EACH_EDGE (e, ei, bb->succs)
1831 if (e->insns.r)
1832 commit_one_edge_insertion (e);
1837 /* Print out RTL-specific basic block information (live information
1838 at start and end with TDF_DETAILS). FLAGS are the TDF_* masks
1839 documented in dumpfile.h. */
1841 static void
1842 rtl_dump_bb (FILE *outf, basic_block bb, int indent, int flags)
1844 rtx insn;
1845 rtx last;
1846 char *s_indent;
1848 s_indent = (char *) alloca ((size_t) indent + 1);
1849 memset (s_indent, ' ', (size_t) indent);
1850 s_indent[indent] = '\0';
1852 if (df && (flags & TDF_DETAILS))
1854 df_dump_top (bb, outf);
1855 putc ('\n', outf);
1858 if (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK)
1859 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
1860 insn = NEXT_INSN (insn))
1862 if (! (flags & TDF_SLIM))
1863 print_rtl_single (outf, insn);
1864 else
1865 dump_insn_slim (outf, insn);
1869 if (df && (flags & TDF_DETAILS))
1871 df_dump_bottom (bb, outf);
1872 putc ('\n', outf);
1877 /* Like dump_function_to_file, but for RTL. Print out dataflow information
1878 for the start of each basic block. FLAGS are the TDF_* masks documented
1879 in dumpfile.h. */
1881 void
1882 print_rtl_with_bb (FILE *outf, const_rtx rtx_first, int flags)
1884 const_rtx tmp_rtx;
1885 if (rtx_first == 0)
1886 fprintf (outf, "(nil)\n");
1887 else
1889 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1890 int max_uid = get_max_uid ();
1891 basic_block *start = XCNEWVEC (basic_block, max_uid);
1892 basic_block *end = XCNEWVEC (basic_block, max_uid);
1893 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
1894 basic_block bb;
1896 /* After freeing the CFG, we still have BLOCK_FOR_INSN set on most
1897 insns, but the CFG is not maintained so the basic block info
1898 is not reliable. Therefore it's omitted from the dumps. */
1899 if (! (cfun->curr_properties & PROP_cfg))
1900 flags &= ~TDF_BLOCKS;
1902 if (df)
1903 df_dump_start (outf);
1905 if (flags & TDF_BLOCKS)
1907 FOR_EACH_BB_REVERSE (bb)
1909 rtx x;
1911 start[INSN_UID (BB_HEAD (bb))] = bb;
1912 end[INSN_UID (BB_END (bb))] = bb;
1913 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
1915 enum bb_state state = IN_MULTIPLE_BB;
1917 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1918 state = IN_ONE_BB;
1919 in_bb_p[INSN_UID (x)] = state;
1921 if (x == BB_END (bb))
1922 break;
1927 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1929 if (flags & TDF_BLOCKS)
1931 bb = start[INSN_UID (tmp_rtx)];
1932 if (bb != NULL)
1934 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, true, false);
1935 if (df && (flags & TDF_DETAILS))
1936 df_dump_top (bb, outf);
1939 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1940 && !NOTE_P (tmp_rtx)
1941 && !BARRIER_P (tmp_rtx))
1942 fprintf (outf, ";; Insn is not within a basic block\n");
1943 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1944 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1947 if (! (flags & TDF_SLIM))
1948 print_rtl_single (outf, tmp_rtx);
1949 else
1950 dump_insn_slim (outf, tmp_rtx);
1952 if (flags & TDF_BLOCKS)
1954 bb = end[INSN_UID (tmp_rtx)];
1955 if (bb != NULL)
1957 dump_bb_info (outf, bb, 0, dump_flags | TDF_COMMENT, false, true);
1958 if (df && (flags & TDF_DETAILS))
1959 df_dump_bottom (bb, outf);
1960 putc ('\n', outf);
1965 free (start);
1966 free (end);
1967 free (in_bb_p);
1970 if (crtl->epilogue_delay_list != 0)
1972 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1973 for (tmp_rtx = crtl->epilogue_delay_list; tmp_rtx != 0;
1974 tmp_rtx = XEXP (tmp_rtx, 1))
1975 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1979 /* Update the branch probability of BB if a REG_BR_PROB is present. */
1981 void
1982 update_br_prob_note (basic_block bb)
1984 rtx note;
1985 if (!JUMP_P (BB_END (bb)))
1986 return;
1987 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
1988 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
1989 return;
1990 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
1993 /* Get the last insn associated with block BB (that includes barriers and
1994 tablejumps after BB). */
1996 get_last_bb_insn (basic_block bb)
1998 rtx tmp;
1999 rtx end = BB_END (bb);
2001 /* Include any jump table following the basic block. */
2002 if (tablejump_p (end, NULL, &tmp))
2003 end = tmp;
2005 /* Include any barriers that may follow the basic block. */
2006 tmp = next_nonnote_insn_bb (end);
2007 while (tmp && BARRIER_P (tmp))
2009 end = tmp;
2010 tmp = next_nonnote_insn_bb (end);
2013 return end;
2016 /* Verify the CFG and RTL consistency common for both underlying RTL and
2017 cfglayout RTL.
2019 Currently it does following checks:
2021 - overlapping of basic blocks
2022 - insns with wrong BLOCK_FOR_INSN pointers
2023 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
2024 - tails of basic blocks (ensure that boundary is necessary)
2025 - scans body of the basic block for JUMP_INSN, CODE_LABEL
2026 and NOTE_INSN_BASIC_BLOCK
2027 - verify that no fall_thru edge crosses hot/cold partition boundaries
2028 - verify that there are no pending RTL branch predictions
2030 In future it can be extended check a lot of other stuff as well
2031 (reachability of basic blocks, life information, etc. etc.). */
2033 static int
2034 rtl_verify_flow_info_1 (void)
2036 rtx x;
2037 int err = 0;
2038 basic_block bb;
2040 /* Check the general integrity of the basic blocks. */
2041 FOR_EACH_BB_REVERSE (bb)
2043 rtx insn;
2045 if (!(bb->flags & BB_RTL))
2047 error ("BB_RTL flag not set for block %d", bb->index);
2048 err = 1;
2051 FOR_BB_INSNS (bb, insn)
2052 if (BLOCK_FOR_INSN (insn) != bb)
2054 error ("insn %d basic block pointer is %d, should be %d",
2055 INSN_UID (insn),
2056 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
2057 bb->index);
2058 err = 1;
2061 for (insn = BB_HEADER (bb); insn; insn = NEXT_INSN (insn))
2062 if (!BARRIER_P (insn)
2063 && BLOCK_FOR_INSN (insn) != NULL)
2065 error ("insn %d in header of bb %d has non-NULL basic block",
2066 INSN_UID (insn), bb->index);
2067 err = 1;
2069 for (insn = BB_FOOTER (bb); insn; insn = NEXT_INSN (insn))
2070 if (!BARRIER_P (insn)
2071 && BLOCK_FOR_INSN (insn) != NULL)
2073 error ("insn %d in footer of bb %d has non-NULL basic block",
2074 INSN_UID (insn), bb->index);
2075 err = 1;
2079 /* Now check the basic blocks (boundaries etc.) */
2080 FOR_EACH_BB_REVERSE (bb)
2082 int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
2083 edge e, fallthru = NULL;
2084 rtx note;
2085 edge_iterator ei;
2087 if (JUMP_P (BB_END (bb))
2088 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
2089 && EDGE_COUNT (bb->succs) >= 2
2090 && any_condjump_p (BB_END (bb)))
2092 if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability
2093 && profile_status != PROFILE_ABSENT)
2095 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
2096 INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
2097 err = 1;
2100 FOR_EACH_EDGE (e, ei, bb->succs)
2102 bool is_crossing;
2104 if (e->flags & EDGE_FALLTHRU)
2105 n_fallthru++, fallthru = e;
2107 is_crossing = (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
2108 && e->src != ENTRY_BLOCK_PTR
2109 && e->dest != EXIT_BLOCK_PTR);
2110 if (e->flags & EDGE_CROSSING)
2112 if (!is_crossing)
2114 error ("EDGE_CROSSING incorrectly set across same section");
2115 err = 1;
2117 if (e->flags & EDGE_FALLTHRU)
2119 error ("fallthru edge crosses section boundary (bb %i)",
2120 e->src->index);
2121 err = 1;
2123 if (e->flags & EDGE_EH)
2125 error ("EH edge crosses section boundary (bb %i)",
2126 e->src->index);
2127 err = 1;
2130 else if (is_crossing)
2132 error ("EDGE_CROSSING missing across section boundary");
2133 err = 1;
2136 if ((e->flags & ~(EDGE_DFS_BACK
2137 | EDGE_CAN_FALLTHRU
2138 | EDGE_IRREDUCIBLE_LOOP
2139 | EDGE_LOOP_EXIT
2140 | EDGE_CROSSING
2141 | EDGE_PRESERVE)) == 0)
2142 n_branch++;
2144 if (e->flags & EDGE_ABNORMAL_CALL)
2145 n_call++;
2147 if (e->flags & EDGE_EH)
2148 n_eh++;
2149 else if (e->flags & EDGE_ABNORMAL)
2150 n_abnormal++;
2153 if (n_eh && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2155 error ("missing REG_EH_REGION note in the end of bb %i", bb->index);
2156 err = 1;
2158 if (n_eh > 1)
2160 error ("too many eh edges %i", bb->index);
2161 err = 1;
2163 if (n_branch
2164 && (!JUMP_P (BB_END (bb))
2165 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2166 || any_condjump_p (BB_END (bb))))))
2168 error ("too many outgoing branch edges from bb %i", bb->index);
2169 err = 1;
2171 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2173 error ("fallthru edge after unconditional jump %i", bb->index);
2174 err = 1;
2176 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2178 error ("wrong number of branch edges after unconditional jump %i",
2179 bb->index);
2180 err = 1;
2182 if (n_branch != 1 && any_condjump_p (BB_END (bb))
2183 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2185 error ("wrong amount of branch edges after conditional jump %i",
2186 bb->index);
2187 err = 1;
2189 if (n_call && !CALL_P (BB_END (bb)))
2191 error ("call edges for non-call insn in bb %i", bb->index);
2192 err = 1;
2194 if (n_abnormal
2195 && (!CALL_P (BB_END (bb)) && n_call != n_abnormal)
2196 && (!JUMP_P (BB_END (bb))
2197 || any_condjump_p (BB_END (bb))
2198 || any_uncondjump_p (BB_END (bb))))
2200 error ("abnormal edges for no purpose in bb %i", bb->index);
2201 err = 1;
2204 for (x = BB_HEAD (bb); x != NEXT_INSN (BB_END (bb)); x = NEXT_INSN (x))
2205 /* We may have a barrier inside a basic block before dead code
2206 elimination. There is no BLOCK_FOR_INSN field in a barrier. */
2207 if (!BARRIER_P (x) && BLOCK_FOR_INSN (x) != bb)
2209 debug_rtx (x);
2210 if (! BLOCK_FOR_INSN (x))
2211 error
2212 ("insn %d inside basic block %d but block_for_insn is NULL",
2213 INSN_UID (x), bb->index);
2214 else
2215 error
2216 ("insn %d inside basic block %d but block_for_insn is %i",
2217 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
2219 err = 1;
2222 /* OK pointers are correct. Now check the header of basic
2223 block. It ought to contain optional CODE_LABEL followed
2224 by NOTE_BASIC_BLOCK. */
2225 x = BB_HEAD (bb);
2226 if (LABEL_P (x))
2228 if (BB_END (bb) == x)
2230 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2231 bb->index);
2232 err = 1;
2235 x = NEXT_INSN (x);
2238 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2240 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2241 bb->index);
2242 err = 1;
2245 if (BB_END (bb) == x)
2246 /* Do checks for empty blocks here. */
2248 else
2249 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2251 if (NOTE_INSN_BASIC_BLOCK_P (x))
2253 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2254 INSN_UID (x), bb->index);
2255 err = 1;
2258 if (x == BB_END (bb))
2259 break;
2261 if (control_flow_insn_p (x))
2263 error ("in basic block %d:", bb->index);
2264 fatal_insn ("flow control insn inside a basic block", x);
2269 /* Clean up. */
2270 return err;
2273 /* Verify the CFG and RTL consistency common for both underlying RTL and
2274 cfglayout RTL.
2276 Currently it does following checks:
2277 - all checks of rtl_verify_flow_info_1
2278 - test head/end pointers
2279 - check that all insns are in the basic blocks
2280 (except the switch handling code, barriers and notes)
2281 - check that all returns are followed by barriers
2282 - check that all fallthru edge points to the adjacent blocks. */
2284 static int
2285 rtl_verify_flow_info (void)
2287 basic_block bb;
2288 int err = rtl_verify_flow_info_1 ();
2289 rtx x;
2290 rtx last_head = get_last_insn ();
2291 basic_block *bb_info;
2292 int num_bb_notes;
2293 const rtx rtx_first = get_insns ();
2294 basic_block last_bb_seen = ENTRY_BLOCK_PTR, curr_bb = NULL;
2295 const int max_uid = get_max_uid ();
2297 bb_info = XCNEWVEC (basic_block, max_uid);
2299 FOR_EACH_BB_REVERSE (bb)
2301 edge e;
2302 rtx head = BB_HEAD (bb);
2303 rtx end = BB_END (bb);
2305 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2307 /* Verify the end of the basic block is in the INSN chain. */
2308 if (x == end)
2309 break;
2311 /* And that the code outside of basic blocks has NULL bb field. */
2312 if (!BARRIER_P (x)
2313 && BLOCK_FOR_INSN (x) != NULL)
2315 error ("insn %d outside of basic blocks has non-NULL bb field",
2316 INSN_UID (x));
2317 err = 1;
2321 if (!x)
2323 error ("end insn %d for block %d not found in the insn stream",
2324 INSN_UID (end), bb->index);
2325 err = 1;
2328 /* Work backwards from the end to the head of the basic block
2329 to verify the head is in the RTL chain. */
2330 for (; x != NULL_RTX; x = PREV_INSN (x))
2332 /* While walking over the insn chain, verify insns appear
2333 in only one basic block. */
2334 if (bb_info[INSN_UID (x)] != NULL)
2336 error ("insn %d is in multiple basic blocks (%d and %d)",
2337 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
2338 err = 1;
2341 bb_info[INSN_UID (x)] = bb;
2343 if (x == head)
2344 break;
2346 if (!x)
2348 error ("head insn %d for block %d not found in the insn stream",
2349 INSN_UID (head), bb->index);
2350 err = 1;
2353 last_head = PREV_INSN (x);
2355 e = find_fallthru_edge (bb->succs);
2356 if (!e)
2358 rtx insn;
2360 /* Ensure existence of barrier in BB with no fallthru edges. */
2361 for (insn = NEXT_INSN (BB_END (bb)); ; insn = NEXT_INSN (insn))
2363 if (!insn || NOTE_INSN_BASIC_BLOCK_P (insn))
2365 error ("missing barrier after block %i", bb->index);
2366 err = 1;
2367 break;
2369 if (BARRIER_P (insn))
2370 break;
2373 else if (e->src != ENTRY_BLOCK_PTR
2374 && e->dest != EXIT_BLOCK_PTR)
2376 rtx insn;
2378 if (e->src->next_bb != e->dest)
2380 error
2381 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2382 e->src->index, e->dest->index);
2383 err = 1;
2385 else
2386 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2387 insn = NEXT_INSN (insn))
2388 if (BARRIER_P (insn) || INSN_P (insn))
2390 error ("verify_flow_info: Incorrect fallthru %i->%i",
2391 e->src->index, e->dest->index);
2392 fatal_insn ("wrong insn in the fallthru edge", insn);
2393 err = 1;
2398 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2400 /* Check that the code before the first basic block has NULL
2401 bb field. */
2402 if (!BARRIER_P (x)
2403 && BLOCK_FOR_INSN (x) != NULL)
2405 error ("insn %d outside of basic blocks has non-NULL bb field",
2406 INSN_UID (x));
2407 err = 1;
2410 free (bb_info);
2412 num_bb_notes = 0;
2413 last_bb_seen = ENTRY_BLOCK_PTR;
2415 for (x = rtx_first; x; x = NEXT_INSN (x))
2417 if (NOTE_INSN_BASIC_BLOCK_P (x))
2419 bb = NOTE_BASIC_BLOCK (x);
2421 num_bb_notes++;
2422 if (bb != last_bb_seen->next_bb)
2423 internal_error ("basic blocks not laid down consecutively");
2425 curr_bb = last_bb_seen = bb;
2428 if (!curr_bb)
2430 switch (GET_CODE (x))
2432 case BARRIER:
2433 case NOTE:
2434 break;
2436 case CODE_LABEL:
2437 /* An addr_vec is placed outside any basic block. */
2438 if (NEXT_INSN (x)
2439 && JUMP_TABLE_DATA_P (NEXT_INSN (x)))
2440 x = NEXT_INSN (x);
2442 /* But in any case, non-deletable labels can appear anywhere. */
2443 break;
2445 default:
2446 fatal_insn ("insn outside basic block", x);
2450 if (JUMP_P (x)
2451 && returnjump_p (x) && ! condjump_p (x)
2452 && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_insn (x))))
2453 fatal_insn ("return not followed by barrier", x);
2454 if (curr_bb && x == BB_END (curr_bb))
2455 curr_bb = NULL;
2458 if (num_bb_notes != n_basic_blocks - NUM_FIXED_BLOCKS)
2459 internal_error
2460 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2461 num_bb_notes, n_basic_blocks);
2463 return err;
2466 /* Assume that the preceding pass has possibly eliminated jump instructions
2467 or converted the unconditional jumps. Eliminate the edges from CFG.
2468 Return true if any edges are eliminated. */
2470 bool
2471 purge_dead_edges (basic_block bb)
2473 edge e;
2474 rtx insn = BB_END (bb), note;
2475 bool purged = false;
2476 bool found;
2477 edge_iterator ei;
2479 if (DEBUG_INSN_P (insn) && insn != BB_HEAD (bb))
2481 insn = PREV_INSN (insn);
2482 while ((DEBUG_INSN_P (insn) || NOTE_P (insn)) && insn != BB_HEAD (bb));
2484 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2485 if (NONJUMP_INSN_P (insn)
2486 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
2488 rtx eqnote;
2490 if (! may_trap_p (PATTERN (insn))
2491 || ((eqnote = find_reg_equal_equiv_note (insn))
2492 && ! may_trap_p (XEXP (eqnote, 0))))
2493 remove_note (insn, note);
2496 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2497 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2499 bool remove = false;
2501 /* There are three types of edges we need to handle correctly here: EH
2502 edges, abnormal call EH edges, and abnormal call non-EH edges. The
2503 latter can appear when nonlocal gotos are used. */
2504 if (e->flags & EDGE_ABNORMAL_CALL)
2506 if (!CALL_P (insn))
2507 remove = true;
2508 else if (can_nonlocal_goto (insn))
2510 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
2512 else if (flag_tm && find_reg_note (insn, REG_TM, NULL))
2514 else
2515 remove = true;
2517 else if (e->flags & EDGE_EH)
2518 remove = !can_throw_internal (insn);
2520 if (remove)
2522 remove_edge (e);
2523 df_set_bb_dirty (bb);
2524 purged = true;
2526 else
2527 ei_next (&ei);
2530 if (JUMP_P (insn))
2532 rtx note;
2533 edge b,f;
2534 edge_iterator ei;
2536 /* We do care only about conditional jumps and simplejumps. */
2537 if (!any_condjump_p (insn)
2538 && !returnjump_p (insn)
2539 && !simplejump_p (insn))
2540 return purged;
2542 /* Branch probability/prediction notes are defined only for
2543 condjumps. We've possibly turned condjump into simplejump. */
2544 if (simplejump_p (insn))
2546 note = find_reg_note (insn, REG_BR_PROB, NULL);
2547 if (note)
2548 remove_note (insn, note);
2549 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
2550 remove_note (insn, note);
2553 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2555 /* Avoid abnormal flags to leak from computed jumps turned
2556 into simplejumps. */
2558 e->flags &= ~EDGE_ABNORMAL;
2560 /* See if this edge is one we should keep. */
2561 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
2562 /* A conditional jump can fall through into the next
2563 block, so we should keep the edge. */
2565 ei_next (&ei);
2566 continue;
2568 else if (e->dest != EXIT_BLOCK_PTR
2569 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
2570 /* If the destination block is the target of the jump,
2571 keep the edge. */
2573 ei_next (&ei);
2574 continue;
2576 else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn))
2577 /* If the destination block is the exit block, and this
2578 instruction is a return, then keep the edge. */
2580 ei_next (&ei);
2581 continue;
2583 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
2584 /* Keep the edges that correspond to exceptions thrown by
2585 this instruction and rematerialize the EDGE_ABNORMAL
2586 flag we just cleared above. */
2588 e->flags |= EDGE_ABNORMAL;
2589 ei_next (&ei);
2590 continue;
2593 /* We do not need this edge. */
2594 df_set_bb_dirty (bb);
2595 purged = true;
2596 remove_edge (e);
2599 if (EDGE_COUNT (bb->succs) == 0 || !purged)
2600 return purged;
2602 if (dump_file)
2603 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
2605 if (!optimize)
2606 return purged;
2608 /* Redistribute probabilities. */
2609 if (single_succ_p (bb))
2611 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
2612 single_succ_edge (bb)->count = bb->count;
2614 else
2616 note = find_reg_note (insn, REG_BR_PROB, NULL);
2617 if (!note)
2618 return purged;
2620 b = BRANCH_EDGE (bb);
2621 f = FALLTHRU_EDGE (bb);
2622 b->probability = INTVAL (XEXP (note, 0));
2623 f->probability = REG_BR_PROB_BASE - b->probability;
2624 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2625 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2628 return purged;
2630 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
2632 /* First, there should not be any EH or ABCALL edges resulting
2633 from non-local gotos and the like. If there were, we shouldn't
2634 have created the sibcall in the first place. Second, there
2635 should of course never have been a fallthru edge. */
2636 gcc_assert (single_succ_p (bb));
2637 gcc_assert (single_succ_edge (bb)->flags
2638 == (EDGE_SIBCALL | EDGE_ABNORMAL));
2640 return 0;
2643 /* If we don't see a jump insn, we don't know exactly why the block would
2644 have been broken at this point. Look for a simple, non-fallthru edge,
2645 as these are only created by conditional branches. If we find such an
2646 edge we know that there used to be a jump here and can then safely
2647 remove all non-fallthru edges. */
2648 found = false;
2649 FOR_EACH_EDGE (e, ei, bb->succs)
2650 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
2652 found = true;
2653 break;
2656 if (!found)
2657 return purged;
2659 /* Remove all but the fake and fallthru edges. The fake edge may be
2660 the only successor for this block in the case of noreturn
2661 calls. */
2662 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2664 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
2666 df_set_bb_dirty (bb);
2667 remove_edge (e);
2668 purged = true;
2670 else
2671 ei_next (&ei);
2674 gcc_assert (single_succ_p (bb));
2676 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
2677 single_succ_edge (bb)->count = bb->count;
2679 if (dump_file)
2680 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
2681 bb->index);
2682 return purged;
2685 /* Search all basic blocks for potentially dead edges and purge them. Return
2686 true if some edge has been eliminated. */
2688 bool
2689 purge_all_dead_edges (void)
2691 int purged = false;
2692 basic_block bb;
2694 FOR_EACH_BB (bb)
2696 bool purged_here = purge_dead_edges (bb);
2698 purged |= purged_here;
2701 return purged;
2704 /* This is used by a few passes that emit some instructions after abnormal
2705 calls, moving the basic block's end, while they in fact do want to emit
2706 them on the fallthru edge. Look for abnormal call edges, find backward
2707 the call in the block and insert the instructions on the edge instead.
2709 Similarly, handle instructions throwing exceptions internally.
2711 Return true when instructions have been found and inserted on edges. */
2713 bool
2714 fixup_abnormal_edges (void)
2716 bool inserted = false;
2717 basic_block bb;
2719 FOR_EACH_BB (bb)
2721 edge e;
2722 edge_iterator ei;
2724 /* Look for cases we are interested in - calls or instructions causing
2725 exceptions. */
2726 FOR_EACH_EDGE (e, ei, bb->succs)
2727 if ((e->flags & EDGE_ABNORMAL_CALL)
2728 || ((e->flags & (EDGE_ABNORMAL | EDGE_EH))
2729 == (EDGE_ABNORMAL | EDGE_EH)))
2730 break;
2732 if (e && !CALL_P (BB_END (bb)) && !can_throw_internal (BB_END (bb)))
2734 rtx insn;
2736 /* Get past the new insns generated. Allow notes, as the insns
2737 may be already deleted. */
2738 insn = BB_END (bb);
2739 while ((NONJUMP_INSN_P (insn) || NOTE_P (insn))
2740 && !can_throw_internal (insn)
2741 && insn != BB_HEAD (bb))
2742 insn = PREV_INSN (insn);
2744 if (CALL_P (insn) || can_throw_internal (insn))
2746 rtx stop, next;
2748 e = find_fallthru_edge (bb->succs);
2750 stop = NEXT_INSN (BB_END (bb));
2751 BB_END (bb) = insn;
2753 for (insn = NEXT_INSN (insn); insn != stop; insn = next)
2755 next = NEXT_INSN (insn);
2756 if (INSN_P (insn))
2758 delete_insn (insn);
2760 /* Sometimes there's still the return value USE.
2761 If it's placed after a trapping call (i.e. that
2762 call is the last insn anyway), we have no fallthru
2763 edge. Simply delete this use and don't try to insert
2764 on the non-existent edge. */
2765 if (GET_CODE (PATTERN (insn)) != USE)
2767 /* We're not deleting it, we're moving it. */
2768 INSN_DELETED_P (insn) = 0;
2769 PREV_INSN (insn) = NULL_RTX;
2770 NEXT_INSN (insn) = NULL_RTX;
2772 insert_insn_on_edge (insn, e);
2773 inserted = true;
2776 else if (!BARRIER_P (insn))
2777 set_block_for_insn (insn, NULL);
2781 /* It may be that we don't find any trapping insn. In this
2782 case we discovered quite late that the insn that had been
2783 marked as can_throw_internal in fact couldn't trap at all.
2784 So we should in fact delete the EH edges out of the block. */
2785 else
2786 purge_dead_edges (bb);
2790 return inserted;
2793 /* Cut the insns from FIRST to LAST out of the insns stream. */
2796 unlink_insn_chain (rtx first, rtx last)
2798 rtx prevfirst = PREV_INSN (first);
2799 rtx nextlast = NEXT_INSN (last);
2801 PREV_INSN (first) = NULL;
2802 NEXT_INSN (last) = NULL;
2803 if (prevfirst)
2804 NEXT_INSN (prevfirst) = nextlast;
2805 if (nextlast)
2806 PREV_INSN (nextlast) = prevfirst;
2807 else
2808 set_last_insn (prevfirst);
2809 if (!prevfirst)
2810 set_first_insn (nextlast);
2811 return first;
2814 /* Skip over inter-block insns occurring after BB which are typically
2815 associated with BB (e.g., barriers). If there are any such insns,
2816 we return the last one. Otherwise, we return the end of BB. */
2818 static rtx
2819 skip_insns_after_block (basic_block bb)
2821 rtx insn, last_insn, next_head, prev;
2823 next_head = NULL_RTX;
2824 if (bb->next_bb != EXIT_BLOCK_PTR)
2825 next_head = BB_HEAD (bb->next_bb);
2827 for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
2829 if (insn == next_head)
2830 break;
2832 switch (GET_CODE (insn))
2834 case BARRIER:
2835 last_insn = insn;
2836 continue;
2838 case NOTE:
2839 switch (NOTE_KIND (insn))
2841 case NOTE_INSN_BLOCK_END:
2842 gcc_unreachable ();
2843 continue;
2844 default:
2845 continue;
2846 break;
2848 break;
2850 case CODE_LABEL:
2851 if (NEXT_INSN (insn)
2852 && JUMP_TABLE_DATA_P (NEXT_INSN (insn)))
2854 insn = NEXT_INSN (insn);
2855 last_insn = insn;
2856 continue;
2858 break;
2860 default:
2861 break;
2864 break;
2867 /* It is possible to hit contradictory sequence. For instance:
2869 jump_insn
2870 NOTE_INSN_BLOCK_BEG
2871 barrier
2873 Where barrier belongs to jump_insn, but the note does not. This can be
2874 created by removing the basic block originally following
2875 NOTE_INSN_BLOCK_BEG. In such case reorder the notes. */
2877 for (insn = last_insn; insn != BB_END (bb); insn = prev)
2879 prev = PREV_INSN (insn);
2880 if (NOTE_P (insn))
2881 switch (NOTE_KIND (insn))
2883 case NOTE_INSN_BLOCK_END:
2884 gcc_unreachable ();
2885 break;
2886 case NOTE_INSN_DELETED:
2887 case NOTE_INSN_DELETED_LABEL:
2888 case NOTE_INSN_DELETED_DEBUG_LABEL:
2889 continue;
2890 default:
2891 reorder_insns (insn, insn, last_insn);
2895 return last_insn;
2898 /* Locate or create a label for a given basic block. */
2900 static rtx
2901 label_for_bb (basic_block bb)
2903 rtx label = BB_HEAD (bb);
2905 if (!LABEL_P (label))
2907 if (dump_file)
2908 fprintf (dump_file, "Emitting label for block %d\n", bb->index);
2910 label = block_label (bb);
2913 return label;
2916 /* Locate the effective beginning and end of the insn chain for each
2917 block, as defined by skip_insns_after_block above. */
2919 static void
2920 record_effective_endpoints (void)
2922 rtx next_insn;
2923 basic_block bb;
2924 rtx insn;
2926 for (insn = get_insns ();
2927 insn
2928 && NOTE_P (insn)
2929 && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
2930 insn = NEXT_INSN (insn))
2931 continue;
2932 /* No basic blocks at all? */
2933 gcc_assert (insn);
2935 if (PREV_INSN (insn))
2936 cfg_layout_function_header =
2937 unlink_insn_chain (get_insns (), PREV_INSN (insn));
2938 else
2939 cfg_layout_function_header = NULL_RTX;
2941 next_insn = get_insns ();
2942 FOR_EACH_BB (bb)
2944 rtx end;
2946 if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
2947 BB_HEADER (bb) = unlink_insn_chain (next_insn,
2948 PREV_INSN (BB_HEAD (bb)));
2949 end = skip_insns_after_block (bb);
2950 if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
2951 BB_FOOTER (bb) = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
2952 next_insn = NEXT_INSN (BB_END (bb));
2955 cfg_layout_function_footer = next_insn;
2956 if (cfg_layout_function_footer)
2957 cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
2960 static unsigned int
2961 into_cfg_layout_mode (void)
2963 cfg_layout_initialize (0);
2964 return 0;
2967 static unsigned int
2968 outof_cfg_layout_mode (void)
2970 basic_block bb;
2972 FOR_EACH_BB (bb)
2973 if (bb->next_bb != EXIT_BLOCK_PTR)
2974 bb->aux = bb->next_bb;
2976 cfg_layout_finalize ();
2978 return 0;
2981 struct rtl_opt_pass pass_into_cfg_layout_mode =
2984 RTL_PASS,
2985 "into_cfglayout", /* name */
2986 NULL, /* gate */
2987 into_cfg_layout_mode, /* execute */
2988 NULL, /* sub */
2989 NULL, /* next */
2990 0, /* static_pass_number */
2991 TV_CFG, /* tv_id */
2992 0, /* properties_required */
2993 PROP_cfglayout, /* properties_provided */
2994 0, /* properties_destroyed */
2995 0, /* todo_flags_start */
2996 0 /* todo_flags_finish */
3000 struct rtl_opt_pass pass_outof_cfg_layout_mode =
3003 RTL_PASS,
3004 "outof_cfglayout", /* name */
3005 NULL, /* gate */
3006 outof_cfg_layout_mode, /* execute */
3007 NULL, /* sub */
3008 NULL, /* next */
3009 0, /* static_pass_number */
3010 TV_CFG, /* tv_id */
3011 0, /* properties_required */
3012 0, /* properties_provided */
3013 PROP_cfglayout, /* properties_destroyed */
3014 0, /* todo_flags_start */
3015 0 /* todo_flags_finish */
3020 /* Link the basic blocks in the correct order, compacting the basic
3021 block queue while at it. If STAY_IN_CFGLAYOUT_MODE is false, this
3022 function also clears the basic block header and footer fields.
3024 This function is usually called after a pass (e.g. tracer) finishes
3025 some transformations while in cfglayout mode. The required sequence
3026 of the basic blocks is in a linked list along the bb->aux field.
3027 This functions re-links the basic block prev_bb and next_bb pointers
3028 accordingly, and it compacts and renumbers the blocks.
3030 FIXME: This currently works only for RTL, but the only RTL-specific
3031 bits are the STAY_IN_CFGLAYOUT_MODE bits. The tracer pass was moved
3032 to GIMPLE a long time ago, but it doesn't relink the basic block
3033 chain. It could do that (to give better initial RTL) if this function
3034 is made IR-agnostic (and moved to cfganal.c or cfg.c while at it). */
3036 void
3037 relink_block_chain (bool stay_in_cfglayout_mode)
3039 basic_block bb, prev_bb;
3040 int index;
3042 /* Maybe dump the re-ordered sequence. */
3043 if (dump_file)
3045 fprintf (dump_file, "Reordered sequence:\n");
3046 for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
3048 bb = (basic_block) bb->aux, index++)
3050 fprintf (dump_file, " %i ", index);
3051 if (get_bb_original (bb))
3052 fprintf (dump_file, "duplicate of %i ",
3053 get_bb_original (bb)->index);
3054 else if (forwarder_block_p (bb)
3055 && !LABEL_P (BB_HEAD (bb)))
3056 fprintf (dump_file, "compensation ");
3057 else
3058 fprintf (dump_file, "bb %i ", bb->index);
3059 fprintf (dump_file, " [%i]\n", bb->frequency);
3063 /* Now reorder the blocks. */
3064 prev_bb = ENTRY_BLOCK_PTR;
3065 bb = ENTRY_BLOCK_PTR->next_bb;
3066 for (; bb; prev_bb = bb, bb = (basic_block) bb->aux)
3068 bb->prev_bb = prev_bb;
3069 prev_bb->next_bb = bb;
3071 prev_bb->next_bb = EXIT_BLOCK_PTR;
3072 EXIT_BLOCK_PTR->prev_bb = prev_bb;
3074 /* Then, clean up the aux fields. */
3075 FOR_ALL_BB (bb)
3077 bb->aux = NULL;
3078 if (!stay_in_cfglayout_mode)
3079 BB_HEADER (bb) = BB_FOOTER (bb) = NULL;
3082 /* Maybe reset the original copy tables, they are not valid anymore
3083 when we renumber the basic blocks in compact_blocks. If we are
3084 are going out of cfglayout mode, don't re-allocate the tables. */
3085 free_original_copy_tables ();
3086 if (stay_in_cfglayout_mode)
3087 initialize_original_copy_tables ();
3089 /* Finally, put basic_block_info in the new order. */
3090 compact_blocks ();
3094 /* Given a reorder chain, rearrange the code to match. */
3096 static void
3097 fixup_reorder_chain (void)
3099 basic_block bb;
3100 rtx insn = NULL;
3102 if (cfg_layout_function_header)
3104 set_first_insn (cfg_layout_function_header);
3105 insn = cfg_layout_function_header;
3106 while (NEXT_INSN (insn))
3107 insn = NEXT_INSN (insn);
3110 /* First do the bulk reordering -- rechain the blocks without regard to
3111 the needed changes to jumps and labels. */
3113 for (bb = ENTRY_BLOCK_PTR->next_bb; bb; bb = (basic_block) bb->aux)
3115 if (BB_HEADER (bb))
3117 if (insn)
3118 NEXT_INSN (insn) = BB_HEADER (bb);
3119 else
3120 set_first_insn (BB_HEADER (bb));
3121 PREV_INSN (BB_HEADER (bb)) = insn;
3122 insn = BB_HEADER (bb);
3123 while (NEXT_INSN (insn))
3124 insn = NEXT_INSN (insn);
3126 if (insn)
3127 NEXT_INSN (insn) = BB_HEAD (bb);
3128 else
3129 set_first_insn (BB_HEAD (bb));
3130 PREV_INSN (BB_HEAD (bb)) = insn;
3131 insn = BB_END (bb);
3132 if (BB_FOOTER (bb))
3134 NEXT_INSN (insn) = BB_FOOTER (bb);
3135 PREV_INSN (BB_FOOTER (bb)) = insn;
3136 while (NEXT_INSN (insn))
3137 insn = NEXT_INSN (insn);
3141 NEXT_INSN (insn) = cfg_layout_function_footer;
3142 if (cfg_layout_function_footer)
3143 PREV_INSN (cfg_layout_function_footer) = insn;
3145 while (NEXT_INSN (insn))
3146 insn = NEXT_INSN (insn);
3148 set_last_insn (insn);
3149 #ifdef ENABLE_CHECKING
3150 verify_insn_chain ();
3151 #endif
3153 /* Now add jumps and labels as needed to match the blocks new
3154 outgoing edges. */
3156 for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = (basic_block) bb->aux)
3158 edge e_fall, e_taken, e;
3159 rtx bb_end_insn;
3160 rtx ret_label = NULL_RTX;
3161 basic_block nb, src_bb;
3162 edge_iterator ei;
3164 if (EDGE_COUNT (bb->succs) == 0)
3165 continue;
3167 /* Find the old fallthru edge, and another non-EH edge for
3168 a taken jump. */
3169 e_taken = e_fall = NULL;
3171 FOR_EACH_EDGE (e, ei, bb->succs)
3172 if (e->flags & EDGE_FALLTHRU)
3173 e_fall = e;
3174 else if (! (e->flags & EDGE_EH))
3175 e_taken = e;
3177 bb_end_insn = BB_END (bb);
3178 if (JUMP_P (bb_end_insn))
3180 ret_label = JUMP_LABEL (bb_end_insn);
3181 if (any_condjump_p (bb_end_insn))
3183 /* This might happen if the conditional jump has side
3184 effects and could therefore not be optimized away.
3185 Make the basic block to end with a barrier in order
3186 to prevent rtl_verify_flow_info from complaining. */
3187 if (!e_fall)
3189 gcc_assert (!onlyjump_p (bb_end_insn)
3190 || returnjump_p (bb_end_insn));
3191 BB_FOOTER (bb) = emit_barrier_after (bb_end_insn);
3192 continue;
3195 /* If the old fallthru is still next, nothing to do. */
3196 if (bb->aux == e_fall->dest
3197 || e_fall->dest == EXIT_BLOCK_PTR)
3198 continue;
3200 /* The degenerated case of conditional jump jumping to the next
3201 instruction can happen for jumps with side effects. We need
3202 to construct a forwarder block and this will be done just
3203 fine by force_nonfallthru below. */
3204 if (!e_taken)
3207 /* There is another special case: if *neither* block is next,
3208 such as happens at the very end of a function, then we'll
3209 need to add a new unconditional jump. Choose the taken
3210 edge based on known or assumed probability. */
3211 else if (bb->aux != e_taken->dest)
3213 rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
3215 if (note
3216 && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
3217 && invert_jump (bb_end_insn,
3218 (e_fall->dest == EXIT_BLOCK_PTR
3219 ? NULL_RTX
3220 : label_for_bb (e_fall->dest)), 0))
3222 e_fall->flags &= ~EDGE_FALLTHRU;
3223 gcc_checking_assert (could_fall_through
3224 (e_taken->src, e_taken->dest));
3225 e_taken->flags |= EDGE_FALLTHRU;
3226 update_br_prob_note (bb);
3227 e = e_fall, e_fall = e_taken, e_taken = e;
3231 /* If the "jumping" edge is a crossing edge, and the fall
3232 through edge is non-crossing, leave things as they are. */
3233 else if ((e_taken->flags & EDGE_CROSSING)
3234 && !(e_fall->flags & EDGE_CROSSING))
3235 continue;
3237 /* Otherwise we can try to invert the jump. This will
3238 basically never fail, however, keep up the pretense. */
3239 else if (invert_jump (bb_end_insn,
3240 (e_fall->dest == EXIT_BLOCK_PTR
3241 ? NULL_RTX
3242 : label_for_bb (e_fall->dest)), 0))
3244 e_fall->flags &= ~EDGE_FALLTHRU;
3245 gcc_checking_assert (could_fall_through
3246 (e_taken->src, e_taken->dest));
3247 e_taken->flags |= EDGE_FALLTHRU;
3248 update_br_prob_note (bb);
3249 if (LABEL_NUSES (ret_label) == 0
3250 && single_pred_p (e_taken->dest))
3251 delete_insn (ret_label);
3252 continue;
3255 else if (extract_asm_operands (PATTERN (bb_end_insn)) != NULL)
3257 /* If the old fallthru is still next or if
3258 asm goto doesn't have a fallthru (e.g. when followed by
3259 __builtin_unreachable ()), nothing to do. */
3260 if (! e_fall
3261 || bb->aux == e_fall->dest
3262 || e_fall->dest == EXIT_BLOCK_PTR)
3263 continue;
3265 /* Otherwise we'll have to use the fallthru fixup below. */
3267 else
3269 /* Otherwise we have some return, switch or computed
3270 jump. In the 99% case, there should not have been a
3271 fallthru edge. */
3272 gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
3273 continue;
3276 else
3278 /* No fallthru implies a noreturn function with EH edges, or
3279 something similarly bizarre. In any case, we don't need to
3280 do anything. */
3281 if (! e_fall)
3282 continue;
3284 /* If the fallthru block is still next, nothing to do. */
3285 if (bb->aux == e_fall->dest)
3286 continue;
3288 /* A fallthru to exit block. */
3289 if (e_fall->dest == EXIT_BLOCK_PTR)
3290 continue;
3293 /* We got here if we need to add a new jump insn.
3294 Note force_nonfallthru can delete E_FALL and thus we have to
3295 save E_FALL->src prior to the call to force_nonfallthru. */
3296 src_bb = e_fall->src;
3297 nb = force_nonfallthru_and_redirect (e_fall, e_fall->dest, ret_label);
3298 if (nb)
3300 nb->aux = bb->aux;
3301 bb->aux = nb;
3302 /* Don't process this new block. */
3303 bb = nb;
3305 /* Make sure new bb is tagged for correct section (same as
3306 fall-thru source, since you cannot fall-thru across
3307 section boundaries). */
3308 BB_COPY_PARTITION (src_bb, single_pred (bb));
3309 if (flag_reorder_blocks_and_partition
3310 && targetm_common.have_named_sections
3311 && JUMP_P (BB_END (bb))
3312 && !any_condjump_p (BB_END (bb))
3313 && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
3314 add_reg_note (BB_END (bb), REG_CROSSING_JUMP, NULL_RTX);
3318 relink_block_chain (/*stay_in_cfglayout_mode=*/false);
3320 /* Annoying special case - jump around dead jumptables left in the code. */
3321 FOR_EACH_BB (bb)
3323 edge e = find_fallthru_edge (bb->succs);
3325 if (e && !can_fallthru (e->src, e->dest))
3326 force_nonfallthru (e);
3329 /* Ensure goto_locus from edges has some instructions with that locus
3330 in RTL. */
3331 if (!optimize)
3332 FOR_EACH_BB (bb)
3334 edge e;
3335 edge_iterator ei;
3337 FOR_EACH_EDGE (e, ei, bb->succs)
3338 if (e->goto_locus && !(e->flags & EDGE_ABNORMAL))
3340 edge e2;
3341 edge_iterator ei2;
3342 basic_block dest, nb;
3343 rtx end;
3345 insn = BB_END (e->src);
3346 end = PREV_INSN (BB_HEAD (e->src));
3347 while (insn != end
3348 && (!NONDEBUG_INSN_P (insn) || INSN_LOCATOR (insn) == 0))
3349 insn = PREV_INSN (insn);
3350 if (insn != end
3351 && locator_eq (INSN_LOCATOR (insn), (int) e->goto_locus))
3352 continue;
3353 if (simplejump_p (BB_END (e->src))
3354 && INSN_LOCATOR (BB_END (e->src)) == 0)
3356 INSN_LOCATOR (BB_END (e->src)) = e->goto_locus;
3357 continue;
3359 dest = e->dest;
3360 if (dest == EXIT_BLOCK_PTR)
3362 /* Non-fallthru edges to the exit block cannot be split. */
3363 if (!(e->flags & EDGE_FALLTHRU))
3364 continue;
3366 else
3368 insn = BB_HEAD (dest);
3369 end = NEXT_INSN (BB_END (dest));
3370 while (insn != end && !NONDEBUG_INSN_P (insn))
3371 insn = NEXT_INSN (insn);
3372 if (insn != end && INSN_LOCATOR (insn)
3373 && locator_eq (INSN_LOCATOR (insn), (int) e->goto_locus))
3374 continue;
3376 nb = split_edge (e);
3377 if (!INSN_P (BB_END (nb)))
3378 BB_END (nb) = emit_insn_after_noloc (gen_nop (), BB_END (nb),
3379 nb);
3380 INSN_LOCATOR (BB_END (nb)) = e->goto_locus;
3382 /* If there are other incoming edges to the destination block
3383 with the same goto locus, redirect them to the new block as
3384 well, this can prevent other such blocks from being created
3385 in subsequent iterations of the loop. */
3386 for (ei2 = ei_start (dest->preds); (e2 = ei_safe_edge (ei2)); )
3387 if (e2->goto_locus
3388 && !(e2->flags & (EDGE_ABNORMAL | EDGE_FALLTHRU))
3389 && locator_eq (e->goto_locus, e2->goto_locus))
3390 redirect_edge_and_branch (e2, nb);
3391 else
3392 ei_next (&ei2);
3397 /* Perform sanity checks on the insn chain.
3398 1. Check that next/prev pointers are consistent in both the forward and
3399 reverse direction.
3400 2. Count insns in chain, going both directions, and check if equal.
3401 3. Check that get_last_insn () returns the actual end of chain. */
3403 DEBUG_FUNCTION void
3404 verify_insn_chain (void)
3406 rtx x, prevx, nextx;
3407 int insn_cnt1, insn_cnt2;
3409 for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
3410 x != 0;
3411 prevx = x, insn_cnt1++, x = NEXT_INSN (x))
3412 gcc_assert (PREV_INSN (x) == prevx);
3414 gcc_assert (prevx == get_last_insn ());
3416 for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
3417 x != 0;
3418 nextx = x, insn_cnt2++, x = PREV_INSN (x))
3419 gcc_assert (NEXT_INSN (x) == nextx);
3421 gcc_assert (insn_cnt1 == insn_cnt2);
3424 /* If we have assembler epilogues, the block falling through to exit must
3425 be the last one in the reordered chain when we reach final. Ensure
3426 that this condition is met. */
3427 static void
3428 fixup_fallthru_exit_predecessor (void)
3430 edge e;
3431 basic_block bb = NULL;
3433 /* This transformation is not valid before reload, because we might
3434 separate a call from the instruction that copies the return
3435 value. */
3436 gcc_assert (reload_completed);
3438 e = find_fallthru_edge (EXIT_BLOCK_PTR->preds);
3439 if (e)
3440 bb = e->src;
3442 if (bb && bb->aux)
3444 basic_block c = ENTRY_BLOCK_PTR->next_bb;
3446 /* If the very first block is the one with the fall-through exit
3447 edge, we have to split that block. */
3448 if (c == bb)
3450 bb = split_block (bb, NULL)->dest;
3451 bb->aux = c->aux;
3452 c->aux = bb;
3453 BB_FOOTER (bb) = BB_FOOTER (c);
3454 BB_FOOTER (c) = NULL;
3457 while (c->aux != bb)
3458 c = (basic_block) c->aux;
3460 c->aux = bb->aux;
3461 while (c->aux)
3462 c = (basic_block) c->aux;
3464 c->aux = bb;
3465 bb->aux = NULL;
3469 /* In case there are more than one fallthru predecessors of exit, force that
3470 there is only one. */
3472 static void
3473 force_one_exit_fallthru (void)
3475 edge e, predecessor = NULL;
3476 bool more = false;
3477 edge_iterator ei;
3478 basic_block forwarder, bb;
3480 FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
3481 if (e->flags & EDGE_FALLTHRU)
3483 if (predecessor == NULL)
3484 predecessor = e;
3485 else
3487 more = true;
3488 break;
3492 if (!more)
3493 return;
3495 /* Exit has several fallthru predecessors. Create a forwarder block for
3496 them. */
3497 forwarder = split_edge (predecessor);
3498 for (ei = ei_start (EXIT_BLOCK_PTR->preds); (e = ei_safe_edge (ei)); )
3500 if (e->src == forwarder
3501 || !(e->flags & EDGE_FALLTHRU))
3502 ei_next (&ei);
3503 else
3504 redirect_edge_and_branch_force (e, forwarder);
3507 /* Fix up the chain of blocks -- make FORWARDER immediately precede the
3508 exit block. */
3509 FOR_EACH_BB (bb)
3511 if (bb->aux == NULL && bb != forwarder)
3513 bb->aux = forwarder;
3514 break;
3519 /* Return true in case it is possible to duplicate the basic block BB. */
3521 static bool
3522 cfg_layout_can_duplicate_bb_p (const_basic_block bb)
3524 /* Do not attempt to duplicate tablejumps, as we need to unshare
3525 the dispatch table. This is difficult to do, as the instructions
3526 computing jump destination may be hoisted outside the basic block. */
3527 if (tablejump_p (BB_END (bb), NULL, NULL))
3528 return false;
3530 /* Do not duplicate blocks containing insns that can't be copied. */
3531 if (targetm.cannot_copy_insn_p)
3533 rtx insn = BB_HEAD (bb);
3534 while (1)
3536 if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
3537 return false;
3538 if (insn == BB_END (bb))
3539 break;
3540 insn = NEXT_INSN (insn);
3544 return true;
3548 duplicate_insn_chain (rtx from, rtx to)
3550 rtx insn, last, copy;
3552 /* Avoid updating of boundaries of previous basic block. The
3553 note will get removed from insn stream in fixup. */
3554 last = emit_note (NOTE_INSN_DELETED);
3556 /* Create copy at the end of INSN chain. The chain will
3557 be reordered later. */
3558 for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
3560 switch (GET_CODE (insn))
3562 case DEBUG_INSN:
3563 /* Don't duplicate label debug insns. */
3564 if (TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL)
3565 break;
3566 /* FALLTHRU */
3567 case INSN:
3568 case CALL_INSN:
3569 case JUMP_INSN:
3570 /* Avoid copying of dispatch tables. We never duplicate
3571 tablejumps, so this can hit only in case the table got
3572 moved far from original jump. */
3573 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
3574 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
3576 /* Avoid copying following barrier as well if any
3577 (and debug insns in between). */
3578 rtx next;
3580 for (next = NEXT_INSN (insn);
3581 next != NEXT_INSN (to);
3582 next = NEXT_INSN (next))
3583 if (!DEBUG_INSN_P (next))
3584 break;
3585 if (next != NEXT_INSN (to) && BARRIER_P (next))
3586 insn = next;
3587 break;
3589 copy = emit_copy_of_insn_after (insn, get_last_insn ());
3590 if (JUMP_P (insn) && JUMP_LABEL (insn) != NULL_RTX
3591 && ANY_RETURN_P (JUMP_LABEL (insn)))
3592 JUMP_LABEL (copy) = JUMP_LABEL (insn);
3593 maybe_copy_prologue_epilogue_insn (insn, copy);
3594 break;
3596 case CODE_LABEL:
3597 break;
3599 case BARRIER:
3600 emit_barrier ();
3601 break;
3603 case NOTE:
3604 switch (NOTE_KIND (insn))
3606 /* In case prologue is empty and function contain label
3607 in first BB, we may want to copy the block. */
3608 case NOTE_INSN_PROLOGUE_END:
3610 case NOTE_INSN_DELETED:
3611 case NOTE_INSN_DELETED_LABEL:
3612 case NOTE_INSN_DELETED_DEBUG_LABEL:
3613 /* No problem to strip these. */
3614 case NOTE_INSN_FUNCTION_BEG:
3615 /* There is always just single entry to function. */
3616 case NOTE_INSN_BASIC_BLOCK:
3617 break;
3619 case NOTE_INSN_EPILOGUE_BEG:
3620 case NOTE_INSN_SWITCH_TEXT_SECTIONS:
3621 emit_note_copy (insn);
3622 break;
3624 default:
3625 /* All other notes should have already been eliminated. */
3626 gcc_unreachable ();
3628 break;
3629 default:
3630 gcc_unreachable ();
3633 insn = NEXT_INSN (last);
3634 delete_insn (last);
3635 return insn;
3638 /* Create a duplicate of the basic block BB. */
3640 static basic_block
3641 cfg_layout_duplicate_bb (basic_block bb)
3643 rtx insn;
3644 basic_block new_bb;
3646 insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
3647 new_bb = create_basic_block (insn,
3648 insn ? get_last_insn () : NULL,
3649 EXIT_BLOCK_PTR->prev_bb);
3651 BB_COPY_PARTITION (new_bb, bb);
3652 if (BB_HEADER (bb))
3654 insn = BB_HEADER (bb);
3655 while (NEXT_INSN (insn))
3656 insn = NEXT_INSN (insn);
3657 insn = duplicate_insn_chain (BB_HEADER (bb), insn);
3658 if (insn)
3659 BB_HEADER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
3662 if (BB_FOOTER (bb))
3664 insn = BB_FOOTER (bb);
3665 while (NEXT_INSN (insn))
3666 insn = NEXT_INSN (insn);
3667 insn = duplicate_insn_chain (BB_FOOTER (bb), insn);
3668 if (insn)
3669 BB_FOOTER (new_bb) = unlink_insn_chain (insn, get_last_insn ());
3672 return new_bb;
3676 /* Main entry point to this module - initialize the datastructures for
3677 CFG layout changes. It keeps LOOPS up-to-date if not null.
3679 FLAGS is a set of additional flags to pass to cleanup_cfg(). */
3681 void
3682 cfg_layout_initialize (unsigned int flags)
3684 rtx x;
3685 basic_block bb;
3687 initialize_original_copy_tables ();
3689 cfg_layout_rtl_register_cfg_hooks ();
3691 record_effective_endpoints ();
3693 /* Make sure that the targets of non local gotos are marked. */
3694 for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
3696 bb = BLOCK_FOR_INSN (XEXP (x, 0));
3697 bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
3700 cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
3703 /* Splits superblocks. */
3704 void
3705 break_superblocks (void)
3707 sbitmap superblocks;
3708 bool need = false;
3709 basic_block bb;
3711 superblocks = sbitmap_alloc (last_basic_block);
3712 sbitmap_zero (superblocks);
3714 FOR_EACH_BB (bb)
3715 if (bb->flags & BB_SUPERBLOCK)
3717 bb->flags &= ~BB_SUPERBLOCK;
3718 SET_BIT (superblocks, bb->index);
3719 need = true;
3722 if (need)
3724 rebuild_jump_labels (get_insns ());
3725 find_many_sub_basic_blocks (superblocks);
3728 free (superblocks);
3731 /* Finalize the changes: reorder insn list according to the sequence specified
3732 by aux pointers, enter compensation code, rebuild scope forest. */
3734 void
3735 cfg_layout_finalize (void)
3737 #ifdef ENABLE_CHECKING
3738 verify_flow_info ();
3739 #endif
3740 force_one_exit_fallthru ();
3741 rtl_register_cfg_hooks ();
3742 if (reload_completed
3743 #ifdef HAVE_epilogue
3744 && !HAVE_epilogue
3745 #endif
3747 fixup_fallthru_exit_predecessor ();
3748 fixup_reorder_chain ();
3750 rebuild_jump_labels (get_insns ());
3751 delete_dead_jumptables ();
3753 #ifdef ENABLE_CHECKING
3754 verify_insn_chain ();
3755 verify_flow_info ();
3756 #endif
3760 /* Same as split_block but update cfg_layout structures. */
3762 static basic_block
3763 cfg_layout_split_block (basic_block bb, void *insnp)
3765 rtx insn = (rtx) insnp;
3766 basic_block new_bb = rtl_split_block (bb, insn);
3768 BB_FOOTER (new_bb) = BB_FOOTER (bb);
3769 BB_FOOTER (bb) = NULL;
3771 return new_bb;
3774 /* Redirect Edge to DEST. */
3775 static edge
3776 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
3778 basic_block src = e->src;
3779 edge ret;
3781 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
3782 return NULL;
3784 if (e->dest == dest)
3785 return e;
3787 if (e->src != ENTRY_BLOCK_PTR
3788 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
3790 df_set_bb_dirty (src);
3791 return ret;
3794 if (e->src == ENTRY_BLOCK_PTR
3795 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
3797 if (dump_file)
3798 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
3799 e->src->index, dest->index);
3801 df_set_bb_dirty (e->src);
3802 redirect_edge_succ (e, dest);
3803 return e;
3806 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
3807 in the case the basic block appears to be in sequence. Avoid this
3808 transformation. */
3810 if (e->flags & EDGE_FALLTHRU)
3812 /* Redirect any branch edges unified with the fallthru one. */
3813 if (JUMP_P (BB_END (src))
3814 && label_is_jump_target_p (BB_HEAD (e->dest),
3815 BB_END (src)))
3817 edge redirected;
3819 if (dump_file)
3820 fprintf (dump_file, "Fallthru edge unified with branch "
3821 "%i->%i redirected to %i\n",
3822 e->src->index, e->dest->index, dest->index);
3823 e->flags &= ~EDGE_FALLTHRU;
3824 redirected = redirect_branch_edge (e, dest);
3825 gcc_assert (redirected);
3826 redirected->flags |= EDGE_FALLTHRU;
3827 df_set_bb_dirty (redirected->src);
3828 return redirected;
3830 /* In case we are redirecting fallthru edge to the branch edge
3831 of conditional jump, remove it. */
3832 if (EDGE_COUNT (src->succs) == 2)
3834 /* Find the edge that is different from E. */
3835 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
3837 if (s->dest == dest
3838 && any_condjump_p (BB_END (src))
3839 && onlyjump_p (BB_END (src)))
3840 delete_insn (BB_END (src));
3842 if (dump_file)
3843 fprintf (dump_file, "Redirecting fallthru edge %i->%i to %i\n",
3844 e->src->index, e->dest->index, dest->index);
3845 ret = redirect_edge_succ_nodup (e, dest);
3847 else
3848 ret = redirect_branch_edge (e, dest);
3850 /* We don't want simplejumps in the insn stream during cfglayout. */
3851 gcc_assert (!simplejump_p (BB_END (src)));
3853 df_set_bb_dirty (src);
3854 return ret;
3857 /* Simple wrapper as we always can redirect fallthru edges. */
3858 static basic_block
3859 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
3861 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
3863 gcc_assert (redirected);
3864 return NULL;
3867 /* Same as delete_basic_block but update cfg_layout structures. */
3869 static void
3870 cfg_layout_delete_block (basic_block bb)
3872 rtx insn, next, prev = PREV_INSN (BB_HEAD (bb)), *to, remaints;
3874 if (BB_HEADER (bb))
3876 next = BB_HEAD (bb);
3877 if (prev)
3878 NEXT_INSN (prev) = BB_HEADER (bb);
3879 else
3880 set_first_insn (BB_HEADER (bb));
3881 PREV_INSN (BB_HEADER (bb)) = prev;
3882 insn = BB_HEADER (bb);
3883 while (NEXT_INSN (insn))
3884 insn = NEXT_INSN (insn);
3885 NEXT_INSN (insn) = next;
3886 PREV_INSN (next) = insn;
3888 next = NEXT_INSN (BB_END (bb));
3889 if (BB_FOOTER (bb))
3891 insn = BB_FOOTER (bb);
3892 while (insn)
3894 if (BARRIER_P (insn))
3896 if (PREV_INSN (insn))
3897 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
3898 else
3899 BB_FOOTER (bb) = NEXT_INSN (insn);
3900 if (NEXT_INSN (insn))
3901 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
3903 if (LABEL_P (insn))
3904 break;
3905 insn = NEXT_INSN (insn);
3907 if (BB_FOOTER (bb))
3909 insn = BB_END (bb);
3910 NEXT_INSN (insn) = BB_FOOTER (bb);
3911 PREV_INSN (BB_FOOTER (bb)) = insn;
3912 while (NEXT_INSN (insn))
3913 insn = NEXT_INSN (insn);
3914 NEXT_INSN (insn) = next;
3915 if (next)
3916 PREV_INSN (next) = insn;
3917 else
3918 set_last_insn (insn);
3921 if (bb->next_bb != EXIT_BLOCK_PTR)
3922 to = &BB_HEADER (bb->next_bb);
3923 else
3924 to = &cfg_layout_function_footer;
3926 rtl_delete_block (bb);
3928 if (prev)
3929 prev = NEXT_INSN (prev);
3930 else
3931 prev = get_insns ();
3932 if (next)
3933 next = PREV_INSN (next);
3934 else
3935 next = get_last_insn ();
3937 if (next && NEXT_INSN (next) != prev)
3939 remaints = unlink_insn_chain (prev, next);
3940 insn = remaints;
3941 while (NEXT_INSN (insn))
3942 insn = NEXT_INSN (insn);
3943 NEXT_INSN (insn) = *to;
3944 if (*to)
3945 PREV_INSN (*to) = insn;
3946 *to = remaints;
3950 /* Return true when blocks A and B can be safely merged. */
3952 static bool
3953 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
3955 /* If we are partitioning hot/cold basic blocks, we don't want to
3956 mess up unconditional or indirect jumps that cross between hot
3957 and cold sections.
3959 Basic block partitioning may result in some jumps that appear to
3960 be optimizable (or blocks that appear to be mergeable), but which really
3961 must be left untouched (they are required to make it safely across
3962 partition boundaries). See the comments at the top of
3963 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
3965 if (BB_PARTITION (a) != BB_PARTITION (b))
3966 return false;
3968 /* Protect the loop latches. */
3969 if (current_loops && b->loop_father->latch == b)
3970 return false;
3972 /* If we would end up moving B's instructions, make sure it doesn't fall
3973 through into the exit block, since we cannot recover from a fallthrough
3974 edge into the exit block occurring in the middle of a function. */
3975 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
3977 edge e = find_fallthru_edge (b->succs);
3978 if (e && e->dest == EXIT_BLOCK_PTR)
3979 return false;
3982 /* There must be exactly one edge in between the blocks. */
3983 return (single_succ_p (a)
3984 && single_succ (a) == b
3985 && single_pred_p (b) == 1
3986 && a != b
3987 /* Must be simple edge. */
3988 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
3989 && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
3990 /* If the jump insn has side effects, we can't kill the edge.
3991 When not optimizing, try_redirect_by_replacing_jump will
3992 not allow us to redirect an edge by replacing a table jump. */
3993 && (!JUMP_P (BB_END (a))
3994 || ((!optimize || reload_completed)
3995 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
3998 /* Merge block A and B. The blocks must be mergeable. */
4000 static void
4001 cfg_layout_merge_blocks (basic_block a, basic_block b)
4003 bool forwarder_p = (b->flags & BB_FORWARDER_BLOCK) != 0;
4004 rtx insn;
4006 gcc_checking_assert (cfg_layout_can_merge_blocks_p (a, b));
4008 if (dump_file)
4009 fprintf (dump_file, "Merging block %d into block %d...\n", b->index,
4010 a->index);
4012 /* If there was a CODE_LABEL beginning B, delete it. */
4013 if (LABEL_P (BB_HEAD (b)))
4015 delete_insn (BB_HEAD (b));
4018 /* We should have fallthru edge in a, or we can do dummy redirection to get
4019 it cleaned up. */
4020 if (JUMP_P (BB_END (a)))
4021 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
4022 gcc_assert (!JUMP_P (BB_END (a)));
4024 /* When not optimizing CFG and the edge is the only place in RTL which holds
4025 some unique locus, emit a nop with that locus in between. */
4026 if (!optimize)
4027 emit_nop_for_unique_locus_between (a, b);
4029 /* Possible line number notes should appear in between. */
4030 if (BB_HEADER (b))
4032 rtx first = BB_END (a), last;
4034 last = emit_insn_after_noloc (BB_HEADER (b), BB_END (a), a);
4035 /* The above might add a BARRIER as BB_END, but as barriers
4036 aren't valid parts of a bb, remove_insn doesn't update
4037 BB_END if it is a barrier. So adjust BB_END here. */
4038 while (BB_END (a) != first && BARRIER_P (BB_END (a)))
4039 BB_END (a) = PREV_INSN (BB_END (a));
4040 delete_insn_chain (NEXT_INSN (first), last, false);
4041 BB_HEADER (b) = NULL;
4044 /* In the case basic blocks are not adjacent, move them around. */
4045 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
4047 insn = unlink_insn_chain (BB_HEAD (b), BB_END (b));
4049 emit_insn_after_noloc (insn, BB_END (a), a);
4051 /* Otherwise just re-associate the instructions. */
4052 else
4054 insn = BB_HEAD (b);
4055 BB_END (a) = BB_END (b);
4058 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
4059 We need to explicitly call. */
4060 update_bb_for_insn_chain (insn, BB_END (b), a);
4062 /* Skip possible DELETED_LABEL insn. */
4063 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
4064 insn = NEXT_INSN (insn);
4065 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
4066 BB_HEAD (b) = NULL;
4067 delete_insn (insn);
4069 df_bb_delete (b->index);
4071 /* Possible tablejumps and barriers should appear after the block. */
4072 if (BB_FOOTER (b))
4074 if (!BB_FOOTER (a))
4075 BB_FOOTER (a) = BB_FOOTER (b);
4076 else
4078 rtx last = BB_FOOTER (a);
4080 while (NEXT_INSN (last))
4081 last = NEXT_INSN (last);
4082 NEXT_INSN (last) = BB_FOOTER (b);
4083 PREV_INSN (BB_FOOTER (b)) = last;
4085 BB_FOOTER (b) = NULL;
4088 /* If B was a forwarder block, propagate the locus on the edge. */
4089 if (forwarder_p && !EDGE_SUCC (b, 0)->goto_locus)
4090 EDGE_SUCC (b, 0)->goto_locus = EDGE_SUCC (a, 0)->goto_locus;
4092 if (dump_file)
4093 fprintf (dump_file, "Merged blocks %d and %d.\n", a->index, b->index);
4096 /* Split edge E. */
4098 static basic_block
4099 cfg_layout_split_edge (edge e)
4101 basic_block new_bb =
4102 create_basic_block (e->src != ENTRY_BLOCK_PTR
4103 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
4104 NULL_RTX, e->src);
4106 if (e->dest == EXIT_BLOCK_PTR)
4107 BB_COPY_PARTITION (new_bb, e->src);
4108 else
4109 BB_COPY_PARTITION (new_bb, e->dest);
4110 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
4111 redirect_edge_and_branch_force (e, new_bb);
4113 return new_bb;
4116 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
4118 static void
4119 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
4123 /* Return 1 if BB ends with a call, possibly followed by some
4124 instructions that must stay with the call, 0 otherwise. */
4126 static bool
4127 rtl_block_ends_with_call_p (basic_block bb)
4129 rtx insn = BB_END (bb);
4131 while (!CALL_P (insn)
4132 && insn != BB_HEAD (bb)
4133 && (keep_with_call_p (insn)
4134 || NOTE_P (insn)
4135 || DEBUG_INSN_P (insn)))
4136 insn = PREV_INSN (insn);
4137 return (CALL_P (insn));
4140 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
4142 static bool
4143 rtl_block_ends_with_condjump_p (const_basic_block bb)
4145 return any_condjump_p (BB_END (bb));
4148 /* Return true if we need to add fake edge to exit.
4149 Helper function for rtl_flow_call_edges_add. */
4151 static bool
4152 need_fake_edge_p (const_rtx insn)
4154 if (!INSN_P (insn))
4155 return false;
4157 if ((CALL_P (insn)
4158 && !SIBLING_CALL_P (insn)
4159 && !find_reg_note (insn, REG_NORETURN, NULL)
4160 && !(RTL_CONST_OR_PURE_CALL_P (insn))))
4161 return true;
4163 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
4164 && MEM_VOLATILE_P (PATTERN (insn)))
4165 || (GET_CODE (PATTERN (insn)) == PARALLEL
4166 && asm_noperands (insn) != -1
4167 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
4168 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
4171 /* Add fake edges to the function exit for any non constant and non noreturn
4172 calls, volatile inline assembly in the bitmap of blocks specified by
4173 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
4174 that were split.
4176 The goal is to expose cases in which entering a basic block does not imply
4177 that all subsequent instructions must be executed. */
4179 static int
4180 rtl_flow_call_edges_add (sbitmap blocks)
4182 int i;
4183 int blocks_split = 0;
4184 int last_bb = last_basic_block;
4185 bool check_last_block = false;
4187 if (n_basic_blocks == NUM_FIXED_BLOCKS)
4188 return 0;
4190 if (! blocks)
4191 check_last_block = true;
4192 else
4193 check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
4195 /* In the last basic block, before epilogue generation, there will be
4196 a fallthru edge to EXIT. Special care is required if the last insn
4197 of the last basic block is a call because make_edge folds duplicate
4198 edges, which would result in the fallthru edge also being marked
4199 fake, which would result in the fallthru edge being removed by
4200 remove_fake_edges, which would result in an invalid CFG.
4202 Moreover, we can't elide the outgoing fake edge, since the block
4203 profiler needs to take this into account in order to solve the minimal
4204 spanning tree in the case that the call doesn't return.
4206 Handle this by adding a dummy instruction in a new last basic block. */
4207 if (check_last_block)
4209 basic_block bb = EXIT_BLOCK_PTR->prev_bb;
4210 rtx insn = BB_END (bb);
4212 /* Back up past insns that must be kept in the same block as a call. */
4213 while (insn != BB_HEAD (bb)
4214 && keep_with_call_p (insn))
4215 insn = PREV_INSN (insn);
4217 if (need_fake_edge_p (insn))
4219 edge e;
4221 e = find_edge (bb, EXIT_BLOCK_PTR);
4222 if (e)
4224 insert_insn_on_edge (gen_use (const0_rtx), e);
4225 commit_edge_insertions ();
4230 /* Now add fake edges to the function exit for any non constant
4231 calls since there is no way that we can determine if they will
4232 return or not... */
4234 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
4236 basic_block bb = BASIC_BLOCK (i);
4237 rtx insn;
4238 rtx prev_insn;
4240 if (!bb)
4241 continue;
4243 if (blocks && !TEST_BIT (blocks, i))
4244 continue;
4246 for (insn = BB_END (bb); ; insn = prev_insn)
4248 prev_insn = PREV_INSN (insn);
4249 if (need_fake_edge_p (insn))
4251 edge e;
4252 rtx split_at_insn = insn;
4254 /* Don't split the block between a call and an insn that should
4255 remain in the same block as the call. */
4256 if (CALL_P (insn))
4257 while (split_at_insn != BB_END (bb)
4258 && keep_with_call_p (NEXT_INSN (split_at_insn)))
4259 split_at_insn = NEXT_INSN (split_at_insn);
4261 /* The handling above of the final block before the epilogue
4262 should be enough to verify that there is no edge to the exit
4263 block in CFG already. Calling make_edge in such case would
4264 cause us to mark that edge as fake and remove it later. */
4266 #ifdef ENABLE_CHECKING
4267 if (split_at_insn == BB_END (bb))
4269 e = find_edge (bb, EXIT_BLOCK_PTR);
4270 gcc_assert (e == NULL);
4272 #endif
4274 /* Note that the following may create a new basic block
4275 and renumber the existing basic blocks. */
4276 if (split_at_insn != BB_END (bb))
4278 e = split_block (bb, split_at_insn);
4279 if (e)
4280 blocks_split++;
4283 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
4286 if (insn == BB_HEAD (bb))
4287 break;
4291 if (blocks_split)
4292 verify_flow_info ();
4294 return blocks_split;
4297 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
4298 the conditional branch target, SECOND_HEAD should be the fall-thru
4299 there is no need to handle this here the loop versioning code handles
4300 this. the reason for SECON_HEAD is that it is needed for condition
4301 in trees, and this should be of the same type since it is a hook. */
4302 static void
4303 rtl_lv_add_condition_to_bb (basic_block first_head ,
4304 basic_block second_head ATTRIBUTE_UNUSED,
4305 basic_block cond_bb, void *comp_rtx)
4307 rtx label, seq, jump;
4308 rtx op0 = XEXP ((rtx)comp_rtx, 0);
4309 rtx op1 = XEXP ((rtx)comp_rtx, 1);
4310 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
4311 enum machine_mode mode;
4314 label = block_label (first_head);
4315 mode = GET_MODE (op0);
4316 if (mode == VOIDmode)
4317 mode = GET_MODE (op1);
4319 start_sequence ();
4320 op0 = force_operand (op0, NULL_RTX);
4321 op1 = force_operand (op1, NULL_RTX);
4322 do_compare_rtx_and_jump (op0, op1, comp, 0,
4323 mode, NULL_RTX, NULL_RTX, label, -1);
4324 jump = get_last_insn ();
4325 JUMP_LABEL (jump) = label;
4326 LABEL_NUSES (label)++;
4327 seq = get_insns ();
4328 end_sequence ();
4330 /* Add the new cond , in the new head. */
4331 emit_insn_after(seq, BB_END(cond_bb));
4335 /* Given a block B with unconditional branch at its end, get the
4336 store the return the branch edge and the fall-thru edge in
4337 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
4338 static void
4339 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
4340 edge *fallthru_edge)
4342 edge e = EDGE_SUCC (b, 0);
4344 if (e->flags & EDGE_FALLTHRU)
4346 *fallthru_edge = e;
4347 *branch_edge = EDGE_SUCC (b, 1);
4349 else
4351 *branch_edge = e;
4352 *fallthru_edge = EDGE_SUCC (b, 1);
4356 void
4357 init_rtl_bb_info (basic_block bb)
4359 gcc_assert (!bb->il.x.rtl);
4360 bb->il.x.head_ = NULL;
4361 bb->il.x.rtl = ggc_alloc_cleared_rtl_bb_info ();
4364 /* Returns true if it is possible to remove edge E by redirecting
4365 it to the destination of the other edge from E->src. */
4367 static bool
4368 rtl_can_remove_branch_p (const_edge e)
4370 const_basic_block src = e->src;
4371 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
4372 const_rtx insn = BB_END (src), set;
4374 /* The conditions are taken from try_redirect_by_replacing_jump. */
4375 if (target == EXIT_BLOCK_PTR)
4376 return false;
4378 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
4379 return false;
4381 if (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX)
4382 || BB_PARTITION (src) != BB_PARTITION (target))
4383 return false;
4385 if (!onlyjump_p (insn)
4386 || tablejump_p (insn, NULL, NULL))
4387 return false;
4389 set = single_set (insn);
4390 if (!set || side_effects_p (set))
4391 return false;
4393 return true;
4396 static basic_block
4397 rtl_duplicate_bb (basic_block bb)
4399 bb = cfg_layout_duplicate_bb (bb);
4400 bb->aux = NULL;
4401 return bb;
4404 /* Implementation of CFG manipulation for linearized RTL. */
4405 struct cfg_hooks rtl_cfg_hooks = {
4406 "rtl",
4407 rtl_verify_flow_info,
4408 rtl_dump_bb,
4409 rtl_create_basic_block,
4410 rtl_redirect_edge_and_branch,
4411 rtl_redirect_edge_and_branch_force,
4412 rtl_can_remove_branch_p,
4413 rtl_delete_block,
4414 rtl_split_block,
4415 rtl_move_block_after,
4416 rtl_can_merge_blocks, /* can_merge_blocks_p */
4417 rtl_merge_blocks,
4418 rtl_predict_edge,
4419 rtl_predicted_by_p,
4420 cfg_layout_can_duplicate_bb_p,
4421 rtl_duplicate_bb,
4422 rtl_split_edge,
4423 rtl_make_forwarder_block,
4424 rtl_tidy_fallthru_edge,
4425 rtl_force_nonfallthru,
4426 rtl_block_ends_with_call_p,
4427 rtl_block_ends_with_condjump_p,
4428 rtl_flow_call_edges_add,
4429 NULL, /* execute_on_growing_pred */
4430 NULL, /* execute_on_shrinking_pred */
4431 NULL, /* duplicate loop for trees */
4432 NULL, /* lv_add_condition_to_bb */
4433 NULL, /* lv_adjust_loop_header_phi*/
4434 NULL, /* extract_cond_bb_edges */
4435 NULL /* flush_pending_stmts */
4438 /* Implementation of CFG manipulation for cfg layout RTL, where
4439 basic block connected via fallthru edges does not have to be adjacent.
4440 This representation will hopefully become the default one in future
4441 version of the compiler. */
4443 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
4444 "cfglayout mode",
4445 rtl_verify_flow_info_1,
4446 rtl_dump_bb,
4447 cfg_layout_create_basic_block,
4448 cfg_layout_redirect_edge_and_branch,
4449 cfg_layout_redirect_edge_and_branch_force,
4450 rtl_can_remove_branch_p,
4451 cfg_layout_delete_block,
4452 cfg_layout_split_block,
4453 rtl_move_block_after,
4454 cfg_layout_can_merge_blocks_p,
4455 cfg_layout_merge_blocks,
4456 rtl_predict_edge,
4457 rtl_predicted_by_p,
4458 cfg_layout_can_duplicate_bb_p,
4459 cfg_layout_duplicate_bb,
4460 cfg_layout_split_edge,
4461 rtl_make_forwarder_block,
4462 NULL, /* tidy_fallthru_edge */
4463 rtl_force_nonfallthru,
4464 rtl_block_ends_with_call_p,
4465 rtl_block_ends_with_condjump_p,
4466 rtl_flow_call_edges_add,
4467 NULL, /* execute_on_growing_pred */
4468 NULL, /* execute_on_shrinking_pred */
4469 duplicate_loop_to_header_edge, /* duplicate loop for trees */
4470 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
4471 NULL, /* lv_adjust_loop_header_phi*/
4472 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
4473 NULL /* flush_pending_stmts */
4476 #include "gt-cfgrtl.h"