gcc/cfgcleanup.c

   1 /* Control flow optimization code for GNU compiler.
   2    Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   3    1999, 2000, 2001 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file contains optimizer of the control flow.  The main entrypoint is
  23    cleanup_cfg.  Following optimizations are performed:
  24
  25    - Unreachable blocks removal
  26    - Edge forwarding (edge to the forwarder block is forwarded to it's
  27      succesor.  Simplification of the branch instruction is performed by
  28      underlying infrastructure so branch can be converted to simplejump or
  29      elliminated).
  30    - Cross jumping (tail merging)
  31    - Conditional jump-around-simplejump simplification
  32    - Basic block merging.  */
  33
  34 #include "config.h"
  35 #include "system.h"
  36 #include "rtl.h"
  37 #include "hard-reg-set.h"
  38 #include "basic-block.h"
  39 #include "timevar.h"
  40 #include "output.h"
  41 #include "insn-config.h"
  42 #include "flags.h"
  43 #include "recog.h"
  44 #include "toplev.h"
  45
  46 #include "obstack.h"
  47
  48 static bool try_crossjump_to_edge       PARAMS ((int, edge, edge));
  49 static bool try_crossjump_bb            PARAMS ((int, basic_block));
  50 static bool outgoing_edges_match        PARAMS ((basic_block, basic_block));
  51 static int flow_find_cross_jump         PARAMS ((int, basic_block, basic_block,
  52                                                  rtx *, rtx *));
  53
  54 static bool delete_unreachable_blocks   PARAMS ((void));
  55 static bool tail_recursion_label_p      PARAMS ((rtx));
  56 static void merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
  57                                                           basic_block));
  58 static void merge_blocks_move_successor_nojumps PARAMS ((basic_block,
  59                                                         basic_block));
  60 static bool merge_blocks                PARAMS ((edge,basic_block,basic_block,
  61                                                  int));
  62 static bool try_optimize_cfg            PARAMS ((int));
  63 static bool try_simplify_condjump       PARAMS ((basic_block));
  64 static bool try_forward_edges           PARAMS ((int, basic_block));
  65 \f
  66 /* Simplify a conditional jump around an unconditional jump.
  67    Return true if something changed.  */
  68
  69 static bool
  70 try_simplify_condjump (cbranch_block)
  71      basic_block cbranch_block;
  72 {
  73   basic_block jump_block, jump_dest_block, cbranch_dest_block;
  74   edge cbranch_jump_edge, cbranch_fallthru_edge;
  75   rtx cbranch_insn;
  76
  77   /* Verify that there are exactly two successors.  */
  78   if (!cbranch_block->succ
  79       || !cbranch_block->succ->succ_next
  80       || cbranch_block->succ->succ_next->succ_next)
  81     return false;
  82
  83   /* Verify that we've got a normal conditional branch at the end
  84      of the block.  */
  85   cbranch_insn = cbranch_block->end;
  86   if (!any_condjump_p (cbranch_insn))
  87     return false;
  88
  89   cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
  90   cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
  91
  92   /* The next block must not have multiple predecessors, must not
  93      be the last block in the function, and must contain just the
  94      unconditional jump.  */
  95   jump_block = cbranch_fallthru_edge->dest;
  96   if (jump_block->pred->pred_next
  97       || jump_block->index == n_basic_blocks - 1
  98       || !forwarder_block_p (jump_block))
  99     return false;
 100   jump_dest_block = jump_block->succ->dest;
 101
 102   /* The conditional branch must target the block after the
 103      unconditional branch.  */
 104   cbranch_dest_block = cbranch_jump_edge->dest;
 105
 106   if (!can_fallthru (jump_block, cbranch_dest_block))
 107     return false;
 108
 109   /* Invert the conditional branch.  */
 110   if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
 111     return false;
 112
 113   if (rtl_dump_file)
 114     fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
 115              INSN_UID (cbranch_insn), INSN_UID (jump_block->end));
 116
 117   /* Success.  Update the CFG to match.  Note that after this point
 118      the edge variable names appear backwards; the redirection is done
 119      this way to preserve edge profile data.  */
 120   cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
 121                                                 cbranch_dest_block);
 122   cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
 123                                                     jump_dest_block);
 124   cbranch_jump_edge->flags |= EDGE_FALLTHRU;
 125   cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
 126
 127   /* Delete the block with the unconditional jump, and clean up the mess.  */
 128   flow_delete_block (jump_block);
 129   tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block);
 130
 131   return true;
 132 }
 133 \f
 134 /* Attempt to forward edges leaving basic block B.
 135    Return true if sucessful.  */
 136
 137 static bool
 138 try_forward_edges (mode, b)
 139      basic_block b;
 140      int mode;
 141 {
 142   bool changed = false;
 143   edge e, next;
 144
 145   for (e = b->succ; e ; e = next)
 146     {
 147       basic_block target, first;
 148       int counter;
 149
 150       next = e->succ_next;
 151
 152       /* Skip complex edges because we don't know how to update them.
 153
 154          Still handle fallthru edges, as we can suceed to forward fallthru
 155          edge to the same place as the branch edge of conditional branch
 156          and turn conditional branch to an unconditonal branch.  */
 157       if (e->flags & EDGE_COMPLEX)
 158         continue;
 159
 160       target = first = e->dest;
 161       counter = 0;
 162
 163       /* Look for the real destination of the jump.
 164          Avoid inifinite loop in the infinite empty loop by counting
 165          up to n_basic_blocks.  */
 166       while (forwarder_block_p (target)
 167              && target->succ->dest != EXIT_BLOCK_PTR
 168              && counter < n_basic_blocks)
 169         {
 170           /* Bypass trivial infinite loops.  */
 171           if (target == target->succ->dest)
 172             counter = n_basic_blocks;
 173
 174           /* Avoid killing of loop pre-headers, as it is the place loop
 175              optimizer wants to hoist code to.
 176
 177              For fallthru forwarders, the LOOP_BEG note must appear between
 178              the header of block and CODE_LABEL of the loop, for non forwarders
 179              it must appear before the JUMP_INSN.  */
 180           if (mode & CLEANUP_PRE_LOOP)
 181             {
 182               rtx insn = (target->succ->flags & EDGE_FALLTHRU
 183                           ? target->head : prev_nonnote_insn (target->end));
 184
 185               if (GET_CODE (insn) != NOTE)
 186                 insn = NEXT_INSN (insn);
 187
 188               for (;insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
 189                    insn = NEXT_INSN (insn))
 190                 if (GET_CODE (insn) == NOTE
 191                     && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
 192                   break;
 193
 194               if (GET_CODE (insn) == NOTE)
 195                 break;
 196             }
 197           target = target->succ->dest, counter++;
 198         }
 199
 200       if (counter >= n_basic_blocks)
 201         {
 202           if (rtl_dump_file)
 203             fprintf (rtl_dump_file, "Infinite loop in BB %i.\n",
 204                      target->index);
 205         }
 206       else if (target == first)
 207         ; /* We didn't do anything.  */
 208       else
 209         {
 210           /* Save the values now, as the edge may get removed.  */
 211           gcov_type edge_count = e->count;
 212           int edge_probability = e->probability;
 213
 214           if (redirect_edge_and_branch (e, target))
 215             {
 216               /* We successfully forwarded the edge.  Now update profile
 217                  data: for each edge we traversed in the chain, remove
 218                  the original edge's execution count.  */
 219               int edge_frequency = ((edge_probability * b->frequency
 220                                      + REG_BR_PROB_BASE / 2)
 221                                     / REG_BR_PROB_BASE);
 222
 223               do
 224                 {
 225                   first->count -= edge_count;
 226                   first->succ->count -= edge_count;
 227                   first->frequency -= edge_frequency;
 228                   first = first->succ->dest;
 229                 }
 230               while (first != target);
 231
 232               changed = true;
 233             }
 234           else
 235             {
 236               if (rtl_dump_file)
 237                 fprintf (rtl_dump_file, "Forwarding edge %i->%i to %i failed.\n",
 238                          b->index, e->dest->index, target->index);
 239             }
 240         }
 241     }
 242
 243   return changed;
 244 }
 245 \f
 246 /* Return true if LABEL is used for tail recursion.  */
 247
 248 static bool
 249 tail_recursion_label_p (label)
 250      rtx label;
 251 {
 252   rtx x;
 253
 254   for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
 255     if (label == XEXP (x, 0))
 256       return true;
 257
 258   return false;
 259 }
 260
 261 /* Blocks A and B are to be merged into a single block.  A has no incoming
 262    fallthru edge, so it can be moved before B without adding or modifying
 263    any jumps (aside from the jump from A to B).  */
 264
 265 static void
 266 merge_blocks_move_predecessor_nojumps (a, b)
 267      basic_block a, b;
 268 {
 269   rtx barrier;
 270   int index;
 271
 272   barrier = next_nonnote_insn (a->end);
 273   if (GET_CODE (barrier) != BARRIER)
 274     abort ();
 275   delete_insn (barrier);
 276
 277   /* Move block and loop notes out of the chain so that we do not
 278      disturb their order.
 279
 280      ??? A better solution would be to squeeze out all the non-nested notes
 281      and adjust the block trees appropriately.   Even better would be to have
 282      a tighter connection between block trees and rtl so that this is not
 283      necessary.  */
 284   squeeze_notes (&a->head, &a->end);
 285
 286   /* Scramble the insn chain.  */
 287   if (a->end != PREV_INSN (b->head))
 288     reorder_insns_nobb (a->head, a->end, PREV_INSN (b->head));
 289
 290   if (rtl_dump_file)
 291     {
 292       fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
 293                a->index, b->index);
 294     }
 295
 296   /* Swap the records for the two blocks around.  Although we are deleting B,
 297      A is now where B was and we want to compact the BB array from where
 298      A used to be.  */
 299   BASIC_BLOCK (a->index) = b;
 300   BASIC_BLOCK (b->index) = a;
 301   index = a->index;
 302   a->index = b->index;
 303   b->index = index;
 304
 305   /* Now blocks A and B are contiguous.  Merge them.  */
 306   merge_blocks_nomove (a, b);
 307 }
 308
 309 /* Blocks A and B are to be merged into a single block.  B has no outgoing
 310    fallthru edge, so it can be moved after A without adding or modifying
 311    any jumps (aside from the jump from A to B).  */
 312
 313 static void
 314 merge_blocks_move_successor_nojumps (a, b)
 315      basic_block a, b;
 316 {
 317   rtx barrier, real_b_end;
 318
 319   real_b_end = b->end;
 320   barrier = NEXT_INSN (b->end);
 321
 322   /* Recognize a jump table following block B.  */
 323   if (barrier
 324       && GET_CODE (barrier) == CODE_LABEL
 325       && NEXT_INSN (barrier)
 326       && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
 327       && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
 328           || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
 329     {
 330       /* Temporarily add the table jump insn to b, so that it will also
 331          be moved to the correct location.  */
 332       b->end = NEXT_INSN (barrier);
 333       barrier = NEXT_INSN (b->end);
 334     }
 335
 336   /* There had better have been a barrier there.  Delete it.  */
 337   if (barrier && GET_CODE (barrier) == BARRIER)
 338     delete_insn (barrier);
 339
 340   /* Move block and loop notes out of the chain so that we do not
 341      disturb their order.
 342
 343      ??? A better solution would be to squeeze out all the non-nested notes
 344      and adjust the block trees appropriately.   Even better would be to have
 345      a tighter connection between block trees and rtl so that this is not
 346      necessary.  */
 347   squeeze_notes (&b->head, &b->end);
 348
 349   /* Scramble the insn chain.  */
 350   reorder_insns_nobb (b->head, b->end, a->end);
 351
 352   /* Restore the real end of b.  */
 353   b->end = real_b_end;
 354
 355   /* Now blocks A and B are contiguous.  Merge them.  */
 356   merge_blocks_nomove (a, b);
 357
 358   if (rtl_dump_file)
 359     {
 360       fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
 361                b->index, a->index);
 362     }
 363 }
 364
 365 /* Attempt to merge basic blocks that are potentially non-adjacent.
 366    Return true iff the attempt succeeded.  */
 367
 368 static bool
 369 merge_blocks (e, b, c, mode)
 370      edge e;
 371      basic_block b, c;
 372      int mode;
 373 {
 374   /* If C has a tail recursion label, do not merge.  There is no
 375      edge recorded from the call_placeholder back to this label, as
 376      that would make optimize_sibling_and_tail_recursive_calls more
 377      complex for no gain.  */
 378   if ((mode & CLEANUP_PRE_SIBCALL)
 379       && GET_CODE (c->head) == CODE_LABEL
 380       && tail_recursion_label_p (c->head))
 381     return false;
 382
 383   /* If B has a fallthru edge to C, no need to move anything.  */
 384   if (e->flags & EDGE_FALLTHRU)
 385     {
 386       merge_blocks_nomove (b, c);
 387
 388       if (rtl_dump_file)
 389         {
 390           fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
 391                    b->index, c->index);
 392         }
 393
 394       return true;
 395     }
 396   /* Otherwise we will need to move code around.  Do that only if expensive
 397      transformations are allowed.  */
 398   else if (mode & CLEANUP_EXPENSIVE)
 399     {
 400       edge tmp_edge, b_fallthru_edge;
 401       bool c_has_outgoing_fallthru;
 402       bool b_has_incoming_fallthru;
 403
 404       /* Avoid overactive code motion, as the forwarder blocks should be
 405          eliminated by edge redirection instead.  One exception might have
 406          been if B is a forwarder block and C has no fallthru edge, but
 407          that should be cleaned up by bb-reorder instead.  */
 408       if (forwarder_block_p (b) || forwarder_block_p (c))
 409         return false;
 410
 411       /* We must make sure to not munge nesting of lexical blocks,
 412          and loop notes.  This is done by squeezing out all the notes
 413          and leaving them there to lie.  Not ideal, but functional.  */
 414
 415       for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
 416         if (tmp_edge->flags & EDGE_FALLTHRU)
 417           break;
 418       c_has_outgoing_fallthru = (tmp_edge != NULL);
 419
 420       for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
 421         if (tmp_edge->flags & EDGE_FALLTHRU)
 422           break;
 423       b_has_incoming_fallthru = (tmp_edge != NULL);
 424       b_fallthru_edge = tmp_edge;
 425
 426       /* Otherwise, we're going to try to move C after B.  If C does
 427          not have an outgoing fallthru, then it can be moved
 428          immediately after B without introducing or modifying jumps.  */
 429       if (! c_has_outgoing_fallthru)
 430         {
 431           merge_blocks_move_successor_nojumps (b, c);
 432           return true;
 433         }
 434
 435       /* If B does not have an incoming fallthru, then it can be moved
 436          immediately before C without introducing or modifying jumps.
 437          C cannot be the first block, so we do not have to worry about
 438          accessing a non-existent block.  */
 439
 440       if (b_has_incoming_fallthru)
 441         {
 442           if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
 443             return false;
 444           force_nonfallthru (b_fallthru_edge);
 445         }
 446       merge_blocks_move_predecessor_nojumps (b, c);
 447       return true;
 448     }
 449   return false;
 450 }
 451 \f
 452 /* Look through the insns at the end of BB1 and BB2 and find the longest
 453    sequence that are equivalent.  Store the first insns for that sequence
 454    in *F1 and *F2 and return the sequence length.
 455
 456    To simplify callers of this function, if the blocks match exactly,
 457    store the head of the blocks in *F1 and *F2.  */
 458
 459 static int
 460 flow_find_cross_jump (mode, bb1, bb2, f1, f2)
 461      int mode ATTRIBUTE_UNUSED;
 462      basic_block bb1, bb2;
 463      rtx *f1, *f2;
 464 {
 465   rtx i1, i2, p1, p2, last1, last2, afterlast1, afterlast2;
 466   int ninsns = 0;
 467
 468   /* Skip simple jumps at the end of the blocks.  Complex jumps still
 469      need to be compared for equivalence, which we'll do below.  */
 470
 471   i1 = bb1->end;
 472   if (onlyjump_p (i1)
 473       || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
 474     i1 = PREV_INSN (i1);
 475   i2 = bb2->end;
 476   if (onlyjump_p (i2)
 477       || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
 478     i2 = PREV_INSN (i2);
 479
 480   last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
 481   while (true)
 482     {
 483       /* Ignore notes.  */
 484       while ((GET_CODE (i1) == NOTE && i1 != bb1->head))
 485         i1 = PREV_INSN (i1);
 486       while ((GET_CODE (i2) == NOTE && i2 != bb2->head))
 487         i2 = PREV_INSN (i2);
 488
 489       if (i1 == bb1->head || i2 == bb2->head)
 490         break;
 491
 492       /* Verify that I1 and I2 are equivalent.  */
 493
 494       if (GET_CODE (i1) != GET_CODE (i2))
 495         break;
 496
 497       p1 = PATTERN (i1);
 498       p2 = PATTERN (i2);
 499
 500       /* If this is a CALL_INSN, compare register usage information.
 501          If we don't check this on stack register machines, the two
 502          CALL_INSNs might be merged leaving reg-stack.c with mismatching
 503          numbers of stack registers in the same basic block.
 504          If we don't check this on machines with delay slots, a delay slot may
 505          be filled that clobbers a parameter expected by the subroutine.
 506
 507          ??? We take the simple route for now and assume that if they're
 508          equal, they were constructed identically.  */
 509
 510       if (GET_CODE (i1) == CALL_INSN
 511           && ! rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
 512                             CALL_INSN_FUNCTION_USAGE (i2)))
 513         break;
 514
 515 #ifdef STACK_REGS
 516       /* If cross_jump_death_matters is not 0, the insn's mode
 517          indicates whether or not the insn contains any stack-like
 518          regs.  */
 519
 520       if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
 521         {
 522           /* If register stack conversion has already been done, then
 523              death notes must also be compared before it is certain that
 524              the two instruction streams match.  */
 525
 526           rtx note;
 527           HARD_REG_SET i1_regset, i2_regset;
 528
 529           CLEAR_HARD_REG_SET (i1_regset);
 530           CLEAR_HARD_REG_SET (i2_regset);
 531
 532           for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
 533             if (REG_NOTE_KIND (note) == REG_DEAD
 534                 && STACK_REG_P (XEXP (note, 0)))
 535               SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
 536
 537           for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
 538             if (REG_NOTE_KIND (note) == REG_DEAD
 539                 && STACK_REG_P (XEXP (note, 0)))
 540               SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
 541
 542           GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
 543
 544           break;
 545
 546         done:
 547           ;
 548         }
 549 #endif
 550
 551       if (GET_CODE (p1) != GET_CODE (p2))
 552         break;
 553
 554       if (! rtx_renumbered_equal_p (p1, p2))
 555         {
 556           /* The following code helps take care of G++ cleanups.  */
 557           rtx equiv1 = find_reg_equal_equiv_note (i1);
 558           rtx equiv2 = find_reg_equal_equiv_note (i2);
 559
 560           if (equiv1 && equiv2
 561               /* If the equivalences are not to a constant, they may
 562                  reference pseudos that no longer exist, so we can't
 563                  use them.  */
 564               && CONSTANT_P (XEXP (equiv1, 0))
 565               && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
 566             {
 567               rtx s1 = single_set (i1);
 568               rtx s2 = single_set (i2);
 569               if (s1 != 0 && s2 != 0
 570                   && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
 571                 {
 572                   validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
 573                   validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
 574                   if (! rtx_renumbered_equal_p (p1, p2))
 575                     cancel_changes (0);
 576                   else if (apply_change_group ())
 577                     goto win;
 578                 }
 579             }
 580           break;
 581         }
 582
 583     win:
 584       /* Don't begin a cross-jump with a USE or CLOBBER insn.  */
 585       if (GET_CODE (p1) != USE && GET_CODE (p1) != CLOBBER)
 586         {
 587           /* If the merged insns have different REG_EQUAL notes, then
 588              remove them.  */
 589           rtx equiv1 = find_reg_equal_equiv_note (i1);
 590           rtx equiv2 = find_reg_equal_equiv_note (i2);
 591
 592           if (equiv1 && !equiv2)
 593             remove_note (i1, equiv1);
 594           else if (!equiv1 && equiv2)
 595             remove_note (i2, equiv2);
 596           else if (equiv1 && equiv2
 597                    && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
 598             {
 599               remove_note (i1, equiv1);
 600               remove_note (i2, equiv2);
 601             }
 602
 603           afterlast1 = last1, afterlast2 = last2;
 604           last1 = i1, last2 = i2;
 605           ninsns++;
 606         }
 607       i1 = PREV_INSN (i1);
 608       i2 = PREV_INSN (i2);
 609     }
 610
 611 #ifdef HAVE_cc0
 612   if (ninsns)
 613     {
 614       /* Don't allow the insn after a compare to be shared by
 615          cross-jumping unless the compare is also shared.  */
 616       if (reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
 617         last1 = afterlast1, last2 = afterlast2, ninsns--;
 618     }
 619 #endif
 620
 621   /* Include preceeding notes and labels in the cross-jump.  One,
 622      this may bring us to the head of the blocks as requested above.
 623      Two, it keeps line number notes as matched as may be.  */
 624   if (ninsns)
 625     {
 626       while (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == NOTE)
 627         last1 = PREV_INSN (last1);
 628       if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
 629         last1 = PREV_INSN (last1);
 630       while (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == NOTE)
 631         last2 = PREV_INSN (last2);
 632       if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
 633         last2 = PREV_INSN (last2);
 634
 635       *f1 = last1;
 636       *f2 = last2;
 637     }
 638
 639   return ninsns;
 640 }
 641
 642 /* Return true iff outgoing edges of BB1 and BB2 match, together with
 643    the branch instruction.  This means that if we commonize the control
 644    flow before end of the basic block, the semantic remains unchanged.
 645
 646    We may assume that there exists one edge with a common destination.  */
 647
 648 static bool
 649 outgoing_edges_match (bb1, bb2)
 650      basic_block bb1;
 651      basic_block bb2;
 652 {
 653   /* If BB1 has only one successor, we must be looking at an unconditional
 654      jump.  Which, by the assumption above, means that we only need to check
 655      that BB2 has one successor.  */
 656   if (bb1->succ && !bb1->succ->succ_next)
 657     return (bb2->succ && !bb2->succ->succ_next);
 658
 659   /* Match conditional jumps - this may get tricky when fallthru and branch
 660      edges are crossed.  */
 661   if (bb1->succ
 662       && bb1->succ->succ_next
 663       && !bb1->succ->succ_next->succ_next
 664       && any_condjump_p (bb1->end))
 665     {
 666       edge b1, f1, b2, f2;
 667       bool reverse, match;
 668       rtx set1, set2, cond1, cond2;
 669       enum rtx_code code1, code2;
 670
 671       if (!bb2->succ
 672           || !bb2->succ->succ_next
 673           || bb1->succ->succ_next->succ_next
 674           || !any_condjump_p (bb2->end))
 675         return false;
 676
 677       b1 = BRANCH_EDGE (bb1);
 678       b2 = BRANCH_EDGE (bb2);
 679       f1 = FALLTHRU_EDGE (bb1);
 680       f2 = FALLTHRU_EDGE (bb2);
 681
 682       /* Get around possible forwarders on fallthru edges.  Other cases
 683          should be optimized out already.  */
 684       if (forwarder_block_p (f1->dest))
 685         f1 = f1->dest->succ;
 686       if (forwarder_block_p (f2->dest))
 687         f2 = f2->dest->succ;
 688
 689       /* To simplify use of this function, return false if there are
 690          unneeded forwarder blocks.  These will get eliminated later
 691          during cleanup_cfg.  */
 692       if (forwarder_block_p (f1->dest)
 693           || forwarder_block_p (f2->dest)
 694           || forwarder_block_p (b1->dest)
 695           || forwarder_block_p (b2->dest))
 696         return false;
 697
 698       if (f1->dest == f2->dest && b1->dest == b2->dest)
 699         reverse = false;
 700       else if (f1->dest == b2->dest && b1->dest == f2->dest)
 701         reverse = true;
 702       else
 703         return false;
 704
 705       set1 = pc_set (bb1->end);
 706       set2 = pc_set (bb2->end);
 707       if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
 708           != (XEXP (SET_SRC (set2), 1) == pc_rtx))
 709         reverse = !reverse;
 710
 711       cond1 = XEXP (SET_SRC (set1), 0);
 712       cond2 = XEXP (SET_SRC (set2), 0);
 713       code1 = GET_CODE (cond1);
 714       if (reverse)
 715         code2 = reversed_comparison_code (cond2, bb2->end);
 716       else
 717         code2 = GET_CODE (cond2);
 718       if (code2 == UNKNOWN)
 719         return false;
 720
 721       /* Verify codes and operands match.  */
 722       match = ((code1 == code2
 723                 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
 724                 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
 725                || (code1 == swap_condition (code2)
 726                    && rtx_renumbered_equal_p (XEXP (cond1, 1),
 727                                               XEXP (cond2, 0))
 728                    && rtx_renumbered_equal_p (XEXP (cond1, 0),
 729                                               XEXP (cond2, 1))));
 730
 731       /* If we return true, we will join the blocks.  Which means that
 732          we will only have one branch prediction bit to work with.  Thus
 733          we require the existing branches to have probabilities that are
 734          roughly similar.  */
 735       /* ??? We should use bb->frequency to allow merging in infrequently
 736          executed blocks, but at the moment it is not available when
 737          cleanup_cfg is run.  */
 738       if (match && !optimize_size)
 739         {
 740           rtx note1, note2;
 741           int prob1, prob2;
 742           note1 = find_reg_note (bb1->end, REG_BR_PROB, 0);
 743           note2 = find_reg_note (bb2->end, REG_BR_PROB, 0);
 744
 745           if (note1 && note2)
 746             {
 747               prob1 = INTVAL (XEXP (note1, 0));
 748               prob2 = INTVAL (XEXP (note2, 0));
 749               if (reverse)
 750                 prob2 = REG_BR_PROB_BASE - prob2;
 751
 752               /* Fail if the difference in probabilities is
 753                  greater than 5%.  */
 754               if (abs (prob1 - prob2) > REG_BR_PROB_BASE / 20)
 755                 return false;
 756             }
 757           else if (note1 || note2)
 758             return false;
 759         }
 760
 761       if (rtl_dump_file && match)
 762         fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
 763                  bb1->index, bb2->index);
 764
 765       return match;
 766     }
 767
 768   /* ??? We can handle computed jumps too.  This may be important for
 769      inlined functions containing switch statements.  Also jumps w/o
 770      fallthru edges can be handled by simply matching whole insn.  */
 771   return false;
 772 }
 773
 774 /* E1 and E2 are edges with the same destination block.  Search their
 775    predecessors for common code.  If found, redirect control flow from
 776    (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC.  */
 777
 778 static bool
 779 try_crossjump_to_edge (mode, e1, e2)
 780      int mode;
 781      edge e1, e2;
 782 {
 783   int nmatch;
 784   basic_block src1 = e1->src, src2 = e2->src;
 785   basic_block redirect_to;
 786   rtx newpos1, newpos2;
 787   edge s;
 788   rtx last;
 789   rtx label;
 790   rtx note;
 791
 792   /* Search backward through forwarder blocks.  We don't need to worry
 793      about multiple entry or chained forwarders, as they will be optimized
 794      away.  We do this to look past the unconditional jump following a
 795      conditional jump that is required due to the current CFG shape.  */
 796   if (src1->pred
 797       && !src1->pred->pred_next
 798       && forwarder_block_p (src1))
 799     {
 800       e1 = src1->pred;
 801       src1 = e1->src;
 802     }
 803   if (src2->pred
 804       && !src2->pred->pred_next
 805       && forwarder_block_p (src2))
 806     {
 807       e2 = src2->pred;
 808       src2 = e2->src;
 809     }
 810
 811   /* Nothing to do if we reach ENTRY, or a common source block.  */
 812   if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
 813     return false;
 814   if (src1 == src2)
 815     return false;
 816
 817   /* Seeing more than 1 forwarder blocks would confuse us later...  */
 818   if (forwarder_block_p (e1->dest)
 819       && forwarder_block_p (e1->dest->succ->dest))
 820     return false;
 821   if (forwarder_block_p (e2->dest)
 822       && forwarder_block_p (e2->dest->succ->dest))
 823     return false;
 824
 825   /* Likewise with dead code (possibly newly created by the other optimizations
 826      of cfg_cleanup).  */
 827   if (!src1->pred || !src2->pred)
 828     return false;
 829
 830   /* Likewise with complex edges.
 831      ??? We should be able to handle most complex edges later with some
 832      care.  */
 833   if (e1->flags & EDGE_COMPLEX)
 834     return false;
 835
 836   /* Look for the common insn sequence, part the first ...  */
 837   if (!outgoing_edges_match (src1, src2))
 838     return false;
 839
 840   /* ... and part the second.  */
 841   nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
 842   if (!nmatch)
 843     return false;
 844
 845   /* Avoid splitting if possible.  */
 846   if (newpos2 == src2->head)
 847     redirect_to = src2;
 848   else
 849     {
 850       if (rtl_dump_file)
 851         fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
 852                  src2->index, nmatch);
 853       redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
 854     }
 855
 856   if (rtl_dump_file)
 857     fprintf (rtl_dump_file,
 858              "Cross jumping from bb %i to bb %i; %i common insns\n",
 859              src1->index, src2->index, nmatch);
 860
 861   redirect_to->count += src1->count;
 862   redirect_to->frequency += src1->frequency;
 863
 864   /* Recompute the frequencies and counts of outgoing edges.  */
 865   for (s = redirect_to->succ; s; s = s->succ_next)
 866     {
 867       edge s2;
 868       basic_block d = s->dest;
 869
 870       if (forwarder_block_p (d))
 871         d = d->succ->dest;
 872       for (s2 = src1->succ; ; s2 = s2->succ_next)
 873         {
 874           basic_block d2 = s2->dest;
 875           if (forwarder_block_p (d2))
 876             d2 = d2->succ->dest;
 877           if (d == d2)
 878             break;
 879         }
 880       s->count += s2->count;
 881
 882       /* Take care to update possible forwarder blocks.  We verified
 883          that there is no more than one in the chain, so we can't run
 884          into infinite loop.  */
 885       if (forwarder_block_p (s->dest))
 886         {
 887           s->dest->succ->count += s2->count;
 888           s->dest->count += s2->count;
 889           s->dest->frequency += EDGE_FREQUENCY (s);
 890         }
 891       if (forwarder_block_p (s2->dest))
 892         {
 893           s2->dest->succ->count -= s2->count;
 894           s2->dest->count -= s2->count;
 895           s2->dest->frequency -= EDGE_FREQUENCY (s);
 896         }
 897       if (!redirect_to->frequency && !src1->frequency)
 898         s->probability = (s->probability + s2->probability) / 2;
 899       else
 900         s->probability =
 901           ((s->probability * redirect_to->frequency +
 902             s2->probability * src1->frequency)
 903            / (redirect_to->frequency + src1->frequency));
 904     }
 905
 906   note = find_reg_note (redirect_to->end, REG_BR_PROB, 0);
 907   if (note)
 908     XEXP (note, 0) = GEN_INT (BRANCH_EDGE (redirect_to)->probability);
 909
 910   /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1.  */
 911
 912   /* Skip possible basic block header.  */
 913   if (GET_CODE (newpos1) == CODE_LABEL)
 914     newpos1 = NEXT_INSN (newpos1);
 915   if (GET_CODE (newpos1) == NOTE)
 916     newpos1 = NEXT_INSN (newpos1);
 917   last = src1->end;
 918
 919   /* Emit the jump insn.  */
 920   label = block_label (redirect_to);
 921   emit_jump_insn_after (gen_jump (label), src1->end);
 922   JUMP_LABEL (src1->end) = label;
 923   LABEL_NUSES (label)++;
 924
 925   /* Delete the now unreachable instructions.  */
 926   delete_insn_chain (newpos1, last);
 927
 928   /* Make sure there is a barrier after the new jump.  */
 929   last = next_nonnote_insn (src1->end);
 930   if (!last || GET_CODE (last) != BARRIER)
 931     emit_barrier_after (src1->end);
 932
 933   /* Update CFG.  */
 934   while (src1->succ)
 935     remove_edge (src1->succ);
 936   make_single_succ_edge (src1, redirect_to, 0);
 937
 938   return true;
 939 }
 940
 941 /* Search the predecessors of BB for common insn sequences.  When found,
 942    share code between them by redirecting control flow.  Return true if
 943    any changes made.  */
 944
 945 static bool
 946 try_crossjump_bb (mode, bb)
 947      int mode;
 948      basic_block bb;
 949 {
 950   edge e, e2, nexte2, nexte, fallthru;
 951   bool changed;
 952
 953   /* Nothing to do if there is not at least two incomming edges.  */
 954   if (!bb->pred || !bb->pred->pred_next)
 955     return false;
 956
 957   /* It is always cheapest to redirect a block that ends in a branch to
 958      a block that falls through into BB, as that adds no branches to the
 959      program.  We'll try that combination first.  */
 960   for (fallthru = bb->pred; fallthru; fallthru = fallthru->pred_next)
 961     if (fallthru->flags & EDGE_FALLTHRU)
 962       break;
 963
 964   changed = false;
 965   for (e = bb->pred; e; e = nexte)
 966     {
 967       nexte = e->pred_next;
 968
 969       /* Elide complex edges now, as neither try_crossjump_to_edge
 970          nor outgoing_edges_match can handle them.  */
 971       if (e->flags & EDGE_COMPLEX)
 972         continue;
 973
 974       /* As noted above, first try with the fallthru predecessor.  */
 975       if (fallthru)
 976         {
 977           /* Don't combine the fallthru edge into anything else.
 978              If there is a match, we'll do it the other way around.  */
 979           if (e == fallthru)
 980             continue;
 981
 982           if (try_crossjump_to_edge (mode, e, fallthru))
 983             {
 984               changed = true;
 985               nexte = bb->pred;
 986               continue;
 987             }
 988         }
 989
 990       /* Non-obvious work limiting check: Recognize that we're going
 991          to call try_crossjump_bb on every basic block.  So if we have
 992          two blocks with lots of outgoing edges (a switch) and they
 993          share lots of common destinations, then we would do the
 994          cross-jump check once for each common destination.
 995
 996          Now, if the blocks actually are cross-jump candidates, then
 997          all of their destinations will be shared.  Which means that
 998          we only need check them for cross-jump candidacy once.  We
 999          can eliminate redundant checks of crossjump(A,B) by arbitrarily
1000          choosing to do the check from the block for which the edge
1001          in question is the first successor of A.  */
1002       if (e->src->succ != e)
1003         continue;
1004
1005       for (e2 = bb->pred; e2; e2 = nexte2)
1006         {
1007           nexte2 = e2->pred_next;
1008
1009           if (e2 == e)
1010             continue;
1011
1012           /* We've already checked the fallthru edge above.  */
1013           if (e2 == fallthru)
1014             continue;
1015
1016           /* Again, neither try_crossjump_to_edge nor outgoing_edges_match
1017              can handle complex edges.  */
1018           if (e2->flags & EDGE_COMPLEX)
1019             continue;
1020
1021           /* The "first successor" check above only prevents multiple
1022              checks of crossjump(A,B).  In order to prevent redundant
1023              checks of crossjump(B,A), require that A be the block
1024              with the lowest index.  */
1025           if (e->src->index > e2->src->index)
1026             continue;
1027
1028           if (try_crossjump_to_edge (mode, e, e2))
1029             {
1030               changed = true;
1031               nexte = bb->pred;
1032               break;
1033             }
1034         }
1035     }
1036
1037   return changed;
1038 }
1039
1040 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1041    instructions etc.  Return nonzero if changes were made.  */
1042
1043 static bool
1044 try_optimize_cfg (mode)
1045      int mode;
1046 {
1047   int i;
1048   bool changed_overall = false;
1049   bool changed;
1050   int iterations = 0;
1051
1052   if (mode & CLEANUP_CROSSJUMP)
1053     add_noreturn_fake_exit_edges ();
1054
1055   /* Attempt to merge blocks as made possible by edge removal.  If a block
1056      has only one successor, and the successor has only one predecessor,
1057      they may be combined.  */
1058
1059   do
1060     {
1061       changed = false;
1062       iterations++;
1063
1064       if (rtl_dump_file)
1065         fprintf (rtl_dump_file, "\n\ntry_optimize_cfg iteration %i\n\n",
1066                  iterations);
1067
1068       for (i = 0; i < n_basic_blocks;)
1069         {
1070           basic_block c, b = BASIC_BLOCK (i);
1071           edge s;
1072           bool changed_here = false;
1073
1074           /* Delete trivially dead basic blocks.  */
1075           while (b->pred == NULL)
1076             {
1077               c = BASIC_BLOCK (b->index - 1);
1078               if (rtl_dump_file)
1079                 fprintf (rtl_dump_file, "Deleting block %i.\n", b->index);
1080               flow_delete_block (b);
1081               changed = true;
1082               b = c;
1083             }
1084
1085           /* Remove code labels no longer used.  Don't do this before
1086              CALL_PLACEHOLDER is removed, as some branches may be hidden
1087              within.  */
1088           if (b->pred->pred_next == NULL
1089               && (b->pred->flags & EDGE_FALLTHRU)
1090               && !(b->pred->flags & EDGE_COMPLEX)
1091               && GET_CODE (b->head) == CODE_LABEL
1092               && (!(mode & CLEANUP_PRE_SIBCALL)
1093                   || !tail_recursion_label_p (b->head))
1094               /* If previous block ends with condjump jumping to next BB,
1095                  we can't delete the label.  */
1096               && (b->pred->src == ENTRY_BLOCK_PTR
1097                   || !reg_mentioned_p (b->head, b->pred->src->end)))
1098             {
1099               rtx label = b->head;
1100               b->head = NEXT_INSN (b->head);
1101               delete_insn_chain (label, label);
1102               if (rtl_dump_file)
1103                 fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1104                          b->index);
1105             }
1106
1107           /* If we fall through an empty block, we can remove it.  */
1108           if (b->pred->pred_next == NULL
1109               && (b->pred->flags & EDGE_FALLTHRU)
1110               && GET_CODE (b->head) != CODE_LABEL
1111               && forwarder_block_p (b)
1112               /* Note that forwarder_block_p true ensures that there
1113                  is a successor for this block.  */
1114               && (b->succ->flags & EDGE_FALLTHRU)
1115               && n_basic_blocks > 1)
1116             {
1117               if (rtl_dump_file)
1118                 fprintf (rtl_dump_file, "Deleting fallthru block %i.\n",
1119                          b->index);
1120               c = BASIC_BLOCK (b->index ? b->index - 1 : 1);
1121               redirect_edge_succ_nodup (b->pred, b->succ->dest);
1122               flow_delete_block (b);
1123               changed = true;
1124               b = c;
1125             }
1126
1127           /* Merge blocks.  Loop because chains of blocks might be
1128              combineable.  */
1129           while ((s = b->succ) != NULL
1130                  && s->succ_next == NULL
1131                  && !(s->flags & EDGE_COMPLEX)
1132                  && (c = s->dest) != EXIT_BLOCK_PTR
1133                  && c->pred->pred_next == NULL
1134                  /* If the jump insn has side effects,
1135                     we can't kill the edge.  */
1136                  && (GET_CODE (b->end) != JUMP_INSN
1137                      || onlyjump_p (b->end))
1138                  && merge_blocks (s, b, c, mode))
1139             changed_here = true;
1140
1141           /* Simplify branch over branch.  */
1142           if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b))
1143             changed_here = true;
1144
1145           /* If B has a single outgoing edge, but uses a non-trivial jump
1146              instruction without side-effects, we can either delete the
1147              jump entirely, or replace it with a simple unconditional jump.
1148              Use redirect_edge_and_branch to do the dirty work.  */
1149           if (b->succ
1150               && ! b->succ->succ_next
1151               && b->succ->dest != EXIT_BLOCK_PTR
1152               && onlyjump_p (b->end)
1153               && redirect_edge_and_branch (b->succ, b->succ->dest))
1154             changed_here = true;
1155
1156           /* Simplify branch to branch.  */
1157           if (try_forward_edges (mode, b))
1158             changed_here = true;
1159
1160           /* Look for shared code between blocks.  */
1161           if ((mode & CLEANUP_CROSSJUMP)
1162               && try_crossjump_bb (mode, b))
1163             changed_here = true;
1164
1165           /* Don't get confused by the index shift caused by deleting
1166              blocks.  */
1167           if (!changed_here)
1168             i = b->index + 1;
1169           else
1170             changed = true;
1171         }
1172
1173       if ((mode & CLEANUP_CROSSJUMP)
1174           && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1175         changed = true;
1176
1177 #ifdef ENABLE_CHECKING
1178       if (changed)
1179         verify_flow_info ();
1180 #endif
1181
1182       changed_overall |= changed;
1183     }
1184   while (changed);
1185
1186   if (mode & CLEANUP_CROSSJUMP)
1187     remove_fake_edges ();
1188
1189   return changed_overall;
1190 }
1191 \f
1192 /* Delete all unreachable basic blocks.  */
1193
1194 static bool
1195 delete_unreachable_blocks ()
1196 {
1197   int i;
1198   bool changed = false;
1199
1200   find_unreachable_blocks ();
1201
1202   /* Delete all unreachable basic blocks.  Count down so that we
1203      don't interfere with the block renumbering that happens in
1204      flow_delete_block.  */
1205
1206   for (i = n_basic_blocks - 1; i >= 0; --i)
1207     {
1208       basic_block b = BASIC_BLOCK (i);
1209
1210       if (!(b->flags & BB_REACHABLE))
1211         flow_delete_block (b), changed = true;
1212     }
1213
1214   if (changed)
1215     tidy_fallthru_edges ();
1216   return changed;
1217 }
1218 \f
1219 /* Tidy the CFG by deleting unreachable code and whatnot.  */
1220
1221 bool
1222 cleanup_cfg (mode)
1223      int mode;
1224 {
1225   int i;
1226   bool changed = false;
1227
1228   timevar_push (TV_CLEANUP_CFG);
1229   changed = delete_unreachable_blocks ();
1230   if (try_optimize_cfg (mode))
1231     delete_unreachable_blocks (), changed = true;
1232
1233   /* Kill the data we won't maintain.  */
1234   free_EXPR_LIST_list (&label_value_list);
1235   free_EXPR_LIST_list (&tail_recursion_label_list);
1236   timevar_pop (TV_CLEANUP_CFG);
1237
1238   /* Clear bb->aux on all basic blocks.  */
1239   for (i = 0; i < n_basic_blocks; ++i)
1240     BASIC_BLOCK (i)->aux = NULL;
1241   return changed;
1242 }