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 basic_block 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   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 (tablejump_p (jump_insn, NULL, &tmp))
 660     {
 661       rtvec vec = XVEC (tmp, GET_CODE (tmp) == ADDR_DIFF_VEC);
 662       int i, veclen = GET_NUM_ELEM (vec);
 663
 664       for (i = 0; i < veclen; ++i)
 665         if (XEXP (RTVEC_ELT (vec, i), 0) == label)
 666           return true;
 667     }
 668
 669   return false;
 670 }
 671
 672 /* Return true if LABEL is used for tail recursion.  */
 673
 674 static bool
 675 tail_recursion_label_p (label)
 676      rtx label;
 677 {
 678   rtx x;
 679
 680   for (x = tail_recursion_label_list; x; x = XEXP (x, 1))
 681     if (label == XEXP (x, 0))
 682       return true;
 683
 684   return false;
 685 }
 686
 687 /* Blocks A and B are to be merged into a single block.  A has no incoming
 688    fallthru edge, so it can be moved before B without adding or modifying
 689    any jumps (aside from the jump from A to B).  */
 690
 691 static void
 692 merge_blocks_move_predecessor_nojumps (a, b)
 693      basic_block a, b;
 694 {
 695   rtx barrier;
 696
 697   barrier = next_nonnote_insn (a->end);
 698   if (GET_CODE (barrier) != BARRIER)
 699     abort ();
 700   delete_insn (barrier);
 701
 702   /* Move block and loop notes out of the chain so that we do not
 703      disturb their order.
 704
 705      ??? A better solution would be to squeeze out all the non-nested notes
 706      and adjust the block trees appropriately.   Even better would be to have
 707      a tighter connection between block trees and rtl so that this is not
 708      necessary.  */
 709   if (squeeze_notes (&a->head, &a->end))
 710     abort ();
 711
 712   /* Scramble the insn chain.  */
 713   if (a->end != PREV_INSN (b->head))
 714     reorder_insns_nobb (a->head, a->end, PREV_INSN (b->head));
 715   a->flags |= BB_DIRTY;
 716
 717   if (rtl_dump_file)
 718     fprintf (rtl_dump_file, "Moved block %d before %d and merged.\n",
 719              a->index, b->index);
 720
 721   /* Swap the records for the two blocks around.  */
 722
 723   unlink_block (a);
 724   link_block (a, b->prev_bb);
 725
 726   /* Now blocks A and B are contiguous.  Merge them.  */
 727   merge_blocks_nomove (a, b);
 728 }
 729
 730 /* Blocks A and B are to be merged into a single block.  B has no outgoing
 731    fallthru edge, so it can be moved after A without adding or modifying
 732    any jumps (aside from the jump from A to B).  */
 733
 734 static void
 735 merge_blocks_move_successor_nojumps (a, b)
 736      basic_block a, b;
 737 {
 738   rtx barrier, real_b_end;
 739
 740   real_b_end = b->end;
 741   barrier = NEXT_INSN (b->end);
 742
 743   /* Recognize a jump table following block B.  */
 744   if (barrier
 745       && GET_CODE (barrier) == CODE_LABEL
 746       && NEXT_INSN (barrier)
 747       && GET_CODE (NEXT_INSN (barrier)) == JUMP_INSN
 748       && (GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_VEC
 749           || GET_CODE (PATTERN (NEXT_INSN (barrier))) == ADDR_DIFF_VEC))
 750     {
 751       /* Temporarily add the table jump insn to b, so that it will also
 752          be moved to the correct location.  */
 753       b->end = NEXT_INSN (barrier);
 754       barrier = NEXT_INSN (b->end);
 755     }
 756
 757   /* There had better have been a barrier there.  Delete it.  */
 758   if (barrier && GET_CODE (barrier) == BARRIER)
 759     delete_insn (barrier);
 760
 761   /* Move block and loop notes out of the chain so that we do not
 762      disturb their order.
 763
 764      ??? A better solution would be to squeeze out all the non-nested notes
 765      and adjust the block trees appropriately.   Even better would be to have
 766      a tighter connection between block trees and rtl so that this is not
 767      necessary.  */
 768   if (squeeze_notes (&b->head, &b->end))
 769     abort ();
 770
 771   /* Scramble the insn chain.  */
 772   reorder_insns_nobb (b->head, b->end, a->end);
 773
 774   /* Restore the real end of b.  */
 775   b->end = real_b_end;
 776
 777   if (rtl_dump_file)
 778     fprintf (rtl_dump_file, "Moved block %d after %d and merged.\n",
 779              b->index, a->index);
 780
 781   /* Now blocks A and B are contiguous.  Merge them.  */
 782   merge_blocks_nomove (a, b);
 783 }
 784
 785 /* Attempt to merge basic blocks that are potentially non-adjacent.
 786    Return NULL iff the attempt failed, otherwise return basic block
 787    where cleanup_cfg should continue.  Because the merging commonly
 788    moves basic block away or introduces another optimization
 789    possiblity, return basic block just before B so cleanup_cfg don't
 790    need to iterate.
 791
 792    It may be good idea to return basic block before C in the case
 793    C has been moved after B and originally appeared earlier in the
 794    insn seqeunce, but we have no infromation available about the
 795    relative ordering of these two.  Hopefully it is not too common.  */
 796
 797 static basic_block
 798 merge_blocks (e, b, c, mode)
 799      edge e;
 800      basic_block b, c;
 801      int mode;
 802 {
 803   basic_block next;
 804   /* If C has a tail recursion label, do not merge.  There is no
 805      edge recorded from the call_placeholder back to this label, as
 806      that would make optimize_sibling_and_tail_recursive_calls more
 807      complex for no gain.  */
 808   if ((mode & CLEANUP_PRE_SIBCALL)
 809       && GET_CODE (c->head) == CODE_LABEL
 810       && tail_recursion_label_p (c->head))
 811     return NULL;
 812
 813   /* If B has a fallthru edge to C, no need to move anything.  */
 814   if (e->flags & EDGE_FALLTHRU)
 815     {
 816       int b_index = b->index, c_index = c->index;
 817       merge_blocks_nomove (b, c);
 818       update_forwarder_flag (b);
 819
 820       if (rtl_dump_file)
 821         fprintf (rtl_dump_file, "Merged %d and %d without moving.\n",
 822                  b_index, c_index);
 823
 824       return b->prev_bb == ENTRY_BLOCK_PTR ? b : b->prev_bb;
 825     }
 826
 827   /* Otherwise we will need to move code around.  Do that only if expensive
 828      transformations are allowed.  */
 829   else if (mode & CLEANUP_EXPENSIVE)
 830     {
 831       edge tmp_edge, b_fallthru_edge;
 832       bool c_has_outgoing_fallthru;
 833       bool b_has_incoming_fallthru;
 834
 835       /* Avoid overactive code motion, as the forwarder blocks should be
 836          eliminated by edge redirection instead.  One exception might have
 837          been if B is a forwarder block and C has no fallthru edge, but
 838          that should be cleaned up by bb-reorder instead.  */
 839       if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
 840         return NULL;
 841
 842       /* We must make sure to not munge nesting of lexical blocks,
 843          and loop notes.  This is done by squeezing out all the notes
 844          and leaving them there to lie.  Not ideal, but functional.  */
 845
 846       for (tmp_edge = c->succ; tmp_edge; tmp_edge = tmp_edge->succ_next)
 847         if (tmp_edge->flags & EDGE_FALLTHRU)
 848           break;
 849
 850       c_has_outgoing_fallthru = (tmp_edge != NULL);
 851
 852       for (tmp_edge = b->pred; tmp_edge; tmp_edge = tmp_edge->pred_next)
 853         if (tmp_edge->flags & EDGE_FALLTHRU)
 854           break;
 855
 856       b_has_incoming_fallthru = (tmp_edge != NULL);
 857       b_fallthru_edge = tmp_edge;
 858       next = b->prev_bb;
 859       if (next == c)
 860         next = next->prev_bb;
 861
 862       /* Otherwise, we're going to try to move C after B.  If C does
 863          not have an outgoing fallthru, then it can be moved
 864          immediately after B without introducing or modifying jumps.  */
 865       if (! c_has_outgoing_fallthru)
 866         {
 867           merge_blocks_move_successor_nojumps (b, c);
 868           return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
 869         }
 870
 871       /* If B does not have an incoming fallthru, then it can be moved
 872          immediately before C without introducing or modifying jumps.
 873          C cannot be the first block, so we do not have to worry about
 874          accessing a non-existent block.  */
 875
 876       if (b_has_incoming_fallthru)
 877         {
 878           basic_block bb;
 879
 880           if (b_fallthru_edge->src == ENTRY_BLOCK_PTR)
 881             return NULL;
 882           bb = force_nonfallthru (b_fallthru_edge);
 883           if (bb)
 884             notice_new_block (bb);
 885         }
 886
 887       merge_blocks_move_predecessor_nojumps (b, c);
 888       return next == ENTRY_BLOCK_PTR ? next->next_bb : next;
 889     }
 890
 891   return NULL;
 892 }
 893 \f
 894
 895 /* Return true if I1 and I2 are equivalent and thus can be crossjumped.  */
 896
 897 static bool
 898 insns_match_p (mode, i1, i2)
 899      int mode ATTRIBUTE_UNUSED;
 900      rtx i1, i2;
 901 {
 902   rtx p1, p2;
 903
 904   /* Verify that I1 and I2 are equivalent.  */
 905   if (GET_CODE (i1) != GET_CODE (i2))
 906     return false;
 907
 908   p1 = PATTERN (i1);
 909   p2 = PATTERN (i2);
 910
 911   if (GET_CODE (p1) != GET_CODE (p2))
 912     return false;
 913
 914   /* If this is a CALL_INSN, compare register usage information.
 915      If we don't check this on stack register machines, the two
 916      CALL_INSNs might be merged leaving reg-stack.c with mismatching
 917      numbers of stack registers in the same basic block.
 918      If we don't check this on machines with delay slots, a delay slot may
 919      be filled that clobbers a parameter expected by the subroutine.
 920
 921      ??? We take the simple route for now and assume that if they're
 922      equal, they were constructed identically.  */
 923
 924   if (GET_CODE (i1) == CALL_INSN
 925       && (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (i1),
 926                         CALL_INSN_FUNCTION_USAGE (i2))
 927           || SIBLING_CALL_P (i1) != SIBLING_CALL_P (i2)))
 928     return false;
 929
 930 #ifdef STACK_REGS
 931   /* If cross_jump_death_matters is not 0, the insn's mode
 932      indicates whether or not the insn contains any stack-like
 933      regs.  */
 934
 935   if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
 936     {
 937       /* If register stack conversion has already been done, then
 938          death notes must also be compared before it is certain that
 939          the two instruction streams match.  */
 940
 941       rtx note;
 942       HARD_REG_SET i1_regset, i2_regset;
 943
 944       CLEAR_HARD_REG_SET (i1_regset);
 945       CLEAR_HARD_REG_SET (i2_regset);
 946
 947       for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
 948         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
 949           SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
 950
 951       for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
 952         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
 953           SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
 954
 955       GO_IF_HARD_REG_EQUAL (i1_regset, i2_regset, done);
 956
 957       return false;
 958
 959     done:
 960       ;
 961     }
 962 #endif
 963
 964   if (reload_completed
 965       ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
 966     return true;
 967
 968   /* Do not do EQUIV substitution after reload.  First, we're undoing the
 969      work of reload_cse.  Second, we may be undoing the work of the post-
 970      reload splitting pass.  */
 971   /* ??? Possibly add a new phase switch variable that can be used by
 972      targets to disallow the troublesome insns after splitting.  */
 973   if (!reload_completed)
 974     {
 975       /* The following code helps take care of G++ cleanups.  */
 976       rtx equiv1 = find_reg_equal_equiv_note (i1);
 977       rtx equiv2 = find_reg_equal_equiv_note (i2);
 978
 979       if (equiv1 && equiv2
 980           /* If the equivalences are not to a constant, they may
 981              reference pseudos that no longer exist, so we can't
 982              use them.  */
 983           && (! reload_completed
 984               || (CONSTANT_P (XEXP (equiv1, 0))
 985                   && rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))))
 986         {
 987           rtx s1 = single_set (i1);
 988           rtx s2 = single_set (i2);
 989           if (s1 != 0 && s2 != 0
 990               && rtx_renumbered_equal_p (SET_DEST (s1), SET_DEST (s2)))
 991             {
 992               validate_change (i1, &SET_SRC (s1), XEXP (equiv1, 0), 1);
 993               validate_change (i2, &SET_SRC (s2), XEXP (equiv2, 0), 1);
 994               if (! rtx_renumbered_equal_p (p1, p2))
 995                 cancel_changes (0);
 996               else if (apply_change_group ())
 997                 return true;
 998             }
 999         }
1000     }
1001
1002   return false;
1003 }
1004 \f
1005 /* Look through the insns at the end of BB1 and BB2 and find the longest
1006    sequence that are equivalent.  Store the first insns for that sequence
1007    in *F1 and *F2 and return the sequence length.
1008
1009    To simplify callers of this function, if the blocks match exactly,
1010    store the head of the blocks in *F1 and *F2.  */
1011
1012 static int
1013 flow_find_cross_jump (mode, bb1, bb2, f1, f2)
1014      int mode ATTRIBUTE_UNUSED;
1015      basic_block bb1, bb2;
1016      rtx *f1, *f2;
1017 {
1018   rtx i1, i2, last1, last2, afterlast1, afterlast2;
1019   int ninsns = 0;
1020
1021   /* Skip simple jumps at the end of the blocks.  Complex jumps still
1022      need to be compared for equivalence, which we'll do below.  */
1023
1024   i1 = bb1->end;
1025   last1 = afterlast1 = last2 = afterlast2 = NULL_RTX;
1026   if (onlyjump_p (i1)
1027       || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
1028     {
1029       last1 = i1;
1030       i1 = PREV_INSN (i1);
1031     }
1032
1033   i2 = bb2->end;
1034   if (onlyjump_p (i2)
1035       || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
1036     {
1037       last2 = i2;
1038       /* Count everything except for unconditional jump as insn.  */
1039       if (!simplejump_p (i2) && !returnjump_p (i2) && last1)
1040         ninsns++;
1041       i2 = PREV_INSN (i2);
1042     }
1043
1044   while (true)
1045     {
1046       /* Ignore notes.  */
1047       while (!INSN_P (i1) && i1 != bb1->head)
1048         i1 = PREV_INSN (i1);
1049
1050       while (!INSN_P (i2) && i2 != bb2->head)
1051         i2 = PREV_INSN (i2);
1052
1053       if (i1 == bb1->head || i2 == bb2->head)
1054         break;
1055
1056       if (!insns_match_p (mode, i1, i2))
1057         break;
1058
1059       /* Don't begin a cross-jump with a NOTE insn.  */
1060       if (INSN_P (i1))
1061         {
1062           /* If the merged insns have different REG_EQUAL notes, then
1063              remove them.  */
1064           rtx equiv1 = find_reg_equal_equiv_note (i1);
1065           rtx equiv2 = find_reg_equal_equiv_note (i2);
1066
1067           if (equiv1 && !equiv2)
1068             remove_note (i1, equiv1);
1069           else if (!equiv1 && equiv2)
1070             remove_note (i2, equiv2);
1071           else if (equiv1 && equiv2
1072                    && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
1073             {
1074               remove_note (i1, equiv1);
1075               remove_note (i2, equiv2);
1076             }
1077
1078           afterlast1 = last1, afterlast2 = last2;
1079           last1 = i1, last2 = i2;
1080           ninsns++;
1081         }
1082
1083       i1 = PREV_INSN (i1);
1084       i2 = PREV_INSN (i2);
1085     }
1086
1087 #ifdef HAVE_cc0
1088   /* Don't allow the insn after a compare to be shared by
1089      cross-jumping unless the compare is also shared.  */
1090   if (ninsns && reg_mentioned_p (cc0_rtx, last1) && ! sets_cc0_p (last1))
1091     last1 = afterlast1, last2 = afterlast2, ninsns--;
1092 #endif
1093
1094   /* Include preceding notes and labels in the cross-jump.  One,
1095      this may bring us to the head of the blocks as requested above.
1096      Two, it keeps line number notes as matched as may be.  */
1097   if (ninsns)
1098     {
1099       while (last1 != bb1->head && !INSN_P (PREV_INSN (last1)))
1100         last1 = PREV_INSN (last1);
1101
1102       if (last1 != bb1->head && GET_CODE (PREV_INSN (last1)) == CODE_LABEL)
1103         last1 = PREV_INSN (last1);
1104
1105       while (last2 != bb2->head && !INSN_P (PREV_INSN (last2)))
1106         last2 = PREV_INSN (last2);
1107
1108       if (last2 != bb2->head && GET_CODE (PREV_INSN (last2)) == CODE_LABEL)
1109         last2 = PREV_INSN (last2);
1110
1111       *f1 = last1;
1112       *f2 = last2;
1113     }
1114
1115   return ninsns;
1116 }
1117
1118 /* Return true iff outgoing edges of BB1 and BB2 match, together with
1119    the branch instruction.  This means that if we commonize the control
1120    flow before end of the basic block, the semantic remains unchanged.
1121
1122    We may assume that there exists one edge with a common destination.  */
1123
1124 static bool
1125 outgoing_edges_match (mode, bb1, bb2)
1126      int mode;
1127      basic_block bb1;
1128      basic_block bb2;
1129 {
1130   int nehedges1 = 0, nehedges2 = 0;
1131   edge fallthru1 = 0, fallthru2 = 0;
1132   edge e1, e2;
1133
1134   /* If BB1 has only one successor, we may be looking at either an
1135      unconditional jump, or a fake edge to exit.  */
1136   if (bb1->succ && !bb1->succ->succ_next
1137       && (bb1->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1138       && (GET_CODE (bb1->end) != JUMP_INSN || simplejump_p (bb1->end)))
1139     return (bb2->succ &&  !bb2->succ->succ_next
1140             && (bb2->succ->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
1141             && (GET_CODE (bb2->end) != JUMP_INSN || simplejump_p (bb2->end)));
1142
1143   /* Match conditional jumps - this may get tricky when fallthru and branch
1144      edges are crossed.  */
1145   if (bb1->succ
1146       && bb1->succ->succ_next
1147       && !bb1->succ->succ_next->succ_next
1148       && any_condjump_p (bb1->end)
1149       && onlyjump_p (bb1->end))
1150     {
1151       edge b1, f1, b2, f2;
1152       bool reverse, match;
1153       rtx set1, set2, cond1, cond2;
1154       enum rtx_code code1, code2;
1155
1156       if (!bb2->succ
1157           || !bb2->succ->succ_next
1158           || bb2->succ->succ_next->succ_next
1159           || !any_condjump_p (bb2->end)
1160           || !onlyjump_p (bb2->end))
1161         return false;
1162
1163       b1 = BRANCH_EDGE (bb1);
1164       b2 = BRANCH_EDGE (bb2);
1165       f1 = FALLTHRU_EDGE (bb1);
1166       f2 = FALLTHRU_EDGE (bb2);
1167
1168       /* Get around possible forwarders on fallthru edges.  Other cases
1169          should be optimized out already.  */
1170       if (FORWARDER_BLOCK_P (f1->dest))
1171         f1 = f1->dest->succ;
1172
1173       if (FORWARDER_BLOCK_P (f2->dest))
1174         f2 = f2->dest->succ;
1175
1176       /* To simplify use of this function, return false if there are
1177          unneeded forwarder blocks.  These will get eliminated later
1178          during cleanup_cfg.  */
1179       if (FORWARDER_BLOCK_P (f1->dest)
1180           || FORWARDER_BLOCK_P (f2->dest)
1181           || FORWARDER_BLOCK_P (b1->dest)
1182           || FORWARDER_BLOCK_P (b2->dest))
1183         return false;
1184
1185       if (f1->dest == f2->dest && b1->dest == b2->dest)
1186         reverse = false;
1187       else if (f1->dest == b2->dest && b1->dest == f2->dest)
1188         reverse = true;
1189       else
1190         return false;
1191
1192       set1 = pc_set (bb1->end);
1193       set2 = pc_set (bb2->end);
1194       if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
1195           != (XEXP (SET_SRC (set2), 1) == pc_rtx))
1196         reverse = !reverse;
1197
1198       cond1 = XEXP (SET_SRC (set1), 0);
1199       cond2 = XEXP (SET_SRC (set2), 0);
1200       code1 = GET_CODE (cond1);
1201       if (reverse)
1202         code2 = reversed_comparison_code (cond2, bb2->end);
1203       else
1204         code2 = GET_CODE (cond2);
1205
1206       if (code2 == UNKNOWN)
1207         return false;
1208
1209       /* Verify codes and operands match.  */
1210       match = ((code1 == code2
1211                 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
1212                 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
1213                || (code1 == swap_condition (code2)
1214                    && rtx_renumbered_equal_p (XEXP (cond1, 1),
1215                                               XEXP (cond2, 0))
1216                    && rtx_renumbered_equal_p (XEXP (cond1, 0),
1217                                               XEXP (cond2, 1))));
1218
1219       /* If we return true, we will join the blocks.  Which means that
1220          we will only have one branch prediction bit to work with.  Thus
1221          we require the existing branches to have probabilities that are
1222          roughly similar.  */
1223       if (match
1224           && !optimize_size
1225           && maybe_hot_bb_p (bb1)
1226           && maybe_hot_bb_p (bb2))
1227         {
1228           int prob2;
1229
1230           if (b1->dest == b2->dest)
1231             prob2 = b2->probability;
1232           else
1233             /* Do not use f2 probability as f2 may be forwarded.  */
1234             prob2 = REG_BR_PROB_BASE - b2->probability;
1235
1236           /* Fail if the difference in probabilities is greater than 50%.
1237              This rules out two well-predicted branches with opposite
1238              outcomes.  */
1239           if (abs (b1->probability - prob2) > REG_BR_PROB_BASE / 2)
1240             {
1241               if (rtl_dump_file)
1242                 fprintf (rtl_dump_file,
1243                          "Outcomes of branch in bb %i and %i differs to much (%i %i)\n",
1244                          bb1->index, bb2->index, b1->probability, prob2);
1245
1246               return false;
1247             }
1248         }
1249
1250       if (rtl_dump_file && match)
1251         fprintf (rtl_dump_file, "Conditionals in bb %i and %i match.\n",
1252                  bb1->index, bb2->index);
1253
1254       return match;
1255     }
1256
1257   /* Generic case - we are seeing a computed jump, table jump or trapping
1258      instruction.  */
1259
1260 #ifndef CASE_DROPS_THROUGH
1261   /* Check whether there are tablejumps in the end of BB1 and BB2.
1262      Return true if they are identical.  */
1263     {
1264       rtx label1, label2;
1265       rtx table1, table2;
1266
1267       if (tablejump_p (bb1->end, &label1, &table1)
1268           && tablejump_p (bb2->end, &label2, &table2)
1269           && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
1270         {
1271           /* The labels should never be the same rtx.  If they really are same
1272              the jump tables are same too. So disable crossjumping of blocks BB1
1273              and BB2 because when deleting the common insns in the end of BB1
1274              by delete_block () the jump table would be deleted too.  */
1275           /* If LABEL2 is referenced in BB1->END do not do anything
1276              because we would loose information when replacing
1277              LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END.  */
1278           if (label1 != label2 && !rtx_referenced_p (label2, bb1->end))
1279             {
1280               /* Set IDENTICAL to true when the tables are identical.  */
1281               bool identical = false;
1282               rtx p1, p2;
1283
1284               p1 = PATTERN (table1);
1285               p2 = PATTERN (table2);
1286               if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
1287                 {
1288                   identical = true;
1289                 }
1290               else if (GET_CODE (p1) == ADDR_DIFF_VEC
1291                        && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
1292                        && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
1293                        && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
1294                 {
1295                   int i;
1296
1297                   identical = true;
1298                   for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
1299                     if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
1300                       identical = false;
1301                 }
1302
1303               if (identical)
1304                 {
1305                   replace_label_data rr;
1306                   bool match;
1307
1308                   /* Temporarily replace references to LABEL1 with LABEL2
1309                      in BB1->END so that we could compare the instructions.  */
1310                   rr.r1 = label1;
1311                   rr.r2 = label2;
1312                   rr.update_label_nuses = false;
1313                   for_each_rtx (&bb1->end, replace_label, &rr);
1314
1315                   match = insns_match_p (mode, bb1->end, bb2->end);
1316                   if (rtl_dump_file && match)
1317                     fprintf (rtl_dump_file,
1318                              "Tablejumps in bb %i and %i match.\n",
1319                              bb1->index, bb2->index);
1320
1321                   /* Set the original label in BB1->END because when deleting
1322                      a block whose end is a tablejump, the tablejump referenced
1323                      from the instruction is deleted too.  */
1324                   rr.r1 = label2;
1325                   rr.r2 = label1;
1326                   for_each_rtx (&bb1->end, replace_label, &rr);
1327
1328                   return match;
1329                 }
1330             }
1331           return false;
1332         }
1333     }
1334 #endif
1335
1336   /* First ensure that the instructions match.  There may be many outgoing
1337      edges so this test is generally cheaper.  */
1338   if (!insns_match_p (mode, bb1->end, bb2->end))
1339     return false;
1340
1341   /* Search the outgoing edges, ensure that the counts do match, find possible
1342      fallthru and exception handling edges since these needs more
1343      validation.  */
1344   for (e1 = bb1->succ, e2 = bb2->succ; e1 && e2;
1345        e1 = e1->succ_next, e2 = e2->succ_next)
1346     {
1347       if (e1->flags & EDGE_EH)
1348         nehedges1++;
1349
1350       if (e2->flags & EDGE_EH)
1351         nehedges2++;
1352
1353       if (e1->flags & EDGE_FALLTHRU)
1354         fallthru1 = e1;
1355       if (e2->flags & EDGE_FALLTHRU)
1356         fallthru2 = e2;
1357     }
1358
1359   /* If number of edges of various types does not match, fail.  */
1360   if (e1 || e2
1361       || nehedges1 != nehedges2
1362       || (fallthru1 != 0) != (fallthru2 != 0))
1363     return false;
1364
1365   /* fallthru edges must be forwarded to the same destination.  */
1366   if (fallthru1)
1367     {
1368       basic_block d1 = (forwarder_block_p (fallthru1->dest)
1369                         ? fallthru1->dest->succ->dest: fallthru1->dest);
1370       basic_block d2 = (forwarder_block_p (fallthru2->dest)
1371                         ? fallthru2->dest->succ->dest: fallthru2->dest);
1372
1373       if (d1 != d2)
1374         return false;
1375     }
1376
1377   /* In case we do have EH edges, ensure we are in the same region.  */
1378   if (nehedges1)
1379     {
1380       rtx n1 = find_reg_note (bb1->end, REG_EH_REGION, 0);
1381       rtx n2 = find_reg_note (bb2->end, REG_EH_REGION, 0);
1382
1383       if (XEXP (n1, 0) != XEXP (n2, 0))
1384         return false;
1385     }
1386
1387   /* We don't need to match the rest of edges as above checks should be enought
1388      to ensure that they are equivalent.  */
1389   return true;
1390 }
1391
1392 /* E1 and E2 are edges with the same destination block.  Search their
1393    predecessors for common code.  If found, redirect control flow from
1394    (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC.  */
1395
1396 static bool
1397 try_crossjump_to_edge (mode, e1, e2)
1398      int mode;
1399      edge e1, e2;
1400 {
1401   int nmatch;
1402   basic_block src1 = e1->src, src2 = e2->src;
1403   basic_block redirect_to, redirect_from, to_remove;
1404   rtx newpos1, newpos2;
1405   edge s;
1406
1407   /* Search backward through forwarder blocks.  We don't need to worry
1408      about multiple entry or chained forwarders, as they will be optimized
1409      away.  We do this to look past the unconditional jump following a
1410      conditional jump that is required due to the current CFG shape.  */
1411   if (src1->pred
1412       && !src1->pred->pred_next
1413       && FORWARDER_BLOCK_P (src1))
1414     e1 = src1->pred, src1 = e1->src;
1415
1416   if (src2->pred
1417       && !src2->pred->pred_next
1418       && FORWARDER_BLOCK_P (src2))
1419     e2 = src2->pred, src2 = e2->src;
1420
1421   /* Nothing to do if we reach ENTRY, or a common source block.  */
1422   if (src1 == ENTRY_BLOCK_PTR || src2 == ENTRY_BLOCK_PTR)
1423     return false;
1424   if (src1 == src2)
1425     return false;
1426
1427   /* Seeing more than 1 forwarder blocks would confuse us later...  */
1428   if (FORWARDER_BLOCK_P (e1->dest)
1429       && FORWARDER_BLOCK_P (e1->dest->succ->dest))
1430     return false;
1431
1432   if (FORWARDER_BLOCK_P (e2->dest)
1433       && FORWARDER_BLOCK_P (e2->dest->succ->dest))
1434     return false;
1435
1436   /* Likewise with dead code (possibly newly created by the other optimizations
1437      of cfg_cleanup).  */
1438   if (!src1->pred || !src2->pred)
1439     return false;
1440
1441   /* Look for the common insn sequence, part the first ...  */
1442   if (!outgoing_edges_match (mode, src1, src2))
1443     return false;
1444
1445   /* ... and part the second.  */
1446   nmatch = flow_find_cross_jump (mode, src1, src2, &newpos1, &newpos2);
1447   if (!nmatch)
1448     return false;
1449
1450 #ifndef CASE_DROPS_THROUGH
1451   /* Here we know that the insns in the end of SRC1 which are common with SRC2
1452      will be deleted.
1453      If we have tablejumps in the end of SRC1 and SRC2
1454      they have been already compared for equivalence in outgoing_edges_match ()
1455      so replace the references to TABLE1 by references to TABLE2.  */
1456     {
1457       rtx label1, label2;
1458       rtx table1, table2;
1459
1460       if (tablejump_p (src1->end, &label1, &table1)
1461           && tablejump_p (src2->end, &label2, &table2)
1462           && label1 != label2)
1463         {
1464           replace_label_data rr;
1465           rtx insn;
1466
1467           /* Replace references to LABEL1 with LABEL2.  */
1468           rr.r1 = label1;
1469           rr.r2 = label2;
1470           rr.update_label_nuses = true;
1471           for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
1472             {
1473               /* Do not replace the label in SRC1->END because when deleting
1474                  a block whose end is a tablejump, the tablejump referenced
1475                  from the instruction is deleted too.  */
1476               if (insn != src1->end)
1477                 for_each_rtx (&insn, replace_label, &rr);
1478             }
1479         }
1480     }
1481 #endif
1482
1483   /* Avoid splitting if possible.  */
1484   if (newpos2 == src2->head)
1485     redirect_to = src2;
1486   else
1487     {
1488       if (rtl_dump_file)
1489         fprintf (rtl_dump_file, "Splitting bb %i before %i insns\n",
1490                  src2->index, nmatch);
1491       redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
1492     }
1493
1494   if (rtl_dump_file)
1495     fprintf (rtl_dump_file,
1496              "Cross jumping from bb %i to bb %i; %i common insns\n",
1497              src1->index, src2->index, nmatch);
1498
1499   redirect_to->count += src1->count;
1500   redirect_to->frequency += src1->frequency;
1501   /* We may have some registers visible trought the block.  */
1502   redirect_to->flags |= BB_DIRTY;
1503
1504   /* Recompute the frequencies and counts of outgoing edges.  */
1505   for (s = redirect_to->succ; s; s = s->succ_next)
1506     {
1507       edge s2;
1508       basic_block d = s->dest;
1509
1510       if (FORWARDER_BLOCK_P (d))
1511         d = d->succ->dest;
1512
1513       for (s2 = src1->succ; ; s2 = s2->succ_next)
1514         {
1515           basic_block d2 = s2->dest;
1516           if (FORWARDER_BLOCK_P (d2))
1517             d2 = d2->succ->dest;
1518           if (d == d2)
1519             break;
1520         }
1521
1522       s->count += s2->count;
1523
1524       /* Take care to update possible forwarder blocks.  We verified
1525          that there is no more than one in the chain, so we can't run
1526          into infinite loop.  */
1527       if (FORWARDER_BLOCK_P (s->dest))
1528         {
1529           s->dest->succ->count += s2->count;
1530           s->dest->count += s2->count;
1531           s->dest->frequency += EDGE_FREQUENCY (s);
1532         }
1533
1534       if (FORWARDER_BLOCK_P (s2->dest))
1535         {
1536           s2->dest->succ->count -= s2->count;
1537           if (s2->dest->succ->count < 0)
1538             s2->dest->succ->count = 0;
1539           s2->dest->count -= s2->count;
1540           s2->dest->frequency -= EDGE_FREQUENCY (s);
1541           if (s2->dest->frequency < 0)
1542             s2->dest->frequency = 0;
1543           if (s2->dest->count < 0)
1544             s2->dest->count = 0;
1545         }
1546
1547       if (!redirect_to->frequency && !src1->frequency)
1548         s->probability = (s->probability + s2->probability) / 2;
1549       else
1550         s->probability
1551           = ((s->probability * redirect_to->frequency +
1552               s2->probability * src1->frequency)
1553              / (redirect_to->frequency + src1->frequency));
1554     }
1555
1556   update_br_prob_note (redirect_to);
1557
1558   /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1.  */
1559
1560   /* Skip possible basic block header.  */
1561   if (GET_CODE (newpos1) == CODE_LABEL)
1562     newpos1 = NEXT_INSN (newpos1);
1563
1564   if (GET_CODE (newpos1) == NOTE)
1565     newpos1 = NEXT_INSN (newpos1);
1566
1567   redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
1568   to_remove = redirect_from->succ->dest;
1569
1570   redirect_edge_and_branch_force (redirect_from->succ, redirect_to);
1571   delete_block (to_remove);
1572
1573   update_forwarder_flag (redirect_from);
1574
1575   return true;
1576 }
1577
1578 /* Search the predecessors of BB for common insn sequences.  When found,
1579    share code between them by redirecting control flow.  Return true if
1580    any changes made.  */
1581
1582 static bool
1583 try_crossjump_bb (mode, bb)
1584      int mode;
1585      basic_block bb;
1586 {
1587   edge e, e2, nexte2, nexte, fallthru;
1588   bool changed;
1589   int n = 0, max;
1590
1591   /* Nothing to do if there is not at least two incoming edges.  */
1592   if (!bb->pred || !bb->pred->pred_next)
1593     return false;
1594
1595   /* It is always cheapest to redirect a block that ends in a branch to
1596      a block that falls through into BB, as that adds no branches to the
1597      program.  We'll try that combination first.  */
1598   fallthru = NULL;
1599   max = PARAM_VALUE (PARAM_MAX_CROSSJUMP_EDGES);
1600   for (e = bb->pred; e ; e = e->pred_next, n++)
1601     {
1602       if (e->flags & EDGE_FALLTHRU)
1603         fallthru = e;
1604       if (n > max)
1605         return false;
1606     }
1607
1608   changed = false;
1609   for (e = bb->pred; e; e = nexte)
1610     {
1611       nexte = e->pred_next;
1612
1613       /* As noted above, first try with the fallthru predecessor.  */
1614       if (fallthru)
1615         {
1616           /* Don't combine the fallthru edge into anything else.
1617              If there is a match, we'll do it the other way around.  */
1618           if (e == fallthru)
1619             continue;
1620
1621           if (try_crossjump_to_edge (mode, e, fallthru))
1622             {
1623               changed = true;
1624               nexte = bb->pred;
1625               continue;
1626             }
1627         }
1628
1629       /* Non-obvious work limiting check: Recognize that we're going
1630          to call try_crossjump_bb on every basic block.  So if we have
1631          two blocks with lots of outgoing edges (a switch) and they
1632          share lots of common destinations, then we would do the
1633          cross-jump check once for each common destination.
1634
1635          Now, if the blocks actually are cross-jump candidates, then
1636          all of their destinations will be shared.  Which means that
1637          we only need check them for cross-jump candidacy once.  We
1638          can eliminate redundant checks of crossjump(A,B) by arbitrarily
1639          choosing to do the check from the block for which the edge
1640          in question is the first successor of A.  */
1641       if (e->src->succ != e)
1642         continue;
1643
1644       for (e2 = bb->pred; e2; e2 = nexte2)
1645         {
1646           nexte2 = e2->pred_next;
1647
1648           if (e2 == e)
1649             continue;
1650
1651           /* We've already checked the fallthru edge above.  */
1652           if (e2 == fallthru)
1653             continue;
1654
1655           /* The "first successor" check above only prevents multiple
1656              checks of crossjump(A,B).  In order to prevent redundant
1657              checks of crossjump(B,A), require that A be the block
1658              with the lowest index.  */
1659           if (e->src->index > e2->src->index)
1660             continue;
1661
1662           if (try_crossjump_to_edge (mode, e, e2))
1663             {
1664               changed = true;
1665               nexte = bb->pred;
1666               break;
1667             }
1668         }
1669     }
1670
1671   return changed;
1672 }
1673
1674 /* Do simple CFG optimizations - basic block merging, simplifying of jump
1675    instructions etc.  Return nonzero if changes were made.  */
1676
1677 static bool
1678 try_optimize_cfg (mode)
1679      int mode;
1680 {
1681   bool changed_overall = false;
1682   bool changed;
1683   int iterations = 0;
1684   basic_block bb, b, next;
1685
1686   if (mode & CLEANUP_CROSSJUMP)
1687     add_noreturn_fake_exit_edges ();
1688
1689   FOR_EACH_BB (bb)
1690     update_forwarder_flag (bb);
1691
1692   if (mode & CLEANUP_UPDATE_LIFE)
1693     clear_bb_flags ();
1694
1695   if (! (* targetm.cannot_modify_jumps_p) ())
1696     {
1697       /* Attempt to merge blocks as made possible by edge removal.  If
1698          a block has only one successor, and the successor has only
1699          one predecessor, they may be combined.  */
1700       do
1701         {
1702           changed = false;
1703           iterations++;
1704
1705           if (rtl_dump_file)
1706             fprintf (rtl_dump_file,
1707                      "\n\ntry_optimize_cfg iteration %i\n\n",
1708                      iterations);
1709
1710           for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR;)
1711             {
1712               basic_block c;
1713               edge s;
1714               bool changed_here = false;
1715
1716               /* Delete trivially dead basic blocks.  */
1717               while (b->pred == NULL)
1718                 {
1719                   c = b->prev_bb;
1720                   if (rtl_dump_file)
1721                     fprintf (rtl_dump_file, "Deleting block %i.\n",
1722                              b->index);
1723
1724                   delete_block (b);
1725                   changed = true;
1726                   b = c;
1727                 }
1728
1729               /* Remove code labels no longer used.  Don't do this
1730                  before CALL_PLACEHOLDER is removed, as some branches
1731                  may be hidden within.  */
1732               if (b->pred->pred_next == NULL
1733                   && (b->pred->flags & EDGE_FALLTHRU)
1734                   && !(b->pred->flags & EDGE_COMPLEX)
1735                   && GET_CODE (b->head) == CODE_LABEL
1736                   && (!(mode & CLEANUP_PRE_SIBCALL)
1737                       || !tail_recursion_label_p (b->head))
1738                   /* If the previous block ends with a branch to this
1739                      block, we can't delete the label.  Normally this
1740                      is a condjump that is yet to be simplified, but
1741                      if CASE_DROPS_THRU, this can be a tablejump with
1742                      some element going to the same place as the
1743                      default (fallthru).  */
1744                   && (b->pred->src == ENTRY_BLOCK_PTR
1745                       || GET_CODE (b->pred->src->end) != JUMP_INSN
1746                       || ! label_is_jump_target_p (b->head,
1747                                                    b->pred->src->end)))
1748                 {
1749                   rtx label = b->head;
1750
1751                   b->head = NEXT_INSN (b->head);
1752                   delete_insn_chain (label, label);
1753                   if (rtl_dump_file)
1754                     fprintf (rtl_dump_file, "Deleted label in block %i.\n",
1755                              b->index);
1756                 }
1757
1758               /* If we fall through an empty block, we can remove it.  */
1759               if (b->pred->pred_next == NULL
1760                   && (b->pred->flags & EDGE_FALLTHRU)
1761                   && GET_CODE (b->head) != CODE_LABEL
1762                   && FORWARDER_BLOCK_P (b)
1763                   /* Note that forwarder_block_p true ensures that
1764                      there is a successor for this block.  */
1765                   && (b->succ->flags & EDGE_FALLTHRU)
1766                   && n_basic_blocks > 1)
1767                 {
1768                   if (rtl_dump_file)
1769                     fprintf (rtl_dump_file,
1770                              "Deleting fallthru block %i.\n",
1771                              b->index);
1772
1773                   c = b->prev_bb == ENTRY_BLOCK_PTR ? b->next_bb : b->prev_bb;
1774                   redirect_edge_succ_nodup (b->pred, b->succ->dest);
1775                   delete_block (b);
1776                   changed = true;
1777                   b = c;
1778                 }
1779
1780               if ((s = b->succ) != NULL
1781                   && s->succ_next == NULL
1782                   && !(s->flags & EDGE_COMPLEX)
1783                   && (c = s->dest) != EXIT_BLOCK_PTR
1784                   && c->pred->pred_next == NULL
1785                   && b != c
1786                   /* If the jump insn has side effects,
1787                      we can't kill the edge.  */
1788                   && (GET_CODE (b->end) != JUMP_INSN
1789                       || (flow2_completed
1790                           ? simplejump_p (b->end)
1791                           : onlyjump_p (b->end)))
1792                   && (next = merge_blocks (s, b, c, mode)))
1793                 {
1794                   b = next;
1795                   changed_here = true;
1796                 }
1797
1798               /* Simplify branch over branch.  */
1799               if ((mode & CLEANUP_EXPENSIVE) && try_simplify_condjump (b))
1800                 changed_here = true;
1801
1802               /* If B has a single outgoing edge, but uses a
1803                  non-trivial jump instruction without side-effects, we
1804                  can either delete the jump entirely, or replace it
1805                  with a simple unconditional jump.  Use
1806                  redirect_edge_and_branch to do the dirty work.  */
1807               if (b->succ
1808                   && ! b->succ->succ_next
1809                   && b->succ->dest != EXIT_BLOCK_PTR
1810                   && onlyjump_p (b->end)
1811                   && redirect_edge_and_branch (b->succ, b->succ->dest))
1812                 {
1813                   update_forwarder_flag (b);
1814                   changed_here = true;
1815                 }
1816
1817               /* Simplify branch to branch.  */
1818               if (try_forward_edges (mode, b))
1819                 changed_here = true;
1820
1821               /* Look for shared code between blocks.  */
1822               if ((mode & CLEANUP_CROSSJUMP)
1823                   && try_crossjump_bb (mode, b))
1824                 changed_here = true;
1825
1826               /* Don't get confused by the index shift caused by
1827                  deleting blocks.  */
1828               if (!changed_here)
1829                 b = b->next_bb;
1830               else
1831                 changed = true;
1832             }
1833
1834           if ((mode & CLEANUP_CROSSJUMP)
1835               && try_crossjump_bb (mode, EXIT_BLOCK_PTR))
1836             changed = true;
1837
1838 #ifdef ENABLE_CHECKING
1839           if (changed)
1840             verify_flow_info ();
1841 #endif
1842
1843           changed_overall |= changed;
1844         }
1845       while (changed);
1846     }
1847
1848   if (mode & CLEANUP_CROSSJUMP)
1849     remove_fake_edges ();
1850
1851   clear_aux_for_blocks ();
1852
1853   return changed_overall;
1854 }
1855 \f
1856 /* Delete all unreachable basic blocks.  */
1857
1858 bool
1859 delete_unreachable_blocks ()
1860 {
1861   bool changed = false;
1862   basic_block b, next_bb;
1863
1864   find_unreachable_blocks ();
1865
1866   /* Delete all unreachable basic blocks.  */
1867
1868   for (b = ENTRY_BLOCK_PTR->next_bb; b != EXIT_BLOCK_PTR; b = next_bb)
1869     {
1870       next_bb = b->next_bb;
1871
1872       if (!(b->flags & BB_REACHABLE))
1873         {
1874           delete_block (b);
1875           changed = true;
1876         }
1877     }
1878
1879   if (changed)
1880     tidy_fallthru_edges ();
1881   return changed;
1882 }
1883 \f
1884 /* Tidy the CFG by deleting unreachable code and whatnot.  */
1885
1886 bool
1887 cleanup_cfg (mode)
1888      int mode;
1889 {
1890   bool changed = false;
1891
1892   timevar_push (TV_CLEANUP_CFG);
1893   if (delete_unreachable_blocks ())
1894     {
1895       changed = true;
1896       /* We've possibly created trivially dead code.  Cleanup it right
1897          now to introduce more opportunities for try_optimize_cfg.  */
1898       if (!(mode & (CLEANUP_NO_INSN_DEL
1899                     | CLEANUP_UPDATE_LIFE | CLEANUP_PRE_SIBCALL))
1900           && !reload_completed)
1901         delete_trivially_dead_insns (get_insns(), max_reg_num ());
1902     }
1903
1904   compact_blocks ();
1905
1906   while (try_optimize_cfg (mode))
1907     {
1908       delete_unreachable_blocks (), changed = true;
1909       if (mode & CLEANUP_UPDATE_LIFE)
1910         {
1911           /* Cleaning up CFG introduces more opportunities for dead code
1912              removal that in turn may introduce more opportunities for
1913              cleaning up the CFG.  */
1914           if (!update_life_info_in_dirty_blocks (UPDATE_LIFE_GLOBAL_RM_NOTES,
1915                                                  PROP_DEATH_NOTES
1916                                                  | PROP_SCAN_DEAD_CODE
1917                                                  | PROP_KILL_DEAD_CODE
1918                                                  | PROP_LOG_LINKS))
1919             break;
1920         }
1921       else if (!(mode & (CLEANUP_NO_INSN_DEL | CLEANUP_PRE_SIBCALL))
1922                && (mode & CLEANUP_EXPENSIVE)
1923                && !reload_completed)
1924         {
1925           if (!delete_trivially_dead_insns (get_insns(), max_reg_num ()))
1926             break;
1927         }
1928       else
1929         break;
1930       delete_dead_jumptables ();
1931     }
1932
1933   /* Kill the data we won't maintain.  */
1934   free_EXPR_LIST_list (&label_value_list);
1935   timevar_pop (TV_CLEANUP_CFG);
1936
1937   return changed;
1938 }