gcc/cfglayout.c

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