gcc/cfglayout.c

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