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