OSDN Git Service

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