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