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