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