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 (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 (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 (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 (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 \f
 967 /* Return true in case it is possible to duplicate the basic block BB.  */
 968
 969 /* We do not want to declare the function in a header file, since it should
 970    only be used through the cfghooks interface, and we do not want to move
 971    it to cfgrtl.c since it would require also moving quite a lot of related
 972    code.  */
 973 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
 974
 975 bool
 976 cfg_layout_can_duplicate_bb_p (basic_block bb)
 977 {
 978   /* Do not attempt to duplicate tablejumps, as we need to unshare
 979      the dispatch table.  This is difficult to do, as the instructions
 980      computing jump destination may be hoisted outside the basic block.  */
 981   if (tablejump_p (BB_END (bb), NULL, NULL))
 982     return false;
 983
 984   /* Do not duplicate blocks containing insns that can't be copied.  */
 985   if (targetm.cannot_copy_insn_p)
 986     {
 987       rtx insn = BB_HEAD (bb);
 988       while (1)
 989         {
 990           if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
 991             return false;
 992           if (insn == BB_END (bb))
 993             break;
 994           insn = NEXT_INSN (insn);
 995         }
 996     }
 997
 998   return true;
 999 }
1000
1001 rtx
1002 duplicate_insn_chain (rtx from, rtx to)
1003 {
1004   rtx insn, last;
1005
1006   /* Avoid updating of boundaries of previous basic block.  The
1007      note will get removed from insn stream in fixup.  */
1008   last = emit_note (NOTE_INSN_DELETED);
1009
1010   /* Create copy at the end of INSN chain.  The chain will
1011      be reordered later.  */
1012   for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
1013     {
1014       switch (GET_CODE (insn))
1015         {
1016         case INSN:
1017         case CALL_INSN:
1018         case JUMP_INSN:
1019           /* Avoid copying of dispatch tables.  We never duplicate
1020              tablejumps, so this can hit only in case the table got
1021              moved far from original jump.  */
1022           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1023               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1024             break;
1025           emit_copy_of_insn_after (insn, get_last_insn ());
1026           break;
1027
1028         case CODE_LABEL:
1029           break;
1030
1031         case BARRIER:
1032           emit_barrier ();
1033           break;
1034
1035         case NOTE:
1036           switch (NOTE_KIND (insn))
1037             {
1038               /* In case prologue is empty and function contain label
1039                  in first BB, we may want to copy the block.  */
1040             case NOTE_INSN_PROLOGUE_END:
1041
1042             case NOTE_INSN_DELETED:
1043             case NOTE_INSN_DELETED_LABEL:
1044               /* No problem to strip these.  */
1045             case NOTE_INSN_EPILOGUE_BEG:
1046               /* Debug code expect these notes to exist just once.
1047                  Keep them in the master copy.
1048                  ??? It probably makes more sense to duplicate them for each
1049                  epilogue copy.  */
1050             case NOTE_INSN_FUNCTION_BEG:
1051               /* There is always just single entry to function.  */
1052             case NOTE_INSN_BASIC_BLOCK:
1053               break;
1054
1055             case NOTE_INSN_SWITCH_TEXT_SECTIONS:
1056               emit_note_copy (insn);
1057               break;
1058
1059             default:
1060               /* All other notes should have already been eliminated.
1061                */
1062               gcc_unreachable ();
1063             }
1064           break;
1065         default:
1066           gcc_unreachable ();
1067         }
1068     }
1069   insn = NEXT_INSN (last);
1070   delete_insn (last);
1071   return insn;
1072 }
1073 /* Create a duplicate of the basic block BB.  */
1074
1075 /* We do not want to declare the function in a header file, since it should
1076    only be used through the cfghooks interface, and we do not want to move
1077    it to cfgrtl.c since it would require also moving quite a lot of related
1078    code.  */
1079 extern basic_block cfg_layout_duplicate_bb (basic_block);
1080
1081 basic_block
1082 cfg_layout_duplicate_bb (basic_block bb)
1083 {
1084   rtx insn;
1085   basic_block new_bb;
1086
1087   insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1088   new_bb = create_basic_block (insn,
1089                                insn ? get_last_insn () : NULL,
1090                                EXIT_BLOCK_PTR->prev_bb);
1091
1092   BB_COPY_PARTITION (new_bb, bb);
1093   if (bb->il.rtl->header)
1094     {
1095       insn = bb->il.rtl->header;
1096       while (NEXT_INSN (insn))
1097         insn = NEXT_INSN (insn);
1098       insn = duplicate_insn_chain (bb->il.rtl->header, insn);
1099       if (insn)
1100         new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ());
1101     }
1102
1103   if (bb->il.rtl->footer)
1104     {
1105       insn = bb->il.rtl->footer;
1106       while (NEXT_INSN (insn))
1107         insn = NEXT_INSN (insn);
1108       insn = duplicate_insn_chain (bb->il.rtl->footer, insn);
1109       if (insn)
1110         new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ());
1111     }
1112
1113   return new_bb;
1114 }
1115
1116 \f
1117 /* Main entry point to this module - initialize the datastructures for
1118    CFG layout changes.  It keeps LOOPS up-to-date if not null.
1119
1120    FLAGS is a set of additional flags to pass to cleanup_cfg().  */
1121
1122 void
1123 cfg_layout_initialize (unsigned int flags)
1124 {
1125   rtx x;
1126   basic_block bb;
1127
1128   initialize_original_copy_tables ();
1129
1130   cfg_layout_rtl_register_cfg_hooks ();
1131
1132   record_effective_endpoints ();
1133
1134   /* Make sure that the targets of non local gotos are marked.  */
1135   for (x = nonlocal_goto_handler_labels; x; x = XEXP (x, 1))
1136     {
1137       bb = BLOCK_FOR_INSN (XEXP (x, 0));
1138       bb->flags |= BB_NON_LOCAL_GOTO_TARGET;
1139     }
1140
1141   cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
1142 }
1143
1144 /* Splits superblocks.  */
1145 void
1146 break_superblocks (void)
1147 {
1148   sbitmap superblocks;
1149   bool need = false;
1150   basic_block bb;
1151
1152   superblocks = sbitmap_alloc (last_basic_block);
1153   sbitmap_zero (superblocks);
1154
1155   FOR_EACH_BB (bb)
1156     if (bb->flags & BB_SUPERBLOCK)
1157       {
1158         bb->flags &= ~BB_SUPERBLOCK;
1159         SET_BIT (superblocks, bb->index);
1160         need = true;
1161       }
1162
1163   if (need)
1164     {
1165       rebuild_jump_labels (get_insns ());
1166       find_many_sub_basic_blocks (superblocks);
1167     }
1168
1169   free (superblocks);
1170 }
1171
1172 /* Finalize the changes: reorder insn list according to the sequence specified
1173    by aux pointers, enter compensation code, rebuild scope forest.  */
1174
1175 void
1176 cfg_layout_finalize (void)
1177 {
1178 #ifdef ENABLE_CHECKING
1179   verify_flow_info ();
1180 #endif
1181   rtl_register_cfg_hooks ();
1182   if (reload_completed
1183 #ifdef HAVE_epilogue
1184       && !HAVE_epilogue
1185 #endif
1186       )
1187     fixup_fallthru_exit_predecessor ();
1188   fixup_reorder_chain ();
1189
1190   rebuild_jump_labels (get_insns ());
1191   delete_dead_jumptables ();
1192
1193 #ifdef ENABLE_CHECKING
1194   verify_insn_chain ();
1195   verify_flow_info ();
1196 #endif
1197 }
1198
1199 /* Checks whether all N blocks in BBS array can be copied.  */
1200 bool
1201 can_copy_bbs_p (basic_block *bbs, unsigned n)
1202 {
1203   unsigned i;
1204   edge e;
1205   int ret = true;
1206
1207   for (i = 0; i < n; i++)
1208     bbs[i]->flags |= BB_DUPLICATED;
1209
1210   for (i = 0; i < n; i++)
1211     {
1212       /* In case we should redirect abnormal edge during duplication, fail.  */
1213       edge_iterator ei;
1214       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1215         if ((e->flags & EDGE_ABNORMAL)
1216             && (e->dest->flags & BB_DUPLICATED))
1217           {
1218             ret = false;
1219             goto end;
1220           }
1221
1222       if (!can_duplicate_block_p (bbs[i]))
1223         {
1224           ret = false;
1225           break;
1226         }
1227     }
1228
1229 end:
1230   for (i = 0; i < n; i++)
1231     bbs[i]->flags &= ~BB_DUPLICATED;
1232
1233   return ret;
1234 }
1235
1236 /* Duplicates N basic blocks stored in array BBS.  Newly created basic blocks
1237    are placed into array NEW_BBS in the same order.  Edges from basic blocks
1238    in BBS are also duplicated and copies of those of them
1239    that lead into BBS are redirected to appropriate newly created block.  The
1240    function assigns bbs into loops (copy of basic block bb is assigned to
1241    bb->loop_father->copy loop, so this must be set up correctly in advance)
1242    and updates dominators locally (LOOPS structure that contains the information
1243    about dominators is passed to enable this).
1244
1245    BASE is the superloop to that basic block belongs; if its header or latch
1246    is copied, we do not set the new blocks as header or latch.
1247
1248    Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1249    also in the same order.
1250
1251    Newly created basic blocks are put after the basic block AFTER in the
1252    instruction stream, and the order of the blocks in BBS array is preserved.  */
1253
1254 void
1255 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1256           edge *edges, unsigned num_edges, edge *new_edges,
1257           struct loop *base, basic_block after)
1258 {
1259   unsigned i, j;
1260   basic_block bb, new_bb, dom_bb;
1261   edge e;
1262
1263   /* Duplicate bbs, update dominators, assign bbs to loops.  */
1264   for (i = 0; i < n; i++)
1265     {
1266       /* Duplicate.  */
1267       bb = bbs[i];
1268       new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1269       after = new_bb;
1270       bb->flags |= BB_DUPLICATED;
1271       /* Possibly set loop header.  */
1272       if (bb->loop_father->header == bb && bb->loop_father != base)
1273         new_bb->loop_father->header = new_bb;
1274       /* Or latch.  */
1275       if (bb->loop_father->latch == bb && bb->loop_father != base)
1276         new_bb->loop_father->latch = new_bb;
1277     }
1278
1279   /* Set dominators.  */
1280   for (i = 0; i < n; i++)
1281     {
1282       bb = bbs[i];
1283       new_bb = new_bbs[i];
1284
1285       dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1286       if (dom_bb->flags & BB_DUPLICATED)
1287         {
1288           dom_bb = get_bb_copy (dom_bb);
1289           set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1290         }
1291     }
1292
1293   /* Redirect edges.  */
1294   for (j = 0; j < num_edges; j++)
1295     new_edges[j] = NULL;
1296   for (i = 0; i < n; i++)
1297     {
1298       edge_iterator ei;
1299       new_bb = new_bbs[i];
1300       bb = bbs[i];
1301
1302       FOR_EACH_EDGE (e, ei, new_bb->succs)
1303         {
1304           for (j = 0; j < num_edges; j++)
1305             if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1306               new_edges[j] = e;
1307
1308           if (!(e->dest->flags & BB_DUPLICATED))
1309             continue;
1310           redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1311         }
1312     }
1313
1314   /* Clear information about duplicates.  */
1315   for (i = 0; i < n; i++)
1316     bbs[i]->flags &= ~BB_DUPLICATED;
1317 }
1318
1319 #include "gt-cfglayout.h"