gcc/cfglayout.c

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