Daily bump.
[official-gcc.git] / gcc / cfgrtl.c
bloba42063b6c4cbb19d51c63e1a58bbbc9044e5c8e1
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
4 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
34 Functions not supposed for generic use:
35 - Infrastructure to determine quickly basic block for insn
36 compute_bb_for_insn, update_bb_for_insn, set_block_for_insn,
37 - Edge redirection with updating and optimizing of insn chain
38 block_label, tidy_fallthru_edge, force_nonfallthru */
40 #include "config.h"
41 #include "system.h"
42 #include "coretypes.h"
43 #include "tm.h"
44 #include "tree.h"
45 #include "rtl.h"
46 #include "hard-reg-set.h"
47 #include "basic-block.h"
48 #include "regs.h"
49 #include "flags.h"
50 #include "output.h"
51 #include "function.h"
52 #include "except.h"
53 #include "toplev.h"
54 #include "tm_p.h"
55 #include "obstack.h"
56 #include "insn-config.h"
57 #include "cfglayout.h"
58 #include "expr.h"
59 #include "target.h"
60 #include "cfgloop.h"
61 #include "ggc.h"
62 #include "tree-pass.h"
63 #include "df.h"
65 static int can_delete_note_p (const_rtx);
66 static int can_delete_label_p (const_rtx);
67 static void commit_one_edge_insertion (edge);
68 static basic_block rtl_split_edge (edge);
69 static bool rtl_move_block_after (basic_block, basic_block);
70 static int rtl_verify_flow_info (void);
71 static basic_block cfg_layout_split_block (basic_block, void *);
72 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
73 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
74 static void cfg_layout_delete_block (basic_block);
75 static void rtl_delete_block (basic_block);
76 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
77 static edge rtl_redirect_edge_and_branch (edge, basic_block);
78 static basic_block rtl_split_block (basic_block, void *);
79 static void rtl_dump_bb (basic_block, FILE *, int);
80 static int rtl_verify_flow_info_1 (void);
81 static void rtl_make_forwarder_block (edge);
83 /* Return true if NOTE is not one of the ones that must be kept paired,
84 so that we may simply delete it. */
86 static int
87 can_delete_note_p (const_rtx note)
89 return (NOTE_KIND (note) == NOTE_INSN_DELETED
90 || NOTE_KIND (note) == NOTE_INSN_BASIC_BLOCK);
93 /* True if a given label can be deleted. */
95 static int
96 can_delete_label_p (const_rtx label)
98 return (!LABEL_PRESERVE_P (label)
99 /* User declared labels must be preserved. */
100 && LABEL_NAME (label) == 0
101 && !in_expr_list_p (forced_labels, label));
104 /* Delete INSN by patching it out. Return the next insn. */
107 delete_insn (rtx insn)
109 rtx next = NEXT_INSN (insn);
110 rtx note;
111 bool really_delete = true;
113 if (LABEL_P (insn))
115 /* Some labels can't be directly removed from the INSN chain, as they
116 might be references via variables, constant pool etc.
117 Convert them to the special NOTE_INSN_DELETED_LABEL note. */
118 if (! can_delete_label_p (insn))
120 const char *name = LABEL_NAME (insn);
122 really_delete = false;
123 PUT_CODE (insn, NOTE);
124 NOTE_KIND (insn) = NOTE_INSN_DELETED_LABEL;
125 NOTE_DELETED_LABEL_NAME (insn) = name;
128 remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
131 if (really_delete)
133 /* If this insn has already been deleted, something is very wrong. */
134 gcc_assert (!INSN_DELETED_P (insn));
135 remove_insn (insn);
136 INSN_DELETED_P (insn) = 1;
139 /* If deleting a jump, decrement the use count of the label. Deleting
140 the label itself should happen in the normal course of block merging. */
141 if (JUMP_P (insn))
143 if (JUMP_LABEL (insn)
144 && LABEL_P (JUMP_LABEL (insn)))
145 LABEL_NUSES (JUMP_LABEL (insn))--;
147 /* If there are more targets, remove them too. */
148 while ((note
149 = find_reg_note (insn, REG_LABEL_TARGET, NULL_RTX)) != NULL_RTX
150 && LABEL_P (XEXP (note, 0)))
152 LABEL_NUSES (XEXP (note, 0))--;
153 remove_note (insn, note);
157 /* Also if deleting any insn that references a label as an operand. */
158 while ((note = find_reg_note (insn, REG_LABEL_OPERAND, NULL_RTX)) != NULL_RTX
159 && LABEL_P (XEXP (note, 0)))
161 LABEL_NUSES (XEXP (note, 0))--;
162 remove_note (insn, note);
165 if (JUMP_P (insn)
166 && (GET_CODE (PATTERN (insn)) == ADDR_VEC
167 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
169 rtx pat = PATTERN (insn);
170 int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
171 int len = XVECLEN (pat, diff_vec_p);
172 int i;
174 for (i = 0; i < len; i++)
176 rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
178 /* When deleting code in bulk (e.g. removing many unreachable
179 blocks) we can delete a label that's a target of the vector
180 before deleting the vector itself. */
181 if (!NOTE_P (label))
182 LABEL_NUSES (label)--;
186 return next;
189 /* Like delete_insn but also purge dead edges from BB. */
192 delete_insn_and_edges (rtx insn)
194 rtx x;
195 bool purge = false;
197 if (INSN_P (insn)
198 && BLOCK_FOR_INSN (insn)
199 && BB_END (BLOCK_FOR_INSN (insn)) == insn)
200 purge = true;
201 x = delete_insn (insn);
202 if (purge)
203 purge_dead_edges (BLOCK_FOR_INSN (insn));
204 return x;
207 /* Unlink a chain of insns between START and FINISH, leaving notes
208 that must be paired. If CLEAR_BB is true, we set bb field for
209 insns that cannot be removed to NULL. */
211 void
212 delete_insn_chain (rtx start, rtx finish, bool clear_bb)
214 rtx next;
216 /* Unchain the insns one by one. It would be quicker to delete all of these
217 with a single unchaining, rather than one at a time, but we need to keep
218 the NOTE's. */
219 while (1)
221 next = NEXT_INSN (start);
222 if (NOTE_P (start) && !can_delete_note_p (start))
224 else
225 next = delete_insn (start);
227 if (clear_bb && !INSN_DELETED_P (start))
228 set_block_for_insn (start, NULL);
230 if (start == finish)
231 break;
232 start = next;
236 /* Like delete_insn_chain but also purge dead edges from BB. */
238 void
239 delete_insn_chain_and_edges (rtx first, rtx last)
241 bool purge = false;
243 if (INSN_P (last)
244 && BLOCK_FOR_INSN (last)
245 && BB_END (BLOCK_FOR_INSN (last)) == last)
246 purge = true;
247 delete_insn_chain (first, last, false);
248 if (purge)
249 purge_dead_edges (BLOCK_FOR_INSN (last));
252 /* Create a new basic block consisting of the instructions between HEAD and END
253 inclusive. This function is designed to allow fast BB construction - reuses
254 the note and basic block struct in BB_NOTE, if any and do not grow
255 BASIC_BLOCK chain and should be used directly only by CFG construction code.
256 END can be NULL in to create new empty basic block before HEAD. Both END
257 and HEAD can be NULL to create basic block at the end of INSN chain.
258 AFTER is the basic block we should be put after. */
260 basic_block
261 create_basic_block_structure (rtx head, rtx end, rtx bb_note, basic_block after)
263 basic_block bb;
265 if (bb_note
266 && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
267 && bb->aux == NULL)
269 /* If we found an existing note, thread it back onto the chain. */
271 rtx after;
273 if (LABEL_P (head))
274 after = head;
275 else
277 after = PREV_INSN (head);
278 head = bb_note;
281 if (after != bb_note && NEXT_INSN (after) != bb_note)
282 reorder_insns_nobb (bb_note, bb_note, after);
284 else
286 /* Otherwise we must create a note and a basic block structure. */
288 bb = alloc_block ();
290 init_rtl_bb_info (bb);
291 if (!head && !end)
292 head = end = bb_note
293 = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
294 else if (LABEL_P (head) && end)
296 bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
297 if (head == end)
298 end = bb_note;
300 else
302 bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
303 head = bb_note;
304 if (!end)
305 end = head;
308 NOTE_BASIC_BLOCK (bb_note) = bb;
311 /* Always include the bb note in the block. */
312 if (NEXT_INSN (end) == bb_note)
313 end = bb_note;
315 BB_HEAD (bb) = head;
316 BB_END (bb) = end;
317 bb->index = last_basic_block++;
318 bb->flags = BB_NEW | BB_RTL;
319 link_block (bb, after);
320 SET_BASIC_BLOCK (bb->index, bb);
321 df_bb_refs_record (bb->index, false);
322 update_bb_for_insn (bb);
323 BB_SET_PARTITION (bb, BB_UNPARTITIONED);
325 /* Tag the block so that we know it has been used when considering
326 other basic block notes. */
327 bb->aux = bb;
329 return bb;
332 /* Create new basic block consisting of instructions in between HEAD and END
333 and place it to the BB chain after block AFTER. END can be NULL in to
334 create new empty basic block before HEAD. Both END and HEAD can be NULL to
335 create basic block at the end of INSN chain. */
337 static basic_block
338 rtl_create_basic_block (void *headp, void *endp, basic_block after)
340 rtx head = (rtx) headp, end = (rtx) endp;
341 basic_block bb;
343 /* Grow the basic block array if needed. */
344 if ((size_t) last_basic_block >= VEC_length (basic_block, basic_block_info))
346 size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
347 VEC_safe_grow_cleared (basic_block, gc, basic_block_info, new_size);
350 n_basic_blocks++;
352 bb = create_basic_block_structure (head, end, NULL, after);
353 bb->aux = NULL;
354 return bb;
357 static basic_block
358 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
360 basic_block newbb = rtl_create_basic_block (head, end, after);
362 return newbb;
365 /* Delete the insns in a (non-live) block. We physically delete every
366 non-deleted-note insn, and update the flow graph appropriately.
368 Return nonzero if we deleted an exception handler. */
370 /* ??? Preserving all such notes strikes me as wrong. It would be nice
371 to post-process the stream to remove empty blocks, loops, ranges, etc. */
373 static void
374 rtl_delete_block (basic_block b)
376 rtx insn, end;
378 /* If the head of this block is a CODE_LABEL, then it might be the
379 label for an exception handler which can't be reached. We need
380 to remove the label from the exception_handler_label list. */
381 insn = BB_HEAD (b);
382 if (LABEL_P (insn))
383 maybe_remove_eh_handler (insn);
385 end = get_last_bb_insn (b);
387 /* Selectively delete the entire chain. */
388 BB_HEAD (b) = NULL;
389 delete_insn_chain (insn, end, true);
392 if (dump_file)
393 fprintf (dump_file, "deleting block %d\n", b->index);
394 df_bb_delete (b->index);
397 /* Records the basic block struct in BLOCK_FOR_INSN for every insn. */
399 void
400 compute_bb_for_insn (void)
402 basic_block bb;
404 FOR_EACH_BB (bb)
406 rtx end = BB_END (bb);
407 rtx insn;
409 for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
411 BLOCK_FOR_INSN (insn) = bb;
412 if (insn == end)
413 break;
418 /* Release the basic_block_for_insn array. */
420 unsigned int
421 free_bb_for_insn (void)
423 rtx insn;
424 for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
425 if (!BARRIER_P (insn))
426 BLOCK_FOR_INSN (insn) = NULL;
427 return 0;
430 struct rtl_opt_pass pass_free_cfg =
433 RTL_PASS,
434 NULL, /* name */
435 NULL, /* gate */
436 free_bb_for_insn, /* execute */
437 NULL, /* sub */
438 NULL, /* next */
439 0, /* static_pass_number */
440 0, /* tv_id */
441 0, /* properties_required */
442 0, /* properties_provided */
443 PROP_cfg, /* properties_destroyed */
444 0, /* todo_flags_start */
445 0, /* todo_flags_finish */
449 /* Return RTX to emit after when we want to emit code on the entry of function. */
451 entry_of_function (void)
453 return (n_basic_blocks > NUM_FIXED_BLOCKS ?
454 BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ());
457 /* Emit INSN at the entry point of the function, ensuring that it is only
458 executed once per function. */
459 void
460 emit_insn_at_entry (rtx insn)
462 edge_iterator ei = ei_start (ENTRY_BLOCK_PTR->succs);
463 edge e = ei_safe_edge (ei);
464 gcc_assert (e->flags & EDGE_FALLTHRU);
466 insert_insn_on_edge (insn, e);
467 commit_edge_insertions ();
470 /* Update BLOCK_FOR_INSN of insns between BEGIN and END
471 (or BARRIER if found) and notify df of the bb change.
472 The insn chain range is inclusive
473 (i.e. both BEGIN and END will be updated. */
475 static void
476 update_bb_for_insn_chain (rtx begin, rtx end, basic_block bb)
478 rtx insn;
480 end = NEXT_INSN (end);
481 for (insn = begin; insn != end; insn = NEXT_INSN (insn))
482 if (!BARRIER_P (insn))
483 df_insn_change_bb (insn, bb);
486 /* Update BLOCK_FOR_INSN of insns in BB to BB,
487 and notify df of the change. */
489 void
490 update_bb_for_insn (basic_block bb)
492 update_bb_for_insn_chain (BB_HEAD (bb), BB_END (bb), bb);
496 /* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
497 note associated with the BLOCK. */
499 static rtx
500 first_insn_after_basic_block_note (basic_block block)
502 rtx insn;
504 /* Get the first instruction in the block. */
505 insn = BB_HEAD (block);
507 if (insn == NULL_RTX)
508 return NULL_RTX;
509 if (LABEL_P (insn))
510 insn = NEXT_INSN (insn);
511 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
513 return NEXT_INSN (insn);
516 /* Creates a new basic block just after basic block B by splitting
517 everything after specified instruction I. */
519 static basic_block
520 rtl_split_block (basic_block bb, void *insnp)
522 basic_block new_bb;
523 rtx insn = (rtx) insnp;
524 edge e;
525 edge_iterator ei;
527 if (!insn)
529 insn = first_insn_after_basic_block_note (bb);
531 if (insn)
532 insn = PREV_INSN (insn);
533 else
534 insn = get_last_insn ();
537 /* We probably should check type of the insn so that we do not create
538 inconsistent cfg. It is checked in verify_flow_info anyway, so do not
539 bother. */
540 if (insn == BB_END (bb))
541 emit_note_after (NOTE_INSN_DELETED, insn);
543 /* Create the new basic block. */
544 new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
545 BB_COPY_PARTITION (new_bb, bb);
546 BB_END (bb) = insn;
548 /* Redirect the outgoing edges. */
549 new_bb->succs = bb->succs;
550 bb->succs = NULL;
551 FOR_EACH_EDGE (e, ei, new_bb->succs)
552 e->src = new_bb;
554 /* The new block starts off being dirty. */
555 df_set_bb_dirty (bb);
556 return new_bb;
559 /* Blocks A and B are to be merged into a single block A. The insns
560 are already contiguous. */
562 static void
563 rtl_merge_blocks (basic_block a, basic_block b)
565 rtx b_head = BB_HEAD (b), b_end = BB_END (b), a_end = BB_END (a);
566 rtx del_first = NULL_RTX, del_last = NULL_RTX;
567 int b_empty = 0;
569 if (dump_file)
570 fprintf (dump_file, "merging block %d into block %d\n", b->index, a->index);
572 /* If there was a CODE_LABEL beginning B, delete it. */
573 if (LABEL_P (b_head))
575 /* This might have been an EH label that no longer has incoming
576 EH edges. Update data structures to match. */
577 maybe_remove_eh_handler (b_head);
579 /* Detect basic blocks with nothing but a label. This can happen
580 in particular at the end of a function. */
581 if (b_head == b_end)
582 b_empty = 1;
584 del_first = del_last = b_head;
585 b_head = NEXT_INSN (b_head);
588 /* Delete the basic block note and handle blocks containing just that
589 note. */
590 if (NOTE_INSN_BASIC_BLOCK_P (b_head))
592 if (b_head == b_end)
593 b_empty = 1;
594 if (! del_last)
595 del_first = b_head;
597 del_last = b_head;
598 b_head = NEXT_INSN (b_head);
601 /* If there was a jump out of A, delete it. */
602 if (JUMP_P (a_end))
604 rtx prev;
606 for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
607 if (!NOTE_P (prev)
608 || NOTE_INSN_BASIC_BLOCK_P (prev)
609 || prev == BB_HEAD (a))
610 break;
612 del_first = a_end;
614 #ifdef HAVE_cc0
615 /* If this was a conditional jump, we need to also delete
616 the insn that set cc0. */
617 if (only_sets_cc0_p (prev))
619 rtx tmp = prev;
621 prev = prev_nonnote_insn (prev);
622 if (!prev)
623 prev = BB_HEAD (a);
624 del_first = tmp;
626 #endif
628 a_end = PREV_INSN (del_first);
630 else if (BARRIER_P (NEXT_INSN (a_end)))
631 del_first = NEXT_INSN (a_end);
633 /* Delete everything marked above as well as crap that might be
634 hanging out between the two blocks. */
635 BB_HEAD (b) = NULL;
636 delete_insn_chain (del_first, del_last, true);
638 /* Reassociate the insns of B with A. */
639 if (!b_empty)
641 update_bb_for_insn_chain (a_end, b_end, a);
643 a_end = b_end;
646 df_bb_delete (b->index);
647 BB_END (a) = a_end;
651 /* Return true when block A and B can be merged. */
653 static bool
654 rtl_can_merge_blocks (basic_block a, basic_block b)
656 /* If we are partitioning hot/cold basic blocks, we don't want to
657 mess up unconditional or indirect jumps that cross between hot
658 and cold sections.
660 Basic block partitioning may result in some jumps that appear to
661 be optimizable (or blocks that appear to be mergeable), but which really
662 must be left untouched (they are required to make it safely across
663 partition boundaries). See the comments at the top of
664 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
666 if (BB_PARTITION (a) != BB_PARTITION (b))
667 return false;
669 /* There must be exactly one edge in between the blocks. */
670 return (single_succ_p (a)
671 && single_succ (a) == b
672 && single_pred_p (b)
673 && a != b
674 /* Must be simple edge. */
675 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
676 && a->next_bb == b
677 && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
678 /* If the jump insn has side effects,
679 we can't kill the edge. */
680 && (!JUMP_P (BB_END (a))
681 || (reload_completed
682 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
685 /* Return the label in the head of basic block BLOCK. Create one if it doesn't
686 exist. */
689 block_label (basic_block block)
691 if (block == EXIT_BLOCK_PTR)
692 return NULL_RTX;
694 if (!LABEL_P (BB_HEAD (block)))
696 BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
699 return BB_HEAD (block);
702 /* Attempt to perform edge redirection by replacing possibly complex jump
703 instruction by unconditional jump or removing jump completely. This can
704 apply only if all edges now point to the same block. The parameters and
705 return values are equivalent to redirect_edge_and_branch. */
707 edge
708 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
710 basic_block src = e->src;
711 rtx insn = BB_END (src), kill_from;
712 rtx set;
713 int fallthru = 0;
715 /* If we are partitioning hot/cold basic blocks, we don't want to
716 mess up unconditional or indirect jumps that cross between hot
717 and cold sections.
719 Basic block partitioning may result in some jumps that appear to
720 be optimizable (or blocks that appear to be mergeable), but which really
721 must be left untouched (they are required to make it safely across
722 partition boundaries). See the comments at the top of
723 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
725 if (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX)
726 || BB_PARTITION (src) != BB_PARTITION (target))
727 return NULL;
729 /* We can replace or remove a complex jump only when we have exactly
730 two edges. Also, if we have exactly one outgoing edge, we can
731 redirect that. */
732 if (EDGE_COUNT (src->succs) >= 3
733 /* Verify that all targets will be TARGET. Specifically, the
734 edge that is not E must also go to TARGET. */
735 || (EDGE_COUNT (src->succs) == 2
736 && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
737 return NULL;
739 if (!onlyjump_p (insn))
740 return NULL;
741 if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
742 return NULL;
744 /* Avoid removing branch with side effects. */
745 set = single_set (insn);
746 if (!set || side_effects_p (set))
747 return NULL;
749 /* In case we zap a conditional jump, we'll need to kill
750 the cc0 setter too. */
751 kill_from = insn;
752 #ifdef HAVE_cc0
753 if (reg_mentioned_p (cc0_rtx, PATTERN (insn))
754 && only_sets_cc0_p (PREV_INSN (insn)))
755 kill_from = PREV_INSN (insn);
756 #endif
758 /* See if we can create the fallthru edge. */
759 if (in_cfglayout || can_fallthru (src, target))
761 if (dump_file)
762 fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
763 fallthru = 1;
765 /* Selectively unlink whole insn chain. */
766 if (in_cfglayout)
768 rtx insn = src->il.rtl->footer;
770 delete_insn_chain (kill_from, BB_END (src), false);
772 /* Remove barriers but keep jumptables. */
773 while (insn)
775 if (BARRIER_P (insn))
777 if (PREV_INSN (insn))
778 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
779 else
780 src->il.rtl->footer = NEXT_INSN (insn);
781 if (NEXT_INSN (insn))
782 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
784 if (LABEL_P (insn))
785 break;
786 insn = NEXT_INSN (insn);
789 else
790 delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)),
791 false);
794 /* If this already is simplejump, redirect it. */
795 else if (simplejump_p (insn))
797 if (e->dest == target)
798 return NULL;
799 if (dump_file)
800 fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
801 INSN_UID (insn), e->dest->index, target->index);
802 if (!redirect_jump (insn, block_label (target), 0))
804 gcc_assert (target == EXIT_BLOCK_PTR);
805 return NULL;
809 /* Cannot do anything for target exit block. */
810 else if (target == EXIT_BLOCK_PTR)
811 return NULL;
813 /* Or replace possibly complicated jump insn by simple jump insn. */
814 else
816 rtx target_label = block_label (target);
817 rtx barrier, label, table;
819 emit_jump_insn_after_noloc (gen_jump (target_label), insn);
820 JUMP_LABEL (BB_END (src)) = target_label;
821 LABEL_NUSES (target_label)++;
822 if (dump_file)
823 fprintf (dump_file, "Replacing insn %i by jump %i\n",
824 INSN_UID (insn), INSN_UID (BB_END (src)));
827 delete_insn_chain (kill_from, insn, false);
829 /* Recognize a tablejump that we are converting to a
830 simple jump and remove its associated CODE_LABEL
831 and ADDR_VEC or ADDR_DIFF_VEC. */
832 if (tablejump_p (insn, &label, &table))
833 delete_insn_chain (label, table, false);
835 barrier = next_nonnote_insn (BB_END (src));
836 if (!barrier || !BARRIER_P (barrier))
837 emit_barrier_after (BB_END (src));
838 else
840 if (barrier != NEXT_INSN (BB_END (src)))
842 /* Move the jump before barrier so that the notes
843 which originally were or were created before jump table are
844 inside the basic block. */
845 rtx new_insn = BB_END (src);
847 update_bb_for_insn_chain (NEXT_INSN (BB_END (src)),
848 PREV_INSN (barrier), src);
850 NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
851 PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
853 NEXT_INSN (new_insn) = barrier;
854 NEXT_INSN (PREV_INSN (barrier)) = new_insn;
856 PREV_INSN (new_insn) = PREV_INSN (barrier);
857 PREV_INSN (barrier) = new_insn;
862 /* Keep only one edge out and set proper flags. */
863 if (!single_succ_p (src))
864 remove_edge (e);
865 gcc_assert (single_succ_p (src));
867 e = single_succ_edge (src);
868 if (fallthru)
869 e->flags = EDGE_FALLTHRU;
870 else
871 e->flags = 0;
873 e->probability = REG_BR_PROB_BASE;
874 e->count = src->count;
876 if (e->dest != target)
877 redirect_edge_succ (e, target);
878 return e;
881 /* Redirect edge representing branch of (un)conditional jump or tablejump,
882 NULL on failure */
883 static edge
884 redirect_branch_edge (edge e, basic_block target)
886 rtx tmp;
887 rtx old_label = BB_HEAD (e->dest);
888 basic_block src = e->src;
889 rtx insn = BB_END (src);
891 /* We can only redirect non-fallthru edges of jump insn. */
892 if (e->flags & EDGE_FALLTHRU)
893 return NULL;
894 else if (!JUMP_P (insn))
895 return NULL;
897 /* Recognize a tablejump and adjust all matching cases. */
898 if (tablejump_p (insn, NULL, &tmp))
900 rtvec vec;
901 int j;
902 rtx new_label = block_label (target);
904 if (target == EXIT_BLOCK_PTR)
905 return NULL;
906 if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
907 vec = XVEC (PATTERN (tmp), 0);
908 else
909 vec = XVEC (PATTERN (tmp), 1);
911 for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
912 if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
914 RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
915 --LABEL_NUSES (old_label);
916 ++LABEL_NUSES (new_label);
919 /* Handle casesi dispatch insns. */
920 if ((tmp = single_set (insn)) != NULL
921 && SET_DEST (tmp) == pc_rtx
922 && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
923 && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
924 && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
926 XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (Pmode,
927 new_label);
928 --LABEL_NUSES (old_label);
929 ++LABEL_NUSES (new_label);
932 else
934 /* ?? We may play the games with moving the named labels from
935 one basic block to the other in case only one computed_jump is
936 available. */
937 if (computed_jump_p (insn)
938 /* A return instruction can't be redirected. */
939 || returnjump_p (insn))
940 return NULL;
942 /* If the insn doesn't go where we think, we're confused. */
943 gcc_assert (JUMP_LABEL (insn) == old_label);
945 /* If the substitution doesn't succeed, die. This can happen
946 if the back end emitted unrecognizable instructions or if
947 target is exit block on some arches. */
948 if (!redirect_jump (insn, block_label (target), 0))
950 gcc_assert (target == EXIT_BLOCK_PTR);
951 return NULL;
955 if (dump_file)
956 fprintf (dump_file, "Edge %i->%i redirected to %i\n",
957 e->src->index, e->dest->index, target->index);
959 if (e->dest != target)
960 e = redirect_edge_succ_nodup (e, target);
962 return e;
965 /* Attempt to change code to redirect edge E to TARGET. Don't do that on
966 expense of adding new instructions or reordering basic blocks.
968 Function can be also called with edge destination equivalent to the TARGET.
969 Then it should try the simplifications and do nothing if none is possible.
971 Return edge representing the branch if transformation succeeded. Return NULL
972 on failure.
973 We still return NULL in case E already destinated TARGET and we didn't
974 managed to simplify instruction stream. */
976 static edge
977 rtl_redirect_edge_and_branch (edge e, basic_block target)
979 edge ret;
980 basic_block src = e->src;
982 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
983 return NULL;
985 if (e->dest == target)
986 return e;
988 if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
990 df_set_bb_dirty (src);
991 return ret;
994 ret = redirect_branch_edge (e, target);
995 if (!ret)
996 return NULL;
998 df_set_bb_dirty (src);
999 return ret;
1002 /* Like force_nonfallthru below, but additionally performs redirection
1003 Used by redirect_edge_and_branch_force. */
1005 static basic_block
1006 force_nonfallthru_and_redirect (edge e, basic_block target)
1008 basic_block jump_block, new_bb = NULL, src = e->src;
1009 rtx note;
1010 edge new_edge;
1011 int abnormal_edge_flags = 0;
1013 /* In the case the last instruction is conditional jump to the next
1014 instruction, first redirect the jump itself and then continue
1015 by creating a basic block afterwards to redirect fallthru edge. */
1016 if (e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR
1017 && any_condjump_p (BB_END (e->src))
1018 && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1020 rtx note;
1021 edge b = unchecked_make_edge (e->src, target, 0);
1022 bool redirected;
1024 redirected = redirect_jump (BB_END (e->src), block_label (target), 0);
1025 gcc_assert (redirected);
1027 note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1028 if (note)
1030 int prob = INTVAL (XEXP (note, 0));
1032 b->probability = prob;
1033 b->count = e->count * prob / REG_BR_PROB_BASE;
1034 e->probability -= e->probability;
1035 e->count -= b->count;
1036 if (e->probability < 0)
1037 e->probability = 0;
1038 if (e->count < 0)
1039 e->count = 0;
1043 if (e->flags & EDGE_ABNORMAL)
1045 /* Irritating special case - fallthru edge to the same block as abnormal
1046 edge.
1047 We can't redirect abnormal edge, but we still can split the fallthru
1048 one and create separate abnormal edge to original destination.
1049 This allows bb-reorder to make such edge non-fallthru. */
1050 gcc_assert (e->dest == target);
1051 abnormal_edge_flags = e->flags & ~(EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
1052 e->flags &= EDGE_FALLTHRU | EDGE_CAN_FALLTHRU;
1054 else
1056 gcc_assert (e->flags & EDGE_FALLTHRU);
1057 if (e->src == ENTRY_BLOCK_PTR)
1059 /* We can't redirect the entry block. Create an empty block
1060 at the start of the function which we use to add the new
1061 jump. */
1062 edge tmp;
1063 edge_iterator ei;
1064 bool found = false;
1066 basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, ENTRY_BLOCK_PTR);
1068 /* Change the existing edge's source to be the new block, and add
1069 a new edge from the entry block to the new block. */
1070 e->src = bb;
1071 for (ei = ei_start (ENTRY_BLOCK_PTR->succs); (tmp = ei_safe_edge (ei)); )
1073 if (tmp == e)
1075 VEC_unordered_remove (edge, ENTRY_BLOCK_PTR->succs, ei.index);
1076 found = true;
1077 break;
1079 else
1080 ei_next (&ei);
1083 gcc_assert (found);
1085 VEC_safe_push (edge, gc, bb->succs, e);
1086 make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
1090 if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags)
1092 /* Create the new structures. */
1094 /* If the old block ended with a tablejump, skip its table
1095 by searching forward from there. Otherwise start searching
1096 forward from the last instruction of the old block. */
1097 if (!tablejump_p (BB_END (e->src), NULL, &note))
1098 note = BB_END (e->src);
1099 note = NEXT_INSN (note);
1101 jump_block = create_basic_block (note, NULL, e->src);
1102 jump_block->count = e->count;
1103 jump_block->frequency = EDGE_FREQUENCY (e);
1104 jump_block->loop_depth = target->loop_depth;
1106 /* Make sure new block ends up in correct hot/cold section. */
1108 BB_COPY_PARTITION (jump_block, e->src);
1109 if (flag_reorder_blocks_and_partition
1110 && targetm.have_named_sections
1111 && JUMP_P (BB_END (jump_block))
1112 && !any_condjump_p (BB_END (jump_block))
1113 && (EDGE_SUCC (jump_block, 0)->flags & EDGE_CROSSING))
1114 REG_NOTES (BB_END (jump_block)) = gen_rtx_EXPR_LIST (REG_CROSSING_JUMP,
1115 NULL_RTX,
1116 REG_NOTES
1117 (BB_END
1118 (jump_block)));
1120 /* Wire edge in. */
1121 new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1122 new_edge->probability = e->probability;
1123 new_edge->count = e->count;
1125 /* Redirect old edge. */
1126 redirect_edge_pred (e, jump_block);
1127 e->probability = REG_BR_PROB_BASE;
1129 new_bb = jump_block;
1131 else
1132 jump_block = e->src;
1134 e->flags &= ~EDGE_FALLTHRU;
1135 if (target == EXIT_BLOCK_PTR)
1137 #ifdef HAVE_return
1138 emit_jump_insn_after_noloc (gen_return (), BB_END (jump_block));
1139 #else
1140 gcc_unreachable ();
1141 #endif
1143 else
1145 rtx label = block_label (target);
1146 emit_jump_insn_after_noloc (gen_jump (label), BB_END (jump_block));
1147 JUMP_LABEL (BB_END (jump_block)) = label;
1148 LABEL_NUSES (label)++;
1151 emit_barrier_after (BB_END (jump_block));
1152 redirect_edge_succ_nodup (e, target);
1154 if (abnormal_edge_flags)
1155 make_edge (src, target, abnormal_edge_flags);
1157 df_mark_solutions_dirty ();
1158 return new_bb;
1161 /* Edge E is assumed to be fallthru edge. Emit needed jump instruction
1162 (and possibly create new basic block) to make edge non-fallthru.
1163 Return newly created BB or NULL if none. */
1165 basic_block
1166 force_nonfallthru (edge e)
1168 return force_nonfallthru_and_redirect (e, e->dest);
1171 /* Redirect edge even at the expense of creating new jump insn or
1172 basic block. Return new basic block if created, NULL otherwise.
1173 Conversion must be possible. */
1175 static basic_block
1176 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1178 if (redirect_edge_and_branch (e, target)
1179 || e->dest == target)
1180 return NULL;
1182 /* In case the edge redirection failed, try to force it to be non-fallthru
1183 and redirect newly created simplejump. */
1184 df_set_bb_dirty (e->src);
1185 return force_nonfallthru_and_redirect (e, target);
1188 /* The given edge should potentially be a fallthru edge. If that is in
1189 fact true, delete the jump and barriers that are in the way. */
1191 static void
1192 rtl_tidy_fallthru_edge (edge e)
1194 rtx q;
1195 basic_block b = e->src, c = b->next_bb;
1197 /* ??? In a late-running flow pass, other folks may have deleted basic
1198 blocks by nopping out blocks, leaving multiple BARRIERs between here
1199 and the target label. They ought to be chastised and fixed.
1201 We can also wind up with a sequence of undeletable labels between
1202 one block and the next.
1204 So search through a sequence of barriers, labels, and notes for
1205 the head of block C and assert that we really do fall through. */
1207 for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1208 if (INSN_P (q))
1209 return;
1211 /* Remove what will soon cease being the jump insn from the source block.
1212 If block B consisted only of this single jump, turn it into a deleted
1213 note. */
1214 q = BB_END (b);
1215 if (JUMP_P (q)
1216 && onlyjump_p (q)
1217 && (any_uncondjump_p (q)
1218 || single_succ_p (b)))
1220 #ifdef HAVE_cc0
1221 /* If this was a conditional jump, we need to also delete
1222 the insn that set cc0. */
1223 if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1224 q = PREV_INSN (q);
1225 #endif
1227 q = PREV_INSN (q);
1230 /* Selectively unlink the sequence. */
1231 if (q != PREV_INSN (BB_HEAD (c)))
1232 delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)), false);
1234 e->flags |= EDGE_FALLTHRU;
1237 /* Should move basic block BB after basic block AFTER. NIY. */
1239 static bool
1240 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1241 basic_block after ATTRIBUTE_UNUSED)
1243 return false;
1246 /* Split a (typically critical) edge. Return the new block.
1247 The edge must not be abnormal.
1249 ??? The code generally expects to be called on critical edges.
1250 The case of a block ending in an unconditional jump to a
1251 block with multiple predecessors is not handled optimally. */
1253 static basic_block
1254 rtl_split_edge (edge edge_in)
1256 basic_block bb;
1257 rtx before;
1259 /* Abnormal edges cannot be split. */
1260 gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1262 /* We are going to place the new block in front of edge destination.
1263 Avoid existence of fallthru predecessors. */
1264 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1266 edge e;
1267 edge_iterator ei;
1269 FOR_EACH_EDGE (e, ei, edge_in->dest->preds)
1270 if (e->flags & EDGE_FALLTHRU)
1271 break;
1273 if (e)
1274 force_nonfallthru (e);
1277 /* Create the basic block note. */
1278 if (edge_in->dest != EXIT_BLOCK_PTR)
1279 before = BB_HEAD (edge_in->dest);
1280 else
1281 before = NULL_RTX;
1283 /* If this is a fall through edge to the exit block, the blocks might be
1284 not adjacent, and the right place is the after the source. */
1285 if (edge_in->flags & EDGE_FALLTHRU && edge_in->dest == EXIT_BLOCK_PTR)
1287 before = NEXT_INSN (BB_END (edge_in->src));
1288 bb = create_basic_block (before, NULL, edge_in->src);
1289 BB_COPY_PARTITION (bb, edge_in->src);
1291 else
1293 bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1294 /* ??? Why not edge_in->dest->prev_bb here? */
1295 BB_COPY_PARTITION (bb, edge_in->dest);
1298 make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1300 /* For non-fallthru edges, we must adjust the predecessor's
1301 jump instruction to target our new block. */
1302 if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1304 edge redirected = redirect_edge_and_branch (edge_in, bb);
1305 gcc_assert (redirected);
1307 else
1308 redirect_edge_succ (edge_in, bb);
1310 return bb;
1313 /* Queue instructions for insertion on an edge between two basic blocks.
1314 The new instructions and basic blocks (if any) will not appear in the
1315 CFG until commit_edge_insertions is called. */
1317 void
1318 insert_insn_on_edge (rtx pattern, edge e)
1320 /* We cannot insert instructions on an abnormal critical edge.
1321 It will be easier to find the culprit if we die now. */
1322 gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1324 if (e->insns.r == NULL_RTX)
1325 start_sequence ();
1326 else
1327 push_to_sequence (e->insns.r);
1329 emit_insn (pattern);
1331 e->insns.r = get_insns ();
1332 end_sequence ();
1335 /* Update the CFG for the instructions queued on edge E. */
1337 static void
1338 commit_one_edge_insertion (edge e)
1340 rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1341 basic_block bb = NULL;
1343 /* Pull the insns off the edge now since the edge might go away. */
1344 insns = e->insns.r;
1345 e->insns.r = NULL_RTX;
1347 if (!before && !after)
1349 /* Figure out where to put these things. If the destination has
1350 one predecessor, insert there. Except for the exit block. */
1351 if (single_pred_p (e->dest) && e->dest != EXIT_BLOCK_PTR)
1353 bb = e->dest;
1355 /* Get the location correct wrt a code label, and "nice" wrt
1356 a basic block note, and before everything else. */
1357 tmp = BB_HEAD (bb);
1358 if (LABEL_P (tmp))
1359 tmp = NEXT_INSN (tmp);
1360 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1361 tmp = NEXT_INSN (tmp);
1362 if (tmp == BB_HEAD (bb))
1363 before = tmp;
1364 else if (tmp)
1365 after = PREV_INSN (tmp);
1366 else
1367 after = get_last_insn ();
1370 /* If the source has one successor and the edge is not abnormal,
1371 insert there. Except for the entry block. */
1372 else if ((e->flags & EDGE_ABNORMAL) == 0
1373 && single_succ_p (e->src)
1374 && e->src != ENTRY_BLOCK_PTR)
1376 bb = e->src;
1378 /* It is possible to have a non-simple jump here. Consider a target
1379 where some forms of unconditional jumps clobber a register. This
1380 happens on the fr30 for example.
1382 We know this block has a single successor, so we can just emit
1383 the queued insns before the jump. */
1384 if (JUMP_P (BB_END (bb)))
1385 before = BB_END (bb);
1386 else
1388 /* We'd better be fallthru, or we've lost track of
1389 what's what. */
1390 gcc_assert (e->flags & EDGE_FALLTHRU);
1392 after = BB_END (bb);
1395 /* Otherwise we must split the edge. */
1396 else
1398 bb = split_edge (e);
1399 after = BB_END (bb);
1401 if (flag_reorder_blocks_and_partition
1402 && targetm.have_named_sections
1403 && e->src != ENTRY_BLOCK_PTR
1404 && BB_PARTITION (e->src) == BB_COLD_PARTITION
1405 && !(e->flags & EDGE_CROSSING))
1407 rtx bb_note, cur_insn;
1409 bb_note = NULL_RTX;
1410 for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb));
1411 cur_insn = NEXT_INSN (cur_insn))
1412 if (NOTE_INSN_BASIC_BLOCK_P (cur_insn))
1414 bb_note = cur_insn;
1415 break;
1418 if (JUMP_P (BB_END (bb))
1419 && !any_condjump_p (BB_END (bb))
1420 && (single_succ_edge (bb)->flags & EDGE_CROSSING))
1421 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
1422 (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
1427 /* Now that we've found the spot, do the insertion. */
1429 if (before)
1431 emit_insn_before_noloc (insns, before, bb);
1432 last = prev_nonnote_insn (before);
1434 else
1435 last = emit_insn_after_noloc (insns, after, bb);
1437 if (returnjump_p (last))
1439 /* ??? Remove all outgoing edges from BB and add one for EXIT.
1440 This is not currently a problem because this only happens
1441 for the (single) epilogue, which already has a fallthru edge
1442 to EXIT. */
1444 e = single_succ_edge (bb);
1445 gcc_assert (e->dest == EXIT_BLOCK_PTR
1446 && single_succ_p (bb) && (e->flags & EDGE_FALLTHRU));
1448 e->flags &= ~EDGE_FALLTHRU;
1449 emit_barrier_after (last);
1451 if (before)
1452 delete_insn (before);
1454 else
1455 gcc_assert (!JUMP_P (last));
1457 /* Mark the basic block for find_many_sub_basic_blocks. */
1458 if (current_ir_type () != IR_RTL_CFGLAYOUT)
1459 bb->aux = &bb->aux;
1462 /* Update the CFG for all queued instructions. */
1464 void
1465 commit_edge_insertions (void)
1467 basic_block bb;
1468 sbitmap blocks;
1469 bool changed = false;
1471 #ifdef ENABLE_CHECKING
1472 verify_flow_info ();
1473 #endif
1475 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1477 edge e;
1478 edge_iterator ei;
1480 FOR_EACH_EDGE (e, ei, bb->succs)
1481 if (e->insns.r)
1483 changed = true;
1484 commit_one_edge_insertion (e);
1488 if (!changed)
1489 return;
1491 /* In the old rtl CFG API, it was OK to insert control flow on an
1492 edge, apparently? In cfglayout mode, this will *not* work, and
1493 the caller is responsible for making sure that control flow is
1494 valid at all times. */
1495 if (current_ir_type () == IR_RTL_CFGLAYOUT)
1496 return;
1498 blocks = sbitmap_alloc (last_basic_block);
1499 sbitmap_zero (blocks);
1500 FOR_EACH_BB (bb)
1501 if (bb->aux)
1503 SET_BIT (blocks, bb->index);
1504 /* Check for forgotten bb->aux values before commit_edge_insertions
1505 call. */
1506 gcc_assert (bb->aux == &bb->aux);
1507 bb->aux = NULL;
1509 find_many_sub_basic_blocks (blocks);
1510 sbitmap_free (blocks);
1514 /* Print out RTL-specific basic block information (live information
1515 at start and end). */
1517 static void
1518 rtl_dump_bb (basic_block bb, FILE *outf, int indent)
1520 rtx insn;
1521 rtx last;
1522 char *s_indent;
1524 s_indent = (char *) alloca ((size_t) indent + 1);
1525 memset (s_indent, ' ', (size_t) indent);
1526 s_indent[indent] = '\0';
1528 if (df)
1530 df_dump_top (bb, outf);
1531 putc ('\n', outf);
1534 for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
1535 insn = NEXT_INSN (insn))
1536 print_rtl_single (outf, insn);
1538 if (df)
1540 df_dump_bottom (bb, outf);
1541 putc ('\n', outf);
1546 /* Like print_rtl, but also print out live information for the start of each
1547 basic block. */
1549 void
1550 print_rtl_with_bb (FILE *outf, const_rtx rtx_first)
1552 const_rtx tmp_rtx;
1553 if (rtx_first == 0)
1554 fprintf (outf, "(nil)\n");
1555 else
1557 enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1558 int max_uid = get_max_uid ();
1559 basic_block *start = XCNEWVEC (basic_block, max_uid);
1560 basic_block *end = XCNEWVEC (basic_block, max_uid);
1561 enum bb_state *in_bb_p = XCNEWVEC (enum bb_state, max_uid);
1563 basic_block bb;
1565 if (df)
1566 df_dump_start (outf);
1568 FOR_EACH_BB_REVERSE (bb)
1570 rtx x;
1572 start[INSN_UID (BB_HEAD (bb))] = bb;
1573 end[INSN_UID (BB_END (bb))] = bb;
1574 for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
1576 enum bb_state state = IN_MULTIPLE_BB;
1578 if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1579 state = IN_ONE_BB;
1580 in_bb_p[INSN_UID (x)] = state;
1582 if (x == BB_END (bb))
1583 break;
1587 for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1589 int did_output;
1590 if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1592 edge e;
1593 edge_iterator ei;
1595 fprintf (outf, ";; Start of basic block (");
1596 FOR_EACH_EDGE (e, ei, bb->preds)
1597 fprintf (outf, " %d", e->src->index);
1598 fprintf (outf, ") -> %d\n", bb->index);
1600 if (df)
1602 df_dump_top (bb, outf);
1603 putc ('\n', outf);
1605 FOR_EACH_EDGE (e, ei, bb->preds)
1607 fputs (";; Pred edge ", outf);
1608 dump_edge_info (outf, e, 0);
1609 fputc ('\n', outf);
1613 if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1614 && !NOTE_P (tmp_rtx)
1615 && !BARRIER_P (tmp_rtx))
1616 fprintf (outf, ";; Insn is not within a basic block\n");
1617 else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1618 fprintf (outf, ";; Insn is in multiple basic blocks\n");
1620 did_output = print_rtl_single (outf, tmp_rtx);
1622 if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1624 edge e;
1625 edge_iterator ei;
1627 fprintf (outf, ";; End of basic block %d -> (", bb->index);
1628 FOR_EACH_EDGE (e, ei, bb->succs)
1629 fprintf (outf, " %d", e->dest->index);
1630 fprintf (outf, ")\n");
1632 if (df)
1634 df_dump_bottom (bb, outf);
1635 putc ('\n', outf);
1637 putc ('\n', outf);
1638 FOR_EACH_EDGE (e, ei, bb->succs)
1640 fputs (";; Succ edge ", outf);
1641 dump_edge_info (outf, e, 1);
1642 fputc ('\n', outf);
1645 if (did_output)
1646 putc ('\n', outf);
1649 free (start);
1650 free (end);
1651 free (in_bb_p);
1654 if (current_function_epilogue_delay_list != 0)
1656 fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1657 for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1658 tmp_rtx = XEXP (tmp_rtx, 1))
1659 print_rtl_single (outf, XEXP (tmp_rtx, 0));
1663 void
1664 update_br_prob_note (basic_block bb)
1666 rtx note;
1667 if (!JUMP_P (BB_END (bb)))
1668 return;
1669 note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
1670 if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
1671 return;
1672 XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
1675 /* Get the last insn associated with block BB (that includes barriers and
1676 tablejumps after BB). */
1678 get_last_bb_insn (basic_block bb)
1680 rtx tmp;
1681 rtx end = BB_END (bb);
1683 /* Include any jump table following the basic block. */
1684 if (tablejump_p (end, NULL, &tmp))
1685 end = tmp;
1687 /* Include any barriers that may follow the basic block. */
1688 tmp = next_nonnote_insn (end);
1689 while (tmp && BARRIER_P (tmp))
1691 end = tmp;
1692 tmp = next_nonnote_insn (end);
1695 return end;
1698 /* Verify the CFG and RTL consistency common for both underlying RTL and
1699 cfglayout RTL.
1701 Currently it does following checks:
1703 - overlapping of basic blocks
1704 - insns with wrong BLOCK_FOR_INSN pointers
1705 - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1706 - tails of basic blocks (ensure that boundary is necessary)
1707 - scans body of the basic block for JUMP_INSN, CODE_LABEL
1708 and NOTE_INSN_BASIC_BLOCK
1709 - verify that no fall_thru edge crosses hot/cold partition boundaries
1710 - verify that there are no pending RTL branch predictions
1712 In future it can be extended check a lot of other stuff as well
1713 (reachability of basic blocks, life information, etc. etc.). */
1715 static int
1716 rtl_verify_flow_info_1 (void)
1718 rtx x;
1719 int err = 0;
1720 basic_block bb;
1722 /* Check the general integrity of the basic blocks. */
1723 FOR_EACH_BB_REVERSE (bb)
1725 rtx insn;
1727 if (!(bb->flags & BB_RTL))
1729 error ("BB_RTL flag not set for block %d", bb->index);
1730 err = 1;
1733 FOR_BB_INSNS (bb, insn)
1734 if (BLOCK_FOR_INSN (insn) != bb)
1736 error ("insn %d basic block pointer is %d, should be %d",
1737 INSN_UID (insn),
1738 BLOCK_FOR_INSN (insn) ? BLOCK_FOR_INSN (insn)->index : 0,
1739 bb->index);
1740 err = 1;
1743 for (insn = bb->il.rtl->header; insn; insn = NEXT_INSN (insn))
1744 if (!BARRIER_P (insn)
1745 && BLOCK_FOR_INSN (insn) != NULL)
1747 error ("insn %d in header of bb %d has non-NULL basic block",
1748 INSN_UID (insn), bb->index);
1749 err = 1;
1751 for (insn = bb->il.rtl->footer; insn; insn = NEXT_INSN (insn))
1752 if (!BARRIER_P (insn)
1753 && BLOCK_FOR_INSN (insn) != NULL)
1755 error ("insn %d in footer of bb %d has non-NULL basic block",
1756 INSN_UID (insn), bb->index);
1757 err = 1;
1761 /* Now check the basic blocks (boundaries etc.) */
1762 FOR_EACH_BB_REVERSE (bb)
1764 int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
1765 edge e, fallthru = NULL;
1766 rtx note;
1767 edge_iterator ei;
1769 if (JUMP_P (BB_END (bb))
1770 && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
1771 && EDGE_COUNT (bb->succs) >= 2
1772 && any_condjump_p (BB_END (bb)))
1774 if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability
1775 && profile_status != PROFILE_ABSENT)
1777 error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
1778 INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
1779 err = 1;
1782 FOR_EACH_EDGE (e, ei, bb->succs)
1784 if (e->flags & EDGE_FALLTHRU)
1786 n_fallthru++, fallthru = e;
1787 if ((e->flags & EDGE_CROSSING)
1788 || (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
1789 && e->src != ENTRY_BLOCK_PTR
1790 && e->dest != EXIT_BLOCK_PTR))
1792 error ("fallthru edge crosses section boundary (bb %i)",
1793 e->src->index);
1794 err = 1;
1798 if ((e->flags & ~(EDGE_DFS_BACK
1799 | EDGE_CAN_FALLTHRU
1800 | EDGE_IRREDUCIBLE_LOOP
1801 | EDGE_LOOP_EXIT
1802 | EDGE_CROSSING)) == 0)
1803 n_branch++;
1805 if (e->flags & EDGE_ABNORMAL_CALL)
1806 n_call++;
1808 if (e->flags & EDGE_EH)
1809 n_eh++;
1810 else if (e->flags & EDGE_ABNORMAL)
1811 n_abnormal++;
1814 if (n_eh && GET_CODE (PATTERN (BB_END (bb))) != RESX
1815 && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
1817 error ("missing REG_EH_REGION note in the end of bb %i", bb->index);
1818 err = 1;
1820 if (n_branch
1821 && (!JUMP_P (BB_END (bb))
1822 || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
1823 || any_condjump_p (BB_END (bb))))))
1825 error ("too many outgoing branch edges from bb %i", bb->index);
1826 err = 1;
1828 if (n_fallthru && any_uncondjump_p (BB_END (bb)))
1830 error ("fallthru edge after unconditional jump %i", bb->index);
1831 err = 1;
1833 if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
1835 error ("wrong amount of branch edges after unconditional jump %i", bb->index);
1836 err = 1;
1838 if (n_branch != 1 && any_condjump_p (BB_END (bb))
1839 && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
1841 error ("wrong amount of branch edges after conditional jump %i",
1842 bb->index);
1843 err = 1;
1845 if (n_call && !CALL_P (BB_END (bb)))
1847 error ("call edges for non-call insn in bb %i", bb->index);
1848 err = 1;
1850 if (n_abnormal
1851 && (!CALL_P (BB_END (bb)) && n_call != n_abnormal)
1852 && (!JUMP_P (BB_END (bb))
1853 || any_condjump_p (BB_END (bb))
1854 || any_uncondjump_p (BB_END (bb))))
1856 error ("abnormal edges for no purpose in bb %i", bb->index);
1857 err = 1;
1860 for (x = BB_HEAD (bb); x != NEXT_INSN (BB_END (bb)); x = NEXT_INSN (x))
1861 /* We may have a barrier inside a basic block before dead code
1862 elimination. There is no BLOCK_FOR_INSN field in a barrier. */
1863 if (!BARRIER_P (x) && BLOCK_FOR_INSN (x) != bb)
1865 debug_rtx (x);
1866 if (! BLOCK_FOR_INSN (x))
1867 error
1868 ("insn %d inside basic block %d but block_for_insn is NULL",
1869 INSN_UID (x), bb->index);
1870 else
1871 error
1872 ("insn %d inside basic block %d but block_for_insn is %i",
1873 INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
1875 err = 1;
1878 /* OK pointers are correct. Now check the header of basic
1879 block. It ought to contain optional CODE_LABEL followed
1880 by NOTE_BASIC_BLOCK. */
1881 x = BB_HEAD (bb);
1882 if (LABEL_P (x))
1884 if (BB_END (bb) == x)
1886 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1887 bb->index);
1888 err = 1;
1891 x = NEXT_INSN (x);
1894 if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
1896 error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
1897 bb->index);
1898 err = 1;
1901 if (BB_END (bb) == x)
1902 /* Do checks for empty blocks here. */
1904 else
1905 for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
1907 if (NOTE_INSN_BASIC_BLOCK_P (x))
1909 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
1910 INSN_UID (x), bb->index);
1911 err = 1;
1914 if (x == BB_END (bb))
1915 break;
1917 if (control_flow_insn_p (x))
1919 error ("in basic block %d:", bb->index);
1920 fatal_insn ("flow control insn inside a basic block", x);
1925 /* Clean up. */
1926 return err;
1929 /* Verify the CFG and RTL consistency common for both underlying RTL and
1930 cfglayout RTL.
1932 Currently it does following checks:
1933 - all checks of rtl_verify_flow_info_1
1934 - test head/end pointers
1935 - check that all insns are in the basic blocks
1936 (except the switch handling code, barriers and notes)
1937 - check that all returns are followed by barriers
1938 - check that all fallthru edge points to the adjacent blocks. */
1940 static int
1941 rtl_verify_flow_info (void)
1943 basic_block bb;
1944 int err = rtl_verify_flow_info_1 ();
1945 rtx x;
1946 rtx last_head = get_last_insn ();
1947 basic_block *bb_info;
1948 int num_bb_notes;
1949 const rtx rtx_first = get_insns ();
1950 basic_block last_bb_seen = ENTRY_BLOCK_PTR, curr_bb = NULL;
1951 const int max_uid = get_max_uid ();
1953 bb_info = XCNEWVEC (basic_block, max_uid);
1955 FOR_EACH_BB_REVERSE (bb)
1957 edge e;
1958 edge_iterator ei;
1959 rtx head = BB_HEAD (bb);
1960 rtx end = BB_END (bb);
1962 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1964 /* Verify the end of the basic block is in the INSN chain. */
1965 if (x == end)
1966 break;
1968 /* And that the code outside of basic blocks has NULL bb field. */
1969 if (!BARRIER_P (x)
1970 && BLOCK_FOR_INSN (x) != NULL)
1972 error ("insn %d outside of basic blocks has non-NULL bb field",
1973 INSN_UID (x));
1974 err = 1;
1978 if (!x)
1980 error ("end insn %d for block %d not found in the insn stream",
1981 INSN_UID (end), bb->index);
1982 err = 1;
1985 /* Work backwards from the end to the head of the basic block
1986 to verify the head is in the RTL chain. */
1987 for (; x != NULL_RTX; x = PREV_INSN (x))
1989 /* While walking over the insn chain, verify insns appear
1990 in only one basic block. */
1991 if (bb_info[INSN_UID (x)] != NULL)
1993 error ("insn %d is in multiple basic blocks (%d and %d)",
1994 INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1995 err = 1;
1998 bb_info[INSN_UID (x)] = bb;
2000 if (x == head)
2001 break;
2003 if (!x)
2005 error ("head insn %d for block %d not found in the insn stream",
2006 INSN_UID (head), bb->index);
2007 err = 1;
2010 last_head = PREV_INSN (x);
2012 FOR_EACH_EDGE (e, ei, bb->succs)
2013 if (e->flags & EDGE_FALLTHRU)
2014 break;
2015 if (!e)
2017 rtx insn;
2019 /* Ensure existence of barrier in BB with no fallthru edges. */
2020 for (insn = BB_END (bb); !insn || !BARRIER_P (insn);
2021 insn = NEXT_INSN (insn))
2022 if (!insn
2023 || NOTE_INSN_BASIC_BLOCK_P (insn))
2025 error ("missing barrier after block %i", bb->index);
2026 err = 1;
2027 break;
2030 else if (e->src != ENTRY_BLOCK_PTR
2031 && e->dest != EXIT_BLOCK_PTR)
2033 rtx insn;
2035 if (e->src->next_bb != e->dest)
2037 error
2038 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2039 e->src->index, e->dest->index);
2040 err = 1;
2042 else
2043 for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2044 insn = NEXT_INSN (insn))
2045 if (BARRIER_P (insn) || INSN_P (insn))
2047 error ("verify_flow_info: Incorrect fallthru %i->%i",
2048 e->src->index, e->dest->index);
2049 fatal_insn ("wrong insn in the fallthru edge", insn);
2050 err = 1;
2055 for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
2057 /* Check that the code before the first basic block has NULL
2058 bb field. */
2059 if (!BARRIER_P (x)
2060 && BLOCK_FOR_INSN (x) != NULL)
2062 error ("insn %d outside of basic blocks has non-NULL bb field",
2063 INSN_UID (x));
2064 err = 1;
2067 free (bb_info);
2069 num_bb_notes = 0;
2070 last_bb_seen = ENTRY_BLOCK_PTR;
2072 for (x = rtx_first; x; x = NEXT_INSN (x))
2074 if (NOTE_INSN_BASIC_BLOCK_P (x))
2076 bb = NOTE_BASIC_BLOCK (x);
2078 num_bb_notes++;
2079 if (bb != last_bb_seen->next_bb)
2080 internal_error ("basic blocks not laid down consecutively");
2082 curr_bb = last_bb_seen = bb;
2085 if (!curr_bb)
2087 switch (GET_CODE (x))
2089 case BARRIER:
2090 case NOTE:
2091 break;
2093 case CODE_LABEL:
2094 /* An addr_vec is placed outside any basic block. */
2095 if (NEXT_INSN (x)
2096 && JUMP_P (NEXT_INSN (x))
2097 && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
2098 || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
2099 x = NEXT_INSN (x);
2101 /* But in any case, non-deletable labels can appear anywhere. */
2102 break;
2104 default:
2105 fatal_insn ("insn outside basic block", x);
2109 if (JUMP_P (x)
2110 && returnjump_p (x) && ! condjump_p (x)
2111 && ! (next_nonnote_insn (x) && BARRIER_P (next_nonnote_insn (x))))
2112 fatal_insn ("return not followed by barrier", x);
2113 if (curr_bb && x == BB_END (curr_bb))
2114 curr_bb = NULL;
2117 if (num_bb_notes != n_basic_blocks - NUM_FIXED_BLOCKS)
2118 internal_error
2119 ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2120 num_bb_notes, n_basic_blocks);
2122 return err;
2125 /* Assume that the preceding pass has possibly eliminated jump instructions
2126 or converted the unconditional jumps. Eliminate the edges from CFG.
2127 Return true if any edges are eliminated. */
2129 bool
2130 purge_dead_edges (basic_block bb)
2132 edge e;
2133 rtx insn = BB_END (bb), note;
2134 bool purged = false;
2135 bool found;
2136 edge_iterator ei;
2138 /* If this instruction cannot trap, remove REG_EH_REGION notes. */
2139 if (NONJUMP_INSN_P (insn)
2140 && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
2142 rtx eqnote;
2144 if (! may_trap_p (PATTERN (insn))
2145 || ((eqnote = find_reg_equal_equiv_note (insn))
2146 && ! may_trap_p (XEXP (eqnote, 0))))
2147 remove_note (insn, note);
2150 /* Cleanup abnormal edges caused by exceptions or non-local gotos. */
2151 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2153 /* There are three types of edges we need to handle correctly here: EH
2154 edges, abnormal call EH edges, and abnormal call non-EH edges. The
2155 latter can appear when nonlocal gotos are used. */
2156 if (e->flags & EDGE_EH)
2158 if (can_throw_internal (BB_END (bb))
2159 /* If this is a call edge, verify that this is a call insn. */
2160 && (! (e->flags & EDGE_ABNORMAL_CALL)
2161 || CALL_P (BB_END (bb))))
2163 ei_next (&ei);
2164 continue;
2167 else if (e->flags & EDGE_ABNORMAL_CALL)
2169 if (CALL_P (BB_END (bb))
2170 && (! (note = find_reg_note (insn, REG_EH_REGION, NULL))
2171 || INTVAL (XEXP (note, 0)) >= 0))
2173 ei_next (&ei);
2174 continue;
2177 else
2179 ei_next (&ei);
2180 continue;
2183 remove_edge (e);
2184 df_set_bb_dirty (bb);
2185 purged = true;
2188 if (JUMP_P (insn))
2190 rtx note;
2191 edge b,f;
2192 edge_iterator ei;
2194 /* We do care only about conditional jumps and simplejumps. */
2195 if (!any_condjump_p (insn)
2196 && !returnjump_p (insn)
2197 && !simplejump_p (insn))
2198 return purged;
2200 /* Branch probability/prediction notes are defined only for
2201 condjumps. We've possibly turned condjump into simplejump. */
2202 if (simplejump_p (insn))
2204 note = find_reg_note (insn, REG_BR_PROB, NULL);
2205 if (note)
2206 remove_note (insn, note);
2207 while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
2208 remove_note (insn, note);
2211 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2213 /* Avoid abnormal flags to leak from computed jumps turned
2214 into simplejumps. */
2216 e->flags &= ~EDGE_ABNORMAL;
2218 /* See if this edge is one we should keep. */
2219 if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
2220 /* A conditional jump can fall through into the next
2221 block, so we should keep the edge. */
2223 ei_next (&ei);
2224 continue;
2226 else if (e->dest != EXIT_BLOCK_PTR
2227 && BB_HEAD (e->dest) == JUMP_LABEL (insn))
2228 /* If the destination block is the target of the jump,
2229 keep the edge. */
2231 ei_next (&ei);
2232 continue;
2234 else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn))
2235 /* If the destination block is the exit block, and this
2236 instruction is a return, then keep the edge. */
2238 ei_next (&ei);
2239 continue;
2241 else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
2242 /* Keep the edges that correspond to exceptions thrown by
2243 this instruction and rematerialize the EDGE_ABNORMAL
2244 flag we just cleared above. */
2246 e->flags |= EDGE_ABNORMAL;
2247 ei_next (&ei);
2248 continue;
2251 /* We do not need this edge. */
2252 df_set_bb_dirty (bb);
2253 purged = true;
2254 remove_edge (e);
2257 if (EDGE_COUNT (bb->succs) == 0 || !purged)
2258 return purged;
2260 if (dump_file)
2261 fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
2263 if (!optimize)
2264 return purged;
2266 /* Redistribute probabilities. */
2267 if (single_succ_p (bb))
2269 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
2270 single_succ_edge (bb)->count = bb->count;
2272 else
2274 note = find_reg_note (insn, REG_BR_PROB, NULL);
2275 if (!note)
2276 return purged;
2278 b = BRANCH_EDGE (bb);
2279 f = FALLTHRU_EDGE (bb);
2280 b->probability = INTVAL (XEXP (note, 0));
2281 f->probability = REG_BR_PROB_BASE - b->probability;
2282 b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2283 f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2286 return purged;
2288 else if (CALL_P (insn) && SIBLING_CALL_P (insn))
2290 /* First, there should not be any EH or ABCALL edges resulting
2291 from non-local gotos and the like. If there were, we shouldn't
2292 have created the sibcall in the first place. Second, there
2293 should of course never have been a fallthru edge. */
2294 gcc_assert (single_succ_p (bb));
2295 gcc_assert (single_succ_edge (bb)->flags
2296 == (EDGE_SIBCALL | EDGE_ABNORMAL));
2298 return 0;
2301 /* If we don't see a jump insn, we don't know exactly why the block would
2302 have been broken at this point. Look for a simple, non-fallthru edge,
2303 as these are only created by conditional branches. If we find such an
2304 edge we know that there used to be a jump here and can then safely
2305 remove all non-fallthru edges. */
2306 found = false;
2307 FOR_EACH_EDGE (e, ei, bb->succs)
2308 if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
2310 found = true;
2311 break;
2314 if (!found)
2315 return purged;
2317 /* Remove all but the fake and fallthru edges. The fake edge may be
2318 the only successor for this block in the case of noreturn
2319 calls. */
2320 for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2322 if (!(e->flags & (EDGE_FALLTHRU | EDGE_FAKE)))
2324 df_set_bb_dirty (bb);
2325 remove_edge (e);
2326 purged = true;
2328 else
2329 ei_next (&ei);
2332 gcc_assert (single_succ_p (bb));
2334 single_succ_edge (bb)->probability = REG_BR_PROB_BASE;
2335 single_succ_edge (bb)->count = bb->count;
2337 if (dump_file)
2338 fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
2339 bb->index);
2340 return purged;
2343 /* Search all basic blocks for potentially dead edges and purge them. Return
2344 true if some edge has been eliminated. */
2346 bool
2347 purge_all_dead_edges (void)
2349 int purged = false;
2350 basic_block bb;
2352 FOR_EACH_BB (bb)
2354 bool purged_here = purge_dead_edges (bb);
2356 purged |= purged_here;
2359 return purged;
2362 /* Same as split_block but update cfg_layout structures. */
2364 static basic_block
2365 cfg_layout_split_block (basic_block bb, void *insnp)
2367 rtx insn = (rtx) insnp;
2368 basic_block new_bb = rtl_split_block (bb, insn);
2370 new_bb->il.rtl->footer = bb->il.rtl->footer;
2371 bb->il.rtl->footer = NULL;
2373 return new_bb;
2376 /* Redirect Edge to DEST. */
2377 static edge
2378 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
2380 basic_block src = e->src;
2381 edge ret;
2383 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
2384 return NULL;
2386 if (e->dest == dest)
2387 return e;
2389 if (e->src != ENTRY_BLOCK_PTR
2390 && (ret = try_redirect_by_replacing_jump (e, dest, true)))
2392 df_set_bb_dirty (src);
2393 return ret;
2396 if (e->src == ENTRY_BLOCK_PTR
2397 && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
2399 if (dump_file)
2400 fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
2401 e->src->index, dest->index);
2403 df_set_bb_dirty (e->src);
2404 redirect_edge_succ (e, dest);
2405 return e;
2408 /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
2409 in the case the basic block appears to be in sequence. Avoid this
2410 transformation. */
2412 if (e->flags & EDGE_FALLTHRU)
2414 /* Redirect any branch edges unified with the fallthru one. */
2415 if (JUMP_P (BB_END (src))
2416 && label_is_jump_target_p (BB_HEAD (e->dest),
2417 BB_END (src)))
2419 edge redirected;
2421 if (dump_file)
2422 fprintf (dump_file, "Fallthru edge unified with branch "
2423 "%i->%i redirected to %i\n",
2424 e->src->index, e->dest->index, dest->index);
2425 e->flags &= ~EDGE_FALLTHRU;
2426 redirected = redirect_branch_edge (e, dest);
2427 gcc_assert (redirected);
2428 e->flags |= EDGE_FALLTHRU;
2429 df_set_bb_dirty (e->src);
2430 return e;
2432 /* In case we are redirecting fallthru edge to the branch edge
2433 of conditional jump, remove it. */
2434 if (EDGE_COUNT (src->succs) == 2)
2436 /* Find the edge that is different from E. */
2437 edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
2439 if (s->dest == dest
2440 && any_condjump_p (BB_END (src))
2441 && onlyjump_p (BB_END (src)))
2442 delete_insn (BB_END (src));
2444 ret = redirect_edge_succ_nodup (e, dest);
2445 if (dump_file)
2446 fprintf (dump_file, "Fallthru edge %i->%i redirected to %i\n",
2447 e->src->index, e->dest->index, dest->index);
2449 else
2450 ret = redirect_branch_edge (e, dest);
2452 /* We don't want simplejumps in the insn stream during cfglayout. */
2453 gcc_assert (!simplejump_p (BB_END (src)));
2455 df_set_bb_dirty (src);
2456 return ret;
2459 /* Simple wrapper as we always can redirect fallthru edges. */
2460 static basic_block
2461 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
2463 edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
2465 gcc_assert (redirected);
2466 return NULL;
2469 /* Same as delete_basic_block but update cfg_layout structures. */
2471 static void
2472 cfg_layout_delete_block (basic_block bb)
2474 rtx insn, next, prev = PREV_INSN (BB_HEAD (bb)), *to, remaints;
2476 if (bb->il.rtl->header)
2478 next = BB_HEAD (bb);
2479 if (prev)
2480 NEXT_INSN (prev) = bb->il.rtl->header;
2481 else
2482 set_first_insn (bb->il.rtl->header);
2483 PREV_INSN (bb->il.rtl->header) = prev;
2484 insn = bb->il.rtl->header;
2485 while (NEXT_INSN (insn))
2486 insn = NEXT_INSN (insn);
2487 NEXT_INSN (insn) = next;
2488 PREV_INSN (next) = insn;
2490 next = NEXT_INSN (BB_END (bb));
2491 if (bb->il.rtl->footer)
2493 insn = bb->il.rtl->footer;
2494 while (insn)
2496 if (BARRIER_P (insn))
2498 if (PREV_INSN (insn))
2499 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
2500 else
2501 bb->il.rtl->footer = NEXT_INSN (insn);
2502 if (NEXT_INSN (insn))
2503 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
2505 if (LABEL_P (insn))
2506 break;
2507 insn = NEXT_INSN (insn);
2509 if (bb->il.rtl->footer)
2511 insn = BB_END (bb);
2512 NEXT_INSN (insn) = bb->il.rtl->footer;
2513 PREV_INSN (bb->il.rtl->footer) = insn;
2514 while (NEXT_INSN (insn))
2515 insn = NEXT_INSN (insn);
2516 NEXT_INSN (insn) = next;
2517 if (next)
2518 PREV_INSN (next) = insn;
2519 else
2520 set_last_insn (insn);
2523 if (bb->next_bb != EXIT_BLOCK_PTR)
2524 to = &bb->next_bb->il.rtl->header;
2525 else
2526 to = &cfg_layout_function_footer;
2528 rtl_delete_block (bb);
2530 if (prev)
2531 prev = NEXT_INSN (prev);
2532 else
2533 prev = get_insns ();
2534 if (next)
2535 next = PREV_INSN (next);
2536 else
2537 next = get_last_insn ();
2539 if (next && NEXT_INSN (next) != prev)
2541 remaints = unlink_insn_chain (prev, next);
2542 insn = remaints;
2543 while (NEXT_INSN (insn))
2544 insn = NEXT_INSN (insn);
2545 NEXT_INSN (insn) = *to;
2546 if (*to)
2547 PREV_INSN (*to) = insn;
2548 *to = remaints;
2552 /* Return true when blocks A and B can be safely merged. */
2554 static bool
2555 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
2557 /* If we are partitioning hot/cold basic blocks, we don't want to
2558 mess up unconditional or indirect jumps that cross between hot
2559 and cold sections.
2561 Basic block partitioning may result in some jumps that appear to
2562 be optimizable (or blocks that appear to be mergeable), but which really
2563 must be left untouched (they are required to make it safely across
2564 partition boundaries). See the comments at the top of
2565 bb-reorder.c:partition_hot_cold_basic_blocks for complete details. */
2567 if (BB_PARTITION (a) != BB_PARTITION (b))
2568 return false;
2570 /* There must be exactly one edge in between the blocks. */
2571 return (single_succ_p (a)
2572 && single_succ (a) == b
2573 && single_pred_p (b) == 1
2574 && a != b
2575 /* Must be simple edge. */
2576 && !(single_succ_edge (a)->flags & EDGE_COMPLEX)
2577 && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
2578 /* If the jump insn has side effects, we can't kill the edge.
2579 When not optimizing, try_redirect_by_replacing_jump will
2580 not allow us to redirect an edge by replacing a table jump. */
2581 && (!JUMP_P (BB_END (a))
2582 || ((!optimize || reload_completed)
2583 ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
2586 /* Merge block A and B. The blocks must be mergeable. */
2588 static void
2589 cfg_layout_merge_blocks (basic_block a, basic_block b)
2591 #ifdef ENABLE_CHECKING
2592 gcc_assert (cfg_layout_can_merge_blocks_p (a, b));
2593 #endif
2595 if (dump_file)
2596 fprintf (dump_file, "merging block %d into block %d\n", b->index, a->index);
2598 /* If there was a CODE_LABEL beginning B, delete it. */
2599 if (LABEL_P (BB_HEAD (b)))
2601 /* This might have been an EH label that no longer has incoming
2602 EH edges. Update data structures to match. */
2603 maybe_remove_eh_handler (BB_HEAD (b));
2605 delete_insn (BB_HEAD (b));
2608 /* We should have fallthru edge in a, or we can do dummy redirection to get
2609 it cleaned up. */
2610 if (JUMP_P (BB_END (a)))
2611 try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
2612 gcc_assert (!JUMP_P (BB_END (a)));
2614 /* Possible line number notes should appear in between. */
2615 if (b->il.rtl->header)
2617 rtx first = BB_END (a), last;
2619 last = emit_insn_after_noloc (b->il.rtl->header, BB_END (a), a);
2620 delete_insn_chain (NEXT_INSN (first), last, false);
2621 b->il.rtl->header = NULL;
2624 /* In the case basic blocks are not adjacent, move them around. */
2625 if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
2627 rtx first = unlink_insn_chain (BB_HEAD (b), BB_END (b));
2629 emit_insn_after_noloc (first, BB_END (a), a);
2630 /* Skip possible DELETED_LABEL insn. */
2631 if (!NOTE_INSN_BASIC_BLOCK_P (first))
2632 first = NEXT_INSN (first);
2633 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (first));
2634 BB_HEAD (b) = NULL;
2636 /* emit_insn_after_noloc doesn't call df_insn_change_bb.
2637 We need to explicitly call. */
2638 update_bb_for_insn_chain (NEXT_INSN (first),
2639 BB_END (b),
2642 delete_insn (first);
2644 /* Otherwise just re-associate the instructions. */
2645 else
2647 rtx insn;
2649 update_bb_for_insn_chain (BB_HEAD (b), BB_END (b), a);
2651 insn = BB_HEAD (b);
2652 /* Skip possible DELETED_LABEL insn. */
2653 if (!NOTE_INSN_BASIC_BLOCK_P (insn))
2654 insn = NEXT_INSN (insn);
2655 gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
2656 BB_HEAD (b) = NULL;
2657 BB_END (a) = BB_END (b);
2658 delete_insn (insn);
2661 df_bb_delete (b->index);
2663 /* Possible tablejumps and barriers should appear after the block. */
2664 if (b->il.rtl->footer)
2666 if (!a->il.rtl->footer)
2667 a->il.rtl->footer = b->il.rtl->footer;
2668 else
2670 rtx last = a->il.rtl->footer;
2672 while (NEXT_INSN (last))
2673 last = NEXT_INSN (last);
2674 NEXT_INSN (last) = b->il.rtl->footer;
2675 PREV_INSN (b->il.rtl->footer) = last;
2677 b->il.rtl->footer = NULL;
2680 if (dump_file)
2681 fprintf (dump_file, "Merged blocks %d and %d.\n",
2682 a->index, b->index);
2685 /* Split edge E. */
2687 static basic_block
2688 cfg_layout_split_edge (edge e)
2690 basic_block new_bb =
2691 create_basic_block (e->src != ENTRY_BLOCK_PTR
2692 ? NEXT_INSN (BB_END (e->src)) : get_insns (),
2693 NULL_RTX, e->src);
2695 if (e->dest == EXIT_BLOCK_PTR)
2696 BB_COPY_PARTITION (new_bb, e->src);
2697 else
2698 BB_COPY_PARTITION (new_bb, e->dest);
2699 make_edge (new_bb, e->dest, EDGE_FALLTHRU);
2700 redirect_edge_and_branch_force (e, new_bb);
2702 return new_bb;
2705 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU. */
2707 static void
2708 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
2712 /* Return 1 if BB ends with a call, possibly followed by some
2713 instructions that must stay with the call, 0 otherwise. */
2715 static bool
2716 rtl_block_ends_with_call_p (basic_block bb)
2718 rtx insn = BB_END (bb);
2720 while (!CALL_P (insn)
2721 && insn != BB_HEAD (bb)
2722 && (keep_with_call_p (insn)
2723 || NOTE_P (insn)))
2724 insn = PREV_INSN (insn);
2725 return (CALL_P (insn));
2728 /* Return 1 if BB ends with a conditional branch, 0 otherwise. */
2730 static bool
2731 rtl_block_ends_with_condjump_p (const_basic_block bb)
2733 return any_condjump_p (BB_END (bb));
2736 /* Return true if we need to add fake edge to exit.
2737 Helper function for rtl_flow_call_edges_add. */
2739 static bool
2740 need_fake_edge_p (const_rtx insn)
2742 if (!INSN_P (insn))
2743 return false;
2745 if ((CALL_P (insn)
2746 && !SIBLING_CALL_P (insn)
2747 && !find_reg_note (insn, REG_NORETURN, NULL)
2748 && !CONST_OR_PURE_CALL_P (insn)))
2749 return true;
2751 return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2752 && MEM_VOLATILE_P (PATTERN (insn)))
2753 || (GET_CODE (PATTERN (insn)) == PARALLEL
2754 && asm_noperands (insn) != -1
2755 && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
2756 || GET_CODE (PATTERN (insn)) == ASM_INPUT);
2759 /* Add fake edges to the function exit for any non constant and non noreturn
2760 calls, volatile inline assembly in the bitmap of blocks specified by
2761 BLOCKS or to the whole CFG if BLOCKS is zero. Return the number of blocks
2762 that were split.
2764 The goal is to expose cases in which entering a basic block does not imply
2765 that all subsequent instructions must be executed. */
2767 static int
2768 rtl_flow_call_edges_add (sbitmap blocks)
2770 int i;
2771 int blocks_split = 0;
2772 int last_bb = last_basic_block;
2773 bool check_last_block = false;
2775 if (n_basic_blocks == NUM_FIXED_BLOCKS)
2776 return 0;
2778 if (! blocks)
2779 check_last_block = true;
2780 else
2781 check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
2783 /* In the last basic block, before epilogue generation, there will be
2784 a fallthru edge to EXIT. Special care is required if the last insn
2785 of the last basic block is a call because make_edge folds duplicate
2786 edges, which would result in the fallthru edge also being marked
2787 fake, which would result in the fallthru edge being removed by
2788 remove_fake_edges, which would result in an invalid CFG.
2790 Moreover, we can't elide the outgoing fake edge, since the block
2791 profiler needs to take this into account in order to solve the minimal
2792 spanning tree in the case that the call doesn't return.
2794 Handle this by adding a dummy instruction in a new last basic block. */
2795 if (check_last_block)
2797 basic_block bb = EXIT_BLOCK_PTR->prev_bb;
2798 rtx insn = BB_END (bb);
2800 /* Back up past insns that must be kept in the same block as a call. */
2801 while (insn != BB_HEAD (bb)
2802 && keep_with_call_p (insn))
2803 insn = PREV_INSN (insn);
2805 if (need_fake_edge_p (insn))
2807 edge e;
2809 e = find_edge (bb, EXIT_BLOCK_PTR);
2810 if (e)
2812 insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
2813 commit_edge_insertions ();
2818 /* Now add fake edges to the function exit for any non constant
2819 calls since there is no way that we can determine if they will
2820 return or not... */
2822 for (i = NUM_FIXED_BLOCKS; i < last_bb; i++)
2824 basic_block bb = BASIC_BLOCK (i);
2825 rtx insn;
2826 rtx prev_insn;
2828 if (!bb)
2829 continue;
2831 if (blocks && !TEST_BIT (blocks, i))
2832 continue;
2834 for (insn = BB_END (bb); ; insn = prev_insn)
2836 prev_insn = PREV_INSN (insn);
2837 if (need_fake_edge_p (insn))
2839 edge e;
2840 rtx split_at_insn = insn;
2842 /* Don't split the block between a call and an insn that should
2843 remain in the same block as the call. */
2844 if (CALL_P (insn))
2845 while (split_at_insn != BB_END (bb)
2846 && keep_with_call_p (NEXT_INSN (split_at_insn)))
2847 split_at_insn = NEXT_INSN (split_at_insn);
2849 /* The handling above of the final block before the epilogue
2850 should be enough to verify that there is no edge to the exit
2851 block in CFG already. Calling make_edge in such case would
2852 cause us to mark that edge as fake and remove it later. */
2854 #ifdef ENABLE_CHECKING
2855 if (split_at_insn == BB_END (bb))
2857 e = find_edge (bb, EXIT_BLOCK_PTR);
2858 gcc_assert (e == NULL);
2860 #endif
2862 /* Note that the following may create a new basic block
2863 and renumber the existing basic blocks. */
2864 if (split_at_insn != BB_END (bb))
2866 e = split_block (bb, split_at_insn);
2867 if (e)
2868 blocks_split++;
2871 make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
2874 if (insn == BB_HEAD (bb))
2875 break;
2879 if (blocks_split)
2880 verify_flow_info ();
2882 return blocks_split;
2885 /* Add COMP_RTX as a condition at end of COND_BB. FIRST_HEAD is
2886 the conditional branch target, SECOND_HEAD should be the fall-thru
2887 there is no need to handle this here the loop versioning code handles
2888 this. the reason for SECON_HEAD is that it is needed for condition
2889 in trees, and this should be of the same type since it is a hook. */
2890 static void
2891 rtl_lv_add_condition_to_bb (basic_block first_head ,
2892 basic_block second_head ATTRIBUTE_UNUSED,
2893 basic_block cond_bb, void *comp_rtx)
2895 rtx label, seq, jump;
2896 rtx op0 = XEXP ((rtx)comp_rtx, 0);
2897 rtx op1 = XEXP ((rtx)comp_rtx, 1);
2898 enum rtx_code comp = GET_CODE ((rtx)comp_rtx);
2899 enum machine_mode mode;
2902 label = block_label (first_head);
2903 mode = GET_MODE (op0);
2904 if (mode == VOIDmode)
2905 mode = GET_MODE (op1);
2907 start_sequence ();
2908 op0 = force_operand (op0, NULL_RTX);
2909 op1 = force_operand (op1, NULL_RTX);
2910 do_compare_rtx_and_jump (op0, op1, comp, 0,
2911 mode, NULL_RTX, NULL_RTX, label);
2912 jump = get_last_insn ();
2913 JUMP_LABEL (jump) = label;
2914 LABEL_NUSES (label)++;
2915 seq = get_insns ();
2916 end_sequence ();
2918 /* Add the new cond , in the new head. */
2919 emit_insn_after(seq, BB_END(cond_bb));
2923 /* Given a block B with unconditional branch at its end, get the
2924 store the return the branch edge and the fall-thru edge in
2925 BRANCH_EDGE and FALLTHRU_EDGE respectively. */
2926 static void
2927 rtl_extract_cond_bb_edges (basic_block b, edge *branch_edge,
2928 edge *fallthru_edge)
2930 edge e = EDGE_SUCC (b, 0);
2932 if (e->flags & EDGE_FALLTHRU)
2934 *fallthru_edge = e;
2935 *branch_edge = EDGE_SUCC (b, 1);
2937 else
2939 *branch_edge = e;
2940 *fallthru_edge = EDGE_SUCC (b, 1);
2944 void
2945 init_rtl_bb_info (basic_block bb)
2947 gcc_assert (!bb->il.rtl);
2948 bb->il.rtl = GGC_CNEW (struct rtl_bb_info);
2952 /* Add EXPR to the end of basic block BB. */
2955 insert_insn_end_bb_new (rtx pat, basic_block bb)
2957 rtx insn = BB_END (bb);
2958 rtx new_insn;
2959 rtx pat_end = pat;
2961 while (NEXT_INSN (pat_end) != NULL_RTX)
2962 pat_end = NEXT_INSN (pat_end);
2964 /* If the last insn is a jump, insert EXPR in front [taking care to
2965 handle cc0, etc. properly]. Similarly we need to care trapping
2966 instructions in presence of non-call exceptions. */
2968 if (JUMP_P (insn)
2969 || (NONJUMP_INSN_P (insn)
2970 && (!single_succ_p (bb)
2971 || single_succ_edge (bb)->flags & EDGE_ABNORMAL)))
2973 #ifdef HAVE_cc0
2974 rtx note;
2975 #endif
2976 /* If this is a jump table, then we can't insert stuff here. Since
2977 we know the previous real insn must be the tablejump, we insert
2978 the new instruction just before the tablejump. */
2979 if (GET_CODE (PATTERN (insn)) == ADDR_VEC
2980 || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
2981 insn = prev_real_insn (insn);
2983 #ifdef HAVE_cc0
2984 /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
2985 if cc0 isn't set. */
2986 note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
2987 if (note)
2988 insn = XEXP (note, 0);
2989 else
2991 rtx maybe_cc0_setter = prev_nonnote_insn (insn);
2992 if (maybe_cc0_setter
2993 && INSN_P (maybe_cc0_setter)
2994 && sets_cc0_p (PATTERN (maybe_cc0_setter)))
2995 insn = maybe_cc0_setter;
2997 #endif
2998 /* FIXME: What if something in cc0/jump uses value set in new
2999 insn? */
3000 new_insn = emit_insn_before_noloc (pat, insn, bb);
3003 /* Likewise if the last insn is a call, as will happen in the presence
3004 of exception handling. */
3005 else if (CALL_P (insn)
3006 && (!single_succ_p (bb)
3007 || single_succ_edge (bb)->flags & EDGE_ABNORMAL))
3009 /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
3010 we search backward and place the instructions before the first
3011 parameter is loaded. Do this for everyone for consistency and a
3012 presumption that we'll get better code elsewhere as well. */
3014 /* Since different machines initialize their parameter registers
3015 in different orders, assume nothing. Collect the set of all
3016 parameter registers. */
3017 insn = find_first_parameter_load (insn, BB_HEAD (bb));
3019 /* If we found all the parameter loads, then we want to insert
3020 before the first parameter load.
3022 If we did not find all the parameter loads, then we might have
3023 stopped on the head of the block, which could be a CODE_LABEL.
3024 If we inserted before the CODE_LABEL, then we would be putting
3025 the insn in the wrong basic block. In that case, put the insn
3026 after the CODE_LABEL. Also, respect NOTE_INSN_BASIC_BLOCK. */
3027 while (LABEL_P (insn)
3028 || NOTE_INSN_BASIC_BLOCK_P (insn))
3029 insn = NEXT_INSN (insn);
3031 new_insn = emit_insn_before_noloc (pat, insn, bb);
3033 else
3034 new_insn = emit_insn_after_noloc (pat, insn, bb);
3036 return new_insn;
3039 /* Returns true if it is possible to remove edge E by redirecting
3040 it to the destination of the other edge from E->src. */
3042 static bool
3043 rtl_can_remove_branch_p (const_edge e)
3045 const_basic_block src = e->src;
3046 const_basic_block target = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest;
3047 const_rtx insn = BB_END (src), set;
3049 /* The conditions are taken from try_redirect_by_replacing_jump. */
3050 if (target == EXIT_BLOCK_PTR)
3051 return false;
3053 if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
3054 return false;
3056 if (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX)
3057 || BB_PARTITION (src) != BB_PARTITION (target))
3058 return false;
3060 if (!onlyjump_p (insn)
3061 || tablejump_p (insn, NULL, NULL))
3062 return false;
3064 set = single_set (insn);
3065 if (!set || side_effects_p (set))
3066 return false;
3068 return true;
3071 /* Implementation of CFG manipulation for linearized RTL. */
3072 struct cfg_hooks rtl_cfg_hooks = {
3073 "rtl",
3074 rtl_verify_flow_info,
3075 rtl_dump_bb,
3076 rtl_create_basic_block,
3077 rtl_redirect_edge_and_branch,
3078 rtl_redirect_edge_and_branch_force,
3079 rtl_can_remove_branch_p,
3080 rtl_delete_block,
3081 rtl_split_block,
3082 rtl_move_block_after,
3083 rtl_can_merge_blocks, /* can_merge_blocks_p */
3084 rtl_merge_blocks,
3085 rtl_predict_edge,
3086 rtl_predicted_by_p,
3087 NULL, /* can_duplicate_block_p */
3088 NULL, /* duplicate_block */
3089 rtl_split_edge,
3090 rtl_make_forwarder_block,
3091 rtl_tidy_fallthru_edge,
3092 rtl_block_ends_with_call_p,
3093 rtl_block_ends_with_condjump_p,
3094 rtl_flow_call_edges_add,
3095 NULL, /* execute_on_growing_pred */
3096 NULL, /* execute_on_shrinking_pred */
3097 NULL, /* duplicate loop for trees */
3098 NULL, /* lv_add_condition_to_bb */
3099 NULL, /* lv_adjust_loop_header_phi*/
3100 NULL, /* extract_cond_bb_edges */
3101 NULL /* flush_pending_stmts */
3104 /* Implementation of CFG manipulation for cfg layout RTL, where
3105 basic block connected via fallthru edges does not have to be adjacent.
3106 This representation will hopefully become the default one in future
3107 version of the compiler. */
3109 /* We do not want to declare these functions in a header file, since they
3110 should only be used through the cfghooks interface, and we do not want to
3111 move them here since it would require also moving quite a lot of related
3112 code. They are in cfglayout.c. */
3113 extern bool cfg_layout_can_duplicate_bb_p (const_basic_block);
3114 extern basic_block cfg_layout_duplicate_bb (basic_block);
3116 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
3117 "cfglayout mode",
3118 rtl_verify_flow_info_1,
3119 rtl_dump_bb,
3120 cfg_layout_create_basic_block,
3121 cfg_layout_redirect_edge_and_branch,
3122 cfg_layout_redirect_edge_and_branch_force,
3123 rtl_can_remove_branch_p,
3124 cfg_layout_delete_block,
3125 cfg_layout_split_block,
3126 rtl_move_block_after,
3127 cfg_layout_can_merge_blocks_p,
3128 cfg_layout_merge_blocks,
3129 rtl_predict_edge,
3130 rtl_predicted_by_p,
3131 cfg_layout_can_duplicate_bb_p,
3132 cfg_layout_duplicate_bb,
3133 cfg_layout_split_edge,
3134 rtl_make_forwarder_block,
3135 NULL,
3136 rtl_block_ends_with_call_p,
3137 rtl_block_ends_with_condjump_p,
3138 rtl_flow_call_edges_add,
3139 NULL, /* execute_on_growing_pred */
3140 NULL, /* execute_on_shrinking_pred */
3141 duplicate_loop_to_header_edge, /* duplicate loop for trees */
3142 rtl_lv_add_condition_to_bb, /* lv_add_condition_to_bb */
3143 NULL, /* lv_adjust_loop_header_phi*/
3144 rtl_extract_cond_bb_edges, /* extract_cond_bb_edges */
3145 NULL /* flush_pending_stmts */