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_KIND (insn))
 102             {
 103             case NOTE_INSN_BLOCK_END:
 104               gcc_unreachable ();
 105               continue;
 106             default:
 107               continue;
 108               break;
 109             }
 110           break;
 111
 112         case CODE_LABEL:
 113           if (NEXT_INSN (insn)
 114               && JUMP_P (NEXT_INSN (insn))
 115               && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
 116                   || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
 117             {
 118               insn = NEXT_INSN (insn);
 119               last_insn = insn;
 120               continue;
 121             }
 122           break;
 123
 124         default:
 125           break;
 126         }
 127
 128       break;
 129     }
 130
 131   /* It is possible to hit contradictory sequence.  For instance:
 132
 133      jump_insn
 134      NOTE_INSN_BLOCK_BEG
 135      barrier
 136
 137      Where barrier belongs to jump_insn, but the note does not.  This can be
 138      created by removing the basic block originally following
 139      NOTE_INSN_BLOCK_BEG.  In such case reorder the notes.  */
 140
 141   for (insn = last_insn; insn != BB_END (bb); insn = prev)
 142     {
 143       prev = PREV_INSN (insn);
 144       if (NOTE_P (insn))
 145         switch (NOTE_KIND (insn))
 146           {
 147           case NOTE_INSN_BLOCK_END:
 148             gcc_unreachable ();
 149             break;
 150           case NOTE_INSN_DELETED:
 151           case NOTE_INSN_DELETED_LABEL:
 152             continue;
 153           default:
 154             reorder_insns (insn, insn, last_insn);
 155           }
 156     }
 157
 158   return last_insn;
 159 }
 160
 161 /* Locate or create a label for a given basic block.  */
 162
 163 static rtx
 164 label_for_bb (basic_block bb)
 165 {
 166   rtx label = BB_HEAD (bb);
 167
 168   if (!LABEL_P (label))
 169     {
 170       if (dump_file)
 171         fprintf (dump_file, "Emitting label for block %d\n", bb->index);
 172
 173       label = block_label (bb);
 174     }
 175
 176   return label;
 177 }
 178
 179 /* Locate the effective beginning and end of the insn chain for each
 180    block, as defined by skip_insns_after_block above.  */
 181
 182 static void
 183 record_effective_endpoints (void)
 184 {
 185   rtx next_insn;
 186   basic_block bb;
 187   rtx insn;
 188
 189   for (insn = get_insns ();
 190        insn
 191        && NOTE_P (insn)
 192        && NOTE_KIND (insn) != NOTE_INSN_BASIC_BLOCK;
 193        insn = NEXT_INSN (insn))
 194     continue;
 195   /* No basic blocks at all?  */
 196   gcc_assert (insn);
 197
 198   if (PREV_INSN (insn))
 199     cfg_layout_function_header =
 200             unlink_insn_chain (get_insns (), PREV_INSN (insn));
 201   else
 202     cfg_layout_function_header = NULL_RTX;
 203
 204   next_insn = get_insns ();
 205   FOR_EACH_BB (bb)
 206     {
 207       rtx end;
 208
 209       if (PREV_INSN (BB_HEAD (bb)) && next_insn != BB_HEAD (bb))
 210         bb->il.rtl->header = unlink_insn_chain (next_insn,
 211                                               PREV_INSN (BB_HEAD (bb)));
 212       end = skip_insns_after_block (bb);
 213       if (NEXT_INSN (BB_END (bb)) && BB_END (bb) != end)
 214         bb->il.rtl->footer = unlink_insn_chain (NEXT_INSN (BB_END (bb)), end);
 215       next_insn = NEXT_INSN (BB_END (bb));
 216     }
 217
 218   cfg_layout_function_footer = next_insn;
 219   if (cfg_layout_function_footer)
 220     cfg_layout_function_footer = unlink_insn_chain (cfg_layout_function_footer, get_last_insn ());
 221 }
 222 \f
 223 /* Data structures representing mapping of INSN_LOCATOR into scope blocks, line
 224    numbers and files.  In order to be GGC friendly we need to use separate
 225    varrays.  This also slightly improve the memory locality in binary search.
 226    The _locs array contains locators where the given property change.  The
 227    block_locators_blocks contains the scope block that is used for all insn
 228    locator greater than corresponding block_locators_locs value and smaller
 229    than the following one.  Similarly for the other properties.  */
 230 static VEC(int,heap) *block_locators_locs;
 231 static GTY(()) VEC(tree,gc) *block_locators_blocks;
 232 static VEC(int,heap) *locations_locators_locs;
 233 DEF_VEC_O(location_t);
 234 DEF_VEC_ALLOC_O(location_t,heap);
 235 static VEC(location_t,heap) *locations_locators_vals;
 236 int prologue_locator;
 237 int epilogue_locator;
 238
 239 /* Hold current location information and last location information, so the
 240    datastructures are built lazilly only when some instructions in given
 241    place are needed.  */
 242 location_t curr_location, last_location;
 243 static tree curr_block, last_block;
 244 static int curr_rtl_loc = -1;
 245
 246 /* Allocate insn locator datastructure.  */
 247 void
 248 insn_locators_alloc (void)
 249 {
 250   prologue_locator = epilogue_locator = 0;
 251
 252   block_locators_locs = VEC_alloc (int, heap, 32);
 253   block_locators_blocks = VEC_alloc (tree, gc, 32);
 254   locations_locators_locs = VEC_alloc (int, heap, 32);
 255   locations_locators_vals = VEC_alloc (location_t, heap, 32);
 256
 257 #ifdef USE_MAPPED_LOCATION
 258   last_location = -1;
 259   curr_location = -1;
 260 #else
 261   last_location.line = -1;
 262   curr_location.line = -1;
 263 #endif
 264   curr_block = NULL;
 265   last_block = NULL;
 266   curr_rtl_loc = 0;
 267 }
 268
 269 /* At the end of emit stage, clear current location.  */
 270 void
 271 insn_locators_finalize (void)
 272 {
 273   if (curr_rtl_loc >= 0)
 274     epilogue_locator = curr_insn_locator ();
 275   curr_rtl_loc = -1;
 276 }
 277
 278 /* Set current location.  */
 279 void
 280 set_curr_insn_source_location (location_t location)
 281 {
 282   /* IV opts calls into RTL expansion to compute costs of operations.  At this
 283      time locators are not initialized.  */
 284   if (curr_rtl_loc == -1)
 285     return;
 286 #ifdef USE_MAPPED_LOCATION
 287   if (location == last_location)
 288     return;
 289 #else
 290   if (location.file && last_location.file
 291       && !strcmp (location.file, last_location.file)
 292       && location.line == last_location.line)
 293     return;
 294 #endif
 295   curr_location = location;
 296 }
 297
 298 /* Set current scope block. */
 299 void
 300 set_curr_insn_block (tree b)
 301 {
 302   /* IV opts calls into RTL expansion to compute costs of operations.  At this
 303      time locators are not initialized.  */
 304   if (curr_rtl_loc == -1)
 305     return;
 306   if (b)
 307     curr_block = b;
 308 }
 309
 310 /* Return current insn locator.  */
 311 int
 312 curr_insn_locator (void)
 313 {
 314   if (curr_rtl_loc == -1)
 315     return 0;
 316   if (last_block != curr_block)
 317     {
 318       curr_rtl_loc++;
 319       VEC_safe_push (int, heap, block_locators_locs, curr_rtl_loc);
 320       VEC_safe_push (tree, gc, block_locators_blocks, curr_block);
 321       last_block = curr_block;
 322     }
 323 #ifdef USE_MAPPED_LOCATION
 324   if (last_location != curr_location)
 325 #else
 326   if (last_location.file != curr_location.file
 327       || last_location.line != curr_location.line)
 328 #endif
 329     {
 330       curr_rtl_loc++;
 331       VEC_safe_push (int, heap, locations_locators_locs, curr_rtl_loc);
 332       VEC_safe_push (location_t, heap, locations_locators_vals, &curr_location);
 333       last_location = curr_location;
 334     }
 335   return curr_rtl_loc;
 336 }
 337
 338 static unsigned int
 339 into_cfg_layout_mode (void)
 340 {
 341   cfg_layout_initialize (0);
 342   return 0;
 343 }
 344
 345 static unsigned int
 346 outof_cfg_layout_mode (void)
 347 {
 348   basic_block bb;
 349
 350   FOR_EACH_BB (bb)
 351     if (bb->next_bb != EXIT_BLOCK_PTR)
 352       bb->aux = bb->next_bb;
 353
 354   cfg_layout_finalize ();
 355
 356   return 0;
 357 }
 358
 359 struct tree_opt_pass pass_into_cfg_layout_mode =
 360 {
 361   "into_cfglayout",                     /* name */
 362   NULL,                                 /* gate */
 363   into_cfg_layout_mode,                 /* execute */
 364   NULL,                                 /* sub */
 365   NULL,                                 /* next */
 366   0,                                    /* static_pass_number */
 367   0,                                    /* tv_id */
 368   0,                                    /* properties_required */
 369   0,                                    /* properties_provided */
 370   0,                                    /* properties_destroyed */
 371   0,                                    /* todo_flags_start */
 372   TODO_dump_func,                       /* todo_flags_finish */
 373   0                                     /* letter */
 374 };
 375
 376 struct tree_opt_pass pass_outof_cfg_layout_mode =
 377 {
 378   "outof_cfglayout",                    /* name */
 379   NULL,                                 /* gate */
 380   outof_cfg_layout_mode,                /* execute */
 381   NULL,                                 /* sub */
 382   NULL,                                 /* next */
 383   0,                                    /* static_pass_number */
 384   0,                                    /* tv_id */
 385   0,                                    /* properties_required */
 386   0,                                    /* properties_provided */
 387   0,                                    /* properties_destroyed */
 388   0,                                    /* todo_flags_start */
 389   TODO_dump_func,                       /* todo_flags_finish */
 390   0                                     /* letter */
 391 };
 392 \f
 393 /* Return sope resulting from combination of S1 and S2.  */
 394 static tree
 395 choose_inner_scope (tree s1, tree s2)
 396 {
 397    if (!s1)
 398      return s2;
 399    if (!s2)
 400      return s1;
 401    if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
 402      return s1;
 403    return s2;
 404 }
 405 \f
 406 /* Emit lexical block notes needed to change scope from S1 to S2.  */
 407
 408 static void
 409 change_scope (rtx orig_insn, tree s1, tree s2)
 410 {
 411   rtx insn = orig_insn;
 412   tree com = NULL_TREE;
 413   tree ts1 = s1, ts2 = s2;
 414   tree s;
 415
 416   while (ts1 != ts2)
 417     {
 418       gcc_assert (ts1 && ts2);
 419       if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
 420         ts1 = BLOCK_SUPERCONTEXT (ts1);
 421       else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
 422         ts2 = BLOCK_SUPERCONTEXT (ts2);
 423       else
 424         {
 425           ts1 = BLOCK_SUPERCONTEXT (ts1);
 426           ts2 = BLOCK_SUPERCONTEXT (ts2);
 427         }
 428     }
 429   com = ts1;
 430
 431   /* Close scopes.  */
 432   s = s1;
 433   while (s != com)
 434     {
 435       rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
 436       NOTE_BLOCK (note) = s;
 437       s = BLOCK_SUPERCONTEXT (s);
 438     }
 439
 440   /* Open scopes.  */
 441   s = s2;
 442   while (s != com)
 443     {
 444       insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
 445       NOTE_BLOCK (insn) = s;
 446       s = BLOCK_SUPERCONTEXT (s);
 447     }
 448 }
 449
 450 /* Return lexical scope block insn belong to.  */
 451 static tree
 452 insn_scope (rtx insn)
 453 {
 454   int max = VEC_length (int, block_locators_locs);
 455   int min = 0;
 456   int loc = INSN_LOCATOR (insn);
 457
 458   /* When block_locators_locs was initialized, the pro- and epilogue
 459      insns didn't exist yet and can therefore not be found this way.
 460      But we know that they belong to the outer most block of the
 461      current function.
 462      Without this test, the prologue would be put inside the block of
 463      the first valid instruction in the function and when that first
 464      insn is part of an inlined function then the low_pc of that
 465      inlined function is messed up.  Likewise for the epilogue and
 466      the last valid instruction.  */
 467   if (loc == prologue_locator || loc == epilogue_locator)
 468     return DECL_INITIAL (cfun->decl);
 469
 470   if (!max || !loc)
 471     return NULL;
 472   while (1)
 473     {
 474       int pos = (min + max) / 2;
 475       int tmp = VEC_index (int, block_locators_locs, pos);
 476
 477       if (tmp <= loc && min != pos)
 478         min = pos;
 479       else if (tmp > loc && max != pos)
 480         max = pos;
 481       else
 482         {
 483           min = pos;
 484           break;
 485         }
 486     }
 487   return VEC_index (tree, block_locators_blocks, min);
 488 }
 489
 490 /* Return line number of the statement specified by the locator.  */
 491 static location_t
 492 locator_location (int loc)
 493 {
 494   int max = VEC_length (int, locations_locators_locs);
 495   int min = 0;
 496
 497   while (1)
 498     {
 499       int pos = (min + max) / 2;
 500       int tmp = VEC_index (int, locations_locators_locs, pos);
 501
 502       if (tmp <= loc && min != pos)
 503         min = pos;
 504       else if (tmp > loc && max != pos)
 505         max = pos;
 506       else
 507         {
 508           min = pos;
 509           break;
 510         }
 511     }
 512   return *VEC_index (location_t, locations_locators_vals, min);
 513 }
 514
 515 /* Return source line of the statement that produced this insn.  */
 516 int
 517 locator_line (int loc)
 518 {
 519   expanded_location xloc;
 520   if (!loc)
 521     return 0;
 522   else
 523     xloc = expand_location (locator_location (loc));
 524   return xloc.line;
 525 }
 526
 527 /* Return line number of the statement that produced this insn.  */
 528 int
 529 insn_line (rtx insn)
 530 {
 531   return locator_line (INSN_LOCATOR (insn));
 532 }
 533
 534 /* Return source file of the statement specified by LOC.  */
 535 const char *
 536 locator_file (int loc)
 537 {
 538   expanded_location xloc;
 539   if (!loc)
 540     return 0;
 541   else
 542     xloc = expand_location (locator_location (loc));
 543   return xloc.file;
 544 }
 545
 546 /* Return source file of the statement that produced this insn.  */
 547 const char *
 548 insn_file (rtx insn)
 549 {
 550   return locator_file (INSN_LOCATOR (insn));
 551 }
 552
 553 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
 554    on the scope tree and the newly reordered instructions.  */
 555
 556 void
 557 reemit_insn_block_notes (void)
 558 {
 559   tree cur_block = DECL_INITIAL (cfun->decl);
 560   rtx insn, note;
 561
 562   insn = get_insns ();
 563   if (!active_insn_p (insn))
 564     insn = next_active_insn (insn);
 565   for (; insn; insn = next_active_insn (insn))
 566     {
 567       tree this_block;
 568
 569       /* Avoid putting scope notes between jump table and its label.  */
 570       if (JUMP_P (insn)
 571           && (GET_CODE (PATTERN (insn)) == ADDR_VEC
 572               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
 573         continue;
 574
 575       this_block = insn_scope (insn);
 576       /* For sequences compute scope resulting from merging all scopes
 577          of instructions nested inside.  */
 578       if (GET_CODE (PATTERN (insn)) == SEQUENCE)
 579         {
 580           int i;
 581           rtx body = PATTERN (insn);
 582
 583           this_block = NULL;
 584           for (i = 0; i < XVECLEN (body, 0); i++)
 585             this_block = choose_inner_scope (this_block,
 586                                          insn_scope (XVECEXP (body, 0, i)));
 587         }
 588       if (! this_block)
 589         continue;
 590
 591       if (this_block != cur_block)
 592         {
 593           change_scope (insn, cur_block, this_block);
 594           cur_block = this_block;
 595         }
 596     }
 597
 598   /* change_scope emits before the insn, not after.  */
 599   note = emit_note (NOTE_INSN_DELETED);
 600   change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
 601   delete_insn (note);
 602
 603   reorder_blocks ();
 604 }
 605 \f
 606
 607 /* Link the basic blocks in the correct order, compacting the basic
 608    block queue while at it.  This also clears the visited flag on
 609    all basic blocks.  If STAY_IN_CFGLAYOUT_MODE is false, this function
 610    also clears the basic block header and footer fields.
 611
 612    This function is usually called after a pass (e.g. tracer) finishes
 613    some transformations while in cfglayout mode.  The required sequence
 614    of the basic blocks is in a linked list along the bb->aux field.
 615    This functions re-links the basic block prev_bb and next_bb pointers
 616    accordingly, and it compacts and renumbers the blocks.  */
 617
 618 void
 619 relink_block_chain (bool stay_in_cfglayout_mode)
 620 {
 621   basic_block bb, prev_bb;
 622   int index;
 623
 624   /* Maybe dump the re-ordered sequence.  */
 625   if (dump_file)
 626     {
 627       fprintf (dump_file, "Reordered sequence:\n");
 628       for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
 629            bb;
 630            bb = bb->aux, index++)
 631         {
 632           fprintf (dump_file, " %i ", index);
 633           if (get_bb_original (bb))
 634             fprintf (dump_file, "duplicate of %i ",
 635                      get_bb_original (bb)->index);
 636           else if (forwarder_block_p (bb)
 637                    && !LABEL_P (BB_HEAD (bb)))
 638             fprintf (dump_file, "compensation ");
 639           else
 640             fprintf (dump_file, "bb %i ", bb->index);
 641           fprintf (dump_file, " [%i]\n", bb->frequency);
 642         }
 643     }
 644
 645   /* Now reorder the blocks.  */
 646   prev_bb = ENTRY_BLOCK_PTR;
 647   bb = ENTRY_BLOCK_PTR->next_bb;
 648   for (; bb; prev_bb = bb, bb = bb->aux)
 649     {
 650       bb->prev_bb = prev_bb;
 651       prev_bb->next_bb = bb;
 652     }
 653   prev_bb->next_bb = EXIT_BLOCK_PTR;
 654   EXIT_BLOCK_PTR->prev_bb = prev_bb;
 655
 656   /* Then, clean up the aux and visited fields.  */
 657   FOR_ALL_BB (bb)
 658     {
 659       bb->aux = NULL;
 660       bb->il.rtl->visited = 0;
 661       if (!stay_in_cfglayout_mode)
 662         bb->il.rtl->header = bb->il.rtl->footer = NULL;
 663     }
 664
 665   /* Maybe reset the original copy tables, they are not valid anymore
 666      when we renumber the basic blocks in compact_blocks.  If we are
 667      are going out of cfglayout mode, don't re-allocate the tables.  */
 668   free_original_copy_tables ();
 669   if (stay_in_cfglayout_mode)
 670     initialize_original_copy_tables ();
 671
 672   /* Finally, put basic_block_info in the new order.  */
 673   compact_blocks ();
 674 }
 675 \f
 676
 677 /* Given a reorder chain, rearrange the code to match.  */
 678
 679 static void
 680 fixup_reorder_chain (void)
 681 {
 682   basic_block bb;
 683   rtx insn = NULL;
 684
 685   if (cfg_layout_function_header)
 686     {
 687       set_first_insn (cfg_layout_function_header);
 688       insn = cfg_layout_function_header;
 689       while (NEXT_INSN (insn))
 690         insn = NEXT_INSN (insn);
 691     }
 692
 693   /* First do the bulk reordering -- rechain the blocks without regard to
 694      the needed changes to jumps and labels.  */
 695
 696   for (bb = ENTRY_BLOCK_PTR->next_bb; bb; bb = bb->aux)
 697     {
 698       if (bb->il.rtl->header)
 699         {
 700           if (insn)
 701             NEXT_INSN (insn) = bb->il.rtl->header;
 702           else
 703             set_first_insn (bb->il.rtl->header);
 704           PREV_INSN (bb->il.rtl->header) = insn;
 705           insn = bb->il.rtl->header;
 706           while (NEXT_INSN (insn))
 707             insn = NEXT_INSN (insn);
 708         }
 709       if (insn)
 710         NEXT_INSN (insn) = BB_HEAD (bb);
 711       else
 712         set_first_insn (BB_HEAD (bb));
 713       PREV_INSN (BB_HEAD (bb)) = insn;
 714       insn = BB_END (bb);
 715       if (bb->il.rtl->footer)
 716         {
 717           NEXT_INSN (insn) = bb->il.rtl->footer;
 718           PREV_INSN (bb->il.rtl->footer) = insn;
 719           while (NEXT_INSN (insn))
 720             insn = NEXT_INSN (insn);
 721         }
 722     }
 723
 724   NEXT_INSN (insn) = cfg_layout_function_footer;
 725   if (cfg_layout_function_footer)
 726     PREV_INSN (cfg_layout_function_footer) = insn;
 727
 728   while (NEXT_INSN (insn))
 729     insn = NEXT_INSN (insn);
 730
 731   set_last_insn (insn);
 732 #ifdef ENABLE_CHECKING
 733   verify_insn_chain ();
 734 #endif
 735
 736   /* Now add jumps and labels as needed to match the blocks new
 737      outgoing edges.  */
 738
 739   for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->aux)
 740     {
 741       edge e_fall, e_taken, e;
 742       rtx bb_end_insn;
 743       basic_block nb;
 744       edge_iterator ei;
 745
 746       if (EDGE_COUNT (bb->succs) == 0)
 747         continue;
 748
 749       /* Find the old fallthru edge, and another non-EH edge for
 750          a taken jump.  */
 751       e_taken = e_fall = NULL;
 752
 753       FOR_EACH_EDGE (e, ei, bb->succs)
 754         if (e->flags & EDGE_FALLTHRU)
 755           e_fall = e;
 756         else if (! (e->flags & EDGE_EH))
 757           e_taken = e;
 758
 759       bb_end_insn = BB_END (bb);
 760       if (JUMP_P (bb_end_insn))
 761         {
 762           if (any_condjump_p (bb_end_insn))
 763             {
 764               /* If the old fallthru is still next, nothing to do.  */
 765               if (bb->aux == e_fall->dest
 766                   || e_fall->dest == EXIT_BLOCK_PTR)
 767                 continue;
 768
 769               /* The degenerated case of conditional jump jumping to the next
 770                  instruction can happen for jumps with side effects.  We need
 771                  to construct a forwarder block and this will be done just
 772                  fine by force_nonfallthru below.  */
 773               if (!e_taken)
 774                 ;
 775
 776               /* There is another special case: if *neither* block is next,
 777                  such as happens at the very end of a function, then we'll
 778                  need to add a new unconditional jump.  Choose the taken
 779                  edge based on known or assumed probability.  */
 780               else if (bb->aux != e_taken->dest)
 781                 {
 782                   rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
 783
 784                   if (note
 785                       && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
 786                       && invert_jump (bb_end_insn,
 787                                       (e_fall->dest == EXIT_BLOCK_PTR
 788                                        ? NULL_RTX
 789                                        : label_for_bb (e_fall->dest)), 0))
 790                     {
 791                       e_fall->flags &= ~EDGE_FALLTHRU;
 792 #ifdef ENABLE_CHECKING
 793                       gcc_assert (could_fall_through
 794                                   (e_taken->src, e_taken->dest));
 795 #endif
 796                       e_taken->flags |= EDGE_FALLTHRU;
 797                       update_br_prob_note (bb);
 798                       e = e_fall, e_fall = e_taken, e_taken = e;
 799                     }
 800                 }
 801
 802               /* If the "jumping" edge is a crossing edge, and the fall
 803                  through edge is non-crossing, leave things as they are.  */
 804               else if ((e_taken->flags & EDGE_CROSSING)
 805                        && !(e_fall->flags & EDGE_CROSSING))
 806                 continue;
 807
 808               /* Otherwise we can try to invert the jump.  This will
 809                  basically never fail, however, keep up the pretense.  */
 810               else if (invert_jump (bb_end_insn,
 811                                     (e_fall->dest == EXIT_BLOCK_PTR
 812                                      ? NULL_RTX
 813                                      : label_for_bb (e_fall->dest)), 0))
 814                 {
 815                   e_fall->flags &= ~EDGE_FALLTHRU;
 816 #ifdef ENABLE_CHECKING
 817                   gcc_assert (could_fall_through
 818                               (e_taken->src, e_taken->dest));
 819 #endif
 820                   e_taken->flags |= EDGE_FALLTHRU;
 821                   update_br_prob_note (bb);
 822                   continue;
 823                 }
 824             }
 825           else
 826             {
 827               /* Otherwise we have some return, switch or computed
 828                  jump.  In the 99% case, there should not have been a
 829                  fallthru edge.  */
 830               gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
 831               continue;
 832             }
 833         }
 834       else
 835         {
 836           /* No fallthru implies a noreturn function with EH edges, or
 837              something similarly bizarre.  In any case, we don't need to
 838              do anything.  */
 839           if (! e_fall)
 840             continue;
 841
 842           /* If the fallthru block is still next, nothing to do.  */
 843           if (bb->aux == e_fall->dest)
 844             continue;
 845
 846           /* A fallthru to exit block.  */
 847           if (e_fall->dest == EXIT_BLOCK_PTR)
 848             continue;
 849         }
 850
 851       /* We got here if we need to add a new jump insn.  */
 852       nb = force_nonfallthru (e_fall);
 853       if (nb)
 854         {
 855           nb->il.rtl->visited = 1;
 856           nb->aux = bb->aux;
 857           bb->aux = nb;
 858           /* Don't process this new block.  */
 859           bb = nb;
 860
 861           /* Make sure new bb is tagged for correct section (same as
 862              fall-thru source, since you cannot fall-throu across
 863              section boundaries).  */
 864           BB_COPY_PARTITION (e_fall->src, single_pred (bb));
 865           if (flag_reorder_blocks_and_partition
 866               && targetm.have_named_sections
 867               && JUMP_P (BB_END (bb))
 868               && !any_condjump_p (BB_END (bb))
 869               && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
 870             REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
 871               (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
 872         }
 873     }
 874
 875   relink_block_chain (/*stay_in_cfglayout_mode=*/false);
 876
 877   /* Annoying special case - jump around dead jumptables left in the code.  */
 878   FOR_EACH_BB (bb)
 879     {
 880       edge e;
 881       edge_iterator ei;
 882
 883       FOR_EACH_EDGE (e, ei, bb->succs)
 884         if (e->flags & EDGE_FALLTHRU)
 885           break;
 886
 887       if (e && !can_fallthru (e->src, e->dest))
 888         force_nonfallthru (e);
 889     }
 890 }
 891 \f
 892 /* Perform sanity checks on the insn chain.
 893    1. Check that next/prev pointers are consistent in both the forward and
 894       reverse direction.
 895    2. Count insns in chain, going both directions, and check if equal.
 896    3. Check that get_last_insn () returns the actual end of chain.  */
 897
 898 void
 899 verify_insn_chain (void)
 900 {
 901   rtx x, prevx, nextx;
 902   int insn_cnt1, insn_cnt2;
 903
 904   for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
 905        x != 0;
 906        prevx = x, insn_cnt1++, x = NEXT_INSN (x))
 907     gcc_assert (PREV_INSN (x) == prevx);
 908
 909   gcc_assert (prevx == get_last_insn ());
 910
 911   for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
 912        x != 0;
 913        nextx = x, insn_cnt2++, x = PREV_INSN (x))
 914     gcc_assert (NEXT_INSN (x) == nextx);
 915
 916   gcc_assert (insn_cnt1 == insn_cnt2);
 917 }
 918 \f
 919 /* If we have assembler epilogues, the block falling through to exit must
 920    be the last one in the reordered chain when we reach final.  Ensure
 921    that this condition is met.  */
 922 static void
 923 fixup_fallthru_exit_predecessor (void)
 924 {
 925   edge e;
 926   edge_iterator ei;
 927   basic_block bb = NULL;
 928
 929   /* This transformation is not valid before reload, because we might
 930      separate a call from the instruction that copies the return
 931      value.  */
 932   gcc_assert (reload_completed);
 933
 934   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 935     if (e->flags & EDGE_FALLTHRU)
 936       bb = e->src;
 937
 938   if (bb && bb->aux)
 939     {
 940       basic_block c = ENTRY_BLOCK_PTR->next_bb;
 941
 942       /* If the very first block is the one with the fall-through exit
 943          edge, we have to split that block.  */
 944       if (c == bb)
 945         {
 946           bb = split_block (bb, NULL)->dest;
 947           bb->aux = c->aux;
 948           c->aux = bb;
 949           bb->il.rtl->footer = c->il.rtl->footer;
 950           c->il.rtl->footer = NULL;
 951         }
 952
 953       while (c->aux != bb)
 954         c = c->aux;
 955
 956       c->aux = bb->aux;
 957       while (c->aux)
 958         c = c->aux;
 959
 960       c->aux = bb;
 961       bb->aux = NULL;
 962     }
 963 }
 964 \f
 965 /* Return true in case it is possible to duplicate the basic block BB.  */
 966
 967 /* We do not want to declare the function in a header file, since it should
 968    only be used through the cfghooks interface, and we do not want to move
 969    it to cfgrtl.c since it would require also moving quite a lot of related
 970    code.  */
 971 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
 972
 973 bool
 974 cfg_layout_can_duplicate_bb_p (basic_block bb)
 975 {
 976   /* Do not attempt to duplicate tablejumps, as we need to unshare
 977      the dispatch table.  This is difficult to do, as the instructions
 978      computing jump destination may be hoisted outside the basic block.  */
 979   if (tablejump_p (BB_END (bb), NULL, NULL))
 980     return false;
 981
 982   /* Do not duplicate blocks containing insns that can't be copied.  */
 983   if (targetm.cannot_copy_insn_p)
 984     {
 985       rtx insn = BB_HEAD (bb);
 986       while (1)
 987         {
 988           if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
 989             return false;
 990           if (insn == BB_END (bb))
 991             break;
 992           insn = NEXT_INSN (insn);
 993         }
 994     }
 995
 996   return true;
 997 }
 998
 999 rtx
