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 static unsigned int
 351 into_cfg_layout_mode (void)
 352 {
 353   cfg_layout_initialize (0);
 354   return 0;
 355 }
 356
 357 static unsigned int
 358 outof_cfg_layout_mode (void)
 359 {
 360   basic_block bb;
 361
 362   FOR_EACH_BB (bb)
 363     if (bb->next_bb != EXIT_BLOCK_PTR)
 364       bb->aux = bb->next_bb;
 365
 366   cfg_layout_finalize ();
 367
 368   return 0;
 369 }
 370
 371 struct tree_opt_pass pass_into_cfg_layout_mode =
 372 {
 373   "into_cfglayout",                     /* name */
 374   NULL,                                 /* gate */
 375   into_cfg_layout_mode,                 /* execute */
 376   NULL,                                 /* sub */
 377   NULL,                                 /* next */
 378   0,                                    /* static_pass_number */
 379   0,                                    /* tv_id */
 380   0,                                    /* properties_required */
 381   0,                                    /* properties_provided */
 382   0,                                    /* properties_destroyed */
 383   0,                                    /* todo_flags_start */
 384   TODO_dump_func,                       /* todo_flags_finish */
 385   0                                     /* letter */
 386 };
 387
 388 struct tree_opt_pass pass_outof_cfg_layout_mode =
 389 {
 390   "outof_cfglayout",                    /* name */
 391   NULL,                                 /* gate */
 392   outof_cfg_layout_mode,                /* execute */
 393   NULL,                                 /* sub */
 394   NULL,                                 /* next */
 395   0,                                    /* static_pass_number */
 396   0,                                    /* tv_id */
 397   0,                                    /* properties_required */
 398   0,                                    /* properties_provided */
 399   0,                                    /* properties_destroyed */
 400   0,                                    /* todo_flags_start */
 401   TODO_dump_func,                       /* todo_flags_finish */
 402   0                                     /* letter */
 403 };
 404
 405 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
 406    found in the block tree.  */
 407
 408 static void
 409 set_block_levels (tree block, int level)
 410 {
 411   while (block)
 412     {
 413       BLOCK_NUMBER (block) = level;
 414       set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
 415       block = BLOCK_CHAIN (block);
 416     }
 417 }
 418 \f
 419 /* Return sope resulting from combination of S1 and S2.  */
 420 static tree
 421 choose_inner_scope (tree s1, tree s2)
 422 {
 423    if (!s1)
 424      return s2;
 425    if (!s2)
 426      return s1;
 427    if (BLOCK_NUMBER (s1) > BLOCK_NUMBER (s2))
 428      return s1;
 429    return s2;
 430 }
 431 \f
 432 /* Emit lexical block notes needed to change scope from S1 to S2.  */
 433
 434 static void
 435 change_scope (rtx orig_insn, tree s1, tree s2)
 436 {
 437   rtx insn = orig_insn;
 438   tree com = NULL_TREE;
 439   tree ts1 = s1, ts2 = s2;
 440   tree s;
 441
 442   while (ts1 != ts2)
 443     {
 444       gcc_assert (ts1 && ts2);
 445       if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
 446         ts1 = BLOCK_SUPERCONTEXT (ts1);
 447       else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
 448         ts2 = BLOCK_SUPERCONTEXT (ts2);
 449       else
 450         {
 451           ts1 = BLOCK_SUPERCONTEXT (ts1);
 452           ts2 = BLOCK_SUPERCONTEXT (ts2);
 453         }
 454     }
 455   com = ts1;
 456
 457   /* Close scopes.  */
 458   s = s1;
 459   while (s != com)
 460     {
 461       rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
 462       NOTE_BLOCK (note) = s;
 463       s = BLOCK_SUPERCONTEXT (s);
 464     }
 465
 466   /* Open scopes.  */
 467   s = s2;
 468   while (s != com)
 469     {
 470       insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
 471       NOTE_BLOCK (insn) = s;
 472       s = BLOCK_SUPERCONTEXT (s);
 473     }
 474 }
 475
 476 /* Return lexical scope block insn belong to.  */
 477 static tree
 478 insn_scope (rtx insn)
 479 {
 480   int max = VEC_length (int, block_locators_locs);
 481   int min = 0;
 482   int loc = INSN_LOCATOR (insn);
 483
 484   /* When block_locators_locs was initialized, the pro- and epilogue
 485      insns didn't exist yet and can therefore not be found this way.
 486      But we know that they belong to the outer most block of the
 487      current function.
 488      Without this test, the prologue would be put inside the block of
 489      the first valid instruction in the function and when that first
 490      insn is part of an inlined function then the low_pc of that
 491      inlined function is messed up.  Likewise for the epilogue and
 492      the last valid instruction.  */
 493   if (loc == prologue_locator || loc == epilogue_locator)
 494     return DECL_INITIAL (cfun->decl);
 495
 496   if (!max || !loc)
 497     return NULL;
 498   while (1)
 499     {
 500       int pos = (min + max) / 2;
 501       int tmp = VEC_index (int, block_locators_locs, pos);
 502
 503       if (tmp <= loc && min != pos)
 504         min = pos;
 505       else if (tmp > loc && max != pos)
 506         max = pos;
 507       else
 508         {
 509           min = pos;
 510           break;
 511         }
 512     }
 513   return VEC_index (tree, block_locators_blocks, min);
 514 }
 515
 516 /* Return line number of the statement specified by the locator.  */
 517 int
 518 locator_line (int loc)
 519 {
 520   int max = VEC_length (int, line_locators_locs);
 521   int min = 0;
 522
 523   if (!max || !loc)
 524     return 0;
 525   while (1)
 526     {
 527       int pos = (min + max) / 2;
 528       int tmp = VEC_index (int, line_locators_locs, pos);
 529
 530       if (tmp <= loc && min != pos)
 531         min = pos;
 532       else if (tmp > loc && max != pos)
 533         max = pos;
 534       else
 535         {
 536           min = pos;
 537           break;
 538         }
 539     }
 540   return VEC_index (int, line_locators_lines, min);
 541 }
 542
 543 /* Return line number of the statement that produced this insn.  */
 544 int
 545 insn_line (rtx insn)
 546 {
 547   return locator_line (INSN_LOCATOR (insn));
 548 }
 549
 550 /* Return source file of the statement specified by LOC.  */
 551 const char *
 552 locator_file (int loc)
 553 {
 554   int max = VEC_length (int, file_locators_locs);
 555   int min = 0;
 556
 557   if (!max || !loc)
 558     return NULL;
 559   while (1)
 560     {
 561       int pos = (min + max) / 2;
 562       int tmp = VEC_index (int, file_locators_locs, pos);
 563
 564       if (tmp <= loc && min != pos)
 565         min = pos;
 566       else if (tmp > loc && max != pos)
 567         max = pos;
 568       else
 569         {
 570           min = pos;
 571           break;
 572         }
 573     }
 574    return VARRAY_CHAR_PTR (file_locators_files, min);
 575 }
 576
 577 /* Return source file of the statement that produced this insn.  */
 578 const char *
 579 insn_file (rtx insn)
 580 {
 581   return locator_file (INSN_LOCATOR (insn));
 582 }
 583
 584 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
 585    on the scope tree and the newly reordered instructions.  */
 586
 587 void
 588 reemit_insn_block_notes (void)
 589 {
 590   tree cur_block = DECL_INITIAL (cfun->decl);
 591   rtx insn, note;
 592
 593   insn = get_insns ();
 594   if (!active_insn_p (insn))
 595     insn = next_active_insn (insn);
 596   for (; insn; insn = next_active_insn (insn))
 597     {
 598       tree this_block;
 599
 600       /* Avoid putting scope notes between jump table and its label.  */
 601       if (JUMP_P (insn)
 602           && (GET_CODE (PATTERN (insn)) == ADDR_VEC
 603               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
 604         continue;
 605
 606       this_block = insn_scope (insn);
 607       /* For sequences compute scope resulting from merging all scopes
 608          of instructions nested inside.  */
 609       if (GET_CODE (PATTERN (insn)) == SEQUENCE)
 610         {
 611           int i;
 612           rtx body = PATTERN (insn);
 613
 614           this_block = NULL;
 615           for (i = 0; i < XVECLEN (body, 0); i++)
 616             this_block = choose_inner_scope (this_block,
 617                                          insn_scope (XVECEXP (body, 0, i)));
 618         }
 619       if (! this_block)
 620         continue;
 621
 622       if (this_block != cur_block)
 623         {
 624           change_scope (insn, cur_block, this_block);
 625           cur_block = this_block;
 626         }
 627     }
 628
 629   /* change_scope emits before the insn, not after.  */
 630   note = emit_note (NOTE_INSN_DELETED);
 631   change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
 632   delete_insn (note);
 633
 634   reorder_blocks ();
 635 }
 636 \f
 637
 638 /* Link the basic blocks in the correct order, compacting the basic
 639    block queue while at it.  This also clears the visited flag on
 640    all basic blocks.  If STAY_IN_CFGLAYOUT_MODE is false, this function
 641    also clears the basic block header and footer fields.
 642
 643    This function is usually called after a pass (e.g. tracer) finishes
 644    some transformations while in cfglayout mode.  The required sequence
 645    of the basic blocks is in a linked list along the bb->aux field.
 646    This functions re-links the basic block prev_bb and next_bb pointers
 647    accordingly, and it compacts and renumbers the blocks.  */
 648
 649 void
 650 relink_block_chain (bool stay_in_cfglayout_mode)
 651 {
 652   basic_block bb, prev_bb;
 653   int index;
 654
 655   /* Maybe dump the re-ordered sequence.  */
 656   if (dump_file)
 657     {
 658       fprintf (dump_file, "Reordered sequence:\n");
 659       for (bb = ENTRY_BLOCK_PTR->next_bb, index = NUM_FIXED_BLOCKS;
 660            bb;
 661            bb = bb->aux, index++)
 662         {
 663           fprintf (dump_file, " %i ", index);
 664           if (get_bb_original (bb))
 665             fprintf (dump_file, "duplicate of %i ",
 666                      get_bb_original (bb)->index);
 667           else if (forwarder_block_p (bb)
 668                    && !LABEL_P (BB_HEAD (bb)))
 669             fprintf (dump_file, "compensation ");
 670           else
 671             fprintf (dump_file, "bb %i ", bb->index);
 672           fprintf (dump_file, " [%i]\n", bb->frequency);
 673         }
 674     }
 675
 676   /* Now reorder the blocks.  */
 677   prev_bb = ENTRY_BLOCK_PTR;
 678   bb = ENTRY_BLOCK_PTR->next_bb;
 679   for (; bb; prev_bb = bb, bb = bb->aux)
 680     {
 681       bb->prev_bb = prev_bb;
 682       prev_bb->next_bb = bb;
 683     }
 684   prev_bb->next_bb = EXIT_BLOCK_PTR;
 685   EXIT_BLOCK_PTR->prev_bb = prev_bb;
 686
 687   /* Then, clean up the aux and visited fields.  */
 688   FOR_ALL_BB (bb)
 689     {
 690       bb->aux = NULL;
 691       bb->il.rtl->visited = 0;
 692       if (!stay_in_cfglayout_mode)
 693         bb->il.rtl->header = bb->il.rtl->footer = NULL;
 694     }
 695
 696   /* Maybe reset the original copy tables, they are not valid anymore
 697      when we renumber the basic blocks in compact_blocks.  If we are
 698      are going out of cfglayout mode, don't re-allocate the tables.  */
 699   free_original_copy_tables ();
 700   if (stay_in_cfglayout_mode)
 701     initialize_original_copy_tables ();
 702
 703   /* Finally, put basic_block_info in the new order.  */
 704   compact_blocks ();
 705 }
 706 \f
 707
 708 /* Given a reorder chain, rearrange the code to match.  */
 709
 710 static void
 711 fixup_reorder_chain (void)
 712 {
 713   basic_block bb;
 714   rtx insn = NULL;
 715
 716   if (cfg_layout_function_header)
 717     {
 718       set_first_insn (cfg_layout_function_header);
 719       insn = cfg_layout_function_header;
 720       while (NEXT_INSN (insn))
 721         insn = NEXT_INSN (insn);
 722     }
 723
 724   /* First do the bulk reordering -- rechain the blocks without regard to
 725      the needed changes to jumps and labels.  */
 726
 727   for (bb = ENTRY_BLOCK_PTR->next_bb; bb; bb = bb->aux)
 728     {
 729       if (bb->il.rtl->header)
 730         {
 731           if (insn)
 732             NEXT_INSN (insn) = bb->il.rtl->header;
 733           else
 734             set_first_insn (bb->il.rtl->header);
 735           PREV_INSN (bb->il.rtl->header) = insn;
 736           insn = bb->il.rtl->header;
 737           while (NEXT_INSN (insn))
 738             insn = NEXT_INSN (insn);
 739         }
 740       if (insn)
 741         NEXT_INSN (insn) = BB_HEAD (bb);
 742       else
 743         set_first_insn (BB_HEAD (bb));
 744       PREV_INSN (BB_HEAD (bb)) = insn;
 745       insn = BB_END (bb);
 746       if (bb->il.rtl->footer)
 747         {
 748           NEXT_INSN (insn) = bb->il.rtl->footer;
 749           PREV_INSN (bb->il.rtl->footer) = insn;
 750           while (NEXT_INSN (insn))
 751             insn = NEXT_INSN (insn);
 752         }
 753     }
 754
 755   NEXT_INSN (insn) = cfg_layout_function_footer;
 756   if (cfg_layout_function_footer)
 757     PREV_INSN (cfg_layout_function_footer) = insn;
 758
 759   while (NEXT_INSN (insn))
 760     insn = NEXT_INSN (insn);
 761
 762   set_last_insn (insn);
 763 #ifdef ENABLE_CHECKING
 764   verify_insn_chain ();
 765 #endif
 766
 767   /* Now add jumps and labels as needed to match the blocks new
 768      outgoing edges.  */
 769
 770   for (bb = ENTRY_BLOCK_PTR->next_bb; bb ; bb = bb->aux)
 771     {
 772       edge e_fall, e_taken, e;
 773       rtx bb_end_insn;
 774       basic_block nb;
 775       edge_iterator ei;
 776
 777       if (EDGE_COUNT (bb->succs) == 0)
 778         continue;
 779
 780       /* Find the old fallthru edge, and another non-EH edge for
 781          a taken jump.  */
 782       e_taken = e_fall = NULL;
 783
 784       FOR_EACH_EDGE (e, ei, bb->succs)
 785         if (e->flags & EDGE_FALLTHRU)
 786           e_fall = e;
 787         else if (! (e->flags & EDGE_EH))
 788           e_taken = e;
 789
 790       bb_end_insn = BB_END (bb);
 791       if (JUMP_P (bb_end_insn))
 792         {
 793           if (any_condjump_p (bb_end_insn))
 794             {
 795               /* If the old fallthru is still next, nothing to do.  */
 796               if (bb->aux == e_fall->dest
 797                   || e_fall->dest == EXIT_BLOCK_PTR)
 798                 continue;
 799
 800               /* The degenerated case of conditional jump jumping to the next
 801                  instruction can happen for jumps with side effects.  We need
 802                  to construct a forwarder block and this will be done just
 803                  fine by force_nonfallthru below.  */
 804               if (!e_taken)
 805                 ;
 806
 807               /* There is another special case: if *neither* block is next,
 808                  such as happens at the very end of a function, then we'll
 809                  need to add a new unconditional jump.  Choose the taken
 810                  edge based on known or assumed probability.  */
 811               else if (bb->aux != e_taken->dest)
 812                 {
 813                   rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
 814
 815                   if (note
 816                       && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
 817                       && invert_jump (bb_end_insn,
 818                                       (e_fall->dest == EXIT_BLOCK_PTR
 819                                        ? NULL_RTX
 820                                        : label_for_bb (e_fall->dest)), 0))
 821                     {
 822                       e_fall->flags &= ~EDGE_FALLTHRU;
 823 #ifdef ENABLE_CHECKING
 824                       gcc_assert (could_fall_through
 825                                   (e_taken->src, e_taken->dest));
 826 #endif
 827                       e_taken->flags |= EDGE_FALLTHRU;
 828                       update_br_prob_note (bb);
 829                       e = e_fall, e_fall = e_taken, e_taken = e;
 830                     }
 831                 }
 832
 833               /* If the "jumping" edge is a crossing edge, and the fall
 834                  through edge is non-crossing, leave things as they are.  */
 835               else if ((e_taken->flags & EDGE_CROSSING)
 836                        && !(e_fall->flags & EDGE_CROSSING))
 837                 continue;
 838
 839               /* Otherwise we can try to invert the jump.  This will
 840                  basically never fail, however, keep up the pretense.  */
 841               else if (invert_jump (bb_end_insn,
 842                                     (e_fall->dest == EXIT_BLOCK_PTR
 843                                      ? NULL_RTX
 844                                      : label_for_bb (e_fall->dest)), 0))
 845                 {
 846                   e_fall->flags &= ~EDGE_FALLTHRU;
 847 #ifdef ENABLE_CHECKING
 848                   gcc_assert (could_fall_through
 849                               (e_taken->src, e_taken->dest));
 850 #endif
 851                   e_taken->flags |= EDGE_FALLTHRU;
 852                   update_br_prob_note (bb);
 853                   continue;
 854                 }
 855             }
 856           else
 857             {
 858               /* Otherwise we have some return, switch or computed
 859                  jump.  In the 99% case, there should not have been a
 860                  fallthru edge.  */
 861               gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
 862               continue;
 863             }
 864         }
 865       else
 866         {
 867           /* No fallthru implies a noreturn function with EH edges, or
 868              something similarly bizarre.  In any case, we don't need to
 869              do anything.  */
 870           if (! e_fall)
 871             continue;
 872
 873           /* If the fallthru block is still next, nothing to do.  */
 874           if (bb->aux == e_fall->dest)
 875             continue;
 876
 877           /* A fallthru to exit block.  */
 878           if (e_fall->dest == EXIT_BLOCK_PTR)
 879             continue;
 880         }
 881
 882       /* We got here if we need to add a new jump insn.  */
 883       nb = force_nonfallthru (e_fall);
 884       if (nb)
 885         {
 886           nb->il.rtl->visited = 1;
 887           nb->aux = bb->aux;
 888           bb->aux = nb;
 889           /* Don't process this new block.  */
 890           bb = nb;
 891
 892           /* Make sure new bb is tagged for correct section (same as
 893              fall-thru source, since you cannot fall-throu across
 894              section boundaries).  */
 895           BB_COPY_PARTITION (e_fall->src, single_pred (bb));
 896           if (flag_reorder_blocks_and_partition
 897               && targetm.have_named_sections
 898               && JUMP_P (BB_END (bb))
 899               && !any_condjump_p (BB_END (bb))
 900               && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
 901             REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
 902               (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
 903         }
 904     }
 905
 906   relink_block_chain (/*stay_in_cfglayout_mode=*/false);
 907
 908   /* Annoying special case - jump around dead jumptables left in the code.  */
 909   FOR_EACH_BB (bb)
 910     {
 911       edge e;
 912       edge_iterator ei;
 913
 914       FOR_EACH_EDGE (e, ei, bb->succs)
 915         if (e->flags & EDGE_FALLTHRU)
 916           break;
 917
 918       if (e && !can_fallthru (e->src, e->dest))
 919         force_nonfallthru (e);
 920     }
 921 }
 922 \f
 923 /* Perform sanity checks on the insn chain.
 924    1. Check that next/prev pointers are consistent in both the forward and
 925       reverse direction.
 926    2. Count insns in chain, going both directions, and check if equal.
 927    3. Check that get_last_insn () returns the actual end of chain.  */
 928
 929 void
 930 verify_insn_chain (void)
 931 {
 932   rtx x, prevx, nextx;
 933   int insn_cnt1, insn_cnt2;
 934
 935   for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
 936        x != 0;
 937        prevx = x, insn_cnt1++, x = NEXT_INSN (x))
 938     gcc_assert (PREV_INSN (x) == prevx);
 939
 940   gcc_assert (prevx == get_last_insn ());
 941
 942   for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
 943        x != 0;
 944        nextx = x, insn_cnt2++, x = PREV_INSN (x))
 945     gcc_assert (NEXT_INSN (x) == nextx);
 946
 947   gcc_assert (insn_cnt1 == insn_cnt2);
 948 }
 949 \f
 950 /* If we have assembler epilogues, the block falling through to exit must
 951    be the last one in the reordered chain when we reach final.  Ensure
 952    that this condition is met.  */
 953 static void
 954 fixup_fallthru_exit_predecessor (void)
 955 {
 956   edge e;
 957   edge_iterator ei;
 958   basic_block bb = NULL;
 959
 960   /* This transformation is not valid before reload, because we might
 961      separate a call from the instruction that copies the return
 962      value.  */
 963   gcc_assert (reload_completed);
 964
 965   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 966     if (e->flags & EDGE_FALLTHRU)
 967       bb = e->src;
 968
 969   if (bb && bb->aux)
 970     {
 971       basic_block c = ENTRY_BLOCK_PTR->next_bb;
 972
 973       /* If the very first block is the one with the fall-through exit
 974          edge, we have to split that block.  */
 975       if (c == bb)
 976         {
 977           bb = split_block (bb, NULL)->dest;
 978           bb->aux = c->aux;
 979           c->aux = bb;
 980           bb->il.rtl->footer = c->il.rtl->footer;
 981           c->il.rtl->footer = NULL;
 982         }
 983
 984       while (c->aux != bb)
 985         c = c->aux;
 986
 987       c->aux = bb->aux;
 988       while (c->aux)
 989         c = c->aux;
 990
 991       c->aux = bb;
 992       bb->aux = NULL;
 993     }
 994 }
 995 \f
 996 /* Return true in case it is possible to duplicate the basic block BB.  */
 997
 998 /* We do not want to declare the function in a header file, since it should
 999    only be used through the cfghooks interface, and we do not want to move
1000    it to cfgrtl.c since it would require also moving quite a lot of related
1001    code.  */
1002 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
1003
1004 bool
1005 cfg_layout_can_duplicate_bb_p (basic_block bb)
1006 {
1007   /* Do not attempt to duplicate tablejumps, as we need to unshare
1008      the dispatch table.  This is difficult to do, as the instructions
1009      computing jump destination may be hoisted outside the basic block.  */
1010   if (tablejump_p (BB_END (bb), NULL, NULL))
1011     return false;
1012
1013   /* Do not duplicate blocks containing insns that can't be copied.  */
1014   if (targetm.cannot_copy_insn_p)
1015     {
1016       rtx insn = BB_HEAD (bb);
1017       while (1)
1018         {
1019           if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
1020             return false;
1021           if (insn == BB_END (bb))
1022             break;
1023           insn = NEXT_INSN (insn);
1024         }
1025     }
1026
1027   return true;
1028 }
1029
1030 rtx
1031 duplicate_insn_chain (rtx from, rtx to)
1032 {
1033   rtx insn, last;
1034
1035   /* Avoid updating of boundaries of previous basic block.  The
1036      note will get removed from insn stream in fixup.  */
1037   last = emit_note (NOTE_INSN_DELETED);
1038
1039   /* Create copy at the end of INSN chain.  The chain will
1040      be reordered later.  */
1041   for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
1042     {
1043       switch (GET_CODE (insn))
1044         {
1045         case INSN:
1046         case CALL_INSN:
1047         case JUMP_INSN:
1048           /* Avoid copying of dispatch tables.  We never duplicate
1049              tablejumps, so this can hit only in case the table got
1050              moved far from original jump.  */
1051           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1052               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1053             break;
1054           emit_copy_of_insn_after (insn, get_last_insn ());
1055           break;
1056
1057         case CODE_LABEL:
1058           break;
1059
1060         case BARRIER:
1061           emit_barrier ();
1062           break;
1063
1064         case NOTE:
1065           switch (NOTE_LINE_NUMBER (insn))
1066             {
1067               /* In case prologue is empty and function contain label
1068                  in first BB, we may want to copy the block.  */
1069             case NOTE_INSN_PROLOGUE_END:
1070
1071             case NOTE_INSN_DELETED:
1072             case NOTE_INSN_DELETED_LABEL:
1073               /* No problem to strip these.  */
1074             case NOTE_INSN_EPILOGUE_BEG:
1075               /* Debug code expect these notes to exist just once.
1076                  Keep them in the master copy.
1077                  ??? It probably makes more sense to duplicate them for each
1078                  epilogue copy.  */
1079             case NOTE_INSN_FUNCTION_BEG:
1080               /* There is always just single entry to function.  */
1081             case NOTE_INSN_BASIC_BLOCK:
1082               break;
1083
1084             case NOTE_INSN_SWITCH_TEXT_SECTIONS:
1085               emit_note_copy (insn);
1086               break;
1087
1088             default:
1089               /* All other notes should have already been eliminated.
1090                */
1091               gcc_assert (NOTE_LINE_NUMBER (insn) >= 0);
1092
1093               /* It is possible that no_line_number is set and the note
1094                  won't be emitted.  */
1095               emit_note_copy (insn);
1096             }
1097           break;
1098         default:
1099           gcc_unreachable ();
1100         }
1101     }
1102   insn = NEXT_INSN (last);
1103   delete_insn (last);
1104   return insn;
1105 }
1106 /* Create a duplicate of the basic block BB.  */
1107
1108 /* We do not want to declare the function in a header file, since it should
1109    only be used through the cfghooks interface, and we do not want to move
1110    it to cfgrtl.c since it would require also moving quite a lot of related
1111    code.  */
1112 extern basic_block cfg_layout_duplicate_bb (basic_block);
1113
1114 basic_block
1115 cfg_layout_duplicate_bb (basic_block bb)
1116 {
1117   rtx insn;
1118   basic_block new_bb;
1119
1120   insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1121   new_bb = create_basic_block (insn,
1122                                insn ? get_last_insn () : NULL,
1123                                EXIT_BLOCK_PTR->prev_bb);
1124
1125   BB_COPY_PARTITION (new_bb, bb);
1126   if (bb->il.rtl->header)
1127     {
1128       insn = bb->il.rtl->header;
1129       while (NEXT_INSN (insn))
1130         insn = NEXT_INSN (insn);
1131       insn = duplicate_insn_chain (bb->il.rtl->header, insn);
1132       if (insn)
1133         new_bb->il.rtl->header = unlink_insn_chain (insn, get_last_insn ());
1134     }
1135
1136   if (bb->il.rtl->footer)
1137     {
1138       insn = bb->il.rtl->footer;
1139       while (NEXT_INSN (insn))
1140         insn = NEXT_INSN (insn);
1141       insn = duplicate_insn_chain (bb->il.rtl->footer, insn);
1142       if (insn)
1143         new_bb->il.rtl->footer = unlink_insn_chain (insn, get_last_insn ());
1144     }
1145
1146   if (bb->il.rtl->global_live_at_start)
1147     {
1148       new_bb->il.rtl->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
1149       new_bb->il.rtl->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
1150       COPY_REG_SET (new_bb->il.rtl->global_live_at_start,
1151                     bb->il.rtl->global_live_at_start);
1152       COPY_REG_SET (new_bb->il.rtl->global_live_at_end,
1153                     bb->il.rtl->global_live_at_end);
1154     }
1155
1156   return new_bb;
1157 }
1158 \f
1159 /* Main entry point to this module - initialize the datastructures for
1160    CFG layout changes.  It keeps LOOPS up-to-date if not null.
1161
1162    FLAGS is a set of additional flags to pass to cleanup_cfg().  It should
1163    include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1164    to date.  */
1165
1166 void
1167 cfg_layout_initialize (unsigned int flags)
1168 {
1169   initialize_original_copy_tables ();
1170
1171   cfg_layout_rtl_register_cfg_hooks ();
1172
1173   record_effective_endpoints ();
1174
1175   cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
1176 }
1177
1178 /* Splits superblocks.  */
1179 void
1180 break_superblocks (void)
1181 {
1182   sbitmap superblocks;
1183   bool need = false;
1184   basic_block bb;
1185
1186   superblocks = sbitmap_alloc (last_basic_block);
1187   sbitmap_zero (superblocks);
1188
1189   FOR_EACH_BB (bb)
1190     if (bb->flags & BB_SUPERBLOCK)
1191       {
1192         bb->flags &= ~BB_SUPERBLOCK;
1193         SET_BIT (superblocks, bb->index);
1194         need = true;
1195       }
1196
1197   if (need)
1198     {
1199       rebuild_jump_labels (get_insns ());
1200       find_many_sub_basic_blocks (superblocks);
1201     }
1202
1203   free (superblocks);
1204 }
1205
1206 /* Finalize the changes: reorder insn list according to the sequence specified
1207    by aux pointers, enter compensation code, rebuild scope forest.  */
1208
1209 void
1210 cfg_layout_finalize (void)
1211 {
1212 #ifdef ENABLE_CHECKING
1213   verify_flow_info ();
1214 #endif
1215   rtl_register_cfg_hooks ();
1216   if (reload_completed
1217 #ifdef HAVE_epilogue
1218       && !HAVE_epilogue
1219 #endif
1220       )
1221     fixup_fallthru_exit_predecessor ();
1222   fixup_reorder_chain ();
1223
1224   rebuild_jump_labels (get_insns ());
1225   delete_dead_jumptables ();
1226
1227 #ifdef ENABLE_CHECKING
1228   verify_insn_chain ();
1229   verify_flow_info ();
1230 #endif
1231 }
1232
1233 /* Checks whether all N blocks in BBS array can be copied.  */
1234 bool
1235 can_copy_bbs_p (basic_block *bbs, unsigned n)
1236 {
1237   unsigned i;
1238   edge e;
1239   int ret = true;
1240
1241   for (i = 0; i < n; i++)
1242     bbs[i]->flags |= BB_DUPLICATED;
1243
1244   for (i = 0; i < n; i++)
1245     {
1246       /* In case we should redirect abnormal edge during duplication, fail.  */
1247       edge_iterator ei;
1248       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1249         if ((e->flags & EDGE_ABNORMAL)
1250             && (e->dest->flags & BB_DUPLICATED))
1251           {
1252             ret = false;
1253             goto end;
1254           }
1255
1256       if (!can_duplicate_block_p (bbs[i]))
1257         {
1258           ret = false;
1259           break;
1260         }
1261     }
1262
1263 end:
1264   for (i = 0; i < n; i++)
1265     bbs[i]->flags &= ~BB_DUPLICATED;
1266
1267   return ret;
1268 }
1269
1270 /* Duplicates N basic blocks stored in array BBS.  Newly created basic blocks
1271    are placed into array NEW_BBS in the same order.  Edges from basic blocks
1272    in BBS are also duplicated and copies of those of them
1273    that lead into BBS are redirected to appropriate newly created block.  The
1274    function assigns bbs into loops (copy of basic block bb is assigned to
1275    bb->loop_father->copy loop, so this must be set up correctly in advance)
1276    and updates dominators locally (LOOPS structure that contains the information
1277    about dominators is passed to enable this).
1278
1279    BASE is the superloop to that basic block belongs; if its header or latch
1280    is copied, we do not set the new blocks as header or latch.
1281
1282    Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1283    also in the same order.
1284
1285    Newly created basic blocks are put after the basic block AFTER in the
1286    instruction stream, and the order of the blocks in BBS array is preserved.  */
1287
1288 void
1289 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1290           edge *edges, unsigned num_edges, edge *new_edges,
1291           struct loop *base, basic_block after)
1292 {
1293   unsigned i, j;
1294   basic_block bb, new_bb, dom_bb;
1295   edge e;
1296
1297   /* Duplicate bbs, update dominators, assign bbs to loops.  */
1298   for (i = 0; i < n; i++)
1299     {
1300       /* Duplicate.  */
1301       bb = bbs[i];
1302       new_bb = new_bbs[i] = duplicate_block (bb, NULL, after);
1303       after = new_bb;
1304       bb->flags |= BB_DUPLICATED;
1305       /* Possibly set loop header.  */
1306       if (bb->loop_father->header == bb && bb->loop_father != base)
1307         new_bb->loop_father->header = new_bb;
1308       /* Or latch.  */
1309       if (bb->loop_father->latch == bb && bb->loop_father != base)
1310         new_bb->loop_father->latch = new_bb;
1311     }
1312
1313   /* Set dominators.  */
1314   for (i = 0; i < n; i++)
1315     {
1316       bb = bbs[i];
1317       new_bb = new_bbs[i];
1318
1319       dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1320       if (dom_bb->flags & BB_DUPLICATED)
1321         {
1322           dom_bb = get_bb_copy (dom_bb);
1323           set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1324         }
1325     }
1326
1327   /* Redirect edges.  */
1328   for (j = 0; j < num_edges; j++)
1329     new_edges[j] = NULL;
1330   for (i = 0; i < n; i++)
1331     {
1332       edge_iterator ei;
1333       new_bb = new_bbs[i];
1334       bb = bbs[i];
1335
1336       FOR_EACH_EDGE (e, ei, new_bb->succs)
1337         {
1338           for (j = 0; j < num_edges; j++)
1339             if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1340               new_edges[j] = e;
1341
1342           if (!(e->dest->flags & BB_DUPLICATED))
1343             continue;
1344           redirect_edge_and_branch_force (e, get_bb_copy (e->dest));
1345         }
1346     }
1347
1348   /* Clear information about duplicates.  */
1349   for (i = 0; i < n; i++)
1350     bbs[i]->flags &= ~BB_DUPLICATED;
1351 }
1352
1353 #include "gt-cfglayout.h"