contrib/gcc-3.4/gcc/cfglayout.c

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