LCOV - code coverage report
Current view: top level - gcc - tree-ssa-threadupdate.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 962 997 96.5 %
Date: 2020-03-28 11:57:23 Functions: 37 38 97.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Thread edges through blocks and update the control flow and SSA graphs.
       2                 :            :    Copyright (C) 2004-2020 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
       7                 :            : it under the terms of the GNU General Public License as published by
       8                 :            : the Free Software Foundation; either version 3, or (at your option)
       9                 :            : any later version.
      10                 :            : 
      11                 :            : GCC is distributed in the hope that it will be useful,
      12                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      13                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      14                 :            : GNU General Public License 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                 :            : #include "config.h"
      21                 :            : #include "system.h"
      22                 :            : #include "coretypes.h"
      23                 :            : #include "backend.h"
      24                 :            : #include "tree.h"
      25                 :            : #include "gimple.h"
      26                 :            : #include "cfghooks.h"
      27                 :            : #include "tree-pass.h"
      28                 :            : #include "ssa.h"
      29                 :            : #include "fold-const.h"
      30                 :            : #include "cfganal.h"
      31                 :            : #include "gimple-iterator.h"
      32                 :            : #include "tree-ssa.h"
      33                 :            : #include "tree-ssa-threadupdate.h"
      34                 :            : #include "cfgloop.h"
      35                 :            : #include "dbgcnt.h"
      36                 :            : #include "tree-cfg.h"
      37                 :            : #include "tree-vectorizer.h"
      38                 :            : 
      39                 :            : /* Given a block B, update the CFG and SSA graph to reflect redirecting
      40                 :            :    one or more in-edges to B to instead reach the destination of an
      41                 :            :    out-edge from B while preserving any side effects in B.
      42                 :            : 
      43                 :            :    i.e., given A->B and B->C, change A->B to be A->C yet still preserve the
      44                 :            :    side effects of executing B.
      45                 :            : 
      46                 :            :      1. Make a copy of B (including its outgoing edges and statements).  Call
      47                 :            :         the copy B'.  Note B' has no incoming edges or PHIs at this time.
      48                 :            : 
      49                 :            :      2. Remove the control statement at the end of B' and all outgoing edges
      50                 :            :         except B'->C.
      51                 :            : 
      52                 :            :      3. Add a new argument to each PHI in C with the same value as the existing
      53                 :            :         argument associated with edge B->C.  Associate the new PHI arguments
      54                 :            :         with the edge B'->C.
      55                 :            : 
      56                 :            :      4. For each PHI in B, find or create a PHI in B' with an identical
      57                 :            :         PHI_RESULT.  Add an argument to the PHI in B' which has the same
      58                 :            :         value as the PHI in B associated with the edge A->B.  Associate
      59                 :            :         the new argument in the PHI in B' with the edge A->B.
      60                 :            : 
      61                 :            :      5. Change the edge A->B to A->B'.
      62                 :            : 
      63                 :            :         5a. This automatically deletes any PHI arguments associated with the
      64                 :            :             edge A->B in B.
      65                 :            : 
      66                 :            :         5b. This automatically associates each new argument added in step 4
      67                 :            :             with the edge A->B'.
      68                 :            : 
      69                 :            :      6. Repeat for other incoming edges into B.
      70                 :            : 
      71                 :            :      7. Put the duplicated resources in B and all the B' blocks into SSA form.
      72                 :            : 
      73                 :            :    Note that block duplication can be minimized by first collecting the
      74                 :            :    set of unique destination blocks that the incoming edges should
      75                 :            :    be threaded to.
      76                 :            : 
      77                 :            :    We reduce the number of edges and statements we create by not copying all
      78                 :            :    the outgoing edges and the control statement in step #1.  We instead create
      79                 :            :    a template block without the outgoing edges and duplicate the template.
      80                 :            : 
      81                 :            :    Another case this code handles is threading through a "joiner" block.  In
      82                 :            :    this case, we do not know the destination of the joiner block, but one
      83                 :            :    of the outgoing edges from the joiner block leads to a threadable path.  This
      84                 :            :    case largely works as outlined above, except the duplicate of the joiner
      85                 :            :    block still contains a full set of outgoing edges and its control statement.
      86                 :            :    We just redirect one of its outgoing edges to our jump threading path.  */
      87                 :            : 
      88                 :            : 
      89                 :            : /* Steps #5 and #6 of the above algorithm are best implemented by walking
      90                 :            :    all the incoming edges which thread to the same destination edge at
      91                 :            :    the same time.  That avoids lots of table lookups to get information
      92                 :            :    for the destination edge.
      93                 :            : 
      94                 :            :    To realize that implementation we create a list of incoming edges
      95                 :            :    which thread to the same outgoing edge.  Thus to implement steps
      96                 :            :    #5 and #6 we traverse our hash table of outgoing edge information.
      97                 :            :    For each entry we walk the list of incoming edges which thread to
      98                 :            :    the current outgoing edge.  */
      99                 :            : 
     100                 :            : struct el
     101                 :            : {
     102                 :            :   edge e;
     103                 :            :   struct el *next;
     104                 :            : };
     105                 :            : 
     106                 :            : /* Main data structure recording information regarding B's duplicate
     107                 :            :    blocks.  */
     108                 :            : 
     109                 :            : /* We need to efficiently record the unique thread destinations of this
     110                 :            :    block and specific information associated with those destinations.  We
     111                 :            :    may have many incoming edges threaded to the same outgoing edge.  This
     112                 :            :    can be naturally implemented with a hash table.  */
     113                 :            : 
     114                 :            : struct redirection_data : free_ptr_hash<redirection_data>
     115                 :            : {
     116                 :            :   /* We support wiring up two block duplicates in a jump threading path.
     117                 :            : 
     118                 :            :      One is a normal block copy where we remove the control statement
     119                 :            :      and wire up its single remaining outgoing edge to the thread path.
     120                 :            : 
     121                 :            :      The other is a joiner block where we leave the control statement
     122                 :            :      in place, but wire one of the outgoing edges to a thread path.
     123                 :            : 
     124                 :            :      In theory we could have multiple block duplicates in a jump
     125                 :            :      threading path, but I haven't tried that.
     126                 :            : 
     127                 :            :      The duplicate blocks appear in this array in the same order in
     128                 :            :      which they appear in the jump thread path.  */
     129                 :            :   basic_block dup_blocks[2];
     130                 :            : 
     131                 :            :   /* The jump threading path.  */
     132                 :            :   vec<jump_thread_edge *> *path;
     133                 :            : 
     134                 :            :   /* A list of incoming edges which we want to thread to the
     135                 :            :      same path.  */
     136                 :            :   struct el *incoming_edges;
     137                 :            : 
     138                 :            :   /* hash_table support.  */
     139                 :            :   static inline hashval_t hash (const redirection_data *);
     140                 :            :   static inline int equal (const redirection_data *, const redirection_data *);
     141                 :            : };
     142                 :            : 
     143                 :            : /* Dump a jump threading path, including annotations about each
     144                 :            :    edge in the path.  */
     145                 :            : 
     146                 :            : static void
     147                 :        189 : dump_jump_thread_path (FILE *dump_file, vec<jump_thread_edge *> path,
     148                 :            :                        bool registering)
     149                 :            : {
     150                 :        189 :   fprintf (dump_file,
     151                 :            :            "  %s%s jump thread: (%d, %d) incoming edge; ",
     152                 :            :            (registering ? "Registering" : "Cancelling"),
     153                 :        189 :            (path[0]->type == EDGE_FSM_THREAD ? " FSM": ""),
     154                 :        189 :            path[0]->e->src->index, path[0]->e->dest->index);
     155                 :            : 
     156                 :        591 :   for (unsigned int i = 1; i < path.length (); i++)
     157                 :            :     {
     158                 :            :       /* We can get paths with a NULL edge when the final destination
     159                 :            :          of a jump thread turns out to be a constant address.  We dump
     160                 :            :          those paths when debugging, so we have to be prepared for that
     161                 :            :          possibility here.  */
     162                 :        402 :       if (path[i]->e == NULL)
     163                 :          0 :         continue;
     164                 :            : 
     165                 :        402 :       if (path[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
     166                 :         47 :         fprintf (dump_file, " (%d, %d) joiner; ",
     167                 :         47 :                  path[i]->e->src->index, path[i]->e->dest->index);
     168                 :        402 :       if (path[i]->type == EDGE_COPY_SRC_BLOCK)
     169                 :         97 :        fprintf (dump_file, " (%d, %d) normal;",
     170                 :         97 :                  path[i]->e->src->index, path[i]->e->dest->index);
     171                 :        402 :       if (path[i]->type == EDGE_NO_COPY_SRC_BLOCK)
     172                 :         99 :        fprintf (dump_file, " (%d, %d) nocopy;",
     173                 :         99 :                  path[i]->e->src->index, path[i]->e->dest->index);
     174                 :        402 :       if (path[0]->type == EDGE_FSM_THREAD)
     175                 :        462 :         fprintf (dump_file, " (%d, %d) ",
     176                 :        231 :                  path[i]->e->src->index, path[i]->e->dest->index);
     177                 :            :     }
     178                 :        189 :   fputc ('\n', dump_file);
     179                 :        189 : }
     180                 :            : 
     181                 :            : /* Simple hashing function.  For any given incoming edge E, we're going
     182                 :            :    to be most concerned with the final destination of its jump thread
     183                 :            :    path.  So hash on the block index of the final edge in the path.  */
     184                 :            : 
     185                 :            : inline hashval_t
     186                 :            : redirection_data::hash (const redirection_data *p)
     187                 :            : {
     188                 :            :   vec<jump_thread_edge *> *path = p->path;
     189                 :            :   return path->last ()->e->dest->index;
     190                 :            : }
     191                 :            : 
     192                 :            : /* Given two hash table entries, return true if they have the same
     193                 :            :    jump threading path.  */
     194                 :            : inline int
     195                 :     162660 : redirection_data::equal (const redirection_data *p1, const redirection_data *p2)
     196                 :            : {
     197                 :     162660 :   vec<jump_thread_edge *> *path1 = p1->path;
     198                 :     162660 :   vec<jump_thread_edge *> *path2 = p2->path;
     199                 :            : 
     200                 :     487980 :   if (path1->length () != path2->length ())
     201                 :            :     return false;
     202                 :            : 
     203                 :     246169 :   for (unsigned int i = 1; i < path1->length (); i++)
     204                 :            :     {
     205                 :     178431 :       if ((*path1)[i]->type != (*path2)[i]->type
     206                 :     178431 :           || (*path1)[i]->e != (*path2)[i]->e)
     207                 :            :         return false;
     208                 :            :     }
     209                 :            : 
     210                 :            :   return true;
     211                 :            : }
     212                 :            : 
     213                 :            : /* Rather than search all the edges in jump thread paths each time
     214                 :            :    DOM is able to simply if control statement, we build a hash table
     215                 :            :    with the deleted edges.  We only care about the address of the edge,
     216                 :            :    not its contents.  */
     217                 :            : struct removed_edges : nofree_ptr_hash<edge_def>
     218                 :            : {
     219                 :    1270300 :   static hashval_t hash (edge e) { return htab_hash_pointer (e); }
     220                 :    1028600 :   static bool equal (edge e1, edge e2) { return e1 == e2; }
     221                 :            : };
     222                 :            : 
     223                 :            : static hash_table<removed_edges> *removed_edges;
     224                 :            : 
     225                 :            : /* Data structure of information to pass to hash table traversal routines.  */
     226                 :            : struct ssa_local_info_t
     227                 :            : {
     228                 :            :   /* The current block we are working on.  */
     229                 :            :   basic_block bb;
     230                 :            : 
     231                 :            :   /* We only create a template block for the first duplicated block in a
     232                 :            :      jump threading path as we may need many duplicates of that block.
     233                 :            : 
     234                 :            :      The second duplicate block in a path is specific to that path.  Creating
     235                 :            :      and sharing a template for that block is considerably more difficult.  */
     236                 :            :   basic_block template_block;
     237                 :            : 
     238                 :            :   /* If we append debug stmts to the template block after creating it,
     239                 :            :      this iterator won't be the last one in the block, and further
     240                 :            :      copies of the template block shouldn't get debug stmts after
     241                 :            :      it.  */
     242                 :            :   gimple_stmt_iterator template_last_to_copy;
     243                 :            : 
     244                 :            :   /* Blocks duplicated for the thread.  */
     245                 :            :   bitmap duplicate_blocks;
     246                 :            : 
     247                 :            :   /* TRUE if we thread one or more jumps, FALSE otherwise.  */
     248                 :            :   bool jumps_threaded;
     249                 :            : 
     250                 :            :   /* When we have multiple paths through a joiner which reach different
     251                 :            :      final destinations, then we may need to correct for potential
     252                 :            :      profile insanities.  */
     253                 :            :   bool need_profile_correction;
     254                 :            : };
     255                 :            : 
     256                 :            : /* Passes which use the jump threading code register jump threading
     257                 :            :    opportunities as they are discovered.  We keep the registered
     258                 :            :    jump threading opportunities in this vector as edge pairs
     259                 :            :    (original_edge, target_edge).  */
     260                 :            : static vec<vec<jump_thread_edge *> *> paths;
     261                 :            : 
     262                 :            : /* When we start updating the CFG for threading, data necessary for jump
     263                 :            :    threading is attached to the AUX field for the incoming edge.  Use these
     264                 :            :    macros to access the underlying structure attached to the AUX field.  */
     265                 :            : #define THREAD_PATH(E) ((vec<jump_thread_edge *> *)(E)->aux)
     266                 :            : 
     267                 :            : /* Jump threading statistics.  */
     268                 :            : 
     269                 :            : struct thread_stats_d
     270                 :            : {
     271                 :            :   unsigned long num_threaded_edges;
     272                 :            : };
     273                 :            : 
     274                 :            : struct thread_stats_d thread_stats;
     275                 :            : 
     276                 :            : 
     277                 :            : /* Remove the last statement in block BB if it is a control statement
     278                 :            :    Also remove all outgoing edges except the edge which reaches DEST_BB.
     279                 :            :    If DEST_BB is NULL, then remove all outgoing edges.  */
     280                 :            : 
     281                 :            : void
     282                 :     708752 : remove_ctrl_stmt_and_useless_edges (basic_block bb, basic_block dest_bb)
     283                 :            : {
     284                 :     708752 :   gimple_stmt_iterator gsi;
     285                 :     708752 :   edge e;
     286                 :     708752 :   edge_iterator ei;
     287                 :            : 
     288                 :     708752 :   gsi = gsi_last_bb (bb);
     289                 :            : 
     290                 :            :   /* If the duplicate ends with a control statement, then remove it.
     291                 :            : 
     292                 :            :      Note that if we are duplicating the template block rather than the
     293                 :            :      original basic block, then the duplicate might not have any real
     294                 :            :      statements in it.  */
     295                 :     708752 :   if (!gsi_end_p (gsi)
     296                 :     708752 :       && gsi_stmt (gsi)
     297                 :     708752 :       && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
     298                 :       1693 :           || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
     299                 :       1672 :           || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH))
     300                 :     708752 :     gsi_remove (&gsi, true);
     301                 :            : 
     302                 :    2132560 :   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
     303                 :            :     {
     304                 :    1423810 :       if (e->dest != dest_bb)
     305                 :            :         {
     306                 :    1130300 :           free_dom_edge_info (e);
     307                 :    1130300 :           remove_edge (e);
     308                 :            :         }
     309                 :            :       else
     310                 :            :         {
     311                 :     293510 :           e->probability = profile_probability::always ();
     312                 :     293510 :           ei_next (&ei);
     313                 :            :         }
     314                 :            :     }
     315                 :            : 
     316                 :            :   /* If the remaining edge is a loop exit, there must have
     317                 :            :      a removed edge that was not a loop exit.
     318                 :            : 
     319                 :            :      In that case BB and possibly other blocks were previously
     320                 :            :      in the loop, but are now outside the loop.  Thus, we need
     321                 :            :      to update the loop structures.  */
     322                 :     708752 :   if (single_succ_p (bb)
     323                 :     367266 :       && loop_outer (bb->loop_father)
     324                 :     782508 :       && loop_exit_edge_p (bb->loop_father, single_succ_edge (bb)))
     325                 :      19841 :     loops_state_set (LOOPS_NEED_FIXUP);
     326                 :     708752 : }
     327                 :            : 
     328                 :            : /* Create a duplicate of BB.  Record the duplicate block in an array
     329                 :            :    indexed by COUNT stored in RD.  */
     330                 :            : 
     331                 :            : static void
     332                 :     523489 : create_block_for_threading (basic_block bb,
     333                 :            :                             struct redirection_data *rd,
     334                 :            :                             unsigned int count,
     335                 :            :                             bitmap *duplicate_blocks)
     336                 :            : {
     337                 :     523489 :   edge_iterator ei;
     338                 :     523489 :   edge e;
     339                 :            : 
     340                 :            :   /* We can use the generic block duplication code and simply remove
     341                 :            :      the stuff we do not need.  */
     342                 :     523489 :   rd->dup_blocks[count] = duplicate_block (bb, NULL, NULL);
     343                 :            : 
     344                 :    1571050 :   FOR_EACH_EDGE (e, ei, rd->dup_blocks[count]->succs)
     345                 :            :     {
     346                 :    1047560 :       e->aux = NULL;
     347                 :            : 
     348                 :            :       /* If we duplicate a block with an outgoing edge marked as
     349                 :            :          EDGE_IGNORE, we must clear EDGE_IGNORE so that it doesn't
     350                 :            :          leak out of the current pass.
     351                 :            : 
     352                 :            :          It would be better to simplify switch statements and remove
     353                 :            :          the edges before we get here, but the sequencing is nontrivial.  */
     354                 :    1047560 :       e->flags &= ~EDGE_IGNORE;
     355                 :            :     }
     356                 :            : 
     357                 :            :   /* Zero out the profile, since the block is unreachable for now.  */
     358                 :     523489 :   rd->dup_blocks[count]->count = profile_count::uninitialized ();
     359                 :     523489 :   if (duplicate_blocks)
     360                 :     523489 :     bitmap_set_bit (*duplicate_blocks, rd->dup_blocks[count]->index);
     361                 :     523489 : }
     362                 :            : 
     363                 :            : /* Main data structure to hold information for duplicates of BB.  */
     364                 :            : 
     365                 :            : static hash_table<redirection_data> *redirection_data;
     366                 :            : 
     367                 :            : /* Given an outgoing edge E lookup and return its entry in our hash table.
     368                 :            : 
     369                 :            :    If INSERT is true, then we insert the entry into the hash table if
     370                 :            :    it is not already present.  INCOMING_EDGE is added to the list of incoming
     371                 :            :    edges associated with E in the hash table.  */
     372                 :            : 
     373                 :            : static struct redirection_data *
     374                 :     554323 : lookup_redirection_data (edge e, enum insert_option insert)
     375                 :            : {
     376                 :     554323 :   struct redirection_data **slot;
     377                 :     554323 :   struct redirection_data *elt;
     378                 :     554323 :   vec<jump_thread_edge *> *path = THREAD_PATH (e);
     379                 :            : 
     380                 :            :   /* Build a hash table element so we can see if E is already
     381                 :            :      in the table.  */
     382                 :     554323 :   elt = XNEW (struct redirection_data);
     383                 :     554323 :   elt->path = path;
     384                 :     554323 :   elt->dup_blocks[0] = NULL;
     385                 :     554323 :   elt->dup_blocks[1] = NULL;
     386                 :     554323 :   elt->incoming_edges = NULL;
     387                 :            : 
     388                 :     554323 :   slot = redirection_data->find_slot (elt, insert);
     389                 :            : 
     390                 :            :   /* This will only happen if INSERT is false and the entry is not
     391                 :            :      in the hash table.  */
     392                 :     554323 :   if (slot == NULL)
     393                 :            :     {
     394                 :          0 :       free (elt);
     395                 :          0 :       return NULL;
     396                 :            :     }
     397                 :            : 
     398                 :            :   /* This will only happen if E was not in the hash table and
     399                 :            :      INSERT is true.  */
     400                 :     554323 :   if (*slot == NULL)
     401                 :            :     {
     402                 :     486585 :       *slot = elt;
     403                 :     486585 :       elt->incoming_edges = XNEW (struct el);
     404                 :     486585 :       elt->incoming_edges->e = e;
     405                 :     486585 :       elt->incoming_edges->next = NULL;
     406                 :     486585 :       return elt;
     407                 :            :     }
     408                 :            :   /* E was in the hash table.  */
     409                 :            :   else
     410                 :            :     {
     411                 :            :       /* Free ELT as we do not need it anymore, we will extract the
     412                 :            :          relevant entry from the hash table itself.  */
     413                 :      67738 :       free (elt);
     414                 :            : 
     415                 :            :       /* Get the entry stored in the hash table.  */
     416                 :      67738 :       elt = *slot;
     417                 :            : 
     418                 :            :       /* If insertion was requested, then we need to add INCOMING_EDGE
     419                 :            :          to the list of incoming edges associated with E.  */
     420                 :      67738 :       if (insert)
     421                 :            :         {
     422                 :      67738 :           struct el *el = XNEW (struct el);
     423                 :      67738 :           el->next = elt->incoming_edges;
     424                 :      67738 :           el->e = e;
     425                 :      67738 :           elt->incoming_edges = el;
     426                 :            :         }
     427                 :            : 
     428                 :      67738 :       return elt;
     429                 :            :     }
     430                 :            : }
     431                 :            : 
     432                 :            : /* Similar to copy_phi_args, except that the PHI arg exists, it just
     433                 :            :    does not have a value associated with it.  */
     434                 :            : 
     435                 :            : static void
     436                 :      36904 : copy_phi_arg_into_existing_phi (edge src_e, edge tgt_e)
     437                 :            : {
     438                 :      36904 :   int src_idx = src_e->dest_idx;
     439                 :      36904 :   int tgt_idx = tgt_e->dest_idx;
     440                 :            : 
     441                 :            :   /* Iterate over each PHI in e->dest.  */
     442                 :      36904 :   for (gphi_iterator gsi = gsi_start_phis (src_e->dest),
     443                 :      36904 :                            gsi2 = gsi_start_phis (tgt_e->dest);
     444                 :      74490 :        !gsi_end_p (gsi);
     445                 :      37586 :        gsi_next (&gsi), gsi_next (&gsi2))
     446                 :            :     {
     447                 :      37586 :       gphi *src_phi = gsi.phi ();
     448                 :      37586 :       gphi *dest_phi = gsi2.phi ();
     449                 :      37586 :       tree val = gimple_phi_arg_def (src_phi, src_idx);
     450                 :      37586 :       location_t locus = gimple_phi_arg_location (src_phi, src_idx);
     451                 :            : 
     452                 :      37586 :       SET_PHI_ARG_DEF (dest_phi, tgt_idx, val);
     453                 :      37586 :       gimple_phi_arg_set_location (dest_phi, tgt_idx, locus);
     454                 :            :     }
     455                 :      36904 : }
     456                 :            : 
     457                 :            : /* Given ssa_name DEF, backtrack jump threading PATH from node IDX
     458                 :            :    to see if it has constant value in a flow sensitive manner.  Set
     459                 :            :    LOCUS to location of the constant phi arg and return the value.
     460                 :            :    Return DEF directly if either PATH or idx is ZERO.  */
     461                 :            : 
     462                 :            : static tree
     463                 :     104739 : get_value_locus_in_path (tree def, vec<jump_thread_edge *> *path,
     464                 :            :                          basic_block bb, int idx, location_t *locus)
     465                 :            : {
     466                 :     104739 :   tree arg;
     467                 :     104739 :   gphi *def_phi;
     468                 :     104739 :   basic_block def_bb;
     469                 :            : 
     470                 :     104739 :   if (path == NULL || idx == 0)
     471                 :            :     return def;
     472                 :            : 
     473                 :      85283 :   def_phi = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (def));
     474                 :      58408 :   if (!def_phi)
     475                 :            :     return def;
     476                 :            : 
     477                 :      58408 :   def_bb = gimple_bb (def_phi);
     478                 :            :   /* Don't propagate loop invariants into deeper loops.  */
     479                 :      58408 :   if (!def_bb || bb_loop_depth (def_bb) < bb_loop_depth (bb))
     480                 :       4098 :     return def;
     481                 :            : 
     482                 :            :   /* Backtrack jump threading path from IDX to see if def has constant
     483                 :            :      value.  */
     484                 :      83161 :   for (int j = idx - 1; j >= 0; j--)
     485                 :            :     {
     486                 :      56570 :       edge e = (*path)[j]->e;
     487                 :      56570 :       if (e->dest == def_bb)
     488                 :            :         {
     489                 :      27719 :           arg = gimple_phi_arg_def (def_phi, e->dest_idx);
     490                 :      27719 :           if (is_gimple_min_invariant (arg))
     491                 :            :             {
     492                 :      10477 :               *locus = gimple_phi_arg_location (def_phi, e->dest_idx);
     493                 :      10477 :               return arg;
     494                 :            :             }
     495                 :            :           break;
     496                 :            :         }
     497                 :            :     }
     498                 :            : 
     499                 :            :   return def;
     500                 :            : }
     501                 :            : 
     502                 :            : /* For each PHI in BB, copy the argument associated with SRC_E to TGT_E.
     503                 :            :    Try to backtrack jump threading PATH from node IDX to see if the arg
     504                 :            :    has constant value, copy constant value instead of argument itself
     505                 :            :    if yes.  */
     506                 :            : 
     507                 :            : static void
     508                 :     643693 : copy_phi_args (basic_block bb, edge src_e, edge tgt_e,
     509                 :            :                vec<jump_thread_edge *> *path, int idx)
     510                 :            : {
     511                 :     643693 :   gphi_iterator gsi;
     512                 :     643693 :   int src_indx = src_e->dest_idx;
     513                 :            : 
     514                 :     914780 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     515                 :            :     {
     516                 :     271087 :       gphi *phi = gsi.phi ();
     517                 :     271087 :       tree def = gimple_phi_arg_def (phi, src_indx);
     518                 :     271087 :       location_t locus = gimple_phi_arg_location (phi, src_indx);
     519                 :            : 
     520                 :     271087 :       if (TREE_CODE (def) == SSA_NAME
     521                 :     492042 :           && !virtual_operand_p (gimple_phi_result (phi)))
     522                 :     104739 :         def = get_value_locus_in_path (def, path, bb, idx, &locus);
     523                 :            : 
     524                 :     271087 :       add_phi_arg (phi, def, tgt_e, locus);
     525                 :            :     }
     526                 :     643693 : }
     527                 :            : 
     528                 :            : /* We have recently made a copy of ORIG_BB, including its outgoing
     529                 :            :    edges.  The copy is NEW_BB.  Every PHI node in every direct successor of
     530                 :            :    ORIG_BB has a new argument associated with edge from NEW_BB to the
     531                 :            :    successor.  Initialize the PHI argument so that it is equal to the PHI
     532                 :            :    argument associated with the edge from ORIG_BB to the successor.
     533                 :            :    PATH and IDX are used to check if the new PHI argument has constant
     534                 :            :    value in a flow sensitive manner.  */
     535                 :            : 
     536                 :            : static void
     537                 :     108247 : update_destination_phis (basic_block orig_bb, basic_block new_bb,
     538                 :            :                          vec<jump_thread_edge *> *path, int idx)
     539                 :            : {
     540                 :     108247 :   edge_iterator ei;
     541                 :     108247 :   edge e;
     542                 :            : 
     543                 :     322960 :   FOR_EACH_EDGE (e, ei, orig_bb->succs)
     544                 :            :     {
     545                 :     214713 :       edge e2 = find_edge (new_bb, e->dest);
     546                 :     214713 :       copy_phi_args (e->dest, e, e2, path, idx);
     547                 :            :     }
     548                 :     108247 : }
     549                 :            : 
     550                 :            : /* Given a duplicate block and its single destination (both stored
     551                 :            :    in RD).  Create an edge between the duplicate and its single
     552                 :            :    destination.
     553                 :            : 
     554                 :            :    Add an additional argument to any PHI nodes at the single
     555                 :            :    destination.  IDX is the start node in jump threading path
     556                 :            :    we start to check to see if the new PHI argument has constant
     557                 :            :    value along the jump threading path.  */
     558                 :            : 
     559                 :            : static void
     560                 :     415242 : create_edge_and_update_destination_phis (struct redirection_data *rd,
     561                 :            :                                          basic_block bb, int idx)
     562                 :            : {
     563                 :     415242 :   edge e = make_single_succ_edge (bb, rd->path->last ()->e->dest, EDGE_FALLTHRU);
     564                 :            : 
     565                 :     415242 :   rescan_loop_exit (e, true, false);
     566                 :            : 
     567                 :            :   /* We used to copy the thread path here.  That was added in 2007
     568                 :            :      and dutifully updated through the representation changes in 2013.
     569                 :            : 
     570                 :            :      In 2013 we added code to thread from an interior node through
     571                 :            :      the backedge to another interior node.  That runs after the code
     572                 :            :      to thread through loop headers from outside the loop.
     573                 :            : 
     574                 :            :      The latter may delete edges in the CFG, including those
     575                 :            :      which appeared in the jump threading path we copied here.  Thus
     576                 :            :      we'd end up using a dangling pointer.
     577                 :            : 
     578                 :            :      After reviewing the 2007/2011 code, I can't see how anything
     579                 :            :      depended on copying the AUX field and clearly copying the jump
     580                 :            :      threading path is problematical due to embedded edge pointers.
     581                 :            :      It has been removed.  */
     582                 :     415242 :   e->aux = NULL;
     583                 :            : 
     584                 :            :   /* If there are any PHI nodes at the destination of the outgoing edge
     585                 :            :      from the duplicate block, then we will need to add a new argument
     586                 :            :      to them.  The argument should have the same value as the argument
     587                 :            :      associated with the outgoing edge stored in RD.  */
     588                 :     415242 :   copy_phi_args (e->dest, rd->path->last ()->e, e, rd->path, idx);
     589                 :     415242 : }
     590                 :            : 
     591                 :            : /* Look through PATH beginning at START and return TRUE if there are
     592                 :            :    any additional blocks that need to be duplicated.  Otherwise,
     593                 :            :    return FALSE.  */
     594                 :            : static bool
     595                 :     108247 : any_remaining_duplicated_blocks (vec<jump_thread_edge *> *path,
     596                 :            :                                  unsigned int start)
     597                 :            : {
     598                 :     249610 :   for (unsigned int i = start + 1; i < path->length (); i++)
     599                 :            :     {
     600                 :      53462 :       if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
     601                 :      53462 :           || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
     602                 :            :         return true;
     603                 :            :     }
     604                 :            :   return false;
     605                 :            : }
     606                 :            : 
     607                 :            : 
     608                 :            : /* Compute the amount of profile count coming into the jump threading
     609                 :            :    path stored in RD that we are duplicating, returned in PATH_IN_COUNT_PTR and
     610                 :            :    PATH_IN_FREQ_PTR, as well as the amount of counts flowing out of the
     611                 :            :    duplicated path, returned in PATH_OUT_COUNT_PTR.  LOCAL_INFO is used to
     612                 :            :    identify blocks duplicated for jump threading, which have duplicated
     613                 :            :    edges that need to be ignored in the analysis.  Return true if path contains
     614                 :            :    a joiner, false otherwise.
     615                 :            : 
     616                 :            :    In the non-joiner case, this is straightforward - all the counts
     617                 :            :    flowing into the jump threading path should flow through the duplicated
     618                 :            :    block and out of the duplicated path.
     619                 :            : 
     620                 :            :    In the joiner case, it is very tricky.  Some of the counts flowing into
     621                 :            :    the original path go offpath at the joiner.  The problem is that while
     622                 :            :    we know how much total count goes off-path in the original control flow,
     623                 :            :    we don't know how many of the counts corresponding to just the jump
     624                 :            :    threading path go offpath at the joiner.
     625                 :            : 
     626                 :            :    For example, assume we have the following control flow and identified
     627                 :            :    jump threading paths:
     628                 :            : 
     629                 :            :                 A     B     C
     630                 :            :                  \    |    /
     631                 :            :                Ea \   |Eb / Ec
     632                 :            :                    \  |  /
     633                 :            :                     v v v
     634                 :            :                       J       <-- Joiner
     635                 :            :                      / \
     636                 :            :                 Eoff/   \Eon
     637                 :            :                    /     \
     638                 :            :                   v       v
     639                 :            :                 Soff     Son  <--- Normal
     640                 :            :                          /\
     641                 :            :                       Ed/  \ Ee
     642                 :            :                        /    \
     643                 :            :                       v     v
     644                 :            :                       D      E
     645                 :            : 
     646                 :            :             Jump threading paths: A -> J -> Son -> D (path 1)
     647                 :            :                                   C -> J -> Son -> E (path 2)
     648                 :            : 
     649                 :            :    Note that the control flow could be more complicated:
     650                 :            :    - Each jump threading path may have more than one incoming edge.  I.e. A and
     651                 :            :    Ea could represent multiple incoming blocks/edges that are included in
     652                 :            :    path 1.
     653                 :            :    - There could be EDGE_NO_COPY_SRC_BLOCK edges after the joiner (either
     654                 :            :    before or after the "normal" copy block).  These are not duplicated onto
     655                 :            :    the jump threading path, as they are single-successor.
     656                 :            :    - Any of the blocks along the path may have other incoming edges that
     657                 :            :    are not part of any jump threading path, but add profile counts along
     658                 :            :    the path.
     659                 :            : 
     660                 :            :    In the above example, after all jump threading is complete, we will
     661                 :            :    end up with the following control flow:
     662                 :            : 
     663                 :            :                 A          B           C
     664                 :            :                 |          |           |
     665                 :            :               Ea|          |Eb         |Ec
     666                 :            :                 |          |           |
     667                 :            :                 v          v           v
     668                 :            :                Ja          J          Jc
     669                 :            :                / \        / \Eon'     / \
     670                 :            :           Eona/   \   ---/---\--------   \Eonc
     671                 :            :              /     \ /  /     \           \
     672                 :            :             v       v  v       v          v
     673                 :            :            Sona     Soff      Son       Sonc
     674                 :            :              \                 /\         /
     675                 :            :               \___________    /  \  _____/
     676                 :            :                           \  /    \/
     677                 :            :                            vv      v
     678                 :            :                             D      E
     679                 :            : 
     680                 :            :    The main issue to notice here is that when we are processing path 1
     681                 :            :    (A->J->Son->D) we need to figure out the outgoing edge weights to
     682                 :            :    the duplicated edges Ja->Sona and Ja->Soff, while ensuring that the
     683                 :            :    sum of the incoming weights to D remain Ed.  The problem with simply
     684                 :            :    assuming that Ja (and Jc when processing path 2) has the same outgoing
     685                 :            :    probabilities to its successors as the original block J, is that after
     686                 :            :    all paths are processed and other edges/counts removed (e.g. none
     687                 :            :    of Ec will reach D after processing path 2), we may end up with not
     688                 :            :    enough count flowing along duplicated edge Sona->D.
     689                 :            : 
     690                 :            :    Therefore, in the case of a joiner, we keep track of all counts
     691                 :            :    coming in along the current path, as well as from predecessors not
     692                 :            :    on any jump threading path (Eb in the above example).  While we
     693                 :            :    first assume that the duplicated Eona for Ja->Sona has the same
     694                 :            :    probability as the original, we later compensate for other jump
     695                 :            :    threading paths that may eliminate edges.  We do that by keep track
     696                 :            :    of all counts coming into the original path that are not in a jump
     697                 :            :    thread (Eb in the above example, but as noted earlier, there could
     698                 :            :    be other predecessors incoming to the path at various points, such
     699                 :            :    as at Son).  Call this cumulative non-path count coming into the path
     700                 :            :    before D as Enonpath.  We then ensure that the count from Sona->D is as at
     701                 :            :    least as big as (Ed - Enonpath), but no bigger than the minimum
     702                 :            :    weight along the jump threading path.  The probabilities of both the
     703                 :            :    original and duplicated joiner block J and Ja will be adjusted
     704                 :            :    accordingly after the updates.  */
     705                 :            : 
     706                 :            : static bool
     707                 :     486585 : compute_path_counts (struct redirection_data *rd,
     708                 :            :                      ssa_local_info_t *local_info,
     709                 :            :                      profile_count *path_in_count_ptr,
     710                 :            :                      profile_count *path_out_count_ptr)
     711                 :            : {
     712                 :     486585 :   edge e = rd->incoming_edges->e;
     713                 :     486585 :   vec<jump_thread_edge *> *path = THREAD_PATH (e);
     714                 :     486585 :   edge elast = path->last ()->e;
     715                 :     486585 :   profile_count nonpath_count = profile_count::zero ();
     716                 :     486585 :   bool has_joiner = false;
     717                 :     486585 :   profile_count path_in_count = profile_count::zero ();
     718                 :            : 
     719                 :            :   /* Start by accumulating incoming edge counts to the path's first bb
     720                 :            :      into a couple buckets:
     721                 :            :         path_in_count: total count of incoming edges that flow into the
     722                 :            :                   current path.
     723                 :            :         nonpath_count: total count of incoming edges that are not
     724                 :            :                   flowing along *any* path.  These are the counts
     725                 :            :                   that will still flow along the original path after
     726                 :            :                   all path duplication is done by potentially multiple
     727                 :            :                   calls to this routine.
     728                 :            :      (any other incoming edge counts are for a different jump threading
     729                 :            :      path that will be handled by a later call to this routine.)
     730                 :            :      To make this easier, start by recording all incoming edges that flow into
     731                 :            :      the current path in a bitmap.  We could add up the path's incoming edge
     732                 :            :      counts here, but we still need to walk all the first bb's incoming edges
     733                 :            :      below to add up the counts of the other edges not included in this jump
     734                 :            :      threading path.  */
     735                 :     486585 :   struct el *next, *el;
     736                 :     486585 :   auto_bitmap in_edge_srcs;
     737                 :    1040910 :   for (el = rd->incoming_edges; el; el = next)
     738                 :            :     {
     739                 :     554323 :       next = el->next;
     740                 :     554323 :       bitmap_set_bit (in_edge_srcs, el->e->src->index);
     741                 :            :     }
     742                 :     486585 :   edge ein;
     743                 :     486585 :   edge_iterator ei;
     744                 :    1575790 :   FOR_EACH_EDGE (ein, ei, e->dest->preds)
     745                 :            :     {
     746                 :    1089200 :       vec<jump_thread_edge *> *ein_path = THREAD_PATH (ein);
     747                 :            :       /* Simply check the incoming edge src against the set captured above.  */
     748                 :    1089200 :       if (ein_path
     749                 :    1089200 :           && bitmap_bit_p (in_edge_srcs, (*ein_path)[0]->e->src->index))
     750                 :            :         {
     751                 :            :           /* It is necessary but not sufficient that the last path edges
     752                 :            :              are identical.  There may be different paths that share the
     753                 :            :              same last path edge in the case where the last edge has a nocopy
     754                 :            :              source block.  */
     755                 :     554323 :           gcc_assert (ein_path->last ()->e == elast);
     756                 :     554323 :           path_in_count += ein->count ();
     757                 :            :         }
     758                 :     534878 :       else if (!ein_path)
     759                 :            :         {
     760                 :            :           /* Keep track of the incoming edges that are not on any jump-threading
     761                 :            :              path.  These counts will still flow out of original path after all
     762                 :            :              jump threading is complete.  */
     763                 :     319597 :             nonpath_count += ein->count ();
     764                 :            :         }
     765                 :            :     }
     766                 :            : 
     767                 :            :   /* Now compute the fraction of the total count coming into the first
     768                 :            :      path bb that is from the current threading path.  */
     769                 :     486585 :   profile_count total_count = e->dest->count;
     770                 :            :   /* Handle incoming profile insanities.  */
     771                 :     486585 :   if (total_count < path_in_count)
     772                 :      25336 :     path_in_count = total_count;
     773                 :     486585 :   profile_probability onpath_scale = path_in_count.probability_in (total_count);
     774                 :            : 
     775                 :            :   /* Walk the entire path to do some more computation in order to estimate
     776                 :            :      how much of the path_in_count will flow out of the duplicated threading
     777                 :            :      path.  In the non-joiner case this is straightforward (it should be
     778                 :            :      the same as path_in_count, although we will handle incoming profile
     779                 :            :      insanities by setting it equal to the minimum count along the path).
     780                 :            : 
     781                 :            :      In the joiner case, we need to estimate how much of the path_in_count
     782                 :            :      will stay on the threading path after the joiner's conditional branch.
     783                 :            :      We don't really know for sure how much of the counts
     784                 :            :      associated with this path go to each successor of the joiner, but we'll
     785                 :            :      estimate based on the fraction of the total count coming into the path
     786                 :            :      bb was from the threading paths (computed above in onpath_scale).
     787                 :            :      Afterwards, we will need to do some fixup to account for other threading
     788                 :            :      paths and possible profile insanities.
     789                 :            : 
     790                 :            :      In order to estimate the joiner case's counts we also need to update
     791                 :            :      nonpath_count with any additional counts coming into the path.  Other
     792                 :            :      blocks along the path may have additional predecessors from outside
     793                 :            :      the path.  */
     794                 :     486585 :   profile_count path_out_count = path_in_count;
     795                 :     486585 :   profile_count min_path_count = path_in_count;
     796                 :    2098930 :   for (unsigned int i = 1; i < path->length (); i++)
     797                 :            :     {
     798                 :     562882 :       edge epath = (*path)[i]->e;
     799                 :     562882 :       profile_count cur_count = epath->count ();
     800                 :     562882 :       if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
     801                 :            :         {
     802                 :     108247 :           has_joiner = true;
     803                 :     108247 :           cur_count = cur_count.apply_probability (onpath_scale);
     804                 :            :         }
     805                 :            :       /* In the joiner case we need to update nonpath_count for any edges
     806                 :            :          coming into the path that will contribute to the count flowing
     807                 :            :          into the path successor.  */
     808                 :     562882 :       if (has_joiner && epath != elast)
     809                 :            :         {
     810                 :            :           /* Look for other incoming edges after joiner.  */
     811                 :     210195 :           FOR_EACH_EDGE (ein, ei, epath->dest->preds)
     812                 :            :             {
     813                 :     153891 :               if (ein != epath
     814                 :            :                   /* Ignore in edges from blocks we have duplicated for a
     815                 :            :                      threading path, which have duplicated edge counts until
     816                 :            :                      they are redirected by an invocation of this routine.  */
     817                 :     251478 :                   && !bitmap_bit_p (local_info->duplicate_blocks,
     818                 :      97587 :                                     ein->src->index))
     819                 :      31890 :                 nonpath_count += ein->count ();
     820                 :            :             }
     821                 :            :         }
     822                 :     562882 :       if (cur_count < path_out_count)
     823                 :     193743 :         path_out_count = cur_count;
     824                 :     562882 :       if (epath->count () < min_path_count)
     825                 :     175523 :         min_path_count = epath->count ();
     826                 :            :     }
     827                 :            : 
     828                 :            :   /* We computed path_out_count above assuming that this path targeted
     829                 :            :      the joiner's on-path successor with the same likelihood as it
     830                 :            :      reached the joiner.  However, other thread paths through the joiner
     831                 :            :      may take a different path through the normal copy source block
     832                 :            :      (i.e. they have a different elast), meaning that they do not
     833                 :            :      contribute any counts to this path's elast.  As a result, it may
     834                 :            :      turn out that this path must have more count flowing to the on-path
     835                 :            :      successor of the joiner.  Essentially, all of this path's elast
     836                 :            :      count must be contributed by this path and any nonpath counts
     837                 :            :      (since any path through the joiner with a different elast will not
     838                 :            :      include a copy of this elast in its duplicated path).
     839                 :            :      So ensure that this path's path_out_count is at least the
     840                 :            :      difference between elast->count () and nonpath_count.  Otherwise the edge
     841                 :            :      counts after threading will not be sane.  */
     842                 :     486585 :   if (local_info->need_profile_correction
     843                 :     486585 :       && has_joiner && path_out_count < elast->count () - nonpath_count)
     844                 :            :     {
     845                 :      12487 :       path_out_count = elast->count () - nonpath_count;
     846                 :            :       /* But neither can we go above the minimum count along the path
     847                 :            :          we are duplicating.  This can be an issue due to profile
     848                 :            :          insanities coming in to this pass.  */
     849                 :      12487 :       if (path_out_count > min_path_count)
     850                 :       8062 :         path_out_count = min_path_count;
     851                 :            :     }
     852                 :            : 
     853                 :     486585 :   *path_in_count_ptr = path_in_count;
     854                 :     486585 :   *path_out_count_ptr = path_out_count;
     855                 :     486585 :   return has_joiner;
     856                 :            : }
     857                 :            : 
     858                 :            : 
     859                 :            : /* Update the counts and frequencies for both an original path
     860                 :            :    edge EPATH and its duplicate EDUP.  The duplicate source block
     861                 :            :    will get a count of PATH_IN_COUNT and PATH_IN_FREQ,
     862                 :            :    and the duplicate edge EDUP will have a count of PATH_OUT_COUNT.  */
     863                 :            : static void
     864                 :     562882 : update_profile (edge epath, edge edup, profile_count path_in_count,
     865                 :            :                 profile_count path_out_count)
     866                 :            : {
     867                 :            : 
     868                 :            :   /* First update the duplicated block's count.  */
     869                 :     562882 :   if (edup)
     870                 :            :     {
     871                 :     466807 :       basic_block dup_block = edup->src;
     872                 :            : 
     873                 :            :       /* Edup's count is reduced by path_out_count.  We need to redistribute
     874                 :            :          probabilities to the remaining edges.  */
     875                 :            : 
     876                 :     466807 :       edge esucc;
     877                 :     466807 :       edge_iterator ei;
     878                 :     466807 :       profile_probability edup_prob
     879                 :     466807 :          = path_out_count.probability_in (path_in_count);
     880                 :            : 
     881                 :            :       /* Either scale up or down the remaining edges.
     882                 :            :          probabilities are always in range <0,1> and thus we can't do
     883                 :            :          both by same loop.  */
     884                 :     466807 :       if (edup->probability > edup_prob)
     885                 :            :         {
     886                 :      21711 :            profile_probability rev_scale
     887                 :      43422 :              = (profile_probability::always () - edup->probability)
     888                 :      21711 :                / (profile_probability::always () - edup_prob);
     889                 :      63628 :            FOR_EACH_EDGE (esucc, ei, dup_block->succs)
     890                 :      41917 :              if (esucc != edup)
     891                 :      20206 :                esucc->probability /= rev_scale;
     892                 :            :         }
     893                 :     445096 :       else if (edup->probability < edup_prob)
     894                 :            :         {
     895                 :      10231 :            profile_probability scale
     896                 :      10231 :              = (profile_probability::always () - edup_prob)
     897                 :      10231 :                / (profile_probability::always () - edup->probability);
     898                 :      30850 :           FOR_EACH_EDGE (esucc, ei, dup_block->succs)
     899                 :      20619 :             if (esucc != edup)
     900                 :      10388 :               esucc->probability *= scale;
     901                 :            :         }
     902                 :     466807 :       if (edup_prob.initialized_p ())
     903                 :     441612 :         edup->probability = edup_prob;
     904                 :            : 
     905                 :     466807 :       gcc_assert (!dup_block->count.initialized_p ());
     906                 :     466807 :       dup_block->count = path_in_count;
     907                 :            :     }
     908                 :            : 
     909                 :     562882 :   if (path_in_count == profile_count::zero ())
     910                 :       4536 :     return;
     911                 :            : 
     912                 :     558346 :   profile_count final_count = epath->count () - path_out_count;
     913                 :            : 
     914                 :            :   /* Now update the original block's count in the
     915                 :            :      opposite manner - remove the counts/freq that will flow
     916                 :            :      into the duplicated block.  Handle underflow due to precision/
     917                 :            :      rounding issues.  */
     918                 :     558346 :   epath->src->count -= path_in_count;
     919                 :            : 
     920                 :            :   /* Next update this path edge's original and duplicated counts.  We know
     921                 :            :      that the duplicated path will have path_out_count flowing
     922                 :            :      out of it (in the joiner case this is the count along the duplicated path
     923                 :            :      out of the duplicated joiner).  This count can then be removed from the
     924                 :            :      original path edge.  */
     925                 :            : 
     926                 :     558346 :   edge esucc;
     927                 :     558346 :   edge_iterator ei;
     928                 :     558346 :   profile_probability epath_prob = final_count.probability_in (epath->src->count);
     929                 :            : 
     930                 :     558346 :   if (epath->probability > epath_prob)
     931                 :            :     {
     932                 :     388563 :        profile_probability rev_scale
     933                 :     777126 :          = (profile_probability::always () - epath->probability)
     934                 :     388563 :            / (profile_probability::always () - epath_prob);
     935                 :    1168010 :        FOR_EACH_EDGE (esucc, ei, epath->src->succs)
     936                 :     779446 :          if (esucc != epath)
     937                 :     390883 :            esucc->probability /= rev_scale;
     938                 :            :     }
     939                 :     169783 :   else if (epath->probability < epath_prob)
     940                 :            :     {
     941                 :      16836 :        profile_probability scale
     942                 :      16836 :          = (profile_probability::always () - epath_prob)
     943                 :      16836 :            / (profile_probability::always () - epath->probability);
     944                 :      50714 :       FOR_EACH_EDGE (esucc, ei, epath->src->succs)
     945                 :      33878 :         if (esucc != epath)
     946                 :      17042 :           esucc->probability *= scale;
     947                 :            :     }
     948                 :     558346 :   if (epath_prob.initialized_p ())
     949                 :     488522 :     epath->probability = epath_prob;
     950                 :            : }
     951                 :            : 
     952                 :            : /* Wire up the outgoing edges from the duplicate blocks and
     953                 :            :    update any PHIs as needed.  Also update the profile counts
     954                 :            :    on the original and duplicate blocks and edges.  */
     955                 :            : void
     956                 :     486585 : ssa_fix_duplicate_block_edges (struct redirection_data *rd,
     957                 :            :                                ssa_local_info_t *local_info)
     958                 :            : {
     959                 :     486585 :   bool multi_incomings = (rd->incoming_edges->next != NULL);
     960                 :     486585 :   edge e = rd->incoming_edges->e;
     961                 :     486585 :   vec<jump_thread_edge *> *path = THREAD_PATH (e);
     962                 :     486585 :   edge elast = path->last ()->e;
     963                 :     486585 :   profile_count path_in_count = profile_count::zero ();
     964                 :     486585 :   profile_count path_out_count = profile_count::zero ();
     965                 :            : 
     966                 :            :   /* First determine how much profile count to move from original
     967                 :            :      path to the duplicate path.  This is tricky in the presence of
     968                 :            :      a joiner (see comments for compute_path_counts), where some portion
     969                 :            :      of the path's counts will flow off-path from the joiner.  In the
     970                 :            :      non-joiner case the path_in_count and path_out_count should be the
     971                 :            :      same.  */
     972                 :     486585 :   bool has_joiner = compute_path_counts (rd, local_info,
     973                 :            :                                          &path_in_count, &path_out_count);
     974                 :            : 
     975                 :    2098930 :   for (unsigned int count = 0, i = 1; i < path->length (); i++)
     976                 :            :     {
     977                 :     562882 :       edge epath = (*path)[i]->e;
     978                 :            : 
     979                 :            :       /* If we were threading through an joiner block, then we want
     980                 :            :          to keep its control statement and redirect an outgoing edge.
     981                 :            :          Else we want to remove the control statement & edges, then create
     982                 :            :          a new outgoing edge.  In both cases we may need to update PHIs.  */
     983                 :     562882 :       if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
     984                 :            :         {
     985                 :     108247 :           edge victim;
     986                 :     108247 :           edge e2;
     987                 :            : 
     988                 :     108247 :           gcc_assert (has_joiner);
     989                 :            : 
     990                 :            :           /* This updates the PHIs at the destination of the duplicate
     991                 :            :              block.  Pass 0 instead of i if we are threading a path which
     992                 :            :              has multiple incoming edges.  */
     993                 :     199513 :           update_destination_phis (local_info->bb, rd->dup_blocks[count],
     994                 :            :                                    path, multi_incomings ? 0 : i);
     995                 :            : 
     996                 :            :           /* Find the edge from the duplicate block to the block we're
     997                 :            :              threading through.  That's the edge we want to redirect.  */
     998                 :     108247 :           victim = find_edge (rd->dup_blocks[count], (*path)[i]->e->dest);
     999                 :            : 
    1000                 :            :           /* If there are no remaining blocks on the path to duplicate,
    1001                 :            :              then redirect VICTIM to the final destination of the jump
    1002                 :            :              threading path.  */
    1003                 :     108247 :           if (!any_remaining_duplicated_blocks (path, i))
    1004                 :            :             {
    1005                 :      71343 :               e2 = redirect_edge_and_branch (victim, elast->dest);
    1006                 :            :               /* If we redirected the edge, then we need to copy PHI arguments
    1007                 :            :                  at the target.  If the edge already existed (e2 != victim
    1008                 :            :                  case), then the PHIs in the target already have the correct
    1009                 :            :                  arguments.  */
    1010                 :      71343 :               if (e2 == victim)
    1011                 :      13738 :                 copy_phi_args (e2->dest, elast, e2,
    1012                 :            :                                path, multi_incomings ? 0 : i);
    1013                 :            :             }
    1014                 :            :           else
    1015                 :            :             {
    1016                 :            :               /* Redirect VICTIM to the next duplicated block in the path.  */
    1017                 :      36904 :               e2 = redirect_edge_and_branch (victim, rd->dup_blocks[count + 1]);
    1018                 :            : 
    1019                 :            :               /* We need to update the PHIs in the next duplicated block.  We
    1020                 :            :                  want the new PHI args to have the same value as they had
    1021                 :            :                  in the source of the next duplicate block.
    1022                 :            : 
    1023                 :            :                  Thus, we need to know which edge we traversed into the
    1024                 :            :                  source of the duplicate.  Furthermore, we may have
    1025                 :            :                  traversed many edges to reach the source of the duplicate.
    1026                 :            : 
    1027                 :            :                  Walk through the path starting at element I until we
    1028                 :            :                  hit an edge marked with EDGE_COPY_SRC_BLOCK.  We want
    1029                 :            :                  the edge from the prior element.  */
    1030                 :      76230 :               for (unsigned int j = i + 1; j < path->length (); j++)
    1031                 :            :                 {
    1032                 :      38115 :                   if ((*path)[j]->type == EDGE_COPY_SRC_BLOCK)
    1033                 :            :                     {
    1034                 :      36904 :                       copy_phi_arg_into_existing_phi ((*path)[j - 1]->e, e2);
    1035                 :      36904 :                       break;
    1036                 :            :                     }
    1037                 :            :                 }
    1038                 :            :             }
    1039                 :            : 
    1040                 :            :           /* Update the counts of both the original block
    1041                 :            :              and path edge, and the duplicates.  The path duplicate's
    1042                 :            :              incoming count are the totals for all edges
    1043                 :            :              incoming to this jump threading path computed earlier.
    1044                 :            :              And we know that the duplicated path will have path_out_count
    1045                 :            :              flowing out of it (i.e. along the duplicated path out of the
    1046                 :            :              duplicated joiner).  */
    1047                 :     108247 :           update_profile (epath, e2, path_in_count, path_out_count);
    1048                 :            :         }
    1049                 :     454635 :       else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK)
    1050                 :            :         {
    1051                 :     415242 :           remove_ctrl_stmt_and_useless_edges (rd->dup_blocks[count], NULL);
    1052                 :     793331 :           create_edge_and_update_destination_phis (rd, rd->dup_blocks[count],
    1053                 :            :                                                    multi_incomings ? 0 : i);
    1054                 :     415242 :           if (count == 1)
    1055                 :      36904 :             single_succ_edge (rd->dup_blocks[1])->aux = NULL;
    1056                 :            : 
    1057                 :            :           /* Update the counts of both the original block
    1058                 :            :              and path edge, and the duplicates.  Since we are now after
    1059                 :            :              any joiner that may have existed on the path, the count
    1060                 :            :              flowing along the duplicated threaded path is path_out_count.
    1061                 :            :              If we didn't have a joiner, then cur_path_freq was the sum
    1062                 :            :              of the total frequencies along all incoming edges to the
    1063                 :            :              thread path (path_in_freq).  If we had a joiner, it would have
    1064                 :            :              been updated at the end of that handling to the edge frequency
    1065                 :            :              along the duplicated joiner path edge.  */
    1066                 :     415242 :           update_profile (epath, EDGE_SUCC (rd->dup_blocks[count], 0),
    1067                 :            :                           path_out_count, path_out_count);
    1068                 :            :         }
    1069                 :            :       else
    1070                 :            :         {
    1071                 :            :           /* No copy case.  In this case we don't have an equivalent block
    1072                 :            :              on the duplicated thread path to update, but we do need
    1073                 :            :              to remove the portion of the counts/freqs that were moved
    1074                 :            :              to the duplicated path from the counts/freqs flowing through
    1075                 :            :              this block on the original path.  Since all the no-copy edges
    1076                 :            :              are after any joiner, the removed count is the same as
    1077                 :            :              path_out_count.
    1078                 :            : 
    1079                 :            :              If we didn't have a joiner, then cur_path_freq was the sum
    1080                 :            :              of the total frequencies along all incoming edges to the
    1081                 :            :              thread path (path_in_freq).  If we had a joiner, it would have
    1082                 :            :              been updated at the end of that handling to the edge frequency
    1083                 :            :              along the duplicated joiner path edge.  */
    1084                 :      39393 :            update_profile (epath, NULL, path_out_count, path_out_count);
    1085                 :            :         }
    1086                 :            : 
    1087                 :            :       /* Increment the index into the duplicated path when we processed
    1088                 :            :          a duplicated block.  */
    1089                 :     562882 :       if ((*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK
    1090                 :     562882 :           || (*path)[i]->type == EDGE_COPY_SRC_BLOCK)
    1091                 :            :         {
    1092                 :     523489 :           count++;
    1093                 :            :         }
    1094                 :            :     }
    1095                 :     486585 : }
    1096                 :            : 
    1097                 :            : /* Hash table traversal callback routine to create duplicate blocks.  */
    1098                 :            : 
    1099                 :            : int
    1100                 :     486585 : ssa_create_duplicates (struct redirection_data **slot,
    1101                 :            :                        ssa_local_info_t *local_info)
    1102                 :            : {
    1103                 :     486585 :   struct redirection_data *rd = *slot;
    1104                 :            : 
    1105                 :            :   /* The second duplicated block in a jump threading path is specific
    1106                 :            :      to the path.  So it gets stored in RD rather than in LOCAL_DATA.
    1107                 :            : 
    1108                 :            :      Each time we're called, we have to look through the path and see
    1109                 :            :      if a second block needs to be duplicated.
    1110                 :            : 
    1111                 :            :      Note the search starts with the third edge on the path.  The first
    1112                 :            :      edge is the incoming edge, the second edge always has its source
    1113                 :            :      duplicated.  Thus we start our search with the third edge.  */
    1114                 :     486585 :   vec<jump_thread_edge *> *path = rd->path;
    1115                 :    1046270 :   for (unsigned int i = 2; i < path->length (); i++)
    1116                 :            :     {
    1117                 :      73455 :       if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
    1118                 :      73455 :           || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
    1119                 :            :         {
    1120                 :      36904 :           create_block_for_threading ((*path)[i]->e->src, rd, 1,
    1121                 :            :                                       &local_info->duplicate_blocks);
    1122                 :      36904 :           break;
    1123                 :            :         }
    1124                 :            :     }
    1125                 :            : 
    1126                 :            :   /* Create a template block if we have not done so already.  Otherwise
    1127                 :            :      use the template to create a new block.  */
    1128                 :     486585 :   if (local_info->template_block == NULL)
    1129                 :            :     {
    1130                 :     414195 :       create_block_for_threading ((*path)[1]->e->src, rd, 0,
    1131                 :            :                                   &local_info->duplicate_blocks);
    1132                 :     414195 :       local_info->template_block = rd->dup_blocks[0];
    1133                 :     414195 :       local_info->template_last_to_copy
    1134                 :     828390 :         = gsi_last_bb (local_info->template_block);
    1135                 :            : 
    1136                 :            :       /* We do not create any outgoing edges for the template.  We will
    1137                 :            :          take care of that in a later traversal.  That way we do not
    1138                 :            :          create edges that are going to just be deleted.  */
    1139                 :            :     }
    1140                 :            :   else
    1141                 :            :     {
    1142                 :      72390 :       gimple_seq seq = NULL;
    1143                 :     144780 :       if (gsi_stmt (local_info->template_last_to_copy)
    1144                 :     144780 :           != gsi_stmt (gsi_last_bb (local_info->template_block)))
    1145                 :            :         {
    1146                 :          0 :           if (gsi_end_p (local_info->template_last_to_copy))
    1147                 :            :             {
    1148                 :          0 :               seq = bb_seq (local_info->template_block);
    1149                 :          0 :               set_bb_seq (local_info->template_block, NULL);
    1150                 :            :             }
    1151                 :            :           else
    1152                 :          0 :             seq = gsi_split_seq_after (local_info->template_last_to_copy);
    1153                 :            :         }
    1154                 :      72390 :       create_block_for_threading (local_info->template_block, rd, 0,
    1155                 :            :                                   &local_info->duplicate_blocks);
    1156                 :      72390 :       if (seq)
    1157                 :            :         {
    1158                 :          0 :           if (gsi_end_p (local_info->template_last_to_copy))
    1159                 :          0 :             set_bb_seq (local_info->template_block, seq);
    1160                 :            :           else
    1161                 :          0 :             gsi_insert_seq_after (&local_info->template_last_to_copy,
    1162                 :            :                                   seq, GSI_SAME_STMT);
    1163                 :            :         }
    1164                 :            : 
    1165                 :            :       /* Go ahead and wire up outgoing edges and update PHIs for the duplicate
    1166                 :            :          block.   */
    1167                 :      72390 :       ssa_fix_duplicate_block_edges (rd, local_info);
    1168                 :            :     }
    1169                 :            : 
    1170                 :     486585 :   if (MAY_HAVE_DEBUG_STMTS)
    1171                 :            :     {
    1172                 :            :       /* Copy debug stmts from each NO_COPY src block to the block
    1173                 :            :          that would have been its predecessor, if we can append to it
    1174                 :            :          (we can't add stmts after a block-ending stmt), or prepending
    1175                 :            :          to the duplicate of the successor, if there is one.  If
    1176                 :            :          there's no duplicate successor, we'll mostly drop the blocks
    1177                 :            :          on the floor; propagate_threaded_block_debug_into, called
    1178                 :            :          elsewhere, will consolidate and preserve the effects of the
    1179                 :            :          binds, but none of the markers.  */
    1180                 :     335201 :       gimple_stmt_iterator copy_to = gsi_last_bb (rd->dup_blocks[0]);
    1181                 :     335201 :       if (!gsi_end_p (copy_to))
    1182                 :            :         {
    1183                 :     321483 :           if (stmt_ends_bb_p (gsi_stmt (copy_to)))
    1184                 :            :             {
    1185                 :     296220 :               if (rd->dup_blocks[1])
    1186                 :      55590 :                 copy_to = gsi_after_labels (rd->dup_blocks[1]);
    1187                 :            :               else
    1188                 :     268425 :                 copy_to = gsi_none ();
    1189                 :            :             }
    1190                 :            :           else
    1191                 :      25263 :             gsi_next (&copy_to);
    1192                 :            :         }
    1193                 :     789454 :       for (unsigned int i = 2, j = 0; i < path->length (); i++)
    1194                 :      59526 :         if ((*path)[i]->type == EDGE_NO_COPY_SRC_BLOCK
    1195                 :      59526 :             && gsi_bb (copy_to))
    1196                 :            :           {
    1197                 :       4082 :             for (gimple_stmt_iterator gsi = gsi_start_bb ((*path)[i]->e->src);
    1198                 :      13814 :                  !gsi_end_p (gsi); gsi_next (&gsi))
    1199                 :            :               {
    1200                 :       9732 :                 if (!is_gimple_debug (gsi_stmt (gsi)))
    1201                 :       1202 :                   continue;
    1202                 :       8530 :                 gimple *stmt = gsi_stmt (gsi);
    1203                 :       8530 :                 gimple *copy = gimple_copy (stmt);
    1204                 :       8530 :                 gsi_insert_before (&copy_to, copy, GSI_SAME_STMT);
    1205                 :            :               }
    1206                 :            :           }
    1207                 :      55444 :         else if ((*path)[i]->type == EDGE_COPY_SRC_BLOCK
    1208                 :      55444 :                  || (*path)[i]->type == EDGE_COPY_SRC_JOINER_BLOCK)
    1209                 :            :           {
    1210                 :      29494 :             j++;
    1211                 :      29494 :             gcc_assert (j < 2);
    1212                 :      29494 :             copy_to = gsi_last_bb (rd->dup_blocks[j]);
    1213                 :      29494 :             if (!gsi_end_p (copy_to))
    1214                 :            :               {
    1215                 :      28981 :                 if (stmt_ends_bb_p (gsi_stmt (copy_to)))
    1216                 :      23757 :                   copy_to = gsi_none ();
    1217                 :            :                 else
    1218                 :       5224 :                   gsi_next (&copy_to);
    1219                 :            :               }
    1220                 :            :           }
    1221                 :            :     }
    1222                 :            : 
    1223                 :            :   /* Keep walking the hash table.  */
    1224                 :     486585 :   return 1;
    1225                 :            : }
    1226                 :            : 
    1227                 :            : /* We did not create any outgoing edges for the template block during
    1228                 :            :    block creation.  This hash table traversal callback creates the
    1229                 :            :    outgoing edge for the template block.  */
    1230                 :            : 
    1231                 :            : inline int
    1232                 :     414195 : ssa_fixup_template_block (struct redirection_data **slot,
    1233                 :            :                           ssa_local_info_t *local_info)
    1234                 :            : {
    1235                 :     414195 :   struct redirection_data *rd = *slot;
    1236                 :            : 
    1237                 :            :   /* If this is the template block halt the traversal after updating
    1238                 :            :      it appropriately.
    1239                 :            : 
    1240                 :            :      If we were threading through an joiner block, then we want
    1241                 :            :      to keep its control statement and redirect an outgoing edge.
    1242                 :            :      Else we want to remove the control statement & edges, then create
    1243                 :            :      a new outgoing edge.  In both cases we may need to update PHIs.  */
    1244                 :     414195 :   if (rd->dup_blocks[0] && rd->dup_blocks[0] == local_info->template_block)
    1245                 :            :     {
    1246                 :     414195 :       ssa_fix_duplicate_block_edges (rd, local_info);
    1247                 :     414195 :       return 0;
    1248                 :            :     }
    1249                 :            : 
    1250                 :            :   return 1;
    1251                 :            : }
    1252                 :            : 
    1253                 :            : /* Hash table traversal callback to redirect each incoming edge
    1254                 :            :    associated with this hash table element to its new destination.  */
    1255                 :            : 
    1256                 :            : int
    1257                 :     486585 : ssa_redirect_edges (struct redirection_data **slot,
    1258                 :            :                     ssa_local_info_t *local_info)
    1259                 :            : {
    1260                 :     486585 :   struct redirection_data *rd = *slot;
    1261                 :     486585 :   struct el *next, *el;
    1262                 :            : 
    1263                 :            :   /* Walk over all the incoming edges associated with this hash table
    1264                 :            :      entry.  */
    1265                 :    1040910 :   for (el = rd->incoming_edges; el; el = next)
    1266                 :            :     {
    1267                 :     554323 :       edge e = el->e;
    1268                 :     554323 :       vec<jump_thread_edge *> *path = THREAD_PATH (e);
    1269                 :            : 
    1270                 :            :       /* Go ahead and free this element from the list.  Doing this now
    1271                 :            :          avoids the need for another list walk when we destroy the hash
    1272                 :            :          table.  */
    1273                 :     554323 :       next = el->next;
    1274                 :     554323 :       free (el);
    1275                 :            : 
    1276                 :     554323 :       thread_stats.num_threaded_edges++;
    1277                 :            : 
    1278                 :     554323 :       if (rd->dup_blocks[0])
    1279                 :            :         {
    1280                 :     554323 :           edge e2;
    1281                 :            : 
    1282                 :     554323 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1283                 :         75 :             fprintf (dump_file, "  Threaded jump %d --> %d to %d\n",
    1284                 :         75 :                      e->src->index, e->dest->index, rd->dup_blocks[0]->index);
    1285                 :            : 
    1286                 :            :           /* Redirect the incoming edge (possibly to the joiner block) to the
    1287                 :            :              appropriate duplicate block.  */
    1288                 :     554323 :           e2 = redirect_edge_and_branch (e, rd->dup_blocks[0]);
    1289                 :     554323 :           gcc_assert (e == e2);
    1290                 :     554323 :           flush_pending_stmts (e2);
    1291                 :            :         }
    1292                 :            : 
    1293                 :            :       /* Go ahead and clear E->aux.  It's not needed anymore and failure
    1294                 :            :          to clear it will cause all kinds of unpleasant problems later.  */
    1295                 :     554323 :       delete_jump_thread_path (path);
    1296                 :     554323 :       e->aux = NULL;
    1297                 :            : 
    1298                 :            :     }
    1299                 :            : 
    1300                 :            :   /* Indicate that we actually threaded one or more jumps.  */
    1301                 :     486585 :   if (rd->incoming_edges)
    1302                 :     486585 :     local_info->jumps_threaded = true;
    1303                 :            : 
    1304                 :     486585 :   return 1;
    1305                 :            : }
    1306                 :            : 
    1307                 :            : /* Return true if this block has no executable statements other than
    1308                 :            :    a simple ctrl flow instruction.  When the number of outgoing edges
    1309                 :            :    is one, this is equivalent to a "forwarder" block.  */
    1310                 :            : 
    1311                 :            : static bool
    1312                 :     300671 : redirection_block_p (basic_block bb)
    1313                 :            : {
    1314                 :     300671 :   gimple_stmt_iterator gsi;
    1315                 :            : 
    1316                 :            :   /* Advance to the first executable statement.  */
    1317                 :     601342 :   gsi = gsi_start_bb (bb);
    1318                 :     731783 :   while (!gsi_end_p (gsi)
    1319                 :     731783 :          && (gimple_code (gsi_stmt (gsi)) == GIMPLE_LABEL
    1320                 :     728432 :              || is_gimple_debug (gsi_stmt (gsi))
    1321                 :     300095 :              || gimple_nop_p (gsi_stmt (gsi))
    1322                 :     300095 :              || gimple_clobber_p (gsi_stmt (gsi))))
    1323                 :     431112 :     gsi_next (&gsi);
    1324                 :            : 
    1325                 :            :   /* Check if this is an empty block.  */
    1326                 :     300671 :   if (gsi_end_p (gsi))
    1327                 :            :     return true;
    1328                 :            : 
    1329                 :            :   /* Test that we've reached the terminating control statement.  */
    1330                 :     299555 :   return gsi_stmt (gsi)
    1331                 :     299555 :          && (gimple_code (gsi_stmt (gsi)) == GIMPLE_COND
    1332                 :     147864 :              || gimple_code (gsi_stmt (gsi)) == GIMPLE_GOTO
    1333                 :     147842 :              || gimple_code (gsi_stmt (gsi)) == GIMPLE_SWITCH);
    1334                 :            : }
    1335                 :            : 
    1336                 :            : /* BB is a block which ends with a COND_EXPR or SWITCH_EXPR and when BB
    1337                 :            :    is reached via one or more specific incoming edges, we know which
    1338                 :            :    outgoing edge from BB will be traversed.
    1339                 :            : 
    1340                 :            :    We want to redirect those incoming edges to the target of the
    1341                 :            :    appropriate outgoing edge.  Doing so avoids a conditional branch
    1342                 :            :    and may expose new optimization opportunities.  Note that we have
    1343                 :            :    to update dominator tree and SSA graph after such changes.
    1344                 :            : 
    1345                 :            :    The key to keeping the SSA graph update manageable is to duplicate
    1346                 :            :    the side effects occurring in BB so that those side effects still
    1347                 :            :    occur on the paths which bypass BB after redirecting edges.
    1348                 :            : 
    1349                 :            :    We accomplish this by creating duplicates of BB and arranging for
    1350                 :            :    the duplicates to unconditionally pass control to one specific
    1351                 :            :    successor of BB.  We then revector the incoming edges into BB to
    1352                 :            :    the appropriate duplicate of BB.
    1353                 :            : 
    1354                 :            :    If NOLOOP_ONLY is true, we only perform the threading as long as it
    1355                 :            :    does not affect the structure of the loops in a nontrivial way.
    1356                 :            : 
    1357                 :            :    If JOINERS is true, then thread through joiner blocks as well.  */
    1358                 :            : 
    1359                 :            : static bool
    1360                 :    1494890 : thread_block_1 (basic_block bb, bool noloop_only, bool joiners)
    1361                 :            : {
    1362                 :            :   /* E is an incoming edge into BB that we may or may not want to
    1363                 :            :      redirect to a duplicate of BB.  */
    1364                 :    1494890 :   edge e, e2;
    1365                 :    1494890 :   edge_iterator ei;
    1366                 :    1494890 :   ssa_local_info_t local_info;
    1367                 :            : 
    1368                 :    1494890 :   local_info.duplicate_blocks = BITMAP_ALLOC (NULL);
    1369                 :    1494890 :   local_info.need_profile_correction = false;
    1370                 :            : 
    1371                 :            :   /* To avoid scanning a linear array for the element we need we instead
    1372                 :            :      use a hash table.  For normal code there should be no noticeable
    1373                 :            :      difference.  However, if we have a block with a large number of
    1374                 :            :      incoming and outgoing edges such linear searches can get expensive.  */
    1375                 :    1494890 :   redirection_data
    1376                 :    2989790 :     = new hash_table<struct redirection_data> (EDGE_COUNT (bb->succs));
    1377                 :            : 
    1378                 :            :   /* Record each unique threaded destination into a hash table for
    1379                 :            :      efficient lookups.  */
    1380                 :    1494890 :   edge last = NULL;
    1381                 :    4296540 :   FOR_EACH_EDGE (e, ei, bb->preds)
    1382                 :            :     {
    1383                 :    2801650 :       if (e->aux == NULL)
    1384                 :    1349530 :         continue;
    1385                 :            : 
    1386                 :    1452120 :       vec<jump_thread_edge *> *path = THREAD_PATH (e);
    1387                 :            : 
    1388                 :    1991280 :       if (((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && !joiners)
    1389                 :    1721700 :           || ((*path)[1]->type == EDGE_COPY_SRC_BLOCK && joiners))
    1390                 :     514528 :         continue;
    1391                 :            : 
    1392                 :     937588 :       e2 = path->last ()->e;
    1393                 :     937588 :       if (!e2 || noloop_only)
    1394                 :            :         {
    1395                 :            :           /* If NOLOOP_ONLY is true, we only allow threading through the
    1396                 :            :              header of a loop to exit edges.  */
    1397                 :            : 
    1398                 :            :           /* One case occurs when there was loop header buried in a jump
    1399                 :            :              threading path that crosses loop boundaries.  We do not try
    1400                 :            :              and thread this elsewhere, so just cancel the jump threading
    1401                 :            :              request by clearing the AUX field now.  */
    1402                 :     853869 :           if (bb->loop_father != e2->src->loop_father
    1403                 :     812567 :               && (!loop_exit_edge_p (e2->src->loop_father, e2)
    1404                 :       2230 :                   || flow_loop_nested_p (bb->loop_father,
    1405                 :       2230 :                                          e2->dest->loop_father)))
    1406                 :            :             {
    1407                 :            :               /* Since this case is not handled by our special code
    1408                 :            :                  to thread through a loop header, we must explicitly
    1409                 :            :                  cancel the threading request here.  */
    1410                 :      41302 :               delete_jump_thread_path (path);
    1411                 :      41302 :               e->aux = NULL;
    1412                 :      41302 :               continue;
    1413                 :            :             }
    1414                 :            : 
    1415                 :            :           /* Another case occurs when trying to thread through our
    1416                 :            :              own loop header, possibly from inside the loop.  We will
    1417                 :            :              thread these later.  */
    1418                 :            :           unsigned int i;
    1419                 :    2586570 :           for (i = 1; i < path->length (); i++)
    1420                 :            :             {
    1421                 :     863897 :               if ((*path)[i]->e->src == bb->loop_father->header
    1422                 :     863897 :                   && (!loop_exit_edge_p (bb->loop_father, e2)
    1423                 :       1584 :                       || (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK))
    1424                 :            :                 break;
    1425                 :            :             }
    1426                 :            : 
    1427                 :    1542530 :           if (i != path->length ())
    1428                 :     341875 :             continue;
    1429                 :            : 
    1430                 :            :           /* Loop parallelization can be confused by the result of
    1431                 :            :              threading through the loop exit test back into the loop.
    1432                 :            :              However, theading those jumps seems to help other codes.
    1433                 :            : 
    1434                 :            :              I have been unable to find anything related to the shape of
    1435                 :            :              the CFG, the contents of the affected blocks, etc which would
    1436                 :            :              allow a more sensible test than what we're using below which
    1437                 :            :              merely avoids the optimization when parallelizing loops.  */
    1438                 :     429390 :           if (flag_tree_parallelize_loops > 1)
    1439                 :            :             {
    1440                 :        632 :               for (i = 1; i < path->length (); i++)
    1441                 :        223 :                 if (bb->loop_father == e2->src->loop_father
    1442                 :        223 :                     && loop_exits_from_bb_p (bb->loop_father,
    1443                 :        223 :                                              (*path)[i]->e->src)
    1444                 :        324 :                     && !loop_exit_edge_p (bb->loop_father, e2))
    1445                 :            :                   break;
    1446                 :            : 
    1447                 :        362 :               if (i != path->length ())
    1448                 :            :                 {
    1449                 :         88 :                   delete_jump_thread_path (path);
    1450                 :         88 :                   e->aux = NULL;
    1451                 :         88 :                   continue;
    1452                 :            :                 }
    1453                 :            :             }
    1454                 :            :         }
    1455                 :            : 
    1456                 :            :       /* Insert the outgoing edge into the hash table if it is not
    1457                 :            :          already in the hash table.  */
    1458                 :     554323 :       lookup_redirection_data (e, INSERT);
    1459                 :            : 
    1460                 :            :       /* When we have thread paths through a common joiner with different
    1461                 :            :          final destinations, then we may need corrections to deal with
    1462                 :            :          profile insanities.  See the big comment before compute_path_counts.  */
    1463                 :     554323 :       if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
    1464                 :            :         {
    1465                 :     131543 :           if (!last)
    1466                 :            :             last = e2;
    1467                 :      40413 :           else if (e2 != last)
    1468                 :      19189 :             local_info.need_profile_correction = true;
    1469                 :            :         }
    1470                 :            :     }
    1471                 :            : 
    1472                 :            :   /* We do not update dominance info.  */
    1473                 :    1494890 :   free_dominance_info (CDI_DOMINATORS);
    1474                 :            : 
    1475                 :            :   /* We know we only thread through the loop header to loop exits.
    1476                 :            :      Let the basic block duplication hook know we are not creating
    1477                 :            :      a multiple entry loop.  */
    1478                 :    1494890 :   if (noloop_only
    1479                 :    1244850 :       && bb == bb->loop_father->header)
    1480                 :    1435530 :     set_loop_copy (bb->loop_father, loop_outer (bb->loop_father));
    1481                 :            : 
    1482                 :            :   /* Now create duplicates of BB.
    1483                 :            : 
    1484                 :            :      Note that for a block with a high outgoing degree we can waste
    1485                 :            :      a lot of time and memory creating and destroying useless edges.
    1486                 :            : 
    1487                 :            :      So we first duplicate BB and remove the control structure at the
    1488                 :            :      tail of the duplicate as well as all outgoing edges from the
    1489                 :            :      duplicate.  We then use that duplicate block as a template for
    1490                 :            :      the rest of the duplicates.  */
    1491                 :    1494890 :   local_info.template_block = NULL;
    1492                 :    1494890 :   local_info.bb = bb;
    1493                 :    1494890 :   local_info.jumps_threaded = false;
    1494                 :    1494890 :   redirection_data->traverse <ssa_local_info_t *, ssa_create_duplicates>
    1495                 :    1494890 :                             (&local_info);
    1496                 :            : 
    1497                 :            :   /* The template does not have an outgoing edge.  Create that outgoing
    1498                 :            :      edge and update PHI nodes as the edge's target as necessary.
    1499                 :            : 
    1500                 :            :      We do this after creating all the duplicates to avoid creating
    1501                 :            :      unnecessary edges.  */
    1502                 :    1494890 :   redirection_data->traverse <ssa_local_info_t *, ssa_fixup_template_block>
    1503                 :    1494890 :                             (&local_info);
    1504                 :            : 
    1505                 :            :   /* The hash table traversals above created the duplicate blocks (and the
    1506                 :            :      statements within the duplicate blocks).  This loop creates PHI nodes for
    1507                 :            :      the duplicated blocks and redirects the incoming edges into BB to reach
    1508                 :            :      the duplicates of BB.  */
    1509                 :    1494890 :   redirection_data->traverse <ssa_local_info_t *, ssa_redirect_edges>
    1510                 :    1494890 :                             (&local_info);
    1511                 :            : 
    1512                 :            :   /* Done with this block.  Clear REDIRECTION_DATA.  */
    1513                 :    1494890 :   delete redirection_data;
    1514                 :    1494890 :   redirection_data = NULL;
    1515                 :            : 
    1516                 :    1494890 :   if (noloop_only
    1517                 :    1244850 :       && bb == bb->loop_father->header)
    1518                 :     717764 :     set_loop_copy (bb->loop_father, NULL);
    1519                 :            : 
    1520                 :    1494890 :   BITMAP_FREE (local_info.duplicate_blocks);
    1521                 :    1494890 :   local_info.duplicate_blocks = NULL;
    1522                 :            : 
    1523                 :            :   /* Indicate to our caller whether or not any jumps were threaded.  */
    1524                 :    1494890 :   return local_info.jumps_threaded;
    1525                 :            : }
    1526                 :            : 
    1527                 :            : /* Wrapper for thread_block_1 so that we can first handle jump
    1528                 :            :    thread paths which do not involve copying joiner blocks, then
    1529                 :            :    handle jump thread paths which have joiner blocks.
    1530                 :            : 
    1531                 :            :    By doing things this way we can be as aggressive as possible and
    1532                 :            :    not worry that copying a joiner block will create a jump threading
    1533                 :            :    opportunity.  */
    1534                 :            : 
    1535                 :            : static bool
    1536                 :     747447 : thread_block (basic_block bb, bool noloop_only)
    1537                 :            : {
    1538                 :     747447 :   bool retval;
    1539                 :     747447 :   retval = thread_block_1 (bb, noloop_only, false);
    1540                 :     747447 :   retval |= thread_block_1 (bb, noloop_only, true);
    1541                 :     747447 :   return retval;
    1542                 :            : }
    1543                 :            : 
    1544                 :            : /* Callback for dfs_enumerate_from.  Returns true if BB is different
    1545                 :            :    from STOP and DBDS_CE_STOP.  */
    1546                 :            : 
    1547                 :            : static basic_block dbds_ce_stop;
    1548                 :            : static bool
    1549                 :     819726 : dbds_continue_enumeration_p (const_basic_block bb, const void *stop)
    1550                 :            : {
    1551                 :     819726 :   return (bb != (const_basic_block) stop
    1552                 :     819726 :           && bb != dbds_ce_stop);
    1553                 :            : }
    1554                 :            : 
    1555                 :            : /* Evaluates the dominance relationship of latch of the LOOP and BB, and
    1556                 :            :    returns the state.  */
    1557                 :            : 
    1558                 :            : enum bb_dom_status
    1559                 :     173974 : determine_bb_domination_status (class loop *loop, basic_block bb)
    1560                 :            : {
    1561                 :     173974 :   basic_block *bblocks;
    1562                 :     173974 :   unsigned nblocks, i;
    1563                 :     173974 :   bool bb_reachable = false;
    1564                 :     173974 :   edge_iterator ei;
    1565                 :     173974 :   edge e;
    1566                 :            : 
    1567                 :            :   /* This function assumes BB is a successor of LOOP->header.
    1568                 :            :      If that is not the case return DOMST_NONDOMINATING which
    1569                 :            :      is always safe.  */
    1570                 :     173974 :     {
    1571                 :     173974 :       bool ok = false;
    1572                 :            : 
    1573                 :     276171 :       FOR_EACH_EDGE (e, ei, bb->preds)
    1574                 :            :         {
    1575                 :     245474 :           if (e->src == loop->header)
    1576                 :            :             {
    1577                 :            :               ok = true;
    1578                 :            :               break;
    1579                 :            :             }
    1580                 :            :         }
    1581                 :            : 
    1582                 :     173974 :       if (!ok)
    1583                 :            :         return DOMST_NONDOMINATING;
    1584                 :            :     }
    1585                 :            : 
    1586                 :     143277 :   if (bb == loop->latch)
    1587                 :            :     return DOMST_DOMINATING;
    1588                 :            : 
    1589                 :            :   /* Check that BB dominates LOOP->latch, and that it is back-reachable
    1590                 :            :      from it.  */
    1591                 :            : 
    1592                 :     102918 :   bblocks = XCNEWVEC (basic_block, loop->num_nodes);
    1593                 :     102918 :   dbds_ce_stop = loop->header;
    1594                 :     205836 :   nblocks = dfs_enumerate_from (loop->latch, 1, dbds_continue_enumeration_p,
    1595                 :     102918 :                                 bblocks, loop->num_nodes, bb);
    1596                 :     780374 :   for (i = 0; i < nblocks; i++)
    1597                 :    1598270 :     FOR_EACH_EDGE (e, ei, bblocks[i]->preds)
    1598                 :            :       {
    1599                 :     920817 :         if (e->src == loop->header)
    1600                 :            :           {
    1601                 :      15418 :             free (bblocks);
    1602                 :      15418 :             return DOMST_NONDOMINATING;
    1603                 :            :           }
    1604                 :     905399 :         if (e->src == bb)
    1605                 :     123907 :           bb_reachable = true;
    1606                 :            :       }
    1607                 :            : 
    1608                 :      87500 :   free (bblocks);
    1609                 :      87500 :   return (bb_reachable ? DOMST_DOMINATING : DOMST_LOOP_BROKEN);
    1610                 :            : }
    1611                 :            : 
    1612                 :            : /* Thread jumps through the header of LOOP.  Returns true if cfg changes.
    1613                 :            :    If MAY_PEEL_LOOP_HEADERS is false, we avoid threading from entry edges
    1614                 :            :    to the inside of the loop.  */
    1615                 :            : 
    1616                 :            : static bool
    1617                 :     358882 : thread_through_loop_header (class loop *loop, bool may_peel_loop_headers)
    1618                 :            : {
    1619                 :     358882 :   basic_block header = loop->header;
    1620                 :     358882 :   edge e, tgt_edge, latch = loop_latch_edge (loop);
    1621                 :     358882 :   edge_iterator ei;
    1622                 :     358882 :   basic_block tgt_bb, atgt_bb;
    1623                 :     358882 :   enum bb_dom_status domst;
    1624                 :            : 
    1625                 :            :   /* We have already threaded through headers to exits, so all the threading
    1626                 :            :      requests now are to the inside of the loop.  We need to avoid creating
    1627                 :            :      irreducible regions (i.e., loops with more than one entry block), and
    1628                 :            :      also loop with several latch edges, or new subloops of the loop (although
    1629                 :            :      there are cases where it might be appropriate, it is difficult to decide,
    1630                 :            :      and doing it wrongly may confuse other optimizers).
    1631                 :            : 
    1632                 :            :      We could handle more general cases here.  However, the intention is to
    1633                 :            :      preserve some information about the loop, which is impossible if its
    1634                 :            :      structure changes significantly, in a way that is not well understood.
    1635                 :            :      Thus we only handle few important special cases, in which also updating
    1636                 :            :      of the loop-carried information should be feasible:
    1637                 :            : 
    1638                 :            :      1) Propagation of latch edge to a block that dominates the latch block
    1639                 :            :         of a loop.  This aims to handle the following idiom:
    1640                 :            : 
    1641                 :            :         first = 1;
    1642                 :            :         while (1)
    1643                 :            :           {
    1644                 :            :             if (first)
    1645                 :            :               initialize;
    1646                 :            :             first = 0;
    1647                 :            :             body;
    1648                 :            :           }
    1649                 :            : 
    1650                 :            :         After threading the latch edge, this becomes
    1651                 :            : 
    1652                 :            :         first = 1;
    1653                 :            :         if (first)
    1654                 :            :           initialize;
    1655                 :            :         while (1)
    1656                 :            :           {
    1657                 :            :             first = 0;
    1658                 :            :             body;
    1659                 :            :           }
    1660                 :            : 
    1661                 :            :         The original header of the loop is moved out of it, and we may thread
    1662                 :            :         the remaining edges through it without further constraints.
    1663                 :            : 
    1664                 :            :      2) All entry edges are propagated to a single basic block that dominates
    1665                 :            :         the latch block of the loop.  This aims to handle the following idiom
    1666                 :            :         (normally created for "for" loops):
    1667                 :            : 
    1668                 :            :         i = 0;
    1669                 :            :         while (1)
    1670                 :            :           {
    1671                 :            :             if (i >= 100)
    1672                 :            :               break;
    1673                 :            :             body;
    1674                 :            :             i++;
    1675                 :            :           }
    1676                 :            : 
    1677                 :            :         This becomes
    1678                 :            : 
    1679                 :            :         i = 0;
    1680                 :            :         while (1)
    1681                 :            :           {
    1682                 :            :             body;
    1683                 :            :             i++;
    1684                 :            :             if (i >= 100)
    1685                 :            :               break;
    1686                 :            :           }
    1687                 :            :      */
    1688                 :            : 
    1689                 :            :   /* Threading through the header won't improve the code if the header has just
    1690                 :            :      one successor.  */
    1691                 :     358882 :   if (single_succ_p (header))
    1692                 :       1412 :     goto fail;
    1693                 :            : 
    1694                 :     357470 :   if (!may_peel_loop_headers && !redirection_block_p (loop->header))
    1695                 :     124749 :     goto fail;
    1696                 :            :   else
    1697                 :            :     {
    1698                 :     232721 :       tgt_bb = NULL;
    1699                 :     232721 :       tgt_edge = NULL;
    1700                 :     598708 :       FOR_EACH_EDGE (e, ei, header->preds)
    1701                 :            :         {
    1702                 :     419771 :           if (!e->aux)
    1703                 :            :             {
    1704                 :     196512 :               if (e == latch)
    1705                 :     186631 :                 continue;
    1706                 :            : 
    1707                 :            :               /* If latch is not threaded, and there is a header
    1708                 :            :                  edge that is not threaded, we would create loop
    1709                 :            :                  with multiple entries.  */
    1710                 :       9881 :               goto fail;
    1711                 :            :             }
    1712                 :            : 
    1713                 :     223259 :           vec<jump_thread_edge *> *path = THREAD_PATH (e);
    1714                 :            : 
    1715                 :     223259 :           if ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
    1716                 :      43903 :             goto fail;
    1717                 :     179356 :           tgt_edge = (*path)[1]->e;
    1718                 :     179356 :           atgt_bb = tgt_edge->dest;
    1719                 :     179356 :           if (!tgt_bb)
    1720                 :            :             tgt_bb = atgt_bb;
    1721                 :            :           /* Two targets of threading would make us create loop
    1722                 :            :              with multiple entries.  */
    1723                 :          0 :           else if (tgt_bb != atgt_bb)
    1724                 :          0 :             goto fail;
    1725                 :            :         }
    1726                 :            : 
    1727                 :     178937 :       if (!tgt_bb)
    1728                 :            :         {
    1729                 :            :           /* There are no threading requests.  */
    1730                 :            :           return false;
    1731                 :            :         }
    1732                 :            : 
    1733                 :            :       /* Redirecting to empty loop latch is useless.  */
    1734                 :     177809 :       if (tgt_bb == loop->latch
    1735                 :     177809 :           && empty_block_p (loop->latch))
    1736                 :      43005 :         goto fail;
    1737                 :            :     }
    1738                 :            : 
    1739                 :            :   /* The target block must dominate the loop latch, otherwise we would be
    1740                 :            :      creating a subloop.  */
    1741                 :     134804 :   domst = determine_bb_domination_status (loop, tgt_bb);
    1742                 :     134804 :   if (domst == DOMST_NONDOMINATING)
    1743                 :       9783 :     goto fail;
    1744                 :     125021 :   if (domst == DOMST_LOOP_BROKEN)
    1745                 :            :     {
    1746                 :            :       /* If the loop ceased to exist, mark it as such, and thread through its
    1747                 :            :          original header.  */
    1748                 :          7 :       mark_loop_for_removal (loop);
    1749                 :          7 :       return thread_block (header, false);
    1750                 :            :     }
    1751                 :            : 
    1752                 :     125014 :   if (tgt_bb->loop_father->header == tgt_bb)
    1753                 :            :     {
    1754                 :            :       /* If the target of the threading is a header of a subloop, we need
    1755                 :            :          to create a preheader for it, so that the headers of the two loops
    1756                 :            :          do not merge.  */
    1757                 :          0 :       if (EDGE_COUNT (tgt_bb->preds) > 2)
    1758                 :            :         {
    1759                 :          0 :           tgt_bb = create_preheader (tgt_bb->loop_father, 0);
    1760                 :          0 :           gcc_assert (tgt_bb != NULL);
    1761                 :            :         }
    1762                 :            :       else
    1763                 :          0 :         tgt_bb = split_edge (tgt_edge);
    1764                 :            :     }
    1765                 :            : 
    1766                 :     125014 :   basic_block new_preheader;
    1767                 :            : 
    1768                 :            :   /* Now consider the case entry edges are redirected to the new entry
    1769                 :            :      block.  Remember one entry edge, so that we can find the new
    1770                 :            :      preheader (its destination after threading).  */
    1771                 :     172010 :   FOR_EACH_EDGE (e, ei, header->preds)
    1772                 :            :     {
    1773                 :     172010 :       if (e->aux)
    1774                 :            :         break;
    1775                 :            :     }
    1776                 :            : 
    1777                 :            :   /* The duplicate of the header is the new preheader of the loop.  Ensure
    1778                 :            :      that it is placed correctly in the loop hierarchy.  */
    1779                 :     250028 :   set_loop_copy (loop, loop_outer (loop));
    1780                 :            : 
    1781                 :     125014 :   thread_block (header, false);
    1782                 :     125014 :   set_loop_copy (loop, NULL);
    1783                 :     125014 :   new_preheader = e->dest;
    1784                 :            : 
    1785                 :            :   /* Create the new latch block.  This is always necessary, as the latch
    1786                 :            :      must have only a single successor, but the original header had at
    1787                 :            :      least two successors.  */
    1788                 :     125014 :   loop->latch = NULL;
    1789                 :     125014 :   mfb_kj_edge = single_succ_edge (new_preheader);
    1790                 :     125014 :   loop->header = mfb_kj_edge->dest;
    1791                 :     125014 :   latch = make_forwarder_block (tgt_bb, mfb_keep_just, NULL);
    1792                 :     125014 :   loop->header = latch->dest;
    1793                 :     125014 :   loop->latch = latch->src;
    1794                 :     125014 :   return true;
    1795                 :            : 
    1796                 :     232733 : fail:
    1797                 :            :   /* We failed to thread anything.  Cancel the requests.  */
    1798                 :     700283 :   FOR_EACH_EDGE (e, ei, header->preds)
    1799                 :            :     {
    1800                 :     467550 :       vec<jump_thread_edge *> *path = THREAD_PATH (e);
    1801                 :            : 
    1802                 :     467550 :       if (path)
    1803                 :            :         {
    1804                 :     216854 :           delete_jump_thread_path (path);
    1805                 :     216854 :           e->aux = NULL;
    1806                 :            :         }
    1807                 :            :     }
    1808                 :            :   return false;
    1809                 :            : }
    1810                 :            : 
    1811                 :            : /* E1 and E2 are edges into the same basic block.  Return TRUE if the
    1812                 :            :    PHI arguments associated with those edges are equal or there are no
    1813                 :            :    PHI arguments, otherwise return FALSE.  */
    1814                 :            : 
    1815                 :            : static bool
    1816                 :      70228 : phi_args_equal_on_edges (edge e1, edge e2)
    1817                 :            : {
    1818                 :      70228 :   gphi_iterator gsi;
    1819                 :      70228 :   int indx1 = e1->dest_idx;
    1820                 :      70228 :   int indx2 = e2->dest_idx;
    1821                 :            : 
    1822                 :     105893 :   for (gsi = gsi_start_phis (e1->dest); !gsi_end_p (gsi); gsi_next (&gsi))
    1823                 :            :     {
    1824                 :      37937 :       gphi *phi = gsi.phi ();
    1825                 :            : 
    1826                 :      37937 :       if (!operand_equal_p (gimple_phi_arg_def (phi, indx1),
    1827                 :      37937 :                             gimple_phi_arg_def (phi, indx2), 0))
    1828                 :            :         return false;
    1829                 :            :     }
    1830                 :            :   return true;
    1831                 :            : }
    1832                 :            : 
    1833                 :            : /* Return the number of non-debug statements and non-virtual PHIs in a
    1834                 :            :    block.  */
    1835                 :            : 
    1836                 :            : static unsigned int
    1837                 :      14729 : count_stmts_and_phis_in_block (basic_block bb)
    1838                 :            : {
    1839                 :      14729 :   unsigned int num_stmts = 0;
    1840                 :            : 
    1841                 :      14729 :   gphi_iterator gpi;
    1842                 :      41114 :   for (gpi = gsi_start_phis (bb); !gsi_end_p (gpi); gsi_next (&gpi))
    1843                 :      52770 :     if (!virtual_operand_p (PHI_RESULT (gpi.phi ())))
    1844                 :      16924 :       num_stmts++;
    1845                 :            : 
    1846                 :      14729 :   gimple_stmt_iterator gsi;
    1847                 :     106981 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1848                 :            :     {
    1849                 :      77523 :       gimple *stmt = gsi_stmt (gsi);
    1850                 :      77523 :       if (!is_gimple_debug (stmt))
    1851                 :      76264 :         num_stmts++;
    1852                 :            :     }
    1853                 :            : 
    1854                 :      14729 :   return num_stmts;
    1855                 :            : }
    1856                 :            : 
    1857                 :            : 
    1858                 :            : /* Walk through the registered jump threads and convert them into a
    1859                 :            :    form convenient for this pass.
    1860                 :            : 
    1861                 :            :    Any block which has incoming edges threaded to outgoing edges
    1862                 :            :    will have its entry in THREADED_BLOCK set.
    1863                 :            : 
    1864                 :            :    Any threaded edge will have its new outgoing edge stored in the
    1865                 :            :    original edge's AUX field.
    1866                 :            : 
    1867                 :            :    This form avoids the need to walk all the edges in the CFG to
    1868                 :            :    discover blocks which need processing and avoids unnecessary
    1869                 :            :    hash table lookups to map from threaded edge to new target.  */
    1870                 :            : 
    1871                 :            : static void
    1872                 :     347277 : mark_threaded_blocks (bitmap threaded_blocks)
    1873                 :            : {
    1874                 :     347277 :   unsigned int i;
    1875                 :     347277 :   bitmap_iterator bi;
    1876                 :     347277 :   auto_bitmap tmp;
    1877                 :     347277 :   basic_block bb;
    1878                 :     347277 :   edge e;
    1879                 :     347277 :   edge_iterator ei;
    1880                 :            : 
    1881                 :            :   /* It is possible to have jump threads in which one is a subpath
    1882                 :            :      of the other.  ie, (A, B), (B, C), (C, D) where B is a joiner
    1883                 :            :      block and (B, C), (C, D) where no joiner block exists.
    1884                 :            : 
    1885                 :            :      When this occurs ignore the jump thread request with the joiner
    1886                 :            :      block.  It's totally subsumed by the simpler jump thread request.
    1887                 :            : 
    1888                 :            :      This results in less block copying, simpler CFGs.  More importantly,
    1889                 :            :      when we duplicate the joiner block, B, in this case we will create
    1890                 :            :      a new threading opportunity that we wouldn't be able to optimize
    1891                 :            :      until the next jump threading iteration.
    1892                 :            : 
    1893                 :            :      So first convert the jump thread requests which do not require a
    1894                 :            :      joiner block.  */
    1895                 :    2712480 :   for (i = 0; i < paths.length (); i++)
    1896                 :            :     {
    1897                 :    1008960 :       vec<jump_thread_edge *> *path = paths[i];
    1898                 :            : 
    1899                 :    1008960 :       if (path->length () > 1
    1900                 :    1008960 :           && (*path)[1]->type != EDGE_COPY_SRC_JOINER_BLOCK)
    1901                 :            :         {
    1902                 :     556060 :           edge e = (*path)[0]->e;
    1903                 :     556060 :           e->aux = (void *)path;
    1904                 :     556060 :           bitmap_set_bit (tmp, e->dest->index);
    1905                 :            :         }
    1906                 :            :     }
    1907                 :            : 
    1908                 :            :   /* Now iterate again, converting cases where we want to thread
    1909                 :            :      through a joiner block, but only if no other edge on the path
    1910                 :            :      already has a jump thread attached to it.  We do this in two passes,
    1911                 :            :      to avoid situations where the order in the paths vec can hide overlapping
    1912                 :            :      threads (the path is recorded on the incoming edge, so we would miss
    1913                 :            :      cases where the second path starts at a downstream edge on the same
    1914                 :            :      path).  First record all joiner paths, deleting any in the unexpected
    1915                 :            :      case where there is already a path for that incoming edge.  */
    1916                 :    2712480 :   for (i = 0; i < paths.length ();)
    1917                 :            :     {
    1918                 :    1008960 :       vec<jump_thread_edge *> *path = paths[i];
    1919                 :            : 
    1920                 :    1008960 :       if (path->length () > 1
    1921                 :    1008960 :           && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK)
    1922                 :            :         {
    1923                 :            :           /* Attach the path to the starting edge if none is yet recorded.  */
    1924                 :     450854 :           if ((*path)[0]->e->aux == NULL)
    1925                 :            :             {
    1926                 :     364981 :               (*path)[0]->e->aux = path;
    1927                 :     364981 :               i++;
    1928                 :            :             }
    1929                 :            :           else
    1930                 :            :             {
    1931                 :      85873 :               paths.unordered_remove (i);
    1932                 :      85873 :               if (dump_file && (dump_flags & TDF_DETAILS))
    1933                 :          0 :                 dump_jump_thread_path (dump_file, *path, false);
    1934                 :      85873 :               delete_jump_thread_path (path);
    1935                 :            :             }
    1936                 :            :         }
    1937                 :            :       else
    1938                 :            :         {
    1939                 :     558111 :           i++;
    1940                 :            :         }
    1941                 :            :     }
    1942                 :            : 
    1943                 :            :   /* Second, look for paths that have any other jump thread attached to
    1944                 :            :      them, and either finish converting them or cancel them.  */
    1945                 :    2540740 :   for (i = 0; i < paths.length ();)
    1946                 :            :     {
    1947                 :     923092 :       vec<jump_thread_edge *> *path = paths[i];
    1948                 :     923092 :       edge e = (*path)[0]->e;
    1949                 :            : 
    1950                 :     923092 :       if (path->length () > 1
    1951                 :     923092 :           && (*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK && e->aux == path)
    1952                 :            :         {
    1953                 :            :           unsigned int j;
    1954                 :     898608 :           for (j = 1; j < path->length (); j++)
    1955                 :     617687 :             if ((*path)[j]->e->aux != NULL)
    1956                 :            :               break;
    1957                 :            : 
    1958                 :            :           /* If we iterated through the entire path without exiting the loop,
    1959                 :            :              then we are good to go, record it.  */
    1960                 :     364981 :           if (j == path->length ())
    1961                 :            :             {
    1962                 :     280921 :               bitmap_set_bit (tmp, e->dest->index);
    1963                 :     280921 :               i++;
    1964                 :            :             }
    1965                 :            :           else
    1966                 :            :             {
    1967                 :      84060 :               e->aux = NULL;
    1968                 :      84060 :               paths.unordered_remove (i);
    1969                 :      84060 :               if (dump_file && (dump_flags & TDF_DETAILS))
    1970                 :         12 :                 dump_jump_thread_path (dump_file, *path, false);
    1971                 :      84060 :               delete_jump_thread_path (path);
    1972                 :            :             }
    1973                 :            :         }
    1974                 :            :       else
    1975                 :            :         {
    1976                 :     558111 :           i++;
    1977                 :            :         }
    1978                 :            :     }
    1979                 :            : 
    1980                 :            :   /* When optimizing for size, prune all thread paths where statement
    1981                 :            :      duplication is necessary.
    1982                 :            : 
    1983                 :            :      We walk the jump thread path looking for copied blocks.  There's
    1984                 :            :      two types of copied blocks.
    1985                 :            : 
    1986                 :            :        EDGE_COPY_SRC_JOINER_BLOCK is always copied and thus we will
    1987                 :            :        cancel the jump threading request when optimizing for size.
    1988                 :            : 
    1989                 :            :        EDGE_COPY_SRC_BLOCK which is copied, but some of its statements
    1990                 :            :        will be killed by threading.  If threading does not kill all of
    1991                 :            :        its statements, then we should cancel the jump threading request
    1992                 :            :        when optimizing for size.  */
    1993                 :     347277 :   if (optimize_function_for_size_p (cfun))
    1994                 :            :     {
    1995                 :      47594 :       EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
    1996                 :            :         {
    1997                 :     105583 :           FOR_EACH_EDGE (e, ei, BASIC_BLOCK_FOR_FN (cfun, i)->preds)
    1998                 :      70984 :             if (e->aux)
    1999                 :            :               {
    2000                 :      61322 :                 vec<jump_thread_edge *> *path = THREAD_PATH (e);
    2001                 :            : 
    2002                 :            :                 unsigned int j;
    2003                 :     122644 :                 for (j = 1; j < path->length (); j++)
    2004                 :            :                   {
    2005                 :      43028 :                     bb = (*path)[j]->e->src;
    2006                 :      43028 :                     if (redirection_block_p (bb))
    2007                 :            :                       ;
    2008                 :      23027 :                     else if ((*path)[j]->type == EDGE_COPY_SRC_JOINER_BLOCK
    2009                 :      23027 :                              || ((*path)[j]->type == EDGE_COPY_SRC_BLOCK
    2010                 :      29458 :                                  && (count_stmts_and_phis_in_block (bb)
    2011                 :      14729 :                                      != estimate_threading_killed_stmts (bb))))
    2012                 :            :                       break;
    2013                 :            :                   }
    2014                 :            : 
    2015                 :      80872 :                 if (j != path->length ())
    2016                 :            :                   {
    2017                 :      22142 :                     if (dump_file && (dump_flags & TDF_DETAILS))
    2018                 :          0 :                       dump_jump_thread_path (dump_file, *path, 0);
    2019                 :      22142 :                     delete_jump_thread_path (path);
    2020                 :      22142 :                     e->aux = NULL;
    2021                 :            :                   }
    2022                 :            :                 else
    2023                 :      18294 :                   bitmap_set_bit (threaded_blocks, i);
    2024                 :            :               }
    2025                 :            :         }
    2026                 :            :     }
    2027                 :            :   else
    2028                 :     334282 :     bitmap_copy (threaded_blocks, tmp);
    2029                 :            : 
    2030                 :            :   /* If we have a joiner block (J) which has two successors S1 and S2 and
    2031                 :            :      we are threading though S1 and the final destination of the thread
    2032                 :            :      is S2, then we must verify that any PHI nodes in S2 have the same
    2033                 :            :      PHI arguments for the edge J->S2 and J->S1->...->S2.
    2034                 :            : 
    2035                 :            :      We used to detect this prior to registering the jump thread, but
    2036                 :            :      that prohibits propagation of edge equivalences into non-dominated
    2037                 :            :      PHI nodes as the equivalency test might occur before propagation.
    2038                 :            : 
    2039                 :            :      This must also occur after we truncate any jump threading paths
    2040                 :            :      as this scenario may only show up after truncation.
    2041                 :            : 
    2042                 :            :      This works for now, but will need improvement as part of the FSA
    2043                 :            :      optimization.
    2044                 :            : 
    2045                 :            :      Note since we've moved the thread request data to the edges,
    2046                 :            :      we have to iterate on those rather than the threaded_edges vector.  */
    2047                 :     989513 :   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
    2048                 :            :     {
    2049                 :     642236 :       bb = BASIC_BLOCK_FOR_FN (cfun, i);
    2050                 :    2044880 :       FOR_EACH_EDGE (e, ei, bb->preds)
    2051                 :            :         {
    2052                 :    1402640 :           if (e->aux)
    2053                 :            :             {
    2054                 :     814839 :               vec<jump_thread_edge *> *path = THREAD_PATH (e);
    2055                 :     814839 :               bool have_joiner = ((*path)[1]->type == EDGE_COPY_SRC_JOINER_BLOCK);
    2056                 :            : 
    2057                 :     814839 :               if (have_joiner)
    2058                 :            :                 {
    2059                 :     271854 :                   basic_block joiner = e->dest;
    2060                 :     271854 :                   edge final_edge = path->last ()->e;
    2061                 :     271854 :                   basic_block final_dest = final_edge->dest;
    2062                 :     271854 :                   edge e2 = find_edge (joiner, final_dest);
    2063                 :            : 
    2064                 :     271854 :                   if (e2 && !phi_args_equal_on_edges (e2, final_edge))
    2065                 :            :                     {
    2066                 :       2272 :                       delete_jump_thread_path (path);
    2067                 :       2272 :                       e->aux = NULL;
    2068                 :            :                     }
    2069                 :            :                 }
    2070                 :            :             }
    2071                 :            :         }
    2072                 :            :     }
    2073                 :            : 
    2074                 :            :   /* Look for jump threading paths which cross multiple loop headers.
    2075                 :            : 
    2076                 :            :      The code to thread through loop headers will change the CFG in ways
    2077                 :            :      that invalidate the cached loop iteration information.  So we must
    2078                 :            :      detect that case and wipe the cached information.  */
    2079                 :     989513 :   EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi)
    2080                 :            :     {
    2081                 :     642236 :       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
    2082                 :    2044880 :       FOR_EACH_EDGE (e, ei, bb->preds)
    2083                 :            :         {
    2084                 :    1402640 :           if (e->aux)
    2085                 :            :             {
    2086                 :    2674990 :               vec<jump_thread_edge *> *path = THREAD_PATH (e);
    2087                 :            : 
    2088                 :    1862420 :               for (unsigned int i = 0, crossed_headers = 0;
    2089                 :    5349980 :                    i < path->length ();
    2090                 :            :                    i++)
    2091                 :            :                 {
    2092                 :    1867740 :                   basic_block dest = (*path)[i]->e->dest;
    2093                 :    1867740 :                   basic_block src = (*path)[i]->e->src;
    2094                 :            :                   /* If we enter a loop.  */
    2095                 :    1867740 :                   if (flow_loop_nested_p (src->loop_father, dest->loop_father))
    2096                 :     385684 :                     ++crossed_headers;
    2097                 :            :                   /* If we step from a block outside an irreducible region
    2098                 :            :                      to a block inside an irreducible region, then we have
    2099                 :            :                      crossed into a loop.  */
    2100                 :    1482060 :                   else if (! (src->flags & BB_IRREDUCIBLE_LOOP)
    2101                 :    1471180 :                            && (dest->flags & BB_IRREDUCIBLE_LOOP))
    2102                 :       1246 :                       ++crossed_headers;
    2103                 :    1867740 :                   if (crossed_headers > 1)
    2104                 :            :                     {
    2105                 :       5324 :                       vect_free_loop_info_assumptions
    2106                 :      10648 :                         ((*path)[path->length () - 1]->e->dest->loop_father);
    2107                 :       5324 :                       break;
    2108                 :            :                     }
    2109                 :            :                 }
    2110                 :            :             }
    2111                 :            :         }
    2112                 :            :     }
    2113                 :     347277 : }
    2114                 :            : 
    2115                 :            : 
    2116                 :            : /* Verify that the REGION is a valid jump thread.  A jump thread is a special
    2117                 :            :    case of SEME Single Entry Multiple Exits region in which all nodes in the
    2118                 :            :    REGION have exactly one incoming edge.  The only exception is the first block
    2119                 :            :    that may not have been connected to the rest of the cfg yet.  */
    2120                 :            : 
    2121                 :            : DEBUG_FUNCTION void
    2122                 :     293501 : verify_jump_thread (basic_block *region, unsigned n_region)
    2123                 :            : {
    2124                 :     646135 :   for (unsigned i = 0; i < n_region; i++)
    2125                 :     352634 :     gcc_assert (EDGE_COUNT (region[i]->preds) <= 1);
    2126                 :     293501 : }
    2127                 :            : 
    2128                 :            : /* Return true when BB is one of the first N items in BBS.  */
    2129                 :            : 
    2130                 :            : static inline bool
    2131                 :     590963 : bb_in_bbs (basic_block bb, basic_block *bbs, int n)
    2132                 :            : {
    2133                 :    1306400 :   for (int i = 0; i < n; i++)
    2134                 :     716199 :     if (bb == bbs[i])
    2135                 :            :       return true;
    2136                 :            : 
    2137                 :            :   return false;
    2138                 :            : }
    2139                 :            : 
    2140                 :            : DEBUG_FUNCTION void
    2141                 :        132 : debug_path (FILE *dump_file, int pathno)
    2142                 :            : {
    2143                 :        132 :   vec<jump_thread_edge *> *p = paths[pathno];
    2144                 :        132 :   fprintf (dump_file, "path: ");
    2145                 :       1332 :   for (unsigned i = 0; i < p->length (); ++i)
    2146                 :       1068 :     fprintf (dump_file, "%d -> %d, ",
    2147                 :        534 :              (*p)[i]->e->src->index, (*p)[i]->e->dest->index);
    2148                 :        132 :   fprintf (dump_file, "\n");
    2149                 :        132 : }
    2150                 :            : 
    2151                 :            : DEBUG_FUNCTION void
    2152                 :          0 : debug_all_paths ()
    2153                 :            : {
    2154                 :          0 :   for (unsigned i = 0; i < paths.length (); ++i)
    2155                 :          0 :     debug_path (stderr, i);
    2156                 :          0 : }
    2157                 :            : 
    2158                 :            : /* Rewire a jump_thread_edge so that the source block is now a
    2159                 :            :    threaded source block.
    2160                 :            : 
    2161                 :            :    PATH_NUM is an index into the global path table PATHS.
    2162                 :            :    EDGE_NUM is the jump thread edge number into said path.
    2163                 :            : 
    2164                 :            :    Returns TRUE if we were able to successfully rewire the edge.  */
    2165                 :            : 
    2166                 :            : static bool
    2167                 :      13081 : rewire_first_differing_edge (unsigned path_num, unsigned edge_num)
    2168                 :            : {
    2169                 :      13081 :   vec<jump_thread_edge *> *path = paths[path_num];
    2170                 :      13081 :   edge &e = (*path)[edge_num]->e;
    2171                 :      13081 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2172                 :         12 :     fprintf (dump_file, "rewiring edge candidate: %d -> %d\n",
    2173                 :         12 :              e->src->index, e->dest->index);
    2174                 :      13081 :   basic_block src_copy = get_bb_copy (e->src);
    2175                 :      13081 :   if (src_copy == NULL)
    2176                 :            :     {
    2177                 :       4533 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2178                 :          6 :         fprintf (dump_file, "ignoring candidate: there is no src COPY\n");
    2179                 :       4533 :       return false;
    2180                 :            :     }
    2181                 :       8548 :   edge new_edge = find_edge (src_copy, e->dest);
    2182                 :            :   /* If the previously threaded paths created a flow graph where we
    2183                 :            :      can no longer figure out where to go, give up.  */
    2184                 :       8548 :   if (new_edge == NULL)
    2185                 :            :     {
    2186                 :       2424 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2187                 :          6 :         fprintf (dump_file, "ignoring candidate: we lost our way\n");
    2188                 :       2424 :       return false;
    2189                 :            :     }
    2190                 :       6124 :   e = new_edge;
    2191                 :       6124 :   return true;
    2192                 :            : }
    2193                 :            : 
    2194                 :            : /* After an FSM path has been jump threaded, adjust the remaining FSM
    2195                 :            :    paths that are subsets of this path, so these paths can be safely
    2196                 :            :    threaded within the context of the new threaded path.
    2197                 :            : 
    2198                 :            :    For example, suppose we have just threaded:
    2199                 :            : 
    2200                 :            :    5 -> 6 -> 7 -> 8 -> 12   =>   5 -> 6' -> 7' -> 8' -> 12'
    2201                 :            : 
    2202                 :            :    And we have an upcoming threading candidate:
    2203                 :            :    5 -> 6 -> 7 -> 8 -> 15 -> 20
    2204                 :            : 
    2205                 :            :    This function adjusts the upcoming path into:
    2206                 :            :    8' -> 15 -> 20
    2207                 :            : 
    2208                 :            :    CURR_PATH_NUM is an index into the global paths table.  It
    2209                 :            :    specifies the path that was just threaded.  */
    2210                 :            : 
    2211                 :            : static void
    2212                 :     293510 : adjust_paths_after_duplication (unsigned curr_path_num)
    2213                 :            : {
    2214                 :     293510 :   vec<jump_thread_edge *> *curr_path = paths[curr_path_num];
    2215                 :     293510 :   gcc_assert ((*curr_path)[0]->type == EDGE_FSM_THREAD);
    2216                 :            : 
    2217                 :     293510 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2218                 :            :     {
    2219                 :         60 :       fprintf (dump_file, "just threaded: ");
    2220                 :         60 :       debug_path (dump_file, curr_path_num);
    2221                 :            :     }
    2222                 :            : 
    2223                 :            :   /* Iterate through all the other paths and adjust them.  */
    2224                 :   10223300 :   for (unsigned cand_path_num = 0; cand_path_num < paths.length (); )
    2225                 :            :     {
    2226                 :    4818150 :       if (cand_path_num == curr_path_num)
    2227                 :            :         {
    2228                 :     293510 :           ++cand_path_num;
    2229                 :     293510 :           continue;
    2230                 :            :         }
    2231                 :            :       /* Make sure the candidate to adjust starts with the same path
    2232                 :            :          as the recently threaded path and is an FSM thread.  */
    2233                 :    4524640 :       vec<jump_thread_edge *> *cand_path = paths[cand_path_num];
    2234                 :    4524640 :       if ((*cand_path)[0]->type != EDGE_FSM_THREAD
    2235                 :    4524640 :           || (*cand_path)[0]->e != (*curr_path)[0]->e)
    2236                 :            :         {
    2237                 :    4506210 :           ++cand_path_num;
    2238                 :    4506210 :           continue;
    2239                 :            :         }
    2240                 :      18424 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2241                 :            :         {
    2242                 :         12 :           fprintf (dump_file, "adjusting candidate: ");
    2243                 :         12 :           debug_path (dump_file, cand_path_num);
    2244                 :            :         }
    2245                 :            : 
    2246                 :            :       /* Chop off from the candidate path any prefix it shares with
    2247                 :            :          the recently threaded path.  */
    2248                 :      55272 :       unsigned minlength = MIN (curr_path->length (), cand_path->length ());
    2249                 :      18424 :       unsigned j;
    2250                 :      52312 :       for (j = 0; j < minlength; ++j)
    2251                 :            :         {
    2252                 :      42436 :           edge cand_edge = (*cand_path)[j]->e;
    2253                 :      42436 :           edge curr_edge = (*curr_path)[j]->e;
    2254                 :            : 
    2255                 :            :           /* Once the prefix no longer matches, adjust the first
    2256                 :            :              non-matching edge to point from an adjusted edge to
    2257                 :            :              wherever it was going.  */
    2258                 :      42436 :           if (cand_edge != curr_edge)
    2259                 :            :             {
    2260                 :       8548 :               gcc_assert (cand_edge->src == curr_edge->src);
    2261                 :       8548 :               if (!rewire_first_differing_edge (cand_path_num, j))
    2262                 :       2424 :                 goto remove_candidate_from_list;
    2263                 :            :               break;
    2264                 :            :             }
    2265                 :            :         }
    2266                 :      16000 :       if (j == minlength)
    2267                 :            :         {
    2268                 :            :           /* If we consumed the max subgraph we could look at, and
    2269                 :            :              still didn't find any different edges, it's the
    2270                 :            :              last edge after MINLENGTH.  */
    2271                 :      19752 :           if (cand_path->length () > minlength)
    2272                 :            :             {
    2273                 :       4533 :               if (!rewire_first_differing_edge (cand_path_num, j))
    2274                 :       4533 :                 goto remove_candidate_from_list;
    2275                 :            :             }
    2276                 :       5343 :           else if (dump_file && (dump_flags & TDF_DETAILS))
    2277                 :          0 :             fprintf (dump_file, "adjusting first edge after MINLENGTH.\n");
    2278                 :            :         }
    2279                 :      11467 :       if (j > 0)
    2280                 :            :         {
    2281                 :            :           /* If we are removing everything, delete the entire candidate.  */
    2282                 :      22934 :           if (j == cand_path->length ())
    2283                 :            :             {
    2284                 :       5343 :             remove_candidate_from_list:
    2285                 :      12300 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2286                 :         12 :                 fprintf (dump_file, "adjusted candidate: [EMPTY]\n");
    2287                 :      12300 :               delete_jump_thread_path (cand_path);
    2288                 :      12300 :               paths.unordered_remove (cand_path_num);
    2289                 :      12300 :               continue;
    2290                 :            :             }
    2291                 :            :           /* Otherwise, just remove the redundant sub-path.  */
    2292                 :       6124 :           cand_path->block_remove (0, j);
    2293                 :            :         }
    2294                 :       6124 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2295                 :            :         {
    2296                 :          0 :           fprintf (dump_file, "adjusted candidate: ");
    2297                 :          0 :           debug_path (dump_file, cand_path_num);
    2298                 :            :         }
    2299                 :       6124 :       ++cand_path_num;
    2300                 :            :     }
    2301                 :     293510 : }
    2302                 :            : 
    2303                 :            : /* Duplicates a jump-thread path of N_REGION basic blocks.
    2304                 :            :    The ENTRY edge is redirected to the duplicate of the region.
    2305                 :            : 
    2306                 :            :    Remove the last conditional statement in the last basic block in the REGION,
    2307                 :            :    and create a single fallthru edge pointing to the same destination as the
    2308                 :            :    EXIT edge.
    2309                 :            : 
    2310                 :            :    CURRENT_PATH_NO is an index into the global paths[] table
    2311                 :            :    specifying the jump-thread path.
    2312                 :            : 
    2313                 :            :    Returns false if it is unable to copy the region, true otherwise.  */
    2314                 :            : 
    2315                 :            : static bool
    2316                 :     293510 : duplicate_thread_path (edge entry, edge exit, basic_block *region,
    2317                 :            :                        unsigned n_region, unsigned current_path_no)
    2318                 :            : {
    2319                 :     293510 :   unsigned i;
    2320                 :     293510 :   class loop *loop = entry->dest->loop_father;
    2321                 :     293510 :   edge exit_copy;
    2322                 :     293510 :   edge redirected;
    2323                 :     293510 :   profile_count curr_count;
    2324                 :            : 
    2325                 :     293510 :   if (!can_copy_bbs_p (region, n_region))
    2326                 :            :     return false;
    2327                 :            : 
    2328                 :     293510 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2329                 :            :     {
    2330                 :         60 :       fprintf (dump_file, "\nabout to thread: ");
    2331                 :         60 :       debug_path (dump_file, current_path_no);
    2332                 :            :     }
    2333                 :            : 
    2334                 :            :   /* Some sanity checking.  Note that we do not check for all possible
    2335                 :            :      missuses of the functions.  I.e. if you ask to copy something weird,
    2336                 :            :      it will work, but the state of structures probably will not be
    2337                 :            :      correct.  */
    2338                 :     646161 :   for (i = 0; i < n_region; i++)
    2339                 :            :     {
    2340                 :            :       /* We do not handle subloops, i.e. all the blocks must belong to the
    2341                 :            :          same loop.  */
    2342                 :     352651 :       if (region[i]->loop_father != loop)
    2343                 :            :         return false;
    2344                 :            :     }
    2345                 :            : 
    2346                 :     293510 :   initialize_original_copy_tables ();
    2347                 :            : 
    2348                 :     293510 :   set_loop_copy (loop, loop);
    2349                 :            : 
    2350                 :     293510 :   basic_block *region_copy = XNEWVEC (basic_block, n_region);
    2351                 :     293510 :   copy_bbs (region, n_region, region_copy, &exit, 1, &exit_copy, loop,
    2352                 :            :             split_edge_bb_loc (entry), false);
    2353                 :            : 
    2354                 :            :   /* Fix up: copy_bbs redirects all edges pointing to copied blocks.  The
    2355                 :            :      following code ensures that all the edges exiting the jump-thread path are
    2356                 :            :      redirected back to the original code: these edges are exceptions
    2357                 :            :      invalidating the property that is propagated by executing all the blocks of
    2358                 :            :      the jump-thread path in order.  */
    2359                 :            : 
    2360                 :     293510 :   curr_count = entry->count ();
    2361                 :            : 
    2362                 :     646161 :   for (i = 0; i < n_region; i++)
    2363                 :            :     {
    2364                 :     352651 :       edge e;
    2365                 :     352651 :       edge_iterator ei;
    2366                 :     352651 :       basic_block bb = region_copy[i];
    2367                 :            : 
    2368                 :            :       /* Watch inconsistent profile.  */
    2369                 :     352651 :       if (curr_count > region[i]->count)
    2370                 :      12001 :         curr_count = region[i]->count;
    2371                 :            :       /* Scale current BB.  */
    2372                 :     525708 :       if (region[i]->count.nonzero_p () && curr_count.initialized_p ())
    2373                 :            :         {
    2374                 :            :           /* In the middle of the path we only scale the frequencies.
    2375                 :            :              In last BB we need to update probabilities of outgoing edges
    2376                 :            :              because we know which one is taken at the threaded path.  */
    2377                 :     170644 :           if (i + 1 != n_region)
    2378                 :      37457 :             scale_bbs_frequencies_profile_count (region + i, 1,
    2379                 :            :                                                  region[i]->count - curr_count,
    2380                 :            :                                                  region[i]->count);
    2381                 :            :           else
    2382                 :     133187 :             update_bb_profile_for_threading (region[i],
    2383                 :            :                                              curr_count,
    2384                 :            :                                              exit);
    2385                 :     170644 :           scale_bbs_frequencies_profile_count (region_copy + i, 1, curr_count,
    2386                 :     170644 :                                                region_copy[i]->count);
    2387                 :            :         }
    2388                 :            : 
    2389                 :     352651 :       if (single_succ_p (bb))
    2390                 :            :         {
    2391                 :            :           /* Make sure the successor is the next node in the path.  */
    2392                 :      30049 :           gcc_assert (i + 1 == n_region
    2393                 :            :                       || region_copy[i + 1] == single_succ_edge (bb)->dest);
    2394                 :      30049 :           if (i + 1 != n_region)
    2395                 :            :             {
    2396                 :      30049 :               curr_count = single_succ_edge (bb)->count ();
    2397                 :            :             }
    2398                 :     323559 :           continue;
    2399                 :            :         }
    2400                 :            : 
    2401                 :            :       /* Special case the last block on the path: make sure that it does not
    2402                 :            :          jump back on the copied path, including back to itself.  */
    2403                 :     322602 :       if (i + 1 == n_region)
    2404                 :            :         {
    2405                 :     884473 :           FOR_EACH_EDGE (e, ei, bb->succs)
    2406                 :    1181930 :             if (bb_in_bbs (e->dest, region_copy, n_region))
    2407                 :            :               {
    2408                 :        763 :                 basic_block orig = get_bb_original (e->dest);
    2409                 :        763 :                 if (orig)
    2410                 :        763 :                   redirect_edge_and_branch_force (e, orig);
    2411                 :            :               }
    2412                 :     293510 :           continue;
    2413                 :            :         }
    2414                 :            : 
    2415                 :            :       /* Redirect all other edges jumping to non-adjacent blocks back to the
    2416                 :            :          original code.  */
    2417                 :      87276 :       FOR_EACH_EDGE (e, ei, bb->succs)
    2418                 :      58184 :         if (region_copy[i + 1] != e->dest)
    2419                 :            :           {
    2420                 :      29092 :             basic_block orig = get_bb_original (e->dest);
    2421                 :      29092 :             if (orig)
    2422                 :        519 :               redirect_edge_and_branch_force (e, orig);
    2423                 :            :           }
    2424                 :            :         else
    2425                 :            :           {
    2426                 :      29092 :             curr_count = e->count ();
    2427                 :            :           }
    2428                 :            :     }
    2429                 :            : 
    2430                 :            : 
    2431                 :     293510 :   if (flag_checking)
    2432                 :     293501 :     verify_jump_thread (region_copy, n_region);
    2433                 :            : 
    2434                 :            :   /* Remove the last branch in the jump thread path.  */
    2435                 :     293510 :   remove_ctrl_stmt_and_useless_edges (region_copy[n_region - 1], exit->dest);
    2436                 :            : 
    2437                 :            :   /* And fixup the flags on the single remaining edge.  */
    2438                 :     293510 :   edge fix_e = find_edge (region_copy[n_region - 1], exit->dest);
    2439                 :     293510 :   fix_e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE | EDGE_ABNORMAL);
    2440                 :     293510 :   fix_e->flags |= EDGE_FALLTHRU;
    2441                 :            : 
    2442                 :     293510 :   edge e = make_edge (region_copy[n_region - 1], exit->dest, EDGE_FALLTHRU);
    2443                 :            : 
    2444                 :     293510 :   if (e)
    2445                 :            :     {
    2446                 :          0 :       rescan_loop_exit (e, true, false);
    2447                 :          0 :       e->probability = profile_probability::always ();
    2448                 :            :     }
    2449                 :            : 
    2450                 :            :   /* Redirect the entry and add the phi node arguments.  */
    2451                 :     293510 :   if (entry->dest == loop->header)
    2452                 :       5183 :     mark_loop_for_removal (loop);
    2453                 :     293510 :   redirected = redirect_edge_and_branch (entry, get_bb_copy (entry->dest));
    2454                 :     293510 :   gcc_assert (redirected != NULL);
    2455                 :     293510 :   flush_pending_stmts (entry);
    2456                 :            : 
    2457                 :            :   /* Add the other PHI node arguments.  */
    2458                 :     293510 :   add_phi_args_after_copy (region_copy, n_region, NULL);
    2459                 :            : 
    2460                 :     293510 :   free (region_copy);
    2461                 :            : 
    2462                 :     293510 :   adjust_paths_after_duplication (current_path_no);
    2463                 :            : 
    2464                 :     293510 :   free_original_copy_tables ();
    2465                 :     293510 :   return true;
    2466                 :            : }
    2467                 :            : 
    2468                 :            : /* Return true when PATH is a valid jump-thread path.  */
    2469                 :            : 
    2470                 :            : static bool
    2471                 :     293642 : valid_jump_thread_path (vec<jump_thread_edge *> *path)
    2472                 :            : {
    2473                 :     293642 :   unsigned len = path->length ();
    2474                 :            : 
    2475                 :            :   /* Check that the path is connected.  */
    2476                 :     646517 :   for (unsigned int j = 0; j < len - 1; j++)
    2477                 :            :     {
    2478                 :     353007 :       edge e = (*path)[j]->e;
    2479                 :     353007 :       if (e->dest != (*path)[j+1]->e->src)
    2480                 :            :         return false;
    2481                 :            :     }
    2482                 :            :   return true;
    2483                 :            : }
    2484                 :            : 
    2485                 :            : /* Remove any queued jump threads that include edge E.
    2486                 :            : 
    2487                 :            :    We don't actually remove them here, just record the edges into ax
    2488                 :            :    hash table.  That way we can do the search once per iteration of
    2489                 :            :    DOM/VRP rather than for every case where DOM optimizes away a COND_EXPR.  */
    2490                 :            : 
    2491                 :            : void
    2492                 :     107224 : remove_jump_threads_including (edge_def *e)
    2493                 :            : {
    2494                 :     107224 :   if (!paths.exists ())
    2495                 :            :     return;
    2496                 :            : 
    2497                 :      87534 :   if (!removed_edges)
    2498                 :      17313 :     removed_edges = new hash_table<struct removed_edges> (17);
    2499                 :            : 
    2500                 :      87534 :   edge *slot = removed_edges->find_slot (e, INSERT);
    2501                 :      87534 :   *slot = e;
    2502                 :            : }
    2503                 :            : 
    2504                 :            : /* Walk through all blocks and thread incoming edges to the appropriate
    2505                 :            :    outgoing edge for each edge pair recorded in THREADED_EDGES.
    2506                 :            : 
    2507                 :            :    It is the caller's responsibility to fix the dominance information
    2508                 :            :    and rewrite duplicated SSA_NAMEs back into SSA form.
    2509                 :            : 
    2510                 :            :    If MAY_PEEL_LOOP_HEADERS is false, we avoid threading edges through
    2511                 :            :    loop headers if it does not simplify the loop.
    2512                 :            : 
    2513                 :            :    Returns true if one or more edges were threaded, false otherwise.  */
    2514                 :            : 
    2515                 :            : bool
    2516                 :    6821600 : thread_through_all_blocks (bool may_peel_loop_headers)
    2517                 :            : {
    2518                 :    6821600 :   bool retval = false;
    2519                 :    6821600 :   unsigned int i;
    2520                 :    6821600 :   class loop *loop;
    2521                 :    6821600 :   auto_bitmap threaded_blocks;
    2522                 :   13643200 :   hash_set<edge> visited_starting_edges;
    2523                 :            : 
    2524                 :    6821600 :   if (!paths.exists ())
    2525                 :            :     {
    2526                 :    6474330 :       retval = false;
    2527                 :    6474330 :       goto out;
    2528                 :            :     }
    2529                 :            : 
    2530                 :     347277 :   memset (&thread_stats, 0, sizeof (thread_stats));
    2531                 :            : 
    2532                 :            :   /* Remove any paths that referenced removed edges.  */
    2533                 :     347277 :   if (removed_edges)
    2534                 :     282090 :     for (i = 0; i < paths.length (); )
    2535                 :            :       {
    2536                 :     123732 :         unsigned int j;
    2537                 :     123732 :         vec<jump_thread_edge *> *path = paths[i];
    2538                 :            : 
    2539                 :     786248 :         for (j = 0; j < path->length (); j++)
    2540                 :            :           {
    2541                 :     304123 :             edge e = (*path)[j]->e;
    2542                 :     304123 :             if (removed_edges->find_slot (e, NO_INSERT))
    2543                 :            :               break;
    2544                 :            :           }
    2545                 :            : 
    2546                 :     247464 :         if (j != path->length ())
    2547                 :            :           {
    2548                 :      34731 :             delete_jump_thread_path (path);
    2549                 :      34731 :             paths.unordered_remove (i);
    2550                 :      34731 :             continue;
    2551                 :            :           }
    2552                 :      89001 :         i++;
    2553                 :            :       }
    2554                 :            : 
    2555                 :            :   /* Jump-thread all FSM threads before other jump-threads.  */
    2556                 :    3299850 :   for (i = 0; i < paths.length ();)
    2557                 :            :     {
    2558                 :    1302650 :       vec<jump_thread_edge *> *path = paths[i];
    2559                 :    1302650 :       edge entry = (*path)[0]->e;
    2560                 :            : 
    2561                 :            :       /* Only code-generate FSM jump-threads in this loop.  */
    2562                 :    1302650 :       if ((*path)[0]->type != EDGE_FSM_THREAD)
    2563                 :            :         {
    2564                 :    1009010 :           i++;
    2565                 :    1009140 :           continue;
    2566                 :            :         }
    2567                 :            : 
    2568                 :            :       /* Do not jump-thread twice from the same starting edge.
    2569                 :            : 
    2570                 :            :          Previously we only checked that we weren't threading twice
    2571                 :            :          from the same BB, but that was too restrictive.  Imagine a
    2572                 :            :          path that starts from GIMPLE_COND(x_123 == 0,...), where both
    2573                 :            :          edges out of this conditional yield paths that can be
    2574                 :            :          threaded (for example, both lead to an x_123==0 or x_123!=0
    2575                 :            :          conditional further down the line.  */
    2576                 :     293642 :       if (visited_starting_edges.contains (entry)
    2577                 :            :           /* We may not want to realize this jump thread path for
    2578                 :            :              various reasons.  So check it first.  */
    2579                 :     293642 :           || !valid_jump_thread_path (path))
    2580                 :            :         {
    2581                 :            :           /* Remove invalid FSM jump-thread paths.  */
    2582                 :        132 :           delete_jump_thread_path (path);
    2583                 :        132 :           paths.unordered_remove (i);
    2584                 :        132 :           continue;
    2585                 :            :         }
    2586                 :            : 
    2587                 :     293510 :       unsigned len = path->length ();
    2588                 :     293510 :       edge exit = (*path)[len - 1]->e;
    2589                 :     293510 :       basic_block *region = XNEWVEC (basic_block, len - 1);
    2590                 :            : 
    2591                 :     646161 :       for (unsigned int j = 0; j < len - 1; j++)
    2592                 :     352651 :         region[j] = (*path)[j]->e->dest;
    2593                 :            : 
    2594                 :     293510 :       if (duplicate_thread_path (entry, exit, region, len - 1, i))
    2595                 :            :         {
    2596                 :            :           /* We do not update dominance info.  */
    2597                 :     293510 :           free_dominance_info (CDI_DOMINATORS);
    2598                 :     293510 :           visited_starting_edges.add (entry);
    2599                 :     293510 :           retval = true;
    2600                 :     293510 :           thread_stats.num_threaded_edges++;
    2601                 :            :         }
    2602                 :            : 
    2603                 :     293510 :       delete_jump_thread_path (path);
    2604                 :     293510 :       paths.unordered_remove (i);
    2605                 :     293510 :       free (region);
    2606                 :            :     }
    2607                 :            : 
    2608                 :            :   /* Remove from PATHS all the jump-threads starting with an edge already
    2609                 :            :      jump-threaded.  */
    2610                 :    2712570 :   for (i = 0; i < paths.length ();)
    2611                 :            :     {
    2612                 :    1009010 :       vec<jump_thread_edge *> *path = paths[i];
    2613                 :    1009010 :       edge entry = (*path)[0]->e;
    2614                 :            : 
    2615                 :            :       /* Do not jump-thread twice from the same block.  */
    2616                 :    1009010 :       if (visited_starting_edges.contains (entry))
    2617                 :            :         {
    2618                 :         42 :           delete_jump_thread_path (path);
    2619                 :    1009050 :           paths.unordered_remove (i);
    2620                 :            :         }
    2621                 :            :       else
    2622                 :    1008960 :         i++;
    2623                 :            :     }
    2624                 :            : 
    2625                 :     347277 :   mark_threaded_blocks (threaded_blocks);
    2626                 :            : 
    2627                 :     347277 :   initialize_original_copy_tables ();
    2628                 :            : 
    2629                 :            :   /* The order in which we process jump threads can be important.
    2630                 :            : 
    2631                 :            :      Consider if we have two jump threading paths A and B.  If the
    2632                 :            :      target edge of A is the starting edge of B and we thread path A
    2633                 :            :      first, then we create an additional incoming edge into B->dest that
    2634                 :            :      we cannot discover as a jump threading path on this iteration.
    2635                 :            : 
    2636                 :            :      If we instead thread B first, then the edge into B->dest will have
    2637                 :            :      already been redirected before we process path A and path A will
    2638                 :            :      natually, with no further work, target the redirected path for B.
    2639                 :            : 
    2640                 :            :      An post-order is sufficient here.  Compute the ordering first, then
    2641                 :            :      process the blocks.  */
    2642                 :     347277 :   if (!bitmap_empty_p (threaded_blocks))
    2643                 :            :     {
    2644                 :     255791 :       int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
    2645                 :     255791 :       unsigned int postorder_num = post_order_compute (postorder, false, false);
    2646                 :   10134700 :       for (unsigned int i = 0; i < postorder_num; i++)
    2647                 :            :         {
    2648                 :    9878940 :           unsigned int indx = postorder[i];
    2649                 :    9878940 :           if (bitmap_bit_p (threaded_blocks, indx))
    2650                 :            :             {
    2651                 :     622426 :               basic_block bb = BASIC_BLOCK_FOR_FN (cfun, indx);
    2652                 :     622426 :               retval |= thread_block (bb, true);
    2653                 :            :             }
    2654                 :            :         }
    2655                 :     255791 :       free (postorder);
    2656                 :            :     }
    2657                 :            : 
    2658                 :            :   /* Then perform the threading through loop headers.  We start with the
    2659                 :            :      innermost loop, so that the changes in cfg we perform won't affect
    2660                 :            :      further threading.  */
    2661                 :    1298790 :   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
    2662                 :            :     {
    2663                 :    1544140 :       if (!loop->header
    2664                 :     951509 :           || !bitmap_bit_p (threaded_blocks, loop->header->index))
    2665                 :     592627 :         continue;
    2666                 :            : 
    2667                 :     358882 :       retval |= thread_through_loop_header (loop, may_peel_loop_headers);
    2668                 :            :     }
    2669                 :            : 
    2670                 :            :   /* All jump threading paths should have been resolved at this
    2671                 :            :      point.  Verify that is the case.  */
    2672                 :     347277 :   basic_block bb;
    2673                 :   15244200 :   FOR_EACH_BB_FN (bb, cfun)
    2674                 :            :     {
    2675                 :   14897000 :       edge_iterator ei;
    2676                 :   14897000 :       edge e;
    2677                 :   36282900 :       FOR_EACH_EDGE (e, ei, bb->preds)
    2678                 :   21386000 :         gcc_assert (e->aux == NULL);
    2679                 :            :     }
    2680                 :            : 
    2681                 :     347277 :   statistics_counter_event (cfun, "Jumps threaded",
    2682                 :     347277 :                             thread_stats.num_threaded_edges);
    2683                 :            : 
    2684                 :     347277 :   free_original_copy_tables ();
    2685                 :            : 
    2686                 :     347277 :   paths.release ();
    2687                 :            : 
    2688                 :     347277 :   if (retval)
    2689                 :     226750 :     loops_state_set (LOOPS_NEED_FIXUP);
    2690                 :            : 
    2691                 :     120527 :  out:
    2692                 :    6821600 :   delete removed_edges;
    2693                 :    6821600 :   removed_edges = NULL;
    2694                 :    6821600 :   return retval;
    2695                 :            : }
    2696                 :            : 
    2697                 :            : /* Delete the jump threading path PATH.  We have to explicitly delete
    2698                 :            :    each entry in the vector, then the container.  */
    2699                 :            : 
    2700                 :            : void
    2701                 :   13020400 : delete_jump_thread_path (vec<jump_thread_edge *> *path)
    2702                 :            : {
    2703                 :   79649600 :   for (unsigned int i = 0; i < path->length (); i++)
    2704                 :   26804400 :     delete (*path)[i];
    2705                 :   13020400 :   path->release();
    2706                 :   13020400 :   delete path;
    2707                 :   13020400 : }
    2708                 :            : 
    2709                 :            : /* Register a jump threading opportunity.  We queue up all the jump
    2710                 :            :    threading opportunities discovered by a pass and update the CFG
    2711                 :            :    and SSA form all at once.
    2712                 :            : 
    2713                 :            :    E is the edge we can thread, E2 is the new target edge, i.e., we
    2714                 :            :    are effectively recording that E->dest can be changed to E2->dest
    2715                 :            :    after fixing the SSA graph.  */
    2716                 :            : 
    2717                 :            : void
    2718                 :    1349680 : register_jump_thread (vec<jump_thread_edge *> *path)
    2719                 :            : {
    2720                 :    1349680 :   if (!dbg_cnt (registered_jump_thread))
    2721                 :            :     {
    2722                 :          0 :       delete_jump_thread_path (path);
    2723                 :          0 :       return;
    2724                 :            :     }
    2725                 :            : 
    2726                 :            :   /* First make sure there are no NULL outgoing edges on the jump threading
    2727                 :            :      path.  That can happen for jumping to a constant address.  */
    2728                 :    9082870 :   for (unsigned int i = 0; i < path->length (); i++)
    2729                 :            :     {
    2730                 :    3191760 :       if ((*path)[i]->e == NULL)
    2731                 :            :         {
    2732                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2733                 :            :             {
    2734                 :          0 :               fprintf (dump_file,
    2735                 :            :                        "Found NULL edge in jump threading path.  Cancelling jump thread:\n");
    2736                 :          0 :               dump_jump_thread_path (dump_file, *path, false);
    2737                 :            :             }
    2738                 :            : 
    2739                 :          0 :           delete_jump_thread_path (path);
    2740                 :          0 :           return;
    2741                 :            :         }
    2742                 :            : 
    2743                 :            :       /* Only the FSM threader is allowed to thread across
    2744                 :            :          backedges in the CFG.  */
    2745                 :    3191760 :       if (flag_checking
    2746                 :    3191760 :           && (*path)[0]->type != EDGE_FSM_THREAD)
    2747                 :    2498050 :         gcc_assert (((*path)[i]->e->flags & EDGE_DFS_BACK) == 0);
    2748                 :            :     }
    2749                 :            : 
    2750                 :    1349680 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2751                 :        177 :     dump_jump_thread_path (dump_file, *path, true);
    2752                 :            : 
    2753                 :    1349680 :   if (!paths.exists ())
    2754                 :     347277 :     paths.create (5);
    2755                 :            : 
    2756                 :    1349680 :   paths.safe_push (path);
    2757                 :            : }
    2758                 :            : 
    2759                 :            : /* Return how many uses of T there are within BB, as long as there
    2760                 :            :    aren't any uses outside BB.  If there are any uses outside BB,
    2761                 :            :    return -1 if there's at most one use within BB, or -2 if there is
    2762                 :            :    more than one use within BB.  */
    2763                 :            : 
    2764                 :            : static int
    2765                 :    2136900 : uses_in_bb (tree t, basic_block bb)
    2766                 :            : {
    2767                 :    2136900 :   int uses = 0;
    2768                 :    2136900 :   bool outside_bb = false;
    2769                 :            : 
    2770                 :    2136900 :   imm_use_iterator iter;
    2771                 :    2136900 :   use_operand_p use_p;
    2772                 :    6518040 :   FOR_EACH_IMM_USE_FAST (use_p, iter, t)
    2773                 :            :     {
    2774                 :    4548570 :       if (is_gimple_debug (USE_STMT (use_p)))
    2775                 :     541832 :         continue;
    2776                 :            : 
    2777                 :    4006740 :       if (gimple_bb (USE_STMT (use_p)) != bb)
    2778                 :            :         outside_bb = true;
    2779                 :            :       else
    2780                 :    2510910 :         uses++;
    2781                 :            : 
    2782                 :    4006740 :       if (outside_bb && uses > 1)
    2783                 :            :         return -2;
    2784                 :            :     }
    2785                 :            : 
    2786                 :    1969470 :   if (outside_bb)
    2787                 :     559735 :     return -1;
    2788                 :            : 
    2789                 :            :   return uses;
    2790                 :            : }
    2791                 :            : 
    2792                 :            : /* Starting from the final control flow stmt in BB, assuming it will
    2793                 :            :    be removed, follow uses in to-be-removed stmts back to their defs
    2794                 :            :    and count how many defs are to become dead and be removed as
    2795                 :            :    well.  */
    2796                 :            : 
    2797                 :            : unsigned int
    2798                 :    2059620 : estimate_threading_killed_stmts (basic_block bb)
    2799                 :            : {
    2800                 :    2059620 :   int killed_stmts = 0;
    2801                 :    2059620 :   hash_map<tree, int> ssa_remaining_uses;
    2802                 :    4119240 :   auto_vec<gimple *, 4> dead_worklist;
    2803                 :            : 
    2804                 :            :   /* If the block has only two predecessors, threading will turn phi
    2805                 :            :      dsts into either src, so count them as dead stmts.  */
    2806                 :    2059620 :   bool drop_all_phis = EDGE_COUNT (bb->preds) == 2;
    2807                 :            : 
    2808                 :    2059620 :   if (drop_all_phis)
    2809                 :     875542 :     for (gphi_iterator gsi = gsi_start_phis (bb);
    2810                 :    2632590 :          !gsi_end_p (gsi); gsi_next (&gsi))
    2811                 :            :       {
    2812                 :    1757050 :         gphi *phi = gsi.phi ();
    2813                 :    1757050 :         tree dst = gimple_phi_result (phi);
    2814                 :            : 
    2815                 :            :         /* We don't count virtual PHIs as stmts in
    2816                 :            :            record_temporary_equivalences_from_phis.  */
    2817                 :    3514100 :         if (virtual_operand_p (dst))
    2818                 :     662884 :           continue;
    2819                 :            : 
    2820                 :    1094170 :         killed_stmts++;
    2821                 :            :       }
    2822                 :            : 
    2823                 :    4119240 :   if (gsi_end_p (gsi_last_bb (bb)))
    2824                 :          0 :     return killed_stmts;
    2825                 :            : 
    2826                 :    2059620 :   gimple *stmt = gsi_stmt (gsi_last_bb (bb));
    2827                 :    2059620 :   if (gimple_code (stmt) != GIMPLE_COND
    2828                 :     772019 :       && gimple_code (stmt) != GIMPLE_GOTO
    2829                 :    2831600 :       && gimple_code (stmt) != GIMPLE_SWITCH)
    2830                 :     769088 :     return killed_stmts;
    2831                 :            : 
    2832                 :            :   /* The control statement is always dead.  */
    2833                 :    1290530 :   killed_stmts++;
    2834                 :    1290530 :   dead_worklist.quick_push (stmt);
    2835                 :    3820960 :   while (!dead_worklist.is_empty ())
    2836                 :            :     {
    2837                 :    2530420 :       stmt = dead_worklist.pop ();
    2838                 :            : 
    2839                 :    2530420 :       ssa_op_iter iter;
    2840                 :    2530420 :       use_operand_p use_p;
    2841                 :    5493030 :       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
    2842                 :            :         {
    2843                 :    2962610 :           tree t = USE_FROM_PTR (use_p);
    2844                 :    2962610 :           gimple *def = SSA_NAME_DEF_STMT (t);
    2845                 :            : 
    2846                 :    2962610 :           if (gimple_bb (def) == bb
    2847                 :    2425550 :               && (gimple_code (def) != GIMPLE_PHI
    2848                 :     114325 :                   || !drop_all_phis)
    2849                 :    5321880 :               && !gimple_has_side_effects (def))
    2850                 :            :             {
    2851                 :    2246040 :               int *usesp = ssa_remaining_uses.get (t);
    2852                 :     109139 :               int uses;
    2853                 :            : 
    2854                 :     109139 :               if (usesp)
    2855                 :     109139 :                 uses = *usesp;
    2856                 :            :               else
    2857                 :    2136900 :                 uses = uses_in_bb (t, bb);
    2858                 :            : 
    2859                 :    2246040 :               gcc_assert (uses);
    2860                 :            : 
    2861                 :            :               /* Don't bother recording the expected use count if we
    2862                 :            :                  won't find any further uses within BB.  */
    2863                 :    2246040 :               if (!usesp && (uses < -1 || uses > 1))
    2864                 :            :                 {
    2865                 :     330627 :                   usesp = &ssa_remaining_uses.get_or_insert (t);
    2866                 :     330627 :                   *usesp = uses;
    2867                 :            :                 }
    2868                 :            : 
    2869                 :    2246040 :               if (uses < 0)
    2870                 :     812369 :                 continue;
    2871                 :            : 
    2872                 :    1433670 :               --uses;
    2873                 :    1433670 :               if (usesp)
    2874                 :     187132 :                 *usesp = uses;
    2875                 :            : 
    2876                 :    1433670 :               if (!uses)
    2877                 :            :                 {
    2878                 :    1260140 :                   killed_stmts++;
    2879                 :    1260140 :                   if (usesp)
    2880                 :      13596 :                     ssa_remaining_uses.remove (t);
    2881                 :    1260140 :                   if (gimple_code (def) != GIMPLE_PHI)
    2882                 :    1239890 :                     dead_worklist.safe_push (def);
    2883                 :            :                 }
    2884                 :            :             }
    2885                 :            :         }
    2886                 :            :     }
    2887                 :            : 
    2888                 :    1290530 :   if (dump_file)
    2889                 :         30 :     fprintf (dump_file, "threading bb %i kills %i stmts\n",
    2890                 :            :              bb->index, killed_stmts);
    2891                 :            : 
    2892                 :    1290530 :   return killed_stmts;
    2893                 :            : }

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.