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, 2002, 2003, 2004, 2005, 2006, 2007, 2008
   4    Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 3, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING3.  If not see
  20 <http://www.gnu.org/licenses/>.  */
  21
  22 /* This file contains optimizer of the control flow.  The main entry point is
  23    cleanup_cfg.  Following optimizations are performed:
  24
  25    - Unreachable blocks removal
  26    - Edge forwarding (edge to the forwarder block is forwarded to its
  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 "coretypes.h"
  37 #include "tm.h"
  38 #include "rtl.h"
  39 #include "hard-reg-set.h"
  40 #include "regs.h"
  41 #include "timevar.h"
  42 #include "output.h"
  43 #include "insn-config.h"
  44 #include "flags.h"
  45 #include "recog.h"
  46 #include "toplev.h"
  47 #include "cselib.h"
  48 #include "params.h"
  49 #include "tm_p.h"
  50 #include "target.h"
  51 #include "cfglayout.h"
  52 #include "emit-rtl.h"
  53 #include "tree-pass.h"
  54 #include "cfgloop.h"
  55 #include "expr.h"
  56 #include "df.h"
  57 #include "dce.h"
  58 #include "dbgcnt.h"
  59
  60 #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
  61
  62 /* Set to true when we are running first pass of try_optimize_cfg loop.  */
  63 static bool first_pass;
  64
  65 /* Set to true if crossjumps occured in the latest run of try_optimize_cfg.  */
  66 static bool crossjumps_occured;
  67
  68 static bool try_crossjump_to_edge (int, edge, edge);
  69 static bool try_crossjump_bb (int, basic_block);
  70 static bool outgoing_edges_match (int, basic_block, basic_block);
  71 static int flow_find_cross_jump (int, basic_block, basic_block, rtx *, rtx *);
  72 static bool old_insns_match_p (int, rtx, rtx);
  73
  74 static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
  75 static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
  76 static bool try_optimize_cfg (int);
  77 static bool try_simplify_condjump (basic_block);
  78 static bool try_forward_edges (int, basic_block);
  79 static edge thread_jump (edge, basic_block);
  80 static bool mark_effect (rtx, bitmap);
  81 static void notice_new_block (basic_block);
  82 static void update_forwarder_flag (basic_block);
  83 static int mentions_nonequal_regs (rtx *, void *);
  84 static void merge_memattrs (rtx, rtx);
  85 \f
  86 /* Set flags for newly created block.  */
  87
  88 static void
  89 notice_new_block (basic_block bb)
  90 {
  91   if (!bb)
  92     return;
  93
  94   if (forwarder_block_p (bb))
  95     bb->flags |= BB_FORWARDER_BLOCK;
  96 }
  97
  98 /* Recompute forwarder flag after block has been modified.  */
  99
 100 static void
 101 update_forwarder_flag (basic_block bb)
 102 {
 103   if (forwarder_block_p (bb))
 104     bb->flags |= BB_FORWARDER_BLOCK;
 105   else
 106     bb->flags &= ~BB_FORWARDER_BLOCK;
 107 }
 108 \f
 109 /* Simplify a conditional jump around an unconditional jump.
 110    Return true if something changed.  */
 111
 112 static bool
 113 try_simplify_condjump (basic_block cbranch_block)
 114 {
 115   basic_block jump_block, jump_dest_block, cbranch_dest_block;
 116   edge cbranch_jump_edge, cbranch_fallthru_edge;
 117   rtx cbranch_insn;
 118
 119   /* Verify that there are exactly two successors.  */
 120   if (EDGE_COUNT (cbranch_block->succs) != 2)
 121     return false;
 122
 123   /* Verify that we've got a normal conditional branch at the end
 124      of the block.  */
 125   cbranch_insn = BB_END (cbranch_block);
 126   if (!any_condjump_p (cbranch_insn))
 127     return false;
 128
 129   cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
 130   cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
 131
 132   /* The next block must not have multiple predecessors, must not
 133      be the last block in the function, and must contain just the
 134      unconditional jump.  */
 135   jump_block = cbranch_fallthru_edge->dest;
 136   if (!single_pred_p (jump_block)
 137       || jump_block->next_bb == EXIT_BLOCK_PTR
 138       || !FORWARDER_BLOCK_P (jump_block))
 139     return false;
 140   jump_dest_block = single_succ (jump_block);
 141
 142   /* If we are partitioning hot/cold basic blocks, we don't want to
 143      mess up unconditional or indirect jumps that cross between hot
 144      and cold sections.
 145
 146      Basic block partitioning may result in some jumps that appear to
 147      be optimizable (or blocks that appear to be mergeable), but which really
 148      must be left untouched (they are required to make it safely across
 149      partition boundaries).  See the comments at the top of
 150      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
 151
 152   if (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block)
 153       || (cbranch_jump_edge->flags & EDGE_CROSSING))
 154     return false;
 155
 156   /* The conditional branch must target the block after the
 157      unconditional branch.  */
 158   cbranch_dest_block = cbranch_jump_edge->dest;
 159
 160   if (cbranch_dest_block == EXIT_BLOCK_PTR
 161       || !can_fallthru (jump_block, cbranch_dest_block))
 162     return false;
 163
 164   /* Invert the conditional branch.  */
 165   if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
 166     return false;
 167
 168   if (dump_file)
 169     fprintf (dump_file, "Simplifying condjump %i around jump %i\n",
 170              INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
 171
 172   /* Success.  Update the CFG to match.  Note that after this point
 173      the edge variable names appear backwards; the redirection is done
 174      this way to preserve edge profile data.  */
 175   cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
 176                                                 cbranch_dest_block);
 177   cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
 178                                                     jump_dest_block);
 179   cbranch_jump_edge->flags |= EDGE_FALLTHRU;
 180   cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
 181   update_br_prob_note (cbranch_block);
 182
 183   /* Delete the block with the unconditional jump, and clean up the mess.  */
 184   delete_basic_block (jump_block);
 185   tidy_fallthru_edge (cbranch_jump_edge);
 186   update_forwarder_flag (cbranch_block);
 187
 188   return true;
 189 }
 190 \f
 191 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
 192    on register.  Used by jump threading.  */
 193
 194 static bool
 195 mark_effect (rtx exp, regset nonequal)
 196 {
 197   int regno;
 198   rtx dest;
 199   switch (GET_CODE (exp))
 200     {
 201       /* In case we do clobber the register, mark it as equal, as we know the
 202          value is dead so it don't have to match.  */
 203     case CLOBBER:
 204       if (REG_P (XEXP (exp, 0)))
 205         {
 206           dest = XEXP (exp, 0);
 207           regno = REGNO (dest);
 208           CLEAR_REGNO_REG_SET (nonequal, regno);
 209           if (regno < FIRST_PSEUDO_REGISTER)
 210             {
 211               int n = hard_regno_nregs[regno][GET_MODE (dest)];
 212               while (--n > 0)
 213                 CLEAR_REGNO_REG_SET (nonequal, regno + n);
 214             }
 215         }
 216       return false;
 217
 218     case SET:
 219       if (rtx_equal_for_cselib_p (SET_DEST (exp), SET_SRC (exp)))
 220         return false;
 221       dest = SET_DEST (exp);
 222       if (dest == pc_rtx)
 223         return false;
 224       if (!REG_P (dest))
 225         return true;
 226       regno = REGNO (dest);
 227       SET_REGNO_REG_SET (nonequal, regno);
 228       if (regno < FIRST_PSEUDO_REGISTER)
 229         {
 230           int n = hard_regno_nregs[regno][GET_MODE (dest)];
 231           while (--n > 0)
 232             SET_REGNO_REG_SET (nonequal, regno + n);
 233         }
 234       return false;
 235
 236     default:
 237       return false;
 238     }
 239 }
 240
 241 /* Return nonzero if X is a register set in regset DATA.
 242    Called via for_each_rtx.  */
 243 static int
 244 mentions_nonequal_regs (rtx *x, void *data)
 245 {
 246   regset nonequal = (regset) data;
 247   if (REG_P (*x))
 248     {
 249       int regno;
 250
 251       regno = REGNO (*x);
 252       if (REGNO_REG_SET_P (nonequal, regno))
 253         return 1;
 254       if (regno < FIRST_PSEUDO_REGISTER)
 255         {
 256           int n = hard_regno_nregs[regno][GET_MODE (*x)];
 257           while (--n > 0)
 258             if (REGNO_REG_SET_P (nonequal, regno + n))
 259               return 1;
 260         }
 261     }
 262   return 0;
 263 }
 264 /* Attempt to prove that the basic block B will have no side effects and
 265    always continues in the same edge if reached via E.  Return the edge
 266    if exist, NULL otherwise.  */
 267
 268 static edge
 269 thread_jump (edge e, basic_block b)
 270 {
 271   rtx set1, set2, cond1, cond2, insn;
 272   enum rtx_code code1, code2, reversed_code2;
 273   bool reverse1 = false;
 274   unsigned i;
 275   regset nonequal;
 276   bool failed = false;
 277   reg_set_iterator rsi;
 278
 279   if (b->flags & BB_NONTHREADABLE_BLOCK)
 280     return NULL;
 281
 282   /* At the moment, we do handle only conditional jumps, but later we may
 283      want to extend this code to tablejumps and others.  */
 284   if (EDGE_COUNT (e->src->succs) != 2)
 285     return NULL;
 286   if (EDGE_COUNT (b->succs) != 2)
 287     {
 288       b->flags |= BB_NONTHREADABLE_BLOCK;
 289       return NULL;
 290     }
 291
 292   /* Second branch must end with onlyjump, as we will eliminate the jump.  */
 293   if (!any_condjump_p (BB_END (e->src)))
 294     return NULL;
 295
 296   if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
 297     {
 298       b->flags |= BB_NONTHREADABLE_BLOCK;
 299       return NULL;
 300     }
 301
 302   set1 = pc_set (BB_END (e->src));
 303   set2 = pc_set (BB_END (b));
 304   if (((e->flags & EDGE_FALLTHRU) != 0)
 305       != (XEXP (SET_SRC (set1), 1) == pc_rtx))
 306     reverse1 = true;
 307
 308   cond1 = XEXP (SET_SRC (set1), 0);
 309   cond2 = XEXP (SET_SRC (set2), 0);
 310   if (reverse1)
 311     code1 = reversed_comparison_code (cond1, BB_END (e->src));
 312   else
 313     code1 = GET_CODE (cond1);
 314
 315   code2 = GET_CODE (cond2);
 316   reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
 317
 318   if (!comparison_dominates_p (code1, code2)
 319       && !comparison_dominates_p (code1, reversed_code2))
 320     return NULL;
 321
 322   /* Ensure that the comparison operators are equivalent.
 323      ??? This is far too pessimistic.  We should allow swapped operands,
 324      different CCmodes, or for example comparisons for interval, that
 325      dominate even when operands are not equivalent.  */
 326   if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
 327       || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
 328     return NULL;
 329
 330   /* Short circuit cases where block B contains some side effects, as we can't
 331      safely bypass it.  */
 332   for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
 333        insn = NEXT_INSN (insn))
 334     if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
 335       {
 336         b->flags |= BB_NONTHREADABLE_BLOCK;
 337         return NULL;
 338       }
 339
 340   cselib_init (false);
 341
 342   /* First process all values computed in the source basic block.  */
 343   for (insn = NEXT_INSN (BB_HEAD (e->src));
 344        insn != NEXT_INSN (BB_END (e->src));
 345        insn = NEXT_INSN (insn))
 346     if (INSN_P (insn))
 347       cselib_process_insn (insn);
 348
 349   nonequal = BITMAP_ALLOC (NULL);
 350   CLEAR_REG_SET (nonequal);
 351
 352   /* Now assume that we've continued by the edge E to B and continue
 353      processing as if it were same basic block.
 354      Our goal is to prove that whole block is an NOOP.  */
 355
 356   for (insn = NEXT_INSN (BB_HEAD (b));
 357        insn != NEXT_INSN (BB_END (b)) && !failed;
 358        insn = NEXT_INSN (insn))
 359     {
 360       if (INSN_P (insn))
 361         {
 362           rtx pat = PATTERN (insn);
 363
 364           if (GET_CODE (pat) == PARALLEL)
 365             {
 366               for (i = 0; i < (unsigned)XVECLEN (pat, 0); i++)
 367                 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
 368             }
 369           else
 370             failed |= mark_effect (pat, nonequal);
 371         }
 372
 373       cselib_process_insn (insn);
 374     }
 375
 376   /* Later we should clear nonequal of dead registers.  So far we don't
 377      have life information in cfg_cleanup.  */
 378   if (failed)
 379     {
 380       b->flags |= BB_NONTHREADABLE_BLOCK;
 381       goto failed_exit;
 382     }
 383
 384   /* cond2 must not mention any register that is not equal to the
 385      former block.  */
 386   if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
 387     goto failed_exit;
 388
 389   EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, rsi)
 390     goto failed_exit;
 391
 392   BITMAP_FREE (nonequal);
 393   cselib_finish ();
 394   if ((comparison_dominates_p (code1, code2) != 0)
 395       != (XEXP (SET_SRC (set2), 1) == pc_rtx))
 396     return BRANCH_EDGE (b);
 397   else
 398     return FALLTHRU_EDGE (b);
 399
 400 failed_exit:
 401   BITMAP_FREE (nonequal);
 402   cselib_finish ();
 403   return NULL;
 404 }
 405 \f
 406 /* Attempt to forward edges leaving basic block B.
 407    Return true if successful.  */
 408
 409 static bool
 410 try_forward_edges (int mode, basic_block b)
 411 {
 412   bool changed = false;
 413   edge_iterator ei;
 414   edge e, *threaded_edges = NULL;
 415
 416   /* If we are partitioning hot/cold basic blocks, we don't want to
 417      mess up unconditional or indirect jumps that cross between hot
 418      and cold sections.
 419
 420      Basic block partitioning may result in some jumps that appear to
 421      be optimizable (or blocks that appear to be mergeable), but which really
 422      must be left untouched (they are required to make it safely across
 423      partition boundaries).  See the comments at the top of
 424      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
 425
 426   if (find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX))
 427     return false;
 428
 429   for (ei = ei_start (b->succs); (e = ei_safe_edge (ei)); )
 430     {
 431       basic_block target, first;
 432       int counter, goto_locus;
 433       bool threaded = false;
 434       int nthreaded_edges = 0;
 435       bool may_thread = first_pass | df_get_bb_dirty (b);
 436
 437       /* Skip complex edges because we don't know how to update them.
 438
 439          Still handle fallthru edges, as we can succeed to forward fallthru
 440          edge to the same place as the branch edge of conditional branch
 441          and turn conditional branch to an unconditional branch.  */
 442       if (e->flags & EDGE_COMPLEX)
 443         {
 444           ei_next (&ei);
 445           continue;
 446         }
 447
 448       target = first = e->dest;
 449       counter = NUM_FIXED_BLOCKS;
 450       goto_locus = e->goto_locus;
 451
 452       /* If we are partitioning hot/cold basic_blocks, we don't want to mess
 453          up jumps that cross between hot/cold sections.
 454
 455          Basic block partitioning may result in some jumps that appear
 456          to be optimizable (or blocks that appear to be mergeable), but which
 457          really must be left untouched (they are required to make it safely
 458          across partition boundaries).  See the comments at the top of
 459          bb-reorder.c:partition_hot_cold_basic_blocks for complete
 460          details.  */
 461
 462       if (first != EXIT_BLOCK_PTR
 463           && find_reg_note (BB_END (first), REG_CROSSING_JUMP, NULL_RTX))
 464         return false;
 465
 466       while (counter < n_basic_blocks)
 467         {
 468           basic_block new_target = NULL;
 469           bool new_target_threaded = false;
 470           may_thread |= df_get_bb_dirty (target);
 471
 472           if (FORWARDER_BLOCK_P (target)
 473               && !(single_succ_edge (target)->flags & EDGE_CROSSING)
 474               && single_succ (target) != EXIT_BLOCK_PTR)
 475             {
 476               /* Bypass trivial infinite loops.  */
 477               new_target = single_succ (target);
 478               if (target == new_target)
 479                 counter = n_basic_blocks;
 480               else if (!optimize)
 481                 {
 482                   /* When not optimizing, ensure that edges or forwarder
 483                      blocks with different locus are not optimized out.  */
 484                   int locus = single_succ_edge (target)->goto_locus;
 485
 486                   if (locus && goto_locus && !locator_eq (locus, goto_locus))
 487                     counter = n_basic_blocks;
 488                   else if (locus)
 489                     goto_locus = locus;
 490
 491                   if (INSN_P (BB_END (target)))
 492                     {
 493                       locus = INSN_LOCATOR (BB_END (target));
 494
 495                       if (locus && goto_locus
 496                           && !locator_eq (locus, goto_locus))
 497                         counter = n_basic_blocks;
 498                       else if (locus)
 499                         goto_locus = locus;
 500                     }
 501                 }
 502             }
 503
 504           /* Allow to thread only over one edge at time to simplify updating
 505              of probabilities.  */
 506           else if ((mode & CLEANUP_THREADING) && may_thread)
 507             {
 508               edge t = thread_jump (e, target);
 509               if (t)
 510                 {
 511                   if (!threaded_edges)
 512                     threaded_edges = XNEWVEC (edge, n_basic_blocks);
 513                   else
 514                     {
 515                       int i;
 516
 517                       /* Detect an infinite loop across blocks not
 518                          including the start block.  */
 519                       for (i = 0; i < nthreaded_edges; ++i)
 520                         if (threaded_edges[i] == t)
 521                           break;
 522                       if (i < nthreaded_edges)
 523                         {
 524                           counter = n_basic_blocks;
 525                           break;
 526                         }
 527                     }
 528
 529                   /* Detect an infinite loop across the start block.  */
 530                   if (t->dest == b)
 531                     break;
 532
 533                   gcc_assert (nthreaded_edges < n_basic_blocks - NUM_FIXED_BLOCKS);
 534                   threaded_edges[nthreaded_edges++] = t;
 535
 536                   new_target = t->dest;
 537                   new_target_threaded = true;
 538                 }
 539             }
 540
 541           if (!new_target)
 542             break;
 543
 544           counter++;
 545           target = new_target;
 546           threaded |= new_target_threaded;
 547         }
 548
 549       if (counter >= n_basic_blocks)
 550         {
 551           if (dump_file)
 552             fprintf (dump_file, "Infinite loop in BB %i.\n",
 553                      target->index);
 554         }
 555       else if (target == first)
 556         ; /* We didn't do anything.  */
 557       else
 558         {
 559           /* Save the values now, as the edge may get removed.  */
 560           gcov_type edge_count = e->count;
 561           int edge_probability = e->probability;
 562           int edge_frequency;
 563           int n = 0;
 564
 565           e->goto_locus = goto_locus;
 566
 567           /* Don't force if target is exit block.  */
 568           if (threaded && target != EXIT_BLOCK_PTR)
 569             {
 570               notice_new_block (redirect_edge_and_branch_force (e, target));
 571               if (dump_file)
 572                 fprintf (dump_file, "Conditionals threaded.\n");
 573             }
 574           else if (!redirect_edge_and_branch (e, target))
 575             {
 576               if (dump_file)
 577                 fprintf (dump_file,
 578                          "Forwarding edge %i->%i to %i failed.\n",
 579                          b->index, e->dest->index, target->index);
 580               ei_next (&ei);
 581               continue;
 582             }
 583
 584           /* We successfully forwarded the edge.  Now update profile
 585              data: for each edge we traversed in the chain, remove
 586              the original edge's execution count.  */
 587           edge_frequency = ((edge_probability * b->frequency
 588                              + REG_BR_PROB_BASE / 2)
 589                             / REG_BR_PROB_BASE);
 590
 591           if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
 592             b->flags |= BB_FORWARDER_BLOCK;
 593
 594           do
 595             {
 596               edge t;
 597
 598               if (!single_succ_p (first))
 599                 {
 600                   gcc_assert (n < nthreaded_edges);
 601                   t = threaded_edges [n++];
 602                   gcc_assert (t->src == first);
 603                   update_bb_profile_for_threading (first, edge_frequency,
 604                                                    edge_count, t);
 605                   update_br_prob_note (first);
 606                 }
 607               else
 608                 {
 609                   first->count -= edge_count;
 610                   if (first->count < 0)
 611                     first->count = 0;
 612                   first->frequency -= edge_frequency;
 613                   if (first->frequency < 0)
 614                     first->frequency = 0;
 615                   /* It is possible that as the result of
 616                      threading we've removed edge as it is
 617                      threaded to the fallthru edge.  Avoid
 618                      getting out of sync.  */
 619                   if (n < nthreaded_edges
 620                       && first == threaded_edges [n]->src)
 621                     n++;
 622                   t = single_succ_edge (first);
 623                 }
 624
 625               t->count -= edge_count;
 626               if (t->count < 0)
 627                 t->count = 0;
 628               first = t->dest;
 629             }
 630           while (first != target);
 631
 632           changed = true;
 633           continue;
 634         }
 635       ei_next (&ei);
 636     }
 637
 638   if (threaded_edges)
 639     free (threaded_edges);
 640   return changed;
 641 }
 642 \f
 643
 644 /* Blocks A and B are to be merged into a single block.  A has no incoming
 645    fallthru edge, so it can be moved before B without adding or modifying
 646    any jumps (aside from the jump from A to B).  */
 647
 648 static void
 649 merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
 650 {
 651   rtx barrier;
 652
 653   /* If we are partitioning hot/cold basic blocks, we don't want to
 654      mess up unconditional or indirect jumps that cross between hot
 655      and cold sections.
 656
 657      Basic block partitioning may result in some jumps that appear to
 658      be optimizable (or blocks that appear to be mergeable), but which really
 659      must be left untouched (they are required to make it safely across
 660      partition boundaries).  See the comments at the top of
 661      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
 662
 663   if (BB_PARTITION (a) != BB_PARTITION (b))
 664     return;
 665
 666   barrier = next_nonnote_insn (BB_END (a));
 667   gcc_assert (BARRIER_P (barrier));
 668   delete_insn (barrier);
 669
 670   /* Scramble the insn chain.  */
 671   if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
 672     reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
 673   df_set_bb_dirty (a);
 674
 675   if (dump_file)
 676     fprintf (dump_file, "Moved block %d before %d and merged.\n",
 677              a->index, b->index);
 678
 679   /* Swap the records for the two blocks around.  */
 680
 681   unlink_block (a);
 682   link_block (a, b->prev_bb);
 683
 684   /* Now blocks A and B are contiguous.  Merge them.  */
 685   merge_blocks (a, b);
 686 }
 687
 688 /* Blocks A and B are to be merged into a single block.  B has no outgoing
 689    fallthru edge, so it can be moved after A without adding or modifying
 690    any jumps (aside from the jump from A to B).  */
 691
 692 static void
 693 merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
 694 {
 695   rtx barrier, real_b_end;
 696   rtx label, table;
 697
 698   /* If we are partitioning hot/cold basic blocks, we don't want to
 699      mess up unconditional or indirect jumps that cross between hot
 700      and cold sections.
 701
 702      Basic block partitioning may result in some jumps that appear to
 703      be optimizable (or blocks that appear to be mergeable), but which really
 704      must be left untouched (they are required to make it safely across
 705      partition boundaries).  See the comments at the top of
 706      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
 707
 708   if (BB_PARTITION (a) != BB_PARTITION (b))
 709     return;
 710
 711   real_b_end = BB_END (b);
 712
 713   /* If there is a jump table following block B temporarily add the jump table
 714      to block B so that it will also be moved to the correct location.  */
 715   if (tablejump_p (BB_END (b), &label, &table)
 716       && prev_active_insn (label) == BB_END (b))
 717     {
 718       BB_END (b) = table;
 719     }
 720
 721   /* There had better have been a barrier there.  Delete it.  */
 722   barrier = NEXT_INSN (BB_END (b));
 723   if (barrier && BARRIER_P (barrier))
 724     delete_insn (barrier);
 725
 726
 727   /* Scramble the insn chain.  */
 728   reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
 729
 730   /* Restore the real end of b.  */
 731   BB_END (b) = real_b_end;
 732
 733   if (dump_file)
 734     fprintf (dump_file, "Moved block %d after %d and merged.\n",
 735              b->index, a->index);
 736
 737   /* Now blocks A and B are contiguous.  Merge them.  */
 738   merge_blocks (a, b);
 739 }
 740
 741 /* Attempt to merge basic blocks that are potentially non-adjacent.
 742    Return NULL iff the attempt failed, otherwise return basic block
 743    where cleanup_cfg should continue.  Because the merging commonly
 744    moves basic block away or introduces another optimization
 745    possibility, return basic block just before B so cleanup_cfg don't
 746    need to iterate.
 747
 748    It may be good idea to return basic block before C in the case
 749    C has been moved after B and originally appeared earlier in the
 750    insn sequence, but we have no information available about the
 751    relative ordering of these two.  Hopefully it is not too common.  */
 752
 753 static basic_block
 754 merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
 755 {
 756   basic_block next;
 757
 758   /* If we are partitioning hot/cold basic blocks, we don't want to
 759      mess up unconditional or indirect jumps that cross between hot
 760      and cold sections.
 761
 762      Basic block partitioning may result in some jumps that appear to
 763      be optimizable (or blocks that appear to be mergeable), but which really
 764      must be left untouched (they are required to make it safely across
 765      partition boundaries).  See the comments at the top of
 766      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
 767
 768   if (BB_PARTITION (b) != BB_PARTITION (c))
 769     return NULL;
 770
 771   /* If B has a fallthru edge to C, no need to move anything.  */
 772   if (e->flags & EDGE_FALLTHRU)
 773     {
 774       int b_index = b->index, c_index = c->index;
 775       merge_blocks (b, c);
 776       update_forwarder_flag (b);
 777
 778       if (dump_file)
 779         fprintf (dump_file, "Merged %d and %d without moving.\n",
 780                  b_index, c_index);
 781
 782       return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
 783     }
 784
 785   /* Otherwise we will need to move code around.  Do that only if expensive
 786      transformations are allowed.  */
 787   else if (mode & CLEANUP_EXPENSIVE)
 788     {
 789       edge tmp_edge, b_fallthru_edge;
 790       bool c_has_outgoing_fallthru;
 791       bool b_has_incoming_fallthru;
 792       edge_iterator ei;
 793
 794       /* Avoid overactive code motion, as the forwarder blocks should be
 795          eliminated by edge redirection instead.  One exception might have
 796          been if B is a forwarder block and C has no fallthru edge, but
 797          that should be cleaned up by bb-reorder instead.  */
 798       if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
 799         return NULL;
 800
 801       /* We must make sure to not munge nesting of lexical blocks,
 802          and loop notes.  This is done by squeezing out all the notes
 803          and leaving them there to lie.  Not ideal, but functional.  */
 804
 805       FOR_EACH_EDGE (tmp_edge, ei, c->succs)
 806         if (tmp_edge->flags & EDGE_FALLTHRU)
 807           break;
 808
 809       c_has_outgoing_fallthru = (tmp_edge != NULL);
 810
 811       FOR_EACH_EDGE (tmp_edge, ei, b->preds)
 812         if (tmp_edge->flags & EDGE_FALLTHRU)
 813           break;
 814
 815       b_has_incoming_fallthru = (tmp_edge != NULL);
 816       b_fallthru_edge = tmp_edge;
 817       next = b->prev_bb;
 818       if (next == c)
 819         next = next->prev_bb;
 820
 821       /* Otherwise, we're going to try to move C after B.  If C does
 822          not have an outgoing fallthru, then it can be moved
 823          immediately after B without introducing or modifying jumps.  */
 824       if (! c_has_outgoing_fallthru)
 825         {
 826           merge_blocks_move_successor_nojumps (b, c);
 827           return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
 828         }
 829
 830       /* If B does not have an incoming fallthru, then it can be moved
 831          immediately before C without introducing or modifying jumps.
 832          C cannot be the first block, so we do not have to worry about
 833          accessing a non-existent block.  */
 834
 835       if (b_has_incoming_fallthru)
 836         {
 837           basic_block bb;
 838
 839           if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
 840             return NULL;
 841           bb = force_nonfallthru (b_fallthru_edge);
 842           if (bb)
 843             notice_new_block (bb);
 844         }
 845
 846       merge_blocks_move_predecessor_nojumps (b, c);
 847       return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
 848     }
 849
 850   return NULL;
 851 }
 852 \f
 853
 854 /* Removes the memory attributes of MEM expression
 855    if they are not equal.  */
 856
 857 void
 858 merge_memattrs (rtx x, rtx y)
 859 {
 860   int i;
 861   int j;
 862   enum rtx_code code;
 863   const char *fmt;
 864
 865   if (x == y)
 866     return;
 867   if (x == 0 || y == 0)
 868     return;
 869
 870   code = GET_CODE (x);
 871
 872   if (code != GET_CODE (y))
 873     return;
 874
 875   if (GET_MODE (x) != GET_MODE (y))
 876     return;
 877
 878   if (code == MEM && MEM_ATTRS (x) != MEM_ATTRS (y))
 879     {
 880       if (! MEM_ATTRS (x))
 881         MEM_ATTRS (y) = 0;
 882       else if (! MEM_ATTRS (y))
 883         MEM_ATTRS (x) = 0;
 884       else
 885         {
 886           rtx mem_size;
 887
 888           if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
 889             {
 890               set_mem_alias_set (x, 0);
 891               set_mem_alias_set (y, 0);
 892             }
 893
 894           if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
 895             {
 896               set_mem_expr (x, 0);
 897               set_mem_expr (y, 0);
 898               set_mem_offset (x, 0);
 899               set_mem_offset (y, 0);
 900             }
 901           else if (MEM_OFFSET (x) != MEM_OFFSET (y))
 902             {
 903               set_mem_offset (x, 0);
 904               set_mem_offset (y, 0);
 905             }
 906
 907           if (!MEM_SIZE (x))
 908             mem_size = NULL_RTX;
 909           else if (!MEM_SIZE (y))
 910             mem_size = NULL_RTX;
 911           else
 912             mem_size = GEN_INT (MAX (INTVAL (MEM_SIZE (x)),
 913                                      INTVAL (MEM_SIZE (y))));
 914           set_mem_size (x, mem_size);
 915           set_mem_size (y, mem_size);
 916
 917           set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
 918           set_mem_align (y, MEM_ALIGN (x));
 919         }
 920     }
 921
 922   fmt = GET_RTX_FORMAT (code);
 923   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
 924     {
 925       switch (fmt[i])
 926         {
 927         case 'E':
 928           /* Two vectors must have the same length.  */
 929           if (XVECLEN (x, i) != XVECLEN (y, i))
 930             return;
 931
 932           for (j = 0; j < XVECLEN (x, i); j++)
 933             merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
 934
 935           break;
 936
 937         case 'e':
 938           merge_memattrs (XEXP (x, i), XEXP (y, i));
 939         }
 940     }
 941   return;
 942 }
 943
 944
 945 /* Return true if I1 and I2 are equivalent and thus can be crossjumped.  */
 946
 947 static bool
 948 old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx i1, rtx i2)
 949 {
 950   rtx p1, p2;
 951
 952   /* Verify that I1 and I2 are equivalent.  */
 953   if (GET_CODE (i1) != GET_CODE (i2))
 954     return false;
 955
 956   p1 = PATTERN (i1);
 957   p2 = PATTERN (i2);
 958
 959   if (GET_CODE (p1) != GET_CODE (p2))
 960     return false;
 961
 962   /* If this is a CALL_INSN, compare register usage information.
 963      If we don't check this on stack register machines, the two
 964      CALL_INSNs might be merged leaving reg-stack.c with mismatching
 965      numbers of stack registers in the same basic block.
 966      If we don't check this on machines with delay slots, a delay slot may
 967      be filled that clobbers a parameter expected by the subroutine.
 968
 969      ??? We take the simple route for now and assume that if they're
 970      equal, they were constructed identically.  */
 971
 972   if (CALL_P (i1)
 973       && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
 974                         CALL_INSN_FUNCTION_USAGE (i2))
 975           || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
 976     return false;
 977
 978 #ifdef STACK_REGS
 979   /* If cross_jump_death_matters is not 0, the insn's mode
 980      indicates whether or not the insn contains any stack-like
 981      regs.  */
 982
 983   if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
 984     {
 985       /* If register stack conversion has already been done, then
 986          death notes must also be compared before it is certain that
 987          the two instruction streams match.  */
 988
 989       rtx note;
 990       HARD_REG_SET i1_regset, i2_regset;
 991
 992       CLEAR_HARD_REG_SET (i1_regset);
 993       CLEAR_HARD_REG_SET (i2_regset);
 994
 995       for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
 996         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
 997           SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
 998
 999       for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
1000         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
1001           SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
1002
1003       if (!hard_reg_set_equal_p (i1_regset, i2_regset))
1004         return false;
1005     }
1006 #endif
1007
1008   if (reload_completed
1009       ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
1010     return true;
1011
1012   /* Do not do EQUIV substitution after reload.  First, we're undoing the
1013      work of reload_cse.  Second, we may be undoing the work of the post-
1014      reload splitting pass.  */
1015   /* ??? Possibly add a new phase switch variable that can be used by
1016      targets to disallow the troublesome insns after splitting.  */
1017   if (!reload_completed)
1018     {
1019       /* The following code helps take care of G++ cleanups.  */
1020       rtx equiv1 = find_reg_equal_equiv_note (i1);
1021       rtx equiv2 = find_reg_equal_equiv_note (i2);
1022
1023       if (equiv1 && equiv2
1024           /* If the equivalences are not to a constant, they may
1025              reference pseudos that no longer exist, so we can't
1026              use them.  */
1027           && (! reload_completed
1028               || (CONSTANT_P (XEXP (equiv1, 0))
1029                   && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
1030         {
1031           rtx s1 = single_set (i1);
1032           rtx s2 = single_set (i2);
1033           if (s1 != 0 && s2 != 0
1034               && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
1035             {
1036               validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
1037               validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
1038               if (! rtx_renumbered_equal_p (p1, p2))
1039                 cancel_changes (0);
1040               else if (apply_change_group ())
1041                 return true;
1042             }
1043         }
1044     }
1045
1046   return false;
1047 }
1048 \f
1049 /* Look through the insns at the end of BB1 and BB2 and find the longest
1050    sequence that are equivalent.  Store the first insns for that sequence
1051    in *F1 and *F2 and return the sequence length.
1052
1053    To simplify callers of this function, if the blocks match exactly,
1054    store the head of the blocks in *F1 and *F2.  */
1055
1056 static int
1057 flow_find_cross_jump (int mode ATTRIBUTE_UNUSED, basic_block bb1,
1058                       basic_block bb2, rtx *f1, rtx *f2)
1059 {
1060   rtx i1, i2, last1, last2, afterlast1, afterlast2;
1061   int ninsns = 0;
1062
1063   /* Skip simple jumps at the end of the blocks.  Complex jumps still
1064      need to be compared for equivalence, which we'll do below.  */
1065
1066   i1 = BB_END (bb1);
1067   last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
1068   if (onlyjump_p (i1)
1069       || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1070     {
1071       last1 = i1;
1072       i1 = PREV_INSN (i1);
1073     }
1074
1075   i2 = BB_END (bb2);
1076   if (onlyjump_p (i2)
1077       || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1078     {
1079       last2 = i2;
1080       /* Count everything except for unconditional jump as insn.  */
1081       if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1082         ninsns++;
1083       i2 = PREV_INSN (i2);
1084     }
1085
1086   while (true)
1087     {
1088       /* Ignore notes.  */
1089       while (!INSN_P (i1) && i1 != BB_HEAD (bb1))
1090         i1 = PREV_INSN (i1);
1091
1092       while (!INSN_P (i2) && i2 != BB_HEAD (bb2))
1093         i2 = PREV_INSN (i2);
1094
1095       if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
1096         break;
1097
1098       if (!old_insns_match_p (mode, i1, i2))
1099         break;
1100
1101       merge_memattrs (i1, i2);
1102
1103       /* Don't begin a cross-jump with a NOTE insn.  */
1104       if (INSN_P (i1))
1105         {
1106           /* If the merged insns have different REG_EQUAL notes, then
1107              remove them.  */
1108           rtx equiv1 = find_reg_equal_equiv_note (i1);
1109           rtx equiv2 = find_reg_equal_equiv_note (i2);
1110
1111           if (equiv1 && !equiv2)
1112             remove_note (i1, equiv1);
1113           else if (!equiv1 && equiv2)
1114             remove_note (i2, equiv2);
1115           else if (equiv1 && equiv2
1116                    && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1117             {
1118               remove_note (i1, equiv1);
1119               remove_note (i2, equiv2);
1120             }
1121
1122           afterlast1 = last1, afterlast2 = last2;
1123           last1 = i1, last2 = i2;
1124           ninsns++;
1125         }
1126
1127       i1 = PREV_INSN (i1);
1128       i2 = PREV_INSN (i2);
1129     }
1130
1131 #ifdef HAVE_cc0
1132   /* Don't allow the insn after a compare to be shared by
1133      cross-jumping unless the compare is also shared.  */
1134   if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1135     last1 = afterlast1, last2 = afterlast2, ninsns--;
1136 #endif
1137
1138   /* Include preceding notes and labels in the cross-jump.  One,
1139      this may bring us to the head of the blocks as requested above.
1140      Two, it keeps line number notes as matched as may be.  */
1141   if (ninsns)
1142     {
1143       while (last1 != BB_HEAD (bb1) && !INSN_P (PREV_INSN (last1)))
1144         last1 = PREV_INSN (last1);
1145
1146       if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
1147         last1 = PREV_INSN (last1);
1148
1149       while (last2 != BB_HEAD (bb2) && !INSN_P (PREV_INSN (last2)))
1150         last2 = PREV_INSN (last2);
1151
1152       if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
1153         last2 = PREV_INSN (last2);
1154
1155       *f1 = last1;
1156       *f2 = last2;
1157     }
1158
1159   return ninsns;
1160 }
1161
1162 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1163    the branch instruction.  This means that if we commonize the control
1164    flow before end of the basic block, the semantic remains unchanged.
1165
1166    We may assume that there exists one edge with a common destination.  */
1167
1168 static bool
1169 outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
1170 {
1171   int nehedges1 = 0, nehedges2 = 0;
1172   edge fallthru1 = 0, fallthru2 = 0;
1173   edge e1, e2;
1174   edge_iterator ei;
1175
1176   /* If BB1 has only one successor, we may be looking at either an
1177      unconditional jump, or a fake edge to exit.  */
1178   if (single_succ_p (bb1)
1179       && (single_succ_edge (bb1)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1180       && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
1181     return (single_succ_p (bb2)
1182             && (single_succ_edge (bb2)->flags
1183                 & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1184             && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
1185
1186   /* Match conditional jumps - this may get tricky when fallthru and branch
1187      edges are crossed.  */
1188   if (EDGE_COUNT (bb1->succs) == 2
1189       && any_condjump_p (BB_END (bb1))
1190       && onlyjump_p (BB_END (bb1)))
1191     {
1192       edge b1, f1, b2, f2;
1193       bool reverse, match;
1194       rtx set1, set2, cond1, cond2;
1195       enum rtx_code code1, code2;
1196
1197       if (EDGE_COUNT (bb2->succs) != 2
1198           || !any_condjump_p (BB_END (bb2))
1199           || !onlyjump_p (BB_END (bb2)))
1200         return false;
1201
1202       b1 = BRANCH_EDGE (bb1);
1203       b2 = BRANCH_EDGE (bb2);
1204       f1 = FALLTHRU_EDGE (bb1);
1205       f2 = FALLTHRU_EDGE (bb2);
1206
1207       /* Get around possible forwarders on fallthru edges.  Other cases
1208          should be optimized out already.  */
1209       if (FORWARDER_BLOCK_P (f1->dest))
1210         f1 = single_succ_edge (f1->dest);
1211
1212       if (FORWARDER_BLOCK_P (f2->dest))
1213         f2 = single_succ_edge (f2->dest);
1214
1215       /* To simplify use of this function, return false if there are
1216          unneeded forwarder blocks.  These will get eliminated later
1217          during cleanup_cfg.  */
1218       if (FORWARDER_BLOCK_P (f1->dest)
1219           || FORWARDER_BLOCK_P (f2->dest)
1220           || FORWARDER_BLOCK_P (b1->dest)
1221           || FORWARDER_BLOCK_P (b2->dest))
1222         return false;
1223
1224       if (f1->dest == f2->dest && b1->dest == b2->dest)
1225         reverse = false;
1226       else if (f1->dest == b2->dest && b1->dest == f2->dest)
1227         reverse = true;
1228       else
1229         return false;
1230
1231       set1 = pc_set (BB_END (bb1));
1232       set2 = pc_set (BB_END (bb2));
1233       if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1234           != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1235         reverse = !reverse;
1236
1237       cond1 = XEXP (SET_SRC (set1), 0);
1238       cond2 = XEXP (SET_SRC (set2), 0);
1239       code1 = GET_CODE (cond1);
1240       if (reverse)
1241         code2 = reversed_comparison_code (cond2, BB_END (bb2));
1242       else
1243         code2 = GET_CODE (cond2);
1244
1245       if (code2 == UNKNOWN)
1246         return false;
1247
1248       /* Verify codes and operands match.  */
1249       match = ((code1 == code2
1250                 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1251                 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1252                || (code1 == swap_condition (code2)
1253                    && rtx_renumbered_equal_p (XEXP (cond1, 1),
1254                                               XEXP (cond2, 0))
1255                    && rtx_renumbered_equal_p (XEXP (cond1, 0),
1256                                               XEXP (cond2, 1))));
1257
1258       /* If we return true, we will join the blocks.  Which means that
1259          we will only have one branch prediction bit to work with.  Thus
1260          we require the existing branches to have probabilities that are
1261          roughly similar.  */
1262       if (match
1263           && optimize_bb_for_speed_p (bb1)
1264           && optimize_bb_for_speed_p (bb2))
1265         {
1266           int prob2;
1267
1268           if (b1->dest == b2->dest)
1269             prob2 = b2->probability;
1270           else
1271             /* Do not use f2 probability as f2 may be forwarded.  */
1272             prob2 = REG_BR_PROB_BASE - b2->probability;
1273
1274           /* Fail if the difference in probabilities is greater than 50%.
1275              This rules out two well-predicted branches with opposite
1276              outcomes.  */
1277           if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1278             {
1279               if (dump_file)
1280                 fprintf (dump_file,
1281                          "Outcomes of branch in bb %i and %i differ too much (%i %i)\n",
1282                          bb1->index, bb2->index, b1->probability, prob2);
1283
1284               return false;
1285             }
1286         }
1287
1288       if (dump_file && match)
1289         fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
1290                  bb1->index, bb2->index);
1291
1292       return match;
1293     }
1294
1295   /* Generic case - we are seeing a computed jump, table jump or trapping
1296      instruction.  */
1297
1298   /* Check whether there are tablejumps in the end of BB1 and BB2.
1299      Return true if they are identical.  */
1300     {
1301       rtx label1, label2;
1302       rtx table1, table2;
1303
1304       if (tablejump_p (BB_END (bb1), &label1, &table1)
1305           && tablejump_p (BB_END (bb2), &label2, &table2)
1306           && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1307         {
1308           /* The labels should never be the same rtx.  If they really are same
1309              the jump tables are same too. So disable crossjumping of blocks BB1
1310              and BB2 because when deleting the common insns in the end of BB1
1311              by delete_basic_block () the jump table would be deleted too.  */
1312           /* If LABEL2 is referenced in BB1->END do not do anything
1313              because we would loose information when replacing
1314              LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END.  */
1315           if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
1316             {
1317               /* Set IDENTICAL to true when the tables are identical.  */
1318               bool identical = false;
1319               rtx p1, p2;
1320
1321               p1 = PATTERN (table1);
1322               p2 = PATTERN (table2);
1323               if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1324                 {
1325                   identical = true;
1326                 }
1327               else if (GET_CODE (p1) == ADDR_DIFF_VEC
1328                        && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1329                        && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1330                        && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1331                 {
1332                   int i;
1333
1334                   identical = true;
1335                   for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1336                     if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1337                       identical = false;
1338                 }
1339
1340               if (identical)
1341                 {
1342                   replace_label_data rr;
1343                   bool match;
1344
1345                   /* Temporarily replace references to LABEL1 with LABEL2
1346                      in BB1->END so that we could compare the instructions.  */
1347                   rr.r1 = label1;
1348                   rr.r2 = label2;
1349                   rr.update_label_nuses = false;
1350                   for_each_rtx (&BB_END (bb1), replace_label, &rr);
1351
1352                   match = old_insns_match_p (mode, BB_END (bb1), BB_END (bb2));
1353                   if (dump_file && match)
1354                     fprintf (dump_file,
1355                              "Tablejumps in bb %i and %i match.\n",
1356                              bb1->index, bb2->index);
1357
1358                   /* Set the original label in BB1->END because when deleting
1359                      a block whose end is a tablejump, the tablejump referenced
1360                      from the instruction is deleted too.  */
1361                   rr.r1 = label2;
1362                   rr.r2 = label1;
1363                   for_each_rtx (&BB_END (bb1), replace_label, &rr);
1364
1365                   return match;
1366                 }
1367             }
1368           return false;
1369         }
1370     }
1371
1372   /* First ensure that the instructions match.  There may be many outgoing
1373      edges so this test is generally cheaper.  */
1374   if (!old_insns_match_p (mode, BB_END (bb1), BB_END (bb2)))
1375     return false;
1376
1377   /* Search the outgoing edges, ensure that the counts do match, find possible
1378      fallthru and exception handling edges since these needs more
1379      validation.  */
1380   if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
1381     return false;
1382
1383   FOR_EACH_EDGE (e1, ei, bb1->succs)
1384     {
1385       e2 = EDGE_SUCC (bb2, ei.index);
1386
1387       if (e1->flags & EDGE_EH)
1388         nehedges1++;
1389
1390       if (e2->flags & EDGE_EH)
1391         nehedges2++;
1392
1393       if (e1->flags & EDGE_FALLTHRU)
1394         fallthru1 = e1;
1395       if (e2->flags & EDGE_FALLTHRU)
1396         fallthru2 = e2;
1397     }
1398
1399   /* If number of edges of various types does not match, fail.  */
1400   if (nehedges1 != nehedges2
1401       || (fallthru1 != 0) != (fallthru2 != 0))
1402     return false;
1403
1404   /* fallthru edges must be forwarded to the same destination.  */
1405   if (fallthru1)
1406     {
1407       basic_block d1 = (forwarder_block_p (fallthru1->dest)
1408                         ? single_succ (fallthru1->dest): fallthru1->dest);
1409       basic_block d2 = (forwarder_block_p (fallthru2->dest)
1410                         ? single_succ (fallthru2->dest): fallthru2->dest);
1411
1412       if (d1 != d2)
1413         return false;
1414     }
1415
1416   /* Ensure the same EH region.  */
1417   {
1418     rtx n1 = find_reg_note (BB_END (bb1), REG_EH_REGION, 0);
1419     rtx n2 = find_reg_note (BB_END (bb2), REG_EH_REGION, 0);
1420
1421     if (!n1 && n2)
1422       return false;
1423
1424     if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
1425       return false;
1426   }
1427
1428   /* The same checks as in try_crossjump_to_edge. It is required for RTL
1429      version of sequence abstraction.  */
1430   FOR_EACH_EDGE (e1, ei, bb2->succs)
1431     {
1432       edge e2;
1433       edge_iterator ei;
1434       basic_block d1 = e1->dest;
1435
1436       if (FORWARDER_BLOCK_P (d1))
1437         d1 = EDGE_SUCC (d1, 0)->dest;
1438
1439       FOR_EACH_EDGE (e2, ei, bb1->succs)
1440         {
1441           basic_block d2 = e2->dest;
1442           if (FORWARDER_BLOCK_P (d2))
1443             d2 = EDGE_SUCC (d2, 0)->dest;
1444           if (d1 == d2)
1445             break;
1446         }
1447
1448       if (!e2)
1449         return false;
1450     }
1451
1452   return true;
1453 }
1454
1455 /* Returns true if BB basic block has a preserve label.  */
1456
1457 static bool
1458 block_has_preserve_label (basic_block bb)
1459 {
1460   return (bb
1461           && block_label (bb)
1462           && LABEL_PRESERVE_P (block_label (bb)));
1463 }
1464
1465 /* E1 and E2 are edges with the same destination block.  Search their
1466    predecessors for common code.  If found, redirect control flow from
1467    (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC.  */
1468
1469 static bool
1470 try_crossjump_to_edge (int mode, edge e1, edge e2)
1471 {
1472   int nmatch;
1473   basic_block src1 = e1->src, src2 = e2->src;
1474   basic_block redirect_to, redirect_from, to_remove;
1475   rtx newpos1, newpos2;
1476   edge s;
1477   edge_iterator ei;
1478
1479   newpos1 = newpos2 = NULL_RTX;
1480
1481   /* If we have partitioned hot/cold basic blocks, it is a bad idea
1482      to try this optimization.
1483
1484      Basic block partitioning may result in some jumps that appear to
1485      be optimizable (or blocks that appear to be mergeable), but which really
1486      must be left untouched (they are required to make it safely across
1487      partition boundaries).  See the comments at the top of
1488      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
1489
1490   if (flag_reorder_blocks_and_partition && reload_completed)
1491     return false;
1492
1493   /* Search backward through forwarder blocks.  We don't need to worry
1494      about multiple entry or chained forwarders, as they will be optimized
1495      away.  We do this to look past the unconditional jump following a
1496      conditional jump that is required due to the current CFG shape.  */
1497   if (single_pred_p (src1)
1498       && FORWARDER_BLOCK_P (src1))
1499     e1 = single_pred_edge (src1), src1 = e1->src;
1500
1501   if (single_pred_p (src2)
1502       && FORWARDER_BLOCK_P (src2))
1503     e2 = single_pred_edge (src2), src2 = e2->src;
1504
1505   /* Nothing to do if we reach ENTRY, or a common source block.  */
1506   if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1507     return false;
1508   if (src1 == src2)
1509     return false;
1510
1511   /* Seeing more than 1 forwarder blocks would confuse us later...  */
1512   if (FORWARDER_BLOCK_P (e1->dest)
1513       && FORWARDER_BLOCK_P (single_succ (e1->dest)))
1514     return false;
1515
1516   if (FORWARDER_BLOCK_P (e2->dest)
1517       && FORWARDER_BLOCK_P (single_succ (e2->dest)))
1518     return false;
1519
1520   /* Likewise with dead code (possibly newly created by the other optimizations
1521      of cfg_cleanup).  */
1522   if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
1523     return false;
1524
1525   /* Look for the common insn sequence, part the first ...  */
1526   if (!outgoing_edges_match (mode, src1, src2))
1527     return false;
1528
1529   /* ... and part the second.  */
1530   nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1531
1532   /* Don't proceed with the crossjump unless we found a sufficient number
1533      of matching instructions or the 'from' block was totally matched
1534      (such that its predecessors will hopefully be redirected and the
1535      block removed).  */
1536   if ((nmatch < PARAM_VALUE (PARAM_MIN_CROSSJUMP_INSNS))
1537       && (newpos1 != BB_HEAD (src1)))
1538     return false;
1539
1540   /* Avoid deleting preserve label when redirecting ABNORMAL edges.  */
1541   if (block_has_preserve_label (e1->dest)
1542       && (e1->flags & EDGE_ABNORMAL))
1543     return false;
1544
1545   /* Here we know that the insns in the end of SRC1 which are common with SRC2
1546      will be deleted.
1547      If we have tablejumps in the end of SRC1 and SRC2
1548      they have been already compared for equivalence in outgoing_edges_match ()
1549      so replace the references to TABLE1 by references to TABLE2.  */
1550     {
1551       rtx label1, label2;
1552       rtx table1, table2;
1553
1554       if (tablejump_p (BB_END (src1), &label1, &table1)
1555           && tablejump_p (BB_END (src2), &label2, &table2)
1556           && label1 != label2)
1557         {
1558           replace_label_data rr;
1559           rtx insn;
1560
1561           /* Replace references to LABEL1 with LABEL2.  */
1562           rr.r1 = label1;
1563           rr.r2 = label2;
1564           rr.update_label_nuses = true;
1565           for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1566             {
1567               /* Do not replace the label in SRC1->END because when deleting
1568                  a block whose end is a tablejump, the tablejump referenced
1569                  from the instruction is deleted too.  */
1570               if (insn != BB_END (src1))
1571                 for_each_rtx (&insn, replace_label, &rr);
1572             }
1573         }
1574     }
1575
1576   /* Avoid splitting if possible.  We must always split when SRC2 has
1577      EH predecessor edges, or we may end up with basic blocks with both
1578      normal and EH predecessor edges.  */
1579   if (newpos2 == BB_HEAD (src2)
1580       && !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
1581     redirect_to = src2;
1582   else
1583     {
1584       if (newpos2 == BB_HEAD (src2))
1585         {
1586           /* Skip possible basic block header.  */
1587           if (LABEL_P (newpos2))
1588             newpos2 = NEXT_INSN (newpos2);
1589           if (NOTE_P (newpos2))
1590             newpos2 = NEXT_INSN (newpos2);
1591         }
1592
1593       if (dump_file)
1594         fprintf (dump_file, "Splitting bb %i before %i insns\n",
1595                  src2->index, nmatch);
1596       redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1597     }
1598
1599   if (dump_file)
1600     fprintf (dump_file,
1601              "Cross jumping from bb %i to bb %i; %i common insns\n",
1602              src1->index, src2->index, nmatch);
1603
1604   /* We may have some registers visible through the block.  */
1605   df_set_bb_dirty (redirect_to);
1606
1607   /* Recompute the frequencies and counts of outgoing edges.  */
1608   FOR_EACH_EDGE (s, ei, redirect_to->succs)
1609     {
1610       edge s2;
1611       edge_iterator ei;
1612       basic_block d = s->dest;
1613
1614       if (FORWARDER_BLOCK_P (d))
1615         d = single_succ (d);
1616
1617       FOR_EACH_EDGE (s2, ei, src1->succs)
1618         {
1619           basic_block d2 = s2->dest;
1620           if (FORWARDER_BLOCK_P (d2))
1621             d2 = single_succ (d2);
1622           if (d == d2)
1623             break;
1624         }
1625
1626       s->count += s2->count;
1627
1628       /* Take care to update possible forwarder blocks.  We verified
1629          that there is no more than one in the chain, so we can't run
1630          into infinite loop.  */
1631       if (FORWARDER_BLOCK_P (s->dest))
1632         {
1633           single_succ_edge (s->dest)->count += s2->count;
1634           s->dest->count += s2->count;
1635           s->dest->frequency += EDGE_FREQUENCY (s);
1636         }
1637
1638       if (FORWARDER_BLOCK_P (s2->dest))
1639         {
1640           single_succ_edge (s2->dest)->count -= s2->count;
1641           if (single_succ_edge (s2->dest)->count < 0)
1642             single_succ_edge (s2->dest)->count = 0;
1643           s2->dest->count -= s2->count;
1644           s2->dest->frequency -= EDGE_FREQUENCY (s);
1645           if (s2->dest->frequency < 0)
1646             s2->dest->frequency = 0;
1647           if (s2->dest->count < 0)
1648             s2->dest->count = 0;
1649         }
1650
1651       if (!redirect_to->frequency && !src1->frequency)
1652         s->probability = (s->probability + s2->probability) / 2;
1653       else
1654         s->probability
1655           = ((s->probability * redirect_to->frequency +
1656               s2->probability * src1->frequency)
1657              / (redirect_to->frequency + src1->frequency));
1658     }
1659
1660   /* Adjust count and frequency for the block.  An earlier jump
1661      threading pass may have left the profile in an inconsistent
1662      state (see update_bb_profile_for_threading) so we must be
1663      prepared for overflows.  */
1664   redirect_to->count += src1->count;
1665   redirect_to->frequency += src1->frequency;
1666   if (redirect_to->frequency > BB_FREQ_MAX)
1667     redirect_to->frequency = BB_FREQ_MAX;
1668   update_br_prob_note (redirect_to);
1669
1670   /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1.  */
1671
1672   /* Skip possible basic block header.  */
1673   if (LABEL_P (newpos1))
1674     newpos1 = NEXT_INSN (newpos1);
1675
1676   if (NOTE_P (newpos1))
1677     newpos1 = NEXT_INSN (newpos1);
1678
1679   redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
1680   to_remove = single_succ (redirect_from);
1681
1682   redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
1683   delete_basic_block (to_remove);
1684
1685   update_forwarder_flag (redirect_from);
1686   if (redirect_to != src2)
1687     update_forwarder_flag (src2);
1688
1689   return true;
1690 }
1691
1692 /* Search the predecessors of BB for common insn sequences.  When found,
1693    share code between them by redirecting control flow.  Return true if
1694    any changes made.  */
1695
1696 static bool
1697 try_crossjump_bb (int mode, basic_block bb)
1698 {
1699   edge e, e2, fallthru;
1700   bool changed;
1701   unsigned max, ix, ix2;
1702   basic_block ev, ev2;
1703   edge_iterator ei;
1704
1705   /* Nothing to do if there is not at least two incoming edges.  */
1706   if (EDGE_COUNT (bb->preds) < 2)
1707     return false;
1708
1709   /* Don't crossjump if this block ends in a computed jump,
1710      unless we are optimizing for size.  */
1711   if (optimize_bb_for_size_p (bb)
1712       && bb != EXIT_BLOCK_PTR
1713       && computed_jump_p (BB_END (bb)))
1714     return false;
1715
1716   /* If we are partitioning hot/cold basic blocks, we don't want to
1717      mess up unconditional or indirect jumps that cross between hot
1718      and cold sections.
1719
1720      Basic block partitioning may result in some jumps that appear to
1721      be optimizable (or blocks that appear to be mergeable), but which really
1722      must be left untouched (they are required to make it safely across
1723      partition boundaries).  See the comments at the top of
1724      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
1725
1726   if (BB_PARTITION (EDGE_PRED (bb, 0)->src) !=
1727                                         BB_PARTITION (EDGE_PRED (bb, 1)->src)
1728       || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING))
1729     return false;
1730
1731   /* It is always cheapest to redirect a block that ends in a branch to
1732      a block that falls through into BB, as that adds no branches to the
1733      program.  We'll try that combination first.  */
1734   fallthru = NULL;
1735   max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
1736
1737   if (EDGE_COUNT (bb->preds) > max)
1738     return false;
1739
1740   FOR_EACH_EDGE (e, ei, bb->preds)
1741     {
1742       if (e->flags & EDGE_FALLTHRU)
1743         {
1744           fallthru = e;
1745           break;
1746         }
1747     }
1748
1749   changed = false;
1750   for (ix = 0, ev = bb; ix < EDGE_COUNT (ev->preds); )
1751     {
1752       e = EDGE_PRED (ev, ix);
1753       ix++;
1754
1755       /* As noted above, first try with the fallthru predecessor (or, a
1756          fallthru predecessor if we are in cfglayout mode).  */
1757       if (fallthru)
1758         {
1759           /* Don't combine the fallthru edge into anything else.
1760              If there is a match, we'll do it the other way around.  */
1761           if (e == fallthru)
1762             continue;
1763           /* If nothing changed since the last attempt, there is nothing
1764              we can do.  */
1765           if (!first_pass
1766               && (!(df_get_bb_dirty (e->src))
1767                   && !(df_get_bb_dirty (fallthru->src))))
1768             continue;
1769
1770           if (try_crossjump_to_edge (mode, e, fallthru))
1771             {
1772               changed = true;
1773               ix = 0;
1774               ev = bb;
1775               continue;
1776             }
1777         }
1778
1779       /* Non-obvious work limiting check: Recognize that we're going
1780          to call try_crossjump_bb on every basic block.  So if we have
1781          two blocks with lots of outgoing edges (a switch) and they
1782          share lots of common destinations, then we would do the
1783          cross-jump check once for each common destination.
1784
1785          Now, if the blocks actually are cross-jump candidates, then
1786          all of their destinations will be shared.  Which means that
1787          we only need check them for cross-jump candidacy once.  We
1788          can eliminate redundant checks of crossjump(A,B) by arbitrarily
1789          choosing to do the check from the block for which the edge
1790          in question is the first successor of A.  */
1791       if (EDGE_SUCC (e->src, 0) != e)
1792         continue;
1793
1794       for (ix2 = 0, ev2 = bb; ix2 < EDGE_COUNT (ev2->preds); )
1795         {
1796           e2 = EDGE_PRED (ev2, ix2);
1797           ix2++;
1798
1799           if (e2 == e)
1800             continue;
1801
1802           /* We've already checked the fallthru edge above.  */
1803           if (e2 == fallthru)
1804             continue;
1805
1806           /* The "first successor" check above only prevents multiple
1807              checks of crossjump(A,B).  In order to prevent redundant
1808              checks of crossjump(B,A), require that A be the block
1809              with the lowest index.  */
1810           if (e->src->index > e2->src->index)
1811             continue;
1812
1813           /* If nothing changed since the last attempt, there is nothing
1814              we can do.  */
1815           if (!first_pass
1816               && (!(df_get_bb_dirty (e->src))
1817                   && !(df_get_bb_dirty (e2->src))))
1818             continue;
1819
1820           if (try_crossjump_to_edge (mode, e, e2))
1821             {
1822               changed = true;
1823               ev2 = bb;
1824               ix = 0;
1825               break;
1826             }
1827         }
1828     }
1829
1830   if (changed)
1831     crossjumps_occured = true;
1832
1833   return changed;
1834 }
1835
1836 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1837    instructions etc.  Return nonzero if changes were made.  */
1838
1839 static bool
1840 try_optimize_cfg (int mode)
1841 {
1842   bool changed_overall = false;
1843   bool changed;
1844   int iterations = 0;
1845   basic_block bb, b, next;
1846
1847   if (mode & (CLEANUP_CROSSJUMP | CLEANUP_THREADING))
1848     clear_bb_flags ();
1849
1850   crossjumps_occured = false;
1851
1852   FOR_EACH_BB (bb)
1853     update_forwarder_flag (bb);
1854
1855   if (! targetm.cannot_modify_jumps_p ())
1856     {
1857       first_pass = true;
1858       /* Attempt to merge blocks as made possible by edge removal.  If
1859          a block has only one successor, and the successor has only
1860          one predecessor, they may be combined.  */
1861       do
1862         {
1863           changed = false;
1864           iterations++;
1865
1866           if (dump_file)
1867             fprintf (dump_file,
1868                      "\n\ntry_optimize_cfg iteration %i\n\n",
1869                      iterations);
1870
1871           for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
1872             {
1873               basic_block c;
1874               edge s;
1875               bool changed_here = false;
1876
1877               /* Delete trivially dead basic blocks.  */
1878               if (EDGE_COUNT (b->preds) == 0)
1879                 {
1880                   c = b->prev_bb;
1881                   if (dump_file)
1882                     fprintf (dump_file, "Deleting block %i.\n",
1883                              b->index);
1884
1885                   delete_basic_block (b);
1886                   if (!(mode & CLEANUP_CFGLAYOUT))
1887                     changed = true;
1888                   /* Avoid trying to remove ENTRY_BLOCK_PTR.  */
1889                   b = (c == ENTRY_BLOCK_PTR ? c->next_bb : c);
1890                   continue;
1891                 }
1892
1893               /* Remove code labels no longer used.  */
1894               if (single_pred_p (b)
1895                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
1896                   && !(single_pred_edge (b)->flags & EDGE_COMPLEX)
1897                   && LABEL_P (BB_HEAD (b))
1898                   /* If the previous block ends with a branch to this
1899                      block, we can't delete the label.  Normally this
1900                      is a condjump that is yet to be simplified, but
1901                      if CASE_DROPS_THRU, this can be a tablejump with
1902                      some element going to the same place as the
1903                      default (fallthru).  */
1904                   && (single_pred (b) == ENTRY_BLOCK_PTR
1905                       || !JUMP_P (BB_END (single_pred (b)))
1906                       || ! label_is_jump_target_p (BB_HEAD (b),
1907                                                    BB_END (single_pred (b)))))
1908                 {
1909                   rtx label = BB_HEAD (b);
1910
1911                   delete_insn_chain (label, label, false);
1912                   /* If the case label is undeletable, move it after the
1913                      BASIC_BLOCK note.  */
1914                   if (NOTE_KIND (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
1915                     {
1916                       rtx bb_note = NEXT_INSN (BB_HEAD (b));
1917
1918                       reorder_insns_nobb (label, label, bb_note);
1919                       BB_HEAD (b) = bb_note;
1920                       if (BB_END (b) == bb_note)
1921                         BB_END (b) = label;
1922                     }
1923                   if (dump_file)
1924                     fprintf (dump_file, "Deleted label in block %i.\n",
1925                              b->index);
1926                 }
1927
1928               /* If we fall through an empty block, we can remove it.  */
1929               if (!(mode & CLEANUP_CFGLAYOUT)
1930                   && single_pred_p (b)
1931                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
1932                   && !LABEL_P (BB_HEAD (b))
1933                   && FORWARDER_BLOCK_P (b)
1934                   /* Note that forwarder_block_p true ensures that
1935                      there is a successor for this block.  */
1936                   && (single_succ_edge (b)->flags & EDGE_FALLTHRU)
1937                   && n_basic_blocks > NUM_FIXED_BLOCKS + 1)
1938                 {
1939                   if (dump_file)
1940                     fprintf (dump_file,
1941                              "Deleting fallthru block %i.\n",
1942                              b->index);
1943
1944                   c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
1945                   redirect_edge_succ_nodup (single_pred_edge (b),
1946                                             single_succ (b));
1947                   delete_basic_block (b);
1948                   changed = true;
1949                   b = c;
1950                 }
1951
1952               if (single_succ_p (b)
1953                   && (s = single_succ_edge (b))
1954                   && !(s->flags & EDGE_COMPLEX)
1955                   && (c = s->dest) != EXIT_BLOCK_PTR
1956                   && single_pred_p (c)
1957                   && b != c)
1958                 {
1959                   /* When not in cfg_layout mode use code aware of reordering
1960                      INSN.  This code possibly creates new basic blocks so it
1961                      does not fit merge_blocks interface and is kept here in
1962                      hope that it will become useless once more of compiler
1963                      is transformed to use cfg_layout mode.  */
1964
1965                   if ((mode & CLEANUP_CFGLAYOUT)
1966                       && can_merge_blocks_p (b, c))
1967                     {
1968                       merge_blocks (b, c);
1969                       update_forwarder_flag (b);
1970                       changed_here = true;
1971                     }
1972                   else if (!(mode & CLEANUP_CFGLAYOUT)
1973                            /* If the jump insn has side effects,
1974                               we can't kill the edge.  */
1975                            && (!JUMP_P (BB_END (b))
1976                                || (reload_completed
1977                                    ? simplejump_p (BB_END (b))
1978                                    : (onlyjump_p (BB_END (b))
1979                                       && !tablejump_p (BB_END (b),
1980                                                        NULL, NULL))))
1981                            && (next = merge_blocks_move (s, b, c, mode)))
1982                       {
1983                         b = next;
1984                         changed_here = true;
1985                       }
1986                 }
1987
1988               /* Simplify branch over branch.  */
1989               if ((mode & CLEANUP_EXPENSIVE)
1990                    && !(mode & CLEANUP_CFGLAYOUT)
1991                    && try_simplify_condjump (b))
1992                 changed_here = true;
1993
1994               /* If B has a single outgoing edge, but uses a
1995                  non-trivial jump instruction without side-effects, we
1996                  can either delete the jump entirely, or replace it
1997                  with a simple unconditional jump.  */
1998               if (single_succ_p (b)
1999                   && single_succ (b) != EXIT_BLOCK_PTR
2000                   && onlyjump_p (BB_END (b))
2001                   && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
2002                   && try_redirect_by_replacing_jump (single_succ_edge (b),
2003                                                      single_succ (b),
2004                                                      (mode & CLEANUP_CFGLAYOUT) != 0))
2005                 {
2006                   update_forwarder_flag (b);
2007                   changed_here = true;
2008                 }
2009
2010               /* Simplify branch to branch.  */
2011               if (try_forward_edges (mode, b))
2012                 changed_here = true;
2013
2014               /* Look for shared code between blocks.  */
2015               if ((mode & CLEANUP_CROSSJUMP)
2016                   && try_crossjump_bb (mode, b))
2017                 changed_here = true;
2018
2019               /* Don't get confused by the index shift caused by
2020                  deleting blocks.  */
2021               if (!changed_here)
2022                 b = b->next_bb;
2023               else
2024                 changed = true;
2025             }
2026
2027           if ((mode & CLEANUP_CROSSJUMP)
2028               && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
2029             changed = true;
2030
2031 #ifdef ENABLE_CHECKING
2032           if (changed)
2033             verify_flow_info ();
2034 #endif
2035
2036           changed_overall |= changed;
2037           first_pass = false;
2038         }
2039       while (changed);
2040     }
2041
2042   FOR_ALL_BB (b)
2043     b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK);
2044
2045   return changed_overall;
2046 }
2047 \f
2048 /* Delete all unreachable basic blocks.  */
2049
2050 bool
2051 delete_unreachable_blocks (void)
2052 {
2053   bool changed = false;
2054   basic_block b, next_bb;
2055
2056   find_unreachable_blocks ();
2057
2058   /* Delete all unreachable basic blocks.  */
2059
2060   for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
2061     {
2062       next_bb = b->next_bb;
2063
2064       if (!(b->flags & BB_REACHABLE))
2065         {
2066           delete_basic_block (b);
2067           changed = true;
2068         }
2069     }
2070
2071   if (changed)
2072     tidy_fallthru_edges ();
2073   return changed;
2074 }
2075
2076 /* Delete any jump tables never referenced.  We can't delete them at the
2077    time of removing tablejump insn as they are referenced by the preceding
2078    insns computing the destination, so we delay deleting and garbagecollect
2079    them once life information is computed.  */
2080 void
2081 delete_dead_jumptables (void)
2082 {
2083   basic_block bb;
2084
2085   /* A dead jump table does not belong to any basic block.  Scan insns
2086      between two adjacent basic blocks.  */
2087   FOR_EACH_BB (bb)
2088     {
2089       rtx insn, next;
2090
2091       for (insn = NEXT_INSN (BB_END (bb));
2092            insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
2093            insn = next)
2094         {
2095           next = NEXT_INSN (insn);
2096           if (LABEL_P (insn)
2097               && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
2098               && JUMP_P (next)
2099               && (GET_CODE (PATTERN (next)) == ADDR_VEC
2100                   || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
2101             {
2102               rtx label = insn, jump = next;
2103
2104               if (dump_file)
2105                 fprintf (dump_file, "Dead jumptable %i removed\n",
2106                          INSN_UID (insn));
2107
2108               next = NEXT_INSN (next);
2109               delete_insn (jump);
2110               delete_insn (label);
2111             }
2112         }
2113     }
2114 }
2115
2116 \f
2117 /* Tidy the CFG by deleting unreachable code and whatnot.  */
2118
2119 bool
2120 cleanup_cfg (int mode)
2121 {
2122   bool changed = false;
2123
2124   /* Set the cfglayout mode flag here.  We could update all the callers
2125      but that is just inconvenient, especially given that we eventually
2126      want to have cfglayout mode as the default.  */
2127   if (current_ir_type () == IR_RTL_CFGLAYOUT)
2128     mode |= CLEANUP_CFGLAYOUT;
2129
2130   timevar_push (TV_CLEANUP_CFG);
2131   if (delete_unreachable_blocks ())
2132     {
2133       changed = true;
2134       /* We've possibly created trivially dead code.  Cleanup it right
2135          now to introduce more opportunities for try_optimize_cfg.  */
2136       if (!(mode & (CLEANUP_NO_INSN_DEL))
2137           && !reload_completed)
2138         delete_trivially_dead_insns (get_insns (), max_reg_num ());
2139     }
2140
2141   compact_blocks ();
2142
2143   /* To tail-merge blocks ending in the same noreturn function (e.g.
2144      a call to abort) we have to insert fake edges to exit.  Do this
2145      here once.  The fake edges do not interfere with any other CFG
2146      cleanups.  */
2147   if (mode & CLEANUP_CROSSJUMP)
2148     add_noreturn_fake_exit_edges ();
2149
2150   if (!dbg_cnt (cfg_cleanup))
2151     return changed;
2152
2153   while (try_optimize_cfg (mode))
2154     {
2155       delete_unreachable_blocks (), changed = true;
2156       if (!(mode & CLEANUP_NO_INSN_DEL))
2157         {
2158           /* Try to remove some trivially dead insns when doing an expensive
2159              cleanup.  But delete_trivially_dead_insns doesn't work after
2160              reload (it only handles pseudos) and run_fast_dce is too costly
2161              to run in every iteration.
2162
2163              For effective cross jumping, we really want to run a fast DCE to
2164              clean up any dead conditions, or they get in the way of performing
2165              useful tail merges.
2166
2167              Other transformations in cleanup_cfg are not so sensitive to dead
2168              code, so delete_trivially_dead_insns or even doing nothing at all
2169              is good enough.  */
2170           if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
2171               && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2172             break;
2173           else if ((mode & CLEANUP_CROSSJUMP)
2174                    && crossjumps_occured)
2175             run_fast_dce ();
2176         }
2177       else
2178         break;
2179     }
2180
2181   if (mode & CLEANUP_CROSSJUMP)
2182     remove_fake_exit_edges ();
2183
2184   /* Don't call delete_dead_jumptables in cfglayout mode, because
2185      that function assumes that jump tables are in the insns stream.
2186      But we also don't _have_ to delete dead jumptables in cfglayout
2187      mode because we shouldn't even be looking at things that are
2188      not in a basic block.  Dead jumptables are cleaned up when
2189      going out of cfglayout mode.  */
2190   if (!(mode & CLEANUP_CFGLAYOUT))
2191     delete_dead_jumptables ();
2192
2193   timevar_pop (TV_CLEANUP_CFG);
2194
2195   return changed;
2196 }
2197 \f
2198 static unsigned int
2199 rest_of_handle_jump (void)
2200 {
2201   delete_unreachable_blocks ();
2202
2203   if (crtl->tail_call_emit)
2204     fixup_tail_calls ();
2205   return 0;
2206 }
2207
2208 struct rtl_opt_pass pass_jump =
2209 {
2210  {
2211   RTL_PASS,
2212   "sibling",                            /* name */
2213   NULL,                                 /* gate */
2214   rest_of_handle_jump,                  /* execute */
2215   NULL,                                 /* sub */
2216   NULL,                                 /* next */
2217   0,                                    /* static_pass_number */
2218   TV_JUMP,                              /* tv_id */
2219   0,                                    /* properties_required */
2220   0,                                    /* properties_provided */
2221   0,                                    /* properties_destroyed */
2222   TODO_ggc_collect,                     /* todo_flags_start */
2223   TODO_verify_flow,                     /* todo_flags_finish */
2224  }
2225 };
2226
2227
2228 static unsigned int
2229 rest_of_handle_jump2 (void)
2230 {
2231   delete_trivially_dead_insns (get_insns (), max_reg_num ());
2232   if (dump_file)
2233     dump_flow_info (dump_file, dump_flags);
2234   cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
2235                | (flag_thread_jumps ? CLEANUP_THREADING : 0));
2236   return 0;
2237 }
2238
2239
2240 struct rtl_opt_pass pass_jump2 =
2241 {
2242  {
2243   RTL_PASS,
2244   "jump",                               /* name */
2245   NULL,                                 /* gate */
2246   rest_of_handle_jump2,                 /* execute */
2247   NULL,                                 /* sub */
2248   NULL,                                 /* next */
2249   0,                                    /* static_pass_number */
2250   TV_JUMP,                              /* tv_id */
2251   0,                                    /* properties_required */
2252   0,                                    /* properties_provided */
2253   0,                                    /* properties_destroyed */
2254   TODO_ggc_collect,                     /* todo_flags_start */
2255   TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */
2256  }
2257 };
2258
2259