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