OSDN Git Service

* cfgcleanup.c (outgoing_edges_match, try_crossjump_to_edge):
[pf3gnuchains/gcc-fork.git] / gcc / cfgrtl.c
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 Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA.  */
21
22 /* This file contains low level functions to manipulate the CFG and analyze it
23    that are aware of the RTL intermediate language.
24
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
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  */
39 \f
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
61
62 /* The labels mentioned in non-jump rtl.  Valid during find_basic_blocks.  */
63 /* ??? Should probably be using LABEL_NUSES instead.  It would take a
64    bit of surgery to be able to use or co-opt the routines in jump.  */
65 rtx label_value_list;
66
67 static int can_delete_note_p (rtx);
68 static int can_delete_label_p (rtx);
69 static void commit_one_edge_insertion (edge, int);
70 static rtx last_loop_beg_note (rtx);
71 static bool back_edge_of_syntactic_loop_p (basic_block, basic_block);
72 static basic_block rtl_split_edge (edge);
73 static bool rtl_move_block_after (basic_block, basic_block);
74 static int rtl_verify_flow_info (void);
75 static basic_block cfg_layout_split_block (basic_block, void *);
76 static edge cfg_layout_redirect_edge_and_branch (edge, basic_block);
77 static basic_block cfg_layout_redirect_edge_and_branch_force (edge, basic_block);
78 static void cfg_layout_delete_block (basic_block);
79 static void rtl_delete_block (basic_block);
80 static basic_block rtl_redirect_edge_and_branch_force (edge, basic_block);
81 static edge rtl_redirect_edge_and_branch (edge, basic_block);
82 static basic_block rtl_split_block (basic_block, void *);
83 static void rtl_dump_bb (basic_block, FILE *, int);
84 static int rtl_verify_flow_info_1 (void);
85 static void mark_killed_regs (rtx, rtx, void *);
86 static void rtl_make_forwarder_block (edge);
87 \f
88 /* Return true if NOTE is not one of the ones that must be kept paired,
89    so that we may simply delete it.  */
90
91 static int
92 can_delete_note_p (rtx note)
93 {
94   return (NOTE_LINE_NUMBER (note) == NOTE_INSN_DELETED
95           || NOTE_LINE_NUMBER (note) == NOTE_INSN_BASIC_BLOCK
96           || NOTE_LINE_NUMBER (note) == NOTE_INSN_UNLIKELY_EXECUTED_CODE);
97 }
98
99 /* True if a given label can be deleted.  */
100
101 static int
102 can_delete_label_p (rtx label)
103 {
104   return (!LABEL_PRESERVE_P (label)
105           /* User declared labels must be preserved.  */
106           && LABEL_NAME (label) == 0
107           && !in_expr_list_p (forced_labels, label)
108           && !in_expr_list_p (label_value_list, label));
109 }
110
111 /* Delete INSN by patching it out.  Return the next insn.  */
112
113 rtx
114 delete_insn (rtx insn)
115 {
116   rtx next = NEXT_INSN (insn);
117   rtx note;
118   bool really_delete = true;
119
120   if (LABEL_P (insn))
121     {
122       /* Some labels can't be directly removed from the INSN chain, as they
123          might be references via variables, constant pool etc.
124          Convert them to the special NOTE_INSN_DELETED_LABEL note.  */
125       if (! can_delete_label_p (insn))
126         {
127           const char *name = LABEL_NAME (insn);
128
129           really_delete = false;
130           PUT_CODE (insn, NOTE);
131           NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED_LABEL;
132           NOTE_DELETED_LABEL_NAME (insn) = name;
133         }
134
135       remove_node_from_expr_list (insn, &nonlocal_goto_handler_labels);
136     }
137
138   if (really_delete)
139     {
140       /* If this insn has already been deleted, something is very wrong.  */
141       gcc_assert (!INSN_DELETED_P (insn));
142       remove_insn (insn);
143       INSN_DELETED_P (insn) = 1;
144     }
145
146   /* If deleting a jump, decrement the use count of the label.  Deleting
147      the label itself should happen in the normal course of block merging.  */
148   if (JUMP_P (insn)
149       && JUMP_LABEL (insn)
150       && LABEL_P (JUMP_LABEL (insn)))
151     LABEL_NUSES (JUMP_LABEL (insn))--;
152
153   /* Also if deleting an insn that references a label.  */
154   else
155     {
156       while ((note = find_reg_note (insn, REG_LABEL, NULL_RTX)) != NULL_RTX
157              && LABEL_P (XEXP (note, 0)))
158         {
159           LABEL_NUSES (XEXP (note, 0))--;
160           remove_note (insn, note);
161         }
162     }
163
164   if (JUMP_P (insn)
165       && (GET_CODE (PATTERN (insn)) == ADDR_VEC
166           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
167     {
168       rtx pat = PATTERN (insn);
169       int diff_vec_p = GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC;
170       int len = XVECLEN (pat, diff_vec_p);
171       int i;
172
173       for (i = 0; i < len; i++)
174         {
175           rtx label = XEXP (XVECEXP (pat, diff_vec_p, i), 0);
176
177           /* When deleting code in bulk (e.g. removing many unreachable
178              blocks) we can delete a label that's a target of the vector
179              before deleting the vector itself.  */
180           if (!NOTE_P (label))
181             LABEL_NUSES (label)--;
182         }
183     }
184
185   return next;
186 }
187
188 /* Like delete_insn but also purge dead edges from BB.  */
189 rtx
190 delete_insn_and_edges (rtx insn)
191 {
192   rtx x;
193   bool purge = false;
194
195   if (INSN_P (insn)
196       && BLOCK_FOR_INSN (insn)
197       && BB_END (BLOCK_FOR_INSN (insn)) == insn)
198     purge = true;
199   x = delete_insn (insn);
200   if (purge)
201     purge_dead_edges (BLOCK_FOR_INSN (insn));
202   return x;
203 }
204
205 /* Unlink a chain of insns between START and FINISH, leaving notes
206    that must be paired.  */
207
208 void
209 delete_insn_chain (rtx start, rtx finish)
210 {
211   rtx next;
212
213   /* Unchain the insns one by one.  It would be quicker to delete all of these
214      with a single unchaining, rather than one at a time, but we need to keep
215      the NOTE's.  */
216   while (1)
217     {
218       next = NEXT_INSN (start);
219       if (NOTE_P (start) && !can_delete_note_p (start))
220         ;
221       else
222         next = delete_insn (start);
223
224       if (start == finish)
225         break;
226       start = next;
227     }
228 }
229
230 /* Like delete_insn but also purge dead edges from BB.  */
231 void
232 delete_insn_chain_and_edges (rtx first, rtx last)
233 {
234   bool purge = false;
235
236   if (INSN_P (last)
237       && BLOCK_FOR_INSN (last)
238       && BB_END (BLOCK_FOR_INSN (last)) == last)
239     purge = true;
240   delete_insn_chain (first, last);
241   if (purge)
242     purge_dead_edges (BLOCK_FOR_INSN (last));
243 }
244 \f
245 /* Create a new basic block consisting of the instructions between HEAD and END
246    inclusive.  This function is designed to allow fast BB construction - reuses
247    the note and basic block struct in BB_NOTE, if any and do not grow
248    BASIC_BLOCK chain and should be used directly only by CFG construction code.
249    END can be NULL in to create new empty basic block before HEAD.  Both END
250    and HEAD can be NULL to create basic block at the end of INSN chain.
251    AFTER is the basic block we should be put after.  */
252
253 basic_block
254 create_basic_block_structure (rtx head, rtx end, rtx bb_note, basic_block after)
255 {
256   basic_block bb;
257
258   if (bb_note
259       && (bb = NOTE_BASIC_BLOCK (bb_note)) != NULL
260       && bb->aux == NULL)
261     {
262       /* If we found an existing note, thread it back onto the chain.  */
263
264       rtx after;
265
266       if (LABEL_P (head))
267         after = head;
268       else
269         {
270           after = PREV_INSN (head);
271           head = bb_note;
272         }
273
274       if (after != bb_note && NEXT_INSN (after) != bb_note)
275         reorder_insns_nobb (bb_note, bb_note, after);
276     }
277   else
278     {
279       /* Otherwise we must create a note and a basic block structure.  */
280
281       bb = alloc_block ();
282
283       if (!head && !end)
284         head = end = bb_note
285           = emit_note_after (NOTE_INSN_BASIC_BLOCK, get_last_insn ());
286       else if (LABEL_P (head) && end)
287         {
288           bb_note = emit_note_after (NOTE_INSN_BASIC_BLOCK, head);
289           if (head == end)
290             end = bb_note;
291         }
292       else
293         {
294           bb_note = emit_note_before (NOTE_INSN_BASIC_BLOCK, head);
295           head = bb_note;
296           if (!end)
297             end = head;
298         }
299
300       NOTE_BASIC_BLOCK (bb_note) = bb;
301     }
302
303   /* Always include the bb note in the block.  */
304   if (NEXT_INSN (end) == bb_note)
305     end = bb_note;
306
307   BB_HEAD (bb) = head;
308   BB_END (bb) = end;
309   bb->index = last_basic_block++;
310   bb->flags = BB_NEW;
311   link_block (bb, after);
312   BASIC_BLOCK (bb->index) = bb;
313   update_bb_for_insn (bb);
314   BB_SET_PARTITION (bb, BB_UNPARTITIONED);
315
316   /* Tag the block so that we know it has been used when considering
317      other basic block notes.  */
318   bb->aux = bb;
319
320   return bb;
321 }
322
323 /* Create new basic block consisting of instructions in between HEAD and END
324    and place it to the BB chain after block AFTER.  END can be NULL in to
325    create new empty basic block before HEAD.  Both END and HEAD can be NULL to
326    create basic block at the end of INSN chain.  */
327
328 static basic_block
329 rtl_create_basic_block (void *headp, void *endp, basic_block after)
330 {
331   rtx head = headp, end = endp;
332   basic_block bb;
333
334   /* Grow the basic block array if needed.  */
335   if ((size_t) last_basic_block >= VARRAY_SIZE (basic_block_info))
336     {
337       size_t new_size = last_basic_block + (last_basic_block + 3) / 4;
338       VARRAY_GROW (basic_block_info, new_size);
339     }
340
341   n_basic_blocks++;
342
343   bb = create_basic_block_structure (head, end, NULL, after);
344   bb->aux = NULL;
345   return bb;
346 }
347
348 static basic_block
349 cfg_layout_create_basic_block (void *head, void *end, basic_block after)
350 {
351   basic_block newbb = rtl_create_basic_block (head, end, after);
352
353   initialize_bb_rbi (newbb);
354   return newbb;
355 }
356 \f
357 /* Delete the insns in a (non-live) block.  We physically delete every
358    non-deleted-note insn, and update the flow graph appropriately.
359
360    Return nonzero if we deleted an exception handler.  */
361
362 /* ??? Preserving all such notes strikes me as wrong.  It would be nice
363    to post-process the stream to remove empty blocks, loops, ranges, etc.  */
364
365 static void
366 rtl_delete_block (basic_block b)
367 {
368   rtx insn, end, tmp;
369
370   /* If the head of this block is a CODE_LABEL, then it might be the
371      label for an exception handler which can't be reached.  We need
372      to remove the label from the exception_handler_label list.  */
373   insn = BB_HEAD (b);
374   if (LABEL_P (insn))
375     maybe_remove_eh_handler (insn);
376
377   /* Include any jump table following the basic block.  */
378   end = BB_END (b);
379   if (tablejump_p (end, NULL, &tmp))
380     end = tmp;
381
382   /* Include any barrier that may follow the basic block.  */
383   tmp = next_nonnote_insn (end);
384   if (tmp && BARRIER_P (tmp))
385     end = tmp;
386
387   /* Selectively delete the entire chain.  */
388   BB_HEAD (b) = NULL;
389   delete_insn_chain (insn, end);
390 }
391 \f
392 /* Records the basic block struct in BLOCK_FOR_INSN for every insn.  */
393
394 void
395 compute_bb_for_insn (void)
396 {
397   basic_block bb;
398
399   FOR_EACH_BB (bb)
400     {
401       rtx end = BB_END (bb);
402       rtx insn;
403
404       for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
405         {
406           BLOCK_FOR_INSN (insn) = bb;
407           if (insn == end)
408             break;
409         }
410     }
411 }
412
413 /* Release the basic_block_for_insn array.  */
414
415 void
416 free_bb_for_insn (void)
417 {
418   rtx insn;
419   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
420     if (!BARRIER_P (insn))
421       BLOCK_FOR_INSN (insn) = NULL;
422 }
423
424 /* Return RTX to emit after when we want to emit code on the entry of function.  */
425 rtx
426 entry_of_function (void)
427 {
428   return (n_basic_blocks ? BB_HEAD (ENTRY_BLOCK_PTR->next_bb) : get_insns ());
429 }
430
431 /* Update insns block within BB.  */
432
433 void
434 update_bb_for_insn (basic_block bb)
435 {
436   rtx insn;
437
438   for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
439     {
440       if (!BARRIER_P (insn))
441         set_block_for_insn (insn, bb);
442       if (insn == BB_END (bb))
443         break;
444     }
445 }
446 \f
447 /* Creates a new basic block just after basic block B by splitting
448    everything after specified instruction I.  */
449
450 static basic_block
451 rtl_split_block (basic_block bb, void *insnp)
452 {
453   basic_block new_bb;
454   rtx insn = insnp;
455   edge e;
456   edge_iterator ei;
457
458   if (!insn)
459     {
460       insn = first_insn_after_basic_block_note (bb);
461
462       if (insn)
463         insn = PREV_INSN (insn);
464       else
465         insn = get_last_insn ();
466     }
467
468   /* We probably should check type of the insn so that we do not create
469      inconsistent cfg.  It is checked in verify_flow_info anyway, so do not
470      bother.  */
471   if (insn == BB_END (bb))
472     emit_note_after (NOTE_INSN_DELETED, insn);
473
474   /* Create the new basic block.  */
475   new_bb = create_basic_block (NEXT_INSN (insn), BB_END (bb), bb);
476   BB_COPY_PARTITION (new_bb, bb);
477   BB_END (bb) = insn;
478
479   /* Redirect the outgoing edges.  */
480   new_bb->succs = bb->succs;
481   bb->succs = NULL;
482   FOR_EACH_EDGE (e, ei, new_bb->succs)
483     e->src = new_bb;
484
485   if (bb->global_live_at_start)
486     {
487       new_bb->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
488       new_bb->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
489       COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
490
491       /* We now have to calculate which registers are live at the end
492          of the split basic block and at the start of the new basic
493          block.  Start with those registers that are known to be live
494          at the end of the original basic block and get
495          propagate_block to determine which registers are live.  */
496       COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_end);
497       propagate_block (new_bb, new_bb->global_live_at_start, NULL, NULL, 0);
498       COPY_REG_SET (bb->global_live_at_end,
499                     new_bb->global_live_at_start);
500 #ifdef HAVE_conditional_execution
501       /* In the presence of conditional execution we are not able to update
502          liveness precisely.  */
503       if (reload_completed)
504         {
505           bb->flags |= BB_DIRTY;
506           new_bb->flags |= BB_DIRTY;
507         }
508 #endif
509     }
510
511   return new_bb;
512 }
513
514 /* Blocks A and B are to be merged into a single block A.  The insns
515    are already contiguous.  */
516
517 static void
518 rtl_merge_blocks (basic_block a, basic_block b)
519 {
520   rtx b_head = BB_HEAD (b), b_end = BB_END (b), a_end = BB_END (a);
521   rtx del_first = NULL_RTX, del_last = NULL_RTX;
522   int b_empty = 0;
523
524   /* If there was a CODE_LABEL beginning B, delete it.  */
525   if (LABEL_P (b_head))
526     {
527       /* Detect basic blocks with nothing but a label.  This can happen
528          in particular at the end of a function.  */
529       if (b_head == b_end)
530         b_empty = 1;
531
532       del_first = del_last = b_head;
533       b_head = NEXT_INSN (b_head);
534     }
535
536   /* Delete the basic block note and handle blocks containing just that
537      note.  */
538   if (NOTE_INSN_BASIC_BLOCK_P (b_head))
539     {
540       if (b_head == b_end)
541         b_empty = 1;
542       if (! del_last)
543         del_first = b_head;
544
545       del_last = b_head;
546       b_head = NEXT_INSN (b_head);
547     }
548
549   /* If there was a jump out of A, delete it.  */
550   if (JUMP_P (a_end))
551     {
552       rtx prev;
553
554       for (prev = PREV_INSN (a_end); ; prev = PREV_INSN (prev))
555         if (!NOTE_P (prev)
556             || NOTE_LINE_NUMBER (prev) == NOTE_INSN_BASIC_BLOCK
557             || prev == BB_HEAD (a))
558           break;
559
560       del_first = a_end;
561
562 #ifdef HAVE_cc0
563       /* If this was a conditional jump, we need to also delete
564          the insn that set cc0.  */
565       if (only_sets_cc0_p (prev))
566         {
567           rtx tmp = prev;
568
569           prev = prev_nonnote_insn (prev);
570           if (!prev)
571             prev = BB_HEAD (a);
572           del_first = tmp;
573         }
574 #endif
575
576       a_end = PREV_INSN (del_first);
577     }
578   else if (BARRIER_P (NEXT_INSN (a_end)))
579     del_first = NEXT_INSN (a_end);
580
581   /* Delete everything marked above as well as crap that might be
582      hanging out between the two blocks.  */
583   BB_HEAD (b) = NULL;
584   delete_insn_chain (del_first, del_last);
585
586   /* Reassociate the insns of B with A.  */
587   if (!b_empty)
588     {
589       rtx x;
590
591       for (x = a_end; x != b_end; x = NEXT_INSN (x))
592         set_block_for_insn (x, a);
593
594       set_block_for_insn (b_end, a);
595
596       a_end = b_end;
597     }
598
599   BB_END (a) = a_end;
600 }
601
602 /* Return true when block A and B can be merged.  */
603 static bool
604 rtl_can_merge_blocks (basic_block a,basic_block b)
605 {
606   /* If we are partitioning hot/cold basic blocks, we don't want to
607      mess up unconditional or indirect jumps that cross between hot
608      and cold sections.
609
610      Basic block partitioning may result in some jumps that appear to
611      be optimizable (or blocks that appear to be mergeable), but which really 
612      must be left untouched (they are required to make it safely across 
613      partition boundaries).  See  the comments at the top of 
614      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
615
616   if (flag_reorder_blocks_and_partition
617       && (find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX)
618           || find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
619           || BB_PARTITION (a) != BB_PARTITION (b)))
620     return false;
621
622   /* There must be exactly one edge in between the blocks.  */
623   return (EDGE_COUNT (a->succs) == 1
624           && EDGE_SUCC (a, 0)->dest == b
625           && EDGE_COUNT (b->preds) == 1
626           && a != b
627           /* Must be simple edge.  */
628           && !(EDGE_SUCC (a, 0)->flags & EDGE_COMPLEX)
629           && a->next_bb == b
630           && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
631           /* If the jump insn has side effects,
632              we can't kill the edge.  */
633           && (!JUMP_P (BB_END (a))
634               || (reload_completed
635                   ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
636 }
637 \f
638 /* Return the label in the head of basic block BLOCK.  Create one if it doesn't
639    exist.  */
640
641 rtx
642 block_label (basic_block block)
643 {
644   if (block == EXIT_BLOCK_PTR)
645     return NULL_RTX;
646
647   if (!LABEL_P (BB_HEAD (block)))
648     {
649       BB_HEAD (block) = emit_label_before (gen_label_rtx (), BB_HEAD (block));
650     }
651
652   return BB_HEAD (block);
653 }
654
655 /* Attempt to perform edge redirection by replacing possibly complex jump
656    instruction by unconditional jump or removing jump completely.  This can
657    apply only if all edges now point to the same block.  The parameters and
658    return values are equivalent to redirect_edge_and_branch.  */
659
660 edge
661 try_redirect_by_replacing_jump (edge e, basic_block target, bool in_cfglayout)
662 {
663   basic_block src = e->src;
664   rtx insn = BB_END (src), kill_from;
665   rtx set;
666   int fallthru = 0;
667
668   /* If we are partitioning hot/cold basic blocks, we don't want to
669      mess up unconditional or indirect jumps that cross between hot
670      and cold sections.
671
672      Basic block partitioning may result in some jumps that appear to
673      be optimizable (or blocks that appear to be mergeable), but which really 
674      must be left untouched (they are required to make it safely across 
675      partition boundaries).  See  the comments at the top of 
676      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
677   
678   if (flag_reorder_blocks_and_partition
679       && (find_reg_note (insn, REG_CROSSING_JUMP, NULL_RTX)
680           || BB_PARTITION (src) != BB_PARTITION (target)))
681     return NULL;
682
683   /* We can replace or remove a complex jump only when we have exactly
684      two edges.  Also, if we have exactly one outgoing edge, we can
685      redirect that.  */
686   if (EDGE_COUNT (src->succs) >= 3
687       /* Verify that all targets will be TARGET.  Specifically, the
688          edge that is not E must also go to TARGET.  */
689       || (EDGE_COUNT (src->succs) == 2
690           && EDGE_SUCC (src, EDGE_SUCC (src, 0) == e)->dest != target))
691     return NULL;
692
693   if (!onlyjump_p (insn))
694     return NULL;
695   if ((!optimize || reload_completed) && tablejump_p (insn, NULL, NULL))
696     return NULL;
697
698   /* Avoid removing branch with side effects.  */
699   set = single_set (insn);
700   if (!set || side_effects_p (set))
701     return NULL;
702
703   /* In case we zap a conditional jump, we'll need to kill
704      the cc0 setter too.  */
705   kill_from = insn;
706 #ifdef HAVE_cc0
707   if (reg_mentioned_p (cc0_rtx, PATTERN (insn)))
708     kill_from = PREV_INSN (insn);
709 #endif
710
711   /* See if we can create the fallthru edge.  */
712   if (in_cfglayout || can_fallthru (src, target))
713     {
714       if (dump_file)
715         fprintf (dump_file, "Removing jump %i.\n", INSN_UID (insn));
716       fallthru = 1;
717
718       /* Selectively unlink whole insn chain.  */
719       if (in_cfglayout)
720         {
721           rtx insn = src->rbi->footer;
722
723           delete_insn_chain (kill_from, BB_END (src));
724
725           /* Remove barriers but keep jumptables.  */
726           while (insn)
727             {
728               if (BARRIER_P (insn))
729                 {
730                   if (PREV_INSN (insn))
731                     NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
732                   else
733                     src->rbi->footer = NEXT_INSN (insn);
734                   if (NEXT_INSN (insn))
735                     PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
736                 }
737               if (LABEL_P (insn))
738                 break;
739               insn = NEXT_INSN (insn);
740             }
741         }
742       else
743         delete_insn_chain (kill_from, PREV_INSN (BB_HEAD (target)));
744     }
745
746   /* If this already is simplejump, redirect it.  */
747   else if (simplejump_p (insn))
748     {
749       if (e->dest == target)
750         return NULL;
751       if (dump_file)
752         fprintf (dump_file, "Redirecting jump %i from %i to %i.\n",
753                  INSN_UID (insn), e->dest->index, target->index);
754       if (!redirect_jump (insn, block_label (target), 0))
755         {
756           gcc_assert (target == EXIT_BLOCK_PTR);
757           return NULL;
758         }
759     }
760
761   /* Cannot do anything for target exit block.  */
762   else if (target == EXIT_BLOCK_PTR)
763     return NULL;
764
765   /* Or replace possibly complicated jump insn by simple jump insn.  */
766   else
767     {
768       rtx target_label = block_label (target);
769       rtx barrier, label, table;
770
771       emit_jump_insn_after_noloc (gen_jump (target_label), insn);
772       JUMP_LABEL (BB_END (src)) = target_label;
773       LABEL_NUSES (target_label)++;
774       if (dump_file)
775         fprintf (dump_file, "Replacing insn %i by jump %i\n",
776                  INSN_UID (insn), INSN_UID (BB_END (src)));
777
778
779       delete_insn_chain (kill_from, insn);
780
781       /* Recognize a tablejump that we are converting to a
782          simple jump and remove its associated CODE_LABEL
783          and ADDR_VEC or ADDR_DIFF_VEC.  */
784       if (tablejump_p (insn, &label, &table))
785         delete_insn_chain (label, table);
786
787       barrier = next_nonnote_insn (BB_END (src));
788       if (!barrier || !BARRIER_P (barrier))
789         emit_barrier_after (BB_END (src));
790       else
791         {
792           if (barrier != NEXT_INSN (BB_END (src)))
793             {
794               /* Move the jump before barrier so that the notes
795                  which originally were or were created before jump table are
796                  inside the basic block.  */
797               rtx new_insn = BB_END (src);
798               rtx tmp;
799
800               for (tmp = NEXT_INSN (BB_END (src)); tmp != barrier;
801                    tmp = NEXT_INSN (tmp))
802                 set_block_for_insn (tmp, src);
803
804               NEXT_INSN (PREV_INSN (new_insn)) = NEXT_INSN (new_insn);
805               PREV_INSN (NEXT_INSN (new_insn)) = PREV_INSN (new_insn);
806
807               NEXT_INSN (new_insn) = barrier;
808               NEXT_INSN (PREV_INSN (barrier)) = new_insn;
809
810               PREV_INSN (new_insn) = PREV_INSN (barrier);
811               PREV_INSN (barrier) = new_insn;
812             }
813         }
814     }
815
816   /* Keep only one edge out and set proper flags.  */
817   while (EDGE_COUNT (src->succs) > 1)
818     remove_edge (e);
819
820   e = EDGE_SUCC (src, 0);
821   if (fallthru)
822     e->flags = EDGE_FALLTHRU;
823   else
824     e->flags = 0;
825
826   e->probability = REG_BR_PROB_BASE;
827   e->count = src->count;
828
829   /* We don't want a block to end on a line-number note since that has
830      the potential of changing the code between -g and not -g.  */
831   while (NOTE_P (BB_END (e->src))
832          && NOTE_LINE_NUMBER (BB_END (e->src)) >= 0)
833     delete_insn (BB_END (e->src));
834
835   if (e->dest != target)
836     redirect_edge_succ (e, target);
837
838   return e;
839 }
840
841 /* Return last loop_beg note appearing after INSN, before start of next
842    basic block.  Return INSN if there are no such notes.
843
844    When emitting jump to redirect a fallthru edge, it should always appear
845    after the LOOP_BEG notes, as loop optimizer expect loop to either start by
846    fallthru edge or jump following the LOOP_BEG note jumping to the loop exit
847    test.  */
848
849 static rtx
850 last_loop_beg_note (rtx insn)
851 {
852   rtx last = insn;
853
854   for (insn = NEXT_INSN (insn); insn && NOTE_P (insn)
855        && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
856        insn = NEXT_INSN (insn))
857     if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
858       last = insn;
859
860   return last;
861 }
862
863 /* Redirect edge representing branch of (un)conditional jump or tablejump,
864    NULL on failure  */
865 static edge
866 redirect_branch_edge (edge e, basic_block target)
867 {
868   rtx tmp;
869   rtx old_label = BB_HEAD (e->dest);
870   basic_block src = e->src;
871   rtx insn = BB_END (src);
872
873   /* We can only redirect non-fallthru edges of jump insn.  */
874   if (e->flags & EDGE_FALLTHRU)
875     return NULL;
876   else if (!JUMP_P (insn))
877     return NULL;
878
879   /* Recognize a tablejump and adjust all matching cases.  */
880   if (tablejump_p (insn, NULL, &tmp))
881     {
882       rtvec vec;
883       int j;
884       rtx new_label = block_label (target);
885
886       if (target == EXIT_BLOCK_PTR)
887         return NULL;
888       if (GET_CODE (PATTERN (tmp)) == ADDR_VEC)
889         vec = XVEC (PATTERN (tmp), 0);
890       else
891         vec = XVEC (PATTERN (tmp), 1);
892
893       for (j = GET_NUM_ELEM (vec) - 1; j >= 0; --j)
894         if (XEXP (RTVEC_ELT (vec, j), 0) == old_label)
895           {
896             RTVEC_ELT (vec, j) = gen_rtx_LABEL_REF (Pmode, new_label);
897             --LABEL_NUSES (old_label);
898             ++LABEL_NUSES (new_label);
899           }
900
901       /* Handle casesi dispatch insns.  */
902       if ((tmp = single_set (insn)) != NULL
903           && SET_DEST (tmp) == pc_rtx
904           && GET_CODE (SET_SRC (tmp)) == IF_THEN_ELSE
905           && GET_CODE (XEXP (SET_SRC (tmp), 2)) == LABEL_REF
906           && XEXP (XEXP (SET_SRC (tmp), 2), 0) == old_label)
907         {
908           XEXP (SET_SRC (tmp), 2) = gen_rtx_LABEL_REF (VOIDmode,
909                                                        new_label);
910           --LABEL_NUSES (old_label);
911           ++LABEL_NUSES (new_label);
912         }
913     }
914   else
915     {
916       /* ?? We may play the games with moving the named labels from
917          one basic block to the other in case only one computed_jump is
918          available.  */
919       if (computed_jump_p (insn)
920           /* A return instruction can't be redirected.  */
921           || returnjump_p (insn))
922         return NULL;
923
924       /* If the insn doesn't go where we think, we're confused.  */
925       gcc_assert (JUMP_LABEL (insn) == old_label);
926
927       /* If the substitution doesn't succeed, die.  This can happen
928          if the back end emitted unrecognizable instructions or if
929          target is exit block on some arches.  */
930       if (!redirect_jump (insn, block_label (target), 0))
931         {
932           gcc_assert (target == EXIT_BLOCK_PTR);
933           return NULL;
934         }
935     }
936
937   if (dump_file)
938     fprintf (dump_file, "Edge %i->%i redirected to %i\n",
939              e->src->index, e->dest->index, target->index);
940
941   if (e->dest != target)
942     e = redirect_edge_succ_nodup (e, target);
943   return e;
944 }
945
946 /* Attempt to change code to redirect edge E to TARGET.  Don't do that on
947    expense of adding new instructions or reordering basic blocks.
948
949    Function can be also called with edge destination equivalent to the TARGET.
950    Then it should try the simplifications and do nothing if none is possible.
951
952    Return edge representing the branch if transformation succeeded.  Return NULL
953    on failure.
954    We still return NULL in case E already destinated TARGET and we didn't
955    managed to simplify instruction stream.  */
956
957 static edge
958 rtl_redirect_edge_and_branch (edge e, basic_block target)
959 {
960   edge ret;
961   basic_block src = e->src;
962
963   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
964     return NULL;
965
966   if (e->dest == target)
967     return e;
968
969   if ((ret = try_redirect_by_replacing_jump (e, target, false)) != NULL)
970     {
971       src->flags |= BB_DIRTY;
972       return ret;
973     }
974
975   ret = redirect_branch_edge (e, target);
976   if (!ret)
977     return NULL;
978
979   src->flags |= BB_DIRTY;
980   return ret;
981 }
982
983 /* Like force_nonfallthru below, but additionally performs redirection
984    Used by redirect_edge_and_branch_force.  */
985
986 static basic_block
987 force_nonfallthru_and_redirect (edge e, basic_block target)
988 {
989   basic_block jump_block, new_bb = NULL, src = e->src;
990   rtx note;
991   edge new_edge;
992   int abnormal_edge_flags = 0;
993
994   /* In the case the last instruction is conditional jump to the next
995      instruction, first redirect the jump itself and then continue
996      by creating a basic block afterwards to redirect fallthru edge.  */
997   if (e->src != ENTRY_BLOCK_PTR && e->dest != EXIT_BLOCK_PTR
998       && any_condjump_p (BB_END (e->src))
999       /* When called from cfglayout, fallthru edges do not
1000          necessarily go to the next block.  */
1001       && e->src->next_bb == e->dest
1002       && JUMP_LABEL (BB_END (e->src)) == BB_HEAD (e->dest))
1003     {
1004       rtx note;
1005       edge b = unchecked_make_edge (e->src, target, 0);
1006       bool redirected;
1007
1008       redirected = redirect_jump (BB_END (e->src), block_label (target), 0);
1009       gcc_assert (redirected);
1010       
1011       note = find_reg_note (BB_END (e->src), REG_BR_PROB, NULL_RTX);
1012       if (note)
1013         {
1014           int prob = INTVAL (XEXP (note, 0));
1015
1016           b->probability = prob;
1017           b->count = e->count * prob / REG_BR_PROB_BASE;
1018           e->probability -= e->probability;
1019           e->count -= b->count;
1020           if (e->probability < 0)
1021             e->probability = 0;
1022           if (e->count < 0)
1023             e->count = 0;
1024         }
1025     }
1026
1027   if (e->flags & EDGE_ABNORMAL)
1028     {
1029       /* Irritating special case - fallthru edge to the same block as abnormal
1030          edge.
1031          We can't redirect abnormal edge, but we still can split the fallthru
1032          one and create separate abnormal edge to original destination.
1033          This allows bb-reorder to make such edge non-fallthru.  */
1034       gcc_assert (e->dest == target);
1035       abnormal_edge_flags = e->flags & ~(EDGE_FALLTHRU | EDGE_CAN_FALLTHRU);
1036       e->flags &= EDGE_FALLTHRU | EDGE_CAN_FALLTHRU;
1037     }
1038   else
1039     {
1040       gcc_assert (e->flags & EDGE_FALLTHRU);
1041       if (e->src == ENTRY_BLOCK_PTR)
1042         {
1043           /* We can't redirect the entry block.  Create an empty block
1044              at the start of the function which we use to add the new
1045              jump.  */
1046           edge tmp;
1047           edge_iterator ei;
1048           bool found = false;
1049           
1050           basic_block bb = create_basic_block (BB_HEAD (e->dest), NULL, ENTRY_BLOCK_PTR);
1051           
1052           /* Change the existing edge's source to be the new block, and add
1053              a new edge from the entry block to the new block.  */
1054           e->src = bb;
1055           for (ei = ei_start (ENTRY_BLOCK_PTR->succs); (tmp = ei_safe_edge (ei)); )
1056             {
1057               if (tmp == e)
1058                 {
1059                   VEC_unordered_remove (edge, ENTRY_BLOCK_PTR->succs, ei.index);
1060                   found = true;
1061                   break;
1062                 }
1063               else
1064                 ei_next (&ei);
1065             }
1066           
1067           gcc_assert (found);
1068           
1069           VEC_safe_push (edge, bb->succs, e);
1070           make_single_succ_edge (ENTRY_BLOCK_PTR, bb, EDGE_FALLTHRU);
1071         }
1072     }
1073
1074   if (EDGE_COUNT (e->src->succs) >= 2 || abnormal_edge_flags)
1075     {
1076       /* Create the new structures.  */
1077
1078       /* If the old block ended with a tablejump, skip its table
1079          by searching forward from there.  Otherwise start searching
1080          forward from the last instruction of the old block.  */
1081       if (!tablejump_p (BB_END (e->src), NULL, &note))
1082         note = BB_END (e->src);
1083
1084       /* Position the new block correctly relative to loop notes.  */
1085       note = last_loop_beg_note (note);
1086       note = NEXT_INSN (note);
1087
1088       jump_block = create_basic_block (note, NULL, e->src);
1089       jump_block->count = e->count;
1090       jump_block->frequency = EDGE_FREQUENCY (e);
1091       jump_block->loop_depth = target->loop_depth;
1092
1093       if (target->global_live_at_start)
1094         {
1095           jump_block->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
1096           jump_block->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
1097           COPY_REG_SET (jump_block->global_live_at_start,
1098                         target->global_live_at_start);
1099           COPY_REG_SET (jump_block->global_live_at_end,
1100                         target->global_live_at_start);
1101         }
1102
1103       /* Make sure new block ends up in correct hot/cold section.  */
1104
1105       BB_COPY_PARTITION (jump_block, e->src);
1106       if (flag_reorder_blocks_and_partition
1107           && targetm.have_named_sections)
1108         {
1109           if (BB_PARTITION (jump_block) == BB_COLD_PARTITION)
1110             {
1111               rtx bb_note, new_note;
1112               for (bb_note = BB_HEAD (jump_block); 
1113                    bb_note && bb_note != NEXT_INSN (BB_END (jump_block));
1114                    bb_note = NEXT_INSN (bb_note))
1115                 if (NOTE_P (bb_note)
1116                     && NOTE_LINE_NUMBER (bb_note) == NOTE_INSN_BASIC_BLOCK)
1117                   break;
1118               new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
1119                                           bb_note);
1120               NOTE_BASIC_BLOCK (new_note) = jump_block; 
1121             }
1122           if (JUMP_P (BB_END (jump_block))
1123               && !any_condjump_p (BB_END (jump_block))
1124               && (EDGE_SUCC (jump_block, 0)->flags & EDGE_CROSSING))
1125             REG_NOTES (BB_END (jump_block)) = gen_rtx_EXPR_LIST 
1126               (REG_CROSSING_JUMP, NULL_RTX, 
1127                REG_NOTES (BB_END (jump_block)));
1128         }
1129
1130       /* Wire edge in.  */
1131       new_edge = make_edge (e->src, jump_block, EDGE_FALLTHRU);
1132       new_edge->probability = e->probability;
1133       new_edge->count = e->count;
1134
1135       /* Redirect old edge.  */
1136       redirect_edge_pred (e, jump_block);
1137       e->probability = REG_BR_PROB_BASE;
1138
1139       new_bb = jump_block;
1140     }
1141   else
1142     jump_block = e->src;
1143
1144   e->flags &= ~EDGE_FALLTHRU;
1145   if (target == EXIT_BLOCK_PTR)
1146     {
1147 #ifdef HAVE_return
1148         emit_jump_insn_after_noloc (gen_return (), BB_END (jump_block));
1149 #else
1150         gcc_unreachable ();
1151 #endif
1152     }
1153   else
1154     {
1155       rtx label = block_label (target);
1156       emit_jump_insn_after_noloc (gen_jump (label), BB_END (jump_block));
1157       JUMP_LABEL (BB_END (jump_block)) = label;
1158       LABEL_NUSES (label)++;
1159     }
1160
1161   emit_barrier_after (BB_END (jump_block));
1162   redirect_edge_succ_nodup (e, target);
1163
1164   if (abnormal_edge_flags)
1165     make_edge (src, target, abnormal_edge_flags);
1166
1167   return new_bb;
1168 }
1169
1170 /* Edge E is assumed to be fallthru edge.  Emit needed jump instruction
1171    (and possibly create new basic block) to make edge non-fallthru.
1172    Return newly created BB or NULL if none.  */
1173
1174 basic_block
1175 force_nonfallthru (edge e)
1176 {
1177   return force_nonfallthru_and_redirect (e, e->dest);
1178 }
1179
1180 /* Redirect edge even at the expense of creating new jump insn or
1181    basic block.  Return new basic block if created, NULL otherwise.
1182    Abort if conversion is impossible.  */
1183
1184 static basic_block
1185 rtl_redirect_edge_and_branch_force (edge e, basic_block target)
1186 {
1187   if (redirect_edge_and_branch (e, target)
1188       || e->dest == target)
1189     return NULL;
1190
1191   /* In case the edge redirection failed, try to force it to be non-fallthru
1192      and redirect newly created simplejump.  */
1193   return force_nonfallthru_and_redirect (e, target);
1194 }
1195
1196 /* The given edge should potentially be a fallthru edge.  If that is in
1197    fact true, delete the jump and barriers that are in the way.  */
1198
1199 static void
1200 rtl_tidy_fallthru_edge (edge e)
1201 {
1202   rtx q;
1203   basic_block b = e->src, c = b->next_bb;
1204
1205   /* ??? In a late-running flow pass, other folks may have deleted basic
1206      blocks by nopping out blocks, leaving multiple BARRIERs between here
1207      and the target label. They ought to be chastized and fixed.
1208
1209      We can also wind up with a sequence of undeletable labels between
1210      one block and the next.
1211
1212      So search through a sequence of barriers, labels, and notes for
1213      the head of block C and assert that we really do fall through.  */
1214
1215   for (q = NEXT_INSN (BB_END (b)); q != BB_HEAD (c); q = NEXT_INSN (q))
1216     if (INSN_P (q))
1217       return;
1218
1219   /* Remove what will soon cease being the jump insn from the source block.
1220      If block B consisted only of this single jump, turn it into a deleted
1221      note.  */
1222   q = BB_END (b);
1223   if (JUMP_P (q)
1224       && onlyjump_p (q)
1225       && (any_uncondjump_p (q)
1226           || EDGE_COUNT (b->succs) == 1))
1227     {
1228 #ifdef HAVE_cc0
1229       /* If this was a conditional jump, we need to also delete
1230          the insn that set cc0.  */
1231       if (any_condjump_p (q) && only_sets_cc0_p (PREV_INSN (q)))
1232         q = PREV_INSN (q);
1233 #endif
1234
1235       q = PREV_INSN (q);
1236
1237       /* We don't want a block to end on a line-number note since that has
1238          the potential of changing the code between -g and not -g.  */
1239       while (NOTE_P (q) && NOTE_LINE_NUMBER (q) >= 0)
1240         q = PREV_INSN (q);
1241     }
1242
1243   /* Selectively unlink the sequence.  */
1244   if (q != PREV_INSN (BB_HEAD (c)))
1245     delete_insn_chain (NEXT_INSN (q), PREV_INSN (BB_HEAD (c)));
1246
1247   e->flags |= EDGE_FALLTHRU;
1248 }
1249 \f
1250 /* Helper function for split_edge.  Return true in case edge BB2 to BB1
1251    is back edge of syntactic loop.  */
1252
1253 static bool
1254 back_edge_of_syntactic_loop_p (basic_block bb1, basic_block bb2)
1255 {
1256   rtx insn;
1257   int count = 0;
1258   basic_block bb;
1259
1260   if (bb1 == bb2)
1261     return true;
1262
1263   /* ??? Could we guarantee that bb indices are monotone, so that we could
1264      just compare them?  */
1265   for (bb = bb1; bb && bb != bb2; bb = bb->next_bb)
1266     continue;
1267
1268   if (!bb)
1269     return false;
1270
1271   for (insn = BB_END (bb1); insn != BB_HEAD (bb2) && count >= 0;
1272        insn = NEXT_INSN (insn))
1273     if (NOTE_P (insn))
1274       {
1275         if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1276           count++;
1277         else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1278           count--;
1279       }
1280
1281   return count >= 0;
1282 }
1283
1284 /* Should move basic block BB after basic block AFTER.  NIY.  */
1285
1286 static bool
1287 rtl_move_block_after (basic_block bb ATTRIBUTE_UNUSED,
1288                       basic_block after ATTRIBUTE_UNUSED)
1289 {
1290   return false;
1291 }
1292
1293 /* Split a (typically critical) edge.  Return the new block.
1294    Abort on abnormal edges.
1295
1296    ??? The code generally expects to be called on critical edges.
1297    The case of a block ending in an unconditional jump to a
1298    block with multiple predecessors is not handled optimally.  */
1299
1300 static basic_block
1301 rtl_split_edge (edge edge_in)
1302 {
1303   basic_block bb;
1304   rtx before;
1305
1306   /* Abnormal edges cannot be split.  */
1307   gcc_assert (!(edge_in->flags & EDGE_ABNORMAL));
1308
1309   /* We are going to place the new block in front of edge destination.
1310      Avoid existence of fallthru predecessors.  */
1311   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1312     {
1313       edge e;
1314       edge_iterator ei;
1315
1316       FOR_EACH_EDGE (e, ei, edge_in->dest->preds)
1317         if (e->flags & EDGE_FALLTHRU)
1318           break;
1319
1320       if (e)
1321         force_nonfallthru (e);
1322     }
1323
1324   /* Create the basic block note.
1325
1326      Where we place the note can have a noticeable impact on the generated
1327      code.  Consider this cfg:
1328
1329                         E
1330                         |
1331                         0
1332                        / \
1333                    +->1-->2--->E
1334                    |  |
1335                    +--+
1336
1337       If we need to insert an insn on the edge from block 0 to block 1,
1338       we want to ensure the instructions we insert are outside of any
1339       loop notes that physically sit between block 0 and block 1.  Otherwise
1340       we confuse the loop optimizer into thinking the loop is a phony.  */
1341
1342   if (edge_in->dest != EXIT_BLOCK_PTR
1343       && PREV_INSN (BB_HEAD (edge_in->dest))
1344       && NOTE_P (PREV_INSN (BB_HEAD (edge_in->dest)))
1345       && (NOTE_LINE_NUMBER (PREV_INSN (BB_HEAD (edge_in->dest)))
1346           == NOTE_INSN_LOOP_BEG)
1347       && !back_edge_of_syntactic_loop_p (edge_in->dest, edge_in->src))
1348     before = PREV_INSN (BB_HEAD (edge_in->dest));
1349   else if (edge_in->dest != EXIT_BLOCK_PTR)
1350     before = BB_HEAD (edge_in->dest);
1351   else
1352     before = NULL_RTX;
1353
1354   /* If this is a fall through edge to the exit block, the blocks might be
1355      not adjacent, and the right place is the after the source.  */
1356   if (edge_in->flags & EDGE_FALLTHRU && edge_in->dest == EXIT_BLOCK_PTR)
1357     {
1358       before = NEXT_INSN (BB_END (edge_in->src));
1359       if (before
1360           && NOTE_P (before)
1361           && NOTE_LINE_NUMBER (before) == NOTE_INSN_LOOP_END)
1362         before = NEXT_INSN (before);
1363       bb = create_basic_block (before, NULL, edge_in->src);
1364       BB_COPY_PARTITION (bb, edge_in->src);
1365     }
1366   else
1367     {
1368       bb = create_basic_block (before, NULL, edge_in->dest->prev_bb);
1369       /* ??? Why not edge_in->dest->prev_bb here?  */
1370       BB_COPY_PARTITION (bb, edge_in->dest);
1371     }
1372
1373   /* ??? This info is likely going to be out of date very soon.  */
1374   if (edge_in->dest->global_live_at_start)
1375     {
1376       bb->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
1377       bb->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
1378       COPY_REG_SET (bb->global_live_at_start,
1379                     edge_in->dest->global_live_at_start);
1380       COPY_REG_SET (bb->global_live_at_end,
1381                     edge_in->dest->global_live_at_start);
1382     }
1383
1384   make_single_succ_edge (bb, edge_in->dest, EDGE_FALLTHRU);
1385
1386   /* For non-fallthru edges, we must adjust the predecessor's
1387      jump instruction to target our new block.  */
1388   if ((edge_in->flags & EDGE_FALLTHRU) == 0)
1389     {
1390       edge redirected = redirect_edge_and_branch (edge_in, bb);
1391       gcc_assert (redirected);
1392     }
1393   else
1394     redirect_edge_succ (edge_in, bb);
1395
1396   return bb;
1397 }
1398
1399 /* Queue instructions for insertion on an edge between two basic blocks.
1400    The new instructions and basic blocks (if any) will not appear in the
1401    CFG until commit_edge_insertions is called.  */
1402
1403 void
1404 insert_insn_on_edge (rtx pattern, edge e)
1405 {
1406   /* We cannot insert instructions on an abnormal critical edge.
1407      It will be easier to find the culprit if we die now.  */
1408   gcc_assert (!((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)));
1409
1410   if (e->insns.r == NULL_RTX)
1411     start_sequence ();
1412   else
1413     push_to_sequence (e->insns.r);
1414
1415   emit_insn (pattern);
1416
1417   e->insns.r = get_insns ();
1418   end_sequence ();
1419 }
1420
1421 /* Called from safe_insert_insn_on_edge through note_stores, marks live
1422    registers that are killed by the store.  */
1423 static void
1424 mark_killed_regs (rtx reg, rtx set ATTRIBUTE_UNUSED, void *data)
1425 {
1426   regset killed = data;
1427   int regno, i;
1428
1429   if (GET_CODE (reg) == SUBREG)
1430     reg = SUBREG_REG (reg);
1431   if (!REG_P (reg))
1432     return;
1433   regno = REGNO (reg);
1434   if (regno >= FIRST_PSEUDO_REGISTER)
1435     SET_REGNO_REG_SET (killed, regno);
1436   else
1437     {
1438       for (i = 0; i < (int) hard_regno_nregs[regno][GET_MODE (reg)]; i++)
1439         SET_REGNO_REG_SET (killed, regno + i);
1440     }
1441 }
1442
1443 /* Similar to insert_insn_on_edge, tries to put INSN to edge E.  Additionally
1444    it checks whether this will not clobber the registers that are live on the
1445    edge (i.e. it requires liveness information to be up-to-date) and if there
1446    are some, then it tries to save and restore them.  Returns true if
1447    successful.  */
1448 bool
1449 safe_insert_insn_on_edge (rtx insn, edge e)
1450 {
1451   rtx x;
1452   regset killed;
1453   rtx save_regs = NULL_RTX;
1454   unsigned regno;
1455   int noccmode;
1456   enum machine_mode mode;
1457   reg_set_iterator rsi;
1458
1459 #ifdef AVOID_CCMODE_COPIES
1460   noccmode = true;
1461 #else
1462   noccmode = false;
1463 #endif
1464
1465   killed = ALLOC_REG_SET (&reg_obstack);
1466
1467   for (x = insn; x; x = NEXT_INSN (x))
1468     if (INSN_P (x))
1469       note_stores (PATTERN (x), mark_killed_regs, killed);
1470   bitmap_and_into (killed, e->dest->global_live_at_start);
1471
1472   EXECUTE_IF_SET_IN_REG_SET (killed, 0, regno, rsi)
1473     {
1474       mode = regno < FIRST_PSEUDO_REGISTER
1475               ? reg_raw_mode[regno]
1476               : GET_MODE (regno_reg_rtx[regno]);
1477       if (mode == VOIDmode)
1478         return false;
1479
1480       if (noccmode && mode == CCmode)
1481         return false;
1482         
1483       save_regs = alloc_EXPR_LIST (0,
1484                                    alloc_EXPR_LIST (0,
1485                                                     gen_reg_rtx (mode),
1486                                                     gen_raw_REG (mode, regno)),
1487                                    save_regs);
1488     }
1489
1490   if (save_regs)
1491     {
1492       rtx from, to;
1493
1494       start_sequence ();
1495       for (x = save_regs; x; x = XEXP (x, 1))
1496         {
1497           from = XEXP (XEXP (x, 0), 1);
1498           to = XEXP (XEXP (x, 0), 0);
1499           emit_move_insn (to, from);
1500         }
1501       emit_insn (insn);
1502       for (x = save_regs; x; x = XEXP (x, 1))
1503         {
1504           from = XEXP (XEXP (x, 0), 0);
1505           to = XEXP (XEXP (x, 0), 1);
1506           emit_move_insn (to, from);
1507         }
1508       insn = get_insns ();
1509       end_sequence ();
1510       free_EXPR_LIST_list (&save_regs);
1511     }
1512   insert_insn_on_edge (insn, e);
1513   
1514   FREE_REG_SET (killed);
1515   return true;
1516 }
1517
1518 /* Update the CFG for the instructions queued on edge E.  */
1519
1520 static void
1521 commit_one_edge_insertion (edge e, int watch_calls)
1522 {
1523   rtx before = NULL_RTX, after = NULL_RTX, insns, tmp, last;
1524   basic_block bb = NULL;
1525
1526   /* Pull the insns off the edge now since the edge might go away.  */
1527   insns = e->insns.r;
1528   e->insns.r = NULL_RTX;
1529
1530   /* Special case -- avoid inserting code between call and storing
1531      its return value.  */
1532   if (watch_calls && (e->flags & EDGE_FALLTHRU)
1533       && EDGE_COUNT (e->dest->preds) == 1
1534       && e->src != ENTRY_BLOCK_PTR
1535       && CALL_P (BB_END (e->src)))
1536     {
1537       rtx next = next_nonnote_insn (BB_END (e->src));
1538
1539       after = BB_HEAD (e->dest);
1540       /* The first insn after the call may be a stack pop, skip it.  */
1541       while (next
1542              && keep_with_call_p (next))
1543         {
1544           after = next;
1545           next = next_nonnote_insn (next);
1546         }
1547       bb = e->dest;
1548     }
1549   if (!before && !after)
1550     {
1551       /* Figure out where to put these things.  If the destination has
1552          one predecessor, insert there.  Except for the exit block.  */
1553       if (EDGE_COUNT (e->dest->preds) == 1 && e->dest != EXIT_BLOCK_PTR)
1554         {
1555           bb = e->dest;
1556
1557           /* Get the location correct wrt a code label, and "nice" wrt
1558              a basic block note, and before everything else.  */
1559           tmp = BB_HEAD (bb);
1560           if (LABEL_P (tmp))
1561             tmp = NEXT_INSN (tmp);
1562           if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1563             tmp = NEXT_INSN (tmp);
1564           if (tmp 
1565               && NOTE_P (tmp)
1566               && NOTE_LINE_NUMBER (tmp) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
1567             tmp = NEXT_INSN (tmp);
1568           if (tmp == BB_HEAD (bb))
1569             before = tmp;
1570           else if (tmp)
1571             after = PREV_INSN (tmp);
1572           else
1573             after = get_last_insn ();
1574         }
1575
1576       /* If the source has one successor and the edge is not abnormal,
1577          insert there.  Except for the entry block.  */
1578       else if ((e->flags & EDGE_ABNORMAL) == 0
1579                && EDGE_COUNT (e->src->succs) == 1
1580                && e->src != ENTRY_BLOCK_PTR)
1581         {
1582           bb = e->src;
1583
1584           /* It is possible to have a non-simple jump here.  Consider a target
1585              where some forms of unconditional jumps clobber a register.  This
1586              happens on the fr30 for example.
1587
1588              We know this block has a single successor, so we can just emit
1589              the queued insns before the jump.  */
1590           if (JUMP_P (BB_END (bb)))
1591             for (before = BB_END (bb);
1592                  NOTE_P (PREV_INSN (before))
1593                  && NOTE_LINE_NUMBER (PREV_INSN (before)) ==
1594                  NOTE_INSN_LOOP_BEG; before = PREV_INSN (before))
1595               ;
1596           else
1597             {
1598               /* We'd better be fallthru, or we've lost track of
1599                  what's what.  */
1600               gcc_assert (e->flags & EDGE_FALLTHRU);
1601
1602               after = BB_END (bb);
1603             }
1604         }
1605       /* Otherwise we must split the edge.  */
1606       else
1607         {
1608           bb = split_edge (e);
1609           after = BB_END (bb);
1610
1611           if (flag_reorder_blocks_and_partition
1612               && targetm.have_named_sections
1613               && e->src != ENTRY_BLOCK_PTR
1614               && BB_PARTITION (e->src) == BB_COLD_PARTITION
1615               && !(e->flags & EDGE_CROSSING))
1616             {
1617               rtx bb_note, new_note, cur_insn;
1618
1619               bb_note = NULL_RTX;
1620               for (cur_insn = BB_HEAD (bb); cur_insn != NEXT_INSN (BB_END (bb));
1621                    cur_insn = NEXT_INSN (cur_insn))
1622                 if (NOTE_P (cur_insn)
1623                     && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_BASIC_BLOCK)
1624                   {
1625                     bb_note = cur_insn;
1626                     break;
1627                   }
1628
1629               new_note = emit_note_after (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
1630                                           bb_note);
1631               NOTE_BASIC_BLOCK (new_note) = bb;
1632               if (JUMP_P (BB_END (bb))
1633                   && !any_condjump_p (BB_END (bb))
1634                   && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
1635                 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST 
1636                   (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
1637               if (after == bb_note)
1638                 after = new_note;
1639             }
1640         }
1641     }
1642
1643   /* Now that we've found the spot, do the insertion.  */
1644
1645   if (before)
1646     {
1647       emit_insn_before_noloc (insns, before);
1648       last = prev_nonnote_insn (before);
1649     }
1650   else
1651     last = emit_insn_after_noloc (insns, after);
1652
1653   if (returnjump_p (last))
1654     {
1655       /* ??? Remove all outgoing edges from BB and add one for EXIT.
1656          This is not currently a problem because this only happens
1657          for the (single) epilogue, which already has a fallthru edge
1658          to EXIT.  */
1659
1660       e = EDGE_SUCC (bb, 0);
1661       gcc_assert (e->dest == EXIT_BLOCK_PTR
1662                   && EDGE_COUNT (bb->succs) == 1 && (e->flags & EDGE_FALLTHRU));
1663
1664       e->flags &= ~EDGE_FALLTHRU;
1665       emit_barrier_after (last);
1666
1667       if (before)
1668         delete_insn (before);
1669     }
1670   else
1671     gcc_assert (!JUMP_P (last));
1672
1673   /* Mark the basic block for find_sub_basic_blocks.  */
1674   bb->aux = &bb->aux;
1675 }
1676
1677 /* Update the CFG for all queued instructions.  */
1678
1679 void
1680 commit_edge_insertions (void)
1681 {
1682   basic_block bb;
1683   sbitmap blocks;
1684   bool changed = false;
1685
1686 #ifdef ENABLE_CHECKING
1687   verify_flow_info ();
1688 #endif
1689
1690   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1691     {
1692       edge e;
1693       edge_iterator ei;
1694
1695       FOR_EACH_EDGE (e, ei, bb->succs)
1696         if (e->insns.r)
1697           {
1698             changed = true;
1699             commit_one_edge_insertion (e, false);
1700           }
1701     }
1702
1703   if (!changed)
1704     return;
1705
1706   blocks = sbitmap_alloc (last_basic_block);
1707   sbitmap_zero (blocks);
1708   FOR_EACH_BB (bb)
1709     if (bb->aux)
1710       {
1711         SET_BIT (blocks, bb->index);
1712         /* Check for forgotten bb->aux values before commit_edge_insertions
1713            call.  */
1714         gcc_assert (bb->aux == &bb->aux);
1715         bb->aux = NULL;
1716       }
1717   find_many_sub_basic_blocks (blocks);
1718   sbitmap_free (blocks);
1719 }
1720 \f
1721 /* Update the CFG for all queued instructions, taking special care of inserting
1722    code on edges between call and storing its return value.  */
1723
1724 void
1725 commit_edge_insertions_watch_calls (void)
1726 {
1727   basic_block bb;
1728   sbitmap blocks;
1729   bool changed = false;
1730
1731 #ifdef ENABLE_CHECKING
1732   verify_flow_info ();
1733 #endif
1734
1735   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, EXIT_BLOCK_PTR, next_bb)
1736     {
1737       edge e;
1738       edge_iterator ei;
1739
1740       FOR_EACH_EDGE (e, ei, bb->succs)
1741         if (e->insns.r)
1742           {
1743             changed = true;
1744             commit_one_edge_insertion (e, true);
1745           }
1746     }
1747
1748   if (!changed)
1749     return;
1750
1751   blocks = sbitmap_alloc (last_basic_block);
1752   sbitmap_zero (blocks);
1753   FOR_EACH_BB (bb)
1754     if (bb->aux)
1755       {
1756         SET_BIT (blocks, bb->index);
1757         /* Check for forgotten bb->aux values before commit_edge_insertions
1758            call.  */
1759         gcc_assert (bb->aux == &bb->aux);
1760         bb->aux = NULL;
1761       }
1762   find_many_sub_basic_blocks (blocks);
1763   sbitmap_free (blocks);
1764 }
1765 \f
1766 /* Print out RTL-specific basic block information (live information
1767    at start and end).  */
1768
1769 static void
1770 rtl_dump_bb (basic_block bb, FILE *outf, int indent)
1771 {
1772   rtx insn;
1773   rtx last;
1774   char *s_indent;
1775
1776   s_indent = alloca ((size_t) indent + 1);
1777   memset (s_indent, ' ', (size_t) indent);
1778   s_indent[indent] = '\0';
1779
1780   fprintf (outf, ";;%s Registers live at start: ", s_indent);
1781   dump_regset (bb->global_live_at_start, outf);
1782   putc ('\n', outf);
1783
1784   for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb)); insn != last;
1785        insn = NEXT_INSN (insn))
1786     print_rtl_single (outf, insn);
1787
1788   fprintf (outf, ";;%s Registers live at end: ", s_indent);
1789   dump_regset (bb->global_live_at_end, outf);
1790   putc ('\n', outf);
1791 }
1792 \f
1793 /* Like print_rtl, but also print out live information for the start of each
1794    basic block.  */
1795
1796 void
1797 print_rtl_with_bb (FILE *outf, rtx rtx_first)
1798 {
1799   rtx tmp_rtx;
1800
1801   if (rtx_first == 0)
1802     fprintf (outf, "(nil)\n");
1803   else
1804     {
1805       enum bb_state { NOT_IN_BB, IN_ONE_BB, IN_MULTIPLE_BB };
1806       int max_uid = get_max_uid ();
1807       basic_block *start = xcalloc (max_uid, sizeof (basic_block));
1808       basic_block *end = xcalloc (max_uid, sizeof (basic_block));
1809       enum bb_state *in_bb_p = xcalloc (max_uid, sizeof (enum bb_state));
1810
1811       basic_block bb;
1812
1813       FOR_EACH_BB_REVERSE (bb)
1814         {
1815           rtx x;
1816
1817           start[INSN_UID (BB_HEAD (bb))] = bb;
1818           end[INSN_UID (BB_END (bb))] = bb;
1819           for (x = BB_HEAD (bb); x != NULL_RTX; x = NEXT_INSN (x))
1820             {
1821               enum bb_state state = IN_MULTIPLE_BB;
1822
1823               if (in_bb_p[INSN_UID (x)] == NOT_IN_BB)
1824                 state = IN_ONE_BB;
1825               in_bb_p[INSN_UID (x)] = state;
1826
1827               if (x == BB_END (bb))
1828                 break;
1829             }
1830         }
1831
1832       for (tmp_rtx = rtx_first; NULL != tmp_rtx; tmp_rtx = NEXT_INSN (tmp_rtx))
1833         {
1834           int did_output;
1835
1836           if ((bb = start[INSN_UID (tmp_rtx)]) != NULL)
1837             {
1838               fprintf (outf, ";; Start of basic block %d, registers live:",
1839                        bb->index);
1840               dump_regset (bb->global_live_at_start, outf);
1841               putc ('\n', outf);
1842             }
1843
1844           if (in_bb_p[INSN_UID (tmp_rtx)] == NOT_IN_BB
1845               && !NOTE_P (tmp_rtx)
1846               && !BARRIER_P (tmp_rtx))
1847             fprintf (outf, ";; Insn is not within a basic block\n");
1848           else if (in_bb_p[INSN_UID (tmp_rtx)] == IN_MULTIPLE_BB)
1849             fprintf (outf, ";; Insn is in multiple basic blocks\n");
1850
1851           did_output = print_rtl_single (outf, tmp_rtx);
1852
1853           if ((bb = end[INSN_UID (tmp_rtx)]) != NULL)
1854             {
1855               fprintf (outf, ";; End of basic block %d, registers live:\n",
1856                        bb->index);
1857               dump_regset (bb->global_live_at_end, outf);
1858               putc ('\n', outf);
1859             }
1860
1861           if (did_output)
1862             putc ('\n', outf);
1863         }
1864
1865       free (start);
1866       free (end);
1867       free (in_bb_p);
1868     }
1869
1870   if (current_function_epilogue_delay_list != 0)
1871     {
1872       fprintf (outf, "\n;; Insns in epilogue delay list:\n\n");
1873       for (tmp_rtx = current_function_epilogue_delay_list; tmp_rtx != 0;
1874            tmp_rtx = XEXP (tmp_rtx, 1))
1875         print_rtl_single (outf, XEXP (tmp_rtx, 0));
1876     }
1877 }
1878 \f
1879 void
1880 update_br_prob_note (basic_block bb)
1881 {
1882   rtx note;
1883   if (!JUMP_P (BB_END (bb)))
1884     return;
1885   note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
1886   if (!note || INTVAL (XEXP (note, 0)) == BRANCH_EDGE (bb)->probability)
1887     return;
1888   XEXP (note, 0) = GEN_INT (BRANCH_EDGE (bb)->probability);
1889 }
1890 \f
1891 /* Verify the CFG and RTL consistency common for both underlying RTL and
1892    cfglayout RTL.
1893
1894    Currently it does following checks:
1895
1896    - test head/end pointers
1897    - overlapping of basic blocks
1898    - headers of basic blocks (the NOTE_INSN_BASIC_BLOCK note)
1899    - tails of basic blocks (ensure that boundary is necessary)
1900    - scans body of the basic block for JUMP_INSN, CODE_LABEL
1901      and NOTE_INSN_BASIC_BLOCK
1902    - verify that no fall_thru edge crosses hot/cold partition boundaries
1903
1904    In future it can be extended check a lot of other stuff as well
1905    (reachability of basic blocks, life information, etc. etc.).  */
1906
1907 static int
1908 rtl_verify_flow_info_1 (void)
1909 {
1910   const int max_uid = get_max_uid ();
1911   rtx last_head = get_last_insn ();
1912   basic_block *bb_info;
1913   rtx x;
1914   int err = 0;
1915   basic_block bb, last_bb_seen;
1916
1917   bb_info = xcalloc (max_uid, sizeof (basic_block));
1918
1919   /* Check bb chain & numbers.  */
1920   last_bb_seen = ENTRY_BLOCK_PTR;
1921
1922   FOR_EACH_BB_REVERSE (bb)
1923     {
1924       rtx head = BB_HEAD (bb);
1925       rtx end = BB_END (bb);
1926
1927       /* Verify the end of the basic block is in the INSN chain.  */
1928       for (x = last_head; x != NULL_RTX; x = PREV_INSN (x))
1929         if (x == end)
1930           break;
1931
1932       if (!x)
1933         {
1934           error ("end insn %d for block %d not found in the insn stream",
1935                  INSN_UID (end), bb->index);
1936           err = 1;
1937         }
1938
1939       /* Work backwards from the end to the head of the basic block
1940          to verify the head is in the RTL chain.  */
1941       for (; x != NULL_RTX; x = PREV_INSN (x))
1942         {
1943           /* While walking over the insn chain, verify insns appear
1944              in only one basic block and initialize the BB_INFO array
1945              used by other passes.  */
1946           if (bb_info[INSN_UID (x)] != NULL)
1947             {
1948               error ("insn %d is in multiple basic blocks (%d and %d)",
1949                      INSN_UID (x), bb->index, bb_info[INSN_UID (x)]->index);
1950               err = 1;
1951             }
1952
1953           bb_info[INSN_UID (x)] = bb;
1954
1955           if (x == head)
1956             break;
1957         }
1958       if (!x)
1959         {
1960           error ("head insn %d for block %d not found in the insn stream",
1961                  INSN_UID (head), bb->index);
1962           err = 1;
1963         }
1964
1965       last_head = x;
1966     }
1967
1968   /* Now check the basic blocks (boundaries etc.) */
1969   FOR_EACH_BB_REVERSE (bb)
1970     {
1971       int n_fallthru = 0, n_eh = 0, n_call = 0, n_abnormal = 0, n_branch = 0;
1972       edge e, fallthru = NULL;
1973       rtx note;
1974       edge_iterator ei;
1975
1976       if (INSN_P (BB_END (bb))
1977           && (note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX))
1978           && EDGE_COUNT (bb->succs) >= 2
1979           && any_condjump_p (BB_END (bb)))
1980         {
1981           if (INTVAL (XEXP (note, 0)) != BRANCH_EDGE (bb)->probability
1982               && profile_status != PROFILE_ABSENT)
1983             {
1984               error ("verify_flow_info: REG_BR_PROB does not match cfg %wi %i",
1985                      INTVAL (XEXP (note, 0)), BRANCH_EDGE (bb)->probability);
1986               err = 1;
1987             }
1988         }
1989       FOR_EACH_EDGE (e, ei, bb->succs)
1990         {
1991           if (e->flags & EDGE_FALLTHRU)
1992             {
1993               n_fallthru++, fallthru = e;
1994               if ((e->flags & EDGE_CROSSING)
1995                   || (BB_PARTITION (e->src) != BB_PARTITION (e->dest)
1996                       && e->src != ENTRY_BLOCK_PTR
1997                       && e->dest != EXIT_BLOCK_PTR))
1998             { 
1999                   error ("Fallthru edge crosses section boundary (bb %i)",
2000                          e->src->index);
2001                   err = 1;
2002                 }
2003             }
2004
2005           if ((e->flags & ~(EDGE_DFS_BACK
2006                             | EDGE_CAN_FALLTHRU
2007                             | EDGE_IRREDUCIBLE_LOOP
2008                             | EDGE_LOOP_EXIT
2009                             | EDGE_CROSSING)) == 0)
2010             n_branch++;
2011
2012           if (e->flags & EDGE_ABNORMAL_CALL)
2013             n_call++;
2014
2015           if (e->flags & EDGE_EH)
2016             n_eh++;
2017           else if (e->flags & EDGE_ABNORMAL)
2018             n_abnormal++;
2019         }
2020
2021       if (n_eh && GET_CODE (PATTERN (BB_END (bb))) != RESX
2022           && !find_reg_note (BB_END (bb), REG_EH_REGION, NULL_RTX))
2023         {
2024           error ("Missing REG_EH_REGION note in the end of bb %i", bb->index);
2025           err = 1;
2026         }
2027       if (n_branch
2028           && (!JUMP_P (BB_END (bb))
2029               || (n_branch > 1 && (any_uncondjump_p (BB_END (bb))
2030                                    || any_condjump_p (BB_END (bb))))))
2031         {
2032           error ("Too many outgoing branch edges from bb %i", bb->index);
2033           err = 1;
2034         }
2035       if (n_fallthru && any_uncondjump_p (BB_END (bb)))
2036         {
2037           error ("Fallthru edge after unconditional jump %i", bb->index);
2038           err = 1;
2039         }
2040       if (n_branch != 1 && any_uncondjump_p (BB_END (bb)))
2041         {
2042           error ("Wrong amount of branch edges after unconditional jump %i", bb->index);
2043           err = 1;
2044         }
2045       if (n_branch != 1 && any_condjump_p (BB_END (bb))
2046           && JUMP_LABEL (BB_END (bb)) != BB_HEAD (fallthru->dest))
2047         {
2048           error ("Wrong amount of branch edges after conditional jump %i", bb->index);
2049           err = 1;
2050         }
2051       if (n_call && !CALL_P (BB_END (bb)))
2052         {
2053           error ("Call edges for non-call insn in bb %i", bb->index);
2054           err = 1;
2055         }
2056       if (n_abnormal
2057           && (!CALL_P (BB_END (bb)) && n_call != n_abnormal)
2058           && (!JUMP_P (BB_END (bb))
2059               || any_condjump_p (BB_END (bb))
2060               || any_uncondjump_p (BB_END (bb))))
2061         {
2062           error ("Abnormal edges for no purpose in bb %i", bb->index);
2063           err = 1;
2064         }
2065
2066       for (x = BB_HEAD (bb); x != NEXT_INSN (BB_END (bb)); x = NEXT_INSN (x))
2067         /* We may have a barrier inside a basic block before dead code
2068            elimination.  There is no BLOCK_FOR_INSN field in a barrier.  */
2069         if (!BARRIER_P (x) && BLOCK_FOR_INSN (x) != bb)
2070           {
2071             debug_rtx (x);
2072             if (! BLOCK_FOR_INSN (x))
2073               error
2074                 ("insn %d inside basic block %d but block_for_insn is NULL",
2075                  INSN_UID (x), bb->index);
2076             else
2077               error
2078                 ("insn %d inside basic block %d but block_for_insn is %i",
2079                  INSN_UID (x), bb->index, BLOCK_FOR_INSN (x)->index);
2080
2081             err = 1;
2082           }
2083
2084       /* OK pointers are correct.  Now check the header of basic
2085          block.  It ought to contain optional CODE_LABEL followed
2086          by NOTE_BASIC_BLOCK.  */
2087       x = BB_HEAD (bb);
2088       if (LABEL_P (x))
2089         {
2090           if (BB_END (bb) == x)
2091             {
2092               error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2093                      bb->index);
2094               err = 1;
2095             }
2096
2097           x = NEXT_INSN (x);
2098         }
2099
2100       if (!NOTE_INSN_BASIC_BLOCK_P (x) || NOTE_BASIC_BLOCK (x) != bb)
2101         {
2102           error ("NOTE_INSN_BASIC_BLOCK is missing for block %d",
2103                  bb->index);
2104           err = 1;
2105         }
2106
2107       if (BB_END (bb) == x)
2108         /* Do checks for empty blocks here.  */
2109         ;
2110       else
2111         for (x = NEXT_INSN (x); x; x = NEXT_INSN (x))
2112           {
2113             if (NOTE_INSN_BASIC_BLOCK_P (x))
2114               {
2115                 error ("NOTE_INSN_BASIC_BLOCK %d in middle of basic block %d",
2116                        INSN_UID (x), bb->index);
2117                 err = 1;
2118               }
2119
2120             if (x == BB_END (bb))
2121               break;
2122
2123             if (control_flow_insn_p (x))
2124               {
2125                 error ("in basic block %d:", bb->index);
2126                 fatal_insn ("flow control insn inside a basic block", x);
2127               }
2128           }
2129     }
2130
2131   /* Clean up.  */
2132   free (bb_info);
2133   return err;
2134 }
2135
2136 /* Verify the CFG and RTL consistency common for both underlying RTL and
2137    cfglayout RTL.
2138
2139    Currently it does following checks:
2140    - all checks of rtl_verify_flow_info_1
2141    - check that all insns are in the basic blocks
2142      (except the switch handling code, barriers and notes)
2143    - check that all returns are followed by barriers
2144    - check that all fallthru edge points to the adjacent blocks.  */
2145 static int
2146 rtl_verify_flow_info (void)
2147 {
2148   basic_block bb;
2149   int err = rtl_verify_flow_info_1 ();
2150   rtx x;
2151   int num_bb_notes;
2152   const rtx rtx_first = get_insns ();
2153   basic_block last_bb_seen = ENTRY_BLOCK_PTR, curr_bb = NULL;
2154
2155   FOR_EACH_BB_REVERSE (bb)
2156     {
2157       edge e;
2158       edge_iterator ei;
2159
2160       FOR_EACH_EDGE (e, ei, bb->succs)
2161         if (e->flags & EDGE_FALLTHRU)
2162           break;
2163       if (!e)
2164         {
2165           rtx insn;
2166
2167           /* Ensure existence of barrier in BB with no fallthru edges.  */
2168           for (insn = BB_END (bb); !insn || !BARRIER_P (insn);
2169                insn = NEXT_INSN (insn))
2170             if (!insn
2171                 || (NOTE_P (insn)
2172                     && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BASIC_BLOCK))
2173                 {
2174                   error ("missing barrier after block %i", bb->index);
2175                   err = 1;
2176                   break;
2177                 }
2178         }
2179       else if (e->src != ENTRY_BLOCK_PTR
2180                && e->dest != EXIT_BLOCK_PTR)
2181         {
2182           rtx insn;
2183
2184           if (e->src->next_bb != e->dest)
2185             {
2186               error
2187                 ("verify_flow_info: Incorrect blocks for fallthru %i->%i",
2188                  e->src->index, e->dest->index);
2189               err = 1;
2190             }
2191           else
2192             for (insn = NEXT_INSN (BB_END (e->src)); insn != BB_HEAD (e->dest);
2193                  insn = NEXT_INSN (insn))
2194               if (BARRIER_P (insn) || INSN_P (insn))
2195                 {
2196                   error ("verify_flow_info: Incorrect fallthru %i->%i",
2197                          e->src->index, e->dest->index);
2198                   fatal_insn ("wrong insn in the fallthru edge", insn);
2199                   err = 1;
2200                 }
2201         }
2202     }
2203
2204   num_bb_notes = 0;
2205   last_bb_seen = ENTRY_BLOCK_PTR;
2206
2207   for (x = rtx_first; x; x = NEXT_INSN (x))
2208     {
2209       if (NOTE_INSN_BASIC_BLOCK_P (x))
2210         {
2211           bb = NOTE_BASIC_BLOCK (x);
2212
2213           num_bb_notes++;
2214           if (bb != last_bb_seen->next_bb)
2215             internal_error ("basic blocks not laid down consecutively");
2216
2217           curr_bb = last_bb_seen = bb;
2218         }
2219
2220       if (!curr_bb)
2221         {
2222           switch (GET_CODE (x))
2223             {
2224             case BARRIER:
2225             case NOTE:
2226               break;
2227
2228             case CODE_LABEL:
2229               /* An addr_vec is placed outside any basic block.  */
2230               if (NEXT_INSN (x)
2231                   && JUMP_P (NEXT_INSN (x))
2232                   && (GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_DIFF_VEC
2233                       || GET_CODE (PATTERN (NEXT_INSN (x))) == ADDR_VEC))
2234                 x = NEXT_INSN (x);
2235
2236               /* But in any case, non-deletable labels can appear anywhere.  */
2237               break;
2238
2239             default:
2240               fatal_insn ("insn outside basic block", x);
2241             }
2242         }
2243
2244       if (JUMP_P (x)
2245           && returnjump_p (x) && ! condjump_p (x)
2246           && ! (NEXT_INSN (x) && BARRIER_P (NEXT_INSN (x))))
2247             fatal_insn ("return not followed by barrier", x);
2248       if (curr_bb && x == BB_END (curr_bb))
2249         curr_bb = NULL;
2250     }
2251
2252   if (num_bb_notes != n_basic_blocks)
2253     internal_error
2254       ("number of bb notes in insn chain (%d) != n_basic_blocks (%d)",
2255        num_bb_notes, n_basic_blocks);
2256
2257    return err;
2258 }
2259 \f
2260 /* Assume that the preceding pass has possibly eliminated jump instructions
2261    or converted the unconditional jumps.  Eliminate the edges from CFG.
2262    Return true if any edges are eliminated.  */
2263
2264 bool
2265 purge_dead_edges (basic_block bb)
2266 {
2267   edge e;
2268   rtx insn = BB_END (bb), note;
2269   bool purged = false;
2270   bool found;
2271   edge_iterator ei;
2272
2273   /* If this instruction cannot trap, remove REG_EH_REGION notes.  */
2274   if (NONJUMP_INSN_P (insn)
2275       && (note = find_reg_note (insn, REG_EH_REGION, NULL)))
2276     {
2277       rtx eqnote;
2278
2279       if (! may_trap_p (PATTERN (insn))
2280           || ((eqnote = find_reg_equal_equiv_note (insn))
2281               && ! may_trap_p (XEXP (eqnote, 0))))
2282         remove_note (insn, note);
2283     }
2284
2285   /* Cleanup abnormal edges caused by exceptions or non-local gotos.  */
2286   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2287     {
2288       if (e->flags & EDGE_EH)
2289         {
2290           if (can_throw_internal (BB_END (bb)))
2291             {
2292               ei_next (&ei);
2293               continue;
2294             }
2295         }
2296       else if (e->flags & EDGE_ABNORMAL_CALL)
2297         {
2298           if (CALL_P (BB_END (bb))
2299               && (! (note = find_reg_note (insn, REG_EH_REGION, NULL))
2300                   || INTVAL (XEXP (note, 0)) >= 0))
2301             {
2302               ei_next (&ei);
2303               continue;
2304             }
2305         }
2306       else
2307         {
2308           ei_next (&ei);
2309           continue;
2310         }
2311
2312       remove_edge (e);
2313       bb->flags |= BB_DIRTY;
2314       purged = true;
2315     }
2316
2317   if (JUMP_P (insn))
2318     {
2319       rtx note;
2320       edge b,f;
2321       edge_iterator ei;
2322
2323       /* We do care only about conditional jumps and simplejumps.  */
2324       if (!any_condjump_p (insn)
2325           && !returnjump_p (insn)
2326           && !simplejump_p (insn))
2327         return purged;
2328
2329       /* Branch probability/prediction notes are defined only for
2330          condjumps.  We've possibly turned condjump into simplejump.  */
2331       if (simplejump_p (insn))
2332         {
2333           note = find_reg_note (insn, REG_BR_PROB, NULL);
2334           if (note)
2335             remove_note (insn, note);
2336           while ((note = find_reg_note (insn, REG_BR_PRED, NULL)))
2337             remove_note (insn, note);
2338         }
2339
2340       for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2341         {
2342           /* Avoid abnormal flags to leak from computed jumps turned
2343              into simplejumps.  */
2344
2345           e->flags &= ~EDGE_ABNORMAL;
2346
2347           /* See if this edge is one we should keep.  */
2348           if ((e->flags & EDGE_FALLTHRU) && any_condjump_p (insn))
2349             /* A conditional jump can fall through into the next
2350                block, so we should keep the edge.  */
2351             {
2352               ei_next (&ei);
2353               continue;
2354             }
2355           else if (e->dest != EXIT_BLOCK_PTR
2356                    && BB_HEAD (e->dest) == JUMP_LABEL (insn))
2357             /* If the destination block is the target of the jump,
2358                keep the edge.  */
2359             {
2360               ei_next (&ei);
2361               continue;
2362             }
2363           else if (e->dest == EXIT_BLOCK_PTR && returnjump_p (insn))
2364             /* If the destination block is the exit block, and this
2365                instruction is a return, then keep the edge.  */
2366             {
2367               ei_next (&ei);
2368               continue;
2369             }
2370           else if ((e->flags & EDGE_EH) && can_throw_internal (insn))
2371             /* Keep the edges that correspond to exceptions thrown by
2372                this instruction and rematerialize the EDGE_ABNORMAL
2373                flag we just cleared above.  */
2374             {
2375               e->flags |= EDGE_ABNORMAL;
2376               ei_next (&ei);
2377               continue;
2378             }
2379
2380           /* We do not need this edge.  */
2381           bb->flags |= BB_DIRTY;
2382           purged = true;
2383           remove_edge (e);
2384         }
2385
2386       if (EDGE_COUNT (bb->succs) == 0 || !purged)
2387         return purged;
2388
2389       if (dump_file)
2390         fprintf (dump_file, "Purged edges from bb %i\n", bb->index);
2391
2392       if (!optimize)
2393         return purged;
2394
2395       /* Redistribute probabilities.  */
2396       if (EDGE_COUNT (bb->succs) == 1)
2397         {
2398           EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
2399           EDGE_SUCC (bb, 0)->count = bb->count;
2400         }
2401       else
2402         {
2403           note = find_reg_note (insn, REG_BR_PROB, NULL);
2404           if (!note)
2405             return purged;
2406
2407           b = BRANCH_EDGE (bb);
2408           f = FALLTHRU_EDGE (bb);
2409           b->probability = INTVAL (XEXP (note, 0));
2410           f->probability = REG_BR_PROB_BASE - b->probability;
2411           b->count = bb->count * b->probability / REG_BR_PROB_BASE;
2412           f->count = bb->count * f->probability / REG_BR_PROB_BASE;
2413         }
2414
2415       return purged;
2416     }
2417   else if (CALL_P (insn) && SIBLING_CALL_P (insn))
2418     {
2419       /* First, there should not be any EH or ABCALL edges resulting
2420          from non-local gotos and the like.  If there were, we shouldn't
2421          have created the sibcall in the first place.  Second, there
2422          should of course never have been a fallthru edge.  */
2423       gcc_assert (EDGE_COUNT (bb->succs) == 1);
2424       gcc_assert (EDGE_SUCC (bb, 0)->flags == (EDGE_SIBCALL | EDGE_ABNORMAL));
2425
2426       return 0;
2427     }
2428
2429   /* If we don't see a jump insn, we don't know exactly why the block would
2430      have been broken at this point.  Look for a simple, non-fallthru edge,
2431      as these are only created by conditional branches.  If we find such an
2432      edge we know that there used to be a jump here and can then safely
2433      remove all non-fallthru edges.  */
2434   found = false;
2435   FOR_EACH_EDGE (e, ei, bb->succs)
2436     if (! (e->flags & (EDGE_COMPLEX | EDGE_FALLTHRU)))
2437       {
2438         found = true;
2439         break;
2440       }
2441
2442   if (!found)
2443     return purged;
2444
2445   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
2446     {
2447       if (!(e->flags & EDGE_FALLTHRU))
2448         {
2449           bb->flags |= BB_DIRTY;
2450           remove_edge (e);
2451           purged = true;
2452         }
2453       else
2454         ei_next (&ei);
2455     }
2456
2457   gcc_assert (EDGE_COUNT (bb->succs) == 1);
2458
2459   EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE;
2460   EDGE_SUCC (bb, 0)->count = bb->count;
2461
2462   if (dump_file)
2463     fprintf (dump_file, "Purged non-fallthru edges from bb %i\n",
2464              bb->index);
2465   return purged;
2466 }
2467
2468 /* Search all basic blocks for potentially dead edges and purge them.  Return
2469    true if some edge has been eliminated.  */
2470
2471 bool
2472 purge_all_dead_edges (int update_life_p)
2473 {
2474   int purged = false;
2475   sbitmap blocks = 0;
2476   basic_block bb;
2477
2478   if (update_life_p)
2479     {
2480       blocks = sbitmap_alloc (last_basic_block);
2481       sbitmap_zero (blocks);
2482     }
2483
2484   FOR_EACH_BB (bb)
2485     {
2486       bool purged_here = purge_dead_edges (bb);
2487
2488       purged |= purged_here;
2489       if (purged_here && update_life_p)
2490         SET_BIT (blocks, bb->index);
2491     }
2492
2493   if (update_life_p && purged)
2494     update_life_info (blocks, UPDATE_LIFE_GLOBAL,
2495                       PROP_DEATH_NOTES | PROP_SCAN_DEAD_CODE
2496                       | PROP_KILL_DEAD_CODE);
2497
2498   if (update_life_p)
2499     sbitmap_free (blocks);
2500   return purged;
2501 }
2502
2503 /* Same as split_block but update cfg_layout structures.  */
2504
2505 static basic_block
2506 cfg_layout_split_block (basic_block bb, void *insnp)
2507 {
2508   rtx insn = insnp;
2509   basic_block new_bb = rtl_split_block (bb, insn);
2510
2511   new_bb->rbi->footer = bb->rbi->footer;
2512   bb->rbi->footer = NULL;
2513
2514   return new_bb;
2515 }
2516
2517
2518 /* Redirect Edge to DEST.  */
2519 static edge
2520 cfg_layout_redirect_edge_and_branch (edge e, basic_block dest)
2521 {
2522   basic_block src = e->src;
2523   edge ret;
2524
2525   if (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))
2526     return NULL;
2527
2528   if (e->dest == dest)
2529     return e;
2530
2531   if (e->src != ENTRY_BLOCK_PTR
2532       && (ret = try_redirect_by_replacing_jump (e, dest, true)))
2533     {
2534       src->flags |= BB_DIRTY;
2535       return ret;
2536     }
2537
2538   if (e->src == ENTRY_BLOCK_PTR
2539       && (e->flags & EDGE_FALLTHRU) && !(e->flags & EDGE_COMPLEX))
2540     {
2541       if (dump_file)
2542         fprintf (dump_file, "Redirecting entry edge from bb %i to %i\n",
2543                  e->src->index, dest->index);
2544
2545       e->src->flags |= BB_DIRTY;
2546       redirect_edge_succ (e, dest);
2547       return e;
2548     }
2549
2550   /* Redirect_edge_and_branch may decide to turn branch into fallthru edge
2551      in the case the basic block appears to be in sequence.  Avoid this
2552      transformation.  */
2553
2554   if (e->flags & EDGE_FALLTHRU)
2555     {
2556       /* Redirect any branch edges unified with the fallthru one.  */
2557       if (JUMP_P (BB_END (src))
2558           && label_is_jump_target_p (BB_HEAD (e->dest),
2559                                      BB_END (src)))
2560         {
2561           edge redirected;
2562           
2563           if (dump_file)
2564             fprintf (dump_file, "Fallthru edge unified with branch "
2565                      "%i->%i redirected to %i\n",
2566                      e->src->index, e->dest->index, dest->index);
2567           e->flags &= ~EDGE_FALLTHRU;
2568           redirected = redirect_branch_edge (e, dest);
2569           gcc_assert (redirected);
2570           e->flags |= EDGE_FALLTHRU;
2571           e->src->flags |= BB_DIRTY;
2572           return e;
2573         }
2574       /* In case we are redirecting fallthru edge to the branch edge
2575          of conditional jump, remove it.  */
2576       if (EDGE_COUNT (src->succs) == 2)
2577         {
2578           /* Find the edge that is different from E.  */
2579           edge s = EDGE_SUCC (src, EDGE_SUCC (src, 0) == e);
2580
2581           if (s->dest == dest
2582               && any_condjump_p (BB_END (src))
2583               && onlyjump_p (BB_END (src)))
2584             delete_insn (BB_END (src));
2585         }
2586       ret = redirect_edge_succ_nodup (e, dest);
2587       if (dump_file)
2588         fprintf (dump_file, "Fallthru edge %i->%i redirected to %i\n",
2589                  e->src->index, e->dest->index, dest->index);
2590     }
2591   else
2592     ret = redirect_branch_edge (e, dest);
2593
2594   /* We don't want simplejumps in the insn stream during cfglayout.  */
2595   gcc_assert (!simplejump_p (BB_END (src)));
2596
2597   src->flags |= BB_DIRTY;
2598   return ret;
2599 }
2600
2601 /* Simple wrapper as we always can redirect fallthru edges.  */
2602 static basic_block
2603 cfg_layout_redirect_edge_and_branch_force (edge e, basic_block dest)
2604 {
2605   edge redirected = cfg_layout_redirect_edge_and_branch (e, dest);
2606
2607   gcc_assert (redirected);
2608   return NULL;
2609 }
2610
2611 /* Same as delete_basic_block but update cfg_layout structures.  */
2612
2613 static void
2614 cfg_layout_delete_block (basic_block bb)
2615 {
2616   rtx insn, next, prev = PREV_INSN (BB_HEAD (bb)), *to, remaints;
2617
2618   if (bb->rbi->header)
2619     {
2620       next = BB_HEAD (bb);
2621       if (prev)
2622         NEXT_INSN (prev) = bb->rbi->header;
2623       else
2624         set_first_insn (bb->rbi->header);
2625       PREV_INSN (bb->rbi->header) = prev;
2626       insn = bb->rbi->header;
2627       while (NEXT_INSN (insn))
2628         insn = NEXT_INSN (insn);
2629       NEXT_INSN (insn) = next;
2630       PREV_INSN (next) = insn;
2631     }
2632   next = NEXT_INSN (BB_END (bb));
2633   if (bb->rbi->footer)
2634     {
2635       insn = bb->rbi->footer;
2636       while (insn)
2637         {
2638           if (BARRIER_P (insn))
2639             {
2640               if (PREV_INSN (insn))
2641                 NEXT_INSN (PREV_INSN (insn)) = NEXT_INSN (insn);
2642               else
2643                 bb->rbi->footer = NEXT_INSN (insn);
2644               if (NEXT_INSN (insn))
2645                 PREV_INSN (NEXT_INSN (insn)) = PREV_INSN (insn);
2646             }
2647           if (LABEL_P (insn))
2648             break;
2649           insn = NEXT_INSN (insn);
2650         }
2651       if (bb->rbi->footer)
2652         {
2653           insn = BB_END (bb);
2654           NEXT_INSN (insn) = bb->rbi->footer;
2655           PREV_INSN (bb->rbi->footer) = insn;
2656           while (NEXT_INSN (insn))
2657             insn = NEXT_INSN (insn);
2658           NEXT_INSN (insn) = next;
2659           if (next)
2660             PREV_INSN (next) = insn;
2661           else
2662             set_last_insn (insn);
2663         }
2664     }
2665   if (bb->next_bb != EXIT_BLOCK_PTR)
2666     to = &bb->next_bb->rbi->header;
2667   else
2668     to = &cfg_layout_function_footer;
2669   rtl_delete_block (bb);
2670
2671   if (prev)
2672     prev = NEXT_INSN (prev);
2673   else
2674     prev = get_insns ();
2675   if (next)
2676     next = PREV_INSN (next);
2677   else
2678     next = get_last_insn ();
2679
2680   if (next && NEXT_INSN (next) != prev)
2681     {
2682       remaints = unlink_insn_chain (prev, next);
2683       insn = remaints;
2684       while (NEXT_INSN (insn))
2685         insn = NEXT_INSN (insn);
2686       NEXT_INSN (insn) = *to;
2687       if (*to)
2688         PREV_INSN (*to) = insn;
2689       *to = remaints;
2690     }
2691 }
2692
2693 /* Return true when blocks A and B can be safely merged.  */
2694 static bool
2695 cfg_layout_can_merge_blocks_p (basic_block a, basic_block b)
2696 {
2697   /* If we are partitioning hot/cold basic blocks, we don't want to
2698      mess up unconditional or indirect jumps that cross between hot
2699      and cold sections.
2700
2701      Basic block partitioning may result in some jumps that appear to
2702      be optimizable (or blocks that appear to be mergeable), but which really 
2703      must be left untouched (they are required to make it safely across 
2704      partition boundaries).  See  the comments at the top of 
2705      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
2706
2707   if (flag_reorder_blocks_and_partition
2708       && (find_reg_note (BB_END (a), REG_CROSSING_JUMP, NULL_RTX)
2709           || find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
2710           || BB_PARTITION (a) != BB_PARTITION (b)))
2711     return false;
2712
2713   /* There must be exactly one edge in between the blocks.  */
2714   return (EDGE_COUNT (a->succs) == 1
2715           && EDGE_SUCC (a, 0)->dest == b
2716           && EDGE_COUNT (b->preds) == 1
2717           && a != b
2718           /* Must be simple edge.  */
2719           && !(EDGE_SUCC (a, 0)->flags & EDGE_COMPLEX)
2720           && a != ENTRY_BLOCK_PTR && b != EXIT_BLOCK_PTR
2721           /* If the jump insn has side effects,
2722              we can't kill the edge.  */
2723           && (!JUMP_P (BB_END (a))
2724               || (reload_completed
2725                   ? simplejump_p (BB_END (a)) : onlyjump_p (BB_END (a)))));
2726 }
2727
2728 /* Merge block A and B, abort when it is not possible.  */
2729 static void
2730 cfg_layout_merge_blocks (basic_block a, basic_block b)
2731 {
2732 #ifdef ENABLE_CHECKING
2733   gcc_assert (cfg_layout_can_merge_blocks_p (a, b));
2734 #endif
2735
2736   /* If there was a CODE_LABEL beginning B, delete it.  */
2737   if (LABEL_P (BB_HEAD (b)))
2738     delete_insn (BB_HEAD (b));
2739
2740   /* We should have fallthru edge in a, or we can do dummy redirection to get
2741      it cleaned up.  */
2742   if (JUMP_P (BB_END (a)))
2743     try_redirect_by_replacing_jump (EDGE_SUCC (a, 0), b, true);
2744   gcc_assert (!JUMP_P (BB_END (a)));
2745
2746   /* Possible line number notes should appear in between.  */
2747   if (b->rbi->header)
2748     {
2749       rtx first = BB_END (a), last;
2750
2751       last = emit_insn_after_noloc (b->rbi->header, BB_END (a));
2752       delete_insn_chain (NEXT_INSN (first), last);
2753       b->rbi->header = NULL;
2754     }
2755
2756   /* In the case basic blocks are not adjacent, move them around.  */
2757   if (NEXT_INSN (BB_END (a)) != BB_HEAD (b))
2758     {
2759       rtx first = unlink_insn_chain (BB_HEAD (b), BB_END (b));
2760
2761       emit_insn_after_noloc (first, BB_END (a));
2762       /* Skip possible DELETED_LABEL insn.  */
2763       if (!NOTE_INSN_BASIC_BLOCK_P (first))
2764         first = NEXT_INSN (first);
2765       gcc_assert (NOTE_INSN_BASIC_BLOCK_P (first));
2766       BB_HEAD (b) = NULL;
2767       delete_insn (first);
2768     }
2769   /* Otherwise just re-associate the instructions.  */
2770   else
2771     {
2772       rtx insn;
2773
2774       for (insn = BB_HEAD (b);
2775            insn != NEXT_INSN (BB_END (b));
2776            insn = NEXT_INSN (insn))
2777         set_block_for_insn (insn, a);
2778       insn = BB_HEAD (b);
2779       /* Skip possible DELETED_LABEL insn.  */
2780       if (!NOTE_INSN_BASIC_BLOCK_P (insn))
2781         insn = NEXT_INSN (insn);
2782       gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
2783       BB_HEAD (b) = NULL;
2784       BB_END (a) = BB_END (b);
2785       delete_insn (insn);
2786     }
2787
2788   /* Possible tablejumps and barriers should appear after the block.  */
2789   if (b->rbi->footer)
2790     {
2791       if (!a->rbi->footer)
2792         a->rbi->footer = b->rbi->footer;
2793       else
2794         {
2795           rtx last = a->rbi->footer;
2796
2797           while (NEXT_INSN (last))
2798             last = NEXT_INSN (last);
2799           NEXT_INSN (last) = b->rbi->footer;
2800           PREV_INSN (b->rbi->footer) = last;
2801         }
2802       b->rbi->footer = NULL;
2803     }
2804
2805   if (dump_file)
2806     fprintf (dump_file, "Merged blocks %d and %d.\n",
2807              a->index, b->index);
2808 }
2809
2810 /* Split edge E.  */
2811
2812 static basic_block
2813 cfg_layout_split_edge (edge e)
2814 {
2815   edge new_e;
2816   basic_block new_bb =
2817     create_basic_block (e->src != ENTRY_BLOCK_PTR
2818                         ? NEXT_INSN (BB_END (e->src)) : get_insns (),
2819                         NULL_RTX, e->src);
2820
2821   /* ??? This info is likely going to be out of date very soon, but we must
2822      create it to avoid getting an ICE later.  */
2823   if (e->dest->global_live_at_start)
2824     {
2825       new_bb->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
2826       new_bb->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
2827       COPY_REG_SET (new_bb->global_live_at_start,
2828                     e->dest->global_live_at_start);
2829       COPY_REG_SET (new_bb->global_live_at_end,
2830                     e->dest->global_live_at_start);
2831     }
2832
2833   new_e = make_edge (new_bb, e->dest, EDGE_FALLTHRU);
2834   redirect_edge_and_branch_force (e, new_bb);
2835
2836   return new_bb;
2837 }
2838
2839 /* Do postprocessing after making a forwarder block joined by edge FALLTHRU.  */
2840
2841 static void
2842 rtl_make_forwarder_block (edge fallthru ATTRIBUTE_UNUSED)
2843 {
2844 }
2845
2846 /* Return 1 if BB ends with a call, possibly followed by some
2847    instructions that must stay with the call, 0 otherwise.  */
2848
2849 static bool
2850 rtl_block_ends_with_call_p (basic_block bb)
2851 {
2852   rtx insn = BB_END (bb);
2853
2854   while (!CALL_P (insn)
2855          && insn != BB_HEAD (bb)
2856          && keep_with_call_p (insn))
2857     insn = PREV_INSN (insn);
2858   return (CALL_P (insn));
2859 }
2860
2861 /* Return 1 if BB ends with a conditional branch, 0 otherwise.  */
2862
2863 static bool
2864 rtl_block_ends_with_condjump_p (basic_block bb)
2865 {
2866   return any_condjump_p (BB_END (bb));
2867 }
2868
2869 /* Return true if we need to add fake edge to exit.
2870    Helper function for rtl_flow_call_edges_add.  */
2871
2872 static bool
2873 need_fake_edge_p (rtx insn)
2874 {
2875   if (!INSN_P (insn))
2876     return false;
2877
2878   if ((CALL_P (insn)
2879        && !SIBLING_CALL_P (insn)
2880        && !find_reg_note (insn, REG_NORETURN, NULL)
2881        && !find_reg_note (insn, REG_ALWAYS_RETURN, NULL)
2882        && !CONST_OR_PURE_CALL_P (insn)))
2883     return true;
2884
2885   return ((GET_CODE (PATTERN (insn)) == ASM_OPERANDS
2886            && MEM_VOLATILE_P (PATTERN (insn)))
2887           || (GET_CODE (PATTERN (insn)) == PARALLEL
2888               && asm_noperands (insn) != -1
2889               && MEM_VOLATILE_P (XVECEXP (PATTERN (insn), 0, 0)))
2890           || GET_CODE (PATTERN (insn)) == ASM_INPUT);
2891 }
2892
2893 /* Add fake edges to the function exit for any non constant and non noreturn
2894    calls, volatile inline assembly in the bitmap of blocks specified by
2895    BLOCKS or to the whole CFG if BLOCKS is zero.  Return the number of blocks
2896    that were split.
2897
2898    The goal is to expose cases in which entering a basic block does not imply
2899    that all subsequent instructions must be executed.  */
2900
2901 static int
2902 rtl_flow_call_edges_add (sbitmap blocks)
2903 {
2904   int i;
2905   int blocks_split = 0;
2906   int last_bb = last_basic_block;
2907   bool check_last_block = false;
2908
2909   if (n_basic_blocks == 0)
2910     return 0;
2911
2912   if (! blocks)
2913     check_last_block = true;
2914   else
2915     check_last_block = TEST_BIT (blocks, EXIT_BLOCK_PTR->prev_bb->index);
2916
2917   /* In the last basic block, before epilogue generation, there will be
2918      a fallthru edge to EXIT.  Special care is required if the last insn
2919      of the last basic block is a call because make_edge folds duplicate
2920      edges, which would result in the fallthru edge also being marked
2921      fake, which would result in the fallthru edge being removed by
2922      remove_fake_edges, which would result in an invalid CFG.
2923
2924      Moreover, we can't elide the outgoing fake edge, since the block
2925      profiler needs to take this into account in order to solve the minimal
2926      spanning tree in the case that the call doesn't return.
2927
2928      Handle this by adding a dummy instruction in a new last basic block.  */
2929   if (check_last_block)
2930     {
2931       basic_block bb = EXIT_BLOCK_PTR->prev_bb;
2932       rtx insn = BB_END (bb);
2933
2934       /* Back up past insns that must be kept in the same block as a call.  */
2935       while (insn != BB_HEAD (bb)
2936              && keep_with_call_p (insn))
2937         insn = PREV_INSN (insn);
2938
2939       if (need_fake_edge_p (insn))
2940         {
2941           edge e;
2942
2943           e = find_edge (bb, EXIT_BLOCK_PTR);
2944           if (e)
2945             {
2946               insert_insn_on_edge (gen_rtx_USE (VOIDmode, const0_rtx), e);
2947               commit_edge_insertions ();
2948             }
2949         }
2950     }
2951
2952   /* Now add fake edges to the function exit for any non constant
2953      calls since there is no way that we can determine if they will
2954      return or not...  */
2955
2956   for (i = 0; i < last_bb; i++)
2957     {
2958       basic_block bb = BASIC_BLOCK (i);
2959       rtx insn;
2960       rtx prev_insn;
2961
2962       if (!bb)
2963         continue;
2964
2965       if (blocks && !TEST_BIT (blocks, i))
2966         continue;
2967
2968       for (insn = BB_END (bb); ; insn = prev_insn)
2969         {
2970           prev_insn = PREV_INSN (insn);
2971           if (need_fake_edge_p (insn))
2972             {
2973               edge e;
2974               rtx split_at_insn = insn;
2975
2976               /* Don't split the block between a call and an insn that should
2977                  remain in the same block as the call.  */
2978               if (CALL_P (insn))
2979                 while (split_at_insn != BB_END (bb)
2980                        && keep_with_call_p (NEXT_INSN (split_at_insn)))
2981                   split_at_insn = NEXT_INSN (split_at_insn);
2982
2983               /* The handling above of the final block before the epilogue
2984                  should be enough to verify that there is no edge to the exit
2985                  block in CFG already.  Calling make_edge in such case would
2986                  cause us to mark that edge as fake and remove it later.  */
2987
2988 #ifdef ENABLE_CHECKING
2989               if (split_at_insn == BB_END (bb))
2990                 {
2991                   e = find_edge (bb, EXIT_BLOCK_PTR);
2992                   gcc_assert (e == NULL);
2993                 }
2994 #endif
2995
2996               /* Note that the following may create a new basic block
2997                  and renumber the existing basic blocks.  */
2998               if (split_at_insn != BB_END (bb))
2999                 {
3000                   e = split_block (bb, split_at_insn);
3001                   if (e)
3002                     blocks_split++;
3003                 }
3004
3005               make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
3006             }
3007
3008           if (insn == BB_HEAD (bb))
3009             break;
3010         }
3011     }
3012
3013   if (blocks_split)
3014     verify_flow_info ();
3015
3016   return blocks_split;
3017 }
3018
3019 /* Implementation of CFG manipulation for linearized RTL.  */
3020 struct cfg_hooks rtl_cfg_hooks = {
3021   "rtl",
3022   rtl_verify_flow_info,
3023   rtl_dump_bb,
3024   rtl_create_basic_block,
3025   rtl_redirect_edge_and_branch,
3026   rtl_redirect_edge_and_branch_force,
3027   rtl_delete_block,
3028   rtl_split_block,
3029   rtl_move_block_after,
3030   rtl_can_merge_blocks,  /* can_merge_blocks_p */
3031   rtl_merge_blocks,
3032   rtl_predict_edge,
3033   rtl_predicted_by_p,
3034   NULL, /* can_duplicate_block_p */
3035   NULL, /* duplicate_block */
3036   rtl_split_edge,
3037   rtl_make_forwarder_block,
3038   rtl_tidy_fallthru_edge,
3039   rtl_block_ends_with_call_p,
3040   rtl_block_ends_with_condjump_p,
3041   rtl_flow_call_edges_add,
3042   NULL, /* execute_on_growing_pred */
3043   NULL /* execute_on_shrinking_pred */
3044 };
3045
3046 /* Implementation of CFG manipulation for cfg layout RTL, where
3047    basic block connected via fallthru edges does not have to be adjacent.
3048    This representation will hopefully become the default one in future
3049    version of the compiler.  */
3050
3051 /* We do not want to declare these functions in a header file, since they
3052    should only be used through the cfghooks interface, and we do not want to
3053    move them here since it would require also moving quite a lot of related
3054    code.  */
3055 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
3056 extern basic_block cfg_layout_duplicate_bb (basic_block);
3057
3058 struct cfg_hooks cfg_layout_rtl_cfg_hooks = {
3059   "cfglayout mode",
3060   rtl_verify_flow_info_1,
3061   rtl_dump_bb,
3062   cfg_layout_create_basic_block,
3063   cfg_layout_redirect_edge_and_branch,
3064   cfg_layout_redirect_edge_and_branch_force,
3065   cfg_layout_delete_block,
3066   cfg_layout_split_block,
3067   rtl_move_block_after,
3068   cfg_layout_can_merge_blocks_p,
3069   cfg_layout_merge_blocks,
3070   rtl_predict_edge,
3071   rtl_predicted_by_p,
3072   cfg_layout_can_duplicate_bb_p,
3073   cfg_layout_duplicate_bb,
3074   cfg_layout_split_edge,
3075   rtl_make_forwarder_block,
3076   NULL,
3077   rtl_block_ends_with_call_p,
3078   rtl_block_ends_with_condjump_p,
3079   rtl_flow_call_edges_add,
3080   NULL, /* execute_on_growing_pred */
3081   NULL /* execute_on_shrinking_pred */
3082 };
3083