gcc/cfglayout.c

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