contrib/gcc-4.0/gcc/cfglayout.c

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