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