OSDN Git Service

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