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