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