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 Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This file contains optimizer of the control flow.  The main entrypoint is
  23    cleanup_cfg.  Following optimizations are performed:
  24
  25    - Unreachable blocks removal
  26    - Edge forwarding (edge to the forwarder block is forwarded to it's
  27      successor.  Simplification of the branch instruction is performed by
  28      underlying infrastructure so branch can be converted to simplejump or
  29      eliminated).
  30    - Cross jumping (tail merging)
  31    - Conditional jump-around-simplejump simplification
  32    - Basic block merging.  */
  33
  34 #include "config.h"
  35 #include "system.h"
  36 #include "coretypes.h"
  37 #include "tm.h"
  38 #include "rtl.h"
  39 #include "hard-reg-set.h"
  40 #include "basic-block.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
  52 /* cleanup_cfg maintains following flags for each basic block.  */
  53
  54 enum bb_flags
  55 {
  56     /* Set if BB is the forwarder block to avoid too many
  57        forwarder_block_p calls.  */
  58     BB_FORWARDER_BLOCK = 1,
  59     BB_NONTHREADABLE_BLOCK = 2
  60 };
  61
  62 #define BB_FLAGS(BB) (enum bb_flags) (BB)->aux
  63 #define BB_SET_FLAG(BB, FLAG) \
  64   (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux | (FLAG))
  65 #define BB_CLEAR_FLAG(BB, FLAG) \
  66   (BB)->aux = (void *) (long) ((enum bb_flags) (BB)->aux & ~(FLAG))
  67
  68 #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
  69
  70 static bool try_crossjump_to_edge       PARAMS ((int, edge, edge));
  71 static bool try_crossjump_bb            PARAMS ((int, basic_block));
  72 static bool outgoing_edges_match        PARAMS ((int,
  73                                                  basic_block, basic_block));
  74 static int flow_find_cross_jump         PARAMS ((int, basic_block, basic_block,
  75                                                  rtx *, rtx *));
  76 static bool insns_match_p               PARAMS ((int, rtx, rtx));
  77
  78 static bool label_is_jump_target_p      PARAMS ((rtx, rtx));
  79 static bool tail_recursion_label_p      PARAMS ((rtx));
  80 static void merge_blocks_move_predecessor_nojumps PARAMS ((basic_block,
  81                                                           basic_block));
  82 static void merge_blocks_move_successor_nojumps PARAMS ((basic_block,
  83                                                         basic_block));
  84 static bool merge_blocks                PARAMS ((edge,basic_block,basic_block,
  85                                                  int));
  86 static bool try_optimize_cfg            PARAMS ((int));
  87 static bool try_simplify_condjump       PARAMS ((basic_block));
  88 static bool try_forward_edges           PARAMS ((int, basic_block));
  89 static edge thread_jump                 PARAMS ((int, edge, basic_block));
  90 static bool mark_effect                 PARAMS ((rtx, bitmap));
  91 static void notice_new_block            PARAMS ((basic_block));
  92 static void update_forwarder_flag       PARAMS ((basic_block));
  93 static int mentions_nonequal_regs       PARAMS ((rtx *, void *));
  94 \f
  95 /* Set flags for newly created block.  */
  96
  97 static void
  98 notice_new_block (bb)
  99      basic_block bb;
 100 {
 101   if (!bb)
 102     return;
 103
 104   if (forwarder_block_p (bb))
 105     BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
 106 }
 107
 108 /* Recompute forwarder flag after block has been modified.  */
 109
 110 static void
 111 update_forwarder_flag (bb)
 112      basic_block bb;
 113 {
 114   if (forwarder_block_p (bb))
 115     BB_SET_FLAG (bb, BB_FORWARDER_BLOCK);
 116   else
 117     BB_CLEAR_FLAG (bb, BB_FORWARDER_BLOCK);
 118 }
 119 \f
 120 /* Simplify a conditional jump around an unconditional jump.
 121    Return true if something changed.  */
 122
 123 static bool
 124 try_simplify_condjump (cbranch_block)
 125      basic_block cbranch_block;
 126 {
 127   basic_block jump_block, jump_dest_block, cbranch_dest_block;
 128   edge cbranch_jump_edge, cbranch_fallthru_edge;
 129   rtx cbranch_insn;
 130
 131   /* Verify that there are exactly two successors.  */
 132   if (!cbranch_block->succ
 133       || !cbranch_block->succ->succ_next
 134       || cbranch_block->succ->succ_next->succ_next)
 135     return false;
 136
 137   /* Verify that we've got a normal conditional branch at the end
 138      of the block.  */
 139   cbranch_insn = cbranch_block->end;
 140   if (!any_condjump_p (cbranch_insn))
 141     return false;
 142
 143   cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
 144   cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
 145
 146   /* The next block must not have multiple predecessors, must not
 147      be the last block in the function, and must contain just the
 148      unconditional jump.  */
 149   jump_block = cbranch_fallthru_edge->dest;
 150   if (jump_block->pred->pred_next
 151       || jump_block->next_bb == EXIT_BLOCK_PTR
 152       || !FORWARDER_BLOCK_P (jump_block))
 153     return false;
 154   jump_dest_block = jump_block->succ->dest;
 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 (!can_fallthru (jump_block, cbranch_dest_block))
 161     return false;
 162
 163   /* Invert the conditional branch.  */
 164   if (!invert_jump (cbranch_insn, block_label (jump_dest_block), 0))
 165     return false;
 166
 167   if (rtl_dump_file)
 168     fprintf (rtl_dump_file, "Simplifying condjump %i around jump %i\n",
 169              INSN_UID (cbranch_insn), INSN_UID (jump_block->end));
 170
 171   /* Success.  Update the CFG to match.  Note that after this point
 172      the edge variable names appear backwards; the redirection is done
 173      this way to preserve edge profile data.  */
 174   cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
 175                                                 cbranch_dest_block);
 176   cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
 177                                                     jump_dest_block);
 178   cbranch_jump_edge->flags |= EDGE_FALLTHRU;
 179   cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
 180   update_br_prob_note (cbranch_block);
 181
 182   /* Delete the block with the unconditional jump, and clean up the mess.  */
 183   flow_delete_block (jump_block);
 184   tidy_fallthru_edge (cbranch_jump_edge, cbranch_block, cbranch_dest_block);
 185
 186   return true;
 187 }
 188 \f
 189 /* Attempt to prove that operation is NOOP using CSElib or mark the effect
 190    on register.  Used by jump threading.  */
 191
 192 static bool
 193 mark_effect (exp, nonequal)
 194      rtx exp;
 195      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 an register set in regset DATA.
 242    Called via for_each_rtx.  */
 243 static int
 244 mentions_nonequal_regs (x, data)
 245      rtx *x;
 246      void *data;
 247 {
 248   regset nonequal = (regset) data;
 249   if (REG_P (*x))
 250     {
 251       int regno;
 252
 253       regno = REGNO (*x);
 254       if (REGNO_REG_SET_P (nonequal, regno))
 255         return 1;
 256       if (regno < FIRST_PSEUDO_REGISTER)
 257         {
 258           int n = HARD_REGNO_NREGS (regno, GET_MODE (*x));
 259           while (--n > 0)
 260             if (REGNO_REG_SET_P (nonequal, regno + n))
 261               return 1;
 262         }
 263     }
 264   return 0;
 265 }
 266 /* Attempt to prove that the basic block B will have no side effects and
 267    always continues in the same edge if reached via E.  Return the edge
 268    if exist, NULL otherwise.  */
 269
 270 static edge
 271 thread_jump (mode, e, b)
 272      int mode;
 273      edge e;
 274      basic_block b;
 275 {
 276   rtx set1, set2, cond1, cond2, insn;
 277   enum rtx_code code1, code2, reversed_code2;
 278   bool reverse1 = false;
 279   int i;
 280   regset nonequal;
 281   bool failed = false;
 282
 283   if (BB_FLAGS (b) & BB_NONTHREADABLE_BLOCK)
 284     return NULL;
 285
 286   /* At the moment, we do handle only conditional jumps, but later we may
 287      want to extend this code to tablejumps and others.  */
 288   if (!e->src->succ->succ_next || e->src->succ->succ_next->succ_next)
 289     return NULL;
 290   if (!b->succ || !b->succ->succ_next || b->succ->succ_next->succ_next)
 291     {
 292       BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
 293       return NULL;
 294     }
 295
 296   /* Second branch must end with onlyjump, as we will eliminate the jump.  */
 297   if (!any_condjump_p (e->src->end))
 298     return NULL;
 299
 300   if (!any_condjump_p (b->end) || !onlyjump_p (b->end))
 301     {
 302       BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
 303       return NULL;
 304     }
 305
 306   set1 = pc_set (e->src->end);
 307   set2 = pc_set (b->end);
 308   if (((e->flags & EDGE_FALLTHRU) != 0)
 309       != (XEXP (SET_SRC (set1), 1) == pc_rtx))
 310     reverse1 = true;
 311
 312   cond1 = XEXP (SET_SRC (set1), 0);
 313   cond2 = XEXP (SET_SRC (set2), 0);
 314   if (reverse1)
 315     code1 = reversed_comparison_code (cond1, e->src->end);
 316   else
 317     code1 = GET_CODE (cond1);
 318
 319   code2 = GET_CODE (cond2);
 320   reversed_code2 = reversed_comparison_code (cond2, b->end);
 321
 322   if (!comparison_dominates_p (code1, code2)
 323       && !comparison_dominates_p (code1, reversed_code2))
 324     return NULL;
 325
 326   /* Ensure that the comparison operators are equivalent.
 327      ??? This is far too pessimistic.  We should allow swapped operands,
 328      different CCmodes, or for example comparisons for interval, that
 329      dominate even when operands are not equivalent.  */
 330   if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
 331       || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
 332     return NULL;
 333
 334   /* Short circuit cases where block B contains some side effects, as we can't
 335      safely bypass it.  */
 336   for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end);
 337        insn = NEXT_INSN (insn))
 338     if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
 339       {
 340         BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
 341         return NULL;
 342       }
 343
 344   cselib_init ();
 345
 346   /* First process all values computed in the source basic block.  */
 347   for (insn = NEXT_INSN (e->src->head); insn != NEXT_INSN (e->src->end);
 348        insn = NEXT_INSN (insn))
 349     if (INSN_P (insn))
 350       cselib_process_insn (insn);
 351
 352   nonequal = BITMAP_XMALLOC();
 353   CLEAR_REG_SET (nonequal);
 354
 355   /* Now assume that we've continued by the edge E to B and continue
 356      processing as if it were same basic block.
 357      Our goal is to prove that whole block is an NOOP.  */
 358
 359   for (insn = NEXT_INSN (b->head); insn != NEXT_INSN (b->end) && !failed;
 360        insn = NEXT_INSN (insn))
 361     {
 362       if (INSN_P (insn))
 363         {
 364           rtx pat = PATTERN (insn);
 365
 366           if (GET_CODE (pat) == PARALLEL)
 367             {
 368               for (i = 0; i < XVECLEN (pat, 0); i++)
 369                 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
 370             }
 371           else
 372             failed |= mark_effect (pat, nonequal);
 373         }
 374
 375       cselib_process_insn (insn);
 376     }
 377
 378   /* Later we should clear nonequal of dead registers.  So far we don't
 379      have life information in cfg_cleanup.  */
 380   if (failed)
 381     {
 382       BB_SET_FLAG (b, BB_NONTHREADABLE_BLOCK);
 383       goto failed_exit;
 384     }
 385
 386   /* cond2 must not mention any register that is not equal to the
 387      former block.  */
 388   if (for_each_rtx (&cond2, mentions_nonequal_regs, nonequal))
 389     goto failed_exit;
 390
 391   /* In case liveness information is available, we need to prove equivalence
 392      only of the live values.  */
 393   if (mode & CLEANUP_UPDATE_LIFE)
 394     AND_REG_SET (nonequal, b->global_live_at_end);
 395
 396   EXECUTE_IF_SET_IN_REG_SET (nonequal, 0, i, goto failed_exit;);
 397
 398   BITMAP_XFREE (nonequal);
 399   cselib_finish ();
 400   if ((comparison_dominates_p (code1, code2) != 0)
 401       != (XEXP (SET_SRC (set2), 1) == pc_rtx))
 402     return BRANCH_EDGE (b);
 403   else
 404     return FALLTHRU_EDGE (b);
 405
 406 failed_exit:
 407   BITMAP_XFREE (nonequal);
 408   cselib_finish ();
 409   return NULL;
 410 }
 411 \f
 412 /* Attempt to forward edges leaving basic block B.
 413    Return true if successful.  */
 414
 415 static bool
 416 try_forward_edges (mode, b)
 417      basic_block b;
 418      int mode;
 419 {
 420   bool changed = false;
 421   edge e, next, *threaded_edges = NULL;
 422
 423   for (e = b->succ; e; e = next)
 424     {
 425       basic_block target, first;
 426       int counter;
 427       bool threaded = false;
 428       int nthreaded_edges = 0;
 429
 430       next = e->succ_next;
 431
 432       /* Skip complex edges because we don't know how to update them.
 433
 434          Still handle fallthru edges, as we can succeed to forward fallthru
 435          edge to the same place as the branch edge of conditional branch
 436          and turn conditional branch to an unconditional branch.  */
 437       if (e->flags & EDGE_COMPLEX)
 438         continue;
 439
 440       target = first = e->dest;
 441       counter = 0;
 442
 443       while (counter < n_basic_blocks)
 444         {
 445           basic_block new_target = NULL;
 446           bool new_target_threaded = false;
 447
 448           if (FORWARDER_BLOCK_P (target)
 449               && target->succ->dest != EXIT_BLOCK_PTR)
 450             {
 451               /* Bypass trivial infinite loops.  */
 452               if (target == target->succ->dest)
 453                 counter = n_basic_blocks;
 454               new_target = target->succ->dest;
 455             }
 456
 457           /* Allow to thread only over one edge at time to simplify updating
 458              of probabilities.  */
 459           else if (mode & CLEANUP_THREADING)
 460             {
 461               edge t = thread_jump (mode, e, target);
 462               if (t)
 463                 {
 464                   if (!threaded_edges)
 465                     threaded_edges = xmalloc (sizeof (*threaded_edges)
 466                                               * n_basic_blocks);
 467                   else
 468                     {
 469                       int i;
 470
 471                       /* Detect an infinite loop across blocks not
 472                          including the start block.  */
 473                       for (i = 0; i < nthreaded_edges; ++i)
 474                         if (threaded_edges[i] == t)
 475                           break;
 476                       if (i < nthreaded_edges)
 477                         {
 478                           counter = n_basic_blocks;
 479                           break;
 480                         }
 481                     }
 482
 483                   /* Detect an infinite loop across the start block.  */
 484                   if (t->dest == b)
 485                     break;
 486
 487                   if (nthreaded_edges >= n_basic_blocks)
 488                     abort ();
 489                   threaded_edges[nthreaded_edges++] = t;
 490
 491                   new_target = t->dest;
 492                   new_target_threaded = true;
 493                 }
 494             }
 495
 496           if (!new_target)
 497             break;
 498
 499           /* Avoid killing of loop pre-headers, as it is the place loop
 500              optimizer wants to hoist code to.
 501
 502              For fallthru forwarders, the LOOP_BEG note must appear between
 503              the header of block and CODE_LABEL of the loop, for non forwarders
 504              it must appear before the JUMP_INSN.  */
 505           if ((mode & CLEANUP_PRE_LOOP) && optimize)
 506             {
 507               rtx insn = (target->succ->flags & EDGE_FALLTHRU
 508                           ? target->head : prev_nonnote_insn (target->end));
 509
 510               if (GET_CODE (insn) != NOTE)
 511                 insn = NEXT_INSN (insn);
 512
 513               for (; insn && GET_CODE (insn) != CODE_LABEL && !INSN_P (insn);
 514                    insn = NEXT_INSN (insn))
 515                 if (GET_CODE (insn) == NOTE
 516                     && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
 517                   break;
 518
 519               if (GET_CODE (insn) == NOTE)
 520                 break;
 521
 522               /* Do not clean up branches to just past the end of a loop
 523                  at this time; it can mess up the loop optimizer's
 524                  recognition of some patterns.  */
 525
 526               insn = PREV_INSN (target->head);
 527               if (insn && GET_CODE (insn) == NOTE
 528                     && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
 529                 break;
 530             }
 531
 532           counter++;
 533           target = new_target;
 534           threaded |= new_target_threaded;
 535         }
 536
 537       if (counter >= n_basic_blocks)
 538         {
 539           if (rtl_dump_file)
 540             fprintf (rtl_dump_file, "Infinite loop in BB %i.\n",
 541                      target->index);
 542         }
 543       else if (target == first)
 544         ; /* We didn't do anything.  */
 545       else
 546         {
 547           /* Save the values now, as the edge may get removed.  */
 548           gcov_type edge_count = e->count;
 549           int edge_probability = e->probability;
 550           int edge_frequency;
 551           int n = 0;
 552
 553           /* Don't force if target is exit block.  */
 554           if (threaded && target != EXIT_BLOCK_PTR)
 555             {
 556               notice_new_block (redirect_edge_and_branch_force (e, target));
 557               if (rtl_dump_file)
 558                 fprintf (rtl_dump_file, "Conditionals threaded.\n");
 559             }
 560           else if (!redirect_edge_and_branch (e, target))
 561             {
 562               if (rtl_dump_file)
 563                 fprintf (rtl_dump_file,
 564                          "Forwarding edge %i->%i to %i failed.\n",
 565                          b->index, e->dest->index, target->index);
 566               continue;
 567             }
 568
 569           /* We successfully forwarded the edge.  Now update profile
 570              data: for each edge we traversed in the chain, remove
 571              the original edge's execution count.  */
 572           edge_frequency = ((edge_probability * b->frequency
 573                              + REG_BR_PROB_BASE / 2)
 574                             / REG_BR_PROB_BASE);
 575
 576           if (!FORWARDER_BLOCK_P (b) && forwarder_block_p (b))
 577             BB_SET_FLAG (b, BB_FORWARDER_BLOCK);
 578
 579           do
 580             {
 581               edge t;
 582
 583               first->count -= edge_count;
 584               if (first->count < 0)
 585                 first->count = 0;
 586               first->frequency -= edge_frequency;
 587               if (first->frequency < 0)
 588                 first->frequency = 0;
 589               if (first->succ->succ_next)
 590                 {
 591                   edge e;
 592                   int prob;
 593                   if (n >= nthreaded_edges)
 594                     abort ();
 595                   t = threaded_edges [n++];
 596                   if (t->src != first)
 597                     abort ();
 598                   if (first->frequency)
 599                     prob = edge_frequency * REG_BR_PROB_BASE / first->frequency;
 600                   else
 601                     prob = 0;
 602                   if (prob > t->probability)
 603                     prob = t->probability;
 604                   t->probability -= prob;
 605                   prob = REG_BR_PROB_BASE - prob;
 606                   if (prob <= 0)
 607                     {
 608                       first->succ->probability = REG_BR_PROB_BASE;
 609                       first->succ->succ_next->probability = 0;
 610                     }
 611                   else
 612                     for (e = first->succ; e; e = e->succ_next)
 613                       e->probability = ((e->probability * REG_BR_PROB_BASE)
 614                                         / (double) prob);
 615                   update_br_prob_note (first);
 616                 }
 617               else
 618                 {
 619                   /* It is possible that as the result of
 620                      threading we've removed edge as it is
 621                      threaded to the fallthru edge.  Avoid
 622                      getting out of sync.  */
 623                   if (n < nthreaded_edges
 624                       && first == threaded_edges [n]->src)
 625                     n++;
 626                   t = first->succ;
 627                 }
 628
 629               t->count -= edge_count;
 630               if (t->count < 0)
 631                 t->count = 0;
 632               first = t->dest;
 633             }
 634           while (first != target);
 635
 636           changed = true;
 637         }
 638     }
 639
 640   if (threaded_edges)
 641     free (threaded_edges);
 642   return changed;
 643 }
 644 \f
 645 /* Return true if LABEL is a target of JUMP_INSN.  This applies only
 646    to non-complex jumps.  That is, direct unconditional, conditional,
 647    and tablejumps, but not computed jumps or returns.  It also does
 648    not apply to the fallthru case of a conditional jump.  */
 649
 650 static bool
 651 label_is_jump_target_p (label, jump_insn)
 652      rtx label, jump_insn;
 653 {
 654   rtx tmp = JUMP_LABEL (jump_insn);
 655
 656   if (label == tmp)
 657     return true;
 658
 659   if (tmp != NULL_RTX
 660       && (tmp = NEXT_INSN (tmp)) != NULL_RTX
 661       && GET_CODE (tmp) == JUMP_INSN
 662       && (tmp = PATTERN (tmp),
 663           GET_CODE (tmp) == ADDR_VEC
 664           || GET_CODE (tmp) == ADDR_DIFF_VEC))
 665     {
 666       rtvec vec = XVEC (tmp, GET_CODE (tmp) == ADDR_DIFF_VEC);
 667       int i, veclen = GET_NUM_ELEM (vec);
 668
 669       for (i = 0; i < veclen; ++i)
 670         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
 671           return true;
 672     }
 673
 674   return false;
 675 }
 676
 677 /* Return true if LABEL is used for tail recursion.  */
 678
 679 static bool
 680 tail_recursion_label_p (label)
 681      rtx label;
 682 {
 683   rtx x;
 684
 685   for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
 686     if (label == XEXP (x, 0))
 687       return true;
 688
 689   return false;
 690 }
 691
 692 /* Blocks A and B are to be merged into a single block.  A has no incoming
 693    fallthru edge, so it can be moved before B without adding or modifying
 694    any jumps (aside from the jump from A to B).  */
 695
 696 static void
 697 merge_blocks_move_predecessor_nojumps (a, b)
 698      basic_block a, b;
 699 {
 700   rtx barrier;
 701
 702   barrier = next_nonnote_insn (a->end);
 703   if (GET_CODE (barrier) != BARRIER)
 704     abort ();
 705   delete_insn (barrier);
 706
 707   /* Move block and loop notes out of the chain so that we do not
 708      disturb their order.
 709
 710      ??? A better solution would be to squeeze out all the non-nested notes
 711      and adjust the block trees appropriately.   Even better would be to have
 712      a tighter connection between block trees and rtl so that this is not
 713      necessary.  */
 714   if (squeeze_notes (&a->head, &a->end))
 715     abort ();
 716
 717   /* Scramble the insn chain.  */
 718   if (a->end != PREV_INSN (b->head))
 719     reorder_insns_nobb (a->head, a->end, PREV_INSN (b->head));
 720   a->flags |= BB_DIRTY;
 721
 722   if (rtl_dump_file)
 723     fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
 724              a->index, b->index);
 725
 726   /* Swap the records for the two blocks around.  */
 727
 728   unlink_block (a);
 729   link_block (a, b->prev_bb);
 730
 731   /* Now blocks A and B are contiguous.  Merge them.  */
 732   merge_blocks_nomove (a, b);
 733 }
 734
 735 /* Blocks A and B are to be merged into a single block.  B has no outgoing
 736    fallthru edge, so it can be moved after A without adding or modifying
 737    any jumps (aside from the jump from A to B).  */
 738
 739 static void
 740 merge_blocks_move_successor_nojumps (a, b)
 741      basic_block a, b;
 742 {
 743   rtx barrier, real_b_end;
 744
 745   real_b_end = b->end;
 746   barrier = NEXT_INSN (b->end);
 747
 748   /* Recognize a jump table following block B.  */
 749   if (barrier
 750       && GET_CODE (barrier) == CODE_LABEL
 751       && NEXT_INSN (barrier)
 752       && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
 753       && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
 754           || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
 755     {
 756       /* Temporarily add the table jump insn to b, so that it will also
 757          be moved to the correct location.  */
 758       b->end = NEXT_INSN (barrier);
 759       barrier = NEXT_INSN (b->end);
 760     }
 761
 762   /* There had better have been a barrier there.  Delete it.  */
 763   if (barrier && GET_CODE (barrier) == BARRIER)
 764     delete_insn (barrier);
 765
 766   /* Move block and loop notes out of the chain so that we do not
 767      disturb their order.
 768
 769      ??? A better solution would be to squeeze out all the non-nested notes
 770      and adjust the block trees appropriately.   Even better would be to have
 771      a tighter connection between block trees and rtl so that this is not
 772      necessary.  */
 773   if (squeeze_notes (&b->head, &b->end))
 774     abort ();
 775
 776   /* Scramble the insn chain.  */
 777   reorder_insns_nobb (b->head, b->end, a->end);
 778
 779   /* Restore the real end of b.  */
 780   b->end = real_b_end;
 781
 782   if (rtl_dump_file)
 783     fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
 784              b->index, a->index);
 785
 786   /* Now blocks A and B are contiguous.  Merge them.  */
 787   merge_blocks_nomove (a, b);
 788 }
 789
 790 /* Attempt to merge basic blocks that are potentially non-adjacent.
 791    Return true iff the attempt succeeded.  */
 792
 793 static bool
 794 merge_blocks (e, b, c, mode)
 795      edge e;
 796      basic_block b, c;
 797      int mode;
 798 {
 799   /* If C has a tail recursion label, do not merge.  There is no
 800      edge recorded from the call_placeholder back to this label, as
 801      that would make optimize_sibling_and_tail_recursive_calls more
 802      complex for no gain.  */
 803   if ((mode & CLEANUP_PRE_SIBCALL)
 804       && GET_CODE (c->head) == CODE_LABEL
 805       && tail_recursion_label_p (c->head))
 806     return false;
 807
 808   /* If B has a fallthru edge to C, no need to move anything.  */
 809   if (e->flags & EDGE_FALLTHRU)
 810     {
 811       int b_index = b->index, c_index = c->index;
 812       merge_blocks_nomove (b, c);
 813       update_forwarder_flag (b);
 814
 815       if (rtl_dump_file)
 816         fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
 817                  b_index, c_index);
 818
 819       return true;
 820     }
 821
 822   /* Otherwise we will need to move code around.  Do that only if expensive
 823      transformations are allowed.  */
 824   else if (mode & CLEANUP_EXPENSIVE)
 825     {
 826       edge tmp_edge, b_fallthru_edge;
 827       bool c_has_outgoing_fallthru;
 828       bool b_has_incoming_fallthru;
 829
 830       /* Avoid overactive code motion, as the forwarder blocks should be
 831          eliminated by edge redirection instead.  One exception might have
 832          been if B is a forwarder block and C has no fallthru edge, but
 833          that should be cleaned up by bb-reorder instead.  */
 834       if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
 835         return false;
 836
 837       /* We must make sure to not munge nesting of lexical blocks,
 838          and loop notes.  This is done by squeezing out all the notes
 839          and leaving them there to lie.  Not ideal, but functional.  */
 840
 841       for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
 842         if (tmp_edge->flags & EDGE_FALLTHRU)
 843           break;
 844
 845       c_has_outgoing_fallthru = (tmp_edge != NULL);
 846
 847       for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
 848         if (tmp_edge->flags & EDGE_FALLTHRU)
 849           break;
 850
 851       b_has_incoming_fallthru = (tmp_edge != NULL);
 852       b_fallthru_edge = tmp_edge;
 853
 854       /* Otherwise, we're going to try to move C after B.  If C does
 855          not have an outgoing fallthru, then it can be moved
 856          immediately after B without introducing or modifying jumps.  */
 857       if (! c_has_outgoing_fallthru)
 858         {
 859           merge_blocks_move_successor_nojumps (b, c);
 860           return true;
 861         }
 862
 863       /* If B does not have an incoming fallthru, then it can be moved
 864          immediately before C without introducing or modifying jumps.
 865          C cannot be the first block, so we do not have to worry about
 866          accessing a non-existent block.  */
 867
 868       if (b_has_incoming_fallthru)
 869         {
 870           basic_block bb;
 871
 872           if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
 873             return false;
 874           bb = force_nonfallthru (b_fallthru_edge);
 875           if (bb)
 876             notice_new_block (bb);
 877         }
 878
 879       merge_blocks_move_predecessor_nojumps (b, c);
 880       return true;
 881     }
 882
 883   return false;
 884 }
 885 \f
 886
 887 /* Return true if I1 and I2 are equivalent and thus can be crossjumped.  */
 888
 889 static bool
 890 insns_match_p (mode, i1, i2)
 891      int mode ATTRIBUTE_UNUSED;
 892      rtx i1, i2;
 893 {
 894   rtx p1, p2;
 895
 896   /* Verify that I1 and I2 are equivalent.  */
 897   if (GET_CODE (i1) != GET_CODE (i2))
 898     return false;
 899
 900   p1 = PATTERN (i1);
 901   p2 = PATTERN (i2);
 902
 903   if (GET_CODE (p1) != GET_CODE (p2))
 904     return false;
 905
 906   /* If this is a CALL_INSN, compare register usage information.
 907      If we don't check this on stack register machines, the two
 908      CALL_INSNs might be merged leaving reg-stack.c with mismatching
 909      numbers of stack registers in the same basic block.
 910      If we don't check this on machines with delay slots, a delay slot may
 911      be filled that clobbers a parameter expected by the subroutine.
 912
 913      ??? We take the simple route for now and assume that if they're
 914      equal, they were constructed identically.  */
 915
 916   if (GET_CODE (i1) == CALL_INSN
 917       && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
 918                         CALL_INSN_FUNCTION_USAGE (i2))
 919           || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
 920     return false;
 921
 922 #ifdef STACK_REGS
 923   /* If cross_jump_death_matters is not 0, the insn's mode
 924      indicates whether or not the insn contains any stack-like
 925      regs.  */
 926
 927   if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
 928     {
 929       /* If register stack conversion has already been done, then
 930          death notes must also be compared before it is certain that
 931          the two instruction streams match.  */
 932
 933       rtx note;
 934       HARD_REG_SET i1_regset, i2_regset;
 935
 936       CLEAR_HARD_REG_SET (i1_regset);
 937       CLEAR_HARD_REG_SET (i2_regset);
 938
 939       for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
 940         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
 941           SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
 942
 943       for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
 944         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
 945           SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
 946
 947       GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
 948
 949       return false;
 950
 951     done:
 952       ;
 953     }
 954 #endif
 955
 956   if (reload_completed
 957       ? ! rtx_renumbered_equal_p (p1, p2) : ! rtx_equal_p (p1, p2))
 958     {
 959       /* The following code helps take care of G++ cleanups.  */
 960       rtx equiv1 = find_reg_equal_equiv_note (i1);
 961       rtx equiv2 = find_reg_equal_equiv_note (i2);
 962
 963       if (equiv1 && equiv2
 964           /* If the equivalences are not to a constant, they may
 965              reference pseudos that no longer exist, so we can't
 966              use them.  */
 967           && (! reload_completed
 968               || (CONSTANT_P (XEXP (equiv1, 0))
 969                   && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
 970         {
 971           rtx s1 = single_set (i1);
 972           rtx s2 = single_set (i2);
 973           if (s1 != 0 && s2 != 0
 974               && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
 975             {
 976               validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
 977               validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
 978               if (! rtx_renumbered_equal_p (p1, p2))
 979                 cancel_changes (0);
 980               else if (apply_change_group ())
 981                 return true;
 982             }
 983         }
 984
 985       return false;
 986     }
 987
 988   return true;
 989 }
 990 \f
 991 /* Look through the insns at the end of BB1 and BB2 and find the longest
 992    sequence that are equivalent.  Store the first insns for that sequence
 993    in *F1 and *F2 and return the sequence length.
 994
 995    To simplify callers of this function, if the blocks match exactly,
 996    store the head of the blocks in *F1 and *F2.  */
 997
 998 static int
 999 flow_find_cross_jump (mode, bb1, bb2, f1, f2)
1000      int mode ATTRIBUTE_UNUSED;
1001      basic_block bb1, bb2;
1002      rtx *f1, *f2;
1003 {
1004   rtx i1, i2, last1, last2, afterlast1, afterlast2;
1005   int ninsns = 0;
1006
1007   /* Skip simple jumps at the end of the blocks.  Complex jumps still
1008      need to be compared for equivalence, which we'll do below.  */
1009
1010   i1 = bb1->end;
1011   last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
1012   if (onlyjump_p (i1)
1013       || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1014     {
1015       last1 = i1;
1016       i1 = PREV_INSN (i1);
1017     }
1018
1019   i2 = bb2->end;
1020   if (onlyjump_p (i2)
1021       || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1022     {
1023       last2 = i2;
1024       /* Count everything except for unconditional jump as insn.  */
1025       if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1026         ninsns++;
1027       i2 = PREV_INSN (i2);
1028     }
1029
1030   while (true)
1031     {
1032       /* Ignore notes.  */
1033       while (!active_insn_p (i1) && i1 != bb1->head)
1034         i1 = PREV_INSN (i1);
1035
1036       while (!active_insn_p (i2) && i2 != bb2->head)
1037         i2 = PREV_INSN (i2);
1038
1039       if (i1 == bb1->head || i2 == bb2->head)
1040         break;
1041
1042       if (!insns_match_p (mode, i1, i2))
1043         break;
1044
1045       /* Don't begin a cross-jump with a USE or CLOBBER insn.  */
1046       if (active_insn_p (i1))
1047         {
1048           /* If the merged insns have different REG_EQUAL notes, then
1049              remove them.  */
1050           rtx equiv1 = find_reg_equal_equiv_note (i1);
1051           rtx equiv2 = find_reg_equal_equiv_note (i2);
1052
1053           if (equiv1 && !equiv2)
1054             remove_note (i1, equiv1);
1055           else if (!equiv1 && equiv2)
1056             remove_note (i2, equiv2);
1057           else if (equiv1 && equiv2
1058                    && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1059             {
1060               remove_note (i1, equiv1);
1061               remove_note (i2, equiv2);
1062             }
1063
1064           afterlast1 = last1, afterlast2 = last2;
1065           last1 = i1, last2 = i2;
1066           ninsns++;
1067         }
1068
1069       i1 = PREV_INSN (i1);
1070       i2 = PREV_INSN (i2);
1071     }
1072
1073 #ifdef HAVE_cc0
1074   /* Don't allow the insn after a compare to be shared by
1075      cross-jumping unless the compare is also shared.  */
1076   if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1077     last1 = afterlast1, last2 = afterlast2, ninsns--;
1078 #endif
1079
1080   /* Include preceding notes and labels in the cross-jump.  One,
1081      this may bring us to the head of the blocks as requested above.
1082      Two, it keeps line number notes as matched as may be.  */
1083   if (ninsns)
1084     {
1085       while (last1 != bb1->head && !active_insn_p (PREV_INSN (last1)))
1086         last1 = PREV_INSN (last1);
1087
1088       if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
1089         last1 = PREV_INSN (last1);
1090
1091       while (last2 != bb2->head && !active_insn_p (PREV_INSN (last2)))
1092         last2 = PREV_INSN (last2);
1093
1094       if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
1095         last2 = PREV_INSN (last2);
1096
1097       *f1 = last1;
1098       *f2 = last2;
1099     }
1100
1101   return ninsns;
1102 }
1103
1104 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1105    the branch instruction.  This means that if we commonize the control
1106    flow before end of the basic block, the semantic remains unchanged.
1107
1108    We may assume that there exists one edge with a common destination.  */
1109
1110 static bool
1111 outgoing_edges_match (mode, bb1, bb2)
1112      int mode;
1113      basic_block bb1;
1114      basic_block bb2;
1115 {
1116   int nehedges1 = 0, nehedges2 = 0;
1117   edge fallthru1 = 0, fallthru2 = 0;
1118   edge e1, e2;
1119
1120   /* If BB1 has only one successor, we may be looking at either an
1121      unconditional jump, or a fake edge to exit.  */
1122   if (bb1->succ && !bb1->succ->succ_next
1123       && (bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1124       && (GET_CODE (bb1->end) != JUMP_INSN || simplejump_p (bb1->end)))
1125     return (bb2->succ &&  !bb2->succ->succ_next
1126             && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1127             && (GET_CODE (bb2->end) != JUMP_INSN || simplejump_p (bb2->end)));
1128
1129   /* Match conditional jumps - this may get tricky when fallthru and branch
1130      edges are crossed.  */
1131   if (bb1->succ
1132       && bb1->succ->succ_next
1133       && !bb1->succ->succ_next->succ_next
1134       && any_condjump_p (bb1->end)
1135       && onlyjump_p (bb1->end))
1136     {
1137       edge b1, f1, b2, f2;
1138       bool reverse, match;
1139       rtx set1, set2, cond1, cond2;
1140       enum rtx_code code1, code2;
1141
1142       if (!bb2->succ
1143           || !bb2->succ->succ_next
1144           || bb2->succ->succ_next->succ_next
1145           || !any_condjump_p (bb2->end)
1146           || !onlyjump_p (bb2->end))
1147         return false;
1148
1149       b1 = BRANCH_EDGE (bb1);
1150       b2 = BRANCH_EDGE (bb2);
1151       f1 = FALLTHRU_EDGE (bb1);
1152       f2 = FALLTHRU_EDGE (bb2);
1153
1154       /* Get around possible forwarders on fallthru edges.  Other cases
1155          should be optimized out already.  */
1156       if (FORWARDER_BLOCK_P (f1->dest))
1157         f1 = f1->dest->succ;
1158
1159       if (FORWARDER_BLOCK_P (f2->dest))
1160         f2 = f2->dest->succ;
1161
1162       /* To simplify use of this function, return false if there are
1163          unneeded forwarder blocks.  These will get eliminated later
1164          during cleanup_cfg.  */
1165       if (FORWARDER_BLOCK_P (f1->dest)
1166           || FORWARDER_BLOCK_P (f2->dest)
1167           || FORWARDER_BLOCK_P (b1->dest)
1168           || FORWARDER_BLOCK_P (b2->dest))
1169         return false;
1170
1171       if (f1->dest == f2->dest && b1->dest == b2->dest)
1172         reverse = false;
1173       else if (f1->dest == b2->dest && b1->dest == f2->dest)
1174         reverse = true;
1175       else
1176         return false;
1177
1178       set1 = pc_set (bb1->end);
1179       set2 = pc_set (bb2->end);
1180       if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1181           != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1182         reverse = !reverse;
1183
1184       cond1 = XEXP (SET_SRC (set1), 0);
1185       cond2 = XEXP (SET_SRC (set2), 0);
1186       code1 = GET_CODE (cond1);
1187       if (reverse)
1188         code2 = reversed_comparison_code (cond2, bb2->end);
1189       else
1190         code2 = GET_CODE (cond2);
1191
1192       if (code2 == UNKNOWN)
1193         return false;
1194
1195       /* Verify codes and operands match.  */
1196       match = ((code1 == code2
1197                 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1198                 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1199                || (code1 == swap_condition (code2)
1200                    && rtx_renumbered_equal_p (XEXP (cond1, 1),
1201                                               XEXP (cond2, 0))
1202                    && rtx_renumbered_equal_p (XEXP (cond1, 0),
1203                                               XEXP (cond2, 1))));
1204
1205       /* If we return true, we will join the blocks.  Which means that
1206          we will only have one branch prediction bit to work with.  Thus
1207          we require the existing branches to have probabilities that are
1208          roughly similar.  */
1209       if (match
1210           && !optimize_size
1211           && maybe_hot_bb_p (bb1)
1212           && maybe_hot_bb_p (bb2))
1213         {
1214           int prob2;
1215
1216           if (b1->dest == b2->dest)
1217             prob2 = b2->probability;
1218           else
1219             /* Do not use f2 probability as f2 may be forwarded.  */
1220             prob2 = REG_BR_PROB_BASE - b2->probability;
1221
1222           /* Fail if the difference in probabilities is greater than 50%.
1223              This rules out two well-predicted branches with opposite
1224              outcomes.  */
1225           if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1226             {
1227               if (rtl_dump_file)
1228                 fprintf (rtl_dump_file,
1229                          "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1230                          bb1->index, bb2->index, b1->probability, prob2);
1231
1232               return false;
1233             }
1234         }
1235
1236       if (rtl_dump_file && match)
1237         fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
1238                  bb1->index, bb2->index);
1239
1240       return match;
1241     }
1242
1243   /* Generic case - we are seeing a computed jump, table jump or trapping
1244      instruction.  */
1245
1246   /* First ensure that the instructions match.  There may be many outgoing
1247      edges so this test is generally cheaper.
1248      ??? Currently the tablejumps will never match, as they do have
1249      different tables.  */
1250   if (!insns_match_p (mode, bb1->end, bb2->end))
1251     return false;
1252
1253   /* Search the outgoing edges, ensure that the counts do match, find possible
1254      fallthru and exception handling edges since these needs more
1255      validation.  */
1256   for (e1 = bb1->succ, e2 = bb2->succ; e1 && e2;
1257        e1 = e1->succ_next, e2 = e2->succ_next)
1258     {
1259       if (e1->flags & EDGE_EH)
1260         nehedges1++;
1261
1262       if (e2->flags & EDGE_EH)
1263         nehedges2++;
1264
1265       if (e1->flags & EDGE_FALLTHRU)
1266         fallthru1 = e1;
1267       if (e2->flags & EDGE_FALLTHRU)
1268         fallthru2 = e2;
1269     }
1270
1271   /* If number of edges of various types does not match, fail.  */
1272   if (e1 || e2
1273       || nehedges1 != nehedges2
1274       || (fallthru1 != 0) != (fallthru2 != 0))
1275     return false;
1276
1277   /* fallthru edges must be forwarded to the same destination.  */
1278   if (fallthru1)
1279     {
1280       basic_block d1 = (forwarder_block_p (fallthru1->dest)
1281                         ? fallthru1->dest->succ->dest: fallthru1->dest);
1282       basic_block d2 = (forwarder_block_p (fallthru2->dest)
1283                         ? fallthru2->dest->succ->dest: fallthru2->dest);
1284
1285       if (d1 != d2)
1286         return false;
1287     }
1288
1289   /* In case we do have EH edges, ensure we are in the same region.  */
1290   if (nehedges1)
1291     {
1292       rtx n1 = find_reg_note (bb1->end, REG_EH_REGION, 0);
1293       rtx n2 = find_reg_note (bb2->end, REG_EH_REGION, 0);
1294
1295       if (XEXP (n1, 0) != XEXP (n2, 0))
1296         return false;
1297     }
1298
1299   /* We don't need to match the rest of edges as above checks should be enought
1300      to ensure that they are equivalent.  */
1301   return true;
1302 }
1303
1304 /* E1 and E2 are edges with the same destination block.  Search their
1305    predecessors for common code.  If found, redirect control flow from
1306    (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC.  */
1307
1308 static bool
1309 try_crossjump_to_edge (mode, e1, e2)
1310      int mode;
1311      edge e1, e2;
1312 {
1313   int nmatch;
1314   basic_block src1 = e1->src, src2 = e2->src;
1315   basic_block redirect_to, redirect_from, to_remove;
1316   rtx newpos1, newpos2;
1317   edge s;
1318
1319   /* Search backward through forwarder blocks.  We don't need to worry
1320      about multiple entry or chained forwarders, as they will be optimized
1321      away.  We do this to look past the unconditional jump following a
1322      conditional jump that is required due to the current CFG shape.  */
1323   if (src1->pred
1324       && !src1->pred->pred_next
1325       && FORWARDER_BLOCK_P (src1))
1326     e1 = src1->pred, src1 = e1->src;
1327
1328   if (src2->pred
1329       && !src2->pred->pred_next
1330       && FORWARDER_BLOCK_P (src2))
1331     e2 = src2->pred, src2 = e2->src;
1332
1333   /* Nothing to do if we reach ENTRY, or a common source block.  */
1334   if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1335     return false;
1336   if (src1 == src2)
1337     return false;
1338
1339   /* Seeing more than 1 forwarder blocks would confuse us later...  */
1340   if (FORWARDER_BLOCK_P (e1->dest)
1341       && FORWARDER_BLOCK_P (e1->dest->succ->dest))
1342     return false;
1343
1344   if (FORWARDER_BLOCK_P (e2->dest)
1345       && FORWARDER_BLOCK_P (e2->dest->succ->dest))
1346     return false;
1347
1348   /* Likewise with dead code (possibly newly created by the other optimizations
1349      of cfg_cleanup).  */
1350   if (!src1->pred || !src2->pred)
1351     return false;
1352
1353   /* Look for the common insn sequence, part the first ...  */
1354   if (!outgoing_edges_match (mode, src1, src2))
1355     return false;
1356
1357   /* ... and part the second.  */
1358   nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1359   if (!nmatch)
1360     return false;
1361
1362   /* Avoid splitting if possible.  */
1363   if (newpos2 == src2->head)
1364     redirect_to = src2;
1365   else
1366     {
1367       if (rtl_dump_file)
1368         fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
1369                  src2->index, nmatch);
1370       redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1371     }
1372
1373   if (rtl_dump_file)
1374     fprintf (rtl_dump_file,
1375              "Cross jumping from bb %i to bb %i; %i common insns\n",
1376              src1->index, src2->index, nmatch);
1377
1378   redirect_to->count += src1->count;
1379   redirect_to->frequency += src1->frequency;
1380   /* We may have some registers visible trought the block.  */
1381   redirect_to->flags |= BB_DIRTY;
1382
1383   /* Recompute the frequencies and counts of outgoing edges.  */
1384   for (s = redirect_to->succ; s; s = s->succ_next)
1385     {
1386       edge s2;
1387       basic_block d = s->dest;
1388
1389       if (FORWARDER_BLOCK_P (d))
1390         d = d->succ->dest;
1391
1392       for (s2 = src1->succ; ; s2 = s2->succ_next)
1393         {
1394           basic_block d2 = s2->dest;
1395           if (FORWARDER_BLOCK_P (d2))
1396             d2 = d2->succ->dest;
1397           if (d == d2)
1398             break;
1399         }
1400
1401       s->count += s2->count;
1402
1403       /* Take care to update possible forwarder blocks.  We verified
1404          that there is no more than one in the chain, so we can't run
1405          into infinite loop.  */
1406       if (FORWARDER_BLOCK_P (s->dest))
1407         {
1408           s->dest->succ->count += s2->count;
1409           s->dest->count += s2->count;
1410           s->dest->frequency += EDGE_FREQUENCY (s);
1411         }
1412
1413       if (FORWARDER_BLOCK_P (s2->dest))
1414         {
1415           s2->dest->succ->count -= s2->count;
1416           if (s2->dest->succ->count < 0)
1417             s2->dest->succ->count = 0;
1418           s2->dest->count -= s2->count;
1419           s2->dest->frequency -= EDGE_FREQUENCY (s);
1420           if (s2->dest->frequency < 0)
1421             s2->dest->frequency = 0;
1422           if (s2->dest->count < 0)
1423             s2->dest->count = 0;
1424         }
1425
1426       if (!redirect_to->frequency && !src1->frequency)
1427         s->probability = (s->probability + s2->probability) / 2;
1428       else
1429         s->probability
1430           = ((s->probability * redirect_to->frequency +
1431               s2->probability * src1->frequency)
1432              / (redirect_to->frequency + src1->frequency));
1433     }
1434
1435   update_br_prob_note (redirect_to);
1436
1437   /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1.  */
1438
1439   /* Skip possible basic block header.  */
1440   if (GET_CODE (newpos1) == CODE_LABEL)
1441     newpos1 = NEXT_INSN (newpos1);
1442
1443   if (GET_CODE (newpos1) == NOTE)
1444     newpos1 = NEXT_INSN (newpos1);
1445
1446   redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
1447   to_remove = redirect_from->succ->dest;
1448
1449   redirect_edge_and_branch_force (redirect_from->succ, redirect_to);
1450   flow_delete_block (to_remove);
1451
1452   update_forwarder_flag (redirect_from);
1453
1454   return true;
1455 }
1456
1457 /* Search the predecessors of BB for common insn sequences.  When found,
1458    share code between them by redirecting control flow.  Return true if
1459    any changes made.  */
1460
1461 static bool
1462 try_crossjump_bb (mode, bb)
1463      int mode;
1464      basic_block bb;
1465 {
1466   edge e, e2, nexte2, nexte, fallthru;
1467   bool changed;
1468   int n = 0, max;
1469
1470   /* Nothing to do if there is not at least two incoming edges.  */
1471   if (!bb->pred || !bb->pred->pred_next)
1472     return false;
1473
1474   /* It is always cheapest to redirect a block that ends in a branch to
1475      a block that falls through into BB, as that adds no branches to the
1476      program.  We'll try that combination first.  */
1477   fallthru = NULL;
1478   max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
1479   for (e = bb->pred; e ; e = e->pred_next, n++)
1480     {
1481       if (e->flags & EDGE_FALLTHRU)
1482         fallthru = e;
1483       if (n > max)
1484         return false;
1485     }
1486
1487   changed = false;
1488   for (e = bb->pred; e; e = nexte)
1489     {
1490       nexte = e->pred_next;
1491
1492       /* As noted above, first try with the fallthru predecessor.  */
1493       if (fallthru)
1494         {
1495           /* Don't combine the fallthru edge into anything else.
1496              If there is a match, we'll do it the other way around.  */
1497           if (e == fallthru)
1498             continue;
1499
1500           if (try_crossjump_to_edge (mode, e, fallthru))
1501             {
1502               changed = true;
1503               nexte = bb->pred;
1504               continue;
1505             }
1506         }
1507
1508       /* Non-obvious work limiting check: Recognize that we're going
1509          to call try_crossjump_bb on every basic block.  So if we have
1510          two blocks with lots of outgoing edges (a switch) and they
1511          share lots of common destinations, then we would do the
1512          cross-jump check once for each common destination.
1513
1514          Now, if the blocks actually are cross-jump candidates, then
1515          all of their destinations will be shared.  Which means that
1516          we only need check them for cross-jump candidacy once.  We
1517          can eliminate redundant checks of crossjump(A,B) by arbitrarily
1518          choosing to do the check from the block for which the edge
1519          in question is the first successor of A.  */
1520       if (e->src->succ != e)
1521         continue;
1522
1523       for (e2 = bb->pred; e2; e2 = nexte2)
1524         {
1525           nexte2 = e2->pred_next;
1526
1527           if (e2 == e)
1528             continue;
1529
1530           /* We've already checked the fallthru edge above.  */
1531           if (e2 == fallthru)
1532             continue;
1533
1534           /* The "first successor" check above only prevents multiple
1535              checks of crossjump(A,B).  In order to prevent redundant
1536              checks of crossjump(B,A), require that A be the block
1537              with the lowest index.  */
1538           if (e->src->index > e2->src->index)
1539             continue;
1540
1541           if (try_crossjump_to_edge (mode, e, e2))
1542             {
1543               changed = true;
1544               nexte = bb->pred;
1545               break;
1546             }
1547         }
1548     }
1549
1550   return changed;
1551 }
1552
1553 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1554    instructions etc.  Return nonzero if changes were made.  */
1555
1556 static bool
1557 try_optimize_cfg (mode)
1558      int mode;
1559 {
1560   bool changed_overall = false;
1561   bool changed;
1562   int iterations = 0;
1563   basic_block bb, b;
1564
1565   if (mode & CLEANUP_CROSSJUMP)
1566     add_noreturn_fake_exit_edges ();
1567
1568   FOR_EACH_BB (bb)
1569     update_forwarder_flag (bb);
1570
1571   if (mode & CLEANUP_UPDATE_LIFE)
1572     clear_bb_flags ();
1573
1574   if (! (* targetm.cannot_modify_jumps_p) ())
1575     {
1576       /* Attempt to merge blocks as made possible by edge removal.  If
1577          a block has only one successor, and the successor has only
1578          one predecessor, they may be combined.  */
1579       do
1580         {
1581           changed = false;
1582           iterations++;
1583
1584           if (rtl_dump_file)
1585             fprintf (rtl_dump_file,
1586                      "\n\ntry_optimize_cfg iteration %i\n\n",
1587                      iterations);
1588
1589           for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
1590             {
1591               basic_block c;
1592               edge s;
1593               bool changed_here = false;
1594
1595               /* Delete trivially dead basic blocks.  */
1596               while (b->pred == NULL)
1597                 {
1598                   c = b->prev_bb;
1599                   if (rtl_dump_file)
1600                     fprintf (rtl_dump_file, "Deleting block %i.\n",
1601                              b->index);
1602
1603                   flow_delete_block (b);
1604                   changed = true;
1605                   b = c;
1606                 }
1607
1608               /* Remove code labels no longer used.  Don't do this
1609                  before CALL_PLACEHOLDER is removed, as some branches
1610                  may be hidden within.  */
1611               if (b->pred->pred_next == NULL
1612                   && (b->pred->flags & EDGE_FALLTHRU)
1613                   && !(b->pred->flags & EDGE_COMPLEX)
1614                   && GET_CODE (b->head) == CODE_LABEL
1615                   && (!(mode & CLEANUP_PRE_SIBCALL)
1616                       || !tail_recursion_label_p (b->head))
1617                   /* If the previous block ends with a branch to this
1618                      block, we can't delete the label.  Normally this
1619                      is a condjump that is yet to be simplified, but
1620                      if CASE_DROPS_THRU, this can be a tablejump with
1621                      some element going to the same place as the
1622                      default (fallthru).  */
1623                   && (b->pred->src == ENTRY_BLOCK_PTR
1624                       || GET_CODE (b->pred->src->end) != JUMP_INSN
1625                       || ! label_is_jump_target_p (b->head,
1626                                                    b->pred->src->end)))
1627                 {
1628                   rtx label = b->head;
1629
1630                   b->head = NEXT_INSN (b->head);
1631                   delete_insn_chain (label, label);
1632                   if (rtl_dump_file)
1633                     fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1634                              b->index);
1635                 }
1636
1637               /* If we fall through an empty block, we can remove it.  */
1638               if (b->pred->pred_next == NULL
1639                   && (b->pred->flags & EDGE_FALLTHRU)
1640                   && GET_CODE (b->head) != CODE_LABEL
1641                   && FORWARDER_BLOCK_P (b)
1642                   /* Note that forwarder_block_p true ensures that
1643                      there is a successor for this block.  */
1644                   && (b->succ->flags & EDGE_FALLTHRU)
1645                   && n_basic_blocks > 1)
1646                 {
1647                   if (rtl_dump_file)
1648                     fprintf (rtl_dump_file,
1649                              "Deleting fallthru block %i.\n",
1650                              b->index);
1651
1652                   c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
1653                   redirect_edge_succ_nodup (b->pred, b->succ->dest);
1654                   flow_delete_block (b);
1655                   changed = true;
1656                   b = c;
1657                 }
1658
1659               /* Merge blocks.  Loop because chains of blocks might be
1660                  combineable.  */
1661               while ((s = b->succ) != NULL
1662                      && s->succ_next == NULL
1663                      && !(s->flags & EDGE_COMPLEX)
1664                      && (c = s->dest) != EXIT_BLOCK_PTR
1665                      && c->pred->pred_next == NULL
1666                      && b != c
1667                      /* If the jump insn has side effects,
1668                         we can't kill the edge.  */
1669                      && (GET_CODE (b->end) != JUMP_INSN
1670                          || simplejump_p (b->end))
1671                      && merge_blocks (s, b, c, mode))
1672                 changed_here = true;
1673
1674               /* Simplify branch over branch.  */
1675               if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b))
1676                 changed_here = true;
1677
1678               /* If B has a single outgoing edge, but uses a
1679                  non-trivial jump instruction without side-effects, we
1680                  can either delete the jump entirely, or replace it
1681                  with a simple unconditional jump.  Use
1682                  redirect_edge_and_branch to do the dirty work.  */
1683               if (b->succ
1684                   && ! b->succ->succ_next
1685                   && b->succ->dest != EXIT_BLOCK_PTR
1686                   && onlyjump_p (b->end)
1687                   && redirect_edge_and_branch (b->succ, b->succ->dest))
1688                 {
1689                   update_forwarder_flag (b);
1690                   changed_here = true;
1691                 }
1692
1693               /* Simplify branch to branch.  */
1694               if (try_forward_edges (mode, b))
1695                 changed_here = true;
1696
1697               /* Look for shared code between blocks.  */
1698               if ((mode & CLEANUP_CROSSJUMP)
1699                   && try_crossjump_bb (mode, b))
1700                 changed_here = true;
1701
1702               /* Don't get confused by the index shift caused by
1703                  deleting blocks.  */
1704               if (!changed_here)
1705                 b = b->next_bb;
1706               else
1707                 changed = true;
1708             }
1709
1710           if ((mode & CLEANUP_CROSSJUMP)
1711               && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1712             changed = true;
1713
1714 #ifdef ENABLE_CHECKING
1715           if (changed)
1716             verify_flow_info ();
1717 #endif
1718
1719           changed_overall |= changed;
1720         }
1721       while (changed);
1722     }
1723
1724   if (mode & CLEANUP_CROSSJUMP)
1725     remove_fake_edges ();
1726
1727   clear_aux_for_blocks ();
1728
1729   return changed_overall;
1730 }
1731 \f
1732 /* Delete all unreachable basic blocks.  */
1733
1734 bool
1735 delete_unreachable_blocks ()
1736 {
1737   bool changed = false;
1738   basic_block b, next_bb;
1739
1740   find_unreachable_blocks ();
1741
1742   /* Delete all unreachable basic blocks.  */
1743
1744   for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
1745     {
1746       next_bb = b->next_bb;
1747
1748       if (!(b->flags & BB_REACHABLE))
1749         {
1750           flow_delete_block (b);
1751           changed = true;
1752         }
1753     }
1754
1755   if (changed)
1756     tidy_fallthru_edges ();
1757   return changed;
1758 }
1759 \f
1760 /* Tidy the CFG by deleting unreachable code and whatnot.  */
1761
1762 bool
1763 cleanup_cfg (mode)
1764      int mode;
1765 {
1766   bool changed = false;
1767
1768   timevar_push (TV_CLEANUP_CFG);
1769   if (delete_unreachable_blocks ())
1770     {
1771       changed = true;
1772       /* We've possibly created trivially dead code.  Cleanup it right
1773          now to introduce more opportunities for try_optimize_cfg.  */
1774       if (!(mode & (CLEANUP_NO_INSN_DEL
1775                     | CLEANUP_UPDATE_LIFE | CLEANUP_PRE_SIBCALL))
1776           && !reload_completed)
1777         delete_trivially_dead_insns (get_insns(), max_reg_num ());
1778     }
1779
1780   compact_blocks ();
1781
1782   while (try_optimize_cfg (mode))
1783     {
1784       delete_unreachable_blocks (), changed = true;
1785       if (mode & CLEANUP_UPDATE_LIFE)
1786         {
1787           /* Cleaning up CFG introduces more opportunities for dead code
1788              removal that in turn may introduce more opportunities for
1789              cleaning up the CFG.  */
1790           if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
1791                                                  PROP_DEATH_NOTES
1792                                                  | PROP_SCAN_DEAD_CODE
1793                                                  | PROP_KILL_DEAD_CODE
1794                                                  | PROP_LOG_LINKS))
1795             break;
1796         }
1797       else if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_PRE_SIBCALL))
1798                && (mode & CLEANUP_EXPENSIVE)
1799                && !reload_completed)
1800         {
1801           if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1802             break;
1803         }
1804       else
1805         break;
1806       delete_dead_jumptables ();
1807     }
1808
1809   /* Kill the data we won't maintain.  */
1810   free_EXPR_LIST_list (&label_value_list);
1811   timevar_pop (TV_CLEANUP_CFG);
1812
1813   return changed;
1814 }