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