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