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