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 "tree.h"
  24 #include "rtl.h"
  25 #include "hard-reg-set.h"
  26 #include "basic-block.h"
  27 #include "insn-config.h"
  28 #include "output.h"
  29 #include "function.h"
  30 #include "obstack.h"
  31 #include "cfglayout.h"
  32
  33 /* The contents of the current function definition are allocated
  34    in this obstack, and all are freed at the end of the function.  */
  35 extern struct obstack flow_obstack;
  36
  37 /* Holds the interesting trailing notes for the function.  */
  38 static rtx function_tail_eff_head;
  39
  40 static rtx skip_insns_after_block       PARAMS ((basic_block));
  41 static void record_effective_endpoints  PARAMS ((void));
  42 static rtx label_for_bb                 PARAMS ((basic_block));
  43 static void fixup_reorder_chain         PARAMS ((void));
  44
  45 static void set_block_levels            PARAMS ((tree, int));
  46 static void change_scope                PARAMS ((rtx, tree, tree));
  47
  48 void verify_insn_chain                  PARAMS ((void));
  49 static void fixup_fallthru_exit_predecessor PARAMS ((void));
  50
  51 /* Map insn uid to lexical block.  */
  52 static varray_type insn_scopes;
  53 \f
  54 /* Skip over inter-block insns occurring after BB which are typically
  55    associated with BB (e.g., barriers). If there are any such insns,
  56    we return the last one. Otherwise, we return the end of BB.  */
  57
  58 static rtx
  59 skip_insns_after_block (bb)
  60      basic_block bb;
  61 {
  62   rtx insn, last_insn, next_head, prev;
  63
  64   next_head = NULL_RTX;
  65   if (bb->index + 1 != n_basic_blocks)
  66     next_head = BASIC_BLOCK (bb->index + 1)->head;
  67
  68   for (last_insn = insn = bb->end; (insn = NEXT_INSN (insn)) != 0; )
  69     {
  70       if (insn == next_head)
  71         break;
  72
  73       switch (GET_CODE (insn))
  74         {
  75         case BARRIER:
  76           last_insn = insn;
  77           continue;
  78
  79         case NOTE:
  80           switch (NOTE_LINE_NUMBER (insn))
  81             {
  82             case NOTE_INSN_LOOP_END:
  83             case NOTE_INSN_BLOCK_END:
  84               last_insn = insn;
  85               continue;
  86             case NOTE_INSN_DELETED:
  87             case NOTE_INSN_DELETED_LABEL:
  88               continue;
  89
  90             default:
  91               continue;
  92               break;
  93             }
  94           break;
  95
  96         case CODE_LABEL:
  97           if (NEXT_INSN (insn)
  98               && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
  99               && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
 100                   || GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
 101             {
 102               insn = NEXT_INSN (insn);
 103               last_insn = insn;
 104               continue;
 105             }
 106           break;
 107
 108         default:
 109           break;
 110         }
 111
 112       break;
 113     }
 114
 115   /* It is possible to hit contradictory sequence.  For instance:
 116
 117      jump_insn
 118      NOTE_INSN_LOOP_BEG
 119      barrier
 120
 121      Where barrier belongs to jump_insn, but the note does not.  This can be
 122      created by removing the basic block originally following
 123      NOTE_INSN_LOOP_BEG.  In such case reorder the notes.  */
 124
 125   for (insn = last_insn; insn != bb->end; insn = prev)
 126     {
 127       prev = PREV_INSN (insn);
 128       if (GET_CODE (insn) == NOTE)
 129         switch (NOTE_LINE_NUMBER (insn))
 130           {
 131           case NOTE_INSN_LOOP_END:
 132           case NOTE_INSN_BLOCK_END:
 133           case NOTE_INSN_DELETED:
 134           case NOTE_INSN_DELETED_LABEL:
 135             continue;
 136           default:
 137             reorder_insns (insn, insn, last_insn);
 138         }
 139     }
 140
 141   return last_insn;
 142 }
 143
 144 /* Locate or create a label for a given basic block.  */
 145
 146 static rtx
 147 label_for_bb (bb)
 148      basic_block bb;
 149 {
 150   rtx label = bb->head;
 151
 152   if (GET_CODE (label) != CODE_LABEL)
 153     {
 154       if (rtl_dump_file)
 155         fprintf (rtl_dump_file, "Emitting label for block %d\n", bb->index);
 156
 157       label = block_label (bb);
 158       if (bb->head == PREV_INSN (RBI (bb)->eff_head))
 159         RBI (bb)->eff_head = label;
 160     }
 161
 162   return label;
 163 }
 164
 165 /* Locate the effective beginning and end of the insn chain for each
 166    block, as defined by skip_insns_after_block above.  */
 167
 168 static void
 169 record_effective_endpoints ()
 170 {
 171   rtx next_insn = get_insns ();
 172   int i;
 173
 174   for (i = 0; i < n_basic_blocks; i++)
 175     {
 176       basic_block bb = BASIC_BLOCK (i);
 177       rtx end;
 178
 179       RBI (bb)->eff_head = next_insn;
 180       end = skip_insns_after_block (bb);
 181       RBI (bb)->eff_end = end;
 182       next_insn = NEXT_INSN (end);
 183     }
 184
 185   function_tail_eff_head = next_insn;
 186 }
 187 \f
 188 /* Build a varray mapping INSN_UID to lexical block.  Return it.  */
 189
 190 void
 191 scope_to_insns_initialize ()
 192 {
 193   tree block = NULL;
 194   rtx insn, next;
 195
 196   VARRAY_TREE_INIT (insn_scopes, get_max_uid (), "insn scopes");
 197
 198   for (insn = get_insns (); insn; insn = next)
 199     {
 200       next = NEXT_INSN (insn);
 201
 202       if (active_insn_p (insn)
 203           && GET_CODE (PATTERN (insn)) != ADDR_VEC
 204           && GET_CODE (PATTERN (insn)) != ADDR_DIFF_VEC)
 205         VARRAY_TREE (insn_scopes, INSN_UID (insn)) = block;
 206       else if (GET_CODE (insn) == NOTE)
 207         {
 208           switch (NOTE_LINE_NUMBER (insn))
 209             {
 210             case NOTE_INSN_BLOCK_BEG:
 211               block = NOTE_BLOCK (insn);
 212               delete_insn (insn);
 213               break;
 214             case NOTE_INSN_BLOCK_END:
 215               block = BLOCK_SUPERCONTEXT (block);
 216               delete_insn (insn);
 217               break;
 218             default:
 219               break;
 220             }
 221         }
 222     }
 223 }
 224
 225 /* For each lexical block, set BLOCK_NUMBER to the depth at which it is
 226    found in the block tree.  */
 227
 228 static void
 229 set_block_levels (block, level)
 230      tree block;
 231      int level;
 232 {
 233   while (block)
 234     {
 235       BLOCK_NUMBER (block) = level;
 236       set_block_levels (BLOCK_SUBBLOCKS (block), level + 1);
 237       block = BLOCK_CHAIN (block);
 238     }
 239 }
 240
 241 /* Emit lexical block notes needed to change scope from S1 to S2.  */
 242
 243 static void
 244 change_scope (orig_insn, s1, s2)
 245      rtx orig_insn;
 246      tree s1, s2;
 247 {
 248   rtx insn = orig_insn;
 249   tree com = NULL_TREE;
 250   tree ts1 = s1, ts2 = s2;
 251   tree s;
 252
 253   while (ts1 != ts2)
 254     {
 255       if (ts1 == NULL || ts2 == NULL)
 256         abort ();
 257       if (BLOCK_NUMBER (ts1) > BLOCK_NUMBER (ts2))
 258         ts1 = BLOCK_SUPERCONTEXT (ts1);
 259       else if (BLOCK_NUMBER (ts1) < BLOCK_NUMBER (ts2))
 260         ts2 = BLOCK_SUPERCONTEXT (ts2);
 261       else
 262         {
 263           ts1 = BLOCK_SUPERCONTEXT (ts1);
 264           ts2 = BLOCK_SUPERCONTEXT (ts2);
 265         }
 266     }
 267   com = ts1;
 268
 269   /* Close scopes.  */
 270   s = s1;
 271   while (s != com)
 272     {
 273       rtx note = emit_note_before (NOTE_INSN_BLOCK_END, insn);
 274       NOTE_BLOCK (note) = s;
 275       s = BLOCK_SUPERCONTEXT (s);
 276     }
 277
 278   /* Open scopes.  */
 279   s = s2;
 280   while (s != com)
 281     {
 282       insn = emit_note_before (NOTE_INSN_BLOCK_BEG, insn);
 283       NOTE_BLOCK (insn) = s;
 284       s = BLOCK_SUPERCONTEXT (s);
 285     }
 286 }
 287
 288 /* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
 289    on the scope tree and the newly reordered instructions.  */
 290
 291 void
 292 scope_to_insns_finalize ()
 293 {
 294   tree cur_block = DECL_INITIAL (cfun->decl);
 295   rtx insn, note;
 296
 297   /* Tag the blocks with a depth number so that change_scope can find
 298      the common parent easily.  */
 299   set_block_levels (cur_block, 0);
 300
 301   for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
 302     {
 303       tree this_block;
 304
 305       if ((size_t) INSN_UID (insn) >= insn_scopes->num_elements)
 306         continue;
 307       this_block = VARRAY_TREE (insn_scopes, INSN_UID (insn));
 308       if (! this_block)
 309         continue;
 310
 311       if (this_block != cur_block)
 312         {
 313           change_scope (insn, cur_block, this_block);
 314           cur_block = this_block;
 315         }
 316     }
 317
 318   VARRAY_FREE (insn_scopes);
 319
 320   /* change_scope emits before the insn, not after.  */
 321   note = emit_note (NULL, NOTE_INSN_DELETED);
 322   change_scope (note, cur_block, DECL_INITIAL (cfun->decl));
 323   delete_insn (note);
 324
 325   reorder_blocks ();
 326 }
 327 \f
 328 /* Given a reorder chain, rearrange the code to match.  */
 329
 330 static void
 331 fixup_reorder_chain ()
 332 {
 333   basic_block bb, last_bb;
 334   int index;
 335   rtx insn;
 336   int old_n_basic_blocks = n_basic_blocks;
 337
 338   /* First do the bulk reordering -- rechain the blocks without regard to
 339      the needed changes to jumps and labels.  */
 340
 341   for (last_bb = BASIC_BLOCK (0), bb = RBI (last_bb)->next, index = 1;
 342        bb != 0;
 343        last_bb = bb, bb = RBI (bb)->next, index++)
 344     {
 345       rtx last_e = RBI (last_bb)->eff_end;
 346       rtx curr_h = RBI (bb)->eff_head;
 347
 348       NEXT_INSN (last_e) = curr_h;
 349       PREV_INSN (curr_h) = last_e;
 350     }
 351
 352   if (index != n_basic_blocks)
 353     abort ();
 354
 355   insn = RBI (last_bb)->eff_end;
 356   NEXT_INSN (insn) = function_tail_eff_head;
 357   if (function_tail_eff_head)
 358     PREV_INSN (function_tail_eff_head) = insn;
 359
 360   while (NEXT_INSN (insn))
 361     insn = NEXT_INSN (insn);
 362
 363   set_last_insn (insn);
 364 #ifdef ENABLE_CHECKING
 365   verify_insn_chain ();
 366 #endif
 367
 368   /* Now add jumps and labels as needed to match the blocks new
 369      outgoing edges.  */
 370
 371   for (bb = BASIC_BLOCK (0); bb ; bb = RBI (bb)->next)
 372     {
 373       edge e_fall, e_taken, e;
 374       rtx bb_end_insn;
 375       basic_block nb;
 376
 377       if (bb->succ == NULL)
 378         continue;
 379
 380       /* Find the old fallthru edge, and another non-EH edge for
 381          a taken jump.  */
 382       e_taken = e_fall = NULL;
 383       for (e = bb->succ; e ; e = e->succ_next)
 384         if (e->flags & EDGE_FALLTHRU)
 385           e_fall = e;
 386         else if (! (e->flags & EDGE_EH))
 387           e_taken = e;
 388
 389       bb_end_insn = bb->end;
 390       if (GET_CODE (bb_end_insn) == JUMP_INSN)
 391         {
 392           if (any_condjump_p (bb_end_insn))
 393             {
 394               /* If the old fallthru is still next, nothing to do.  */
 395               if (RBI (bb)->next == e_fall->dest
 396                   || (!RBI (bb)->next
 397                       && e_fall->dest == EXIT_BLOCK_PTR))
 398                 continue;
 399
 400               /* There is one special case: if *neither* block is next,
 401                  such as happens at the very end of a function, then we'll
 402                  need to add a new unconditional jump.  Choose the taken
 403                  edge based on known or assumed probability.  */
 404               if (RBI (bb)->next != e_taken->dest)
 405                 {
 406                   rtx note = find_reg_note (bb_end_insn, REG_BR_PROB, 0);
 407
 408                   if (note
 409                       && INTVAL (XEXP (note, 0)) < REG_BR_PROB_BASE / 2
 410                       && invert_jump (bb_end_insn,
 411                                       label_for_bb (e_fall->dest), 0))
 412                     {
 413                       e_fall->flags &= ~EDGE_FALLTHRU;
 414                       e_taken->flags |= EDGE_FALLTHRU;
 415                       update_br_prob_note (bb);
 416                       e = e_fall, e_fall = e_taken, e_taken = e;
 417                     }
 418                 }
 419
 420               /* Otherwise we can try to invert the jump.  This will
 421                  basically never fail, however, keep up the pretense.  */
 422               else if (invert_jump (bb_end_insn,
 423                                     label_for_bb (e_fall->dest), 0))
 424                 {
 425                   e_fall->flags &= ~EDGE_FALLTHRU;
 426                   e_taken->flags |= EDGE_FALLTHRU;
 427                   update_br_prob_note (bb);
 428                   continue;
 429                 }
 430             }
 431           else if (returnjump_p (bb_end_insn))
 432             continue;
 433           else
 434             {
 435               /* Otherwise we have some switch or computed jump.  In the
 436                  99% case, there should not have been a fallthru edge.  */
 437               if (! e_fall)
 438                 continue;
 439
 440 #ifdef CASE_DROPS_THROUGH
 441               /* Except for VAX.  Since we didn't have predication for the
 442                  tablejump, the fallthru block should not have moved.  */
 443               if (RBI (bb)->next == e_fall->dest)
 444                 continue;
 445               bb_end_insn = skip_insns_after_block (bb);
 446 #else
 447               abort ();
 448 #endif
 449             }
 450         }
 451       else
 452         {
 453           /* No fallthru implies a noreturn function with EH edges, or
 454              something similarly bizarre.  In any case, we don't need to
 455              do anything.  */
 456           if (! e_fall)
 457             continue;
 458
 459           /* If the fallthru block is still next, nothing to do.  */
 460           if (RBI (bb)->next == e_fall->dest)
 461             continue;
 462
 463           /* A fallthru to exit block.  */
 464           if (!RBI (bb)->next && e_fall->dest == EXIT_BLOCK_PTR)
 465             continue;
 466         }
 467
 468       /* We got here if we need to add a new jump insn.  */
 469       nb = force_nonfallthru (e_fall);
 470       if (nb)
 471         {
 472           alloc_aux_for_block (nb, sizeof (struct reorder_block_def));
 473           RBI (nb)->eff_head = nb->head;
 474           RBI (nb)->eff_end = NEXT_INSN (nb->end);
 475           RBI (nb)->visited = 1;
 476           RBI (nb)->next = RBI (bb)->next;
 477           RBI (bb)->next = nb;
 478           /* Don't process this new block.  */
 479           bb = nb;
 480         }
 481     }
 482
 483   /* Put basic_block_info in the new order.  */
 484   bb = BASIC_BLOCK (0);
 485   index = 0;
 486
 487   if (rtl_dump_file)
 488     fprintf (rtl_dump_file, "Reordered sequence:\n");
 489
 490   for (; bb; bb = RBI (bb)->next, index++)
 491     {
 492       if (rtl_dump_file)
 493         fprintf (rtl_dump_file, " %i %sbb %i freq %i\n", index,
 494                  bb->index >= old_n_basic_blocks ? "compensation " : "",
 495                  bb->index,
 496                  bb->frequency);
 497
 498       bb->index = index;
 499       BASIC_BLOCK (index) = bb;
 500     }
 501 }
 502 \f
 503 /* Perform sanity checks on the insn chain.
 504    1. Check that next/prev pointers are consistent in both the forward and
 505       reverse direction.
 506    2. Count insns in chain, going both directions, and check if equal.
 507    3. Check that get_last_insn () returns the actual end of chain.  */
 508
 509 void
 510 verify_insn_chain ()
 511 {
 512   rtx x, prevx, nextx;
 513   int insn_cnt1, insn_cnt2;
 514
 515   for (prevx = NULL, insn_cnt1 = 1, x = get_insns ();
 516        x != 0;
 517        prevx = x, insn_cnt1++, x = NEXT_INSN (x))
 518     if (PREV_INSN (x) != prevx)
 519       abort ();
 520
 521   if (prevx != get_last_insn ())
 522     abort ();
 523
 524   for (nextx = NULL, insn_cnt2 = 1, x = get_last_insn ();
 525        x != 0;
 526        nextx = x, insn_cnt2++, x = PREV_INSN (x))
 527     if (NEXT_INSN (x) != nextx)
 528       abort ();
 529
 530   if (insn_cnt1 != insn_cnt2)
 531     abort ();
 532 }
 533
 534 /* The block falling through to exit must be the last one in the reordered
 535    chain.  Ensure it is.  */
 536
 537 static void
 538 fixup_fallthru_exit_predecessor ()
 539 {
 540   edge e;
 541   basic_block bb = NULL;
 542
 543   for (e = EXIT_BLOCK_PTR->pred; e; e = e->pred_next)
 544     if (e->flags & EDGE_FALLTHRU)
 545       bb = e->src;
 546
 547   if (bb && RBI (bb)->next)
 548     {
 549       basic_block c = BASIC_BLOCK (0);
 550
 551       while (RBI (c)->next != bb)
 552         c = RBI (c)->next;
 553
 554       RBI (c)->next = RBI (bb)->next;
 555       while (RBI (c)->next)
 556         c = RBI (c)->next;
 557
 558       RBI (c)->next = bb;
 559       RBI (bb)->next = NULL;
 560     }
 561 }
 562 \f
 563 /* Main entry point to this module: initialize the datastructures for CFG
 564    layout changes.  */
 565
 566 void
 567 cfg_layout_initialize ()
 568 {
 569   alloc_aux_for_blocks (sizeof (struct reorder_block_def));
 570
 571   scope_to_insns_initialize ();
 572
 573   record_effective_endpoints ();
 574 }
 575
 576 /* Finalize the changes: reorder insn list according to the sequence, enter
 577    compensation code, rebuild scope forest.  */
 578
 579 void
 580 cfg_layout_finalize ()
 581 {
 582   fixup_fallthru_exit_predecessor ();
 583   fixup_reorder_chain ();
 584
 585 #ifdef ENABLE_CHECKING
 586   verify_insn_chain ();
 587 #endif
 588
 589   scope_to_insns_finalize ();
 590
 591   free_aux_for_blocks ();
 592
 593 #ifdef ENABLE_CHECKING
 594   verify_flow_info ();
 595 #endif
 596 }