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