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