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