OSDN Git Service

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