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, 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       this_block = insn_scope (insn);
 527       /* For sequences compute scope resulting from merging all scopes
 528          of instructions nested inside.  */
 529       if (GET_CODE (PATTERN (insn)) == SEQUENCE)
 530         {
 531           int i;
 532           rtx body = PATTERN (insn);
 533
 534           this_block = NULL;
 535           for (i = 0; i < XVECLEN (body, 0); i++)
 536             this_block = choose_inner_scope (this_block,
 537                                          insn_scope (XVECEXP (body, 0, i)));
 538         }
 539       if (! this_block)
 540         continue;
 541
 542       if (this_block != cur_block)
 543         {
 544           change_scope (insn, cur_block, this_block);
 545           cur_block = this_block;
 546         }
 547     }
 548
 549   /* change_scope emits before the insn, not after.  */
 550   note = emit_note (NOTE_INSN_DELETED);
 551   change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
 552   delete_insn (note);
 553
 554   reorder_blocks ();
 555 }
 556 \f
 557 /* Given a reorder chain, rearrange the code to match.  */
 558
 559 static void
 560 fixup_reorder_chain (void)
 561 {
 562   basic_block bb, prev_bb;
 563   int index;
 564   rtx insn = NULL;
 565
 566   if (cfg_layout_function_header)
 567     {
 568       set_first_insn (cfg_layout_function_header);
 569       insn = cfg_layout_function_header;
 570       while (NEXT_INSN (insn))
 571         insn = NEXT_INSN (insn);
 572     }
 573
 574   /* First do the bulk reordering -- rechain the blocks without regard to
 575      the needed changes to jumps and labels.  */
 576
 577   for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
 578        bb != 0;
 579        bb = bb->rbi->next, index++)
 580     {
 581       if (bb->rbi->header)
 582         {
 583           if (insn)
 584             NEXT_INSN (insn) = bb->rbi->header;
 585           else
 586             set_first_insn (bb->rbi->header);
 587           PREV_INSN (bb->rbi->header) = insn;
 588           insn = bb->rbi->header;
 589           while (NEXT_INSN (insn))
 590             insn = NEXT_INSN (insn);
 591         }
 592       if (insn)
 593         NEXT_INSN (insn) = BB_HEAD (bb);
 594       else
 595         set_first_insn (BB_HEAD (bb));
 596       PREV_INSN (BB_HEAD (bb)) = insn;
 597       insn = BB_END (bb);
 598       if (bb->rbi->footer)
 599         {
 600           NEXT_INSN (insn) = bb->rbi->footer;
 601           PREV_INSN (bb->rbi->footer) = insn;
 602           while (NEXT_INSN (insn))
 603             insn = NEXT_INSN (insn);
 604         }
 605     }
 606
 607   gcc_assert (index == n_basic_blocks);
 608
 609   NEXT_INSN (insn) = cfg_layout_function_footer;
 610   if (cfg_layout_function_footer)
 611     PREV_INSN (cfg_layout_function_footer) = insn;
 612
 613   while (NEXT_INSN (insn))
 614     insn = NEXT_INSN (insn);
 615
 616   set_last_insn (insn);
 617 #ifdef ENABLE_CHECKING
 618   verify_insn_chain ();
 619 #endif
 620   delete_dead_jumptables ();
 621
 622   /* Now add jumps and labels as needed to match the blocks new
 623      outgoing edges.  */
 624
 625   for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->rbi->next)
 626     {
 627       edge e_fall, e_taken, e;
 628       rtx bb_end_insn;
 629       basic_block nb;
 630       edge_iterator ei;
 631
 632       if (EDGE_COUNT (bb->succs) == 0)
 633         continue;
 634
 635       /* Find the old fallthru edge, and another non-EH edge for
 636          a taken jump.  */
 637       e_taken = e_fall = NULL;
 638
 639       FOR_EACH_EDGE (e, ei, bb->succs)
 640         if (e->flags & EDGE_FALLTHRU)
 641           e_fall = e;
 642         else if (! (e->flags & EDGE_EH))
 643           e_taken = e;
 644
 645       bb_end_insn = BB_END (bb);
 646       if (JUMP_P (bb_end_insn))
 647         {
 648           if (any_condjump_p (bb_end_insn))
 649             {
 650               /* If the old fallthru is still next, nothing to do.  */
 651               if (bb->rbi->next == e_fall->dest
 652                   || e_fall->dest == EXIT_BLOCK_PTR)
 653                 continue;
 654
 655               /* The degenerated case of conditional jump jumping to the next
 656                  instruction can happen on target having jumps with side
 657                  effects.
 658
 659                  Create temporarily the duplicated edge representing branch.
 660                  It will get unidentified by force_nonfallthru_and_redirect
 661                  that would otherwise get confused by fallthru edge not pointing
 662                  to the next basic block.  */
 663               if (!e_taken)
 664                 {
 665                   rtx note;
 666                   edge e_fake;
 667                   bool redirected;
 668
 669                   e_fake = unchecked_make_edge (bb, e_fall->dest, 0);
 670
 671                   redirected = redirect_jump (BB_END (bb),
 672                                               block_label (bb), 0);
 673                   gcc_assert (redirected);
 674
 675                   note = find_reg_note (BB_END (bb), REG_BR_PROB, NULL_RTX);
 676                   if (note)
 677                     {
 678                       int prob = INTVAL (XEXP (note, 0));
 679
 680                       e_fake->probability = prob;
 681                       e_fake->count = e_fall->count * prob / REG_BR_PROB_BASE;
 682                       e_fall->probability -= e_fall->probability;
 683                       e_fall->count -= e_fake->count;
 684                       if (e_fall->probability < 0)
 685                         e_fall->probability = 0;
 686                       if (e_fall->count < 0)
 687                         e_fall->count = 0;
 688                     }
 689                 }
 690               /* There is one special case: if *neither* block is next,
 691                  such as happens at the very end of a function, then we'll
 692                  need to add a new unconditional jump.  Choose the taken
 693                  edge based on known or assumed probability.  */
 694               else if (bb->rbi->next != e_taken->dest)
 695                 {
 696                   rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
 697
 698                   if (note
 699                       && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
 700                       && invert_jump (bb_end_insn,
 701                                       (e_fall->dest == EXIT_BLOCK_PTR
 702                                        ? NULL_RTX
 703                                        : label_for_bb (e_fall->dest)), 0))
 704                     {
 705                       e_fall->flags &= ~EDGE_FALLTHRU;
 706 #ifdef ENABLE_CHECKING
 707                       gcc_assert (could_fall_through
 708                                   (e_taken->src, e_taken->dest));
 709 #endif
 710                       e_taken->flags |= EDGE_FALLTHRU;
 711                       update_br_prob_note (bb);
 712                       e = e_fall, e_fall = e_taken, e_taken = e;
 713                     }
 714                 }
 715
 716               /* If the "jumping" edge is a crossing edge, and the fall
 717                  through edge is non-crossing, leave things as they are.  */
 718               else if ((e_taken->flags & EDGE_CROSSING)
 719                        && !(e_fall->flags & EDGE_CROSSING))
 720                 continue;
 721
 722               /* Otherwise we can try to invert the jump.  This will
 723                  basically never fail, however, keep up the pretense.  */
 724               else if (invert_jump (bb_end_insn,
 725                                     (e_fall->dest == EXIT_BLOCK_PTR
 726                                      ? NULL_RTX
 727                                      : label_for_bb (e_fall->dest)), 0))
 728                 {
 729                   e_fall->flags &= ~EDGE_FALLTHRU;
 730 #ifdef ENABLE_CHECKING
 731                   gcc_assert (could_fall_through
 732                               (e_taken->src, e_taken->dest));
 733 #endif
 734                   e_taken->flags |= EDGE_FALLTHRU;
 735                   update_br_prob_note (bb);
 736                   continue;
 737                 }
 738             }
 739           else
 740             {
 741               /* Otherwise we have some return, switch or computed
 742                  jump.  In the 99% case, there should not have been a
 743                  fallthru edge.  */
 744               gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
 745               continue;
 746             }
 747         }
 748       else
 749         {
 750           /* No fallthru implies a noreturn function with EH edges, or
 751              something similarly bizarre.  In any case, we don't need to
 752              do anything.  */
 753           if (! e_fall)
 754             continue;
 755
 756           /* If the fallthru block is still next, nothing to do.  */
 757           if (bb->rbi->next == e_fall->dest)
 758             continue;
 759
 760           /* A fallthru to exit block.  */
 761           if (e_fall->dest == EXIT_BLOCK_PTR)
 762             continue;
 763         }
 764
 765       /* We got here if we need to add a new jump insn.  */
 766       nb = force_nonfallthru (e_fall);
 767       if (nb)
 768         {
 769           initialize_bb_rbi (nb);
 770           nb->rbi->visited = 1;
 771           nb->rbi->next = bb->rbi->next;
 772           bb->rbi->next = nb;
 773           /* Don't process this new block.  */
 774           bb = nb;
 775
 776           /* Make sure new bb is tagged for correct section (same as
 777              fall-thru source, since you cannot fall-throu across
 778              section boundaries).  */
 779           BB_COPY_PARTITION (e_fall->src, single_pred (bb));
 780           if (flag_reorder_blocks_and_partition
 781               && targetm.have_named_sections)
 782             {
 783               if (BB_PARTITION (single_pred (bb)) == BB_COLD_PARTITION)
 784                 {
 785                   rtx new_note;
 786                   rtx note = BB_HEAD (e_fall->src);
 787
 788                   while (!INSN_P (note)
 789                          && note != BB_END (e_fall->src))
 790                     note = NEXT_INSN (note);
 791
 792                   new_note = emit_note_before
 793                                           (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
 794                                            note);
 795                   NOTE_BASIC_BLOCK (new_note) = bb;
 796                 }
 797               if (JUMP_P (BB_END (bb))
 798                   && !any_condjump_p (BB_END (bb))
 799                   && (single_succ_edge (bb)->flags & EDGE_CROSSING))
 800                 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
 801                   (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
 802             }
 803         }
 804     }
 805
 806   /* Put basic_block_info in the new order.  */
 807
 808   if (dump_file)
 809     {
 810       fprintf (dump_file, "Reordered sequence:\n");
 811       for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
 812            bb;
 813            bb = bb->rbi->next, index++)
 814         {
 815           fprintf (dump_file, " %i ", index);
 816           if (bb->rbi->original)
 817             fprintf (dump_file, "duplicate of %i ",
 818                      bb->rbi->original->index);
 819           else if (forwarder_block_p (bb)
 820                    && !LABEL_P (BB_HEAD (bb)))
 821             fprintf (dump_file, "compensation ");
 822           else
 823             fprintf (dump_file, "bb %i ", bb->index);
 824           fprintf (dump_file, " [%i]\n", bb->frequency);
 825         }
 826     }
 827
 828   prev_bb = ENTRY_BLOCK_PTR;
 829   bb = ENTRY_BLOCK_PTR->next_bb;
 830   index = 0;
 831
 832   for (; bb; prev_bb = bb, bb = bb->rbi->next, index ++)
 833     {
 834       bb->index = index;
 835       BASIC_BLOCK (index) = bb;
 836
 837       update_unlikely_executed_notes (bb);
 838
 839       bb->prev_bb = prev_bb;
 840       prev_bb->next_bb = bb;
 841     }
 842   prev_bb->next_bb = EXIT_BLOCK_PTR;
 843   EXIT_BLOCK_PTR->prev_bb = prev_bb;
 844
 845   /* Annoying special case - jump around dead jumptables left in the code.  */
 846   FOR_EACH_BB (bb)
 847     {
 848       edge e;
 849       edge_iterator ei;
 850
 851       FOR_EACH_EDGE (e, ei, bb->succs)
 852         if (e->flags & EDGE_FALLTHRU)
 853           break;
 854
 855       if (e && !can_fallthru (e->src, e->dest))
 856         force_nonfallthru (e);
 857     }
 858 }
 859 \f
 860 /* Update the basic block number information in any
 861    NOTE_INSN_UNLIKELY_EXECUTED_CODE notes within the basic block.  */
 862
 863 static void
 864 update_unlikely_executed_notes (basic_block bb)
 865 {
 866   rtx cur_insn;
 867
 868   for (cur_insn = BB_HEAD (bb); cur_insn != BB_END (bb);
 869        cur_insn = NEXT_INSN (cur_insn))
 870     if (NOTE_P (cur_insn)
 871         && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
 872       NOTE_BASIC_BLOCK (cur_insn) = bb;
 873 }
 874 \f
 875 /* Perform sanity checks on the insn chain.
 876    1. Check that next/prev pointers are consistent in both the forward and
 877       reverse direction.
 878    2. Count insns in chain, going both directions, and check if equal.
 879    3. Check that get_last_insn () returns the actual end of chain.  */
 880
 881 void
 882 verify_insn_chain (void)
 883 {
 884   rtx x, prevx, nextx;
 885   int insn_cnt1, insn_cnt2;
 886
 887   for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
 888        x != 0;
 889        prevx = x, insn_cnt1++, x = NEXT_INSN (x))
 890     gcc_assert (PREV_INSN (x) == prevx);
 891
 892   gcc_assert (prevx == get_last_insn ());
 893
 894   for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
 895        x != 0;
 896        nextx = x, insn_cnt2++, x = PREV_INSN (x))
 897     gcc_assert (NEXT_INSN (x) == nextx);
 898
 899   gcc_assert (insn_cnt1 == insn_cnt2);
 900 }
 901 \f
 902 /* If we have assembler epilogues, the block falling through to exit must
 903    be the last one in the reordered chain when we reach final.  Ensure
 904    that this condition is met.  */
 905 static void
 906 fixup_fallthru_exit_predecessor (void)
 907 {
 908   edge e;
 909   edge_iterator ei;
 910   basic_block bb = NULL;
 911
 912   /* This transformation is not valid before reload, because we might
 913      separate a call from the instruction that copies the return
 914      value.  */
 915   gcc_assert (reload_completed);
 916
 917   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 918     if (e->flags & EDGE_FALLTHRU)
 919       bb = e->src;
 920
 921   if (bb && bb->rbi->next)
 922     {
 923       basic_block c = ENTRY_BLOCK_PTR->next_bb;
 924
 925       /* If the very first block is the one with the fall-through exit
 926          edge, we have to split that block.  */
 927       if (c == bb)
 928         {
 929           bb = split_block (bb, NULL)->dest;
 930           initialize_bb_rbi (bb);
 931           bb->rbi->next = c->rbi->next;
 932           c->rbi->next = bb;
 933           bb->rbi->footer = c->rbi->footer;
 934           c->rbi->footer = NULL;
 935         }
 936
 937       while (c->rbi->next != bb)
 938         c = c->rbi->next;
 939
 940       c->rbi->next = bb->rbi->next;
 941       while (c->rbi->next)
 942         c = c->rbi->next;
 943
 944       c->rbi->next = bb;
 945       bb->rbi->next = NULL;
 946     }
 947 }
 948 \f
 949 /* Return true in case it is possible to duplicate the basic block BB.  */
 950
 951 /* We do not want to declare the function in a header file, since it should
 952    only be used through the cfghooks interface, and we do not want to move
 953    it to cfgrtl.c since it would require also moving quite a lot of related
 954    code.  */
 955 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
 956
 957 bool
 958 cfg_layout_can_duplicate_bb_p (basic_block bb)
 959 {
 960   /* Do not attempt to duplicate tablejumps, as we need to unshare
 961      the dispatch table.  This is difficult to do, as the instructions
 962      computing jump destination may be hoisted outside the basic block.  */
 963   if (tablejump_p (BB_END (bb), NULL, NULL))
 964     return false;
 965
 966   /* Do not duplicate blocks containing insns that can't be copied.  */
 967   if (targetm.cannot_copy_insn_p)
 968     {
 969       rtx insn = BB_HEAD (bb);
 970       while (1)
 971         {
 972           if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
 973             return false;
 974           if (insn == BB_END (bb))
 975             break;
 976           insn = NEXT_INSN (insn);
 977         }
 978     }
 979
 980   return true;
 981 }
 982
 983 rtx
 984 duplicate_insn_chain (rtx from, rtx to)
 985 {
 986   rtx insn, last;
 987
 988   /* Avoid updating of boundaries of previous basic block.  The
 989      note will get removed from insn stream in fixup.  */
 990   last = emit_note (NOTE_INSN_DELETED);
 991
 992   /* Create copy at the end of INSN chain.  The chain will
 993      be reordered later.  */
 994   for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
 995     {
 996       switch (GET_CODE (insn))
 997         {
 998         case INSN:
 999         case CALL_INSN:
1000         case JUMP_INSN:
1001           /* Avoid copying of dispatch tables.  We never duplicate
1002              tablejumps, so this can hit only in case the table got
1003              moved far from original jump.  */
1004           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1005               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1006             break;
1007           emit_copy_of_insn_after (insn, get_last_insn ());
1008           break;
1009
1010         case CODE_LABEL:
1011           break;
1012
1013         case BARRIER:
1014           emit_barrier ();
1015           break;
1016
1017         case NOTE:
1018           switch (NOTE_LINE_NUMBER (insn))
1019             {
1020               /* In case prologue is empty and function contain label
1021                  in first BB, we may want to copy the block.  */
1022             case NOTE_INSN_PROLOGUE_END:
1023
1024             case NOTE_INSN_LOOP_BEG:
1025             case NOTE_INSN_LOOP_END:
1026               /* Strip down the loop notes - we don't really want to keep
1027                  them consistent in loop copies.  */
1028             case NOTE_INSN_DELETED:
1029             case NOTE_INSN_DELETED_LABEL:
1030               /* No problem to strip these.  */
1031             case NOTE_INSN_EPILOGUE_BEG:
1032             case NOTE_INSN_FUNCTION_END:
1033               /* Debug code expect these notes to exist just once.
1034                  Keep them in the master copy.
1035                  ??? It probably makes more sense to duplicate them for each
1036                  epilogue copy.  */
1037             case NOTE_INSN_FUNCTION_BEG:
1038               /* There is always just single entry to function.  */
1039             case NOTE_INSN_BASIC_BLOCK:
1040               break;
1041
1042             case NOTE_INSN_REPEATED_LINE_NUMBER:
1043             case NOTE_INSN_UNLIKELY_EXECUTED_CODE:
1044               emit_note_copy (insn);
1045               break;
1046
1047             default:
1048               /* All other notes should have already been eliminated.
1049                */
1050               gcc_assert (NOTE_LINE_NUMBER (insn) >= 0);
1051
1052               /* It is possible that no_line_number is set and the note
1053                  won't be emitted.  */
1054               emit_note_copy (insn);
1055             }
1056           break;
1057         default:
1058           gcc_unreachable ();
1059         }
1060     }
1061   insn = NEXT_INSN (last);
1062   delete_insn (last);
1063   return insn;
1064 }
1065 /* Create a duplicate of the basic block BB.  */
1066
1067 /* We do not want to declare the function in a header file, since it should
1068    only be used through the cfghooks interface, and we do not want to move
1069    it to cfgrtl.c since it would require also moving quite a lot of related
1070    code.  */
1071 extern basic_block cfg_layout_duplicate_bb (basic_block);
1072
1073 basic_block
1074 cfg_layout_duplicate_bb (basic_block bb)
1075 {
1076   rtx insn;
1077   basic_block new_bb;
1078
1079   insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1080   new_bb = create_basic_block (insn,
1081                                insn ? get_last_insn () : NULL,
1082                                EXIT_BLOCK_PTR->prev_bb);
1083
1084   BB_COPY_PARTITION (new_bb, bb);
1085   if (bb->rbi->header)
1086     {
1087       insn = bb->rbi->header;
1088       while (NEXT_INSN (insn))
1089         insn = NEXT_INSN (insn);
1090       insn = duplicate_insn_chain (bb->rbi->header, insn);
1091       if (insn)
1092         new_bb->rbi->header = unlink_insn_chain (insn, get_last_insn ());
1093     }
1094
1095   if (bb->rbi->footer)
1096     {
1097       insn = bb->rbi->footer;
1098       while (NEXT_INSN (insn))
1099         insn = NEXT_INSN (insn);
1100       insn = duplicate_insn_chain (bb->rbi->footer, insn);
1101       if (insn)
1102         new_bb->rbi->footer = unlink_insn_chain (insn, get_last_insn ());
1103     }
1104
1105   if (bb->global_live_at_start)
1106     {
1107       new_bb->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
1108       new_bb->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
1109       COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
1110       COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
1111     }
1112
1113   return new_bb;
1114 }
1115 \f
1116 /* Main entry point to this module - initialize the datastructures for
1117    CFG layout changes.  It keeps LOOPS up-to-date if not null.
1118
1119    FLAGS is a set of additional flags to pass to cleanup_cfg().  It should
1120    include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1121    to date.  */
1122
1123 void
1124 cfg_layout_initialize (unsigned int flags)
1125 {
1126   basic_block bb;
1127
1128   /* Our algorithm depends on fact that there are no dead jumptables
1129      around the code.  */
1130   alloc_rbi_pool ();
1131
1132   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1133     initialize_bb_rbi (bb);
1134
1135   cfg_layout_rtl_register_cfg_hooks ();
1136
1137   record_effective_endpoints ();
1138
1139   cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
1140 }
1141
1142 /* Splits superblocks.  */
1143 void
1144 break_superblocks (void)
1145 {
1146   sbitmap superblocks;
1147   bool need = false;
1148   basic_block bb;
1149
1150   superblocks = sbitmap_alloc (last_basic_block);
1151   sbitmap_zero (superblocks);
1152
1153   FOR_EACH_BB (bb)
1154     if (bb->flags & BB_SUPERBLOCK)
1155       {
1156         bb->flags &= ~BB_SUPERBLOCK;
1157         SET_BIT (superblocks, bb->index);
1158         need = true;
1159       }
1160
1161   if (need)
1162     {
1163       rebuild_jump_labels (get_insns ());
1164       find_many_sub_basic_blocks (superblocks);
1165     }
1166
1167   free (superblocks);
1168 }
1169
1170 /* Finalize the changes: reorder insn list according to the sequence, enter
1171    compensation code, rebuild scope forest.  */
1172
1173 void
1174 cfg_layout_finalize (void)
1175 {
1176   basic_block bb;
1177
1178 #ifdef ENABLE_CHECKING
1179   verify_flow_info ();
1180 #endif
1181   rtl_register_cfg_hooks ();
1182   if (reload_completed
1183 #ifdef HAVE_epilogue
1184       && !HAVE_epilogue
1185 #endif
1186       )
1187     fixup_fallthru_exit_predecessor ();
1188   fixup_reorder_chain ();
1189
1190 #ifdef ENABLE_CHECKING
1191   verify_insn_chain ();
1192 #endif
1193
1194   free_rbi_pool ();
1195   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1196     bb->rbi = NULL;
1197
1198   break_superblocks ();
1199
1200 #ifdef ENABLE_CHECKING
1201   verify_flow_info ();
1202 #endif
1203 }
1204
1205 /* Checks whether all N blocks in BBS array can be copied.  */
1206 bool
1207 can_copy_bbs_p (basic_block *bbs, unsigned n)
1208 {
1209   unsigned i;
1210   edge e;
1211   int ret = true;
1212
1213   for (i = 0; i < n; i++)
1214     bbs[i]->rbi->duplicated = 1;
1215
1216   for (i = 0; i < n; i++)
1217     {
1218       /* In case we should redirect abnormal edge during duplication, fail.  */
1219       edge_iterator ei;
1220       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1221         if ((e->flags & EDGE_ABNORMAL)
1222             && e->dest->rbi->duplicated)
1223           {
1224             ret = false;
1225             goto end;
1226           }
1227
1228       if (!can_duplicate_block_p (bbs[i]))
1229         {
1230           ret = false;
1231           break;
1232         }
1233     }
1234
1235 end:
1236   for (i = 0; i < n; i++)
1237     bbs[i]->rbi->duplicated = 0;
1238
1239   return ret;
1240 }
1241
1242 /* Duplicates N basic blocks stored in array BBS.  Newly created basic blocks
1243    are placed into array NEW_BBS in the same order.  Edges from basic blocks
1244    in BBS are also duplicated and copies of those of them
1245    that lead into BBS are redirected to appropriate newly created block.  The
1246    function assigns bbs into loops (copy of basic block bb is assigned to
1247    bb->loop_father->copy loop, so this must be set up correctly in advance)
1248    and updates dominators locally (LOOPS structure that contains the information
1249    about dominators is passed to enable this).
1250
1251    BASE is the superloop to that basic block belongs; if its header or latch
1252    is copied, we do not set the new blocks as header or latch.
1253
1254    Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1255    also in the same order.  */
1256
1257 void
1258 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1259           edge *edges, unsigned n_edges, edge *new_edges,
1260           struct loop *base)
1261 {
1262   unsigned i, j;
1263   basic_block bb, new_bb, dom_bb;
1264   edge e;
1265
1266   /* Duplicate bbs, update dominators, assign bbs to loops.  */
1267   for (i = 0; i < n; i++)
1268     {
1269       /* Duplicate.  */
1270       bb = bbs[i];
1271       new_bb = new_bbs[i] = duplicate_block (bb, NULL);
1272       bb->rbi->duplicated = 1;
1273       /* Add to loop.  */
1274       add_bb_to_loop (new_bb, bb->loop_father->copy);
1275       /* Possibly set header.  */
1276       if (bb->loop_father->header == bb && bb->loop_father != base)
1277         new_bb->loop_father->header = new_bb;
1278       /* Or latch.  */
1279       if (bb->loop_father->latch == bb && bb->loop_father != base)
1280         new_bb->loop_father->latch = new_bb;
1281     }
1282
1283   /* Set dominators.  */
1284   for (i = 0; i < n; i++)
1285     {
1286       bb = bbs[i];
1287       new_bb = new_bbs[i];
1288
1289       dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1290       if (dom_bb->rbi->duplicated)
1291         {
1292           dom_bb = dom_bb->rbi->copy;
1293           set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1294         }
1295     }
1296
1297   /* Redirect edges.  */
1298   for (j = 0; j < n_edges; j++)
1299     new_edges[j] = NULL;
1300   for (i = 0; i < n; i++)
1301     {
1302       edge_iterator ei;
1303       new_bb = new_bbs[i];
1304       bb = bbs[i];
1305
1306       FOR_EACH_EDGE (e, ei, new_bb->succs)
1307         {
1308           for (j = 0; j < n_edges; j++)
1309             if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1310               new_edges[j] = e;
1311
1312           if (!e->dest->rbi->duplicated)
1313             continue;
1314           redirect_edge_and_branch_force (e, e->dest->rbi->copy);
1315         }
1316     }
1317
1318   /* Clear information about duplicates.  */
1319   for (i = 0; i < n; i++)
1320     bbs[i]->rbi->duplicated = 0;
1321 }
1322
1323 #include "gt-cfglayout.h"