gcc/cfglayout.c

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