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               /* Otherwise we have some return, switch or computed
 743                  jump.  In the 99% case, there should not have been a
 744                  fallthru edge.  */
 745               gcc_assert (returnjump_p (bb_end_insn) || !e_fall);
 746               continue;
 747             }
 748         }
 749       else
 750         {
 751           /* No fallthru implies a noreturn function with EH edges, or
 752              something similarly bizarre.  In any case, we don't need to
 753              do anything.  */
 754           if (! e_fall)
 755             continue;
 756
 757           /* If the fallthru block is still next, nothing to do.  */
 758           if (bb->rbi->next == e_fall->dest)
 759             continue;
 760
 761           /* A fallthru to exit block.  */
 762           if (e_fall->dest == EXIT_BLOCK_PTR)
 763             continue;
 764         }
 765
 766       /* We got here if we need to add a new jump insn.  */
 767       nb = force_nonfallthru (e_fall);
 768       if (nb)
 769         {
 770           initialize_bb_rbi (nb);
 771           nb->rbi->visited = 1;
 772           nb->rbi->next = bb->rbi->next;
 773           bb->rbi->next = nb;
 774           /* Don't process this new block.  */
 775           old_bb = bb;
 776           bb = nb;
 777
 778           /* Make sure new bb is tagged for correct section (same as
 779              fall-thru source, since you cannot fall-throu across
 780              section boundaries).  */
 781           BB_COPY_PARTITION (e_fall->src, EDGE_PRED (bb, 0)->src);
 782           if (flag_reorder_blocks_and_partition
 783               && targetm.have_named_sections)
 784             {
 785               if (BB_PARTITION (EDGE_PRED (bb, 0)->src) == BB_COLD_PARTITION)
 786                 {
 787                   rtx new_note;
 788                   rtx note = BB_HEAD (e_fall->src);
 789
 790                   while (!INSN_P (note)
 791                          && note != BB_END (e_fall->src))
 792                     note = NEXT_INSN (note);
 793
 794                   new_note = emit_note_before
 795                                           (NOTE_INSN_UNLIKELY_EXECUTED_CODE,
 796                                            note);
 797                   NOTE_BASIC_BLOCK (new_note) = bb;
 798                 }
 799               if (JUMP_P (BB_END (bb))
 800                   && !any_condjump_p (BB_END (bb))
 801                   && (EDGE_SUCC (bb, 0)->flags & EDGE_CROSSING))
 802                 REG_NOTES (BB_END (bb)) = gen_rtx_EXPR_LIST
 803                   (REG_CROSSING_JUMP, NULL_RTX, REG_NOTES (BB_END (bb)));
 804             }
 805         }
 806     }
 807
 808   /* Put basic_block_info in the new order.  */
 809
 810   if (dump_file)
 811     {
 812       fprintf (dump_file, "Reordered sequence:\n");
 813       for (bb = ENTRY_BLOCK_PTR->next_bb, index = 0;
 814            bb;
 815            bb = bb->rbi->next, index++)
 816         {
 817           fprintf (dump_file, " %i ", index);
 818           if (bb->rbi->original)
 819             fprintf (dump_file, "duplicate of %i ",
 820                      bb->rbi->original->index);
 821           else if (forwarder_block_p (bb)
 822                    && !LABEL_P (BB_HEAD (bb)))
 823             fprintf (dump_file, "compensation ");
 824           else
 825             fprintf (dump_file, "bb %i ", bb->index);
 826           fprintf (dump_file, " [%i]\n", bb->frequency);
 827         }
 828     }
 829
 830   prev_bb = ENTRY_BLOCK_PTR;
 831   bb = ENTRY_BLOCK_PTR->next_bb;
 832   index = 0;
 833
 834   for (; bb; prev_bb = bb, bb = bb->rbi->next, index ++)
 835     {
 836       bb->index = index;
 837       BASIC_BLOCK (index) = bb;
 838
 839       update_unlikely_executed_notes (bb);
 840
 841       bb->prev_bb = prev_bb;
 842       prev_bb->next_bb = bb;
 843     }
 844   prev_bb->next_bb = EXIT_BLOCK_PTR;
 845   EXIT_BLOCK_PTR->prev_bb = prev_bb;
 846
 847   /* Annoying special case - jump around dead jumptables left in the code.  */
 848   FOR_EACH_BB (bb)
 849     {
 850       edge e;
 851       edge_iterator ei;
 852
 853       FOR_EACH_EDGE (e, ei, bb->succs)
 854         if (e->flags & EDGE_FALLTHRU)
 855           break;
 856
 857       if (e && !can_fallthru (e->src, e->dest))
 858         force_nonfallthru (e);
 859     }
 860 }
 861 \f
 862 /* Update the basic block number information in any
 863    NOTE_INSN_UNLIKELY_EXECUTED_CODE notes within the basic block.  */
 864
 865 static void
 866 update_unlikely_executed_notes (basic_block bb)
 867 {
 868   rtx cur_insn;
 869
 870   for (cur_insn = BB_HEAD (bb); cur_insn != BB_END (bb);
 871        cur_insn = NEXT_INSN (cur_insn))
 872     if (NOTE_P (cur_insn)
 873         && NOTE_LINE_NUMBER (cur_insn) == NOTE_INSN_UNLIKELY_EXECUTED_CODE)
 874       NOTE_BASIC_BLOCK (cur_insn) = bb;
 875 }
 876 \f
 877 /* Perform sanity checks on the insn chain.
 878    1. Check that next/prev pointers are consistent in both the forward and
 879       reverse direction.
 880    2. Count insns in chain, going both directions, and check if equal.
 881    3. Check that get_last_insn () returns the actual end of chain.  */
 882
 883 void
 884 verify_insn_chain (void)
 885 {
 886   rtx x, prevx, nextx;
 887   int insn_cnt1, insn_cnt2;
 888
 889   for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
 890        x != 0;
 891        prevx = x, insn_cnt1++, x = NEXT_INSN (x))
 892     gcc_assert (PREV_INSN (x) == prevx);
 893
 894   gcc_assert (prevx == get_last_insn ());
 895
 896   for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
 897        x != 0;
 898        nextx = x, insn_cnt2++, x = PREV_INSN (x))
 899     gcc_assert (NEXT_INSN (x) == nextx);
 900
 901   gcc_assert (insn_cnt1 == insn_cnt2);
 902 }
 903 \f
 904 /* If we have assembler epilogues, the block falling through to exit must
 905    be the last one in the reordered chain when we reach final.  Ensure
 906    that this condition is met.  */
 907 static void
 908 fixup_fallthru_exit_predecessor (void)
 909 {
 910   edge e;
 911   edge_iterator ei;
 912   basic_block bb = NULL;
 913
 914   /* This transformation is not valid before reload, because we might
 915      separate a call from the instruction that copies the return
 916      value.  */
 917   gcc_assert (reload_completed);
 918
 919   FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
 920     if (e->flags & EDGE_FALLTHRU)
 921       bb = e->src;
 922
 923   if (bb && bb->rbi->next)
 924     {
 925       basic_block c = ENTRY_BLOCK_PTR->next_bb;
 926
 927       /* If the very first block is the one with the fall-through exit
 928          edge, we have to split that block.  */
 929       if (c == bb)
 930         {
 931           bb = split_block (bb, NULL)->dest;
 932           initialize_bb_rbi (bb);
 933           bb->rbi->next = c->rbi->next;
 934           c->rbi->next = bb;
 935           bb->rbi->footer = c->rbi->footer;
 936           c->rbi->footer = NULL;
 937         }
 938
 939       while (c->rbi->next != bb)
 940         c = c->rbi->next;
 941
 942       c->rbi->next = bb->rbi->next;
 943       while (c->rbi->next)
 944         c = c->rbi->next;
 945
 946       c->rbi->next = bb;
 947       bb->rbi->next = NULL;
 948     }
 949 }
 950 \f
 951 /* Return true in case it is possible to duplicate the basic block BB.  */
 952
 953 /* We do not want to declare the function in a header file, since it should
 954    only be used through the cfghooks interface, and we do not want to move
 955    it to cfgrtl.c since it would require also moving quite a lot of related
 956    code.  */
 957 extern bool cfg_layout_can_duplicate_bb_p (basic_block);
 958
 959 bool
 960 cfg_layout_can_duplicate_bb_p (basic_block bb)
 961 {
 962   /* Do not attempt to duplicate tablejumps, as we need to unshare
 963      the dispatch table.  This is difficult to do, as the instructions
 964      computing jump destination may be hoisted outside the basic block.  */
 965   if (tablejump_p (BB_END (bb), NULL, NULL))
 966     return false;
 967
 968   /* Do not duplicate blocks containing insns that can't be copied.  */
 969   if (targetm.cannot_copy_insn_p)
 970     {
 971       rtx insn = BB_HEAD (bb);
 972       while (1)
 973         {
 974           if (INSN_P (insn) && targetm.cannot_copy_insn_p (insn))
 975             return false;
 976           if (insn == BB_END (bb))
 977             break;
 978           insn = NEXT_INSN (insn);
 979         }
 980     }
 981
 982   return true;
 983 }
 984
 985 rtx
 986 duplicate_insn_chain (rtx from, rtx to)
 987 {
 988   rtx insn, last;
 989
 990   /* Avoid updating of boundaries of previous basic block.  The
 991      note will get removed from insn stream in fixup.  */
 992   last = emit_note (NOTE_INSN_DELETED);
 993
 994   /* Create copy at the end of INSN chain.  The chain will
 995      be reordered later.  */
 996   for (insn = from; insn != NEXT_INSN (to); insn = NEXT_INSN (insn))
 997     {
 998       switch (GET_CODE (insn))
 999         {
1000         case INSN:
1001         case CALL_INSN:
1002         case JUMP_INSN:
1003           /* Avoid copying of dispatch tables.  We never duplicate
1004              tablejumps, so this can hit only in case the table got
1005              moved far from original jump.  */
1006           if (GET_CODE (PATTERN (insn)) == ADDR_VEC
1007               || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
1008             break;
1009           emit_copy_of_insn_after (insn, get_last_insn ());
1010           break;
1011
1012         case CODE_LABEL:
1013           break;
1014
1015         case BARRIER:
1016           emit_barrier ();
1017           break;
1018
1019         case NOTE:
1020           switch (NOTE_LINE_NUMBER (insn))
1021             {
1022               /* In case prologue is empty and function contain label
1023                  in first BB, we may want to copy the block.  */
1024             case NOTE_INSN_PROLOGUE_END:
1025
1026             case NOTE_INSN_LOOP_BEG:
1027             case NOTE_INSN_LOOP_END:
1028               /* Strip down the loop notes - we don't really want to keep
1029                  them consistent in loop copies.  */
1030             case NOTE_INSN_DELETED:
1031             case NOTE_INSN_DELETED_LABEL:
1032               /* No problem to strip these.  */
1033             case NOTE_INSN_EPILOGUE_BEG:
1034             case NOTE_INSN_FUNCTION_END:
1035               /* Debug code expect these notes to exist just once.
1036                  Keep them in the master copy.
1037                  ??? It probably makes more sense to duplicate them for each
1038                  epilogue copy.  */
1039             case NOTE_INSN_FUNCTION_BEG:
1040               /* There is always just single entry to function.  */
1041             case NOTE_INSN_BASIC_BLOCK:
1042               break;
1043
1044             case NOTE_INSN_REPEATED_LINE_NUMBER:
1045             case NOTE_INSN_UNLIKELY_EXECUTED_CODE:
1046               emit_note_copy (insn);
1047               break;
1048
1049             default:
1050               /* All other notes should have already been eliminated.
1051                */
1052               gcc_assert (NOTE_LINE_NUMBER (insn) >= 0);
1053
1054               /* It is possible that no_line_number is set and the note
1055                  won't be emitted.  */
1056               emit_note_copy (insn);
1057             }
1058           break;
1059         default:
1060           gcc_unreachable ();
1061         }
1062     }
1063   insn = NEXT_INSN (last);
1064   delete_insn (last);
1065   return insn;
1066 }
1067 /* Create a duplicate of the basic block BB.  */
1068
1069 /* We do not want to declare the function in a header file, since it should
1070    only be used through the cfghooks interface, and we do not want to move
1071    it to cfgrtl.c since it would require also moving quite a lot of related
1072    code.  */
1073 extern basic_block cfg_layout_duplicate_bb (basic_block);
1074
1075 basic_block
1076 cfg_layout_duplicate_bb (basic_block bb)
1077 {
1078   rtx insn;
1079   basic_block new_bb;
1080
1081   insn = duplicate_insn_chain (BB_HEAD (bb), BB_END (bb));
1082   new_bb = create_basic_block (insn,
1083                                insn ? get_last_insn () : NULL,
1084                                EXIT_BLOCK_PTR->prev_bb);
1085
1086   BB_COPY_PARTITION (new_bb, bb);
1087   if (bb->rbi->header)
1088     {
1089       insn = bb->rbi->header;
1090       while (NEXT_INSN (insn))
1091         insn = NEXT_INSN (insn);
1092       insn = duplicate_insn_chain (bb->rbi->header, insn);
1093       if (insn)
1094         new_bb->rbi->header = unlink_insn_chain (insn, get_last_insn ());
1095     }
1096
1097   if (bb->rbi->footer)
1098     {
1099       insn = bb->rbi->footer;
1100       while (NEXT_INSN (insn))
1101         insn = NEXT_INSN (insn);
1102       insn = duplicate_insn_chain (bb->rbi->footer, insn);
1103       if (insn)
1104         new_bb->rbi->footer = unlink_insn_chain (insn, get_last_insn ());
1105     }
1106
1107   if (bb->global_live_at_start)
1108     {
1109       new_bb->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
1110       new_bb->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
1111       COPY_REG_SET (new_bb->global_live_at_start, bb->global_live_at_start);
1112       COPY_REG_SET (new_bb->global_live_at_end, bb->global_live_at_end);
1113     }
1114
1115   return new_bb;
1116 }
1117 \f
1118 /* Main entry point to this module - initialize the datastructures for
1119    CFG layout changes.  It keeps LOOPS up-to-date if not null.
1120
1121    FLAGS is a set of additional flags to pass to cleanup_cfg().  It should
1122    include CLEANUP_UPDATE_LIFE if liveness information must be kept up
1123    to date.  */
1124
1125 void
1126 cfg_layout_initialize (unsigned int flags)
1127 {
1128   basic_block bb;
1129
1130   /* Our algorithm depends on fact that there are no dead jumptables
1131      around the code.  */
1132   alloc_rbi_pool ();
1133
1134   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1135     initialize_bb_rbi (bb);
1136
1137   cfg_layout_rtl_register_cfg_hooks ();
1138
1139   record_effective_endpoints ();
1140
1141   cleanup_cfg (CLEANUP_CFGLAYOUT | flags);
1142 }
1143
1144 /* Splits superblocks.  */
1145 void
1146 break_superblocks (void)
1147 {
1148   sbitmap superblocks;
1149   bool need = false;
1150   basic_block bb;
1151
1152   superblocks = sbitmap_alloc (last_basic_block);
1153   sbitmap_zero (superblocks);
1154
1155   FOR_EACH_BB (bb)
1156     if (bb->flags & BB_SUPERBLOCK)
1157       {
1158         bb->flags &= ~BB_SUPERBLOCK;
1159         SET_BIT (superblocks, bb->index);
1160         need = true;
1161       }
1162
1163   if (need)
1164     {
1165       rebuild_jump_labels (get_insns ());
1166       find_many_sub_basic_blocks (superblocks);
1167     }
1168
1169   free (superblocks);
1170 }
1171
1172 /* Finalize the changes: reorder insn list according to the sequence, enter
1173    compensation code, rebuild scope forest.  */
1174
1175 void
1176 cfg_layout_finalize (void)
1177 {
1178   basic_block bb;
1179
1180 #ifdef ENABLE_CHECKING
1181   verify_flow_info ();
1182 #endif
1183   rtl_register_cfg_hooks ();
1184   if (reload_completed
1185 #ifdef HAVE_epilogue
1186       && !HAVE_epilogue
1187 #endif
1188       )
1189     fixup_fallthru_exit_predecessor ();
1190   fixup_reorder_chain ();
1191
1192 #ifdef ENABLE_CHECKING
1193   verify_insn_chain ();
1194 #endif
1195
1196   free_rbi_pool ();
1197   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1198     bb->rbi = NULL;
1199
1200   break_superblocks ();
1201
1202 #ifdef ENABLE_CHECKING
1203   verify_flow_info ();
1204 #endif
1205 }
1206
1207 /* Checks whether all N blocks in BBS array can be copied.  */
1208 bool
1209 can_copy_bbs_p (basic_block *bbs, unsigned n)
1210 {
1211   unsigned i;
1212   edge e;
1213   int ret = true;
1214
1215   for (i = 0; i < n; i++)
1216     bbs[i]->rbi->duplicated = 1;
1217
1218   for (i = 0; i < n; i++)
1219     {
1220       /* In case we should redirect abnormal edge during duplication, fail.  */
1221       edge_iterator ei;
1222       FOR_EACH_EDGE (e, ei, bbs[i]->succs)
1223         if ((e->flags & EDGE_ABNORMAL)
1224             && e->dest->rbi->duplicated)
1225           {
1226             ret = false;
1227             goto end;
1228           }
1229
1230       if (!can_duplicate_block_p (bbs[i]))
1231         {
1232           ret = false;
1233           break;
1234         }
1235     }
1236
1237 end:
1238   for (i = 0; i < n; i++)
1239     bbs[i]->rbi->duplicated = 0;
1240
1241   return ret;
1242 }
1243
1244 /* Duplicates N basic blocks stored in array BBS.  Newly created basic blocks
1245    are placed into array NEW_BBS in the same order.  Edges from basic blocks
1246    in BBS are also duplicated and copies of those of them
1247    that lead into BBS are redirected to appropriate newly created block.  The
1248    function assigns bbs into loops (copy of basic block bb is assigned to
1249    bb->loop_father->copy loop, so this must be set up correctly in advance)
1250    and updates dominators locally (LOOPS structure that contains the information
1251    about dominators is passed to enable this).
1252
1253    BASE is the superloop to that basic block belongs; if its header or latch
1254    is copied, we do not set the new blocks as header or latch.
1255
1256    Created copies of N_EDGES edges in array EDGES are stored in array NEW_EDGES,
1257    also in the same order.  */
1258
1259 void
1260 copy_bbs (basic_block *bbs, unsigned n, basic_block *new_bbs,
1261           edge *edges, unsigned n_edges, edge *new_edges,
1262           struct loop *base)
1263 {
1264   unsigned i, j;
1265   basic_block bb, new_bb, dom_bb;
1266   edge e;
1267
1268   /* Duplicate bbs, update dominators, assign bbs to loops.  */
1269   for (i = 0; i < n; i++)
1270     {
1271       /* Duplicate.  */
1272       bb = bbs[i];
1273       new_bb = new_bbs[i] = duplicate_block (bb, NULL);
1274       bb->rbi->duplicated = 1;
1275       /* Add to loop.  */
1276       add_bb_to_loop (new_bb, bb->loop_father->copy);
1277       /* Possibly set header.  */
1278       if (bb->loop_father->header == bb && bb->loop_father != base)
1279         new_bb->loop_father->header = new_bb;
1280       /* Or latch.  */
1281       if (bb->loop_father->latch == bb && bb->loop_father != base)
1282         new_bb->loop_father->latch = new_bb;
1283     }
1284
1285   /* Set dominators.  */
1286   for (i = 0; i < n; i++)
1287     {
1288       bb = bbs[i];
1289       new_bb = new_bbs[i];
1290
1291       dom_bb = get_immediate_dominator (CDI_DOMINATORS, bb);
1292       if (dom_bb->rbi->duplicated)
1293         {
1294           dom_bb = dom_bb->rbi->copy;
1295           set_immediate_dominator (CDI_DOMINATORS, new_bb, dom_bb);
1296         }
1297     }
1298
1299   /* Redirect edges.  */
1300   for (j = 0; j < n_edges; j++)
1301     new_edges[j] = NULL;
1302   for (i = 0; i < n; i++)
1303     {
1304       edge_iterator ei;
1305       new_bb = new_bbs[i];
1306       bb = bbs[i];
1307
1308       FOR_EACH_EDGE (e, ei, new_bb->succs)
1309         {
1310           for (j = 0; j < n_edges; j++)
1311             if (edges[j] && edges[j]->src == bb && edges[j]->dest == e->dest)
1312               new_edges[j] = e;
1313
1314           if (!e->dest->rbi->duplicated)
1315             continue;
1316           redirect_edge_and_branch_force (e, e->dest->rbi->copy);
1317         }
1318     }
1319
1320   /* Clear information about duplicates.  */
1321   for (i = 0; i < n; i++)
1322     bbs[i]->rbi->duplicated = 0;
1323 }
1324
1325 #include "gt-cfglayout.h"