1000 duplicate_insn_chain (rtx from, rtx to)
1001 {
1002   rtx insn, last;
1003
1004   /* Avoid updating of boundaries of previous basic block.  The
1005      note will get removed from insn stream in fixup.  */
1006   last = emit_note (NOTE_INSN_DELETED);
1007
1008   /* Create copy at the end of INSN chain.  The chain will
1009      be reordered later.  */
1010   for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
1011     {
1012       switch (GET_CODE (insn))
1013         {
1014         case INSN:
1015         case CALL_INSN:
1016         case JUMP_INSN:
1017           /* Avoid copying of dispatch tables.  We never duplicate
1018              tablejumps, so this can hit only in case the table got
1019              moved far from original jump.  */
1020           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1021               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1022             break;
1023           emit_copy_of_insn_after (insn, get_last_insn ());
1024           break;
1025
1026         case CODE_LABEL:
1027           break;
1028
1029         case BARRIER:
1030           emit_barrier ();
1031           break;
1032
1033         case NOTE:
1034           switch (NOTE_KIND (insn))
1035             {
1036               /* In case prologue is empty and function contain label
1037                  in first BB, we may want to copy the block.  */
1038             case NOTE_INSN_PROLOGUE_END:
1039
1040             case NOTE_INSN_DELETED:
1041             case NOTE_INSN_DELETED_LABEL:
1042               /* No problem to strip these.  */
1043             case NOTE_INSN_EPILOGUE_BEG:
1044               /* Debug code expect these notes to exist just once.
1045                  Keep them in the master copy.
1046                  ??? It probably makes more sense to duplicate them for each
1047                  epilogue copy.  */
1048             case NOTE_INSN_FUNCTION_BEG:
1049               /* There is always just single entry to function.  */
1050             case NOTE_INSN_BASIC_BLOCK:
1051               break;
1052
1053             case NOTE_INSN_SWITCH_TEXT_SECTIONS:
1054               emit_note_copy (insn);
1055               break;
1056
1057             default:
1058               /* All other notes should have already been eliminated.
1059                */
1060               gcc_unreachable ();
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"