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