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