gcc/cfglayout.c

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