gcc/cfglayout.c

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