LCOV - code coverage report
Current view: top level - gcc - cfgcleanup.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 93.2 % 1432 1334
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 39 39
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Control flow optimization code for GNU compiler.
       2              :    Copyright (C) 1987-2026 Free Software Foundation, Inc.
       3              : 
       4              : This file is part of GCC.
       5              : 
       6              : GCC is free software; you can redistribute it and/or modify it under
       7              : the terms of the GNU General Public License as published by the Free
       8              : Software Foundation; either version 3, or (at your option) any later
       9              : version.
      10              : 
      11              : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12              : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14              : for more details.
      15              : 
      16              : You should have received a copy of the GNU General Public License
      17              : along with GCC; see the file COPYING3.  If not see
      18              : <http://www.gnu.org/licenses/>.  */
      19              : 
      20              : /* This file contains optimizer of the control flow.  The main entry point is
      21              :    cleanup_cfg.  Following optimizations are performed:
      22              : 
      23              :    - Unreachable blocks removal
      24              :    - Edge forwarding (edge to the forwarder block is forwarded to its
      25              :      successor.  Simplification of the branch instruction is performed by
      26              :      underlying infrastructure so branch can be converted to simplejump or
      27              :      eliminated).
      28              :    - Cross jumping (tail merging)
      29              :    - Conditional jump-around-simplejump simplification
      30              :    - Basic block merging.  */
      31              : 
      32              : #include "config.h"
      33              : #include "system.h"
      34              : #include "coretypes.h"
      35              : #include "backend.h"
      36              : #include "target.h"
      37              : #include "rtl.h"
      38              : #include "tree.h"
      39              : #include "cfghooks.h"
      40              : #include "df.h"
      41              : #include "memmodel.h"
      42              : #include "tm_p.h"
      43              : #include "insn-config.h"
      44              : #include "emit-rtl.h"
      45              : #include "cselib.h"
      46              : #include "tree-pass.h"
      47              : #include "cfgloop.h"
      48              : #include "cfgrtl.h"
      49              : #include "cfganal.h"
      50              : #include "cfgbuild.h"
      51              : #include "cfgcleanup.h"
      52              : #include "dce.h"
      53              : #include "dbgcnt.h"
      54              : #include "rtl-iter.h"
      55              : #include "regs.h"
      56              : #include "function-abi.h"
      57              : 
      58              : #define FORWARDER_BLOCK_P(BB) ((BB)->flags & BB_FORWARDER_BLOCK)
      59              : 
      60              : /* Set to true when we are running first pass of try_optimize_cfg loop.  */
      61              : static bool first_pass;
      62              : 
      63              : /* Set to true if crossjumps occurred in the latest run of try_optimize_cfg.  */
      64              : static bool crossjumps_occurred;
      65              : 
      66              : /* Set to true if we couldn't run an optimization due to stale liveness
      67              :    information; we should run df_analyze to enable more opportunities.  */
      68              : static bool block_was_dirty;
      69              : 
      70              : static bool try_crossjump_to_edge (int, edge, edge, enum replace_direction);
      71              : static bool try_crossjump_bb (int, basic_block);
      72              : static bool outgoing_edges_match (int, basic_block, basic_block);
      73              : static enum replace_direction old_insns_match_p (int, rtx_insn *, rtx_insn *);
      74              : 
      75              : static void merge_blocks_move_predecessor_nojumps (basic_block, basic_block);
      76              : static void merge_blocks_move_successor_nojumps (basic_block, basic_block);
      77              : static bool try_optimize_cfg (int);
      78              : static bool try_simplify_condjump (basic_block);
      79              : static bool try_forward_edges (int, basic_block);
      80              : static edge thread_jump (edge, basic_block);
      81              : static bool mark_effect (rtx, bitmap);
      82              : static void notice_new_block (basic_block);
      83              : static void update_forwarder_flag (basic_block);
      84              : static void merge_memattrs (rtx, rtx);
      85              : 
      86              : /* Set flags for newly created block.  */
      87              : 
      88              : static void
      89        20440 : notice_new_block (basic_block bb)
      90              : {
      91        20440 :   if (!bb)
      92              :     return;
      93              : 
      94        14544 :   if (forwarder_block_p (bb))
      95        14544 :     bb->flags |= BB_FORWARDER_BLOCK;
      96              : }
      97              : 
      98              : /* Recompute forwarder flag after block has been modified.  */
      99              : 
     100              : static void
     101    318457048 : update_forwarder_flag (basic_block bb)
     102              : {
     103    318457048 :   if (forwarder_block_p (bb))
     104     16758214 :     bb->flags |= BB_FORWARDER_BLOCK;
     105              :   else
     106    301698834 :     bb->flags &= ~BB_FORWARDER_BLOCK;
     107    318457048 : }
     108              : 
     109              : /* Simplify a conditional jump around an unconditional jump.
     110              :    Return true if something changed.  */
     111              : 
     112              : static bool
     113     34910945 : try_simplify_condjump (basic_block cbranch_block)
     114              : {
     115     34910945 :   basic_block jump_block, jump_dest_block, cbranch_dest_block;
     116     34910945 :   edge cbranch_jump_edge, cbranch_fallthru_edge;
     117     34910945 :   rtx_insn *cbranch_insn;
     118              : 
     119              :   /* Verify that there are exactly two successors.  */
     120     34910945 :   if (EDGE_COUNT (cbranch_block->succs) != 2)
     121              :     return false;
     122              : 
     123              :   /* Verify that we've got a normal conditional branch at the end
     124              :      of the block.  */
     125     17554980 :   cbranch_insn = BB_END (cbranch_block);
     126     17554980 :   if (!any_condjump_p (cbranch_insn))
     127              :     return false;
     128              : 
     129     15322573 :   cbranch_fallthru_edge = FALLTHRU_EDGE (cbranch_block);
     130     15322573 :   cbranch_jump_edge = BRANCH_EDGE (cbranch_block);
     131              : 
     132              :   /* The next block must not have multiple predecessors, must not
     133              :      be the last block in the function, and must contain just the
     134              :      unconditional jump.  */
     135     15322573 :   jump_block = cbranch_fallthru_edge->dest;
     136     15322573 :   if (!single_pred_p (jump_block)
     137     13614134 :       || jump_block->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun)
     138     28769415 :       || !FORWARDER_BLOCK_P (jump_block))
     139              :     return false;
     140      1697160 :   jump_dest_block = single_succ (jump_block);
     141              : 
     142              :   /* If we are partitioning hot/cold basic blocks, we don't want to
     143              :      mess up unconditional or indirect jumps that cross between hot
     144              :      and cold sections.
     145              : 
     146              :      Basic block partitioning may result in some jumps that appear to
     147              :      be optimizable (or blocks that appear to be mergeable), but which really
     148              :      must be left untouched (they are required to make it safely across
     149              :      partition boundaries).  See the comments at the top of
     150              :      bb-reorder.cc:partition_hot_cold_basic_blocks for complete details.  */
     151              : 
     152      1697160 :   if (BB_PARTITION (jump_block) != BB_PARTITION (jump_dest_block)
     153      1658046 :       || (cbranch_jump_edge->flags & EDGE_CROSSING))
     154              :     return false;
     155              : 
     156              :   /* The conditional branch must target the block after the
     157              :      unconditional branch.  */
     158      1425120 :   cbranch_dest_block = cbranch_jump_edge->dest;
     159              : 
     160      1425120 :   if (cbranch_dest_block == EXIT_BLOCK_PTR_FOR_FN (cfun)
     161      1425120 :       || jump_dest_block == EXIT_BLOCK_PTR_FOR_FN (cfun)
     162      2849413 :       || !can_fallthru (jump_block, cbranch_dest_block))
     163              :     return false;
     164              : 
     165              :   /* Invert the conditional branch.  */
     166         7508 :   if (!invert_jump (as_a <rtx_jump_insn *> (cbranch_insn),
     167         7508 :                     block_label (jump_dest_block), 0))
     168              :     return false;
     169              : 
     170         7508 :   if (dump_file)
     171            1 :     fprintf (dump_file, "Simplifying condjump %i around jump %i\n",
     172            1 :              INSN_UID (cbranch_insn), INSN_UID (BB_END (jump_block)));
     173              : 
     174              :   /* Success.  Update the CFG to match.  Note that after this point
     175              :      the edge variable names appear backwards; the redirection is done
     176              :      this way to preserve edge profile data.  */
     177         7508 :   cbranch_jump_edge = redirect_edge_succ_nodup (cbranch_jump_edge,
     178              :                                                 cbranch_dest_block);
     179         7508 :   cbranch_fallthru_edge = redirect_edge_succ_nodup (cbranch_fallthru_edge,
     180              :                                                     jump_dest_block);
     181         7508 :   cbranch_jump_edge->flags |= EDGE_FALLTHRU;
     182         7508 :   cbranch_fallthru_edge->flags &= ~EDGE_FALLTHRU;
     183         7508 :   update_br_prob_note (cbranch_block);
     184              : 
     185              :   /* Delete the block with the unconditional jump, and clean up the mess.  */
     186         7508 :   delete_basic_block (jump_block);
     187         7508 :   tidy_fallthru_edge (cbranch_jump_edge);
     188         7508 :   update_forwarder_flag (cbranch_block);
     189              : 
     190         7508 :   return true;
     191              : }
     192              : 
     193              : /* Attempt to prove that operation is NOOP using CSElib or mark the effect
     194              :    on register.  Used by jump threading.  */
     195              : 
     196              : static bool
     197     33484258 : mark_effect (rtx exp, regset nonequal)
     198              : {
     199     33484258 :   rtx dest;
     200     33484258 :   switch (GET_CODE (exp))
     201              :     {
     202              :       /* In case we do clobber the register, mark it as equal, as we know the
     203              :          value is dead so it don't have to match.  */
     204      2527540 :     case CLOBBER:
     205      2527540 :       dest = XEXP (exp, 0);
     206      2527540 :       if (REG_P (dest))
     207      2493647 :         bitmap_clear_range (nonequal, REGNO (dest), REG_NREGS (dest));
     208              :       return false;
     209              : 
     210     11252346 :     case SET:
     211     11252346 :       if (cselib_redundant_set_p (exp))
     212              :         return false;
     213     11065538 :       dest = SET_DEST (exp);
     214     11065538 :       if (dest == pc_rtx)
     215              :         return false;
     216     11057666 :       if (!REG_P (dest))
     217              :         return true;
     218     10496682 :       bitmap_set_range (nonequal, REGNO (dest), REG_NREGS (dest));
     219     10496682 :       return false;
     220              : 
     221              :     default:
     222              :       return false;
     223              :     }
     224              : }
     225              : 
     226              : /* Return true if X contains a register in NONEQUAL.  */
     227              : static bool
     228      3617256 : mentions_nonequal_regs (const_rtx x, regset nonequal)
     229              : {
     230      3617256 :   subrtx_iterator::array_type array;
     231      7251396 :   FOR_EACH_SUBRTX (iter, array, x, NONCONST)
     232              :     {
     233      7243524 :       const_rtx x = *iter;
     234      7243524 :       if (REG_P (x))
     235              :         {
     236      3617541 :           unsigned int end_regno = END_REGNO (x);
     237      3625698 :           for (unsigned int regno = REGNO (x); regno < end_regno; ++regno)
     238      3617541 :             if (REGNO_REG_SET_P (nonequal, regno))
     239      3609384 :               return true;
     240              :         }
     241              :     }
     242         7872 :   return false;
     243      3617256 : }
     244              : 
     245              : /* Attempt to prove that the basic block B will have no side effects and
     246              :    always continues in the same edge if reached via E.  Return the edge
     247              :    if exist, NULL otherwise.  */
     248              : 
     249              : static edge
     250     28681485 : thread_jump (edge e, basic_block b)
     251              : {
     252     28681485 :   rtx set1, set2, cond1, cond2;
     253     28681485 :   rtx_insn *insn;
     254     28681485 :   enum rtx_code code1, code2, reversed_code2;
     255     28681485 :   bool reverse1 = false;
     256     28681485 :   unsigned i;
     257     28681485 :   regset nonequal;
     258     28681485 :   bool failed = false;
     259              : 
     260              :   /* Jump threading may cause fixup_partitions to introduce new crossing edges,
     261              :      which is not allowed after reload.  */
     262     28681485 :   gcc_checking_assert (!reload_completed || !crtl->has_bb_partition);
     263              : 
     264     28681485 :   if (b->flags & BB_NONTHREADABLE_BLOCK)
     265              :     return NULL;
     266              : 
     267              :   /* At the moment, we do handle only conditional jumps, but later we may
     268              :      want to extend this code to tablejumps and others.  */
     269     24647429 :   if (EDGE_COUNT (e->src->succs) != 2)
     270              :     return NULL;
     271     17310671 :   if (EDGE_COUNT (b->succs) != 2)
     272              :     {
     273      7633621 :       b->flags |= BB_NONTHREADABLE_BLOCK;
     274      7633621 :       return NULL;
     275              :     }
     276              : 
     277              :   /* Second branch must end with onlyjump, as we will eliminate the jump.  */
     278      9677050 :   if (!any_condjump_p (BB_END (e->src)))
     279              :     return NULL;
     280              : 
     281      8800148 :   if (!any_condjump_p (BB_END (b)) || !onlyjump_p (BB_END (b)))
     282              :     {
     283       649069 :       b->flags |= BB_NONTHREADABLE_BLOCK;
     284       649069 :       return NULL;
     285              :     }
     286              : 
     287      8151079 :   set1 = pc_set (BB_END (e->src));
     288      8151079 :   set2 = pc_set (BB_END (b));
     289      8151079 :   if (((e->flags & EDGE_FALLTHRU) != 0)
     290      8151079 :       != (XEXP (SET_SRC (set1), 1) == pc_rtx))
     291      4043558 :     reverse1 = true;
     292              : 
     293      8151079 :   cond1 = XEXP (SET_SRC (set1), 0);
     294      8151079 :   cond2 = XEXP (SET_SRC (set2), 0);
     295      8151079 :   if (reverse1)
     296      4043558 :     code1 = reversed_comparison_code (cond1, BB_END (e->src));
     297              :   else
     298      4107521 :     code1 = GET_CODE (cond1);
     299              : 
     300      8151079 :   code2 = GET_CODE (cond2);
     301      8151079 :   reversed_code2 = reversed_comparison_code (cond2, BB_END (b));
     302              : 
     303      8151079 :   if (!comparison_dominates_p (code1, code2)
     304      8151079 :       && !comparison_dominates_p (code1, reversed_code2))
     305              :     return NULL;
     306              : 
     307              :   /* Ensure that the comparison operators are equivalent.
     308              :      ??? This is far too pessimistic.  We should allow swapped operands,
     309              :      different CCmodes, or for example comparisons for interval, that
     310              :      dominate even when operands are not equivalent.  */
     311      6555810 :   if (!rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
     312      6555810 :       || !rtx_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
     313              :     return NULL;
     314              : 
     315              :   /* Punt if BB_END (e->src) is doloop-like conditional jump that modifies
     316              :      the registers used in cond1.  */
     317      5622622 :   if (modified_in_p (cond1, BB_END (e->src)))
     318              :     return NULL;
     319              : 
     320              :   /* Short circuit cases where block B contains some side effects, as we can't
     321              :      safely bypass it.  */
     322     64525152 :   for (insn = NEXT_INSN (BB_HEAD (b)); insn != NEXT_INSN (BB_END (b));
     323     53279908 :        insn = NEXT_INSN (insn))
     324     54724290 :     if (INSN_P (insn) && side_effects_p (PATTERN (insn)))
     325              :       {
     326      1444382 :         b->flags |= BB_NONTHREADABLE_BLOCK;
     327      1444382 :         return NULL;
     328              :       }
     329              : 
     330      4178240 :   cselib_init (0);
     331              : 
     332              :   /* First process all values computed in the source basic block.  */
     333     59652222 :   for (insn = NEXT_INSN (BB_HEAD (e->src));
     334     59652222 :        insn != NEXT_INSN (BB_END (e->src));
     335     55473982 :        insn = NEXT_INSN (insn))
     336     55473982 :     if (INSN_P (insn))
     337     51724490 :       cselib_process_insn (insn);
     338              : 
     339      4178240 :   nonequal = BITMAP_ALLOC (NULL);
     340      4178240 :   CLEAR_REG_SET (nonequal);
     341              : 
     342              :   /* Now assume that we've continued by the edge E to B and continue
     343              :      processing as if it were same basic block.
     344              :      Our goal is to prove that whole block is an NOOP.  */
     345              : 
     346     38126183 :   for (insn = NEXT_INSN (BB_HEAD (b));
     347     38126183 :        insn != NEXT_INSN (BB_END (b)) && !failed;
     348     33947943 :        insn = NEXT_INSN (insn))
     349              :     {
     350              :       /* cond2 must not mention any register that is not equal to the
     351              :          former block.  Check this before processing that instruction,
     352              :          as BB_END (b) could contain also clobbers.  */
     353     37557327 :       if (insn == BB_END (b)
     354     37557327 :           && mentions_nonequal_regs (cond2, nonequal))
     355      3609384 :         goto failed_exit;
     356              : 
     357     33947943 :       if (INSN_P (insn))
     358              :         {
     359     30854637 :           rtx pat = PATTERN (insn);
     360              : 
     361     30854637 :           if (GET_CODE (pat) == PARALLEL)
     362              :             {
     363      7704515 :               for (i = 0; i < (unsigned)XVECLEN (pat, 0); i++)
     364      5167068 :                 failed |= mark_effect (XVECEXP (pat, 0, i), nonequal);
     365              :             }
     366              :           else
     367     28317190 :             failed |= mark_effect (pat, nonequal);
     368              :         }
     369              : 
     370     33947943 :       cselib_process_insn (insn);
     371              :     }
     372              : 
     373              :   /* Later we should clear nonequal of dead registers.  So far we don't
     374              :      have life information in cfg_cleanup.  */
     375       568856 :   if (failed)
     376              :     {
     377       560984 :       b->flags |= BB_NONTHREADABLE_BLOCK;
     378       560984 :       goto failed_exit;
     379              :     }
     380              : 
     381         7872 :   if (!REG_SET_EMPTY_P (nonequal))
     382          536 :     goto failed_exit;
     383              : 
     384         7336 :   BITMAP_FREE (nonequal);
     385         7336 :   cselib_finish ();
     386         7336 :   if ((comparison_dominates_p (code1, code2) != 0)
     387         7336 :       != (XEXP (SET_SRC (set2), 1) == pc_rtx))
     388         5125 :     return BRANCH_EDGE (b);
     389              :   else
     390         2211 :     return FALLTHRU_EDGE (b);
     391              : 
     392      4170904 : failed_exit:
     393      4170904 :   BITMAP_FREE (nonequal);
     394      4170904 :   cselib_finish ();
     395      4170904 :   return NULL;
     396              : }
     397              : 
     398              : /* Attempt to forward edges leaving basic block B.
     399              :    Return true if successful.  */
     400              : 
     401              : static bool
     402    406953095 : try_forward_edges (int mode, basic_block b)
     403              : {
     404    406953095 :   bool changed = false;
     405    406953095 :   edge_iterator ei;
     406    406953095 :   edge e, *threaded_edges = NULL;
     407              : 
     408   1020348600 :   for (ei = ei_start (b->succs); (e = ei_safe_edge (ei)); )
     409              :     {
     410    613395505 :       basic_block target, first;
     411    613395505 :       location_t goto_locus;
     412    613395505 :       int counter;
     413    613395505 :       bool threaded = false;
     414    613395505 :       int nthreaded_edges = 0;
     415    613395505 :       bool may_thread = first_pass || (b->flags & BB_MODIFIED) != 0;
     416    613395505 :       bool new_target_threaded = false;
     417              : 
     418              :       /* Skip complex edges because we don't know how to update them.
     419              : 
     420              :          Still handle fallthru edges, as we can succeed to forward fallthru
     421              :          edge to the same place as the branch edge of conditional branch
     422              :          and turn conditional branch to an unconditional branch.  */
     423    613395505 :       if (e->flags & EDGE_COMPLEX)
     424              :         {
     425     35111863 :           ei_next (&ei);
     426     35111863 :           continue;
     427              :         }
     428              : 
     429    578283642 :       target = first = e->dest;
     430    578283642 :       counter = NUM_FIXED_BLOCKS;
     431    578283642 :       goto_locus = e->goto_locus;
     432              : 
     433    608093152 :       while (counter < n_basic_blocks_for_fn (cfun))
     434              :         {
     435    607691924 :           basic_block new_target = NULL;
     436    607691924 :           may_thread |= (target->flags & BB_MODIFIED) != 0;
     437              : 
     438    607691924 :           if (FORWARDER_BLOCK_P (target)
     439    647062844 :               && single_succ (target) != EXIT_BLOCK_PTR_FOR_FN (cfun))
     440              :             {
     441              :               /* Bypass trivial infinite loops.  */
     442     29994839 :               new_target = single_succ (target);
     443     29994839 :               if (target == new_target)
     444              :                 counter = n_basic_blocks_for_fn (cfun);
     445     29732585 :               else if (!optimize)
     446              :                 {
     447              :                   /* When not optimizing, ensure that edges or forwarder
     448              :                      blocks with different locus are not optimized out.  */
     449      1196257 :                   location_t new_locus = single_succ_edge (target)->goto_locus;
     450      1196257 :                   location_t locus = goto_locus;
     451              : 
     452      1196257 :                   if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION
     453       477814 :                       && LOCATION_LOCUS (locus) != UNKNOWN_LOCATION
     454      1510546 :                       && new_locus != locus)
     455              :                     new_target = NULL;
     456              :                   else
     457              :                     {
     458      1013556 :                       if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION)
     459       295113 :                         locus = new_locus;
     460              : 
     461      1013556 :                       rtx_insn *last = BB_END (target);
     462      1013556 :                       if (DEBUG_INSN_P (last))
     463            6 :                         last = prev_nondebug_insn (last);
     464      1013556 :                       if (last && INSN_P (last))
     465       503541 :                         new_locus = INSN_LOCATION (last);
     466              :                       else
     467              :                         new_locus = UNKNOWN_LOCATION;
     468              : 
     469       503541 :                       if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION
     470       486363 :                           && LOCATION_LOCUS (locus) != UNKNOWN_LOCATION
     471      1385499 :                           && new_locus != locus)
     472              :                         new_target = NULL;
     473              :                       else
     474              :                         {
     475      1004962 :                           if (LOCATION_LOCUS (new_locus) != UNKNOWN_LOCATION)
     476       477769 :                             locus = new_locus;
     477              : 
     478              :                           goto_locus = locus;
     479              :                         }
     480              :                     }
     481              :                 }
     482              :             }
     483              : 
     484              :           /* Allow to thread only over one edge at time to simplify updating
     485              :              of probabilities.  */
     486    577697085 :           else if ((mode & CLEANUP_THREADING) && may_thread)
     487              :             {
     488     28681485 :               edge t = thread_jump (e, target);
     489     28681485 :               if (t)
     490              :                 {
     491         7336 :                   if (!threaded_edges)
     492         7262 :                     threaded_edges = XNEWVEC (edge,
     493              :                                               n_basic_blocks_for_fn (cfun));
     494              :                   else
     495              :                     {
     496              :                       int i;
     497              : 
     498              :                       /* Detect an infinite loop across blocks not
     499              :                          including the start block.  */
     500          221 :                       for (i = 0; i < nthreaded_edges; ++i)
     501          166 :                         if (threaded_edges[i] == t)
     502              :                           break;
     503           74 :                       if (i < nthreaded_edges)
     504              :                         {
     505           19 :                           counter = n_basic_blocks_for_fn (cfun);
     506           19 :                           break;
     507              :                         }
     508              :                     }
     509              : 
     510              :                   /* Detect an infinite loop across the start block.  */
     511         7317 :                   if (t->dest == b)
     512              :                     break;
     513              : 
     514         5966 :                   gcc_assert (nthreaded_edges
     515              :                               < (n_basic_blocks_for_fn (cfun)
     516              :                                  - NUM_FIXED_BLOCKS));
     517         5966 :                   threaded_edges[nthreaded_edges++] = t;
     518              : 
     519         5966 :                   new_target = t->dest;
     520         5966 :                   new_target_threaded = true;
     521              :                 }
     522              :             }
     523              : 
     524     29809510 :           if (!new_target)
     525              :             break;
     526              : 
     527     29809510 :           counter++;
     528              :           /* Do not turn non-crossing jump to crossing.  Depending on target
     529              :              it may require different instruction pattern.  */
     530     29809510 :           if ((e->flags & EDGE_CROSSING)
     531     29776801 :               || BB_PARTITION (first) == BB_PARTITION (new_target))
     532              :             {
     533     15335204 :               target = new_target;
     534     15335204 :               threaded |= new_target_threaded;
     535              :             }
     536              :         }
     537              : 
     538    578283642 :       if (counter >= n_basic_blocks_for_fn (cfun))
     539              :         {
     540       401247 :           if (dump_file)
     541            4 :             fprintf (dump_file, "Infinite loop in BB %i.\n",
     542              :                      target->index);
     543              :         }
     544    577882395 :       else if (target == first)
     545              :         ; /* We didn't do anything.  */
     546              :       else
     547              :         {
     548              :           /* Save the values now, as the edge may get removed.  */
     549     14200256 :           profile_count edge_count = e->count ();
     550     14200256 :           int n = 0;
     551              : 
     552     14200256 :           e->goto_locus = goto_locus;
     553              : 
     554              :           /* Don't force if target is exit block.  */
     555     14200256 :           if (threaded && target != EXIT_BLOCK_PTR_FOR_FN (cfun))
     556              :             {
     557         5896 :               notice_new_block (redirect_edge_and_branch_force (e, target));
     558         5896 :               if (dump_file)
     559            0 :                 fprintf (dump_file, "Conditionals threaded.\n");
     560              :             }
     561     14194360 :           else if (!redirect_edge_and_branch (e, target))
     562              :             {
     563      7503889 :               if (dump_file)
     564          183 :                 fprintf (dump_file,
     565              :                          "Forwarding edge %i->%i to %i failed.\n",
     566          183 :                          b->index, e->dest->index, target->index);
     567      7503889 :               ei_next (&ei);
     568      7503889 :               continue;
     569              :             }
     570              : 
     571              :           /* We successfully forwarded the edge.  Now update profile
     572              :              data: for each edge we traversed in the chain, remove
     573              :              the original edge's execution count.  */
     574      6824106 :           do
     575              :             {
     576      6824106 :               edge t;
     577              : 
     578      6824106 :               if (!single_succ_p (first))
     579              :                 {
     580         5947 :                   gcc_assert (n < nthreaded_edges);
     581         5947 :                   t = threaded_edges [n++];
     582         5947 :                   gcc_assert (t->src == first);
     583         5947 :                   update_bb_profile_for_threading (first, edge_count, t);
     584         5947 :                   update_br_prob_note (first);
     585              :                 }
     586              :               else
     587              :                 {
     588      6818159 :                   first->count -= edge_count;
     589              :                   /* It is possible that as the result of
     590              :                      threading we've removed edge as it is
     591              :                      threaded to the fallthru edge.  Avoid
     592              :                      getting out of sync.  */
     593      6818159 :                   if (n < nthreaded_edges
     594            0 :                       && first == threaded_edges [n]->src)
     595            0 :                     n++;
     596      6818159 :                   t = single_succ_edge (first);
     597              :                 }
     598              : 
     599      6824106 :               first = t->dest;
     600              :             }
     601      6824106 :           while (first != target);
     602              : 
     603      6696367 :           changed = true;
     604      6696367 :           continue;
     605      6696367 :         }
     606    564083386 :       ei_next (&ei);
     607              :     }
     608              : 
     609    406953095 :   free (threaded_edges);
     610    406953095 :   return changed;
     611              : }
     612              : 
     613              : 
     614              : /* Blocks A and B are to be merged into a single block.  A has no incoming
     615              :    fallthru edge, so it can be moved before B without adding or modifying
     616              :    any jumps (aside from the jump from A to B).  */
     617              : 
     618              : static void
     619        21160 : merge_blocks_move_predecessor_nojumps (basic_block a, basic_block b)
     620              : {
     621        21160 :   rtx_insn *barrier;
     622              : 
     623              :   /* If we are partitioning hot/cold basic blocks, we don't want to
     624              :      mess up unconditional or indirect jumps that cross between hot
     625              :      and cold sections.
     626              : 
     627              :      Basic block partitioning may result in some jumps that appear to
     628              :      be optimizable (or blocks that appear to be mergeable), but which really
     629              :      must be left untouched (they are required to make it safely across
     630              :      partition boundaries).  See the comments at the top of
     631              :      bb-reorder.cc:partition_hot_cold_basic_blocks for complete details.  */
     632              : 
     633        21160 :   if (BB_PARTITION (a) != BB_PARTITION (b))
     634              :     return;
     635              : 
     636        21160 :   barrier = next_nonnote_insn (BB_END (a));
     637        21160 :   gcc_assert (BARRIER_P (barrier));
     638        21160 :   delete_insn (barrier);
     639              : 
     640              :   /* Scramble the insn chain.  */
     641        21160 :   if (BB_END (a) != PREV_INSN (BB_HEAD (b)))
     642        21127 :     reorder_insns_nobb (BB_HEAD (a), BB_END (a), PREV_INSN (BB_HEAD (b)));
     643        21160 :   df_set_bb_dirty (a);
     644              : 
     645        21160 :   if (dump_file)
     646            0 :     fprintf (dump_file, "Moved block %d before %d and merged.\n",
     647              :              a->index, b->index);
     648              : 
     649              :   /* Swap the records for the two blocks around.  */
     650              : 
     651        21160 :   unlink_block (a);
     652        21160 :   link_block (a, b->prev_bb);
     653              : 
     654              :   /* Now blocks A and B are contiguous.  Merge them.  */
     655        21160 :   merge_blocks (a, b);
     656              : }
     657              : 
     658              : /* Blocks A and B are to be merged into a single block.  B has no outgoing
     659              :    fallthru edge, so it can be moved after A without adding or modifying
     660              :    any jumps (aside from the jump from A to B).  */
     661              : 
     662              : static void
     663        30444 : merge_blocks_move_successor_nojumps (basic_block a, basic_block b)
     664              : {
     665        30444 :   rtx_insn *barrier, *real_b_end;
     666        30444 :   rtx_insn *label;
     667        30444 :   rtx_jump_table_data *table;
     668              : 
     669              :   /* If we are partitioning hot/cold basic blocks, we don't want to
     670              :      mess up unconditional or indirect jumps that cross between hot
     671              :      and cold sections.
     672              : 
     673              :      Basic block partitioning may result in some jumps that appear to
     674              :      be optimizable (or blocks that appear to be mergeable), but which really
     675              :      must be left untouched (they are required to make it safely across
     676              :      partition boundaries).  See the comments at the top of
     677              :      bb-reorder.cc:partition_hot_cold_basic_blocks for complete details.  */
     678              : 
     679        30444 :   if (BB_PARTITION (a) != BB_PARTITION (b))
     680            0 :     return;
     681              : 
     682        30444 :   real_b_end = BB_END (b);
     683              : 
     684              :   /* If there is a jump table following block B temporarily add the jump table
     685              :      to block B so that it will also be moved to the correct location.  */
     686        30444 :   if (tablejump_p (BB_END (b), &label, &table)
     687        30444 :       && prev_active_insn (label) == BB_END (b))
     688              :     {
     689            0 :       BB_END (b) = table;
     690              :     }
     691              : 
     692              :   /* There had better have been a barrier there.  Delete it.  */
     693        30444 :   barrier = NEXT_INSN (BB_END (b));
     694        30444 :   if (barrier && BARRIER_P (barrier))
     695        30444 :     delete_insn (barrier);
     696              : 
     697              : 
     698              :   /* Scramble the insn chain.  */
     699        30444 :   reorder_insns_nobb (BB_HEAD (b), BB_END (b), BB_END (a));
     700              : 
     701              :   /* Restore the real end of b.  */
     702        30444 :   BB_END (b) = real_b_end;
     703              : 
     704        30444 :   if (dump_file)
     705           22 :     fprintf (dump_file, "Moved block %d after %d and merged.\n",
     706              :              b->index, a->index);
     707              : 
     708              :   /* Now blocks A and B are contiguous.  Merge them.  */
     709        30444 :   merge_blocks (a, b);
     710              : }
     711              : 
     712              : /* Attempt to merge basic blocks that are potentially non-adjacent.
     713              :    Return NULL iff the attempt failed, otherwise return basic block
     714              :    where cleanup_cfg should continue.  Because the merging commonly
     715              :    moves basic block away or introduces another optimization
     716              :    possibility, return basic block just before B so cleanup_cfg don't
     717              :    need to iterate.
     718              : 
     719              :    It may be good idea to return basic block before C in the case
     720              :    C has been moved after B and originally appeared earlier in the
     721              :    insn sequence, but we have no information available about the
     722              :    relative ordering of these two.  Hopefully it is not too common.  */
     723              : 
     724              : static basic_block
     725      6886398 : merge_blocks_move (edge e, basic_block b, basic_block c, int mode)
     726              : {
     727      6886398 :   basic_block next;
     728              : 
     729              :   /* If we are partitioning hot/cold basic blocks, we don't want to
     730              :      mess up unconditional or indirect jumps that cross between hot
     731              :      and cold sections.
     732              : 
     733              :      Basic block partitioning may result in some jumps that appear to
     734              :      be optimizable (or blocks that appear to be mergeable), but which really
     735              :      must be left untouched (they are required to make it safely across
     736              :      partition boundaries).  See the comments at the top of
     737              :      bb-reorder.cc:partition_hot_cold_basic_blocks for complete details.  */
     738              : 
     739      6886398 :   if (BB_PARTITION (b) != BB_PARTITION (c))
     740              :     return NULL;
     741              : 
     742              :   /* If B has a fallthru edge to C, no need to move anything.  */
     743      6541298 :   if (e->flags & EDGE_FALLTHRU)
     744              :     {
     745      3854360 :       int b_index = b->index, c_index = c->index;
     746              : 
     747              :       /* Protect the loop latches.  */
     748      3854360 :       if (current_loops && c->loop_father->latch == c)
     749              :         return NULL;
     750              : 
     751      3809395 :       merge_blocks (b, c);
     752      3809395 :       update_forwarder_flag (b);
     753              : 
     754      3809395 :       if (dump_file)
     755          898 :         fprintf (dump_file, "Merged %d and %d without moving.\n",
     756              :                  b_index, c_index);
     757              : 
     758      3809395 :       return b->prev_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? b : b->prev_bb;
     759              :     }
     760              : 
     761              :   /* Otherwise we will need to move code around.  Do that only if expensive
     762              :      transformations are allowed.  */
     763      2686938 :   else if (mode & CLEANUP_EXPENSIVE)
     764              :     {
     765       892260 :       edge tmp_edge, b_fallthru_edge;
     766       892260 :       bool c_has_outgoing_fallthru;
     767       892260 :       bool b_has_incoming_fallthru;
     768              : 
     769              :       /* Avoid overactive code motion, as the forwarder blocks should be
     770              :          eliminated by edge redirection instead.  One exception might have
     771              :          been if B is a forwarder block and C has no fallthru edge, but
     772              :          that should be cleaned up by bb-reorder instead.  */
     773       892260 :       if (FORWARDER_BLOCK_P (b) || FORWARDER_BLOCK_P (c))
     774              :         return NULL;
     775              : 
     776              :       /* We must make sure to not munge nesting of lexical blocks,
     777              :          and loop notes.  This is done by squeezing out all the notes
     778              :          and leaving them there to lie.  Not ideal, but functional.  */
     779              : 
     780        53750 :       tmp_edge = find_fallthru_edge (c->succs);
     781        53750 :       c_has_outgoing_fallthru = (tmp_edge != NULL);
     782              : 
     783        53750 :       tmp_edge = find_fallthru_edge (b->preds);
     784        53750 :       b_has_incoming_fallthru = (tmp_edge != NULL);
     785        53750 :       b_fallthru_edge = tmp_edge;
     786        53750 :       next = b->prev_bb;
     787        53750 :       if (next == c)
     788           63 :         next = next->prev_bb;
     789              : 
     790              :       /* Otherwise, we're going to try to move C after B.  If C does
     791              :          not have an outgoing fallthru, then it can be moved
     792              :          immediately after B without introducing or modifying jumps.  */
     793        53750 :       if (! c_has_outgoing_fallthru)
     794              :         {
     795        30444 :           merge_blocks_move_successor_nojumps (b, c);
     796        30444 :           return next == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? next->next_bb : next;
     797              :         }
     798              : 
     799              :       /* If B does not have an incoming fallthru, then it can be moved
     800              :          immediately before C without introducing or modifying jumps.
     801              :          C cannot be the first block, so we do not have to worry about
     802              :          accessing a non-existent block.  */
     803              : 
     804        23306 :       if (b_has_incoming_fallthru)
     805              :         {
     806        21144 :           basic_block bb;
     807              : 
     808        21144 :           if (b_fallthru_edge->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
     809              :             return NULL;
     810        18998 :           bb = force_nonfallthru (b_fallthru_edge);
     811        18998 :           if (bb)
     812        14544 :             notice_new_block (bb);
     813              :         }
     814              : 
     815        21160 :       merge_blocks_move_predecessor_nojumps (b, c);
     816        21160 :       return next == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? next->next_bb : next;
     817              :     }
     818              : 
     819              :   return NULL;
     820              : }
     821              : 
     822              : 
     823              : /* Removes the memory attributes of MEM expression
     824              :    if they are not equal.  */
     825              : 
     826              : static void
     827    149298290 : merge_memattrs (rtx x, rtx y)
     828              : {
     829    149298290 :   int i;
     830    149298290 :   int j;
     831    149298290 :   enum rtx_code code;
     832    149298290 :   const char *fmt;
     833              : 
     834    149298290 :   if (x == y)
     835              :     return;
     836    111445578 :   if (x == 0 || y == 0)
     837              :     return;
     838              : 
     839    111407893 :   code = GET_CODE (x);
     840              : 
     841    111407893 :   if (code != GET_CODE (y))
     842              :     return;
     843              : 
     844    111407881 :   if (GET_MODE (x) != GET_MODE (y))
     845              :     return;
     846              : 
     847    111404716 :   if (code == MEM && !mem_attrs_eq_p (MEM_ATTRS (x), MEM_ATTRS (y)))
     848              :     {
     849        47605 :       if (! MEM_ATTRS (x))
     850          870 :         MEM_ATTRS (y) = 0;
     851        46735 :       else if (! MEM_ATTRS (y))
     852         1361 :         MEM_ATTRS (x) = 0;
     853              :       else
     854              :         {
     855        45374 :           if (MEM_ALIAS_SET (x) != MEM_ALIAS_SET (y))
     856              :             {
     857         2694 :               set_mem_alias_set (x, 0);
     858         2694 :               set_mem_alias_set (y, 0);
     859              :             }
     860              : 
     861        45374 :           if (! mem_expr_equal_p (MEM_EXPR (x), MEM_EXPR (y)))
     862              :             {
     863        44769 :               set_mem_expr (x, 0);
     864        44769 :               set_mem_expr (y, 0);
     865        44769 :               clear_mem_offset (x);
     866        44769 :               clear_mem_offset (y);
     867              :             }
     868          605 :           else if (MEM_OFFSET_KNOWN_P (x) != MEM_OFFSET_KNOWN_P (y)
     869          605 :                    || (MEM_OFFSET_KNOWN_P (x)
     870            0 :                        && maybe_ne (MEM_OFFSET (x), MEM_OFFSET (y))))
     871              :             {
     872            0 :               clear_mem_offset (x);
     873            0 :               clear_mem_offset (y);
     874              :             }
     875              : 
     876        52260 :           if (!MEM_SIZE_KNOWN_P (x))
     877          221 :             clear_mem_size (y);
     878        51860 :           else if (!MEM_SIZE_KNOWN_P (y))
     879            8 :             clear_mem_size (x);
     880        45145 :           else if (known_le (MEM_SIZE (x), MEM_SIZE (y)))
     881        45101 :             set_mem_size (x, MEM_SIZE (y));
     882           44 :           else if (known_le (MEM_SIZE (y), MEM_SIZE (x)))
     883           44 :             set_mem_size (y, MEM_SIZE (x));
     884              :           else
     885              :             {
     886              :               /* The sizes aren't ordered, so we can't merge them.  */
     887              :               clear_mem_size (x);
     888              :               clear_mem_size (y);
     889              :             }
     890              : 
     891        59190 :           set_mem_align (x, MIN (MEM_ALIGN (x), MEM_ALIGN (y)));
     892        52304 :           set_mem_align (y, MEM_ALIGN (x));
     893              :         }
     894              :     }
     895    111404716 :   if (code == MEM)
     896              :     {
     897      6100692 :       if (MEM_READONLY_P (x) != MEM_READONLY_P (y))
     898              :         {
     899            0 :           MEM_READONLY_P (x) = 0;
     900            0 :           MEM_READONLY_P (y) = 0;
     901              :         }
     902      6100692 :       if (MEM_NOTRAP_P (x) != MEM_NOTRAP_P (y))
     903              :         {
     904          284 :           MEM_NOTRAP_P (x) = 0;
     905          284 :           MEM_NOTRAP_P (y) = 0;
     906              :         }
     907      6100692 :       if (MEM_VOLATILE_P (x) != MEM_VOLATILE_P (y))
     908              :         {
     909          150 :           MEM_VOLATILE_P (x) = 1;
     910          150 :           MEM_VOLATILE_P (y) = 1;
     911              :         }
     912              :     }
     913              : 
     914    111404716 :   fmt = GET_RTX_FORMAT (code);
     915    338368301 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     916              :     {
     917    226963585 :       switch (fmt[i])
     918              :         {
     919       395996 :         case 'E':
     920              :           /* Two vectors must have the same length.  */
     921       395996 :           if (XVECLEN (x, i) != XVECLEN (y, i))
     922              :             return;
     923              : 
     924      1170869 :           for (j = 0; j < XVECLEN (x, i); j++)
     925       774873 :             merge_memattrs (XVECEXP (x, i, j), XVECEXP (y, i, j));
     926              : 
     927              :           break;
     928              : 
     929    139747168 :         case 'e':
     930    139747168 :           merge_memattrs (XEXP (x, i), XEXP (y, i));
     931              :         }
     932              :     }
     933              :   return;
     934              : }
     935              : 
     936              : 
     937              :  /* Checks if patterns P1 and P2 are equivalent, apart from the possibly
     938              :     different single sets S1 and S2.  */
     939              : 
     940              : static bool
     941          110 : equal_different_set_p (rtx p1, rtx s1, rtx p2, rtx s2)
     942              : {
     943          110 :   int i;
     944          110 :   rtx e1, e2;
     945              : 
     946          110 :   if (p1 == s1 && p2 == s2)
     947              :     return true;
     948              : 
     949            0 :   if (GET_CODE (p1) != PARALLEL || GET_CODE (p2) != PARALLEL)
     950              :     return false;
     951              : 
     952            0 :   if (XVECLEN (p1, 0) != XVECLEN (p2, 0))
     953              :     return false;
     954              : 
     955            0 :   for (i = 0; i < XVECLEN (p1, 0); i++)
     956              :     {
     957            0 :       e1 = XVECEXP (p1, 0, i);
     958            0 :       e2 = XVECEXP (p2, 0, i);
     959            0 :       if (e1 == s1 && e2 == s2)
     960            0 :         continue;
     961            0 :       if (reload_completed
     962            0 :           ? rtx_renumbered_equal_p (e1, e2) : rtx_equal_p (e1, e2))
     963            0 :         continue;
     964              : 
     965              :       return false;
     966              :     }
     967              : 
     968              :   return true;
     969              : }
     970              : 
     971              : 
     972              : /* NOTE1 is the REG_EQUAL note, if any, attached to an insn
     973              :    that is a single_set with a SET_SRC of SRC1.  Similarly
     974              :    for NOTE2/SRC2.
     975              : 
     976              :    So effectively NOTE1/NOTE2 are an alternate form of
     977              :    SRC1/SRC2 respectively.
     978              : 
     979              :    Return nonzero if SRC1 or NOTE1 has the same constant
     980              :    integer value as SRC2 or NOTE2.   Else return zero.  */
     981              : static int
     982      7963918 : values_equal_p (rtx note1, rtx note2, rtx src1, rtx src2)
     983              : {
     984      7963918 :   if (note1
     985      7963918 :       && note2
     986      1285359 :       && CONST_INT_P (XEXP (note1, 0))
     987      8021360 :       && rtx_equal_p (XEXP (note1, 0), XEXP (note2, 0)))
     988              :     return 1;
     989              : 
     990      7963810 :   if (!note1
     991      7963810 :       && !note2
     992      6208186 :       && CONST_INT_P (src1)
     993      2680879 :       && CONST_INT_P (src2)
     994     10544485 :       && rtx_equal_p (src1, src2))
     995              :     return 1;
     996              : 
     997      7963810 :   if (note1
     998      1560740 :       && CONST_INT_P (src2)
     999      8112178 :       && rtx_equal_p (XEXP (note1, 0), src2))
    1000              :     return 1;
    1001              : 
    1002      7963810 :   if (note2
    1003      1480135 :       && CONST_INT_P (src1)
    1004      8034015 :       && rtx_equal_p (XEXP (note2, 0), src1))
    1005            2 :     return 1;
    1006              : 
    1007              :   return 0;
    1008              : }
    1009              : 
    1010              : /* Examine register notes on I1 and I2 and return:
    1011              :    - dir_forward if I1 can be replaced by I2, or
    1012              :    - dir_backward if I2 can be replaced by I1, or
    1013              :    - dir_both if both are the case.  */
    1014              : 
    1015              : static enum replace_direction
    1016     14100128 : can_replace_by (rtx_insn *i1, rtx_insn *i2)
    1017              : {
    1018     14100128 :   rtx s1, s2, d1, d2, src1, src2, note1, note2;
    1019     14100128 :   bool c1, c2;
    1020              : 
    1021              :   /* Check for 2 sets.  */
    1022     14100128 :   s1 = single_set (i1);
    1023     14100128 :   s2 = single_set (i2);
    1024     14100128 :   if (s1 == NULL_RTX || s2 == NULL_RTX)
    1025              :     return dir_none;
    1026              : 
    1027              :   /* Check that the 2 sets set the same dest.  */
    1028     13333469 :   d1 = SET_DEST (s1);
    1029     13333469 :   d2 = SET_DEST (s2);
    1030     26666938 :   if (!(reload_completed
    1031     13333469 :         ? rtx_renumbered_equal_p (d1, d2) : rtx_equal_p (d1, d2)))
    1032              :     return dir_none;
    1033              : 
    1034              :   /* Find identical req_equiv or reg_equal note, which implies that the 2 sets
    1035              :      set dest to the same value.  */
    1036      7963918 :   note1 = find_reg_equal_equiv_note (i1);
    1037      7963918 :   note2 = find_reg_equal_equiv_note (i2);
    1038              : 
    1039      7963918 :   src1 = SET_SRC (s1);
    1040      7963918 :   src2 = SET_SRC (s2);
    1041              : 
    1042      7963918 :   if (!values_equal_p (note1, note2, src1, src2))
    1043              :     return dir_none;
    1044              : 
    1045          110 :   if (!equal_different_set_p (PATTERN (i1), s1, PATTERN (i2), s2))
    1046              :     return dir_none;
    1047              : 
    1048              :   /* Although the 2 sets set dest to the same value, we cannot replace
    1049              :        (set (dest) (const_int))
    1050              :      by
    1051              :        (set (dest) (reg))
    1052              :      because we don't know if the reg is live and has the same value at the
    1053              :      location of replacement.  */
    1054          110 :   c1 = CONST_INT_P (src1);
    1055          110 :   c2 = CONST_INT_P (src2);
    1056          110 :   if (c1 && c2)
    1057              :     return dir_both;
    1058          110 :   else if (c2)
    1059              :     return dir_forward;
    1060          110 :   else if (c1)
    1061            2 :     return dir_backward;
    1062              : 
    1063              :   return dir_none;
    1064              : }
    1065              : 
    1066              : /* Merges directions A and B.  */
    1067              : 
    1068              : static enum replace_direction
    1069     23762402 : merge_dir (enum replace_direction a, enum replace_direction b)
    1070              : {
    1071              :   /* Implements the following table:
    1072              :         |bo fw bw no
    1073              :      ---+-----------
    1074              :      bo |bo fw bw no
    1075              :      fw |-- fw no no
    1076              :      bw |-- -- bw no
    1077              :      no |-- -- -- no.  */
    1078              : 
    1079            0 :   if (a == b)
    1080              :     return a;
    1081              : 
    1082     16327796 :   if (a == dir_both)
    1083              :     return b;
    1084      3894514 :   if (b == dir_both)
    1085            0 :     return a;
    1086              : 
    1087              :   return dir_none;
    1088              : }
    1089              : 
    1090              : /* Array of flags indexed by reg note kind, true if the given
    1091              :    reg note is CFA related.  */
    1092              : static const bool reg_note_cfa_p[] = {
    1093              : #undef REG_CFA_NOTE
    1094              : #define DEF_REG_NOTE(NAME) false,
    1095              : #define REG_CFA_NOTE(NAME) true,
    1096              : #include "reg-notes.def"
    1097              : #undef REG_CFA_NOTE
    1098              : #undef DEF_REG_NOTE
    1099              :   false
    1100              : };
    1101              : 
    1102              : /* Return true if I1 and I2 have identical CFA notes (the same order
    1103              :    and equivalent content).  */
    1104              : 
    1105              : static bool
    1106       615776 : insns_have_identical_cfa_notes (rtx_insn *i1, rtx_insn *i2)
    1107              : {
    1108       615776 :   rtx n1, n2;
    1109       615776 :   for (n1 = REG_NOTES (i1), n2 = REG_NOTES (i2); ;
    1110       488120 :        n1 = XEXP (n1, 1), n2 = XEXP (n2, 1))
    1111              :     {
    1112              :       /* Skip over reg notes not related to CFI information.  */
    1113      1617092 :       while (n1 && !reg_note_cfa_p[REG_NOTE_KIND (n1)])
    1114        25076 :         n1 = XEXP (n1, 1);
    1115      1127388 :       while (n2 && !reg_note_cfa_p[REG_NOTE_KIND (n2)])
    1116        23492 :         n2 = XEXP (n2, 1);
    1117      1103896 :       if (n1 == NULL_RTX && n2 == NULL_RTX)
    1118              :         return true;
    1119       599772 :       if (n1 == NULL_RTX || n2 == NULL_RTX)
    1120              :         return false;
    1121       594907 :       if (XEXP (n1, 0) == XEXP (n2, 0))
    1122              :         ;
    1123       594901 :       else if (XEXP (n1, 0) == NULL_RTX || XEXP (n2, 0) == NULL_RTX)
    1124              :         return false;
    1125      1189802 :       else if (!(reload_completed
    1126       594901 :                  ? rtx_renumbered_equal_p (XEXP (n1, 0), XEXP (n2, 0))
    1127            0 :                  : rtx_equal_p (XEXP (n1, 0), XEXP (n2, 0))))
    1128              :         return false;
    1129              :     }
    1130              : }
    1131              : 
    1132              : /* Examine I1 and I2 and return:
    1133              :    - dir_forward if I1 can be replaced by I2, or
    1134              :    - dir_backward if I2 can be replaced by I1, or
    1135              :    - dir_both if both are the case.  */
    1136              : 
    1137              : static enum replace_direction
    1138     41032841 : old_insns_match_p (int mode ATTRIBUTE_UNUSED, rtx_insn *i1, rtx_insn *i2)
    1139              : {
    1140     41032841 :   rtx p1, p2;
    1141              : 
    1142              :   /* Verify that I1 and I2 are equivalent.  */
    1143     41032841 :   if (GET_CODE (i1) != GET_CODE (i2))
    1144              :     return dir_none;
    1145              : 
    1146              :   /* __builtin_unreachable() may lead to empty blocks (ending with
    1147              :      NOTE_INSN_BASIC_BLOCK).  They may be crossjumped. */
    1148     35513573 :   if (NOTE_INSN_BASIC_BLOCK_P (i1) && NOTE_INSN_BASIC_BLOCK_P (i2))
    1149              :     return dir_both;
    1150              : 
    1151              :   /* ??? Do not allow cross-jumping between different stack levels.  */
    1152     35339253 :   p1 = find_reg_note (i1, REG_ARGS_SIZE, NULL);
    1153     35339253 :   p2 = find_reg_note (i2, REG_ARGS_SIZE, NULL);
    1154     35339253 :   if (p1 && p2)
    1155              :     {
    1156      3986335 :       p1 = XEXP (p1, 0);
    1157      3986335 :       p2 = XEXP (p2, 0);
    1158      3986335 :       if (!rtx_equal_p (p1, p2))
    1159              :         return dir_none;
    1160              : 
    1161              :       /* ??? Worse, this adjustment had better be constant lest we
    1162              :          have differing incoming stack levels.  */
    1163      3885242 :       if (!frame_pointer_needed
    1164      3885242 :           && known_eq (find_args_size_adjust (i1), HOST_WIDE_INT_MIN))
    1165           27 :         return dir_none;
    1166              :     }
    1167     31352918 :   else if (p1 || p2)
    1168              :     return dir_none;
    1169              : 
    1170              :   /* Do not allow cross-jumping between frame related insns and other
    1171              :      insns.  */
    1172     33627230 :   if (RTX_FRAME_RELATED_P (i1) != RTX_FRAME_RELATED_P (i2))
    1173              :     return dir_none;
    1174              : 
    1175     33185081 :   p1 = PATTERN (i1);
    1176     33185081 :   p2 = PATTERN (i2);
    1177              : 
    1178     33185081 :   if (GET_CODE (p1) != GET_CODE (p2))
    1179              :     return dir_none;
    1180              : 
    1181              :   /* If this is a CALL_INSN, compare register usage information.
    1182              :      If we don't check this on stack register machines, the two
    1183              :      CALL_INSNs might be merged leaving reg-stack.cc with mismatching
    1184              :      numbers of stack registers in the same basic block.
    1185              :      If we don't check this on machines with delay slots, a delay slot may
    1186              :      be filled that clobbers a parameter expected by the subroutine.
    1187              : 
    1188              :      ??? We take the simple route for now and assume that if they're
    1189              :      equal, they were constructed identically.
    1190              : 
    1191              :      Also check for identical exception regions.  */
    1192              : 
    1193     30631926 :   if (auto call1 = dyn_cast<rtx_call_insn *> (i1))
    1194              :     {
    1195              :       /* Ensure the same EH region.  */
    1196     12291965 :       rtx n1 = find_reg_note (i1, REG_EH_REGION, 0);
    1197     12291965 :       rtx n2 = find_reg_note (i2, REG_EH_REGION, 0);
    1198              : 
    1199     12291965 :       if (!n1 && n2)
    1200              :         return dir_none;
    1201              : 
    1202     12204083 :       if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
    1203              :         return dir_none;
    1204              : 
    1205     11300334 :       if (!rtx_equal_p (CALL_INSN_FUNCTION_USAGE (call1),
    1206     11300334 :                         CALL_INSN_FUNCTION_USAGE (i2))
    1207      7503078 :           || CALL_INSN_ABI_ID (call1) != CALL_INSN_ABI_ID (i2)
    1208     18803412 :           || SIBLING_CALL_P (call1) != SIBLING_CALL_P (i2))
    1209              :         return dir_none;
    1210              : 
    1211              :       /* For address sanitizer, never crossjump __asan_report_* builtins,
    1212              :          otherwise errors might be reported on incorrect lines.  */
    1213      7503078 :       if (flag_sanitize & SANITIZE_ADDRESS)
    1214              :         {
    1215       380575 :           rtx call = get_call_rtx_from (i1);
    1216       380575 :           if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF)
    1217              :             {
    1218       380575 :               rtx symbol = XEXP (XEXP (call, 0), 0);
    1219       380575 :               if (SYMBOL_REF_DECL (symbol)
    1220       380575 :                   && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL)
    1221              :                 {
    1222       380575 :                   if ((DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol))
    1223       380575 :                        == BUILT_IN_NORMAL)
    1224       378562 :                       && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
    1225              :                          >= BUILT_IN_ASAN_REPORT_LOAD1
    1226       757629 :                       && DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))
    1227              :                          <= BUILT_IN_ASAN_STOREN)
    1228              :                     return dir_none;
    1229              :                 }
    1230              :             }
    1231              :         }
    1232              : 
    1233      7126974 :       if (insn_callee_abi (i1) != insn_callee_abi (i2))
    1234              :         return dir_none;
    1235              :     }
    1236              : 
    1237              :   /* If both i1 and i2 are frame related, verify all the CFA notes
    1238              :      in the same order and with the same content.  */
    1239     25406404 :   if (RTX_FRAME_RELATED_P (i1) && !insns_have_identical_cfa_notes (i1, i2))
    1240              :     return dir_none;
    1241              : 
    1242              : #ifdef STACK_REGS
    1243              :   /* If cross_jump_death_matters is not 0, the insn's mode
    1244              :      indicates whether or not the insn contains any stack-like
    1245              :      regs.  */
    1246              : 
    1247     25294752 :   if ((mode & CLEANUP_POST_REGSTACK) && stack_regs_mentioned (i1))
    1248              :     {
    1249              :       /* If register stack conversion has already been done, then
    1250              :          death notes must also be compared before it is certain that
    1251              :          the two instruction streams match.  */
    1252              : 
    1253              :       rtx note;
    1254              :       HARD_REG_SET i1_regset, i2_regset;
    1255              : 
    1256            0 :       CLEAR_HARD_REG_SET (i1_regset);
    1257            0 :       CLEAR_HARD_REG_SET (i2_regset);
    1258              : 
    1259            0 :       for (note = REG_NOTES (i1); note; note = XEXP (note, 1))
    1260            0 :         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
    1261            0 :           SET_HARD_REG_BIT (i1_regset, REGNO (XEXP (note, 0)));
    1262              : 
    1263            0 :       for (note = REG_NOTES (i2); note; note = XEXP (note, 1))
    1264            0 :         if (REG_NOTE_KIND (note) == REG_DEAD && STACK_REG_P (XEXP (note, 0)))
    1265            0 :           SET_HARD_REG_BIT (i2_regset, REGNO (XEXP (note, 0)));
    1266              : 
    1267            0 :       if (i1_regset != i2_regset)
    1268            0 :         return dir_none;
    1269              :     }
    1270              : #endif
    1271              : 
    1272     25294752 :   if (reload_completed
    1273     25294752 :       ? rtx_renumbered_equal_p (p1, p2) : rtx_equal_p (p1, p2))
    1274              :     return dir_both;
    1275              : 
    1276     14100128 :   return can_replace_by (i1, i2);
    1277              : }
    1278              : 
    1279              : /* When comparing insns I1 and I2 in flow_find_cross_jump or
    1280              :    flow_find_head_matching_sequence, ensure the notes match.  */
    1281              : 
    1282              : static void
    1283      8776249 : merge_notes (rtx_insn *i1, rtx_insn *i2)
    1284              : {
    1285              :   /* If the merged insns have different REG_EQUAL notes, then
    1286              :      remove them.  */
    1287      8776249 :   rtx equiv1 = find_reg_equal_equiv_note (i1);
    1288      8776249 :   rtx equiv2 = find_reg_equal_equiv_note (i2);
    1289              : 
    1290      8776249 :   if (equiv1 && !equiv2)
    1291        23678 :     remove_note (i1, equiv1);
    1292      8752571 :   else if (!equiv1 && equiv2)
    1293         5476 :     remove_note (i2, equiv2);
    1294      8747095 :   else if (equiv1 && equiv2
    1295      8747095 :            && !rtx_equal_p (XEXP (equiv1, 0), XEXP (equiv2, 0)))
    1296              :     {
    1297          344 :       remove_note (i1, equiv1);
    1298          344 :       remove_note (i2, equiv2);
    1299              :     }
    1300      8776249 : }
    1301              : 
    1302              :  /* Walks from I1 in BB1 backward till the next non-debug insn, and returns the
    1303              :     resulting insn in I1, and the corresponding bb in BB1.  At the head of a
    1304              :     bb, if there is a predecessor bb that reaches this bb via fallthru, and
    1305              :     FOLLOW_FALLTHRU, walks further in the predecessor bb and registers this in
    1306              :     DID_FALLTHRU.  Otherwise, stops at the head of the bb.  */
    1307              : 
    1308              : static void
    1309     49094662 : walk_to_nondebug_insn (rtx_insn **i1, basic_block *bb1, bool follow_fallthru,
    1310              :                        bool *did_fallthru)
    1311              : {
    1312     49094662 :   edge fallthru;
    1313              : 
    1314     49094662 :   *did_fallthru = false;
    1315              : 
    1316              :   /* Ignore notes.  */
    1317     68106024 :   while (!NONDEBUG_INSN_P (*i1))
    1318              :     {
    1319     20177226 :       if (*i1 != BB_HEAD (*bb1))
    1320              :         {
    1321     18824561 :           *i1 = PREV_INSN (*i1);
    1322     18824561 :           continue;
    1323              :         }
    1324              : 
    1325      1352665 :       if (!follow_fallthru)
    1326              :         return;
    1327              : 
    1328      1169830 :       fallthru = find_fallthru_edge ((*bb1)->preds);
    1329       478686 :       if (!fallthru || fallthru->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
    1330      1648440 :           || !single_succ_p (fallthru->src))
    1331              :         return;
    1332              : 
    1333       186801 :       *bb1 = fallthru->src;
    1334       186801 :       *i1 = BB_END (*bb1);
    1335       186801 :       *did_fallthru = true;
    1336              :      }
    1337              : }
    1338              : 
    1339              : /* Look through the insns at the end of BB1 and BB2 and find the longest
    1340              :    sequence that are either equivalent, or allow forward or backward
    1341              :    replacement.  Store the first insns for that sequence in *F1 and *F2 and
    1342              :    return the sequence length.
    1343              : 
    1344              :    DIR_P indicates the allowed replacement direction on function entry, and
    1345              :    the actual replacement direction on function exit.  If NULL, only equivalent
    1346              :    sequences are allowed.
    1347              : 
    1348              :    To simplify callers of this function, if the blocks match exactly,
    1349              :    store the head of the blocks in *F1 and *F2.  */
    1350              : 
    1351              : int
    1352     15989191 : flow_find_cross_jump (basic_block bb1, basic_block bb2, rtx_insn **f1,
    1353              :                       rtx_insn **f2, enum replace_direction *dir_p)
    1354              : {
    1355     15989191 :   rtx_insn *i1, *i2, *last1, *last2, *afterlast1, *afterlast2;
    1356     15989191 :   int ninsns = 0;
    1357     15989191 :   enum replace_direction dir, last_dir, afterlast_dir;
    1358     15989191 :   bool follow_fallthru, did_fallthru;
    1359              : 
    1360     15989191 :   if (dir_p)
    1361     15989191 :     dir = *dir_p;
    1362              :   else
    1363              :     dir = dir_both;
    1364     15989191 :   afterlast_dir = dir;
    1365     15989191 :   last_dir = afterlast_dir;
    1366              : 
    1367              :   /* Skip simple jumps at the end of the blocks.  Complex jumps still
    1368              :      need to be compared for equivalence, which we'll do below.  */
    1369              : 
    1370     15989191 :   i1 = BB_END (bb1);
    1371     15989191 :   last1 = afterlast1 = last2 = afterlast2 = NULL;
    1372     15989191 :   if (onlyjump_p (i1)
    1373     15989191 :       || (returnjump_p (i1) && !side_effects_p (PATTERN (i1))))
    1374              :     {
    1375     14330661 :       last1 = i1;
    1376     14330661 :       i1 = PREV_INSN (i1);
    1377              :     }
    1378              : 
    1379     15989191 :   i2 = BB_END (bb2);
    1380     15989191 :   if (onlyjump_p (i2)
    1381     15989191 :       || (returnjump_p (i2) && !side_effects_p (PATTERN (i2))))
    1382              :     {
    1383     11613385 :       last2 = i2;
    1384              :       /* Count everything except for unconditional jump as insn.
    1385              :          Don't count any jumps if dir_p is NULL.  */
    1386     11613385 :       if (!simplejump_p (i2) && !returnjump_p (i2) && last1 && dir_p)
    1387              :         ninsns++;
    1388     11613385 :       i2 = PREV_INSN (i2);
    1389              :     }
    1390              : 
    1391     33105471 :   while (true)
    1392              :     {
    1393              :       /* In the following example, we can replace all jumps to C by jumps to A.
    1394              : 
    1395              :          This removes 4 duplicate insns.
    1396              :          [bb A] insn1            [bb C] insn1
    1397              :                 insn2                   insn2
    1398              :          [bb B] insn3                   insn3
    1399              :                 insn4                   insn4
    1400              :                 jump_insn               jump_insn
    1401              : 
    1402              :          We could also replace all jumps to A by jumps to C, but that leaves B
    1403              :          alive, and removes only 2 duplicate insns.  In a subsequent crossjump
    1404              :          step, all jumps to B would be replaced with jumps to the middle of C,
    1405              :          achieving the same result with more effort.
    1406              :          So we allow only the first possibility, which means that we don't allow
    1407              :          fallthru in the block that's being replaced.  */
    1408              : 
    1409     24547331 :       follow_fallthru = dir_p && dir != dir_forward;
    1410     24547331 :       walk_to_nondebug_insn (&i1, &bb1, follow_fallthru, &did_fallthru);
    1411     24547331 :       if (did_fallthru)
    1412        28435 :         dir = dir_backward;
    1413              : 
    1414     24547331 :       follow_fallthru = dir_p && dir != dir_backward;
    1415     24547331 :       walk_to_nondebug_insn (&i2, &bb2, follow_fallthru, &did_fallthru);
    1416     24547331 :       if (did_fallthru)
    1417       158356 :         dir = dir_forward;
    1418              : 
    1419     24547331 :       if (i1 == BB_HEAD (bb1) || i2 == BB_HEAD (bb2))
    1420              :         break;
    1421              : 
    1422              :       /* Do not turn corssing edge to non-crossing or vice versa after
    1423              :          reload. */
    1424     23762402 :       if (BB_PARTITION (BLOCK_FOR_INSN (i1))
    1425     23762402 :           != BB_PARTITION (BLOCK_FOR_INSN (i2))
    1426     23762402 :           && reload_completed)
    1427              :         break;
    1428              : 
    1429     23762402 :       dir = merge_dir (dir, old_insns_match_p (0, i1, i2));
    1430     20991422 :       if (dir == dir_none || (!dir_p && dir != dir_both))
    1431              :         break;
    1432              : 
    1433      8558140 :       merge_memattrs (i1, i2);
    1434              : 
    1435              :       /* Don't begin a cross-jump with a NOTE insn.  */
    1436      8558140 :       if (INSN_P (i1))
    1437              :         {
    1438      8558140 :           merge_notes (i1, i2);
    1439              : 
    1440      8558140 :           afterlast1 = last1, afterlast2 = last2;
    1441      8558140 :           last1 = i1, last2 = i2;
    1442      8558140 :           afterlast_dir = last_dir;
    1443      8558140 :           last_dir = dir;
    1444      8558140 :           if (active_insn_p (i1))
    1445      8451583 :             ninsns++;
    1446              :         }
    1447              : 
    1448      8558140 :       i1 = PREV_INSN (i1);
    1449      8558140 :       i2 = PREV_INSN (i2);
    1450              :     }
    1451              : 
    1452              :   /* Include preceding notes and labels in the cross-jump.  One,
    1453              :      this may bring us to the head of the blocks as requested above.
    1454              :      Two, it keeps line number notes as matched as may be.  */
    1455     15989191 :   if (ninsns)
    1456              :     {
    1457      5156345 :       bb1 = BLOCK_FOR_INSN (last1);
    1458     13309408 :       while (last1 != BB_HEAD (bb1) && !NONDEBUG_INSN_P (PREV_INSN (last1)))
    1459              :         last1 = PREV_INSN (last1);
    1460              : 
    1461     10026863 :       if (last1 != BB_HEAD (bb1) && LABEL_P (PREV_INSN (last1)))
    1462              :         last1 = PREV_INSN (last1);
    1463              : 
    1464      5156345 :       bb2 = BLOCK_FOR_INSN (last2);
    1465     13354812 :       while (last2 != BB_HEAD (bb2) && !NONDEBUG_INSN_P (PREV_INSN (last2)))
    1466              :         last2 = PREV_INSN (last2);
    1467              : 
    1468      9739221 :       if (last2 != BB_HEAD (bb2) && LABEL_P (PREV_INSN (last2)))
    1469              :         last2 = PREV_INSN (last2);
    1470              : 
    1471      5156345 :       *f1 = last1;
    1472      5156345 :       *f2 = last2;
    1473              :     }
    1474              : 
    1475     15989191 :   if (dir_p)
    1476     15989191 :     *dir_p = last_dir;
    1477     15989191 :   return ninsns;
    1478              : }
    1479              : 
    1480              : /* Like flow_find_cross_jump, except start looking for a matching sequence from
    1481              :    the head of the two blocks.  Do not include jumps at the end.
    1482              :    If STOP_AFTER is nonzero, stop after finding that many matching
    1483              :    instructions.  If STOP_AFTER is zero, count all INSN_P insns, if it is
    1484              :    non-zero, only count active insns.  */
    1485              : 
    1486              : int
    1487      4645080 : flow_find_head_matching_sequence (basic_block bb1, basic_block bb2, rtx_insn **f1,
    1488              :                                   rtx_insn **f2, int stop_after)
    1489              : {
    1490      4645080 :   rtx_insn *i1, *i2, *last1, *last2, *beforelast1, *beforelast2;
    1491      4645080 :   int ninsns = 0;
    1492      4645080 :   edge e;
    1493      4645080 :   edge_iterator ei;
    1494      4645080 :   int nehedges1 = 0, nehedges2 = 0;
    1495              : 
    1496     11153351 :   FOR_EACH_EDGE (e, ei, bb1->succs)
    1497      6508271 :     if (e->flags & EDGE_EH)
    1498       339756 :       nehedges1++;
    1499     11493754 :   FOR_EACH_EDGE (e, ei, bb2->succs)
    1500      6848674 :     if (e->flags & EDGE_EH)
    1501       372795 :       nehedges2++;
    1502              : 
    1503      4645080 :   i1 = BB_HEAD (bb1);
    1504      4645080 :   i2 = BB_HEAD (bb2);
    1505      4645080 :   last1 = beforelast1 = last2 = beforelast2 = NULL;
    1506              : 
    1507       204449 :   while (true)
    1508              :     {
    1509              :       /* Ignore notes, except NOTE_INSN_EPILOGUE_BEG.  */
    1510     22820489 :       while (!NONDEBUG_INSN_P (i1) && i1 != BB_END (bb1))
    1511              :         {
    1512     17790811 :           if (NOTE_P (i1) && NOTE_KIND (i1) == NOTE_INSN_EPILOGUE_BEG)
    1513              :             break;
    1514     17766511 :           i1 = NEXT_INSN (i1);
    1515              :         }
    1516              : 
    1517     22468836 :       while (!NONDEBUG_INSN_P (i2) && i2 != BB_END (bb2))
    1518              :         {
    1519     17665576 :           if (NOTE_P (i2) && NOTE_KIND (i2) == NOTE_INSN_EPILOGUE_BEG)
    1520              :             break;
    1521     17619307 :           i2 = NEXT_INSN (i2);
    1522              :         }
    1523              : 
    1524      4849529 :       if ((i1 == BB_END (bb1) && !NONDEBUG_INSN_P (i1))
    1525      4837562 :           || (i2 == BB_END (bb2) && !NONDEBUG_INSN_P (i2)))
    1526              :         break;
    1527              : 
    1528      4832635 :       if (NOTE_P (i1) || NOTE_P (i2)
    1529      4767996 :           || JUMP_P (i1) || JUMP_P (i2))
    1530              :         break;
    1531              : 
    1532              :       /* A sanity check to make sure we're not merging insns with different
    1533              :          effects on EH.  If only one of them ends a basic block, it shouldn't
    1534              :          have an EH edge; if both end a basic block, there should be the same
    1535              :          number of EH edges.  */
    1536      3923613 :       if ((i1 == BB_END (bb1) && i2 != BB_END (bb2)
    1537       216894 :            && nehedges1 > 0)
    1538      3885320 :           || (i2 == BB_END (bb2) && i1 != BB_END (bb1)
    1539       253326 :               && nehedges2 > 0)
    1540      3856385 :           || (i1 == BB_END (bb1) && i2 == BB_END (bb2)
    1541        25216 :               && nehedges1 != nehedges2))
    1542              :         break;
    1543              : 
    1544      3853590 :       if (old_insns_match_p (0, i1, i2) != dir_both)
    1545              :         break;
    1546              : 
    1547       218109 :       merge_memattrs (i1, i2);
    1548              : 
    1549              :       /* Don't begin a cross-jump with a NOTE insn.  */
    1550       218109 :       if (INSN_P (i1))
    1551              :         {
    1552       218109 :           merge_notes (i1, i2);
    1553              : 
    1554       218109 :           beforelast1 = last1, beforelast2 = last2;
    1555       218109 :           last1 = i1, last2 = i2;
    1556       218109 :           if (!stop_after || active_insn_p (i1))
    1557       218109 :             ninsns++;
    1558              :         }
    1559              : 
    1560       218109 :       if (i1 == BB_END (bb1) || i2 == BB_END (bb2)
    1561       204449 :           || (stop_after > 0 && ninsns == stop_after))
    1562              :         break;
    1563              : 
    1564       204449 :       i1 = NEXT_INSN (i1);
    1565       204449 :       i2 = NEXT_INSN (i2);
    1566              :     }
    1567              : 
    1568      4645080 :   if (ninsns)
    1569              :     {
    1570       123769 :       *f1 = last1;
    1571       123769 :       *f2 = last2;
    1572              :     }
    1573              : 
    1574      4645080 :   return ninsns;
    1575              : }
    1576              : 
    1577              : /* Return true iff outgoing edges of BB1 and BB2 match, together with
    1578              :    the branch instruction.  This means that if we commonize the control
    1579              :    flow before end of the basic block, the semantic remains unchanged.
    1580              : 
    1581              :    We may assume that there exists one edge with a common destination.  */
    1582              : 
    1583              : static bool
    1584     47502673 : outgoing_edges_match (int mode, basic_block bb1, basic_block bb2)
    1585              : {
    1586     47502673 :   int nehedges1 = 0, nehedges2 = 0;
    1587     47502673 :   edge fallthru1 = 0, fallthru2 = 0;
    1588     47502673 :   edge e1, e2;
    1589     47502673 :   edge_iterator ei;
    1590              : 
    1591              :   /* If we performed shrink-wrapping, edges to the exit block can
    1592              :      only be distinguished for JUMP_INSNs.  The two paths may differ in
    1593              :      whether they went through the prologue.  Sibcalls are fine, we know
    1594              :      that we either didn't need or inserted an epilogue before them.  */
    1595     47502673 :   if (crtl->shrink_wrapped
    1596      1237418 :       && single_succ_p (bb1)
    1597       472633 :       && single_succ (bb1) == EXIT_BLOCK_PTR_FOR_FN (cfun)
    1598       153875 :       && (!JUMP_P (BB_END (bb1))
    1599              :           /* Punt if the only successor is a fake edge to exit, the jump
    1600              :              must be some weird one.  */
    1601        65934 :           || (single_succ_edge (bb1)->flags & EDGE_FAKE) != 0)
    1602     47590697 :       && !(CALL_P (BB_END (bb1)) && SIBLING_CALL_P (BB_END (bb1))))
    1603              :     return false;
    1604              : 
    1605              :   /* If BB1 has only one successor, we may be looking at either an
    1606              :      unconditional jump, or a fake edge to exit.  */
    1607     47452010 :   if (single_succ_p (bb1)
    1608     19006979 :       && (single_succ_edge (bb1)->flags & (EDGE_COMPLEX | EDGE_FAKE)) == 0
    1609     62860409 :       && (!JUMP_P (BB_END (bb1)) || simplejump_p (BB_END (bb1))))
    1610     15140927 :     return (single_succ_p (bb2)
    1611     13938953 :             && (single_succ_edge (bb2)->flags
    1612     13938953 :                 & (EDGE_COMPLEX | EDGE_FAKE)) == 0
    1613     28999222 :             && (!JUMP_P (BB_END (bb2)) || simplejump_p (BB_END (bb2))));
    1614              : 
    1615              :   /* Match conditional jumps - this may get tricky when fallthru and branch
    1616              :      edges are crossed.  */
    1617     32311083 :   if (EDGE_COUNT (bb1->succs) == 2
    1618     28346626 :       && any_condjump_p (BB_END (bb1))
    1619     51203388 :       && onlyjump_p (BB_END (bb1)))
    1620              :     {
    1621     18892305 :       edge b1, f1, b2, f2;
    1622     18892305 :       bool reverse, match;
    1623     18892305 :       rtx set1, set2, cond1, cond2;
    1624     18892305 :       enum rtx_code code1, code2;
    1625              : 
    1626     18892305 :       if (EDGE_COUNT (bb2->succs) != 2
    1627      8508801 :           || !any_condjump_p (BB_END (bb2))
    1628     27364128 :           || !onlyjump_p (BB_END (bb2)))
    1629              :         return false;
    1630              : 
    1631      8471823 :       b1 = BRANCH_EDGE (bb1);
    1632      8471823 :       b2 = BRANCH_EDGE (bb2);
    1633      8471823 :       f1 = FALLTHRU_EDGE (bb1);
    1634      8471823 :       f2 = FALLTHRU_EDGE (bb2);
    1635              : 
    1636              :       /* Get around possible forwarders on fallthru edges.  Other cases
    1637              :          should be optimized out already.  */
    1638      8471823 :       if (FORWARDER_BLOCK_P (f1->dest))
    1639      3295115 :         f1 = single_succ_edge (f1->dest);
    1640              : 
    1641      8471823 :       if (FORWARDER_BLOCK_P (f2->dest))
    1642      2433077 :         f2 = single_succ_edge (f2->dest);
    1643              : 
    1644              :       /* To simplify use of this function, return false if there are
    1645              :          unneeded forwarder blocks.  These will get eliminated later
    1646              :          during cleanup_cfg.  */
    1647      8471823 :       if (FORWARDER_BLOCK_P (f1->dest)
    1648      8462713 :           || FORWARDER_BLOCK_P (f2->dest)
    1649      8458007 :           || FORWARDER_BLOCK_P (b1->dest)
    1650      8434336 :           || FORWARDER_BLOCK_P (b2->dest))
    1651              :         return false;
    1652              : 
    1653      8406230 :       if (f1->dest == f2->dest && b1->dest == b2->dest)
    1654              :         reverse = false;
    1655      8198333 :       else if (f1->dest == b2->dest && b1->dest == f2->dest)
    1656              :         reverse = true;
    1657              :       else
    1658              :         return false;
    1659              : 
    1660       351846 :       set1 = pc_set (BB_END (bb1));
    1661       351846 :       set2 = pc_set (BB_END (bb2));
    1662       351846 :       if ((XEXP (SET_SRC (set1), 1) == pc_rtx)
    1663       351846 :           != (XEXP (SET_SRC (set2), 1) == pc_rtx))
    1664            0 :         reverse = !reverse;
    1665              : 
    1666       351846 :       cond1 = XEXP (SET_SRC (set1), 0);
    1667       351846 :       cond2 = XEXP (SET_SRC (set2), 0);
    1668       351846 :       code1 = GET_CODE (cond1);
    1669       351846 :       if (reverse)
    1670       143949 :         code2 = reversed_comparison_code (cond2, BB_END (bb2));
    1671              :       else
    1672       207897 :         code2 = GET_CODE (cond2);
    1673              : 
    1674       351846 :       if (code2 == UNKNOWN)
    1675              :         return false;
    1676              : 
    1677              :       /* Verify codes and operands match.  */
    1678       351846 :       match = ((code1 == code2
    1679       300161 :                 && rtx_renumbered_equal_p (XEXP (cond1, 0), XEXP (cond2, 0))
    1680       298095 :                 && rtx_renumbered_equal_p (XEXP (cond1, 1), XEXP (cond2, 1)))
    1681       353912 :                || (code1 == swap_condition (code2)
    1682         4790 :                    && rtx_renumbered_equal_p (XEXP (cond1, 1),
    1683         4790 :                                               XEXP (cond2, 0))
    1684            0 :                    && rtx_renumbered_equal_p (XEXP (cond1, 0),
    1685            0 :                                               XEXP (cond2, 1))));
    1686              : 
    1687              :       /* If we return true, we will join the blocks.  Which means that
    1688              :          we will only have one branch prediction bit to work with.  Thus
    1689              :          we require the existing branches to have probabilities that are
    1690              :          roughly similar.  */
    1691              :       if (match
    1692       298095 :           && optimize_bb_for_speed_p (bb1)
    1693       270184 :           && optimize_bb_for_speed_p (bb2))
    1694              :         {
    1695       260063 :           profile_probability prob2;
    1696              : 
    1697       260063 :           if (b1->dest == b2->dest)
    1698       156394 :             prob2 = b2->probability;
    1699              :           else
    1700              :             /* Do not use f2 probability as f2 may be forwarded.  */
    1701       103669 :             prob2 = b2->probability.invert ();
    1702              : 
    1703              :           /* Fail if the difference in probabilities is greater than 50%.
    1704              :              This rules out two well-predicted branches with opposite
    1705              :              outcomes.  */
    1706       260063 :           if (b1->probability.differs_lot_from_p (prob2))
    1707              :             {
    1708         2379 :               if (dump_file)
    1709              :                 {
    1710            0 :                   fprintf (dump_file,
    1711              :                            "Outcomes of branch in bb %i and %i differ too"
    1712              :                            " much (", bb1->index, bb2->index);
    1713            0 :                   b1->probability.dump (dump_file);
    1714            0 :                   prob2.dump (dump_file);
    1715            0 :                   fprintf (dump_file, ")\n");
    1716              :                 }
    1717         2379 :               return false;
    1718              :             }
    1719              :         }
    1720              : 
    1721       349467 :       if (dump_file && match)
    1722           16 :         fprintf (dump_file, "Conditionals in bb %i and %i match.\n",
    1723              :                  bb1->index, bb2->index);
    1724              : 
    1725              :       return match;
    1726              :     }
    1727              : 
    1728              :   /* Generic case - we are seeing a computed jump, table jump or trapping
    1729              :      instruction.  */
    1730              : 
    1731              :   /* Check whether there are tablejumps in the end of BB1 and BB2.
    1732              :      Return true if they are identical.  */
    1733     13418778 :     {
    1734     13418778 :       rtx_insn *label1, *label2;
    1735     13418778 :       rtx_jump_table_data *table1, *table2;
    1736              : 
    1737     13418778 :       if (tablejump_p (BB_END (bb1), &label1, &table1)
    1738        95822 :           && tablejump_p (BB_END (bb2), &label2, &table2)
    1739     13420944 :           && GET_CODE (PATTERN (table1)) == GET_CODE (PATTERN (table2)))
    1740              :         {
    1741              :           /* Cross-jumping redirects every user of one table to the other.
    1742              :              Keep a shared table and all its users unchanged.  */
    1743         2166 :           if (JUMP_TABLE_SHARED_P (PATTERN (table1))
    1744         2166 :               || JUMP_TABLE_SHARED_P (PATTERN (table2)))
    1745         2166 :             return false;
    1746              : 
    1747              :           /* The labels should never be the same rtx.  If they really are same
    1748              :              the jump tables are same too. So disable crossjumping of blocks BB1
    1749              :              and BB2 because when deleting the common insns in the end of BB1
    1750              :              by delete_basic_block () the jump table would be deleted too.  */
    1751              :           /* If LABEL2 is referenced in BB1->END do not do anything
    1752              :              because we would loose information when replacing
    1753              :              LABEL1 by LABEL2 and then LABEL2 by LABEL1 in BB1->END.  */
    1754         2166 :           if (label1 != label2 && !rtx_referenced_p (label2, BB_END (bb1)))
    1755              :             {
    1756              :               /* Set IDENTICAL to true when the tables are identical.  */
    1757         2166 :               bool identical = false;
    1758         2166 :               rtx p1, p2;
    1759              : 
    1760         2166 :               p1 = PATTERN (table1);
    1761         2166 :               p2 = PATTERN (table2);
    1762         2166 :               if (GET_CODE (p1) == ADDR_VEC && rtx_equal_p (p1, p2))
    1763              :                 {
    1764              :                   identical = true;
    1765              :                 }
    1766         1977 :               else if (GET_CODE (p1) == ADDR_DIFF_VEC
    1767          389 :                        && (XVECLEN (p1, 1) == XVECLEN (p2, 1))
    1768          267 :                        && rtx_equal_p (XEXP (p1, 2), XEXP (p2, 2))
    1769         2244 :                        && rtx_equal_p (XEXP (p1, 3), XEXP (p2, 3)))
    1770              :                 {
    1771          267 :                   int i;
    1772              : 
    1773          267 :                   identical = true;
    1774         1170 :                   for (i = XVECLEN (p1, 1) - 1; i >= 0 && identical; i--)
    1775          903 :                     if (!rtx_equal_p (XVECEXP (p1, 1, i), XVECEXP (p2, 1, i)))
    1776              :                       identical = false;
    1777              :                 }
    1778              : 
    1779          267 :               if (identical)
    1780              :                 {
    1781          237 :                   bool match;
    1782              : 
    1783              :                   /* Temporarily replace references to LABEL1 with LABEL2
    1784              :                      in BB1->END so that we could compare the instructions.  */
    1785          237 :                   replace_label_in_insn (BB_END (bb1), label1, label2, false);
    1786              : 
    1787          237 :                   match = (old_insns_match_p (mode, BB_END (bb1), BB_END (bb2))
    1788              :                            == dir_both);
    1789          237 :                   if (dump_file && match)
    1790            0 :                     fprintf (dump_file,
    1791              :                              "Tablejumps in bb %i and %i match.\n",
    1792              :                              bb1->index, bb2->index);
    1793              : 
    1794              :                   /* Set the original label in BB1->END because when deleting
    1795              :                      a block whose end is a tablejump, the tablejump referenced
    1796              :                      from the instruction is deleted too.  */
    1797          237 :                   replace_label_in_insn (BB_END (bb1), label2, label1, false);
    1798              : 
    1799          237 :                   return match;
    1800              :                 }
    1801              :             }
    1802              :           return false;
    1803              :         }
    1804              :     }
    1805              : 
    1806              :   /* Find the last non-debug non-note instruction in each bb, except
    1807              :      stop when we see the NOTE_INSN_BASIC_BLOCK, as old_insns_match_p
    1808              :      handles that case specially. old_insns_match_p does not handle
    1809              :      other types of instruction notes.  */
    1810     13416612 :   rtx_insn *last1 = BB_END (bb1);
    1811     13416612 :   rtx_insn *last2 = BB_END (bb2);
    1812     13416703 :   while (!NOTE_INSN_BASIC_BLOCK_P (last1) &&
    1813     13286892 :          (DEBUG_INSN_P (last1) || NOTE_P (last1)))
    1814           91 :     last1 = PREV_INSN (last1);
    1815     13435580 :   while (!NOTE_INSN_BASIC_BLOCK_P (last2) &&
    1816     13322972 :          (DEBUG_INSN_P (last2) || NOTE_P (last2)))
    1817        18544 :     last2 = PREV_INSN (last2);
    1818     13416612 :   gcc_assert (last1 && last2);
    1819              : 
    1820              :   /* First ensure that the instructions match.  There may be many outgoing
    1821              :      edges so this test is generally cheaper.  */
    1822     13416612 :   if (old_insns_match_p (mode, last1, last2) != dir_both)
    1823              :     return false;
    1824              : 
    1825              :   /* Search the outgoing edges, ensure that the counts do match, find possible
    1826              :      fallthru and exception handling edges since these needs more
    1827              :      validation.  */
    1828      7515927 :   if (EDGE_COUNT (bb1->succs) != EDGE_COUNT (bb2->succs))
    1829              :     return false;
    1830              : 
    1831      2505296 :   bool nonfakeedges = false;
    1832      6175953 :   FOR_EACH_EDGE (e1, ei, bb1->succs)
    1833              :     {
    1834      3670657 :       e2 = EDGE_SUCC (bb2, ei.index);
    1835              : 
    1836      3670657 :       if ((e1->flags & EDGE_FAKE) == 0)
    1837      2679702 :         nonfakeedges = true;
    1838              : 
    1839      3670657 :       if (e1->flags & EDGE_EH)
    1840      1204146 :         nehedges1++;
    1841              : 
    1842      3670657 :       if (e2->flags & EDGE_EH)
    1843      1204146 :         nehedges2++;
    1844              : 
    1845      3670657 :       if (e1->flags & EDGE_FALLTHRU)
    1846      1260624 :         fallthru1 = e1;
    1847      3670657 :       if (e2->flags & EDGE_FALLTHRU)
    1848      1260624 :         fallthru2 = e2;
    1849              :     }
    1850              : 
    1851              :   /* If number of edges of various types does not match, fail.  */
    1852      2505296 :   if (nehedges1 != nehedges2
    1853      2505296 :       || (fallthru1 != 0) != (fallthru2 != 0))
    1854              :     return false;
    1855              : 
    1856              :   /* If !ACCUMULATE_OUTGOING_ARGS, bb1 (and bb2) have no successors
    1857              :      and the last real insn doesn't have REG_ARGS_SIZE note, don't
    1858              :      attempt to optimize, as the two basic blocks might have different
    1859              :      REG_ARGS_SIZE depths.  For noreturn calls and unconditional
    1860              :      traps there should be REG_ARG_SIZE notes, they could be missing
    1861              :      for __builtin_unreachable () uses though.  */
    1862      2505296 :   if (!nonfakeedges
    1863       990955 :       && !ACCUMULATE_OUTGOING_ARGS
    1864      3496244 :       && (!INSN_P (last1)
    1865       990948 :           || !find_reg_note (last1, REG_ARGS_SIZE, NULL)))
    1866              :     return false;
    1867              : 
    1868              :   /* fallthru edges must be forwarded to the same destination.  */
    1869      2505285 :   if (fallthru1)
    1870              :     {
    1871      1260624 :       basic_block d1 = (FORWARDER_BLOCK_P (fallthru1->dest)
    1872      1260624 :                         ? single_succ (fallthru1->dest) : fallthru1->dest);
    1873      1260624 :       basic_block d2 = (FORWARDER_BLOCK_P (fallthru2->dest)
    1874      1260624 :                         ? single_succ (fallthru2->dest) : fallthru2->dest);
    1875              : 
    1876      1260624 :       if (d1 != d2)
    1877              :         return false;
    1878              :     }
    1879              : 
    1880              :   /* Ensure the same EH region.  */
    1881      1834985 :   {
    1882      1834985 :     rtx n1 = find_reg_note (last1, REG_EH_REGION, 0);
    1883      1834985 :     rtx n2 = find_reg_note (last2, REG_EH_REGION, 0);
    1884              : 
    1885      1834985 :     if (!n1 && n2)
    1886              :       return false;
    1887              : 
    1888      1834985 :     if (n1 && (!n2 || XEXP (n1, 0) != XEXP (n2, 0)))
    1889              :       return false;
    1890              :   }
    1891              : 
    1892              :   /* The same checks as in try_crossjump_to_edge. It is required for RTL
    1893              :      version of sequence abstraction.  */
    1894      4164389 :   FOR_EACH_EDGE (e1, ei, bb2->succs)
    1895              :     {
    1896      2329434 :       edge e2;
    1897      2329434 :       edge_iterator ei;
    1898      2329434 :       basic_block d1 = e1->dest;
    1899              : 
    1900      2329434 :       if (FORWARDER_BLOCK_P (d1))
    1901       599989 :         d1 = EDGE_SUCC (d1, 0)->dest;
    1902              : 
    1903      2825353 :       FOR_EACH_EDGE (e2, ei, bb1->succs)
    1904              :         {
    1905      2825353 :           basic_block d2 = e2->dest;
    1906      2825353 :           if (FORWARDER_BLOCK_P (d2))
    1907       781481 :             d2 = EDGE_SUCC (d2, 0)->dest;
    1908      2825353 :           if (d1 == d2)
    1909              :             break;
    1910              :         }
    1911              : 
    1912      2329434 :       if (!e2)
    1913            0 :         return false;
    1914              :     }
    1915              : 
    1916              :   return true;
    1917              : }
    1918              : 
    1919              : /* Returns true if BB basic block has a preserve label.  */
    1920              : 
    1921              : static bool
    1922       376698 : block_has_preserve_label (basic_block bb)
    1923              : {
    1924       376698 :   return (bb
    1925       376698 :           && block_label (bb)
    1926       698670 :           && LABEL_PRESERVE_P (block_label (bb)));
    1927              : }
    1928              : 
    1929              : /* E1 and E2 are edges with the same destination block.  Search their
    1930              :    predecessors for common code.  If found, redirect control flow from
    1931              :    (maybe the middle of) E1->SRC to (maybe the middle of) E2->SRC (dir_forward),
    1932              :    or the other way around (dir_backward).  DIR specifies the allowed
    1933              :    replacement direction.  */
    1934              : 
    1935              : static bool
    1936     52348011 : try_crossjump_to_edge (int mode, edge e1, edge e2,
    1937              :                        enum replace_direction dir)
    1938              : {
    1939     52348011 :   int nmatch;
    1940     52348011 :   basic_block src1 = e1->src, src2 = e2->src;
    1941     52348011 :   basic_block redirect_to, redirect_from, to_remove;
    1942     52348011 :   basic_block osrc1, osrc2, redirect_edges_to, tmp;
    1943     52348011 :   rtx_insn *newpos1, *newpos2;
    1944     52348011 :   edge s;
    1945     52348011 :   edge_iterator ei;
    1946              : 
    1947     52348011 :   newpos1 = newpos2 = NULL;
    1948              : 
    1949              :   /* Search backward through forwarder blocks.  We don't need to worry
    1950              :      about multiple entry or chained forwarders, as they will be optimized
    1951              :      away.  We do this to look past the unconditional jump following a
    1952              :      conditional jump that is required due to the current CFG shape.  */
    1953     52348011 :   if (single_pred_p (src1)
    1954     52348011 :       && FORWARDER_BLOCK_P (src1))
    1955     11833694 :     e1 = single_pred_edge (src1), src1 = e1->src;
    1956              : 
    1957     52348011 :   if (single_pred_p (src2)
    1958     52347799 :       && FORWARDER_BLOCK_P (src2))
    1959      5559675 :     e2 = single_pred_edge (src2), src2 = e2->src;
    1960              : 
    1961              :   /* Nothing to do if we reach ENTRY, or a common source block.  */
    1962     52348011 :   if (src1 == ENTRY_BLOCK_PTR_FOR_FN (cfun) || src2
    1963              :       == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    1964              :     return false;
    1965     52347581 :   if (src1 == src2)
    1966              :     return false;
    1967              : 
    1968              :   /* Seeing more than 1 forwarder blocks would confuse us later...  */
    1969     52347450 :   if (FORWARDER_BLOCK_P (e1->dest)
    1970     52347450 :       && FORWARDER_BLOCK_P (single_succ (e1->dest)))
    1971              :     return false;
    1972              : 
    1973     52336025 :   if (FORWARDER_BLOCK_P (e2->dest)
    1974     52336025 :       && FORWARDER_BLOCK_P (single_succ (e2->dest)))
    1975              :     return false;
    1976              : 
    1977              :   /* Likewise with dead code (possibly newly created by the other optimizations
    1978              :      of cfg_cleanup).  */
    1979     52335474 :   if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
    1980              :     return false;
    1981              : 
    1982              :   /* Do not turn corssing edge to non-crossing or vice versa after reload.  */
    1983     47670220 :   if (BB_PARTITION (src1) != BB_PARTITION (src2)
    1984       167547 :       && reload_completed)
    1985              :     return false;
    1986              : 
    1987              :   /* Look for the common insn sequence, part the first ...  */
    1988     47502673 :   if (!outgoing_edges_match (mode, src1, src2))
    1989              :     return false;
    1990              : 
    1991              :   /* ... and part the second.  */
    1992     15989191 :   nmatch = flow_find_cross_jump (src1, src2, &newpos1, &newpos2, &dir);
    1993              : 
    1994     15989191 :   osrc1 = src1;
    1995     15989191 :   osrc2 = src2;
    1996     15989191 :   if (newpos1 != NULL_RTX)
    1997      5156345 :     src1 = BLOCK_FOR_INSN (newpos1);
    1998     15989191 :   if (newpos2 != NULL_RTX)
    1999      5156345 :     src2 = BLOCK_FOR_INSN (newpos2);
    2000              : 
    2001              :   /* Check that SRC1 and SRC2 have preds again.  They may have changed
    2002              :      above due to the call to flow_find_cross_jump.  */
    2003     15989191 :   if (EDGE_COUNT (src1->preds) == 0 || EDGE_COUNT (src2->preds) == 0)
    2004              :     return false;
    2005              : 
    2006     15989191 :   if (dir == dir_backward)
    2007              :     {
    2008         1713 :       std::swap (osrc1, osrc2);
    2009         1713 :       std::swap (src1, src2);
    2010         1713 :       std::swap (e1, e2);
    2011         1713 :       std::swap (newpos1, newpos2);
    2012              :     }
    2013              : 
    2014              :   /* Don't proceed with the crossjump unless we found a sufficient number
    2015              :      of matching instructions or the 'from' block was totally matched
    2016              :      (such that its predecessors will hopefully be redirected and the
    2017              :      block removed).  */
    2018     15989191 :   if ((nmatch < param_min_crossjump_insns)
    2019     15857713 :       && (newpos1 != BB_HEAD (src1)))
    2020              :     return false;
    2021              : 
    2022              :   /* Avoid deleting preserve label when redirecting ABNORMAL edges.  */
    2023       376698 :   if (block_has_preserve_label (e1->dest)
    2024       376698 :       && (e1->flags & EDGE_ABNORMAL))
    2025              :     return false;
    2026              : 
    2027              :   /* Here we know that the insns in the end of SRC1 which are common with SRC2
    2028              :      will be deleted.
    2029              :      If we have tablejumps in the end of SRC1 and SRC2
    2030              :      they have been already compared for equivalence in outgoing_edges_match ()
    2031              :      so replace the references to TABLE1 by references to TABLE2.  */
    2032       342231 :   {
    2033       342231 :       rtx_insn *label1, *label2;
    2034       342231 :       rtx_jump_table_data *table1, *table2;
    2035              : 
    2036       342231 :       if (tablejump_p (BB_END (osrc1), &label1, &table1)
    2037          189 :           && tablejump_p (BB_END (osrc2), &label2, &table2)
    2038       342420 :           && label1 != label2)
    2039              :         {
    2040          189 :           rtx_insn *insn;
    2041              : 
    2042              :           /* Replace references to LABEL1 with LABEL2.  */
    2043       565685 :           for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
    2044              :             {
    2045              :               /* Do not replace the label in SRC1->END because when deleting
    2046              :                  a block whose end is a tablejump, the tablejump referenced
    2047              :                  from the instruction is deleted too.  */
    2048       565496 :               if (insn != BB_END (osrc1))
    2049       565307 :                 replace_label_in_insn (insn, label1, label2, true);
    2050              :             }
    2051              :         }
    2052              :   }
    2053              : 
    2054              :   /* Avoid splitting if possible.  We must always split when SRC2 has
    2055              :      EH predecessor edges, or we may end up with basic blocks with both
    2056              :      normal and EH predecessor edges.  */
    2057       342231 :   if (newpos2 == BB_HEAD (src2)
    2058       342231 :       && !(EDGE_PRED (src2, 0)->flags & EDGE_EH))
    2059              :     redirect_to = src2;
    2060              :   else
    2061              :     {
    2062        89745 :       if (newpos2 == BB_HEAD (src2))
    2063              :         {
    2064              :           /* Skip possible basic block header.  */
    2065         6609 :           if (LABEL_P (newpos2))
    2066         6609 :             newpos2 = NEXT_INSN (newpos2);
    2067         6609 :           while (DEBUG_INSN_P (newpos2))
    2068            0 :             newpos2 = NEXT_INSN (newpos2);
    2069         6609 :           if (NOTE_P (newpos2))
    2070         6609 :             newpos2 = NEXT_INSN (newpos2);
    2071         6806 :           while (DEBUG_INSN_P (newpos2))
    2072          197 :             newpos2 = NEXT_INSN (newpos2);
    2073              :         }
    2074              : 
    2075        89745 :       if (dump_file)
    2076            2 :         fprintf (dump_file, "Splitting bb %i before %i insns\n",
    2077              :                  src2->index, nmatch);
    2078        89745 :       redirect_to = split_block (src2, PREV_INSN (newpos2))->dest;
    2079              :     }
    2080              : 
    2081       342231 :   if (dump_file)
    2082           42 :     fprintf (dump_file,
    2083              :              "Cross jumping from bb %i to bb %i; %i common insns\n",
    2084              :              src1->index, src2->index, nmatch);
    2085              : 
    2086              :   /* We may have some registers visible through the block.  */
    2087       342231 :   df_set_bb_dirty (redirect_to);
    2088              : 
    2089       342231 :   if (osrc2 == src2)
    2090              :     redirect_edges_to = redirect_to;
    2091              :   else
    2092        11131 :     redirect_edges_to = osrc2;
    2093              : 
    2094              :   /* Recompute the counts of destinations of outgoing edges.  */
    2095       756373 :   FOR_EACH_EDGE (s, ei, redirect_edges_to->succs)
    2096              :     {
    2097       414142 :       edge s2;
    2098       414142 :       edge_iterator ei;
    2099       414142 :       basic_block d = s->dest;
    2100              : 
    2101       414142 :       if (FORWARDER_BLOCK_P (d))
    2102        30654 :         d = single_succ (d);
    2103              : 
    2104       494582 :       FOR_EACH_EDGE (s2, ei, src1->succs)
    2105              :         {
    2106       494582 :           basic_block d2 = s2->dest;
    2107       494582 :           if (FORWARDER_BLOCK_P (d2))
    2108       104205 :             d2 = single_succ (d2);
    2109       494582 :           if (d == d2)
    2110              :             break;
    2111              :         }
    2112              : 
    2113              :       /* Take care to update possible forwarder blocks.  We verified
    2114              :          that there is no more than one in the chain, so we can't run
    2115              :          into infinite loop.  */
    2116       414142 :       if (FORWARDER_BLOCK_P (s->dest))
    2117        30654 :         s->dest->count += s->count ();
    2118              : 
    2119       414142 :       if (FORWARDER_BLOCK_P (s2->dest))
    2120        80494 :         s2->dest->count -= s->count ();
    2121              : 
    2122       414142 :       s->probability = s->probability.combine_with_count
    2123       414142 :                           (redirect_edges_to->count,
    2124              :                            s2->probability, src1->count);
    2125              :     }
    2126              : 
    2127              :   /* Adjust count for the block.  An earlier jump
    2128              :      threading pass may have left the profile in an inconsistent
    2129              :      state (see update_bb_profile_for_threading) so we must be
    2130              :      prepared for overflows.  */
    2131              :   tmp = redirect_to;
    2132       365713 :   do
    2133              :     {
    2134       353972 :       tmp->count += src1->count;
    2135       353972 :       if (tmp == redirect_edges_to)
    2136              :         break;
    2137        11741 :       tmp = find_fallthru_edge (tmp->succs)->dest;
    2138              :     }
    2139              :   while (true);
    2140       342231 :   update_br_prob_note (redirect_edges_to);
    2141              : 
    2142              :   /* Edit SRC1 to go to REDIRECT_TO at NEWPOS1.  */
    2143              : 
    2144              :   /* Skip possible basic block header.  */
    2145       342231 :   if (LABEL_P (newpos1))
    2146       141280 :     newpos1 = NEXT_INSN (newpos1);
    2147              : 
    2148       357643 :   while (DEBUG_INSN_P (newpos1))
    2149        15412 :     newpos1 = NEXT_INSN (newpos1);
    2150              : 
    2151       599142 :   if (NOTE_INSN_BASIC_BLOCK_P (newpos1))
    2152       255649 :     newpos1 = NEXT_INSN (newpos1);
    2153              : 
    2154              :   /* Skip also prologue and function markers.  */
    2155      1016307 :   while (DEBUG_INSN_P (newpos1)
    2156      1016307 :          || (NOTE_P (newpos1)
    2157        16321 :              && (NOTE_KIND (newpos1) == NOTE_INSN_PROLOGUE_END
    2158        16321 :                  || NOTE_KIND (newpos1) == NOTE_INSN_FUNCTION_BEG)))
    2159       674076 :     newpos1 = NEXT_INSN (newpos1);
    2160              : 
    2161       342231 :   redirect_from = split_block (src1, PREV_INSN (newpos1))->src;
    2162       342231 :   to_remove = single_succ (redirect_from);
    2163              : 
    2164       342231 :   redirect_edge_and_branch_force (single_succ_edge (redirect_from), redirect_to);
    2165       342231 :   delete_basic_block (to_remove);
    2166              : 
    2167       342231 :   update_forwarder_flag (redirect_from);
    2168       342231 :   if (redirect_to != src2)
    2169        89745 :     update_forwarder_flag (src2);
    2170              : 
    2171              :   return true;
    2172              : }
    2173              : 
    2174              : /* Search the predecessors of BB for common insn sequences.  When found,
    2175              :    share code between them by redirecting control flow.  Return true if
    2176              :    any changes made.  */
    2177              : 
    2178              : static bool
    2179     30856713 : try_crossjump_bb (int mode, basic_block bb)
    2180              : {
    2181     30856713 :   edge e, e2, fallthru;
    2182     30856713 :   bool changed;
    2183     30856713 :   unsigned max, ix, ix2;
    2184              : 
    2185              :   /* Nothing to do if there is not at least two incoming edges.  */
    2186     30856713 :   if (EDGE_COUNT (bb->preds) < 2)
    2187              :     return false;
    2188              : 
    2189              :   /* Don't crossjump the predecessors of a computed jump when computed
    2190              :      gotos are duplicated (see pass_duplicate_computed_gotos::gate), as
    2191              :      that copies the jump back into each predecessor.  */
    2192      8465035 :   if (!optimize_function_for_size_p (cfun)
    2193      8253525 :       && flag_expensive_optimizations
    2194      8253348 :       && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
    2195     16255051 :       && computed_jump_p (BB_END (bb)))
    2196              :     return false;
    2197              : 
    2198              :   /* If we are partitioning hot/cold basic blocks, we don't want to
    2199              :      mess up unconditional or indirect jumps that cross between hot
    2200              :      and cold sections.
    2201              : 
    2202              :      Basic block partitioning may result in some jumps that appear to
    2203              :      be optimizable (or blocks that appear to be mergeable), but which really
    2204              :      must be left untouched (they are required to make it safely across
    2205              :      partition boundaries).  See the comments at the top of
    2206              :      bb-reorder.cc:partition_hot_cold_basic_blocks for complete details.  */
    2207              : 
    2208      8464919 :   if (BB_PARTITION (EDGE_PRED (bb, 0)->src) !=
    2209      8464919 :                                         BB_PARTITION (EDGE_PRED (bb, 1)->src)
    2210      8464919 :       || (EDGE_PRED (bb, 0)->flags & EDGE_CROSSING))
    2211              :     return false;
    2212              : 
    2213              :   /* It is always cheapest to redirect a block that ends in a branch to
    2214              :      a block that falls through into BB, as that adds no branches to the
    2215              :      program.  We'll try that combination first.  */
    2216      8258856 :   fallthru = NULL;
    2217      8258856 :   max = param_max_crossjump_edges;
    2218              : 
    2219      8258856 :   if (EDGE_COUNT (bb->preds) > max)
    2220              :     return false;
    2221              : 
    2222      8255905 :   fallthru = find_fallthru_edge (bb->preds);
    2223              : 
    2224      8255905 :   changed = false;
    2225     40605813 :   for (ix = 0; ix < EDGE_COUNT (bb->preds);)
    2226              :     {
    2227     24094003 :       e = EDGE_PRED (bb, ix);
    2228     24094003 :       ix++;
    2229              : 
    2230              :       /* As noted above, first try with the fallthru predecessor (or, a
    2231              :          fallthru predecessor if we are in cfglayout mode).  */
    2232     24094003 :       if (fallthru)
    2233              :         {
    2234              :           /* Don't combine the fallthru edge into anything else.
    2235              :              If there is a match, we'll do it the other way around.  */
    2236     17698035 :           if (e == fallthru)
    2237      6649879 :             continue;
    2238              :           /* If nothing changed since the last attempt, there is nothing
    2239              :              we can do.  */
    2240     11048156 :           if (!first_pass
    2241      4345827 :               && !((e->src->flags & BB_MODIFIED)
    2242      3442110 :                    || (fallthru->src->flags & BB_MODIFIED)))
    2243      3072931 :             continue;
    2244              : 
    2245      7975225 :           if (try_crossjump_to_edge (mode, e, fallthru, dir_forward))
    2246              :             {
    2247       150535 :               changed = true;
    2248       150535 :               ix = 0;
    2249       150535 :               continue;
    2250              :             }
    2251              :         }
    2252              : 
    2253              :       /* Non-obvious work limiting check: Recognize that we're going
    2254              :          to call try_crossjump_bb on every basic block.  So if we have
    2255              :          two blocks with lots of outgoing edges (a switch) and they
    2256              :          share lots of common destinations, then we would do the
    2257              :          cross-jump check once for each common destination.
    2258              : 
    2259              :          Now, if the blocks actually are cross-jump candidates, then
    2260              :          all of their destinations will be shared.  Which means that
    2261              :          we only need check them for cross-jump candidacy once.  We
    2262              :          can eliminate redundant checks of crossjump(A,B) by arbitrarily
    2263              :          choosing to do the check from the block for which the edge
    2264              :          in question is the first successor of A.  */
    2265     14220658 :       if (EDGE_SUCC (e->src, 0) != e)
    2266      2935832 :         continue;
    2267              : 
    2268    171034378 :       for (ix2 = 0; ix2 < EDGE_COUNT (bb->preds); ix2++)
    2269              :         {
    2270    127591340 :           e2 = EDGE_PRED (bb, ix2);
    2271              : 
    2272    127591340 :           if (e2 == e)
    2273     11191931 :             continue;
    2274              : 
    2275              :           /* We've already checked the fallthru edge above.  */
    2276    116399409 :           if (e2 == fallthru)
    2277      6234446 :             continue;
    2278              : 
    2279              :           /* The "first successor" check above only prevents multiple
    2280              :              checks of crossjump(A,B).  In order to prevent redundant
    2281              :              checks of crossjump(B,A), require that A be the block
    2282              :              with the lowest index.  */
    2283    110164963 :           if (e->src->index > e2->src->index)
    2284     54954757 :             continue;
    2285              : 
    2286              :           /* If nothing changed since the last attempt, there is nothing
    2287              :              we can do.  */
    2288     55210206 :           if (!first_pass
    2289     13898540 :               && !((e->src->flags & BB_MODIFIED)
    2290     11718800 :                    || (e2->src->flags & BB_MODIFIED)))
    2291     10837420 :             continue;
    2292              : 
    2293              :           /* Both e and e2 are not fallthru edges, so we can crossjump in either
    2294              :              direction.  */
    2295     44372786 :           if (try_crossjump_to_edge (mode, e, e2, dir_both))
    2296              :             {
    2297              :               changed = true;
    2298              :               ix = 0;
    2299              :               break;
    2300              :             }
    2301              :         }
    2302              :     }
    2303              : 
    2304      8255905 :   if (changed)
    2305       166637 :     crossjumps_occurred = true;
    2306              : 
    2307              :   return changed;
    2308              : }
    2309              : 
    2310              : /* Search the successors of BB for common insn sequences.  When found,
    2311              :    share code between them by moving it across the basic block
    2312              :    boundary.  Return true if any changes made.  */
    2313              : 
    2314              : static bool
    2315     29632901 : try_head_merge_bb (basic_block bb)
    2316              : {
    2317     29632901 :   basic_block final_dest_bb = NULL;
    2318     29632901 :   int max_match = INT_MAX;
    2319     29632901 :   edge e0;
    2320     29632901 :   rtx_insn **headptr, **currptr, **nextptr;
    2321     29632901 :   bool changed, moveall;
    2322     29632901 :   unsigned ix;
    2323     29632901 :   rtx_insn *e0_last_head;
    2324     29632901 :   rtx cond;
    2325     29632901 :   rtx_insn *move_before;
    2326     29632901 :   unsigned nedges = EDGE_COUNT (bb->succs);
    2327     29632901 :   rtx_insn *jump = BB_END (bb);
    2328     29632901 :   regset live, live_union;
    2329              : 
    2330              :   /* Nothing to do if there is not at least two outgoing edges.  */
    2331     29632901 :   if (nedges < 2)
    2332              :     return false;
    2333              : 
    2334              :   /* Don't crossjump if this block ends in a computed jump,
    2335              :      unless we are optimizing for size.  */
    2336     15212535 :   if (optimize_bb_for_size_p (bb)
    2337      1842041 :       && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)
    2338     17054576 :       && computed_jump_p (BB_END (bb)))
    2339              :     return false;
    2340              : 
    2341     15212486 :   cond = get_condition (jump, &move_before, true, false);
    2342     15212486 :   if (cond == NULL_RTX)
    2343      2123293 :     move_before = jump;
    2344              : 
    2345     45958360 :   for (ix = 0; ix < nedges; ix++)
    2346     30745874 :     if (EDGE_SUCC (bb, ix)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
    2347              :       return false;
    2348              : 
    2349     28359938 :   for (ix = 0; ix < nedges; ix++)
    2350              :     {
    2351     23719840 :       edge e = EDGE_SUCC (bb, ix);
    2352     23719840 :       basic_block other_bb = e->dest;
    2353              : 
    2354     23719840 :       if (df_get_bb_dirty (other_bb))
    2355              :         {
    2356       560686 :           block_was_dirty = true;
    2357       560686 :           return false;
    2358              :         }
    2359              : 
    2360     23159154 :       if (e->flags & EDGE_ABNORMAL)
    2361              :         return false;
    2362              : 
    2363              :       /* Normally, all destination blocks must only be reachable from this
    2364              :          block, i.e. they must have one incoming edge.
    2365              : 
    2366              :          There is one special case we can handle, that of multiple consecutive
    2367              :          jumps where the first jumps to one of the targets of the second jump.
    2368              :          This happens frequently in switch statements for default labels.
    2369              :          The structure is as follows:
    2370              :          FINAL_DEST_BB
    2371              :          ....
    2372              :          if (cond) jump A;
    2373              :          fall through
    2374              :          BB
    2375              :          jump with targets A, B, C, D...
    2376              :          A
    2377              :          has two incoming edges, from FINAL_DEST_BB and BB
    2378              : 
    2379              :          In this case, we can try to move the insns through BB and into
    2380              :          FINAL_DEST_BB.  */
    2381     21117730 :       if (EDGE_COUNT (other_bb->preds) != 1)
    2382              :         {
    2383      8343081 :           edge incoming_edge, incoming_bb_other_edge;
    2384      8343081 :           edge_iterator ei;
    2385              : 
    2386      8343081 :           if (final_dest_bb != NULL
    2387      8343081 :               || EDGE_COUNT (other_bb->preds) != 2)
    2388      7970278 :             return false;
    2389              : 
    2390              :           /* We must be able to move the insns across the whole block.  */
    2391      4596574 :           move_before = BB_HEAD (bb);
    2392     29988059 :           while (!NONDEBUG_INSN_P (move_before))
    2393     25391485 :             move_before = NEXT_INSN (move_before);
    2394              : 
    2395      4596574 :           if (EDGE_COUNT (bb->preds) != 1)
    2396              :             return false;
    2397      2788331 :           incoming_edge = EDGE_PRED (bb, 0);
    2398      2788331 :           final_dest_bb = incoming_edge->src;
    2399     10269508 :           if (EDGE_COUNT (final_dest_bb->succs) != 2)
    2400              :             return false;
    2401      3309939 :           FOR_EACH_EDGE (incoming_bb_other_edge, ei, final_dest_bb->succs)
    2402      3309939 :             if (incoming_bb_other_edge != incoming_edge)
    2403              :               break;
    2404      2299230 :           if (incoming_bb_other_edge->dest != other_bb)
    2405              :             return false;
    2406              :         }
    2407              :     }
    2408              : 
    2409      4640098 :   e0 = EDGE_SUCC (bb, 0);
    2410      4640098 :   e0_last_head = NULL;
    2411      4640098 :   changed = false;
    2412              : 
    2413      4763867 :   for (ix = 1; ix < nedges; ix++)
    2414              :     {
    2415      4645080 :       edge e = EDGE_SUCC (bb, ix);
    2416      4645080 :       rtx_insn *e0_last, *e_last;
    2417      4645080 :       int nmatch;
    2418              : 
    2419      4645080 :       nmatch = flow_find_head_matching_sequence (e0->dest, e->dest,
    2420              :                                                  &e0_last, &e_last, 0);
    2421      4645080 :       if (nmatch == 0)
    2422      4521311 :         return false;
    2423              : 
    2424       123769 :       if (nmatch < max_match)
    2425              :         {
    2426       119783 :           max_match = nmatch;
    2427       119783 :           e0_last_head = e0_last;
    2428              :         }
    2429              :     }
    2430              : 
    2431              :   /* If we matched an entire block, we probably have to avoid moving the
    2432              :      last insn.  */
    2433       118787 :   if (max_match > 0
    2434       118787 :       && e0_last_head == BB_END (e0->dest)
    2435       127852 :       && (find_reg_note (e0_last_head, REG_EH_REGION, 0)
    2436         7507 :           || control_flow_insn_p (e0_last_head)))
    2437              :     {
    2438         1571 :       max_match--;
    2439         1571 :       if (max_match == 0)
    2440              :         return false;
    2441          254 :       e0_last_head = prev_real_nondebug_insn (e0_last_head);
    2442              :     }
    2443              : 
    2444       117470 :   if (max_match == 0)
    2445              :     return false;
    2446              : 
    2447              :   /* We must find a union of the live registers at each of the end points.  */
    2448       117470 :   live = BITMAP_ALLOC (NULL);
    2449       117470 :   live_union = BITMAP_ALLOC (NULL);
    2450              : 
    2451       117470 :   currptr = XNEWVEC (rtx_insn *, nedges);
    2452       117470 :   headptr = XNEWVEC (rtx_insn *, nedges);
    2453       117470 :   nextptr = XNEWVEC (rtx_insn *, nedges);
    2454              : 
    2455       473220 :   for (ix = 0; ix < nedges; ix++)
    2456              :     {
    2457       238280 :       int j;
    2458       238280 :       basic_block merge_bb = EDGE_SUCC (bb, ix)->dest;
    2459       238280 :       rtx_insn *head = BB_HEAD (merge_bb);
    2460              : 
    2461      1594718 :       while (!NONDEBUG_INSN_P (head))
    2462      1356438 :         head = NEXT_INSN (head);
    2463       238280 :       headptr[ix] = head;
    2464       238280 :       currptr[ix] = head;
    2465              : 
    2466              :       /* Compute the end point and live information  */
    2467       380987 :       for (j = 1; j < max_match; j++)
    2468       204434 :         do
    2469       204434 :           head = NEXT_INSN (head);
    2470       204434 :         while (!NONDEBUG_INSN_P (head));
    2471       238280 :       simulate_backwards_to_point (merge_bb, live, head);
    2472       238280 :       IOR_REG_SET (live_union, live);
    2473              :     }
    2474              : 
    2475              :   /* If we're moving across two blocks, verify the validity of the
    2476              :      first move, then adjust the target and let the loop below deal
    2477              :      with the final move.  */
    2478       117470 :   if (final_dest_bb != NULL)
    2479              :     {
    2480         7769 :       rtx_insn *move_upto;
    2481              : 
    2482         7769 :       moveall = can_move_insns_across (currptr[0], e0_last_head, move_before,
    2483              :                                        jump, e0->dest, live_union,
    2484              :                                        NULL, &move_upto);
    2485         7769 :       if (!moveall)
    2486              :         {
    2487         6125 :           if (move_upto == NULL_RTX)
    2488         5742 :             goto out;
    2489              : 
    2490         1193 :           while (e0_last_head != move_upto)
    2491              :             {
    2492          810 :               df_simulate_one_insn_backwards (e0->dest, e0_last_head,
    2493              :                                               live_union);
    2494          810 :               e0_last_head = PREV_INSN (e0_last_head);
    2495              :             }
    2496              :         }
    2497         2027 :       if (e0_last_head == NULL_RTX)
    2498            0 :         goto out;
    2499              : 
    2500         2027 :       jump = BB_END (final_dest_bb);
    2501         2027 :       cond = get_condition (jump, &move_before, true, false);
    2502         2027 :       if (cond == NULL_RTX)
    2503            0 :         move_before = jump;
    2504              :     }
    2505              : 
    2506       192279 :   do
    2507              :     {
    2508       192279 :       rtx_insn *move_upto;
    2509       192279 :       moveall = can_move_insns_across (currptr[0], e0_last_head,
    2510              :                                        move_before, jump, e0->dest, live_union,
    2511              :                                        NULL, &move_upto);
    2512       192279 :       if (!moveall && move_upto == NULL_RTX)
    2513              :         {
    2514       151893 :           if (jump == move_before)
    2515              :             break;
    2516              : 
    2517              :           /* Try again, using a different insertion point.  */
    2518        76545 :           move_before = jump;
    2519              : 
    2520        76545 :           continue;
    2521              :         }
    2522              : 
    2523        40386 :       if (final_dest_bb && !moveall)
    2524              :         /* We haven't checked whether a partial move would be OK for the first
    2525              :            move, so we have to fail this case.  */
    2526              :         break;
    2527              : 
    2528        57805 :       changed = true;
    2529        57805 :       for (;;)
    2530              :         {
    2531        57805 :           if (currptr[0] == move_upto)
    2532              :             break;
    2533        52382 :           for (ix = 0; ix < nedges; ix++)
    2534              :             {
    2535        34943 :               rtx_insn *curr = currptr[ix];
    2536        54430 :               do
    2537        54430 :                 curr = NEXT_INSN (curr);
    2538        54430 :               while (!NONDEBUG_INSN_P (curr));
    2539        34943 :               currptr[ix] = curr;
    2540              :             }
    2541              :         }
    2542              : 
    2543              :       /* If we can't currently move all of the identical insns, remember
    2544              :          each insn after the range that we'll merge.  */
    2545        40366 :       if (!moveall)
    2546        17337 :         for (ix = 0; ix < nedges; ix++)
    2547              :           {
    2548        11563 :             rtx_insn *curr = currptr[ix];
    2549        16385 :             do
    2550        16385 :               curr = NEXT_INSN (curr);
    2551        16385 :             while (!NONDEBUG_INSN_P (curr));
    2552        11563 :             nextptr[ix] = curr;
    2553              :           }
    2554              : 
    2555        40366 :       reorder_insns (headptr[0], currptr[0], PREV_INSN (move_before));
    2556        40366 :       df_set_bb_dirty (EDGE_SUCC (bb, 0)->dest);
    2557        40366 :       if (final_dest_bb != NULL)
    2558         2007 :         df_set_bb_dirty (final_dest_bb);
    2559        40366 :       df_set_bb_dirty (bb);
    2560       122370 :       for (ix = 1; ix < nedges; ix++)
    2561              :         {
    2562        41638 :           df_set_bb_dirty (EDGE_SUCC (bb, ix)->dest);
    2563        41638 :           delete_insn_chain (headptr[ix], currptr[ix], false);
    2564              :         }
    2565        40366 :       if (!moveall)
    2566              :         {
    2567         5774 :           if (jump == move_before)
    2568              :             break;
    2569              : 
    2570              :           /* For the unmerged insns, try a different insertion point.  */
    2571         4006 :           move_before = jump;
    2572              : 
    2573        12018 :           for (ix = 0; ix < nedges; ix++)
    2574         8012 :             currptr[ix] = headptr[ix] = nextptr[ix];
    2575              :         }
    2576              :     }
    2577       115143 :   while (!moveall);
    2578              : 
    2579        34592 :  out:
    2580       117470 :   free (currptr);
    2581       117470 :   free (headptr);
    2582       117470 :   free (nextptr);
    2583              : 
    2584       117470 :   crossjumps_occurred |= changed;
    2585              : 
    2586       117470 :   return changed;
    2587              : }
    2588              : 
    2589              : /* Return true if BB contains just bb note, or bb note followed
    2590              :    by only DEBUG_INSNs.  */
    2591              : 
    2592              : static bool
    2593     16708514 : trivially_empty_bb_p (basic_block bb)
    2594              : {
    2595     16708514 :   rtx_insn *insn = BB_END (bb);
    2596              : 
    2597         5598 :   while (1)
    2598              :     {
    2599     16714112 :       if (insn == BB_HEAD (bb))
    2600              :         return true;
    2601     16713155 :       if (!DEBUG_INSN_P (insn))
    2602              :         return false;
    2603         5598 :       insn = PREV_INSN (insn);
    2604              :     }
    2605              : }
    2606              : 
    2607              : /* Return true if BB contains just a return and possibly a USE of the
    2608              :    return value.  Fill in *RET and *USE with the return and use insns
    2609              :    if any found, otherwise NULL.  All CLOBBERs are ignored.  */
    2610              : 
    2611              : bool
    2612    409571927 : bb_is_just_return (basic_block bb, rtx_insn **ret, rtx_insn **use)
    2613              : {
    2614    409571927 :   *ret = *use = NULL;
    2615    409571927 :   rtx_insn *insn;
    2616              : 
    2617    409571927 :   if (bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
    2618              :     return false;
    2619              : 
    2620    543628959 :   FOR_BB_INSNS_REVERSE (bb, insn)
    2621    529837527 :     if (NONDEBUG_INSN_P (insn))
    2622              :       {
    2623    404822909 :         rtx pat = PATTERN (insn);
    2624              : 
    2625    404822909 :         if (!*ret && ANY_RETURN_P (pat))
    2626      7552461 :           *ret = insn;
    2627      7907744 :         else if (*ret && !*use && GET_CODE (pat) == USE
    2628      1155196 :             && REG_P (XEXP (pat, 0))
    2629    398425644 :             && REG_FUNCTION_VALUE_P (XEXP (pat, 0)))
    2630      1151798 :           *use = insn;
    2631    396118650 :         else if (GET_CODE (pat) != CLOBBER)
    2632              :           return false;
    2633              :       }
    2634              : 
    2635     13791432 :   return !!*ret;
    2636              : }
    2637              : 
    2638              : /* Do simple CFG optimizations - basic block merging, simplifying of jump
    2639              :    instructions etc.  Return nonzero if changes were made.  */
    2640              : 
    2641              : static bool
    2642     22291633 : try_optimize_cfg (int mode)
    2643              : {
    2644     22291633 :   bool changed_overall = false;
    2645     22291633 :   bool changed;
    2646     22291633 :   int iterations = 0;
    2647     22291633 :   basic_block bb, b, next;
    2648              : 
    2649     22291633 :   if (mode & (CLEANUP_CROSSJUMP | CLEANUP_THREADING))
    2650      3040657 :     clear_bb_flags ();
    2651              : 
    2652     22291633 :   crossjumps_occurred = false;
    2653              : 
    2654    324856035 :   FOR_EACH_BB_FN (bb, cfun)
    2655    302564402 :     update_forwarder_flag (bb);
    2656              : 
    2657     22291633 :   if (! targetm.cannot_modify_jumps_p ())
    2658              :     {
    2659     22291633 :       first_pass = true;
    2660              :       /* Attempt to merge blocks as made possible by edge removal.  If
    2661              :          a block has only one successor, and the successor has only
    2662              :          one predecessor, they may be combined.  */
    2663     52382588 :       do
    2664              :         {
    2665     26191294 :           block_was_dirty = false;
    2666     26191294 :           changed = false;
    2667     26191294 :           iterations++;
    2668              : 
    2669     26191294 :           if (dump_file)
    2670         1854 :             fprintf (dump_file,
    2671              :                      "\n\ntry_optimize_cfg iteration %i\n\n",
    2672              :                      iterations);
    2673              : 
    2674     26191294 :           for (b = ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb; b
    2675    438952252 :                != EXIT_BLOCK_PTR_FOR_FN (cfun);)
    2676              :             {
    2677    412760958 :               basic_block c;
    2678    412760958 :               edge s;
    2679    412760958 :               bool changed_here = false;
    2680              : 
    2681              :               /* Delete trivially dead basic blocks.  This is either
    2682              :                  blocks with no predecessors, or empty blocks with no
    2683              :                  successors.  However if the empty block with no
    2684              :                  successors is the successor of the ENTRY_BLOCK, it is
    2685              :                  kept.  This ensures that the ENTRY_BLOCK will have a
    2686              :                  successor which is a precondition for many RTL
    2687              :                  passes.  Empty blocks may result from expanding
    2688              :                  __builtin_unreachable ().  */
    2689    412760958 :               if (EDGE_COUNT (b->preds) == 0
    2690    412760958 :                   || (EDGE_COUNT (b->succs) == 0
    2691     16708514 :                       && trivially_empty_bb_p (b)
    2692          957 :                       && single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun))->dest
    2693              :                       != b))
    2694              :                 {
    2695      5671267 :                   c = b->prev_bb;
    2696      5671267 :                   if (EDGE_COUNT (b->preds) > 0)
    2697              :                     {
    2698          957 :                       edge e;
    2699          957 :                       edge_iterator ei;
    2700              : 
    2701          957 :                       if (current_ir_type () == IR_RTL_CFGLAYOUT)
    2702              :                         {
    2703           51 :                           rtx_insn *insn;
    2704           51 :                           for (insn = BB_FOOTER (b);
    2705           51 :                                insn; insn = NEXT_INSN (insn))
    2706           51 :                             if (BARRIER_P (insn))
    2707              :                               break;
    2708           51 :                           if (insn)
    2709          102 :                             FOR_EACH_EDGE (e, ei, b->preds)
    2710           51 :                               if ((e->flags & EDGE_FALLTHRU))
    2711              :                                 {
    2712           51 :                                   if (BB_FOOTER (b)
    2713           51 :                                       && BB_FOOTER (e->src) == NULL)
    2714              :                                     {
    2715           51 :                                       BB_FOOTER (e->src) = BB_FOOTER (b);
    2716           51 :                                       BB_FOOTER (b) = NULL;
    2717              :                                     }
    2718              :                                   else
    2719            0 :                                     emit_barrier_after_bb (e->src);
    2720              :                                 }
    2721              :                         }
    2722              :                       else
    2723              :                         {
    2724          906 :                           rtx_insn *last = get_last_bb_insn (b);
    2725          906 :                           if (last && BARRIER_P (last))
    2726         1812 :                             FOR_EACH_EDGE (e, ei, b->preds)
    2727          906 :                               if ((e->flags & EDGE_FALLTHRU))
    2728          906 :                                 emit_barrier_after (BB_END (e->src));
    2729              :                         }
    2730              :                     }
    2731      5671267 :                   delete_basic_block (b);
    2732      5671267 :                   changed = true;
    2733              :                   /* Avoid trying to remove the exit block.  */
    2734      5671267 :                   b = (c == ENTRY_BLOCK_PTR_FOR_FN (cfun) ? c->next_bb : c);
    2735      5807863 :                   continue;
    2736      5671267 :                 }
    2737              : 
    2738              :               /* Remove code labels no longer used.  */
    2739    407089691 :               if (single_pred_p (b)
    2740    296117228 :                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
    2741    208605992 :                   && !(single_pred_edge (b)->flags & EDGE_COMPLEX)
    2742    205384378 :                   && LABEL_P (BB_HEAD (b))
    2743       843793 :                   && !LABEL_PRESERVE_P (BB_HEAD (b))
    2744              :                   /* If the previous block ends with a branch to this
    2745              :                      block, we can't delete the label.  Normally this
    2746              :                      is a condjump that is yet to be simplified, but
    2747              :                      if CASE_DROPS_THRU, this can be a tablejump with
    2748              :                      some element going to the same place as the
    2749              :                      default (fallthru).  */
    2750    407918186 :                   && (single_pred (b) == ENTRY_BLOCK_PTR_FOR_FN (cfun)
    2751       828444 :                       || !JUMP_P (BB_END (single_pred (b)))
    2752       632699 :                       || ! label_is_jump_target_p (BB_HEAD (b),
    2753       632699 :                                                    BB_END (single_pred (b)))))
    2754              :                 {
    2755       821807 :                   delete_insn (BB_HEAD (b));
    2756       821807 :                   if (dump_file)
    2757           37 :                     fprintf (dump_file, "Deleted label in block %i.\n",
    2758              :                              b->index);
    2759              :                 }
    2760              : 
    2761              :               /* If we fall through an empty block, we can remove it.  */
    2762    407226287 :               if (!(mode & (CLEANUP_CFGLAYOUT | CLEANUP_NO_INSN_DEL))
    2763     86830975 :                   && single_pred_p (b)
    2764     64257018 :                   && (single_pred_edge (b)->flags & EDGE_FALLTHRU)
    2765     45511092 :                   && !LABEL_P (BB_HEAD (b))
    2766     45079563 :                   && FORWARDER_BLOCK_P (b)
    2767              :                   /* Note that forwarder_block_p true ensures that
    2768              :                      there is a successor for this block.  */
    2769      5331894 :                   && (single_succ_edge (b)->flags & EDGE_FALLTHRU)
    2770    407313327 :                   && n_basic_blocks_for_fn (cfun) > NUM_FIXED_BLOCKS + 1)
    2771              :                 {
    2772       136596 :                   if (dump_file)
    2773           11 :                     fprintf (dump_file,
    2774              :                              "Deleting fallthru block %i.\n",
    2775              :                              b->index);
    2776              : 
    2777         2629 :                   c = ((b->prev_bb == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    2778       136596 :                        ? b->next_bb : b->prev_bb);
    2779       136596 :                   redirect_edge_succ_nodup (single_pred_edge (b),
    2780              :                                             single_succ (b));
    2781       136596 :                   delete_basic_block (b);
    2782       136596 :                   changed = true;
    2783       136596 :                   b = c;
    2784       136596 :                   continue;
    2785              :                 }
    2786              : 
    2787              :               /* Merge B with its single successor, if any.  */
    2788    812145448 :               if (single_succ_p (b)
    2789    178053325 :                   && (s = single_succ_edge (b))
    2790    178053325 :                   && !(s->flags & EDGE_COMPLEX)
    2791    168853858 :                   && (c = s->dest) != EXIT_BLOCK_PTR_FOR_FN (cfun)
    2792    142576173 :                   && single_pred_p (c)
    2793    414016078 :                   && b != c)
    2794              :                 {
    2795              :                   /* When not in cfg_layout mode use code aware of reordering
    2796              :                      INSN.  This code possibly creates new basic blocks so it
    2797              :                      does not fit merge_blocks interface and is kept here in
    2798              :                      hope that it will become useless once more of compiler
    2799              :                      is transformed to use cfg_layout mode.  */
    2800              : 
    2801      8823725 :                   if ((mode & CLEANUP_CFGLAYOUT)
    2802      8823725 :                       && can_merge_blocks_p (b, c))
    2803              :                     {
    2804       733367 :                       merge_blocks (b, c);
    2805       733367 :                       update_forwarder_flag (b);
    2806       733367 :                       changed_here = true;
    2807              :                     }
    2808      8090358 :                   else if (!(mode & CLEANUP_CFGLAYOUT)
    2809              :                            /* If the jump insn has side effects,
    2810              :                               we can't kill the edge.  */
    2811      6888451 :                            && (!JUMP_P (BB_END (b))
    2812      2182732 :                                || (reload_completed
    2813      3034363 :                                    ? simplejump_p (BB_END (b))
    2814       851631 :                                    : (onlyjump_p (BB_END (b))
    2815       850783 :                                       && !tablejump_p (BB_END (b),
    2816              :                                                        NULL, NULL))))
    2817     18011119 :                            && (next = merge_blocks_move (s, b, c, mode)))
    2818              :                       {
    2819              :                         b = next;
    2820              :                         changed_here = true;
    2821              :                       }
    2822              :                 }
    2823              : 
    2824              :               /* Try to change a branch to a return to just that return.  */
    2825    406953095 :               rtx_insn *ret, *use;
    2826    406953095 :               if (single_succ_p (b)
    2827    176403233 :                   && onlyjump_p (BB_END (b))
    2828    434696701 :                   && bb_is_just_return (single_succ (b), &ret, &use))
    2829              :                 {
    2830        38112 :                   if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
    2831        38112 :                                      PATTERN (ret), 0))
    2832              :                     {
    2833        38112 :                       if (use)
    2834        22759 :                         emit_insn_before (copy_insn (PATTERN (use)),
    2835        22759 :                                           BB_END (b));
    2836        38112 :                       if (dump_file)
    2837           23 :                         fprintf (dump_file, "Changed jump %d->%d to return.\n",
    2838           23 :                                  b->index, single_succ (b)->index);
    2839        38112 :                       redirect_edge_succ (single_succ_edge (b),
    2840        38112 :                                           EXIT_BLOCK_PTR_FOR_FN (cfun));
    2841        38112 :                       single_succ_edge (b)->flags &= ~EDGE_CROSSING;
    2842        38112 :                       changed_here = true;
    2843              :                     }
    2844              :                 }
    2845              : 
    2846              :               /* Try to change a conditional branch to a return to the
    2847              :                  respective conditional return.  */
    2848    406953095 :               if (EDGE_COUNT (b->succs) == 2
    2849    213356057 :                   && any_condjump_p (BB_END (b))
    2850    593027206 :                   && bb_is_just_return (BRANCH_EDGE (b)->dest, &ret, &use))
    2851              :                 {
    2852       601855 :                   if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
    2853       601855 :                                      PATTERN (ret), 0))
    2854              :                     {
    2855            0 :                       if (use)
    2856            0 :                         emit_insn_before (copy_insn (PATTERN (use)),
    2857            0 :                                           BB_END (b));
    2858            0 :                       if (dump_file)
    2859            0 :                         fprintf (dump_file, "Changed conditional jump %d->%d "
    2860              :                                  "to conditional return.\n",
    2861            0 :                                  b->index, BRANCH_EDGE (b)->dest->index);
    2862            0 :                       redirect_edge_succ (BRANCH_EDGE (b),
    2863            0 :                                           EXIT_BLOCK_PTR_FOR_FN (cfun));
    2864            0 :                       BRANCH_EDGE (b)->flags &= ~EDGE_CROSSING;
    2865            0 :                       changed_here = true;
    2866              :                     }
    2867              :                 }
    2868              : 
    2869              :               /* Try to flip a conditional branch that falls through to
    2870              :                  a return so that it becomes a conditional return and a
    2871              :                  new jump to the original branch target.  */
    2872    406953095 :               if (EDGE_COUNT (b->succs) == 2
    2873    213356057 :                   && BRANCH_EDGE (b)->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
    2874    213356057 :                   && any_condjump_p (BB_END (b))
    2875    593027206 :                   && bb_is_just_return (FALLTHRU_EDGE (b)->dest, &ret, &use))
    2876              :                 {
    2877       164397 :                   if (invert_jump (as_a <rtx_jump_insn *> (BB_END (b)),
    2878       164397 :                                    JUMP_LABEL (BB_END (b)), 0))
    2879              :                     {
    2880       164397 :                       basic_block new_ft = BRANCH_EDGE (b)->dest;
    2881       164397 :                       if (redirect_jump (as_a <rtx_jump_insn *> (BB_END (b)),
    2882       164397 :                                          PATTERN (ret), 0))
    2883              :                         {
    2884            0 :                           if (use)
    2885            0 :                             emit_insn_before (copy_insn (PATTERN (use)),
    2886            0 :                                               BB_END (b));
    2887            0 :                           if (dump_file)
    2888            0 :                             fprintf (dump_file, "Changed conditional jump "
    2889              :                                      "%d->%d to conditional return, adding "
    2890              :                                      "fall-through jump.\n",
    2891            0 :                                      b->index, BRANCH_EDGE (b)->dest->index);
    2892            0 :                           redirect_edge_succ (BRANCH_EDGE (b),
    2893            0 :                                               EXIT_BLOCK_PTR_FOR_FN (cfun));
    2894            0 :                           BRANCH_EDGE (b)->flags &= ~EDGE_CROSSING;
    2895            0 :                           std::swap (BRANCH_EDGE (b)->probability,
    2896            0 :                                      FALLTHRU_EDGE (b)->probability);
    2897            0 :                           update_br_prob_note (b);
    2898            0 :                           basic_block jb = force_nonfallthru (FALLTHRU_EDGE (b));
    2899            0 :                           notice_new_block (jb);
    2900            0 :                           if (!redirect_jump (as_a <rtx_jump_insn *> (BB_END (jb)),
    2901            0 :                                               block_label (new_ft), 0))
    2902            0 :                             gcc_unreachable ();
    2903            0 :                           redirect_edge_succ (single_succ_edge (jb), new_ft);
    2904            0 :                           changed_here = true;
    2905              :                         }
    2906              :                       else
    2907              :                         {
    2908              :                           /* Invert the jump back to what it was.  This should
    2909              :                              never fail.  */
    2910       164397 :                           if (!invert_jump (as_a <rtx_jump_insn *> (BB_END (b)),
    2911       164397 :                                             JUMP_LABEL (BB_END (b)), 0))
    2912            0 :                             gcc_unreachable ();
    2913              :                         }
    2914              :                     }
    2915              :                 }
    2916              : 
    2917              :               /* Simplify branch over branch.  */
    2918    406953095 :               if ((mode & CLEANUP_EXPENSIVE)
    2919    107371606 :                    && !(mode & CLEANUP_CFGLAYOUT)
    2920    441864040 :                    && try_simplify_condjump (b))
    2921              :                 changed_here = true;
    2922              : 
    2923              :               /* If B has a single outgoing edge, but uses a
    2924              :                  non-trivial jump instruction without side-effects, we
    2925              :                  can either delete the jump entirely, or replace it
    2926              :                  with a simple unconditional jump.  */
    2927    406953095 :               if (single_succ_p (b)
    2928    176403295 :                   && single_succ (b) != EXIT_BLOCK_PTR_FOR_FN (cfun)
    2929    146079133 :                   && onlyjump_p (BB_END (b))
    2930     29534598 :                   && !CROSSING_JUMP_P (BB_END (b))
    2931    433577037 :                   && try_redirect_by_replacing_jump (single_succ_edge (b),
    2932              :                                                      single_succ (b),
    2933     28453661 :                                                      (mode & CLEANUP_CFGLAYOUT) != 0))
    2934              :                 {
    2935      4353877 :                   update_forwarder_flag (b);
    2936      4353877 :                   changed_here = true;
    2937              :                 }
    2938              : 
    2939              :               /* Simplify branch to branch.  */
    2940    406953095 :               if (try_forward_edges (mode, b))
    2941              :                 {
    2942      6556523 :                   update_forwarder_flag (b);
    2943      6556523 :                   changed_here = true;
    2944              :                 }
    2945              : 
    2946              :               /* Look for shared code between blocks.  */
    2947    406953095 :               if ((mode & CLEANUP_CROSSJUMP)
    2948    406953095 :                   && try_crossjump_bb (mode, b))
    2949              :                 changed_here = true;
    2950              : 
    2951    406953095 :               if ((mode & CLEANUP_CROSSJUMP)
    2952              :                   /* This can lengthen register lifetimes.  Do it only after
    2953              :                      reload.  */
    2954     29632901 :                   && reload_completed
    2955    436585996 :                   && try_head_merge_bb (b))
    2956              :                 changed_here = true;
    2957              : 
    2958              :               /* Don't get confused by the index shift caused by
    2959              :                  deleting blocks.  */
    2960    406913651 :               if (!changed_here)
    2961    391900088 :                 b = b->next_bb;
    2962              :               else
    2963              :                 changed = true;
    2964              :             }
    2965              : 
    2966     26191294 :           if ((mode & CLEANUP_CROSSJUMP)
    2967     26191294 :               && try_crossjump_bb (mode, EXIT_BLOCK_PTR_FOR_FN (cfun)))
    2968              :             changed = true;
    2969              : 
    2970     26191294 :           if (block_was_dirty)
    2971              :             {
    2972              :               /* This should only be set by head-merging.  */
    2973       200132 :               gcc_assert (mode & CLEANUP_CROSSJUMP);
    2974       200132 :               df_analyze ();
    2975              :             }
    2976              : 
    2977     26191294 :           if (changed)
    2978              :             {
    2979              :               /* Edge forwarding in particular can cause hot blocks previously
    2980              :                  reached by both hot and cold blocks to become dominated only
    2981              :                  by cold blocks. This will cause the verification below to fail,
    2982              :                  and lead to now cold code in the hot section. This is not easy
    2983              :                  to detect and fix during edge forwarding, and in some cases
    2984              :                  is only visible after newly unreachable blocks are deleted,
    2985              :                  which will be done in fixup_partitions.  */
    2986      3899661 :               if ((mode & CLEANUP_NO_PARTITIONING) == 0)
    2987              :                 {
    2988      3761800 :                   fixup_partitions ();
    2989      3761800 :                   checking_verify_flow_info ();
    2990              :                 }
    2991              :             }
    2992              : 
    2993     26191294 :           changed_overall |= changed;
    2994     26191294 :           first_pass = false;
    2995              :         }
    2996              :       while (changed);
    2997              :     }
    2998              : 
    2999    359092946 :   FOR_ALL_BB_FN (b, cfun)
    3000    336801313 :     b->flags &= ~(BB_FORWARDER_BLOCK | BB_NONTHREADABLE_BLOCK);
    3001              : 
    3002     22291633 :   return changed_overall;
    3003              : }
    3004              : 
    3005              : /* Delete all unreachable basic blocks.  */
    3006              : 
    3007              : bool
    3008     28756208 : delete_unreachable_blocks (void)
    3009              : {
    3010     28756208 :   bool changed = false;
    3011     28756208 :   basic_block b, prev_bb;
    3012              : 
    3013     28756208 :   find_unreachable_blocks ();
    3014              : 
    3015              :   /* When we're in GIMPLE mode and there may be debug bind insns, we
    3016              :      should delete blocks in reverse dominator order, so as to get a
    3017              :      chance to substitute all released DEFs into debug bind stmts.  If
    3018              :      we don't have dominators information, walking blocks backward
    3019              :      gets us a better chance of retaining most debug information than
    3020              :      otherwise.  */
    3021     12848229 :   if (MAY_HAVE_DEBUG_BIND_INSNS && current_ir_type () == IR_GIMPLE
    3022     29028978 :       && dom_info_available_p (CDI_DOMINATORS))
    3023              :     {
    3024            0 :       for (b = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
    3025            0 :            b != ENTRY_BLOCK_PTR_FOR_FN (cfun); b = prev_bb)
    3026              :         {
    3027            0 :           prev_bb = b->prev_bb;
    3028              : 
    3029            0 :           if (!(b->flags & BB_REACHABLE))
    3030              :             {
    3031              :               /* Speed up the removal of blocks that don't dominate
    3032              :                  others.  Walking backwards, this should be the common
    3033              :                  case.  */
    3034            0 :               if (!first_dom_son (CDI_DOMINATORS, b))
    3035            0 :                 delete_basic_block (b);
    3036              :               else
    3037              :                 {
    3038            0 :                   auto_vec<basic_block> h
    3039            0 :                     = get_all_dominated_blocks (CDI_DOMINATORS, b);
    3040              : 
    3041            0 :                   while (h.length ())
    3042              :                     {
    3043            0 :                       b = h.pop ();
    3044              : 
    3045            0 :                       prev_bb = b->prev_bb;
    3046              : 
    3047            0 :                       gcc_assert (!(b->flags & BB_REACHABLE));
    3048              : 
    3049            0 :                       delete_basic_block (b);
    3050              :                     }
    3051            0 :                 }
    3052              : 
    3053              :               changed = true;
    3054              :             }
    3055              :         }
    3056              :     }
    3057              :   else
    3058              :     {
    3059     28756208 :       for (b = EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb;
    3060    424995317 :            b != ENTRY_BLOCK_PTR_FOR_FN (cfun); b = prev_bb)
    3061              :         {
    3062    396239109 :           prev_bb = b->prev_bb;
    3063              : 
    3064    396239109 :           if (!(b->flags & BB_REACHABLE))
    3065              :             {
    3066      1718055 :               delete_basic_block (b);
    3067      1718055 :               changed = true;
    3068              :             }
    3069              :         }
    3070              :     }
    3071              : 
    3072     28756208 :   if (changed)
    3073       462408 :     tidy_fallthru_edges ();
    3074     28756208 :   return changed;
    3075              : }
    3076              : 
    3077              : /* Delete any jump tables never referenced.  We can't delete them at the
    3078              :    time of removing tablejump insn as they are referenced by the preceding
    3079              :    insns computing the destination, so we delay deleting and garbagecollect
    3080              :    them once life information is computed.  */
    3081              : void
    3082      9345400 : delete_dead_jumptables (void)
    3083              : {
    3084      9345400 :   basic_block bb;
    3085              : 
    3086              :   /* A dead jump table does not belong to any basic block.  Scan insns
    3087              :      between two adjacent basic blocks.  */
    3088    103921237 :   FOR_EACH_BB_FN (bb, cfun)
    3089              :     {
    3090     94575837 :       rtx_insn *insn, *next;
    3091              : 
    3092     94575837 :       for (insn = NEXT_INSN (BB_END (bb));
    3093    258270581 :            insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
    3094     78464307 :            insn = next)
    3095              :         {
    3096     78464307 :           next = NEXT_INSN (insn);
    3097     78464307 :           if (LABEL_P (insn)
    3098     44452583 :               && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
    3099     80476161 :               && JUMP_TABLE_DATA_P (next))
    3100              :             {
    3101            0 :               rtx_insn *label = insn, *jump = next;
    3102              : 
    3103            0 :               if (dump_file)
    3104            0 :                 fprintf (dump_file, "Dead jumptable %i removed\n",
    3105            0 :                          INSN_UID (insn));
    3106              : 
    3107            0 :               next = NEXT_INSN (next);
    3108            0 :               delete_insn (jump);
    3109            0 :               delete_insn (label);
    3110              :             }
    3111              :         }
    3112              :     }
    3113      9345400 : }
    3114              : 
    3115              : 
    3116              : /* Tidy the CFG by deleting unreachable code and whatnot.  */
    3117              : 
    3118              : bool
    3119     20085773 : cleanup_cfg (int mode)
    3120              : {
    3121     20085773 :   bool changed = false;
    3122              : 
    3123              :   /* Set the cfglayout mode flag here.  We could update all the callers
    3124              :      but that is just inconvenient, especially given that we eventually
    3125              :      want to have cfglayout mode as the default.  */
    3126     20085773 :   if (current_ir_type () == IR_RTL_CFGLAYOUT)
    3127     13322773 :     mode |= CLEANUP_CFGLAYOUT;
    3128              : 
    3129     20085773 :   timevar_push (TV_CLEANUP_CFG);
    3130     20085773 :   if (delete_unreachable_blocks ())
    3131              :     {
    3132       155912 :       changed = true;
    3133              :       /* We've possibly created trivially dead code.  Cleanup it right
    3134              :          now to introduce more opportunities for try_optimize_cfg.  */
    3135       155912 :       if (!(mode & (CLEANUP_NO_INSN_DEL))
    3136        41999 :           && !reload_completed)
    3137        41853 :         delete_trivially_dead_insns (get_insns (), max_reg_num ());
    3138              :     }
    3139              : 
    3140     20085773 :   compact_blocks ();
    3141              : 
    3142              :   /* To tail-merge blocks ending in the same noreturn function (e.g.
    3143              :      a call to abort) we have to insert fake edges to exit.  Do this
    3144              :      here once.  The fake edges do not interfere with any other CFG
    3145              :      cleanups.  */
    3146     20085773 :   if (mode & CLEANUP_CROSSJUMP)
    3147       982744 :     add_noreturn_fake_exit_edges ();
    3148              : 
    3149     20085773 :   if (!dbg_cnt (cfg_cleanup))
    3150              :     return changed;
    3151              : 
    3152     22291633 :   while (try_optimize_cfg (mode))
    3153              :     {
    3154      3807088 :       delete_unreachable_blocks (), changed = true;
    3155      3807088 :       if (!(mode & CLEANUP_NO_INSN_DEL))
    3156              :         {
    3157              :           /* Try to remove some trivially dead insns when doing an expensive
    3158              :              cleanup.  But delete_trivially_dead_insns doesn't work after
    3159              :              reload (it only handles pseudos) and run_fast_dce is too costly
    3160              :              to run in every iteration.
    3161              : 
    3162              :              For effective cross jumping, we really want to run a fast DCE to
    3163              :              clean up any dead conditions, or they get in the way of performing
    3164              :              useful tail merges.
    3165              : 
    3166              :              Other transformations in cleanup_cfg are not so sensitive to dead
    3167              :              code, so delete_trivially_dead_insns or even doing nothing at all
    3168              :              is good enough.  */
    3169       618484 :           if ((mode & CLEANUP_EXPENSIVE) && !reload_completed
    3170      2217192 :               && !delete_trivially_dead_insns (get_insns (), max_reg_num ()))
    3171              :             break;
    3172      2205860 :           if ((mode & CLEANUP_CROSSJUMP) && crossjumps_occurred)
    3173              :             {
    3174        83006 :               run_fast_dce ();
    3175        83006 :               mode &= ~CLEANUP_FORCE_FAST_DCE;
    3176              :             }
    3177              :         }
    3178              :       else
    3179              :         break;
    3180              :     }
    3181              : 
    3182     20085773 :   if (mode & CLEANUP_CROSSJUMP)
    3183       982744 :     remove_fake_exit_edges ();
    3184              : 
    3185     20085773 :   if (mode & CLEANUP_FORCE_FAST_DCE)
    3186       121586 :     run_fast_dce ();
    3187              : 
    3188              :   /* Don't call delete_dead_jumptables in cfglayout mode, because
    3189              :      that function assumes that jump tables are in the insns stream.
    3190              :      But we also don't _have_ to delete dead jumptables in cfglayout
    3191              :      mode because we shouldn't even be looking at things that are
    3192              :      not in a basic block.  Dead jumptables are cleaned up when
    3193              :      going out of cfglayout mode.  */
    3194     20085773 :   if (!(mode & CLEANUP_CFGLAYOUT))
    3195      6763000 :     delete_dead_jumptables ();
    3196              : 
    3197              :   /* ???  We probably do this way too often.  */
    3198     20085773 :   if (current_loops
    3199      9361737 :       && (changed
    3200      6934484 :           || (mode & CLEANUP_CFG_CHANGED)))
    3201              :     {
    3202      2522913 :       timevar_push (TV_REPAIR_LOOPS);
    3203              :       /* The above doesn't preserve dominance info if available.  */
    3204      2522913 :       gcc_assert (!dom_info_available_p (CDI_DOMINATORS));
    3205      2522913 :       calculate_dominance_info (CDI_DOMINATORS);
    3206      2522913 :       fix_loop_structure (NULL);
    3207      2522913 :       free_dominance_info (CDI_DOMINATORS);
    3208      2522913 :       timevar_pop (TV_REPAIR_LOOPS);
    3209              :     }
    3210              : 
    3211     20085773 :   timevar_pop (TV_CLEANUP_CFG);
    3212              : 
    3213     20085773 :   return changed;
    3214              : }
    3215              : 
    3216              : namespace {
    3217              : 
    3218              : const pass_data pass_data_jump =
    3219              : {
    3220              :   RTL_PASS, /* type */
    3221              :   "jump", /* name */
    3222              :   OPTGROUP_NONE, /* optinfo_flags */
    3223              :   TV_JUMP, /* tv_id */
    3224              :   0, /* properties_required */
    3225              :   0, /* properties_provided */
    3226              :   0, /* properties_destroyed */
    3227              :   0, /* todo_flags_start */
    3228              :   0, /* todo_flags_finish */
    3229              : };
    3230              : 
    3231              : class pass_jump : public rtl_opt_pass
    3232              : {
    3233              : public:
    3234       297180 :   pass_jump (gcc::context *ctxt)
    3235       594360 :     : rtl_opt_pass (pass_data_jump, ctxt)
    3236              :   {}
    3237              : 
    3238              :   /* opt_pass methods: */
    3239              :   unsigned int execute (function *) final override;
    3240              : 
    3241              : }; // class pass_jump
    3242              : 
    3243              : unsigned int
    3244      1517124 : pass_jump::execute (function *)
    3245              : {
    3246      1517124 :   delete_trivially_dead_insns (get_insns (), max_reg_num ());
    3247      1517124 :   if (dump_file)
    3248           84 :     dump_flow_info (dump_file, dump_flags);
    3249      3034248 :   cleanup_cfg ((optimize ? CLEANUP_EXPENSIVE : 0)
    3250      1064824 :                | (flag_thread_jumps && flag_expensive_optimizations
    3251      1517124 :                   ? CLEANUP_THREADING : 0));
    3252      1517124 :   return 0;
    3253              : }
    3254              : 
    3255              : } // anon namespace
    3256              : 
    3257              : rtl_opt_pass *
    3258       297180 : make_pass_jump (gcc::context *ctxt)
    3259              : {
    3260       297180 :   return new pass_jump (ctxt);
    3261              : }
    3262              : 
    3263              : namespace {
    3264              : 
    3265              : const pass_data pass_data_jump_after_combine =
    3266              : {
    3267              :   RTL_PASS, /* type */
    3268              :   "jump_after_combine", /* name */
    3269              :   OPTGROUP_NONE, /* optinfo_flags */
    3270              :   TV_JUMP, /* tv_id */
    3271              :   0, /* properties_required */
    3272              :   0, /* properties_provided */
    3273              :   0, /* properties_destroyed */
    3274              :   0, /* todo_flags_start */
    3275              :   0, /* todo_flags_finish */
    3276              : };
    3277              : 
    3278              : class pass_jump_after_combine : public rtl_opt_pass
    3279              : {
    3280              : public:
    3281       297180 :   pass_jump_after_combine (gcc::context *ctxt)
    3282       594360 :     : rtl_opt_pass (pass_data_jump_after_combine, ctxt)
    3283              :   {}
    3284              : 
    3285              :   /* opt_pass methods: */
    3286      1517135 :   bool gate (function *) final override
    3287              :   {
    3288      1517135 :     return flag_thread_jumps && flag_expensive_optimizations;
    3289              :   }
    3290              :   unsigned int execute (function *) final override;
    3291              : 
    3292              : }; // class pass_jump_after_combine
    3293              : 
    3294              : unsigned int
    3295       982583 : pass_jump_after_combine::execute (function *)
    3296              : {
    3297              :   /* Jump threading does not keep dominators up-to-date.  */
    3298       982583 :   free_dominance_info (CDI_DOMINATORS);
    3299       982583 :   cleanup_cfg (CLEANUP_THREADING);
    3300       982583 :   return 0;
    3301              : }
    3302              : 
    3303              : } // anon namespace
    3304              : 
    3305              : rtl_opt_pass *
    3306       297180 : make_pass_jump_after_combine (gcc::context *ctxt)
    3307              : {
    3308       297180 :   return new pass_jump_after_combine (ctxt);
    3309              : }
    3310              : 
    3311              : namespace {
    3312              : 
    3313              : const pass_data pass_data_jump2 =
    3314              : {
    3315              :   RTL_PASS, /* type */
    3316              :   "jump2", /* name */
    3317              :   OPTGROUP_NONE, /* optinfo_flags */
    3318              :   TV_JUMP, /* tv_id */
    3319              :   0, /* properties_required */
    3320              :   0, /* properties_provided */
    3321              :   0, /* properties_destroyed */
    3322              :   0, /* todo_flags_start */
    3323              :   0, /* todo_flags_finish */
    3324              : };
    3325              : 
    3326              : class pass_jump2 : public rtl_opt_pass
    3327              : {
    3328              : public:
    3329       297180 :   pass_jump2 (gcc::context *ctxt)
    3330       594360 :     : rtl_opt_pass (pass_data_jump2, ctxt)
    3331              :   {}
    3332              : 
    3333              :   /* opt_pass methods: */
    3334      1517128 :   unsigned int execute (function *) final override
    3335              :     {
    3336      2051512 :       cleanup_cfg (flag_crossjumping ? CLEANUP_CROSSJUMP : 0);
    3337      1517128 :       return 0;
    3338              :     }
    3339              : 
    3340              : }; // class pass_jump2
    3341              : 
    3342              : } // anon namespace
    3343              : 
    3344              : rtl_opt_pass *
    3345       297180 : make_pass_jump2 (gcc::context *ctxt)
    3346              : {
    3347       297180 :   return new pass_jump2 (ctxt);
    3348              : }
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.