OSDN Git Service

* cfglayout.c (fixup_reorder_chain): Handle case where the
[pf3gnuchains/gcc-fork.git] / gcc / cfglayout.c
1 /* Basic block reordering routines for the GNU compiler.
2    Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
9 version.
10
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING.  If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "rtl.h"
27 #include "hard-reg-set.h"
28 #include "basic-block.h"
29 #include "insn-config.h"
30 #include "output.h"
31 #include "function.h"
32 #include "obstack.h"
33 #include "cfglayout.h"
34 #include "cfgloop.h"
35 #include "target.h"
36 #include "ggc.h"
37 #include "alloc-pool.h"
38 #include "flags.h"
39
40 /* The contents of the current function definition are allocated
41    in this obstack, and all are freed at the end of the function.  */
42 extern struct obstack flow_obstack;
43
44 /* Holds the interesting trailing notes for the function.  */
45 rtx cfg_layout_function_footer, cfg_layout_function_header;
46
47 static rtx skip_insns_after_block (basic_block);
48 static void record_effective_endpoints (void);
49 static rtx label_for_bb (basic_block);
50 static void fixup_reorder_chain (void);
51
52 static void set_block_levels (tree, int);
53 static void change_scope (rtx, tree, tree);
54
55 void verify_insn_chain (void);
56 static void fixup_fallthru_exit_predecessor (void);
57 static tree insn_scope (rtx);
58 static void update_unlikely_executed_notes (basic_block);
59 \f
60 rtx
61 unlink_insn_chain (rtx first, rtx last)
62 {
63   rtx prevfirst = PREV_INSN (first);
64   rtx nextlast = NEXT_INSN (last);
65
66   PREV_INSN (first) = NULL;
67   NEXT_INSN (last) = NULL;
68   if (prevfirst)
69     NEXT_INSN (prevfirst) = nextlast;
70   if (nextlast)
71     PREV_INSN (nextlast) = prevfirst;
72   else
73     set_last_insn (prevfirst);
74   if (!prevfirst)
75     set_first_insn (nextlast);
76   return first;
77 }
78 \f
79 /* Skip over inter-block insns occurring after BB which are typically
80    associated with BB (e.g., barriers). If there are any such insns,
81    we return the last one. Otherwise, we return the end of BB.  */
82
83 static rtx
84 skip_insns_after_block (basic_block bb)
85 {
86   rtx insn, last_insn, next_head, prev;
87
88   next_head = NULL_RTX;
89   if (bb->next_bb != EXIT_BLOCK_PTR)
90     next_head = BB_HEAD (bb->next_bb);
91
92   for (last_insn = insn = BB_END (bb); (insn = NEXT_INSN (insn)) != 0; )
93     {
94       if (insn == next_head)
95         break;
96
97       switch (GET_CODE (insn))
98         {
99         case BARRIER:
100           last_insn = insn;
101           continue;
102
103         case NOTE:
104           switch (NOTE_LINE_NUMBER (insn))
105             {
106             case NOTE_INSN_LOOP_END:
107             case NOTE_INSN_BLOCK_END:
108               last_insn = insn;
109               continue;
110             case NOTE_INSN_DELETED:
111             case NOTE_INSN_DELETED_LABEL:
112               continue;
113
114             default:
115               continue;
116               break;
117             }
118           break;
119
120         case CODE_LABEL:
121           if (NEXT_INSN (insn)
122               && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
123               && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
124                   || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
125             {
126               insn = NEXT_INSN (insn);
127               last_insn = insn;
128               continue;
129             }
130           break;
131
132         default:
133           break;
134         }
135
136       break;
137     }
138
139   /* It is possible to hit contradictory sequence.  For instance:
140
141      jump_insn
142      NOTE_INSN_LOOP_BEG
143      barrier
144
145      Where barrier belongs to jump_insn, but the note does not.  This can be
146      created by removing the basic block originally following
147      NOTE_INSN_LOOP_BEG.  In such case reorder the notes.  */
148
149   for (insn = last_insn; insn != BB_END (bb); insn = prev)
150     {
151       prev = PREV_INSN (insn);
152       if (GET_CODE (insn) == NOTE)
153         switch (NOTE_LINE_NUMBER (insn))
154           {
155           case NOTE_INSN_LOOP_END:
156           case NOTE_INSN_BLOCK_END:
157           case NOTE_INSN_DELETED:
158           case NOTE_INSN_DELETED_LABEL:
159             continue;
160           default:
161             reorder_insns (insn, insn, last_insn);
162           }
163     }
164
165   return last_insn;
166 }
167
168 /* Locate or create a label for a given basic block.  */
169
170 static rtx
171 label_for_bb (basic_block bb)
172 {
173   rtx label = BB_HEAD (bb);
174
175   if (GET_CODE (label) != CODE_LABEL)
176     {
177       if (dump_file)
178         fprintf (dump_file, "Emitting label for block %d\n", bb->index);
179
180       label = block_label (bb);
181     }
182
183   return label;
184 }
185
186 /* Locate the effective beginning and end of the insn chain for each
187    block, as defined by skip_insns_after_block above.  */
188
189 static void
190 record_effective_endpoints (void)
191 {
192   rtx next_insn;
193   basic_block bb;
194   rtx insn;
195
196   for (insn = get_insns ();
197        insn
198        && GET_CODE (insn) == NOTE
199        && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK;
200        insn = NEXT_INSN (insn))
201     continue;
202   if (!insn)
203     abort ();  /* No basic blocks at all?  */
204   if (PREV_INSN (insn))
205     cfg_layout_function_header =
206             unlink_insn_chain (get_insns (), PREV_INSN (insn));
207   else
208     cfg_layout_function_header = NULL_RTX;
209
210   next_insn = get_insns ();
211   FOR_EACH_BB (bb)
212     {
213       rtx end;
214
215       if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
216         bb->rbi->header = unlink_insn_chain (next_insn,
217                                               PREV_INSN (BB_HEAD (bb)));
218       end = skip_insns_after_block (bb);
219       if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
220         bb->rbi->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
221       next_insn = NEXT_INSN (BB_END (bb));
222     }
223
224   cfg_layout_function_footer = next_insn;
225   if (cfg_layout_function_footer)
226     cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
227 }
228 \f
229 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
230    numbers and files.  In order to be GGC friendly we need to use separate
231    varrays.  This also slightly improve the memory locality in binary search.
232    The _locs array contains locators where the given property change.  The
233    block_locators_blocks contains the scope block that is used for all insn
234    locator greater than corresponding block_locators_locs value and smaller
235    than the following one.  Similarly for the other properties.  */
236 static GTY(()) varray_type block_locators_locs;
237 static GTY(()) varray_type block_locators_blocks;
238 static GTY(()) varray_type line_locators_locs;
239 static GTY(()) varray_type line_locators_lines;
240 static GTY(()) varray_type file_locators_locs;
241 static GTY(()) varray_type file_locators_files;
242 int prologue_locator;
243 int epilogue_locator;
244
245 /* During the RTL expansion the lexical blocks and line numbers are
246    represented via INSN_NOTEs.  Replace them by representation using
247    INSN_LOCATORs.  */
248
249 void
250 insn_locators_initialize (void)
251 {
252   tree block = NULL;
253   tree last_block = NULL;
254   rtx insn, next;
255   int loc = 0;
256   int line_number = 0, last_line_number = 0;
257   char *file_name = NULL, *last_file_name = NULL;
258
259   prologue_locator = epilogue_locator = 0;
260
261   VARRAY_INT_INIT (block_locators_locs, 32, "block_locators_locs");
262   VARRAY_TREE_INIT (block_locators_blocks, 32, "block_locators_blocks");
263   VARRAY_INT_INIT (line_locators_locs, 32, "line_locators_locs");
264   VARRAY_INT_INIT (line_locators_lines, 32, "line_locators_lines");
265   VARRAY_INT_INIT (file_locators_locs, 32, "file_locators_locs");
266   VARRAY_CHAR_PTR_INIT (file_locators_files, 32, "file_locators_files");
267
268   for (insn = get_insns (); insn; insn = next)
269     {
270       next = NEXT_INSN (insn);
271
272       if ((active_insn_p (insn)
273            && GET_CODE (PATTERN (insn)) != ADDR_VEC
274            && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
275           || !NEXT_INSN (insn)
276           || (!prologue_locator && file_name))
277         {
278           if (last_block != block)
279             {
280               loc++;
281               VARRAY_PUSH_INT (block_locators_locs, loc);
282               VARRAY_PUSH_TREE (block_locators_blocks, block);
283               last_block = block;
284             }
285           if (last_line_number != line_number)
286             {
287               loc++;
288               VARRAY_PUSH_INT (line_locators_locs, loc);
289               VARRAY_PUSH_INT (line_locators_lines, line_number);
290               last_line_number = line_number;
291             }
292           if (last_file_name != file_name)
293             {
294               loc++;
295               VARRAY_PUSH_INT (file_locators_locs, loc);
296               VARRAY_PUSH_CHAR_PTR (file_locators_files, file_name);
297               last_file_name = file_name;
298             }
299         }
300       if (!prologue_locator && file_name)
301         prologue_locator = loc;
302       if (!NEXT_INSN (insn))
303         epilogue_locator = loc;
304       if (active_insn_p (insn))
305         INSN_LOCATOR (insn) = loc;
306       else if (GET_CODE (insn) == NOTE)
307         {
308           switch (NOTE_LINE_NUMBER (insn))
309             {
310             case NOTE_INSN_BLOCK_BEG:
311               if (cfun->dont_emit_block_notes)
312                 abort ();
313               block = NOTE_BLOCK (insn);
314               delete_insn (insn);
315               break;
316             case NOTE_INSN_BLOCK_END:
317               if (cfun->dont_emit_block_notes)
318                 abort ();
319               block = BLOCK_SUPERCONTEXT (block);
320               if (block && TREE_CODE (block) == FUNCTION_DECL)
321                 block = 0;
322               delete_insn (insn);
323               break;
324             default:
325               if (NOTE_LINE_NUMBER (insn) > 0)
326                 {
327                   line_number = NOTE_LINE_NUMBER (insn);
328                   file_name = (char *)NOTE_SOURCE_FILE (insn);
329                 }
330               break;
331             }
332         }
333
334       if (cfun->dont_emit_block_notes)
335         check_block_change (insn, &block);
336     }
337
338   /* Tag the blocks with a depth number so that change_scope can find
339      the common parent easily.  */
340   set_block_levels (DECL_INITIAL (cfun->decl), 0);
341
342   if (cfun->dont_emit_block_notes)
343     free_block_changes ();
344 }
345
346 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
347    found in the block tree.  */
348
349 static void
350 set_block_levels (tree block, int level)
351 {
352   while (block)
353     {
354       BLOCK_NUMBER (block) = level;
355       set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
356       block = BLOCK_CHAIN (block);
357     }
358 }
359 \f
360 /* Return sope resulting from combination of S1 and S2.  */
361 tree
362 choose_inner_scope (tree s1, tree s2)
363 {
364    if (!s1)
365      return s2;
366    if (!s2)
367      return s1;
368    if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
369      return s1;
370    return s2;
371 }
372 \f
373 /* Emit lexical block notes needed to change scope from S1 to S2.  */
374
375 static void
376 change_scope (rtx orig_insn, tree s1, tree s2)
377 {
378   rtx insn = orig_insn;
379   tree com = NULL_TREE;
380   tree ts1 = s1, ts2 = s2;
381   tree s;
382
383   while (ts1 != ts2)
384     {
385       if (ts1 == NULL || ts2 == NULL)
386         abort ();
387       if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
388         ts1 = BLOCK_SUPERCONTEXT (ts1);
389       else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
390         ts2 = BLOCK_SUPERCONTEXT (ts2);
391       else
392         {
393           ts1 = BLOCK_SUPERCONTEXT (ts1);
394           ts2 = BLOCK_SUPERCONTEXT (ts2);
395         }
396     }
397   com = ts1;
398
399   /* Close scopes.  */
400   s = s1;
401   while (s != com)
402     {
403       rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
404       NOTE_BLOCK (note) = s;
405       s = BLOCK_SUPERCONTEXT (s);
406     }
407
408   /* Open scopes.  */
409   s = s2;
410   while (s != com)
411     {
412       insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
413       NOTE_BLOCK (insn) = s;
414       s = BLOCK_SUPERCONTEXT (s);
415     }
416 }
417
418 /* Return lexical scope block insn belong to.  */
419 static tree
420 insn_scope (rtx insn)
421 {
422   int max = VARRAY_ACTIVE_SIZE (block_locators_locs);
423   int min = 0;
424   int loc = INSN_LOCATOR (insn);
425
426   /* When block_locators_locs was initialized, the pro- and epilogue
427      insns didn't exist yet and can therefore not be found this way.
428      But we know that they belong to the outer most block of the
429      current function.
430      Without this test, the prologue would be put inside the block of
431      the first valid instruction in the function and when that first
432      insn is part of an inlined function then the low_pc of that
433      inlined function is messed up.  Likewise for the epilogue and
434      the last valid instruction.  */
435   if (loc == prologue_locator || loc == epilogue_locator)
436     return DECL_INITIAL (cfun->decl);
437
438   if (!max || !loc)
439     return NULL;
440   while (1)
441     {
442       int pos = (min + max) / 2;
443       int tmp = VARRAY_INT (block_locators_locs, pos);
444
445       if (tmp <= loc && min != pos)
446         min = pos;
447       else if (tmp > loc && max != pos)
448         max = pos;
449       else
450         {
451           min = pos;
452           break;
453         }
454     }
455    return VARRAY_TREE (block_locators_blocks, min);
456 }
457
458 /* Return line number of the statement specified by the locator.  */
459 int
460 locator_line (int loc)
461 {
462   int max = VARRAY_ACTIVE_SIZE (line_locators_locs);
463   int min = 0;
464
465   if (!max || !loc)
466     return 0;
467   while (1)
468     {
469       int pos = (min + max) / 2;
470       int tmp = VARRAY_INT (line_locators_locs, pos);
471
472       if (tmp <= loc && min != pos)
473         min = pos;
474       else if (tmp > loc && max != pos)
475         max = pos;
476       else
477         {
478           min = pos;
479           break;
480         }
481     }
482    return VARRAY_INT (line_locators_lines, min);
483 }
484
485 /* Return line number of the statement that produced this insn.  */
486 int
487 insn_line (rtx insn)
488 {
489   return locator_line (INSN_LOCATOR (insn));
490 }
491
492 /* Return source file of the statement specified by LOC.  */
493 const char *
494 locator_file (int loc)
495 {
496   int max = VARRAY_ACTIVE_SIZE (file_locators_locs);
497   int min = 0;
498
499   if (!max || !loc)
500     return NULL;
501   while (1)
502     {
503       int pos = (min + max) / 2;
504       int tmp = VARRAY_INT (file_locators_locs, pos);
505
506       if (tmp <= loc && min != pos)
507         min = pos;
508       else if (tmp > loc && max != pos)
509         max = pos;
510       else
511         {
512           min = pos;
513           break;
514         }
515     }
516    return VARRAY_CHAR_PTR (file_locators_files, min);
517 }
518
519 /* Return source file of the statement that produced this insn.  */
520 const char *
521 insn_file (rtx insn)
522 {
523   return locator_file (INSN_LOCATOR (insn));
524 }
525
526 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
527    on the scope tree and the newly reordered instructions.  */
528
529 void
530 reemit_insn_block_notes (void)
531 {
532   tree cur_block = DECL_INITIAL (cfun->decl);
533   rtx insn, note;
534
535   insn = get_insns ();
536   if (!active_insn_p (insn))
537     insn = next_active_insn (insn);
538   for (; insn; insn = next_active_insn (insn))
539     {
540       tree this_block;
541
542       this_block = insn_scope (insn);
543       /* For sequences compute scope resulting from merging all scopes
544          of instructions nested inside.  */
545       if (GET_CODE (PATTERN (insn)) == SEQUENCE)
546         {
547           int i;
548           rtx body = PATTERN (insn);
549
550           this_block = NULL;
551           for (i = 0; i < XVECLEN (body, 0); i++)
552             this_block = choose_inner_scope (this_block,
553                                          insn_scope (XVECEXP (body, 0, i)));
554         }
555       if (! this_block)
556         continue;
557
558       if (this_block != cur_block)
559         {
560           change_scope (insn, cur_block, this_block);
561           cur_block = this_block;
562         }
563     }
564
565   /* change_scope emits before the insn, not after.  */
566   note = emit_note (NOTE_INSN_DELETED);
567   change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
568   delete_insn (note);
569
570   reorder_blocks ();
571 }
572 \f
573 /* Given a reorder chain, rearrange the code to match.  */
574
575 static void
576 fixup_reorder_chain (void)
577 {
578   basic_block bb, prev_bb;
579   int index;
580   rtx insn = NULL;
581
582   if (cfg_layout_function_header)
583     {
584       set_first_insn (cfg_layout_function_header);
585       insn = cfg_layout_function_header;
586       while (NEXT_INSN (insn))
587         insn = NEXT_INSN (insn);
588     }
589
590   /* First do the bulk reordering -- rechain the blocks without regard to
591      the needed changes to jumps and labels.  */
592
593   for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
594        bb != 0;
595        bb = bb->rbi->next, index++)
596     {
597       if (bb->rbi->header)
598         {
599           if (insn)
600             NEXT_INSN (insn) = bb->rbi->header;
601           else
602             set_first_insn (bb->rbi->header);
603           PREV_INSN (bb->rbi->header) = insn;
604           insn = bb->rbi->header;
605           while (NEXT_INSN (insn))
606             insn = NEXT_INSN (insn);
607         }
608       if (insn)
609         NEXT_INSN (insn) = BB_HEAD (bb);
610       else
611         set_first_insn (BB_HEAD (bb));
612       PREV_INSN (BB_HEAD (bb)) = insn;
613       insn = BB_END (bb);
614       if (bb->rbi->footer)
615         {
616           NEXT_INSN (insn) = bb->rbi->footer;
617           PREV_INSN (bb->rbi->footer) = insn;
618           while (NEXT_INSN (insn))
619             insn = NEXT_INSN (insn);
620         }
621     }
622
623   if (index != n_basic_blocks)
624     abort ();
625
626   NEXT_INSN (insn) = cfg_layout_function_footer;
627   if (cfg_layout_function_footer)
628     PREV_INSN (cfg_layout_function_footer) = insn;
629
630   while (NEXT_INSN (insn))
631     insn = NEXT_INSN (insn);
632
633   set_last_insn (insn);
634 #ifdef ENABLE_CHECKING
635   verify_insn_chain ();
636 #endif
637   delete_dead_jumptables ();
638
639   /* Now add jumps and labels as needed to match the blocks new
640      outgoing edges.  */
641
642   for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->rbi->next)
643     {
644       edge e_fall, e_taken, e;
645       rtx bb_end_insn;
646       basic_block nb;
647       basic_block old_bb;
648
649       if (bb->succ == NULL)
650         continue;
651
652       /* Find the old fallthru edge, and another non-EH edge for
653          a taken jump.  */
654       e_taken = e_fall = NULL;
655       for (e = bb->succ; e ; e = e->succ_next)
656         if (e->flags & EDGE_FALLTHRU)
657           e_fall = e;
658         else if (! (e->flags & EDGE_EH))
659           e_taken = e;
660
661       bb_end_insn = BB_END (bb);
662       if (GET_CODE (bb_end_insn) == JUMP_INSN)
663         {
664           if (any_condjump_p (bb_end_insn))
665             {
666               /* If the old fallthru is still next, nothing to do.  */
667               if (bb->rbi->next == e_fall->dest
668                   || (!bb->rbi->next
669                       && e_fall->dest == EXIT_BLOCK_PTR))
670                 continue;
671
672               /* The degenerated case of conditional jump jumping to the next
673                  instruction can happen on target having jumps with side
674                  effects.
675
676                  Create temporarily the duplicated edge representing branch.
677                  It will get unidentified by force_nonfallthru_and_redirect
678                  that would otherwise get confused by fallthru edge not pointing
679                  to the next basic block.  */
680               if (!e_taken)
681                 {
682                   rtx note;
683                   edge e_fake;
684
685                   e_fake = unchecked_make_edge (bb, e_fall->dest, 0);
686
687                   if (!redirect_jump (BB_END (bb), block_label (bb), 0))
688                     abort ();
689                   note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
690                   if (note)
691                     {
692                       int prob = INTVAL (XEXP (note, 0));
693
694                       e_fake->probability = prob;
695                       e_fake->count = e_fall->count * prob / REG_BR_PROB_BASE;
696                       e_fall->probability -= e_fall->probability;
697                       e_fall->count -= e_fake->count;
698                       if (e_fall->probability < 0)
699                         e_fall->probability = 0;
700                       if (e_fall->count < 0)
701                         e_fall->count = 0;
702                     }
703                 }
704               /* There is one special case: if *neither* block is next,
705                  such as happens at the very end of a function, then we'll
706                  need to add a new unconditional jump.  Choose the taken
707                  edge based on known or assumed probability.  */
708               else if (bb->rbi->next != e_taken->dest)
709                 {
710                   rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
711
712                   if (note
713                       && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
714                       && invert_jump (bb_end_insn,
715                                       (e_fall->dest == EXIT_BLOCK_PTR
716                                        ? NULL_RTX
717                                        : label_for_bb (e_fall->dest)), 0))
718                     {
719                       e_fall->flags &= ~EDGE_FALLTHRU;
720 #ifdef ENABLE_CHECKING
721                       if (!could_fall_through (e_taken->src, e_taken->dest))
722                         abort ();
723 #endif
724                       e_taken->flags |= EDGE_FALLTHRU;
725                       update_br_prob_note (bb);
726                       e = e_fall, e_fall = e_taken, e_taken = e;
727                     }
728                 }
729
730               /* If the "jumping" edge is a crossing edge, and the fall
731                  through edge is non-crossing, leave things as they are.  */
732               else if (e_taken->crossing_edge && !e_fall->crossing_edge)
733                 continue;
734
735               /* Otherwise we can try to invert the jump.  This will
736                  basically never fail, however, keep up the pretense.  */
737               else if (invert_jump (bb_end_insn,
738                                     (e_fall->dest == EXIT_BLOCK_PTR
739                                      ? NULL_RTX
740                                      : label_for_bb (e_fall->dest)), 0))
741                 {
742                   e_fall->flags &= ~EDGE_FALLTHRU;
743 #ifdef ENABLE_CHECKING
744                   if (!could_fall_through (e_taken->src, e_taken->dest))
745                     abort ();
746 #endif
747                   e_taken->flags |= EDGE_FALLTHRU;
748                   update_br_prob_note (bb);
749                   continue;
750                 }
751             }
752           else if (returnjump_p (bb_end_insn))
753             continue;
754           else
755             {
756               /* Otherwise we have some switch or computed jump.  In the
757                  99% case, there should not have been a fallthru edge.  */
758               if (! e_fall)
759                 continue;
760
761 #ifdef CASE_DROPS_THROUGH
762               /* Except for VAX.  Since we didn't have predication for the
763                  tablejump, the fallthru block should not have moved.  */
764               if (bb->rbi->next == e_fall->dest)
765                 continue;
766               bb_end_insn = skip_insns_after_block (bb);
767 #else
768               abort ();
769 #endif
770             }
771         }
772       else
773         {
774           /* No fallthru implies a noreturn function with EH edges, or
775              something similarly bizarre.  In any case, we don't need to
776              do anything.  */
777           if (! e_fall)
778             continue;
779
780           /* If the fallthru block is still next, nothing to do.  */
781           if (bb->rbi->next == e_fall->dest)
782             continue;
783
784           /* A fallthru to exit block.  */
785           if (e_fall->dest == EXIT_BLOCK_PTR)
786             continue;
787         }
788
789       /* We got here if we need to add a new jump insn.  */
790       nb = force_nonfallthru (e_fall);
791       if (nb)
792         {
793           initialize_bb_rbi (nb);
794           nb->rbi->visited = 1;
795           nb->rbi->next = bb->rbi->next;
796           bb->rbi->next = nb;
797           /* Don't process this new block.  */
798           old_bb = bb;
799           bb = nb;
800           
801           /* Make sure new bb is tagged for correct section (same as
802              fall-thru source).  */
803           e_fall->src->partition = bb->pred->src->partition;
804           if (flag_reorder_blocks_and_partition)
805             {
806               if (bb->pred->src->partition == COLD_PARTITION)
807                 {
808                   rtx new_note;
809                   rtx note = BB_HEAD (e_fall->src);
810                   
811                   while (!INSN_P (note)
812                          && note != BB_END (e_fall->src))
813                     note = NEXT_INSN (note);
814                   
815                   new_note = emit_note_before 
816                                           (NOTE_INSN_UNLIKELY_EXECUTED_CODE, 
817                                            note);
818                   NOTE_BASIC_BLOCK (new_note) = bb;
819                 }
820               if (GET_CODE (BB_END (bb)) == JUMP_INSN
821                   && !any_condjump_p (BB_END (bb))
822                   && bb->succ->crossing_edge )
823                 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST 
824                   (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
825             }
826         }
827     }
828
829   /* Put basic_block_info in the new order.  */
830
831   if (dump_file)
832     {
833       fprintf (dump_file, "Reordered sequence:\n");
834       for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
835            bb;
836            bb = bb->rbi->next, index++)
837         {
838           fprintf (dump_file, " %i ", index);
839           if (bb->rbi->original)
840             fprintf (dump_file, "duplicate of %i ",
841                      bb->rbi->original->index);
842           else if (forwarder_block_p (bb)
843                    && GET_CODE (BB_HEAD (bb)) != CODE_LABEL)
844             fprintf (dump_file, "compensation ");
845           else
846             fprintf (dump_file, "bb %i ", bb->index);
847           fprintf (dump_file, " [%i]\n", bb->frequency);
848         }
849     }
850
851   prev_bb = ENTRY_BLOCK_PTR;
852   bb = ENTRY_BLOCK_PTR->next_bb;
853   index = 0;
854
855   for (; bb; prev_bb = bb, bb = bb->rbi->next, index ++)
856     {
857       bb->index = index;
858       BASIC_BLOCK (index) = bb;
859
860       update_unlikely_executed_notes (bb);
861
862       bb->prev_bb = prev_bb;
863       prev_bb->next_bb = bb;
864     }
865   prev_bb->next_bb = EXIT_BLOCK_PTR;
866   EXIT_BLOCK_PTR->prev_bb = prev_bb;
867
868   /* Annoying special case - jump around dead jumptables left in the code.  */
869   FOR_EACH_BB (bb)
870     {
871       edge e;
872       for (e = bb->succ; e && !(e->flags & EDGE_FALLTHRU); e = e->succ_next)
873         continue;
874       if (e && !can_fallthru (e->src, e->dest))
875         force_nonfallthru (e);
876     }
877 }
878 \f
879 /* Update the basic block number information in any 
880    NOTE_INSN_UNLIKELY_EXECUTED_CODE notes within the basic block.  */
881
882 static void
883 update_unlikely_executed_notes (basic_block bb)
884 {
885   rtx cur_insn;
886
887   for (cur_insn = BB_HEAD (bb); cur_insn != BB_END (bb); 
888        cur_insn = NEXT_INSN (cur_insn)) 
889     if (GET_CODE (cur_insn) == NOTE
890         && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
891       NOTE_BASIC_BLOCK (cur_insn) = bb;
892 }
893 \f
894 /* Perform sanity checks on the insn chain.
895    1. Check that next/prev pointers are consistent in both the forward and
896       reverse direction.
897    2. Count insns in chain, going both directions, and check if equal.
898    3. Check that get_last_insn () returns the actual end of chain.  */
899
900 void
901 verify_insn_chain (void)
902 {
903   rtx x, prevx, nextx;
904   int insn_cnt1, insn_cnt2;
905
906   for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
907        x != 0;
908        prevx = x, insn_cnt1++, x = NEXT_INSN (x))
909     if (PREV_INSN (x) != prevx)
910       abort ();
911
912   if (prevx != get_last_insn ())
913     abort ();
914
915   for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
916        x != 0;
917        nextx = x, insn_cnt2++, x = PREV_INSN (x))
918     if (NEXT_INSN (x) != nextx)
919       abort ();
920
921   if (insn_cnt1 != insn_cnt2)
922     abort ();
923 }
924 \f
925 /* If we have assembler epilogues, the block falling through to exit must
926    be the last one in the reordered chain when we reach final.  Ensure
927    that this condition is met.  */
928 static void
929 fixup_fallthru_exit_predecessor (void)
930 {
931   edge e;
932   basic_block bb = NULL;
933
934   /* This transformation is not valid before reload, because we might separate
935      a call from the instruction that copies the return value.  */
936   if (! reload_completed)
937     abort ();
938
939   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
940     if (e->flags & EDGE_FALLTHRU)
941       bb = e->src;
942
943   if (bb && bb->rbi->next)
944     {
945       basic_block c = ENTRY_BLOCK_PTR->next_bb;
946
947       /* If the very first block is the one with the fall-through exit
948          edge, we have to split that block.  */
949       if (c == bb)
950         {
951           bb = split_block (bb, NULL)->dest;
952           initialize_bb_rbi (bb);
953           bb->rbi->next = c->rbi->next;
954           c->rbi->next = bb;
955           bb->rbi->footer = c->rbi->footer;
956           c->rbi->footer = NULL;
957         }
958
959       while (c->rbi->next != bb)
960         c = c->rbi->next;
961
962       c->rbi->next = bb->rbi->next;
963       while (c->rbi->next)
964         c = c->rbi->next;
965
966       c->rbi->next = bb;
967       bb->rbi->next = NULL;
968     }
969 }
970 \f
971 /* Return true in case it is possible to duplicate the basic block BB.  */
972
973 /* We do not want to declare the function in a header file, since it should
974    only be used through the cfghooks interface, and we do not want to move
975    it to cfgrtl.c since it would require also moving quite a lot of related
976    code.  */
977 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
978
979 bool
980 cfg_layout_can_duplicate_bb_p (basic_block bb)
981 {
982   /* Do not attempt to duplicate tablejumps, as we need to unshare
983      the dispatch table.  This is difficult to do, as the instructions
984      computing jump destination may be hoisted outside the basic block.  */
985   if (tablejump_p (BB_END (bb), NULL, NULL))
986     return false;
987
988   /* Do not duplicate blocks containing insns that can't be copied.  */
989   if (targetm.cannot_copy_insn_p)
990     {
991       rtx insn = BB_HEAD (bb);
992       while (1)
993         {
994           if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
995             return false;
996           if (insn == BB_END (bb))
997             break;
998           insn = NEXT_INSN (insn);
999         }
1000     }
1001
1002   return true;
1003 }
1004
1005 rtx
1006 duplicate_insn_chain (rtx from, rtx to)
1007 {
1008   rtx insn, last;
1009
1010   /* Avoid updating of boundaries of previous basic block.  The
1011      note will get removed from insn stream in fixup.  */
1012   last = emit_note (NOTE_INSN_DELETED);
1013
1014   /* Create copy at the end of INSN chain.  The chain will
1015      be reordered later.  */
1016   for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
1017     {
1018       switch (GET_CODE (insn))
1019         {
1020         case INSN:
1021         case CALL_INSN:
1022         case JUMP_INSN:
1023           /* Avoid copying of dispatch tables.  We never duplicate
1024              tablejumps, so this can hit only in case the table got
1025              moved far from original jump.  */
1026           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1027               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1028             break;
1029           emit_copy_of_insn_after (insn, get_last_insn ());
1030           break;
1031
1032         case CODE_LABEL:
1033           break;
1034
1035         case BARRIER:
1036           emit_barrier ();
1037           break;
1038
1039         case NOTE:
1040           switch (NOTE_LINE_NUMBER (insn))
1041             {
1042               /* In case prologue is empty and function contain label
1043                  in first BB, we may want to copy the block.  */
1044             case NOTE_INSN_PROLOGUE_END:
1045
1046             case NOTE_INSN_LOOP_VTOP:
1047             case NOTE_INSN_LOOP_CONT:
1048             case NOTE_INSN_LOOP_BEG:
1049             case NOTE_INSN_LOOP_END:
1050               /* Strip down the loop notes - we don't really want to keep
1051                  them consistent in loop copies.  */
1052             case NOTE_INSN_DELETED:
1053             case NOTE_INSN_DELETED_LABEL:
1054               /* No problem to strip these.  */
1055             case NOTE_INSN_EPILOGUE_BEG:
1056             case NOTE_INSN_FUNCTION_END:
1057               /* Debug code expect these notes to exist just once.
1058                  Keep them in the master copy.
1059                  ??? It probably makes more sense to duplicate them for each
1060                  epilogue copy.  */
1061             case NOTE_INSN_FUNCTION_BEG:
1062               /* There is always just single entry to function.  */
1063             case NOTE_INSN_BASIC_BLOCK:
1064               break;
1065
1066               /* There is no purpose to duplicate prologue.  */
1067             case NOTE_INSN_BLOCK_BEG:
1068             case NOTE_INSN_BLOCK_END:
1069               /* The BLOCK_BEG/BLOCK_END notes should be eliminated when BB
1070                  reordering is in the progress.  */
1071             case NOTE_INSN_EH_REGION_BEG:
1072             case NOTE_INSN_EH_REGION_END:
1073               /* Should never exist at BB duplication time.  */
1074               abort ();
1075               break;
1076             case NOTE_INSN_REPEATED_LINE_NUMBER:
1077             case NOTE_INSN_UNLIKELY_EXECUTED_CODE:
1078               emit_note_copy (insn);
1079               break;
1080
1081             default:
1082               if (NOTE_LINE_NUMBER (insn) < 0)
1083                 abort ();
1084               /* It is possible that no_line_number is set and the note
1085                  won't be emitted.  */
1086               emit_note_copy (insn);
1087             }
1088           break;
1089         default:
1090           abort ();
1091         }
1092     }
1093   insn = NEXT_INSN (last);
1094   delete_insn (last);
1095   return insn;
1096 }
1097 /* Create a duplicate of the basic block BB.  */
1098
1099 /* We do not want to declare the function in a header file, since it should
1100    only be used through the cfghooks interface, and we do not want to move
1101    it to cfgrtl.c since it would require also moving quite a lot of related
1102    code.  */
1103 extern basic_block cfg_layout_duplicate_bb (basic_block);
1104
1105 basic_block
1106 cfg_layout_duplicate_bb (basic_block bb)
1107 {
1108   rtx insn;
1109   basic_block new_bb;
1110
1111   insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1112   new_bb = create_basic_block (insn,
1113                                insn ? get_last_insn () : NULL,
1114                                EXIT_BLOCK_PTR->prev_bb);
1115
1116   if (bb->rbi->header)
1117     {
1118       insn = bb->rbi->header;
1119       while (NEXT_INSN (insn))
1120         insn = NEXT_INSN (insn);
1121       insn = duplicate_insn_chain (bb->rbi->header, insn);
1122       if (insn)
1123         new_bb->rbi->header = unlink_insn_chain (insn, get_last_insn ());
1124     }
1125
1126   if (bb->rbi->footer)
1127     {
1128       insn = bb->rbi->footer;
1129       while (NEXT_INSN (insn))
1130         insn = NEXT_INSN (insn);
1131       insn = duplicate_insn_chain (bb->rbi->footer, insn);
1132       if (insn)
1133         new_bb->rbi->footer = unlink_insn_chain (insn, get_last_insn ());
1134     }
1135
1136   if (bb->global_live_at_start)
1137     {
1138       new_bb->global_live_at_start = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1139       new_bb->global_live_at_end = OBSTACK_ALLOC_REG_SET (&flow_obstack);
1140       COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
1141       COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
1142     }
1143
1144   return new_bb;
1145 }
1146 \f
1147 /* Main entry point to this module - initialize the data structures for
1148    CFG layout changes.  It keeps LOOPS up-to-date if not null.  */
1149
1150 void
1151 cfg_layout_initialize (void)
1152 {
1153   basic_block bb;
1154
1155   /* Our algorithm depends on fact that there are no dead jumptables
1156      around the code.  */
1157   alloc_rbi_pool ();
1158
1159   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1160     initialize_bb_rbi (bb);
1161
1162   cfg_layout_rtl_register_cfg_hooks ();
1163
1164   record_effective_endpoints ();
1165
1166   cleanup_cfg (CLEANUP_CFGLAYOUT);
1167 }
1168
1169 /* Splits superblocks.  */
1170 void
1171 break_superblocks (void)
1172 {
1173   sbitmap superblocks;
1174   bool need = false;
1175   basic_block bb;
1176
1177   superblocks = sbitmap_alloc (last_basic_block);
1178   sbitmap_zero (superblocks);
1179
1180   FOR_EACH_BB (bb)
1181     if (bb->flags & BB_SUPERBLOCK)
1182       {
1183         bb->flags &= ~BB_SUPERBLOCK;
1184         SET_BIT (superblocks, bb->index);
1185         need = true;
1186       }
1187
1188   if (need)
1189     {
1190       rebuild_jump_labels (get_insns ());
1191       find_many_sub_basic_blocks (superblocks);
1192     }
1193
1194   free (superblocks);
1195 }
1196
1197 /* Finalize the changes: reorder insn list according to the sequence, enter
1198    compensation code, rebuild scope forest.  */
1199
1200 void
1201 cfg_layout_finalize (void)
1202 {
1203   basic_block bb;
1204
1205 #ifdef ENABLE_CHECKING
1206   verify_flow_info ();
1207 #endif
1208   rtl_register_cfg_hooks ();
1209   if (reload_completed
1210 #ifdef HAVE_epilogue
1211       && !HAVE_epilogue
1212 #endif
1213       )
1214     fixup_fallthru_exit_predecessor ();
1215   fixup_reorder_chain ();
1216
1217 #ifdef ENABLE_CHECKING
1218   verify_insn_chain ();
1219 #endif
1220
1221   free_rbi_pool ();
1222   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1223     bb->rbi = NULL;
1224
1225   break_superblocks ();
1226
1227 #ifdef ENABLE_CHECKING
1228   verify_flow_info ();
1229 #endif
1230 }
1231
1232 /* Checks whether all N blocks in BBS array can be copied.  */
1233 bool
1234 can_copy_bbs_p (basic_block *bbs, unsigned n)
1235 {
1236   unsigned i;
1237   edge e;
1238   int ret = true;
1239
1240   for (i = 0; i < n; i++)
1241     bbs[i]->rbi->duplicated = 1;
1242
1243   for (i = 0; i < n; i++)
1244     {
1245       /* In case we should redirect abnormal edge during duplication, fail.  */
1246       for (e = bbs[i]->succ; e; e = e->succ_next)
1247         if ((e->flags & EDGE_ABNORMAL)
1248             && e->dest->rbi->duplicated)
1249           {
1250             ret = false;
1251             goto end;
1252           }
1253
1254       if (!can_duplicate_block_p (bbs[i]))
1255         {
1256           ret = false;
1257           break;
1258         }
1259     }
1260
1261 end:
1262   for (i = 0; i < n; i++)
1263     bbs[i]->rbi->duplicated = 0;
1264
1265   return ret;
1266 }
1267
1268 /* Duplicates N basic blocks stored in array BBS.  Newly created basic blocks
1269    are placed into array NEW_BBS in the same order.  Edges from basic blocks
1270    in BBS are also duplicated and copies of those of them
1271    that lead into BBS are redirected to appropriate newly created block.  The
1272    function assigns bbs into loops (copy of basic block bb is assigned to
1273    bb->loop_father->copy loop, so this must be set up correctly in advance)
1274    and updates dominators locally (LOOPS structure that contains the information
1275    about dominators is passed to enable this).
1276
1277    BASE is the superloop to that basic block belongs; if its header or latch
1278    is copied, we do not set the new blocks as header or latch.
1279
1280    Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1281    also in the same order.  */
1282
1283 void
1284 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1285           edge *edges, unsigned n_edges, edge *new_edges,
1286           struct loop *base)
1287 {
1288   unsigned i, j;
1289   basic_block bb, new_bb, dom_bb;
1290   edge e;
1291
1292   /* Duplicate bbs, update dominators, assign bbs to loops.  */
1293   for (i = 0; i < n; i++)
1294     {
1295       /* Duplicate.  */
1296       bb = bbs[i];
1297       new_bb = new_bbs[i] = duplicate_block (bb, NULL);
1298       bb->rbi->duplicated = 1;
1299       /* Add to loop.  */
1300       add_bb_to_loop (new_bb, bb->loop_father->copy);
1301       /* Possibly set header.  */
1302       if (bb->loop_father->header == bb && bb->loop_father != base)
1303         new_bb->loop_father->header = new_bb;
1304       /* Or latch.  */
1305       if (bb->loop_father->latch == bb && bb->loop_father != base)
1306         new_bb->loop_father->latch = new_bb;
1307     }
1308
1309   /* Set dominators.  */
1310   for (i = 0; i < n; i++)
1311     {
1312       bb = bbs[i];
1313       new_bb = new_bbs[i];
1314
1315       dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1316       if (dom_bb->rbi->duplicated)
1317         {
1318           dom_bb = dom_bb->rbi->copy;
1319           set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1320         }
1321     }
1322
1323   /* Redirect edges.  */
1324   for (j = 0; j < n_edges; j++)
1325     new_edges[j] = NULL;
1326   for (i = 0; i < n; i++)
1327     {
1328       new_bb = new_bbs[i];
1329       bb = bbs[i];
1330
1331       for (e = new_bb->succ; e; e = e->succ_next)
1332         {
1333           for (j = 0; j < n_edges; j++)
1334             if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1335               new_edges[j] = e;
1336
1337           if (!e->dest->rbi->duplicated)
1338             continue;
1339           redirect_edge_and_branch_force (e, e->dest->rbi->copy);
1340         }
1341     }
1342
1343   /* Clear information about duplicates.  */
1344   for (i = 0; i < n; i++)
1345     bbs[i]->rbi->duplicated = 0;
1346 }
1347
1348 #include "gt-cfglayout.h"