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   if (NOTE_INSN_BASIC_BLOCK_P (newpos1))
1676     newpos1 = NEXT_INSN (newpos1);
1677
1678   redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
1679   to_remove = single_succ (redirect_from);
1680
1681   redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
1682   delete_basic_block (to_remove);
1683
1684   update_forwarder_flag (redirect_from);
1685   if (redirect_to != src2)
1686     update_forwarder_flag (src2);
1687
1688   return true;
1689 }
1690
1691 /* Search the predecessors of BB for common insn sequences.  When found,
1692    share code between them by redirecting control flow.  Return true if
1693    any changes made.  */
1694
1695 static bool
1696 try_crossjump_bb (int mode, basic_block bb)
1697 {
1698   edge e, e2, fallthru;
1699   bool changed;
1700   unsigned max, ix, ix2;
1701   basic_block ev, ev2;
1702   edge_iterator ei;
1703
1704   /* Nothing to do if there is not at least two incoming edges.  */
1705   if (EDGE_COUNT (bb->preds) < 2)
1706     return false;
1707
1708   /* Don't crossjump if this block ends in a computed jump,
1709      unless we are optimizing for size.  */
1710   if (optimize_bb_for_size_p (bb)
1711       && bb != EXIT_BLOCK_PTR
1712       && computed_jump_p (BB_END (bb)))
1713     return false;
1714
1715   /* If we are partitioning hot/cold basic blocks, we don't want to
1716      mess up unconditional or indirect jumps that cross between hot
1717      and cold sections.
1718
1719      Basic block partitioning may result in some jumps that appear to
1720      be optimizable (or blocks that appear to be mergeable), but which really
1721      must be left untouched (they are required to make it safely across
1722      partition boundaries).  See the comments at the top of
1723      bb-reorder.c:partition_hot_cold_basic_blocks for complete details.  */
1724
1725   if (BB_PARTITION (EDGE_PRED (bb, 0)->src) !=
1726                                         BB_PARTITION (EDGE_PRED (bb, 1)->src)
1727       || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING))
1728     return false;
1729
1730   /* It is always cheapest to redirect a block that ends in a branch to
1731      a block that falls through into BB, as that adds no branches to the
1732      program.  We'll try that combination first.  */
1733   fallthru = NULL;
1734   max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
1735
1736   if (EDGE_COUNT (bb->preds) > max)
1737     return false;
1738
1739   FOR_EACH_EDGE (e, ei, bb->preds)
1740     {
1741       if (e->flags & EDGE_FALLTHRU)
1742         {
1743           fallthru = e;
1744           break;
1745         }
1746     }
1747
1748   changed = false;
1749   for (ix = 0, ev = bb; ix < EDGE_COUNT (ev->preds); )
1750     {
1751       e = EDGE_PRED (ev, ix);
1752       ix++;
1753
1754       /* As noted above, first try with the fallthru predecessor (or, a
1755          fallthru predecessor if we are in cfglayout mode).  */
1756       if (fallthru)
1757         {
1758           /* Don't combine the fallthru edge into anything else.
1759              If there is a match, we'll do it the other way around.  */
1760           if (e == fallthru)
1761             continue;
1762           /* If nothing changed since the last attempt, there is nothing
1763              we can do.  */
1764           if (!first_pass
1765               && (!(df_get_bb_dirty (e->src))
1766                   && !(df_get_bb_dirty (fallthru->src))))
1767             continue;
1768
1769           if (try_crossjump_to_edge (mode, e, fallthru))
1770             {
1771               changed = true;
1772               ix = 0;
1773               ev = bb;
1774               continue;
1775             }
1776         }
1777
1778       /* Non-obvious work limiting check: Recognize that we're going
1779          to call try_crossjump_bb on every basic block.  So if we have
1780          two blocks with lots of outgoing edges (a switch) and they
1781          share lots of common destinations, then we would do the
1782          cross-jump check once for each common destination.
1783
1784          Now, if the blocks actually are cross-jump candidates, then
1785          all of their destinations will be shared.  Which means that
1786          we only need check them for cross-jump candidacy once.  We
1787          can eliminate redundant checks of crossjump(A,B) by arbitrarily
1788          choosing to do the check from the block for which the edge
1789          in question is the first successor of A.  */
1790       if (EDGE_SUCC (e->src, 0) != e)
1791         continue;
1792
1793       for (ix2 = 0, ev2 = bb; ix2 < EDGE_COUNT (ev2->preds); )
1794         {
1795           e2 = EDGE_PRED (ev2, ix2);
1796           ix2++;
1797
1798           if (e2 == e)
1799             continue;
1800
1801           /* We've already checked the fallthru edge above.  */
1802           if (e2 == fallthru)
1803             continue;
1804
1805           /* The "first successor" check above only prevents multiple
1806              checks of crossjump(A,B).  In order to prevent redundant
1807              checks of crossjump(B,A), require that A be the block
1808              with the lowest index.  */
1809           if (e->src->index > e2->src->index)
1810             continue;
1811
1812           /* If nothing changed since the last attempt, there is nothing
1813              we can do.  */
1814           if (!first_pass
1815               && (!(df_get_bb_dirty (e->src))
1816                   && !(df_get_bb_dirty (e2->src))))
1817             continue;
1818
1819           if (try_crossjump_to_edge (mode, e, e2))
1820             {
1821               changed = true;
1822               ev2 = bb;
1823               ix = 0;
1824               break;
1825             }
1826         }
1827     }
1828
1829   if (changed)
1830     crossjumps_occured = true;
1831
1832   return changed;
1833 }
1834
1835 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1836    instructions etc.  Return nonzero if changes were made.  */
1837
1838 static bool
1839 try_optimize_cfg (int mode)
1840 {
1841   bool changed_overall = false;
1842   bool changed;
1843   int iterations = 0;
1844   basic_block bb, b, next;
1845
1846   if (mode & (CLEANUP_CROSSJUMP | CLEANUP_THREADING))
1847     clear_bb_flags ();
1848
1849   crossjumps_occured = false;
1850
1851   FOR_EACH_BB (bb)
1852     update_forwarder_flag (bb);
1853
1854   if (! targetm.cannot_modify_jumps_p ())
1855     {
1856       first_pass = true;
1857       /* Attempt to merge blocks as made possible by edge removal.  If
1858          a block has only one successor, and the successor has only
1859          one predecessor, they may be combined.  */
1860       do
1861         {
1862           changed = false;
1863           iterations++;
1864
1865           if (dump_file)
1866             fprintf (dump_file,
1867                      "\n\ntry_optimize_cfg iteration %i\n\n",
1868                      iterations);
1869
1870           for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
1871             {
1872               basic_block c;
1873               edge s;
1874               bool changed_here = false;
1875
1876               /* Delete trivially dead basic blocks.  This is either
1877                  blocks with no predecessors, or empty blocks with no
1878                  successors.  Empty blocks may result from expanding
1879                  __builtin_unreachable ().  */
1880               if (EDGE_COUNT (b->preds) == 0
1881                   || (EDGE_COUNT (b->succs) == 0 && BB_HEAD (b) == BB_END (b)))
1882                 {
1883                   c = b->prev_bb;
1884                   if (dump_file)
1885                     fprintf (dump_file, "Deleting block %i.\n",
1886                              b->index);
1887
1888                   delete_basic_block (b);
1889                   if (!(mode & CLEANUP_CFGLAYOUT))
1890                     changed = true;
1891                   /* Avoid trying to remove ENTRY_BLOCK_PTR.  */
1892                   b = (c == ENTRY_BLOCK_PTR ? c->next_bb : c);
1893                   continue;
1894                 }
1895
1896               /* Remove code labels no longer used.  */
1897               if (single_pred_p (b)
1898                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
1899                   && !(single_pred_edge (b)->flags & EDGE_COMPLEX)
1900                   && LABEL_P (BB_HEAD (b))
1901                   /* If the previous block ends with a branch to this
1902                      block, we can't delete the label.  Normally this
1903                      is a condjump that is yet to be simplified, but
1904                      if CASE_DROPS_THRU, this can be a tablejump with
1905                      some element going to the same place as the
1906                      default (fallthru).  */
1907                   && (single_pred (b) == ENTRY_BLOCK_PTR
1908                       || !JUMP_P (BB_END (single_pred (b)))
1909                       || ! label_is_jump_target_p (BB_HEAD (b),
1910                                                    BB_END (single_pred (b)))))
1911                 {
1912                   rtx label = BB_HEAD (b);
1913
1914                   delete_insn_chain (label, label, false);
1915                   /* If the case label is undeletable, move it after the
1916                      BASIC_BLOCK note.  */
1917                   if (NOTE_KIND (BB_HEAD (b)) == NOTE_INSN_DELETED_LABEL)
1918                     {
1919                       rtx bb_note = NEXT_INSN (BB_HEAD (b));
1920
1921                       reorder_insns_nobb (label, label, bb_note);
1922                       BB_HEAD (b) = bb_note;
1923                       if (BB_END (b) == bb_note)
1924                         BB_END (b) = label;
1925                     }
1926                   if (dump_file)
1927                     fprintf (dump_file, "Deleted label in block %i.\n",
1928                              b->index);
1929                 }
1930
1931               /* If we fall through an empty block, we can remove it.  */
1932               if (!(mode & CLEANUP_CFGLAYOUT)
1933                   && single_pred_p (b)
1934                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
1935                   && !LABEL_P (BB_HEAD (b))
1936                   && FORWARDER_BLOCK_P (b)
1937                   /* Note that forwarder_block_p true ensures that
1938                      there is a successor for this block.  */
1939                   && (single_succ_edge (b)->flags & EDGE_FALLTHRU)
1940                   && n_basic_blocks > NUM_FIXED_BLOCKS + 1)
1941                 {
1942                   if (dump_file)
1943                     fprintf (dump_file,
1944                              "Deleting fallthru block %i.\n",
1945                              b->index);
1946
1947                   c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
1948                   redirect_edge_succ_nodup (single_pred_edge (b),
1949                                             single_succ (b));
1950                   delete_basic_block (b);
1951                   changed = true;
1952                   b = c;
1953                 }
1954
1955               if (single_succ_p (b)
1956                   && (s = single_succ_edge (b))
1957                   && !(s->flags & EDGE_COMPLEX)
1958                   && (c = s->dest) != EXIT_BLOCK_PTR
1959                   && single_pred_p (c)
1960                   && b != c)
1961                 {
1962                   /* When not in cfg_layout mode use code aware of reordering
1963                      INSN.  This code possibly creates new basic blocks so it
1964                      does not fit merge_blocks interface and is kept here in
1965                      hope that it will become useless once more of compiler
1966                      is transformed to use cfg_layout mode.  */
1967
1968                   if ((mode & CLEANUP_CFGLAYOUT)
1969                       && can_merge_blocks_p (b, c))
1970                     {
1971                       merge_blocks (b, c);
1972                       update_forwarder_flag (b);
1973                       changed_here = true;
1974                     }
1975                   else if (!(mode & CLEANUP_CFGLAYOUT)
1976                            /* If the jump insn has side effects,
1977                               we can't kill the edge.  */
1978                            && (!JUMP_P (BB_END (b))
1979                                || (reload_completed
1980                                    ? simplejump_p (BB_END (b))
1981                                    : (onlyjump_p (BB_END (b))
1982                                       && !tablejump_p (BB_END (b),
1983                                                        NULL, NULL))))
1984                            && (next = merge_blocks_move (s, b, c, mode)))
1985                       {
1986                         b = next;
1987                         changed_here = true;
1988                       }
1989                 }
1990
1991               /* Simplify branch over branch.  */
1992               if ((mode & CLEANUP_EXPENSIVE)
1993                    && !(mode & CLEANUP_CFGLAYOUT)
1994                    && try_simplify_condjump (b))
1995                 changed_here = true;
1996
1997               /* If B has a single outgoing edge, but uses a
1998                  non-trivial jump instruction without side-effects, we
1999                  can either delete the jump entirely, or replace it
2000                  with a simple unconditional jump.  */
2001               if (single_succ_p (b)
2002                   && single_succ (b) != EXIT_BLOCK_PTR
2003                   && onlyjump_p (BB_END (b))
2004                   && !find_reg_note (BB_END (b), REG_CROSSING_JUMP, NULL_RTX)
2005                   && try_redirect_by_replacing_jump (single_succ_edge (b),
2006                                                      single_succ (b),
2007                                                      (mode & CLEANUP_CFGLAYOUT) != 0))
2008                 {
2009                   update_forwarder_flag (b);
2010                   changed_here = true;
2011                 }
2012
2013               /* Simplify branch to branch.  */
2014               if (try_forward_edges (mode, b))
2015                 changed_here = true;
2016
2017               /* Look for shared code between blocks.  */
2018               if ((mode & CLEANUP_CROSSJUMP)
2019                   && try_crossjump_bb (mode, b))
2020                 changed_here = true;
2021
2022               /* Don't get confused by the index shift caused by
2023                  deleting blocks.  */
2024               if (!changed_here)
2025                 b = b->next_bb;
2026               else
2027                 changed = true;
2028             }
2029
2030           if ((mode & CLEANUP_CROSSJUMP)
2031               && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
2032             changed = true;
2033
2034 #ifdef ENABLE_CHECKING
2035           if (changed)
2036             verify_flow_info ();
2037 #endif
2038
2039           changed_overall |= changed;
2040           first_pass = false;
2041         }
2042       while (changed);
2043     }
2044
2045   FOR_ALL_BB (b)
2046     b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK);
2047
2048   return changed_overall;
2049 }
2050 \f
2051 /* Delete all unreachable basic blocks.  */
2052
2053 bool
2054 delete_unreachable_blocks (void)
2055 {
2056   bool changed = false;
2057   basic_block b, next_bb;
2058
2059   find_unreachable_blocks ();
2060
2061   /* Delete all unreachable basic blocks.  */
2062
2063   for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
2064     {
2065       next_bb = b->next_bb;
2066
2067       if (!(b->flags & BB_REACHABLE))
2068         {
2069           delete_basic_block (b);
2070           changed = true;
2071         }
2072     }
2073
2074   if (changed)
2075     tidy_fallthru_edges ();
2076   return changed;
2077 }
2078
2079 /* Delete any jump tables never referenced.  We can't delete them at the
2080    time of removing tablejump insn as they are referenced by the preceding
2081    insns computing the destination, so we delay deleting and garbagecollect
2082    them once life information is computed.  */
2083 void
2084 delete_dead_jumptables (void)
2085 {
2086   basic_block bb;
2087
2088   /* A dead jump table does not belong to any basic block.  Scan insns
2089      between two adjacent basic blocks.  */
2090   FOR_EACH_BB (bb)
2091     {
2092       rtx insn, next;
2093
2094       for (insn = NEXT_INSN (BB_END (bb));
2095            insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
2096            insn = next)
2097         {
2098           next = NEXT_INSN (insn);
2099           if (LABEL_P (insn)
2100               && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
2101               && JUMP_P (next)
2102               && (GET_CODE (PATTERN (next)) == ADDR_VEC
2103                   || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
2104             {
2105               rtx label = insn, jump = next;
2106
2107               if (dump_file)
2108                 fprintf (dump_file, "Dead jumptable %i removed\n",
2109                          INSN_UID (insn));
2110
2111               next = NEXT_INSN (next);
2112               delete_insn (jump);
2113               delete_insn (label);
2114             }
2115         }
2116     }
2117 }
2118
2119 \f
2120 /* Tidy the CFG by deleting unreachable code and whatnot.  */
2121
2122 bool
2123 cleanup_cfg (int mode)
2124 {
2125   bool changed = false;
2126
2127   /* Set the cfglayout mode flag here.  We could update all the callers
2128      but that is just inconvenient, especially given that we eventually
2129      want to have cfglayout mode as the default.  */
2130   if (current_ir_type () == IR_RTL_CFGLAYOUT)
2131     mode |= CLEANUP_CFGLAYOUT;
2132
2133   timevar_push (TV_CLEANUP_CFG);
2134   if (delete_unreachable_blocks ())
2135     {
2136       changed = true;
2137       /* We've possibly created trivially dead code.  Cleanup it right
2138          now to introduce more opportunities for try_optimize_cfg.  */
2139       if (!(mode & (CLEANUP_NO_INSN_DEL))
2140           && !reload_completed)
2141         delete_trivially_dead_insns (get_insns (), max_reg_num ());
2142     }
2143
2144   compact_blocks ();
2145
2146   /* To tail-merge blocks ending in the same noreturn function (e.g.
2147      a call to abort) we have to insert fake edges to exit.  Do this
2148      here once.  The fake edges do not interfere with any other CFG
2149      cleanups.  */
2150   if (mode & CLEANUP_CROSSJUMP)
2151     add_noreturn_fake_exit_edges ();
2152
2153   if (!dbg_cnt (cfg_cleanup))
2154     return changed;
2155
2156   while (try_optimize_cfg (mode))
2157     {
2158       delete_unreachable_blocks (), changed = true;
2159       if (!(mode & CLEANUP_NO_INSN_DEL))
2160         {
2161           /* Try to remove some trivially dead insns when doing an expensive
2162              cleanup.  But delete_trivially_dead_insns doesn't work after
2163              reload (it only handles pseudos) and run_fast_dce is too costly
2164              to run in every iteration.
2165
2166              For effective cross jumping, we really want to run a fast DCE to
2167              clean up any dead conditions, or they get in the way of performing
2168              useful tail merges.
2169
2170              Other transformations in cleanup_cfg are not so sensitive to dead
2171              code, so delete_trivially_dead_insns or even doing nothing at all
2172              is good enough.  */
2173           if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
2174               && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
2175             break;
2176           else if ((mode & CLEANUP_CROSSJUMP)
2177                    && crossjumps_occured)
2178             run_fast_dce ();
2179         }
2180       else
2181         break;
2182     }
2183
2184   if (mode & CLEANUP_CROSSJUMP)
2185     remove_fake_exit_edges ();
2186
2187   /* Don't call delete_dead_jumptables in cfglayout mode, because
2188      that function assumes that jump tables are in the insns stream.
2189      But we also don't _have_ to delete dead jumptables in cfglayout
2190      mode because we shouldn't even be looking at things that are
2191      not in a basic block.  Dead jumptables are cleaned up when
2192      going out of cfglayout mode.  */
2193   if (!(mode & CLEANUP_CFGLAYOUT))
2194     delete_dead_jumptables ();
2195
2196   timevar_pop (TV_CLEANUP_CFG);
2197
2198   return changed;
2199 }
2200 \f
2201 static unsigned int
2202 rest_of_handle_jump (void)
2203 {
2204   if (crtl->tail_call_emit)
2205     fixup_tail_calls ();
2206   return 0;
2207 }
2208
2209 struct rtl_opt_pass pass_jump =
2210 {
2211  {
2212   RTL_PASS,
2213   "sibling",                            /* name */
2214   NULL,                                 /* gate */
2215   rest_of_handle_jump,                  /* execute */
2216   NULL,                                 /* sub */
2217   NULL,                                 /* next */
2218   0,                                    /* static_pass_number */
2219   TV_JUMP,                              /* tv_id */
2220   0,                                    /* properties_required */
2221   0,                                    /* properties_provided */
2222   0,                                    /* properties_destroyed */
2223   TODO_ggc_collect,                     /* todo_flags_start */
2224   TODO_verify_flow,                     /* todo_flags_finish */
2225  }
2226 };
2227
2228
2229 static unsigned int
2230 rest_of_handle_jump2 (void)
2231 {
2232   delete_trivially_dead_insns (get_insns (), max_reg_num ());
2233   if (dump_file)
2234     dump_flow_info (dump_file, dump_flags);
2235   cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
2236                | (flag_thread_jumps ? CLEANUP_THREADING : 0));
2237   return 0;
2238 }
2239
2240
2241 struct rtl_opt_pass pass_jump2 =
2242 {
2243  {
2244   RTL_PASS,
2245   "jump",                               /* name */
2246   NULL,                                 /* gate */
2247   rest_of_handle_jump2,                 /* execute */
2248   NULL,                                 /* sub */
2249   NULL,                                 /* next */
2250   0,                                    /* static_pass_number */
2251   TV_JUMP,                              /* tv_id */
2252   0,                                    /* properties_required */
2253   0,                                    /* properties_provided */
2254   0,                                    /* properties_destroyed */
2255   TODO_ggc_collect,                     /* todo_flags_start */
2256   TODO_dump_func | TODO_verify_rtl_sharing,/* todo_flags_finish */
2257  }
2258 };
2259
2260