gcc/cfgcleanup.c

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