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