LCOV - code coverage report
Current view: top level - gcc - tree-into-ssa.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1179 1344 87.7 %
Date: 2020-04-04 11:58:09 Functions: 72 87 82.8 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Rewrite a program in Normal form into SSA.
       2                 :            :    Copyright (C) 2001-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Diego Novillo <dnovillo@redhat.com>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify
       8                 :            : it under the terms of the GNU General Public License as published by
       9                 :            : the Free Software Foundation; either version 3, or (at your option)
      10                 :            : any later version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful,
      13                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            : GNU General Public License for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "backend.h"
      25                 :            : #include "rtl.h"
      26                 :            : #include "tree.h"
      27                 :            : #include "gimple.h"
      28                 :            : #include "tree-pass.h"
      29                 :            : #include "ssa.h"
      30                 :            : #include "gimple-pretty-print.h"
      31                 :            : #include "diagnostic-core.h"
      32                 :            : #include "langhooks.h"
      33                 :            : #include "cfganal.h"
      34                 :            : #include "gimple-iterator.h"
      35                 :            : #include "tree-cfg.h"
      36                 :            : #include "tree-into-ssa.h"
      37                 :            : #include "tree-dfa.h"
      38                 :            : #include "tree-ssa.h"
      39                 :            : #include "domwalk.h"
      40                 :            : #include "statistics.h"
      41                 :            : #include "stringpool.h"
      42                 :            : #include "attribs.h"
      43                 :            : #include "asan.h"
      44                 :            : 
      45                 :            : #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
      46                 :            : 
      47                 :            : /* This file builds the SSA form for a function as described in:
      48                 :            :    R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
      49                 :            :    Computing Static Single Assignment Form and the Control Dependence
      50                 :            :    Graph. ACM Transactions on Programming Languages and Systems,
      51                 :            :    13(4):451-490, October 1991.  */
      52                 :            : 
      53                 :            : /* Structure to map a variable VAR to the set of blocks that contain
      54                 :            :    definitions for VAR.  */
      55                 :            : struct def_blocks
      56                 :            : {
      57                 :            :   /* Blocks that contain definitions of VAR.  Bit I will be set if the
      58                 :            :      Ith block contains a definition of VAR.  */
      59                 :            :   bitmap def_blocks;
      60                 :            : 
      61                 :            :   /* Blocks that contain a PHI node for VAR.  */
      62                 :            :   bitmap phi_blocks;
      63                 :            : 
      64                 :            :   /* Blocks where VAR is live-on-entry.  Similar semantics as
      65                 :            :      DEF_BLOCKS.  */
      66                 :            :   bitmap livein_blocks;
      67                 :            : };
      68                 :            : 
      69                 :            : /* Stack of trees used to restore the global currdefs to its original
      70                 :            :    state after completing rewriting of a block and its dominator
      71                 :            :    children.  Its elements have the following properties:
      72                 :            : 
      73                 :            :    - An SSA_NAME (N) indicates that the current definition of the
      74                 :            :      underlying variable should be set to the given SSA_NAME.  If the
      75                 :            :      symbol associated with the SSA_NAME is not a GIMPLE register, the
      76                 :            :      next slot in the stack must be a _DECL node (SYM).  In this case,
      77                 :            :      the name N in the previous slot is the current reaching
      78                 :            :      definition for SYM.
      79                 :            : 
      80                 :            :    - A _DECL node indicates that the underlying variable has no
      81                 :            :      current definition.
      82                 :            : 
      83                 :            :    - A NULL node at the top entry is used to mark the last slot
      84                 :            :      associated with the current block.  */
      85                 :            : static vec<tree> block_defs_stack;
      86                 :            : 
      87                 :            : 
      88                 :            : /* Set of existing SSA names being replaced by update_ssa.  */
      89                 :            : static sbitmap old_ssa_names;
      90                 :            : 
      91                 :            : /* Set of new SSA names being added by update_ssa.  Note that both
      92                 :            :    NEW_SSA_NAMES and OLD_SSA_NAMES are dense bitmaps because most of
      93                 :            :    the operations done on them are presence tests.  */
      94                 :            : static sbitmap new_ssa_names;
      95                 :            : 
      96                 :            : static sbitmap interesting_blocks;
      97                 :            : 
      98                 :            : /* Set of SSA names that have been marked to be released after they
      99                 :            :    were registered in the replacement table.  They will be finally
     100                 :            :    released after we finish updating the SSA web.  */
     101                 :            : bitmap names_to_release;
     102                 :            : 
     103                 :            : /* vec of vec of PHIs to rewrite in a basic block.  Element I corresponds
     104                 :            :    the to basic block with index I.  Allocated once per compilation, *not*
     105                 :            :    released between different functions.  */
     106                 :            : static vec< vec<gphi *> > phis_to_rewrite;
     107                 :            : 
     108                 :            : /* The bitmap of non-NULL elements of PHIS_TO_REWRITE.  */
     109                 :            : static bitmap blocks_with_phis_to_rewrite;
     110                 :            : 
     111                 :            : /* Growth factor for NEW_SSA_NAMES and OLD_SSA_NAMES.  These sets need
     112                 :            :    to grow as the callers to create_new_def_for will create new names on
     113                 :            :    the fly.
     114                 :            :    FIXME.  Currently set to 1/3 to avoid frequent reallocations but still
     115                 :            :    need to find a reasonable growth strategy.  */
     116                 :            : #define NAME_SETS_GROWTH_FACTOR (MAX (3, num_ssa_names / 3))
     117                 :            : 
     118                 :            : 
     119                 :            : /* The function the SSA updating data structures have been initialized for.
     120                 :            :    NULL if they need to be initialized by create_new_def_for.  */
     121                 :            : static struct function *update_ssa_initialized_fn = NULL;
     122                 :            : 
     123                 :            : /* Global data to attach to the main dominator walk structure.  */
     124                 :            : struct mark_def_sites_global_data
     125                 :            : {
     126                 :            :   /* This bitmap contains the variables which are set before they
     127                 :            :      are used in a basic block.  */
     128                 :            :   bitmap kills;
     129                 :            : };
     130                 :            : 
     131                 :            : /* It is advantageous to avoid things like life analysis for variables which
     132                 :            :    do not need PHI nodes.  This enum describes whether or not a particular
     133                 :            :    variable may need a PHI node.  */
     134                 :            : 
     135                 :            : enum need_phi_state {
     136                 :            :   /* This is the default.  If we are still in this state after finding
     137                 :            :      all the definition and use sites, then we will assume the variable
     138                 :            :      needs PHI nodes.  This is probably an overly conservative assumption.  */
     139                 :            :   NEED_PHI_STATE_UNKNOWN,
     140                 :            : 
     141                 :            :   /* This state indicates that we have seen one or more sets of the
     142                 :            :      variable in a single basic block and that the sets dominate all
     143                 :            :      uses seen so far.  If after finding all definition and use sites
     144                 :            :      we are still in this state, then the variable does not need any
     145                 :            :      PHI nodes.  */
     146                 :            :   NEED_PHI_STATE_NO,
     147                 :            : 
     148                 :            :   /* This state indicates that we have either seen multiple definitions of
     149                 :            :      the variable in multiple blocks, or that we encountered a use in a
     150                 :            :      block that was not dominated by the block containing the set(s) of
     151                 :            :      this variable.  This variable is assumed to need PHI nodes.  */
     152                 :            :   NEED_PHI_STATE_MAYBE
     153                 :            : };
     154                 :            : 
     155                 :            : /* Information stored for both SSA names and decls.  */
     156                 :            : struct common_info
     157                 :            : {
     158                 :            :   /* This field indicates whether or not the variable may need PHI nodes.
     159                 :            :      See the enum's definition for more detailed information about the
     160                 :            :      states.  */
     161                 :            :   ENUM_BITFIELD (need_phi_state) need_phi_state : 2;
     162                 :            : 
     163                 :            :   /* The current reaching definition replacing this var.  */
     164                 :            :   tree current_def;
     165                 :            : 
     166                 :            :   /* Definitions for this var.  */
     167                 :            :   struct def_blocks def_blocks;
     168                 :            : };
     169                 :            : 
     170                 :            : /* Information stored for decls.  */
     171                 :            : struct var_info
     172                 :            : {
     173                 :            :   /* The variable.  */
     174                 :            :   tree var;
     175                 :            : 
     176                 :            :   /* Information stored for both SSA names and decls.  */
     177                 :            :   common_info info;
     178                 :            : };
     179                 :            : 
     180                 :            : 
     181                 :            : /* VAR_INFOS hashtable helpers.  */
     182                 :            : 
     183                 :            : struct var_info_hasher : free_ptr_hash <var_info>
     184                 :            : {
     185                 :            :   static inline hashval_t hash (const value_type &);
     186                 :            :   static inline bool equal (const value_type &, const compare_type &);
     187                 :            : };
     188                 :            : 
     189                 :            : inline hashval_t
     190                 :            : var_info_hasher::hash (const value_type &p)
     191                 :            : {
     192                 :            :   return DECL_UID (p->var);
     193                 :            : }
     194                 :            : 
     195                 :            : inline bool
     196                 : 1304890000 : var_info_hasher::equal (const value_type &p1, const compare_type &p2)
     197                 :            : {
     198                 : 1304890000 :   return p1->var == p2->var;
     199                 :            : }
     200                 :            : 
     201                 :            : 
     202                 :            : /* Each entry in VAR_INFOS contains an element of type STRUCT 
     203                 :            :    VAR_INFO_D.  */
     204                 :            : static hash_table<var_info_hasher> *var_infos;
     205                 :            : 
     206                 :            : 
     207                 :            : /* Information stored for SSA names.  */
     208                 :            : struct ssa_name_info
     209                 :            : {
     210                 :            :   /* Age of this record (so that info_for_ssa_name table can be cleared
     211                 :            :      quickly); if AGE < CURRENT_INFO_FOR_SSA_NAME_AGE, then the fields
     212                 :            :      are assumed to be null.  */
     213                 :            :   unsigned age;
     214                 :            : 
     215                 :            :   /* Replacement mappings, allocated from update_ssa_obstack.  */
     216                 :            :   bitmap repl_set;
     217                 :            : 
     218                 :            :   /* Information stored for both SSA names and decls.  */
     219                 :            :   common_info info;
     220                 :            : };
     221                 :            : 
     222                 :            : static vec<ssa_name_info *> info_for_ssa_name;
     223                 :            : static unsigned current_info_for_ssa_name_age;
     224                 :            : 
     225                 :            : static bitmap_obstack update_ssa_obstack;
     226                 :            : 
     227                 :            : /* The set of blocks affected by update_ssa.  */
     228                 :            : static bitmap blocks_to_update;
     229                 :            : 
     230                 :            : /* The main entry point to the SSA renamer (rewrite_blocks) may be
     231                 :            :    called several times to do different, but related, tasks.
     232                 :            :    Initially, we need it to rename the whole program into SSA form.
     233                 :            :    At other times, we may need it to only rename into SSA newly
     234                 :            :    exposed symbols.  Finally, we can also call it to incrementally fix
     235                 :            :    an already built SSA web.  */
     236                 :            : enum rewrite_mode {
     237                 :            :     /* Convert the whole function into SSA form.  */
     238                 :            :     REWRITE_ALL,
     239                 :            : 
     240                 :            :     /* Incrementally update the SSA web by replacing existing SSA
     241                 :            :        names with new ones.  See update_ssa for details.  */
     242                 :            :     REWRITE_UPDATE
     243                 :            : };
     244                 :            : 
     245                 :            : /* The set of symbols we ought to re-write into SSA form in update_ssa.  */
     246                 :            : static bitmap symbols_to_rename_set;
     247                 :            : static vec<tree> symbols_to_rename;
     248                 :            : 
     249                 :            : /* Mark SYM for renaming.  */
     250                 :            : 
     251                 :            : static void
     252                 :   88603200 : mark_for_renaming (tree sym)
     253                 :            : {
     254                 :   88603200 :   if (!symbols_to_rename_set)
     255                 :    1534940 :     symbols_to_rename_set = BITMAP_ALLOC (NULL);
     256                 :   88603200 :   if (bitmap_set_bit (symbols_to_rename_set, DECL_UID (sym)))
     257                 :    5996140 :     symbols_to_rename.safe_push (sym);
     258                 :   88603200 : }
     259                 :            : 
     260                 :            : /* Return true if SYM is marked for renaming.  */
     261                 :            : 
     262                 :            : static bool
     263                 :  269101000 : marked_for_renaming (tree sym)
     264                 :            : {
     265                 :  269101000 :   if (!symbols_to_rename_set || sym == NULL_TREE)
     266                 :            :     return false;
     267                 :  126855000 :   return bitmap_bit_p (symbols_to_rename_set, DECL_UID (sym));
     268                 :            : }
     269                 :            : 
     270                 :            : 
     271                 :            : /* Return true if STMT needs to be rewritten.  When renaming a subset
     272                 :            :    of the variables, not all statements will be processed.  This is
     273                 :            :    decided in mark_def_sites.  */
     274                 :            : 
     275                 :            : static inline bool
     276                 :  610487000 : rewrite_uses_p (gimple *stmt)
     277                 :            : {
     278                 :  610487000 :   return gimple_visited_p (stmt);
     279                 :            : }
     280                 :            : 
     281                 :            : 
     282                 :            : /* Set the rewrite marker on STMT to the value given by REWRITE_P.  */
     283                 :            : 
     284                 :            : static inline void
     285                 :  555719000 : set_rewrite_uses (gimple *stmt, bool rewrite_p)
     286                 :            : {
     287                 :  555719000 :   gimple_set_visited (stmt, rewrite_p);
     288                 :   39814300 : }
     289                 :            : 
     290                 :            : 
     291                 :            : /* Return true if the DEFs created by statement STMT should be
     292                 :            :    registered when marking new definition sites.  This is slightly
     293                 :            :    different than rewrite_uses_p: it's used by update_ssa to
     294                 :            :    distinguish statements that need to have both uses and defs
     295                 :            :    processed from those that only need to have their defs processed.
     296                 :            :    Statements that define new SSA names only need to have their defs
     297                 :            :    registered, but they don't need to have their uses renamed.  */
     298                 :            : 
     299                 :            : static inline bool
     300                 :  440720000 : register_defs_p (gimple *stmt)
     301                 :            : {
     302                 :  292394000 :   return gimple_plf (stmt, GF_PLF_1) != 0;
     303                 :            : }
     304                 :            : 
     305                 :            : 
     306                 :            : /* If REGISTER_DEFS_P is true, mark STMT to have its DEFs registered.  */
     307                 :            : 
     308                 :            : static inline void
     309                 :  495736000 : set_register_defs (gimple *stmt, bool register_defs_p)
     310                 :            : {
     311                 :  532147000 :   gimple_set_plf (stmt, GF_PLF_1, register_defs_p);
     312                 :            : }
     313                 :            : 
     314                 :            : 
     315                 :            : /* Get the information associated with NAME.  */
     316                 :            : 
     317                 :            : static inline ssa_name_info *
     318                 :  184252000 : get_ssa_name_ann (tree name)
     319                 :            : {
     320                 :  184252000 :   unsigned ver = SSA_NAME_VERSION (name);
     321                 :  184252000 :   unsigned len = info_for_ssa_name.length ();
     322                 :  184252000 :   struct ssa_name_info *info;
     323                 :            : 
     324                 :            :   /* Re-allocate the vector at most once per update/into-SSA.  */
     325                 :  184252000 :   if (ver >= len)
     326                 :    3743140 :     info_for_ssa_name.safe_grow_cleared (num_ssa_names);
     327                 :            : 
     328                 :            :   /* But allocate infos lazily.  */
     329                 :  184252000 :   info = info_for_ssa_name[ver];
     330                 :  184252000 :   if (!info)
     331                 :            :     {
     332                 :    5789300 :       info = XCNEW (struct ssa_name_info);
     333                 :    5789300 :       info->age = current_info_for_ssa_name_age;
     334                 :    5789300 :       info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
     335                 :    5789300 :       info_for_ssa_name[ver] = info;
     336                 :            :     }
     337                 :            : 
     338                 :  184252000 :   if (info->age < current_info_for_ssa_name_age)
     339                 :            :     {
     340                 :   14577700 :       info->age = current_info_for_ssa_name_age;
     341                 :   14577700 :       info->repl_set = NULL;
     342                 :   14577700 :       info->info.need_phi_state = NEED_PHI_STATE_UNKNOWN;
     343                 :   14577700 :       info->info.current_def = NULL_TREE;
     344                 :   14577700 :       info->info.def_blocks.def_blocks = NULL;
     345                 :   14577700 :       info->info.def_blocks.phi_blocks = NULL;
     346                 :   14577700 :       info->info.def_blocks.livein_blocks = NULL;
     347                 :            :     }
     348                 :            : 
     349                 :  184252000 :   return info;
     350                 :            : }
     351                 :            : 
     352                 :            : /* Return and allocate the auxiliar information for DECL.  */
     353                 :            : 
     354                 :            : static inline var_info *
     355                 :  432759000 : get_var_info (tree decl)
     356                 :            : {
     357                 :  432759000 :   var_info vi;
     358                 :  432759000 :   var_info **slot;
     359                 :  432759000 :   vi.var = decl;
     360                 :  432759000 :   slot = var_infos->find_slot_with_hash (&vi, DECL_UID (decl), INSERT);
     361                 :  432759000 :   if (*slot == NULL)
     362                 :            :     {
     363                 :   17334300 :       var_info *v = XCNEW (var_info);
     364                 :   17334300 :       v->var = decl;
     365                 :   17334300 :       *slot = v;
     366                 :   17334300 :       return v;
     367                 :            :     }
     368                 :            :   return *slot;
     369                 :            : }
     370                 :            : 
     371                 :            : 
     372                 :            : /* Clears info for SSA names.  */
     373                 :            : 
     374                 :            : static void
     375                 :    2722530 : clear_ssa_name_info (void)
     376                 :            : {
     377                 :    2722530 :   current_info_for_ssa_name_age++;
     378                 :            : 
     379                 :            :   /* If current_info_for_ssa_name_age wraps we use stale information.
     380                 :            :      Asser that this does not happen.  */
     381                 :    2722530 :   gcc_assert (current_info_for_ssa_name_age != 0);
     382                 :    2722530 : }
     383                 :            : 
     384                 :            : 
     385                 :            : /* Get access to the auxiliar information stored per SSA name or decl.  */
     386                 :            : 
     387                 :            : static inline common_info *
     388                 :  553105000 : get_common_info (tree var)
     389                 :            : {
     390                 :  553105000 :   if (TREE_CODE (var) == SSA_NAME)
     391                 :  126373000 :     return &get_ssa_name_ann (var)->info;
     392                 :            :   else
     393                 :  426732000 :     return &get_var_info (var)->info;
     394                 :            : }
     395                 :            : 
     396                 :            : 
     397                 :            : /* Return the current definition for VAR.  */
     398                 :            : 
     399                 :            : tree
     400                 :     458805 : get_current_def (tree var)
     401                 :            : {
     402                 :     458805 :   return get_common_info (var)->current_def;
     403                 :            : }
     404                 :            : 
     405                 :            : 
     406                 :            : /* Sets current definition of VAR to DEF.  */
     407                 :            : 
     408                 :            : void
     409                 :       1231 : set_current_def (tree var, tree def)
     410                 :            : {
     411                 :       1231 :   get_common_info (var)->current_def = def;
     412                 :       1231 : }
     413                 :            : 
     414                 :            : /* Cleans up the REWRITE_THIS_STMT and REGISTER_DEFS_IN_THIS_STMT flags for
     415                 :            :    all statements in basic block BB.  */
     416                 :            : 
     417                 :            : static void
     418                 :   47573700 : initialize_flags_in_bb (basic_block bb)
     419                 :            : {
     420                 :   47573700 :   gimple *stmt;
     421                 :   47573700 :   gimple_stmt_iterator gsi;
     422                 :            : 
     423                 :   67731000 :   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     424                 :            :     {
     425                 :   20157300 :       gimple *phi = gsi_stmt (gsi);
     426                 :   20157300 :       set_rewrite_uses (phi, false);
     427                 :   20157300 :       set_register_defs (phi, false);
     428                 :            :     }
     429                 :            : 
     430                 :  441626000 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     431                 :            :     {
     432                 :  346479000 :       stmt = gsi_stmt (gsi);
     433                 :            : 
     434                 :            :       /* We are going to use the operand cache API, such as
     435                 :            :          SET_USE, SET_DEF, and FOR_EACH_IMM_USE_FAST.  The operand
     436                 :            :          cache for each statement should be up-to-date.  */
     437                 :  691817000 :       gcc_checking_assert (!gimple_modified_p (stmt));
     438                 :  346479000 :       set_rewrite_uses (stmt, false);
     439                 :  346479000 :       set_register_defs (stmt, false);
     440                 :            :     }
     441                 :   47573700 : }
     442                 :            : 
     443                 :            : /* Mark block BB as interesting for update_ssa.  */
     444                 :            : 
     445                 :            : static void
     446                 :  270355000 : mark_block_for_update (basic_block bb)
     447                 :            : {
     448                 :  270355000 :   gcc_checking_assert (blocks_to_update != NULL);
     449                 :  270355000 :   if (!bitmap_set_bit (blocks_to_update, bb->index))
     450                 :            :     return;
     451                 :   47573700 :   initialize_flags_in_bb (bb);
     452                 :            : }
     453                 :            : 
     454                 :            : /* Return the set of blocks where variable VAR is defined and the blocks
     455                 :            :    where VAR is live on entry (livein).  If no entry is found in
     456                 :            :    DEF_BLOCKS, a new one is created and returned.  */
     457                 :            : 
     458                 :            : static inline def_blocks *
     459                 :  209108000 : get_def_blocks_for (common_info *info)
     460                 :            : {
     461                 :  209108000 :   def_blocks *db_p = &info->def_blocks;
     462                 :  209108000 :   if (!db_p->def_blocks)
     463                 :            :     {
     464                 :   26667700 :       db_p->def_blocks = BITMAP_ALLOC (&update_ssa_obstack);
     465                 :   26667700 :       db_p->phi_blocks = BITMAP_ALLOC (&update_ssa_obstack);
     466                 :   26667700 :       db_p->livein_blocks = BITMAP_ALLOC (&update_ssa_obstack);
     467                 :            :     }
     468                 :            : 
     469                 :  209108000 :   return db_p;
     470                 :            : }
     471                 :            : 
     472                 :            : 
     473                 :            : /* Mark block BB as the definition site for variable VAR.  PHI_P is true if
     474                 :            :    VAR is defined by a PHI node.  */
     475                 :            : 
     476                 :            : static void
     477                 :   77824900 : set_def_block (tree var, basic_block bb, bool phi_p)
     478                 :            : {
     479                 :   77824900 :   def_blocks *db_p;
     480                 :   77824900 :   common_info *info;
     481                 :            : 
     482                 :   77824900 :   info = get_common_info (var);
     483                 :   77824900 :   db_p = get_def_blocks_for (info);
     484                 :            : 
     485                 :            :   /* Set the bit corresponding to the block where VAR is defined.  */
     486                 :   77824900 :   bitmap_set_bit (db_p->def_blocks, bb->index);
     487                 :   77824900 :   if (phi_p)
     488                 :   12604500 :     bitmap_set_bit (db_p->phi_blocks, bb->index);
     489                 :            : 
     490                 :            :   /* Keep track of whether or not we may need to insert PHI nodes.
     491                 :            : 
     492                 :            :      If we are in the UNKNOWN state, then this is the first definition
     493                 :            :      of VAR.  Additionally, we have not seen any uses of VAR yet, so
     494                 :            :      we do not need a PHI node for this variable at this time (i.e.,
     495                 :            :      transition to NEED_PHI_STATE_NO).
     496                 :            : 
     497                 :            :      If we are in any other state, then we either have multiple definitions
     498                 :            :      of this variable occurring in different blocks or we saw a use of the
     499                 :            :      variable which was not dominated by the block containing the
     500                 :            :      definition(s).  In this case we may need a PHI node, so enter
     501                 :            :      state NEED_PHI_STATE_MAYBE.  */
     502                 :   77824900 :   if (info->need_phi_state == NEED_PHI_STATE_UNKNOWN)
     503                 :   21006800 :     info->need_phi_state = NEED_PHI_STATE_NO;
     504                 :            :   else
     505                 :   56818200 :     info->need_phi_state = NEED_PHI_STATE_MAYBE;
     506                 :   77824900 : }
     507                 :            : 
     508                 :            : 
     509                 :            : /* Mark block BB as having VAR live at the entry to BB.  */
     510                 :            : 
     511                 :            : static void
     512                 :   56445300 : set_livein_block (tree var, basic_block bb)
     513                 :            : {
     514                 :   56445300 :   common_info *info;
     515                 :   56445300 :   def_blocks *db_p;
     516                 :            : 
     517                 :   56445300 :   info = get_common_info (var);
     518                 :   56445300 :   db_p = get_def_blocks_for (info);
     519                 :            : 
     520                 :            :   /* Set the bit corresponding to the block where VAR is live in.  */
     521                 :   56445300 :   bitmap_set_bit (db_p->livein_blocks, bb->index);
     522                 :            : 
     523                 :            :   /* Keep track of whether or not we may need to insert PHI nodes.
     524                 :            : 
     525                 :            :      If we reach here in NEED_PHI_STATE_NO, see if this use is dominated
     526                 :            :      by the single block containing the definition(s) of this variable.  If
     527                 :            :      it is, then we remain in NEED_PHI_STATE_NO, otherwise we transition to
     528                 :            :      NEED_PHI_STATE_MAYBE.  */
     529                 :   56445300 :   if (info->need_phi_state == NEED_PHI_STATE_NO)
     530                 :            :     {
     531                 :    7226420 :       int def_block_index = bitmap_first_set_bit (db_p->def_blocks);
     532                 :            : 
     533                 :    7226420 :       if (def_block_index == -1
     534                 :   14452800 :           || ! dominated_by_p (CDI_DOMINATORS, bb,
     535                 :    7226420 :                                BASIC_BLOCK_FOR_FN (cfun, def_block_index)))
     536                 :      61971 :         info->need_phi_state = NEED_PHI_STATE_MAYBE;
     537                 :            :     }
     538                 :            :   else
     539                 :   49218800 :     info->need_phi_state = NEED_PHI_STATE_MAYBE;
     540                 :   56445300 : }
     541                 :            : 
     542                 :            : 
     543                 :            : /* Return true if NAME is in OLD_SSA_NAMES.  */
     544                 :            : 
     545                 :            : static inline bool
     546                 :  122886000 : is_old_name (tree name)
     547                 :            : {
     548                 :  122886000 :   unsigned ver = SSA_NAME_VERSION (name);
     549                 :  122886000 :   if (!old_ssa_names)
     550                 :            :     return false;
     551                 :  122204000 :   return (ver < SBITMAP_SIZE (old_ssa_names)
     552                 :  122204000 :           && bitmap_bit_p (old_ssa_names, ver));
     553                 :            : }
     554                 :            : 
     555                 :            : 
     556                 :            : /* Return true if NAME is in NEW_SSA_NAMES.  */
     557                 :            : 
     558                 :            : static inline bool
     559                 :   47869600 : is_new_name (tree name)
     560                 :            : {
     561                 :   47869600 :   unsigned ver = SSA_NAME_VERSION (name);
     562                 :   47869600 :   if (!new_ssa_names)
     563                 :            :     return false;
     564                 :   47187400 :   return (ver < SBITMAP_SIZE (new_ssa_names)
     565                 :   47187400 :           && bitmap_bit_p (new_ssa_names, ver));
     566                 :            : }
     567                 :            : 
     568                 :            : 
     569                 :            : /* Return the names replaced by NEW_TREE (i.e., REPL_TBL[NEW_TREE].SET).  */
     570                 :            : 
     571                 :            : static inline bitmap
     572                 :   18847500 : names_replaced_by (tree new_tree)
     573                 :            : {
     574                 :   37534600 :   return get_ssa_name_ann (new_tree)->repl_set;
     575                 :            : }
     576                 :            : 
     577                 :            : 
     578                 :            : /* Add OLD to REPL_TBL[NEW_TREE].SET.  */
     579                 :            : 
     580                 :            : static inline void
     581                 :   12893700 : add_to_repl_tbl (tree new_tree, tree old)
     582                 :            : {
     583                 :   12893700 :   bitmap *set = &get_ssa_name_ann (new_tree)->repl_set;
     584                 :   12893700 :   if (!*set)
     585                 :   12893700 :     *set = BITMAP_ALLOC (&update_ssa_obstack);
     586                 :   12893700 :   bitmap_set_bit (*set, SSA_NAME_VERSION (old));
     587                 :   12893700 : }
     588                 :            : 
     589                 :            : 
     590                 :            : /* Add a new mapping NEW_TREE -> OLD REPL_TBL.  Every entry N_i in REPL_TBL
     591                 :            :    represents the set of names O_1 ... O_j replaced by N_i.  This is
     592                 :            :    used by update_ssa and its helpers to introduce new SSA names in an
     593                 :            :    already formed SSA web.  */
     594                 :            : 
     595                 :            : static void
     596                 :   12893700 : add_new_name_mapping (tree new_tree, tree old)
     597                 :            : {
     598                 :            :   /* OLD and NEW_TREE must be different SSA names for the same symbol.  */
     599                 :   45642600 :   gcc_checking_assert (new_tree != old
     600                 :            :                        && SSA_NAME_VAR (new_tree) == SSA_NAME_VAR (old));
     601                 :            : 
     602                 :            :   /* We may need to grow NEW_SSA_NAMES and OLD_SSA_NAMES because our
     603                 :            :      caller may have created new names since the set was created.  */
     604                 :   25787400 :   if (SBITMAP_SIZE (new_ssa_names) <= num_ssa_names - 1)
     605                 :            :     {
     606                 :      43759 :       unsigned int new_sz = num_ssa_names + NAME_SETS_GROWTH_FACTOR;
     607                 :      43759 :       new_ssa_names = sbitmap_resize (new_ssa_names, new_sz, 0);
     608                 :      43759 :       old_ssa_names = sbitmap_resize (old_ssa_names, new_sz, 0);
     609                 :            :     }
     610                 :            : 
     611                 :            :   /* Update the REPL_TBL table.  */
     612                 :   12893700 :   add_to_repl_tbl (new_tree, old);
     613                 :            : 
     614                 :            :   /* If OLD had already been registered as a new name, then all the
     615                 :            :      names that OLD replaces should also be replaced by NEW_TREE.  */
     616                 :   12893700 :   if (is_new_name (old))
     617                 :     160512 :     bitmap_ior_into (names_replaced_by (new_tree), names_replaced_by (old));
     618                 :            : 
     619                 :            :   /* Register NEW_TREE and OLD in NEW_SSA_NAMES and OLD_SSA_NAMES,
     620                 :            :      respectively.  */
     621                 :   12893700 :   bitmap_set_bit (new_ssa_names, SSA_NAME_VERSION (new_tree));
     622                 :   12893700 :   bitmap_set_bit (old_ssa_names, SSA_NAME_VERSION (old));
     623                 :   12893700 : }
     624                 :            : 
     625                 :            : 
     626                 :            : /* Call back for walk_dominator_tree used to collect definition sites
     627                 :            :    for every variable in the function.  For every statement S in block
     628                 :            :    BB:
     629                 :            : 
     630                 :            :    1- Variables defined by S in the DEFS of S are marked in the bitmap
     631                 :            :       KILLS.
     632                 :            : 
     633                 :            :    2- If S uses a variable VAR and there is no preceding kill of VAR,
     634                 :            :       then it is marked in the LIVEIN_BLOCKS bitmap associated with VAR.
     635                 :            : 
     636                 :            :    This information is used to determine which variables are live
     637                 :            :    across block boundaries to reduce the number of PHI nodes
     638                 :            :    we create.  */
     639                 :            : 
     640                 :            : static void
     641                 :   43034100 : mark_def_sites (basic_block bb, gimple *stmt, bitmap kills)
     642                 :            : {
     643                 :   43034100 :   tree def;
     644                 :   43034100 :   use_operand_p use_p;
     645                 :   43034100 :   ssa_op_iter iter;
     646                 :            : 
     647                 :            :   /* Since this is the first time that we rewrite the program into SSA
     648                 :            :      form, force an operand scan on every statement.  */
     649                 :   43034100 :   update_stmt (stmt);
     650                 :            : 
     651                 :   43034100 :   gcc_checking_assert (blocks_to_update == NULL);
     652                 :   43034100 :   set_register_defs (stmt, false);
     653                 :   43034100 :   set_rewrite_uses (stmt, false);
     654                 :            : 
     655                 :   43034100 :   if (is_gimple_debug (stmt))
     656                 :            :     {
     657                 :    1860230 :       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
     658                 :            :         {
     659                 :          0 :           tree sym = USE_FROM_PTR (use_p);
     660                 :          0 :           gcc_checking_assert (DECL_P (sym));
     661                 :          0 :           set_rewrite_uses (stmt, true);
     662                 :            :         }
     663                 :    1860230 :       if (rewrite_uses_p (stmt))
     664                 :          0 :         bitmap_set_bit (interesting_blocks, bb->index);
     665                 :    1860230 :       return;
     666                 :            :     }
     667                 :            : 
     668                 :            :   /* If a variable is used before being set, then the variable is live
     669                 :            :      across a block boundary, so mark it live-on-entry to BB.  */
     670                 :   94097200 :   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
     671                 :            :     {
     672                 :   52923400 :       tree sym = USE_FROM_PTR (use_p);
     673                 :   52923400 :       if (TREE_CODE (sym) == SSA_NAME)
     674                 :   13109100 :         continue;
     675                 :   39814300 :       gcc_checking_assert (DECL_P (sym));
     676                 :   39814300 :       if (!bitmap_bit_p (kills, DECL_UID (sym)))
     677                 :   23255400 :         set_livein_block (sym, bb);
     678                 :   52923400 :       set_rewrite_uses (stmt, true);
     679                 :            :     }
     680                 :            : 
     681                 :            :   /* Now process the defs.  Mark BB as the definition block and add
     682                 :            :      each def to the set of killed symbols.  */
     683                 :   77585100 :   FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
     684                 :            :     {
     685                 :   36411300 :       if (TREE_CODE (def) == SSA_NAME)
     686                 :   13007100 :         continue;
     687                 :   23404200 :       gcc_checking_assert (DECL_P (def));
     688                 :   23404200 :       set_def_block (def, bb, false);
     689                 :   23404200 :       bitmap_set_bit (kills, DECL_UID (def));
     690                 :   36411300 :       set_register_defs (stmt, true);
     691                 :            :     }
     692                 :            : 
     693                 :            :   /* If we found the statement interesting then also mark the block BB
     694                 :            :      as interesting.  */
     695                 :   41173800 :   if (rewrite_uses_p (stmt) || register_defs_p (stmt))
     696                 :   75504200 :     bitmap_set_bit (interesting_blocks, bb->index);
     697                 :            : }
     698                 :            : 
     699                 :            : /* Structure used by prune_unused_phi_nodes to record bounds of the intervals
     700                 :            :    in the dfs numbering of the dominance tree.  */
     701                 :            : 
     702                 :            : struct dom_dfsnum
     703                 :            : {
     704                 :            :   /* Basic block whose index this entry corresponds to.  */
     705                 :            :   unsigned bb_index;
     706                 :            : 
     707                 :            :   /* The dfs number of this node.  */
     708                 :            :   unsigned dfs_num;
     709                 :            : };
     710                 :            : 
     711                 :            : /* Compares two entries of type struct dom_dfsnum by dfs_num field.  Callback
     712                 :            :    for qsort.  */
     713                 :            : 
     714                 :            : static int
     715                 : 1280510000 : cmp_dfsnum (const void *a, const void *b)
     716                 :            : {
     717                 : 1280510000 :   const struct dom_dfsnum *const da = (const struct dom_dfsnum *) a;
     718                 : 1280510000 :   const struct dom_dfsnum *const db = (const struct dom_dfsnum *) b;
     719                 :            : 
     720                 : 1280510000 :   return (int) da->dfs_num - (int) db->dfs_num;
     721                 :            : }
     722                 :            : 
     723                 :            : /* Among the intervals starting at the N points specified in DEFS, find
     724                 :            :    the one that contains S, and return its bb_index.  */
     725                 :            : 
     726                 :            : static unsigned
     727                 :   20105400 : find_dfsnum_interval (struct dom_dfsnum *defs, unsigned n, unsigned s)
     728                 :            : {
     729                 :          0 :   unsigned f = 0, t = n, m;
     730                 :            : 
     731                 :  120792000 :   while (t > f + 1)
     732                 :            :     {
     733                 :  100686000 :       m = (f + t) / 2;
     734                 :  100686000 :       if (defs[m].dfs_num <= s)
     735                 :            :         f = m;
     736                 :            :       else
     737                 :   74275100 :         t = m;
     738                 :            :     }
     739                 :            : 
     740                 :   20105400 :   return defs[f].bb_index;
     741                 :            : }
     742                 :            : 
     743                 :            : /* Clean bits from PHIS for phi nodes whose value cannot be used in USES.
     744                 :            :    KILLS is a bitmap of blocks where the value is defined before any use.  */
     745                 :            : 
     746                 :            : static void
     747                 :   11526400 : prune_unused_phi_nodes (bitmap phis, bitmap kills, bitmap uses)
     748                 :            : {
     749                 :   11526400 :   bitmap_iterator bi;
     750                 :   11526400 :   unsigned i, b, p, u, top;
     751                 :   11526400 :   bitmap live_phis;
     752                 :   11526400 :   basic_block def_bb, use_bb;
     753                 :   11526400 :   edge e;
     754                 :   11526400 :   edge_iterator ei;
     755                 :   11526400 :   bitmap to_remove;
     756                 :   11526400 :   struct dom_dfsnum *defs;
     757                 :   11526400 :   unsigned n_defs, adef;
     758                 :            : 
     759                 :   11526400 :   if (bitmap_empty_p (uses))
     760                 :            :     {
     761                 :    2892480 :       bitmap_clear (phis);
     762                 :   10119000 :       return;
     763                 :            :     }
     764                 :            : 
     765                 :            :   /* The phi must dominate a use, or an argument of a live phi.  Also, we
     766                 :            :      do not create any phi nodes in def blocks, unless they are also livein.  */
     767                 :    8633950 :   to_remove = BITMAP_ALLOC (NULL);
     768                 :    8633950 :   bitmap_and_compl (to_remove, kills, uses);
     769                 :    8633950 :   bitmap_and_compl_into (phis, to_remove);
     770                 :    8633950 :   if (bitmap_empty_p (phis))
     771                 :            :     {
     772                 :    4334020 :       BITMAP_FREE (to_remove);
     773                 :    4334020 :       return;
     774                 :            :     }
     775                 :            : 
     776                 :            :   /* We want to remove the unnecessary phi nodes, but we do not want to compute
     777                 :            :      liveness information, as that may be linear in the size of CFG, and if
     778                 :            :      there are lot of different variables to rewrite, this may lead to quadratic
     779                 :            :      behavior.
     780                 :            : 
     781                 :            :      Instead, we basically emulate standard dce.  We put all uses to worklist,
     782                 :            :      then for each of them find the nearest def that dominates them.  If this
     783                 :            :      def is a phi node, we mark it live, and if it was not live before, we
     784                 :            :      add the predecessors of its basic block to the worklist.
     785                 :            : 
     786                 :            :      To quickly locate the nearest def that dominates use, we use dfs numbering
     787                 :            :      of the dominance tree (that is already available in order to speed up
     788                 :            :      queries).  For each def, we have the interval given by the dfs number on
     789                 :            :      entry to and on exit from the corresponding subtree in the dominance tree.
     790                 :            :      The nearest dominator for a given use is the smallest of these intervals
     791                 :            :      that contains entry and exit dfs numbers for the basic block with the use.
     792                 :            :      If we store the bounds for all the uses to an array and sort it, we can
     793                 :            :      locate the nearest dominating def in logarithmic time by binary search.*/
     794                 :    4299930 :   bitmap_ior (to_remove, kills, phis);
     795                 :    4299930 :   n_defs = bitmap_count_bits (to_remove);
     796                 :    4299930 :   defs = XNEWVEC (struct dom_dfsnum, 2 * n_defs + 1);
     797                 :    4299930 :   defs[0].bb_index = 1;
     798                 :    4299930 :   defs[0].dfs_num = 0;
     799                 :    4299930 :   adef = 1;
     800                 :   31530100 :   EXECUTE_IF_SET_IN_BITMAP (to_remove, 0, i, bi)
     801                 :            :     {
     802                 :   27230200 :       def_bb = BASIC_BLOCK_FOR_FN (cfun, i);
     803                 :   27230200 :       defs[adef].bb_index = i;
     804                 :   27230200 :       defs[adef].dfs_num = bb_dom_dfs_in (CDI_DOMINATORS, def_bb);
     805                 :   27230200 :       defs[adef + 1].bb_index = i;
     806                 :   27230200 :       defs[adef + 1].dfs_num = bb_dom_dfs_out (CDI_DOMINATORS, def_bb);
     807                 :   27230200 :       adef += 2;
     808                 :            :     }
     809                 :    4299930 :   BITMAP_FREE (to_remove);
     810                 :    4299930 :   gcc_assert (adef == 2 * n_defs + 1);
     811                 :    4299930 :   qsort (defs, adef, sizeof (struct dom_dfsnum), cmp_dfsnum);
     812                 :    4299930 :   gcc_assert (defs[0].bb_index == 1);
     813                 :            : 
     814                 :            :   /* Now each DEFS entry contains the number of the basic block to that the
     815                 :            :      dfs number corresponds.  Change them to the number of basic block that
     816                 :            :      corresponds to the interval following the dfs number.  Also, for the
     817                 :            :      dfs_out numbers, increase the dfs number by one (so that it corresponds
     818                 :            :      to the start of the following interval, not to the end of the current
     819                 :            :      one).  We use WORKLIST as a stack.  */
     820                 :    8599850 :   auto_vec<int> worklist (n_defs + 1);
     821                 :    4299930 :   worklist.quick_push (1);
     822                 :    4299930 :   top = 1;
     823                 :    4299930 :   n_defs = 1;
     824                 :   58760400 :   for (i = 1; i < adef; i++)
     825                 :            :     {
     826                 :   54460400 :       b = defs[i].bb_index;
     827                 :   54460400 :       if (b == top)
     828                 :            :         {
     829                 :            :           /* This is a closing element.  Interval corresponding to the top
     830                 :            :              of the stack after removing it follows.  */
     831                 :   27230200 :           worklist.pop ();
     832                 :   27230200 :           top = worklist[worklist.length () - 1];
     833                 :   27230200 :           defs[n_defs].bb_index = top;
     834                 :   27230200 :           defs[n_defs].dfs_num = defs[i].dfs_num + 1;
     835                 :            :         }
     836                 :            :       else
     837                 :            :         {
     838                 :            :           /* Opening element.  Nothing to do, just push it to the stack and move
     839                 :            :              it to the correct position.  */
     840                 :   27230200 :           defs[n_defs].bb_index = defs[i].bb_index;
     841                 :   27230200 :           defs[n_defs].dfs_num = defs[i].dfs_num;
     842                 :   27230200 :           worklist.quick_push (b);
     843                 :   27230200 :           top = b;
     844                 :            :         }
     845                 :            : 
     846                 :            :       /* If this interval starts at the same point as the previous one, cancel
     847                 :            :          the previous one.  */
     848                 :   54460400 :       if (defs[n_defs].dfs_num == defs[n_defs - 1].dfs_num)
     849                 :    6434830 :         defs[n_defs - 1].bb_index = defs[n_defs].bb_index;
     850                 :            :       else
     851                 :   48025600 :         n_defs++;
     852                 :            :     }
     853                 :    4299930 :   worklist.pop ();
     854                 :    4299930 :   gcc_assert (worklist.is_empty ());
     855                 :            : 
     856                 :            :   /* Now process the uses.  */
     857                 :    4299930 :   live_phis = BITMAP_ALLOC (NULL);
     858                 :   25173500 :   EXECUTE_IF_SET_IN_BITMAP (uses, 0, i, bi)
     859                 :            :     {
     860                 :   20873600 :       worklist.safe_push (i);
     861                 :            :     }
     862                 :            : 
     863                 :   28833000 :   while (!worklist.is_empty ())
     864                 :            :     {
     865                 :   24533100 :       b = worklist.pop ();
     866                 :   24533100 :       if (b == ENTRY_BLOCK)
     867                 :      15605 :         continue;
     868                 :            : 
     869                 :            :       /* If there is a phi node in USE_BB, it is made live.  Otherwise,
     870                 :            :          find the def that dominates the immediate dominator of USE_BB
     871                 :            :          (the kill in USE_BB does not dominate the use).  */
     872                 :   24517500 :       if (bitmap_bit_p (phis, b))
     873                 :            :         p = b;
     874                 :            :       else
     875                 :            :         {
     876                 :   60316200 :           use_bb = get_immediate_dominator (CDI_DOMINATORS,
     877                 :   20105400 :                                             BASIC_BLOCK_FOR_FN (cfun, b));
     878                 :   20105400 :           p = find_dfsnum_interval (defs, n_defs,
     879                 :            :                                     bb_dom_dfs_in (CDI_DOMINATORS, use_bb));
     880                 :   20105400 :           if (!bitmap_bit_p (phis, p))
     881                 :   14203500 :             continue;
     882                 :            :         }
     883                 :            : 
     884                 :            :       /* If the phi node is already live, there is nothing to do.  */
     885                 :   10314000 :       if (!bitmap_set_bit (live_phis, p))
     886                 :    4790920 :         continue;
     887                 :            : 
     888                 :            :       /* Add the new uses to the worklist.  */
     889                 :    5523040 :       def_bb = BASIC_BLOCK_FOR_FN (cfun, p);
     890                 :   19422600 :       FOR_EACH_EDGE (e, ei, def_bb->preds)
     891                 :            :         {
     892                 :   13899500 :           u = e->src->index;
     893                 :   13899500 :           if (bitmap_bit_p (uses, u))
     894                 :    6832590 :             continue;
     895                 :            : 
     896                 :            :           /* In case there is a kill directly in the use block, do not record
     897                 :            :              the use (this is also necessary for correctness, as we assume that
     898                 :            :              uses dominated by a def directly in their block have been filtered
     899                 :            :              out before).  */
     900                 :    7066920 :           if (bitmap_bit_p (kills, u))
     901                 :    3407450 :             continue;
     902                 :            : 
     903                 :    3659470 :           bitmap_set_bit (uses, u);
     904                 :    3659470 :           worklist.safe_push (u);
     905                 :            :         }
     906                 :            :     }
     907                 :            : 
     908                 :    4299930 :   bitmap_copy (phis, live_phis);
     909                 :    4299930 :   BITMAP_FREE (live_phis);
     910                 :    4299930 :   free (defs);
     911                 :            : }
     912                 :            : 
     913                 :            : /* Return the set of blocks where variable VAR is defined and the blocks
     914                 :            :    where VAR is live on entry (livein).  Return NULL, if no entry is
     915                 :            :    found in DEF_BLOCKS.  */
     916                 :            : 
     917                 :            : static inline def_blocks *
     918                 :   21323400 : find_def_blocks_for (tree var)
     919                 :            : {
     920                 :   42646800 :   def_blocks *p = &get_common_info (var)->def_blocks;
     921                 :   21323400 :   if (!p->def_blocks)
     922                 :          0 :     return NULL;
     923                 :            :   return p;
     924                 :            : }
     925                 :            : 
     926                 :            : 
     927                 :            : /* Marks phi node PHI in basic block BB for rewrite.  */
     928                 :            : 
     929                 :            : static void
     930                 :   21625600 : mark_phi_for_rewrite (basic_block bb, gphi *phi)
     931                 :            : {
     932                 :   21625600 :   vec<gphi *> phis;
     933                 :   21625600 :   unsigned n, idx = bb->index;
     934                 :            : 
     935                 :   21625600 :   if (rewrite_uses_p (phi))
     936                 :   11280300 :     return;
     937                 :            : 
     938                 :   13397000 :   set_rewrite_uses (phi, true);
     939                 :            : 
     940                 :   13397000 :   if (!blocks_with_phis_to_rewrite)
     941                 :            :     return;
     942                 :            : 
     943                 :   10345300 :   if (bitmap_set_bit (blocks_with_phis_to_rewrite, idx))
     944                 :            :     {
     945                 :    8088930 :       n = (unsigned) last_basic_block_for_fn (cfun) + 1;
     946                 :   16177900 :       if (phis_to_rewrite.length () < n)
     947                 :     163046 :         phis_to_rewrite.safe_grow_cleared (n);
     948                 :            : 
     949                 :    8088930 :       phis = phis_to_rewrite[idx];
     950                 :    8088930 :       gcc_assert (!phis.exists ());
     951                 :    8088930 :       phis.create (10);
     952                 :            :     }
     953                 :            :   else
     954                 :    2256400 :     phis = phis_to_rewrite[idx];
     955                 :            : 
     956                 :   10345300 :   phis.safe_push (phi);
     957                 :   10345300 :   phis_to_rewrite[idx] = phis;
     958                 :            : }
     959                 :            : 
     960                 :            : /* Insert PHI nodes for variable VAR using the iterated dominance
     961                 :            :    frontier given in PHI_INSERTION_POINTS.  If UPDATE_P is true, this
     962                 :            :    function assumes that the caller is incrementally updating the
     963                 :            :    existing SSA form, in which case VAR may be an SSA name instead of
     964                 :            :    a symbol.
     965                 :            : 
     966                 :            :    PHI_INSERTION_POINTS is updated to reflect nodes that already had a
     967                 :            :    PHI node for VAR.  On exit, only the nodes that received a PHI node
     968                 :            :    for VAR will be present in PHI_INSERTION_POINTS.  */
     969                 :            : 
     970                 :            : static void
     971                 :   11526400 : insert_phi_nodes_for (tree var, bitmap phi_insertion_points, bool update_p)
     972                 :            : {
     973                 :   11526400 :   unsigned bb_index;
     974                 :   11526400 :   edge e;
     975                 :   11526400 :   gphi *phi;
     976                 :   11526400 :   basic_block bb;
     977                 :   11526400 :   bitmap_iterator bi;
     978                 :   11526400 :   def_blocks *def_map = find_def_blocks_for (var);
     979                 :            : 
     980                 :            :   /* Remove the blocks where we already have PHI nodes for VAR.  */
     981                 :   11526400 :   bitmap_and_compl_into (phi_insertion_points, def_map->phi_blocks);
     982                 :            : 
     983                 :            :   /* Remove obviously useless phi nodes.  */
     984                 :   11526400 :   prune_unused_phi_nodes (phi_insertion_points, def_map->def_blocks,
     985                 :            :                           def_map->livein_blocks);
     986                 :            : 
     987                 :            :   /* And insert the PHI nodes.  */
     988                 :   17049500 :   EXECUTE_IF_SET_IN_BITMAP (phi_insertion_points, 0, bb_index, bi)
     989                 :            :     {
     990                 :    5523040 :       bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
     991                 :    5523040 :       if (update_p)
     992                 :    2471390 :         mark_block_for_update (bb);
     993                 :            : 
     994                 :    5523040 :       if (dump_file && (dump_flags & TDF_DETAILS))
     995                 :            :         {
     996                 :       1434 :           fprintf (dump_file, "creating PHI node in block #%d for ", bb_index);
     997                 :       1434 :           print_generic_expr (dump_file, var, TDF_SLIM);
     998                 :       1434 :           fprintf (dump_file, "\n");
     999                 :            :         }
    1000                 :    5523040 :       phi = NULL;
    1001                 :            : 
    1002                 :    5523040 :       if (TREE_CODE (var) == SSA_NAME)
    1003                 :            :         {
    1004                 :            :           /* If we are rewriting SSA names, create the LHS of the PHI
    1005                 :            :              node by duplicating VAR.  This is useful in the case of
    1006                 :            :              pointers, to also duplicate pointer attributes (alias
    1007                 :            :              information, in particular).  */
    1008                 :    1300720 :           edge_iterator ei;
    1009                 :    1300720 :           tree new_lhs;
    1010                 :            : 
    1011                 :    1300720 :           gcc_checking_assert (update_p);
    1012                 :    1300720 :           new_lhs = duplicate_ssa_name (var, NULL);
    1013                 :    1300720 :           phi = create_phi_node (new_lhs, bb);
    1014                 :    1300720 :           add_new_name_mapping (new_lhs, var);
    1015                 :            : 
    1016                 :            :           /* Add VAR to every argument slot of PHI.  We need VAR in
    1017                 :            :              every argument so that rewrite_update_phi_arguments knows
    1018                 :            :              which name is this PHI node replacing.  If VAR is a
    1019                 :            :              symbol marked for renaming, this is not necessary, the
    1020                 :            :              renamer will use the symbol on the LHS to get its
    1021                 :            :              reaching definition.  */
    1022                 :    4032560 :           FOR_EACH_EDGE (e, ei, bb->preds)
    1023                 :    2731840 :             add_phi_arg (phi, var, e, UNKNOWN_LOCATION);
    1024                 :            :         }
    1025                 :            :       else
    1026                 :            :         {
    1027                 :    4222330 :           tree tracked_var;
    1028                 :            : 
    1029                 :    4222330 :           gcc_checking_assert (DECL_P (var));
    1030                 :    4222330 :           phi = create_phi_node (var, bb);
    1031                 :            : 
    1032                 :    4222330 :           tracked_var = target_for_debug_bind (var);
    1033                 :    4222330 :           if (tracked_var)
    1034                 :            :             {
    1035                 :     415449 :               gimple *note = gimple_build_debug_bind (tracked_var,
    1036                 :            :                                                       PHI_RESULT (phi),
    1037                 :            :                                                      phi);
    1038                 :     415449 :               gimple_stmt_iterator si = gsi_after_labels (bb);
    1039                 :     415449 :               gsi_insert_before (&si, note, GSI_SAME_STMT);
    1040                 :            :             }
    1041                 :            :         }
    1042                 :            : 
    1043                 :            :       /* Mark this PHI node as interesting for update_ssa.  */
    1044                 :    5523040 :       set_register_defs (phi, true);
    1045                 :    5523040 :       mark_phi_for_rewrite (bb, phi);
    1046                 :            :     }
    1047                 :   11526400 : }
    1048                 :            : 
    1049                 :            : /* Sort var_infos after DECL_UID of their var.  */
    1050                 :            : 
    1051                 :            : static int
    1052                 :   40038000 : insert_phi_nodes_compare_var_infos (const void *a, const void *b)
    1053                 :            : {
    1054                 :   40038000 :   const var_info *defa = *(var_info * const *)a;
    1055                 :   40038000 :   const var_info *defb = *(var_info * const *)b;
    1056                 :   40038000 :   if (DECL_UID (defa->var) < DECL_UID (defb->var))
    1057                 :            :     return -1;
    1058                 :            :   else
    1059                 :   18710000 :     return 1;
    1060                 :            : }
    1061                 :            : 
    1062                 :            : /* Insert PHI nodes at the dominance frontier of blocks with variable
    1063                 :            :    definitions.  DFS contains the dominance frontier information for
    1064                 :            :    the flowgraph.  */
    1065                 :            : 
    1066                 :            : static void
    1067                 :    1847060 : insert_phi_nodes (bitmap_head *dfs)
    1068                 :            : {
    1069                 :    1847060 :   hash_table<var_info_hasher>::iterator hi;
    1070                 :    1847060 :   unsigned i;
    1071                 :    1847060 :   var_info *info;
    1072                 :            : 
    1073                 :    1847060 :   timevar_push (TV_TREE_INSERT_PHI_NODES);
    1074                 :            : 
    1075                 :            :   /* When the gimplifier introduces SSA names it cannot easily avoid
    1076                 :            :      situations where abnormal edges added by CFG construction break
    1077                 :            :      the use-def dominance requirement.  For this case rewrite SSA
    1078                 :            :      names with broken use-def dominance out-of-SSA and register them
    1079                 :            :      for PHI insertion.  We only need to do this if abnormal edges
    1080                 :            :      can appear in the function.  */
    1081                 :    1847060 :   tree name;
    1082                 :    1847060 :   if (cfun->calls_setjmp
    1083                 :    1847060 :       || cfun->has_nonlocal_label)
    1084                 :       6695 :     FOR_EACH_SSA_NAME (i, name, cfun)
    1085                 :            :       {
    1086                 :       5068 :         gimple *def_stmt = SSA_NAME_DEF_STMT (name);
    1087                 :       5068 :         if (SSA_NAME_IS_DEFAULT_DEF (name))
    1088                 :          0 :           continue;
    1089                 :            : 
    1090                 :       5068 :         basic_block def_bb = gimple_bb (def_stmt);
    1091                 :       5068 :         imm_use_iterator it;
    1092                 :       5068 :         gimple *use_stmt;
    1093                 :       5068 :         bool need_phis = false;
    1094                 :      10205 :         FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
    1095                 :            :           {
    1096                 :       5137 :             basic_block use_bb = gimple_bb (use_stmt);
    1097                 :       5137 :             if (use_bb != def_bb
    1098                 :       5137 :                 && ! dominated_by_p (CDI_DOMINATORS, use_bb, def_bb))
    1099                 :            :               need_phis = true;
    1100                 :            :           }
    1101                 :       5068 :         if (need_phis)
    1102                 :            :           {
    1103                 :         52 :             tree var = create_tmp_reg (TREE_TYPE (name));
    1104                 :         52 :             use_operand_p use_p;
    1105                 :        104 :             FOR_EACH_IMM_USE_STMT (use_stmt, it, name)
    1106                 :            :               {
    1107                 :         52 :                 basic_block use_bb = gimple_bb (use_stmt);
    1108                 :        156 :                 FOR_EACH_IMM_USE_ON_STMT (use_p, it)
    1109                 :         52 :                     SET_USE (use_p, var);
    1110                 :         52 :                 update_stmt (use_stmt);
    1111                 :         52 :                 set_livein_block (var, use_bb);
    1112                 :         52 :                 set_rewrite_uses (use_stmt, true);
    1113                 :         52 :                 bitmap_set_bit (interesting_blocks, use_bb->index);
    1114                 :            :               }
    1115                 :         52 :             def_operand_p def_p;
    1116                 :         52 :             ssa_op_iter dit;
    1117                 :        104 :             FOR_EACH_SSA_DEF_OPERAND (def_p, def_stmt, dit, SSA_OP_DEF)
    1118                 :         52 :               if (DEF_FROM_PTR (def_p) == name)
    1119                 :         52 :                 SET_DEF (def_p, var);
    1120                 :         52 :             update_stmt (def_stmt);
    1121                 :         52 :             set_def_block (var, def_bb, false);
    1122                 :         52 :             set_register_defs (def_stmt, true);
    1123                 :         52 :             bitmap_set_bit (interesting_blocks, def_bb->index);
    1124                 :         52 :             release_ssa_name (name);
    1125                 :            :           }
    1126                 :            :       }
    1127                 :            : 
    1128                 :    1847060 :   auto_vec<var_info *> vars (var_infos->elements ());
    1129                 :   15032200 :   FOR_EACH_HASH_TABLE_ELEMENT (*var_infos, info, var_info_p, hi)
    1130                 :   11338100 :     if (info->info.need_phi_state != NEED_PHI_STATE_NO)
    1131                 :   16998400 :       vars.quick_push (info);
    1132                 :            : 
    1133                 :            :   /* Do two stages to avoid code generation differences for UID
    1134                 :            :      differences but no UID ordering differences.  */
    1135                 :    1847060 :   vars.qsort (insert_phi_nodes_compare_var_infos);
    1136                 :            : 
    1137                 :    7507290 :   FOR_EACH_VEC_ELT (vars, i, info)
    1138                 :            :     {
    1139                 :    5660230 :       bitmap idf = compute_idf (info->info.def_blocks.def_blocks, dfs);
    1140                 :    5660230 :       insert_phi_nodes_for (info->var, idf, false);
    1141                 :    5660230 :       BITMAP_FREE (idf);
    1142                 :            :     }
    1143                 :            : 
    1144                 :    1847460 :   timevar_pop (TV_TREE_INSERT_PHI_NODES);
    1145                 :    1847060 : }
    1146                 :            : 
    1147                 :            : 
    1148                 :            : /* Push SYM's current reaching definition into BLOCK_DEFS_STACK and
    1149                 :            :    register DEF (an SSA_NAME) to be a new definition for SYM.  */
    1150                 :            : 
    1151                 :            : static void
    1152                 :   26455900 : register_new_def (tree def, tree sym)
    1153                 :            : {
    1154                 :   26455900 :   common_info *info = get_common_info (sym);
    1155                 :   26455900 :   tree currdef;
    1156                 :            : 
    1157                 :            :   /* If this variable is set in a single basic block and all uses are
    1158                 :            :      dominated by the set(s) in that single basic block, then there is
    1159                 :            :      no reason to record anything for this variable in the block local
    1160                 :            :      definition stacks.  Doing so just wastes time and memory.
    1161                 :            : 
    1162                 :            :      This is the same test to prune the set of variables which may
    1163                 :            :      need PHI nodes.  So we just use that information since it's already
    1164                 :            :      computed and available for us to use.  */
    1165                 :   26455900 :   if (info->need_phi_state == NEED_PHI_STATE_NO)
    1166                 :            :     {
    1167                 :    5677890 :       info->current_def = def;
    1168                 :    5677890 :       return;
    1169                 :            :     }
    1170                 :            : 
    1171                 :   20778000 :   currdef = info->current_def;
    1172                 :            : 
    1173                 :            :   /* If SYM is not a GIMPLE register, then CURRDEF may be a name whose
    1174                 :            :      SSA_NAME_VAR is not necessarily SYM.  In this case, also push SYM
    1175                 :            :      in the stack so that we know which symbol is being defined by
    1176                 :            :      this SSA name when we unwind the stack.  */
    1177                 :   20778000 :   if (currdef && !is_gimple_reg (sym))
    1178                 :   14309200 :     block_defs_stack.safe_push (sym);
    1179                 :            : 
    1180                 :            :   /* Push the current reaching definition into BLOCK_DEFS_STACK.  This
    1181                 :            :      stack is later used by the dominator tree callbacks to restore
    1182                 :            :      the reaching definitions for all the variables defined in the
    1183                 :            :      block after a recursive visit to all its immediately dominated
    1184                 :            :      blocks.  If there is no current reaching definition, then just
    1185                 :            :      record the underlying _DECL node.  */
    1186                 :   24837900 :   block_defs_stack.safe_push (currdef ? currdef : sym);
    1187                 :            : 
    1188                 :            :   /* Set the current reaching definition for SYM to be DEF.  */
    1189                 :   20778000 :   info->current_def = def;
    1190                 :            : }
    1191                 :            : 
    1192                 :            : 
    1193                 :            : /* Perform a depth-first traversal of the dominator tree looking for
    1194                 :            :    variables to rename.  BB is the block where to start searching.
    1195                 :            :    Renaming is a five step process:
    1196                 :            : 
    1197                 :            :    1- Every definition made by PHI nodes at the start of the blocks is
    1198                 :            :       registered as the current definition for the corresponding variable.
    1199                 :            : 
    1200                 :            :    2- Every statement in BB is rewritten.  USE and VUSE operands are
    1201                 :            :       rewritten with their corresponding reaching definition.  DEF and
    1202                 :            :       VDEF targets are registered as new definitions.
    1203                 :            : 
    1204                 :            :    3- All the PHI nodes in successor blocks of BB are visited.  The
    1205                 :            :       argument corresponding to BB is replaced with its current reaching
    1206                 :            :       definition.
    1207                 :            : 
    1208                 :            :    4- Recursively rewrite every dominator child block of BB.
    1209                 :            : 
    1210                 :            :    5- Restore (in reverse order) the current reaching definition for every
    1211                 :            :       new definition introduced in this block.  This is done so that when
    1212                 :            :       we return from the recursive call, all the current reaching
    1213                 :            :       definitions are restored to the names that were valid in the
    1214                 :            :       dominator parent of BB.  */
    1215                 :            : 
    1216                 :            : /* Return the current definition for variable VAR.  If none is found,
    1217                 :            :    create a new SSA name to act as the zeroth definition for VAR.  */
    1218                 :            : 
    1219                 :            : static tree
    1220                 :  155444000 : get_reaching_def (tree var)
    1221                 :            : {
    1222                 :  155444000 :   common_info *info = get_common_info (var);
    1223                 :  155444000 :   tree currdef;
    1224                 :            : 
    1225                 :            :   /* Lookup the current reaching definition for VAR.  */
    1226                 :  155444000 :   currdef = info->current_def;
    1227                 :            : 
    1228                 :            :   /* If there is no reaching definition for VAR, create and register a
    1229                 :            :      default definition for it (if needed).  */
    1230                 :  155444000 :   if (currdef == NULL_TREE)
    1231                 :            :     {
    1232                 :   15838300 :       tree sym = DECL_P (var) ? var : SSA_NAME_VAR (var);
    1233                 :   13838600 :       if (! sym)
    1234                 :          2 :         sym = create_tmp_reg (TREE_TYPE (var));
    1235                 :   13838600 :       currdef = get_or_create_ssa_default_def (cfun, sym);
    1236                 :            :     }
    1237                 :            : 
    1238                 :            :   /* Return the current reaching definition for VAR, or the default
    1239                 :            :      definition, if we had to create one.  */
    1240                 :  155444000 :   return currdef;
    1241                 :            : }
    1242                 :            : 
    1243                 :            : 
    1244                 :            : /* Helper function for rewrite_stmt.  Rewrite uses in a debug stmt.  */
    1245                 :            : 
    1246                 :            : static void
    1247                 :          0 : rewrite_debug_stmt_uses (gimple *stmt)
    1248                 :            : {
    1249                 :          0 :   use_operand_p use_p;
    1250                 :          0 :   ssa_op_iter iter;
    1251                 :          0 :   bool update = false;
    1252                 :            : 
    1253                 :          0 :   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
    1254                 :            :     {
    1255                 :          0 :       tree var = USE_FROM_PTR (use_p), def;
    1256                 :          0 :       common_info *info = get_common_info (var);
    1257                 :          0 :       gcc_checking_assert (DECL_P (var));
    1258                 :          0 :       def = info->current_def;
    1259                 :          0 :       if (!def)
    1260                 :            :         {
    1261                 :          0 :           if (TREE_CODE (var) == PARM_DECL
    1262                 :          0 :               && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
    1263                 :            :             {
    1264                 :          0 :               gimple_stmt_iterator gsi
    1265                 :            :                 =
    1266                 :          0 :              gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
    1267                 :            :               int lim;
    1268                 :            :               /* Search a few source bind stmts at the start of first bb to
    1269                 :            :                  see if a DEBUG_EXPR_DECL can't be reused.  */
    1270                 :          0 :               for (lim = 32;
    1271                 :          0 :                    !gsi_end_p (gsi) && lim > 0;
    1272                 :          0 :                    gsi_next (&gsi), lim--)
    1273                 :            :                 {
    1274                 :          0 :                   gimple *gstmt = gsi_stmt (gsi);
    1275                 :          0 :                   if (!gimple_debug_source_bind_p (gstmt))
    1276                 :            :                     break;
    1277                 :          0 :                   if (gimple_debug_source_bind_get_value (gstmt) == var)
    1278                 :            :                     {
    1279                 :          0 :                       def = gimple_debug_source_bind_get_var (gstmt);
    1280                 :          0 :                       if (TREE_CODE (def) == DEBUG_EXPR_DECL)
    1281                 :            :                         break;
    1282                 :            :                       else
    1283                 :            :                         def = NULL_TREE;
    1284                 :            :                     }
    1285                 :            :                 }
    1286                 :            :               /* If not, add a new source bind stmt.  */
    1287                 :          0 :               if (def == NULL_TREE)
    1288                 :            :                 {
    1289                 :          0 :                   gimple *def_temp;
    1290                 :          0 :                   def = make_node (DEBUG_EXPR_DECL);
    1291                 :          0 :                   def_temp = gimple_build_debug_source_bind (def, var, NULL);
    1292                 :          0 :                   DECL_ARTIFICIAL (def) = 1;
    1293                 :          0 :                   TREE_TYPE (def) = TREE_TYPE (var);
    1294                 :          0 :                   SET_DECL_MODE (def, DECL_MODE (var));
    1295                 :          0 :                   gsi =
    1296                 :          0 :                  gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
    1297                 :          0 :                   gsi_insert_before (&gsi, def_temp, GSI_SAME_STMT);
    1298                 :            :                 }
    1299                 :          0 :               update = true;
    1300                 :            :             }
    1301                 :            :         }
    1302                 :            :       else
    1303                 :            :         {
    1304                 :            :           /* Check if info->current_def can be trusted.  */
    1305                 :          0 :           basic_block bb = gimple_bb (stmt);
    1306                 :          0 :           basic_block def_bb
    1307                 :          0 :               = SSA_NAME_IS_DEFAULT_DEF (def)
    1308                 :          0 :               ? NULL : gimple_bb (SSA_NAME_DEF_STMT (def));
    1309                 :            : 
    1310                 :            :           /* If definition is in current bb, it is fine.  */
    1311                 :          0 :           if (bb == def_bb)
    1312                 :            :             ;
    1313                 :            :           /* If definition bb doesn't dominate the current bb,
    1314                 :            :              it can't be used.  */
    1315                 :          0 :           else if (def_bb && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
    1316                 :            :             def = NULL;
    1317                 :            :           /* If there is just one definition and dominates the current
    1318                 :            :              bb, it is fine.  */
    1319                 :          0 :           else if (info->need_phi_state == NEED_PHI_STATE_NO)
    1320                 :            :             ;
    1321                 :            :           else
    1322                 :            :             {
    1323                 :          0 :               def_blocks *db_p = get_def_blocks_for (info);
    1324                 :            : 
    1325                 :            :               /* If there are some non-debug uses in the current bb,
    1326                 :            :                  it is fine.  */
    1327                 :          0 :               if (bitmap_bit_p (db_p->livein_blocks, bb->index))
    1328                 :            :                 ;
    1329                 :            :               /* Otherwise give up for now.  */
    1330                 :            :               else
    1331                 :            :                 def = NULL;
    1332                 :            :             }
    1333                 :            :         }
    1334                 :          0 :       if (def == NULL)
    1335                 :            :         {
    1336                 :          0 :           gimple_debug_bind_reset_value (stmt);
    1337                 :          0 :           update_stmt (stmt);
    1338                 :          0 :           return;
    1339                 :            :         }
    1340                 :          0 :       SET_USE (use_p, def);
    1341                 :            :     }
    1342                 :          0 :   if (update)
    1343                 :          0 :     update_stmt (stmt);
    1344                 :            : }
    1345                 :            : 
    1346                 :            : /* SSA Rewriting Step 2.  Rewrite every variable used in each statement in
    1347                 :            :    the block with its immediate reaching definitions.  Update the current
    1348                 :            :    definition of a variable when a new real or virtual definition is found.  */
    1349                 :            : 
    1350                 :            : static void
    1351                 :   44337600 : rewrite_stmt (gimple_stmt_iterator *si)
    1352                 :            : {
    1353                 :   44337600 :   use_operand_p use_p;
    1354                 :   44337600 :   def_operand_p def_p;
    1355                 :   44337600 :   ssa_op_iter iter;
    1356                 :   44337600 :   gimple *stmt = gsi_stmt (*si);
    1357                 :            : 
    1358                 :            :   /* If mark_def_sites decided that we don't need to rewrite this
    1359                 :            :      statement, ignore it.  */
    1360                 :   44337600 :   gcc_assert (blocks_to_update == NULL);
    1361                 :   44337600 :   if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
    1362                 :   10007100 :     return;
    1363                 :            : 
    1364                 :   34330400 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1365                 :            :     {
    1366                 :          4 :       fprintf (dump_file, "Renaming statement ");
    1367                 :          4 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1368                 :          4 :       fprintf (dump_file, "\n");
    1369                 :            :     }
    1370                 :            : 
    1371                 :            :   /* Step 1.  Rewrite USES in the statement.  */
    1372                 :   34330400 :   if (rewrite_uses_p (stmt))
    1373                 :            :     {
    1374                 :   31537000 :       if (is_gimple_debug (stmt))
    1375                 :          0 :         rewrite_debug_stmt_uses (stmt);
    1376                 :            :       else
    1377                 :   77440000 :         FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
    1378                 :            :           {
    1379                 :   45903000 :             tree var = USE_FROM_PTR (use_p);
    1380                 :   45903000 :             if (TREE_CODE (var) == SSA_NAME)
    1381                 :    6088600 :               continue;
    1382                 :   39814400 :             gcc_checking_assert (DECL_P (var));
    1383                 :   39814400 :             SET_USE (use_p, get_reaching_def (var));
    1384                 :            :           }
    1385                 :            :     }
    1386                 :            : 
    1387                 :            :   /* Step 2.  Register the statement's DEF operands.  */
    1388                 :   34330400 :   if (register_defs_p (stmt))
    1389                 :   46270800 :     FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
    1390                 :            :       {
    1391                 :   24219700 :         tree var = DEF_FROM_PTR (def_p);
    1392                 :   24219700 :         tree name;
    1393                 :   24219700 :         tree tracked_var;
    1394                 :            : 
    1395                 :   24219700 :         if (TREE_CODE (var) == SSA_NAME)
    1396                 :     815439 :           continue;
    1397                 :   23404300 :         gcc_checking_assert (DECL_P (var));
    1398                 :            : 
    1399                 :   23404300 :         if (gimple_clobber_p (stmt)
    1400                 :   23404300 :             && is_gimple_reg (var))
    1401                 :            :           {
    1402                 :            :             /* If we rewrite a DECL into SSA form then drop its
    1403                 :            :                clobber stmts and replace uses with a new default def.  */
    1404                 :      94372 :             gcc_checking_assert (VAR_P (var) && !gimple_vdef (stmt));
    1405                 :      47186 :             gsi_replace (si, gimple_build_nop (), true);
    1406                 :      47186 :             register_new_def (get_or_create_ssa_default_def (cfun, var), var);
    1407                 :      47186 :             break;
    1408                 :            :           }
    1409                 :            : 
    1410                 :   23357100 :         name = make_ssa_name (var, stmt);
    1411                 :   23357100 :         SET_DEF (def_p, name);
    1412                 :   23357100 :         register_new_def (DEF_FROM_PTR (def_p), var);
    1413                 :            : 
    1414                 :   23357100 :         tracked_var = target_for_debug_bind (var);
    1415                 :   23357100 :         if (tracked_var)
    1416                 :            :           {
    1417                 :    1233090 :             gimple *note = gimple_build_debug_bind (tracked_var, name, stmt);
    1418                 :    1233090 :             gsi_insert_after (si, note, GSI_SAME_STMT);
    1419                 :            :           }
    1420                 :            :       }
    1421                 :            : }
    1422                 :            : 
    1423                 :            : 
    1424                 :            : /* SSA Rewriting Step 3.  Visit all the successor blocks of BB looking for
    1425                 :            :    PHI nodes.  For every PHI node found, add a new argument containing the
    1426                 :            :    current reaching definition for the variable and the edge through which
    1427                 :            :    that definition is reaching the PHI node.  */
    1428                 :            : 
    1429                 :            : static void
    1430                 :   13290300 : rewrite_add_phi_arguments (basic_block bb)
    1431                 :            : {
    1432                 :   13290300 :   edge e;
    1433                 :   13290300 :   edge_iterator ei;
    1434                 :            : 
    1435                 :   30906200 :   FOR_EACH_EDGE (e, ei, bb->succs)
    1436                 :            :     {
    1437                 :   17615900 :       gphi *phi;
    1438                 :   17615900 :       gphi_iterator gsi;
    1439                 :            : 
    1440                 :   25849200 :       for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi);
    1441                 :    8233310 :            gsi_next (&gsi))
    1442                 :            :         {
    1443                 :    8233310 :           tree currdef, res;
    1444                 :    8233310 :           location_t loc;
    1445                 :            : 
    1446                 :    8233310 :           phi = gsi.phi ();
    1447                 :    8233310 :           res = gimple_phi_result (phi);
    1448                 :   16466600 :           currdef = get_reaching_def (SSA_NAME_VAR (res));
    1449                 :            :           /* Virtual operand PHI args do not need a location.  */
    1450                 :   16466600 :           if (virtual_operand_p (res))
    1451                 :            :             loc = UNKNOWN_LOCATION;
    1452                 :            :           else
    1453                 :    2906500 :             loc = gimple_location (SSA_NAME_DEF_STMT (currdef));
    1454                 :    8233310 :           add_phi_arg (phi, currdef, e, loc);
    1455                 :            :         }
    1456                 :            :     }
    1457                 :   13290300 : }
    1458                 :            : 
    1459                 :    1847060 : class rewrite_dom_walker : public dom_walker
    1460                 :            : {
    1461                 :            : public:
    1462                 :    1847060 :   rewrite_dom_walker (cdi_direction direction)
    1463                 :    3694120 :     : dom_walker (direction, ALL_BLOCKS, NULL) {}
    1464                 :            : 
    1465                 :            :   virtual edge before_dom_children (basic_block);
    1466                 :            :   virtual void after_dom_children (basic_block);
    1467                 :            : };
    1468                 :            : 
    1469                 :            : /* SSA Rewriting Step 1.  Initialization, create a block local stack
    1470                 :            :    of reaching definitions for new SSA names produced in this block
    1471                 :            :    (BLOCK_DEFS).  Register new definitions for every PHI node in the
    1472                 :            :    block.  */
    1473                 :            : 
    1474                 :            : edge
    1475                 :   13290300 : rewrite_dom_walker::before_dom_children (basic_block bb)
    1476                 :            : {
    1477                 :   13290300 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1478                 :          6 :     fprintf (dump_file, "\n\nRenaming block #%d\n\n", bb->index);
    1479                 :            : 
    1480                 :            :   /* Mark the unwind point for this block.  */
    1481                 :   13290300 :   block_defs_stack.safe_push (NULL_TREE);
    1482                 :            : 
    1483                 :            :   /* Step 1.  Register new definitions for every PHI node in the block.
    1484                 :            :      Conceptually, all the PHI nodes are executed in parallel and each PHI
    1485                 :            :      node introduces a new version for the associated variable.  */
    1486                 :   16341900 :   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
    1487                 :    3051650 :        gsi_next (&gsi))
    1488                 :            :     {
    1489                 :    3051650 :       tree result = gimple_phi_result (gsi_stmt (gsi));
    1490                 :    6103300 :       register_new_def (result, SSA_NAME_VAR (result));
    1491                 :            :     }
    1492                 :            : 
    1493                 :            :   /* Step 2.  Rewrite every variable used in each statement in the block
    1494                 :            :      with its immediate reaching definitions.  Update the current definition
    1495                 :            :      of a variable when a new real or virtual definition is found.  */
    1496                 :   13290300 :   if (bitmap_bit_p (interesting_blocks, bb->index))
    1497                 :   66753300 :     for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
    1498                 :   44337600 :          gsi_next (&gsi))
    1499                 :   44337600 :       rewrite_stmt (&gsi);
    1500                 :            : 
    1501                 :            :   /* Step 3.  Visit all the successor blocks of BB looking for PHI nodes.
    1502                 :            :      For every PHI node found, add a new argument containing the current
    1503                 :            :      reaching definition for the variable and the edge through which that
    1504                 :            :      definition is reaching the PHI node.  */
    1505                 :   13290300 :   rewrite_add_phi_arguments (bb);
    1506                 :            : 
    1507                 :   13290300 :   return NULL;
    1508                 :            : }
    1509                 :            : 
    1510                 :            : 
    1511                 :            : 
    1512                 :            : /* Called after visiting all the statements in basic block BB and all
    1513                 :            :    of its dominator children.  Restore CURRDEFS to its original value.  */
    1514                 :            : 
    1515                 :            : void
    1516                 :   13290300 : rewrite_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
    1517                 :            : {
    1518                 :            :   /* Restore CURRDEFS to its original state.  */
    1519                 :   34068300 :   while (block_defs_stack.length () > 0)
    1520                 :            :     {
    1521                 :   34068300 :       tree tmp = block_defs_stack.pop ();
    1522                 :   34068300 :       tree saved_def, var;
    1523                 :            : 
    1524                 :   34068300 :       if (tmp == NULL_TREE)
    1525                 :            :         break;
    1526                 :            : 
    1527                 :   20778000 :       if (TREE_CODE (tmp) == SSA_NAME)
    1528                 :            :         {
    1529                 :            :           /* If we recorded an SSA_NAME, then make the SSA_NAME the
    1530                 :            :              current definition of its underlying variable.  Note that
    1531                 :            :              if the SSA_NAME is not for a GIMPLE register, the symbol
    1532                 :            :              being defined is stored in the next slot in the stack.
    1533                 :            :              This mechanism is needed because an SSA name for a
    1534                 :            :              non-register symbol may be the definition for more than
    1535                 :            :              one symbol (e.g., SFTs, aliased variables, etc).  */
    1536                 :   16718200 :           saved_def = tmp;
    1537                 :   16718200 :           var = SSA_NAME_VAR (saved_def);
    1538                 :   16718200 :           if (!is_gimple_reg (var))
    1539                 :   14309200 :             var = block_defs_stack.pop ();
    1540                 :            :         }
    1541                 :            :       else
    1542                 :            :         {
    1543                 :            :           /* If we recorded anything else, it must have been a _DECL
    1544                 :            :              node and its current reaching definition must have been
    1545                 :            :              NULL.  */
    1546                 :            :           saved_def = NULL;
    1547                 :            :           var = tmp;
    1548                 :            :         }
    1549                 :            : 
    1550                 :   20778000 :       get_common_info (var)->current_def = saved_def;
    1551                 :            :     }
    1552                 :   13290300 : }
    1553                 :            : 
    1554                 :            : 
    1555                 :            : /* Dump bitmap SET (assumed to contain VAR_DECLs) to FILE.  */
    1556                 :            : 
    1557                 :            : DEBUG_FUNCTION void
    1558                 :          0 : debug_decl_set (bitmap set)
    1559                 :            : {
    1560                 :          0 :   dump_decl_set (stderr, set);
    1561                 :          0 :   fprintf (stderr, "\n");
    1562                 :          0 : }
    1563                 :            : 
    1564                 :            : 
    1565                 :            : /* Dump the renaming stack (block_defs_stack) to FILE.  Traverse the
    1566                 :            :    stack up to a maximum of N levels.  If N is -1, the whole stack is
    1567                 :            :    dumped.  New levels are created when the dominator tree traversal
    1568                 :            :    used for renaming enters a new sub-tree.  */
    1569                 :            : 
    1570                 :            : void
    1571                 :          0 : dump_defs_stack (FILE *file, int n)
    1572                 :            : {
    1573                 :          0 :   int i, j;
    1574                 :            : 
    1575                 :          0 :   fprintf (file, "\n\nRenaming stack");
    1576                 :          0 :   if (n > 0)
    1577                 :          0 :     fprintf (file, " (up to %d levels)", n);
    1578                 :          0 :   fprintf (file, "\n\n");
    1579                 :            : 
    1580                 :          0 :   i = 1;
    1581                 :          0 :   fprintf (file, "Level %d (current level)\n", i);
    1582                 :          0 :   for (j = (int) block_defs_stack.length () - 1; j >= 0; j--)
    1583                 :            :     {
    1584                 :          0 :       tree name, var;
    1585                 :            : 
    1586                 :          0 :       name = block_defs_stack[j];
    1587                 :          0 :       if (name == NULL_TREE)
    1588                 :            :         {
    1589                 :          0 :           i++;
    1590                 :          0 :           if (n > 0 && i > n)
    1591                 :            :             break;
    1592                 :          0 :           fprintf (file, "\nLevel %d\n", i);
    1593                 :          0 :           continue;
    1594                 :            :         }
    1595                 :            : 
    1596                 :          0 :       if (DECL_P (name))
    1597                 :            :         {
    1598                 :            :           var = name;
    1599                 :            :           name = NULL_TREE;
    1600                 :            :         }
    1601                 :            :       else
    1602                 :            :         {
    1603                 :          0 :           var = SSA_NAME_VAR (name);
    1604                 :          0 :           if (!is_gimple_reg (var))
    1605                 :            :             {
    1606                 :          0 :               j--;
    1607                 :          0 :               var = block_defs_stack[j];
    1608                 :            :             }
    1609                 :            :         }
    1610                 :            : 
    1611                 :          0 :       fprintf (file, "    Previous CURRDEF (");
    1612                 :          0 :       print_generic_expr (file, var);
    1613                 :          0 :       fprintf (file, ") = ");
    1614                 :          0 :       if (name)
    1615                 :          0 :         print_generic_expr (file, name);
    1616                 :            :       else
    1617                 :          0 :         fprintf (file, "<NIL>");
    1618                 :          0 :       fprintf (file, "\n");
    1619                 :            :     }
    1620                 :          0 : }
    1621                 :            : 
    1622                 :            : 
    1623                 :            : /* Dump the renaming stack (block_defs_stack) to stderr.  Traverse the
    1624                 :            :    stack up to a maximum of N levels.  If N is -1, the whole stack is
    1625                 :            :    dumped.  New levels are created when the dominator tree traversal
    1626                 :            :    used for renaming enters a new sub-tree.  */
    1627                 :            : 
    1628                 :            : DEBUG_FUNCTION void
    1629                 :          0 : debug_defs_stack (int n)
    1630                 :            : {
    1631                 :          0 :   dump_defs_stack (stderr, n);
    1632                 :          0 : }
    1633                 :            : 
    1634                 :            : 
    1635                 :            : /* Dump the current reaching definition of every symbol to FILE.  */
    1636                 :            : 
    1637                 :            : void
    1638                 :          0 : dump_currdefs (FILE *file)
    1639                 :            : {
    1640                 :          0 :   unsigned i;
    1641                 :          0 :   tree var;
    1642                 :            : 
    1643                 :          0 :   if (symbols_to_rename.is_empty ())
    1644                 :          0 :     return;
    1645                 :            : 
    1646                 :          0 :   fprintf (file, "\n\nCurrent reaching definitions\n\n");
    1647                 :          0 :   FOR_EACH_VEC_ELT (symbols_to_rename, i, var)
    1648                 :            :     {
    1649                 :          0 :       common_info *info = get_common_info (var);
    1650                 :          0 :       fprintf (file, "CURRDEF (");
    1651                 :          0 :       print_generic_expr (file, var);
    1652                 :          0 :       fprintf (file, ") = ");
    1653                 :          0 :       if (info->current_def)
    1654                 :          0 :         print_generic_expr (file, info->current_def);
    1655                 :            :       else
    1656                 :          0 :         fprintf (file, "<NIL>");
    1657                 :          0 :       fprintf (file, "\n");
    1658                 :            :     }
    1659                 :            : }
    1660                 :            : 
    1661                 :            : 
    1662                 :            : /* Dump the current reaching definition of every symbol to stderr.  */
    1663                 :            : 
    1664                 :            : DEBUG_FUNCTION void
    1665                 :          0 : debug_currdefs (void)
    1666                 :            : {
    1667                 :          0 :   dump_currdefs (stderr);
    1668                 :          0 : }
    1669                 :            : 
    1670                 :            : 
    1671                 :            : /* Dump SSA information to FILE.  */
    1672                 :            : 
    1673                 :            : void
    1674                 :          0 : dump_tree_ssa (FILE *file)
    1675                 :            : {
    1676                 :          0 :   const char *funcname
    1677                 :          0 :     = lang_hooks.decl_printable_name (current_function_decl, 2);
    1678                 :            : 
    1679                 :          0 :   fprintf (file, "SSA renaming information for %s\n\n", funcname);
    1680                 :            : 
    1681                 :          0 :   dump_var_infos (file);
    1682                 :          0 :   dump_defs_stack (file, -1);
    1683                 :          0 :   dump_currdefs (file);
    1684                 :          0 :   dump_tree_ssa_stats (file);
    1685                 :          0 : }
    1686                 :            : 
    1687                 :            : 
    1688                 :            : /* Dump SSA information to stderr.  */
    1689                 :            : 
    1690                 :            : DEBUG_FUNCTION void
    1691                 :          0 : debug_tree_ssa (void)
    1692                 :            : {
    1693                 :          0 :   dump_tree_ssa (stderr);
    1694                 :          0 : }
    1695                 :            : 
    1696                 :            : 
    1697                 :            : /* Dump statistics for the hash table HTAB.  */
    1698                 :            : 
    1699                 :            : static void
    1700                 :         78 : htab_statistics (FILE *file, const hash_table<var_info_hasher> &htab)
    1701                 :            : {
    1702                 :         78 :   fprintf (file, "size %ld, %ld elements, %f collision/search ratio\n",
    1703                 :         78 :            (long) htab.size (),
    1704                 :         78 :            (long) htab.elements (),
    1705                 :            :            htab.collisions ());
    1706                 :         78 : }
    1707                 :            : 
    1708                 :            : 
    1709                 :            : /* Dump SSA statistics on FILE.  */
    1710                 :            : 
    1711                 :            : void
    1712                 :         78 : dump_tree_ssa_stats (FILE *file)
    1713                 :            : {
    1714                 :         78 :   if (var_infos)
    1715                 :            :     {
    1716                 :         78 :       fprintf (file, "\nHash table statistics:\n");
    1717                 :         78 :       fprintf (file, "    var_infos:   ");
    1718                 :         78 :       htab_statistics (file, *var_infos);
    1719                 :         78 :       fprintf (file, "\n");
    1720                 :            :     }
    1721                 :         78 : }
    1722                 :            : 
    1723                 :            : 
    1724                 :            : /* Dump SSA statistics on stderr.  */
    1725                 :            : 
    1726                 :            : DEBUG_FUNCTION void
    1727                 :          0 : debug_tree_ssa_stats (void)
    1728                 :            : {
    1729                 :          0 :   dump_tree_ssa_stats (stderr);
    1730                 :          0 : }
    1731                 :            : 
    1732                 :            : 
    1733                 :            : /* Callback for htab_traverse to dump the VAR_INFOS hash table.  */
    1734                 :            : 
    1735                 :            : int
    1736                 :          0 : debug_var_infos_r (var_info **slot, FILE *file)
    1737                 :            : {
    1738                 :          0 :   var_info *info = *slot;
    1739                 :            : 
    1740                 :          0 :   fprintf (file, "VAR: ");
    1741                 :          0 :   print_generic_expr (file, info->var, dump_flags);
    1742                 :          0 :   bitmap_print (file, info->info.def_blocks.def_blocks,
    1743                 :            :                 ", DEF_BLOCKS: { ", "}");
    1744                 :          0 :   bitmap_print (file, info->info.def_blocks.livein_blocks,
    1745                 :            :                 ", LIVEIN_BLOCKS: { ", "}");
    1746                 :          0 :   bitmap_print (file, info->info.def_blocks.phi_blocks,
    1747                 :            :                 ", PHI_BLOCKS: { ", "}\n");
    1748                 :            : 
    1749                 :          0 :   return 1;
    1750                 :            : }
    1751                 :            : 
    1752                 :            : 
    1753                 :            : /* Dump the VAR_INFOS hash table on FILE.  */
    1754                 :            : 
    1755                 :            : void
    1756                 :          0 : dump_var_infos (FILE *file)
    1757                 :            : {
    1758                 :          0 :   fprintf (file, "\n\nDefinition and live-in blocks:\n\n");
    1759                 :          0 :   if (var_infos)
    1760                 :          0 :     var_infos->traverse <FILE *, debug_var_infos_r> (file);
    1761                 :          0 : }
    1762                 :            : 
    1763                 :            : 
    1764                 :            : /* Dump the VAR_INFOS hash table on stderr.  */
    1765                 :            : 
    1766                 :            : DEBUG_FUNCTION void
    1767                 :          0 : debug_var_infos (void)
    1768                 :            : {
    1769                 :          0 :   dump_var_infos (stderr);
    1770                 :          0 : }
    1771                 :            : 
    1772                 :            : 
    1773                 :            : /* Register NEW_NAME to be the new reaching definition for OLD_NAME.  */
    1774                 :            : 
    1775                 :            : static inline void
    1776                 :   59768300 : register_new_update_single (tree new_name, tree old_name)
    1777                 :            : {
    1778                 :   59768300 :   common_info *info = get_common_info (old_name);
    1779                 :   59768300 :   tree currdef = info->current_def;
    1780                 :            : 
    1781                 :            :   /* Push the current reaching definition into BLOCK_DEFS_STACK.
    1782                 :            :      This stack is later used by the dominator tree callbacks to
    1783                 :            :      restore the reaching definitions for all the variables
    1784                 :            :      defined in the block after a recursive visit to all its
    1785                 :            :      immediately dominated blocks.  */
    1786                 :   59768300 :   block_defs_stack.reserve (2);
    1787                 :   59768300 :   block_defs_stack.quick_push (currdef);
    1788                 :   59768300 :   block_defs_stack.quick_push (old_name);
    1789                 :            : 
    1790                 :            :   /* Set the current reaching definition for OLD_NAME to be
    1791                 :            :      NEW_NAME.  */
    1792                 :   59768300 :   info->current_def = new_name;
    1793                 :   59768300 : }
    1794                 :            : 
    1795                 :            : 
    1796                 :            : /* Register NEW_NAME to be the new reaching definition for all the
    1797                 :            :    names in OLD_NAMES.  Used by the incremental SSA update routines to
    1798                 :            :    replace old SSA names with new ones.  */
    1799                 :            : 
    1800                 :            : static inline void
    1801                 :   12654200 : register_new_update_set (tree new_name, bitmap old_names)
    1802                 :            : {
    1803                 :   12654200 :   bitmap_iterator bi;
    1804                 :   12654200 :   unsigned i;
    1805                 :            : 
    1806                 :   25466800 :   EXECUTE_IF_SET_IN_BITMAP (old_names, 0, i, bi)
    1807                 :   12812600 :     register_new_update_single (new_name, ssa_name (i));
    1808                 :   12654200 : }
    1809                 :            : 
    1810                 :            : 
    1811                 :            : 
    1812                 :            : /* If the operand pointed to by USE_P is a name in OLD_SSA_NAMES or
    1813                 :            :    it is a symbol marked for renaming, replace it with USE_P's current
    1814                 :            :    reaching definition.  */
    1815                 :            : 
    1816                 :            : static inline void
    1817                 :  126238000 : maybe_replace_use (use_operand_p use_p)
    1818                 :            : {
    1819                 :  126238000 :   tree rdef = NULL_TREE;
    1820                 :  126238000 :   tree use = USE_FROM_PTR (use_p);
    1821                 :  234580000 :   tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
    1822                 :            : 
    1823                 :  126238000 :   if (marked_for_renaming (sym))
    1824                 :   49277300 :     rdef = get_reaching_def (sym);
    1825                 :   76961000 :   else if (is_old_name (use))
    1826                 :   36350000 :     rdef = get_reaching_def (use);
    1827                 :            : 
    1828                 :  126238000 :   if (rdef && rdef != use)
    1829                 :   37428900 :     SET_USE (use_p, rdef);
    1830                 :  126238000 : }
    1831                 :            : 
    1832                 :            : 
    1833                 :            : /* Same as maybe_replace_use, but without introducing default stmts,
    1834                 :            :    returning false to indicate a need to do so.  */
    1835                 :            : 
    1836                 :            : static inline bool
    1837                 :    7372550 : maybe_replace_use_in_debug_stmt (use_operand_p use_p)
    1838                 :            : {
    1839                 :    7372550 :   tree rdef = NULL_TREE;
    1840                 :    7372550 :   tree use = USE_FROM_PTR (use_p);
    1841                 :   14715000 :   tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
    1842                 :            : 
    1843                 :    7372550 :   if (marked_for_renaming (sym))
    1844                 :      30098 :     rdef = get_var_info (sym)->info.current_def;
    1845                 :    7342450 :   else if (is_old_name (use))
    1846                 :            :     {
    1847                 :    7179360 :       rdef = get_ssa_name_ann (use)->info.current_def;
    1848                 :            :       /* We can't assume that, if there's no current definition, the
    1849                 :            :          default one should be used.  It could be the case that we've
    1850                 :            :          rearranged blocks so that the earlier definition no longer
    1851                 :            :          dominates the use.  */
    1852                 :    7503070 :       if (!rdef && SSA_NAME_IS_DEFAULT_DEF (use))
    1853                 :            :         rdef = use;
    1854                 :            :     }
    1855                 :            :   else
    1856                 :            :     rdef = use;
    1857                 :            : 
    1858                 :    7372550 :   if (rdef && rdef != use)
    1859                 :    3713340 :     SET_USE (use_p, rdef);
    1860                 :            : 
    1861                 :    7372550 :   return rdef != NULL_TREE;
    1862                 :            : }
    1863                 :            : 
    1864                 :            : 
    1865                 :            : /* If DEF has x_5 = ASAN_POISON () as its current def, add
    1866                 :            :    ASAN_POISON_USE (x_5) stmt before GSI to denote the stmt writes into
    1867                 :            :    a poisoned (out of scope) variable.  */
    1868                 :            : 
    1869                 :            : static void
    1870                 :      27582 : maybe_add_asan_poison_write (tree def, gimple_stmt_iterator *gsi)
    1871                 :            : {
    1872                 :      27582 :   tree cdef = get_current_def (def);
    1873                 :      27582 :   if (cdef != NULL
    1874                 :      21743 :       && TREE_CODE (cdef) == SSA_NAME
    1875                 :      49325 :       && gimple_call_internal_p (SSA_NAME_DEF_STMT (cdef), IFN_ASAN_POISON))
    1876                 :            :     {
    1877                 :          3 :       gcall *call
    1878                 :          3 :         = gimple_build_call_internal (IFN_ASAN_POISON_USE, 1, cdef);
    1879                 :          3 :       gimple_set_location (call, gimple_location (gsi_stmt (*gsi)));
    1880                 :          3 :       gsi_insert_before (gsi, call, GSI_SAME_STMT);
    1881                 :            :     }
    1882                 :      27582 : }
    1883                 :            : 
    1884                 :            : 
    1885                 :            : /* If the operand pointed to by DEF_P is an SSA name in NEW_SSA_NAMES
    1886                 :            :    or OLD_SSA_NAMES, or if it is a symbol marked for renaming,
    1887                 :            :    register it as the current definition for the names replaced by
    1888                 :            :    DEF_P.  Returns whether the statement should be removed.  */
    1889                 :            : 
    1890                 :            : static inline bool
    1891                 :   51530600 : maybe_register_def (def_operand_p def_p, gimple *stmt,
    1892                 :            :                     gimple_stmt_iterator gsi)
    1893                 :            : {
    1894                 :   51530600 :   tree def = DEF_FROM_PTR (def_p);
    1895                 :   88988600 :   tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
    1896                 :   51530600 :   bool to_delete = false;
    1897                 :            : 
    1898                 :            :   /* If DEF is a naked symbol that needs renaming, create a new
    1899                 :            :      name for it.  */
    1900                 :   51530600 :   if (marked_for_renaming (sym))
    1901                 :            :     {
    1902                 :   35579600 :       if (DECL_P (def))
    1903                 :            :         {
    1904                 :   14072700 :           if (gimple_clobber_p (stmt) && is_gimple_reg (sym))
    1905                 :            :             {
    1906                 :    1242940 :               gcc_checking_assert (VAR_P (sym));
    1907                 :            :               /* Replace clobber stmts with a default def. This new use of a
    1908                 :            :                  default definition may make it look like SSA_NAMEs have
    1909                 :            :                  conflicting lifetimes, so we need special code to let them
    1910                 :            :                  coalesce properly.  */
    1911                 :    1242940 :               to_delete = true;
    1912                 :    1242940 :               def = get_or_create_ssa_default_def (cfun, sym);
    1913                 :            :             }
    1914                 :            :           else
    1915                 :            :             {
    1916                 :   12829800 :               if (asan_sanitize_use_after_scope ())
    1917                 :      27582 :                 maybe_add_asan_poison_write (def, &gsi);
    1918                 :   12829800 :               def = make_ssa_name (def, stmt);
    1919                 :            :             }
    1920                 :   14072700 :           SET_DEF (def_p, def);
    1921                 :            : 
    1922                 :   14072700 :           tree tracked_var = target_for_debug_bind (sym);
    1923                 :   14072700 :           if (tracked_var)
    1924                 :            :             {
    1925                 :    2054650 :               gimple *note = gimple_build_debug_bind (tracked_var, def, stmt);
    1926                 :            :               /* If stmt ends the bb, insert the debug stmt on the single
    1927                 :            :                  non-EH edge from the stmt.  */
    1928                 :    2160220 :               if (gsi_one_before_end_p (gsi) && stmt_ends_bb_p (stmt))
    1929                 :            :                 {
    1930                 :         43 :                   basic_block bb = gsi_bb (gsi);
    1931                 :         43 :                   edge_iterator ei;
    1932                 :         43 :                   edge e, ef = NULL;
    1933                 :        129 :                   FOR_EACH_EDGE (e, ei, bb->succs)
    1934                 :         86 :                     if (!(e->flags & EDGE_EH))
    1935                 :            :                       {
    1936                 :         43 :                         gcc_checking_assert (!ef);
    1937                 :            :                         ef = e;
    1938                 :            :                       }
    1939                 :            :                   /* If there are other predecessors to ef->dest, then
    1940                 :            :                      there must be PHI nodes for the modified
    1941                 :            :                      variable, and therefore there will be debug bind
    1942                 :            :                      stmts after the PHI nodes.  The debug bind notes
    1943                 :            :                      we'd insert would force the creation of a new
    1944                 :            :                      block (diverging codegen) and be redundant with
    1945                 :            :                      the post-PHI bind stmts, so don't add them.
    1946                 :            : 
    1947                 :            :                      As for the exit edge, there wouldn't be redundant
    1948                 :            :                      bind stmts, but there wouldn't be a PC to bind
    1949                 :            :                      them to either, so avoid diverging the CFG.  */
    1950                 :         43 :                   if (ef && single_pred_p (ef->dest)
    1951                 :         86 :                       && ef->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1952                 :            :                     {
    1953                 :            :                       /* If there were PHI nodes in the node, we'd
    1954                 :            :                          have to make sure the value we're binding
    1955                 :            :                          doesn't need rewriting.  But there shouldn't
    1956                 :            :                          be PHI nodes in a single-predecessor block,
    1957                 :            :                          so we just add the note.  */
    1958                 :         43 :                       gsi_insert_on_edge_immediate (ef, note);
    1959                 :            :                     }
    1960                 :            :                 }
    1961                 :            :               else
    1962                 :    2054610 :                 gsi_insert_after (&gsi, note, GSI_SAME_STMT);
    1963                 :            :             }
    1964                 :            :         }
    1965                 :            : 
    1966                 :   35579600 :       register_new_update_single (def, sym);
    1967                 :            :     }
    1968                 :            :   else
    1969                 :            :     {
    1970                 :            :       /* If DEF is a new name, register it as a new definition
    1971                 :            :          for all the names replaced by DEF.  */
    1972                 :   15951100 :       if (is_new_name (def))
    1973                 :    7943800 :         register_new_update_set (def, names_replaced_by (def));
    1974                 :            : 
    1975                 :            :       /* If DEF is an old name, register DEF as a new
    1976                 :            :          definition for itself.  */
    1977                 :   15951100 :       if (is_old_name (def))
    1978                 :    4000370 :         register_new_update_single (def, def);
    1979                 :            :     }
    1980                 :            : 
    1981                 :   51530600 :   return to_delete;
    1982                 :            : }
    1983                 :            : 
    1984                 :            : 
    1985                 :            : /* Update every variable used in the statement pointed-to by SI.  The
    1986                 :            :    statement is assumed to be in SSA form already.  Names in
    1987                 :            :    OLD_SSA_NAMES used by SI will be updated to their current reaching
    1988                 :            :    definition.  Names in OLD_SSA_NAMES or NEW_SSA_NAMES defined by SI
    1989                 :            :    will be registered as a new definition for their corresponding name
    1990                 :            :    in OLD_SSA_NAMES.  Returns whether STMT should be removed.  */
    1991                 :            : 
    1992                 :            : static bool
    1993                 :  353003000 : rewrite_update_stmt (gimple *stmt, gimple_stmt_iterator gsi)
    1994                 :            : {
    1995                 :  353003000 :   use_operand_p use_p;
    1996                 :  353003000 :   def_operand_p def_p;
    1997                 :  353003000 :   ssa_op_iter iter;
    1998                 :            : 
    1999                 :            :   /* Only update marked statements.  */
    2000                 :  353003000 :   if (!rewrite_uses_p (stmt) && !register_defs_p (stmt))
    2001                 :            :     return false;
    2002                 :            : 
    2003                 :   91007000 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2004                 :            :     {
    2005                 :      36741 :       fprintf (dump_file, "Updating SSA information for statement ");
    2006                 :      36741 :       print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    2007                 :            :     }
    2008                 :            : 
    2009                 :            :   /* Rewrite USES included in OLD_SSA_NAMES and USES whose underlying
    2010                 :            :      symbol is marked for renaming.  */
    2011                 :   91007000 :   if (rewrite_uses_p (stmt))
    2012                 :            :     {
    2013                 :   83046300 :       if (is_gimple_debug (stmt))
    2014                 :            :         {
    2015                 :    7957570 :           bool failed = false;
    2016                 :            : 
    2017                 :   15314300 :           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
    2018                 :    7372550 :             if (!maybe_replace_use_in_debug_stmt (use_p))
    2019                 :            :               {
    2020                 :            :                 failed = true;
    2021                 :            :                 break;
    2022                 :            :               }
    2023                 :            : 
    2024                 :    7957570 :           if (failed)
    2025                 :            :             {
    2026                 :            :               /* DOM sometimes threads jumps in such a way that a
    2027                 :            :                  debug stmt ends up referencing a SSA variable that no
    2028                 :            :                  longer dominates the debug stmt, but such that all
    2029                 :            :                  incoming definitions refer to the same definition in
    2030                 :            :                  an earlier dominator.  We could try to recover that
    2031                 :            :                  definition somehow, but this will have to do for now.
    2032                 :            : 
    2033                 :            :                  Introducing a default definition, which is what
    2034                 :            :                  maybe_replace_use() would do in such cases, may
    2035                 :            :                  modify code generation, for the otherwise-unused
    2036                 :            :                  default definition would never go away, modifying SSA
    2037                 :            :                  version numbers all over.  */
    2038                 :      15809 :               gimple_debug_bind_reset_value (stmt);
    2039                 :      15809 :               update_stmt (stmt);
    2040                 :            :             }
    2041                 :            :         }
    2042                 :            :       else
    2043                 :            :         {
    2044                 :  201327000 :           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES)
    2045                 :  126238000 :             maybe_replace_use (use_p);
    2046                 :            :         }
    2047                 :            :     }
    2048                 :            : 
    2049                 :            :   /* Register definitions of names in NEW_SSA_NAMES and OLD_SSA_NAMES.
    2050                 :            :      Also register definitions for names whose underlying symbol is
    2051                 :            :      marked for renaming.  */
    2052                 :   91007000 :   bool to_delete = false;
    2053                 :   91007000 :   if (register_defs_p (stmt))
    2054                 :  101569000 :     FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
    2055                 :   51530600 :       to_delete |= maybe_register_def (def_p, stmt, gsi);
    2056                 :            : 
    2057                 :            :   return to_delete;
    2058                 :            : }
    2059                 :            : 
    2060                 :            : 
    2061                 :            : /* Visit all the successor blocks of BB looking for PHI nodes.  For
    2062                 :            :    every PHI node found, check if any of its arguments is in
    2063                 :            :    OLD_SSA_NAMES.  If so, and if the argument has a current reaching
    2064                 :            :    definition, replace it.  */
    2065                 :            : 
    2066                 :            : static void
    2067                 :   48863100 : rewrite_update_phi_arguments (basic_block bb)
    2068                 :            : {
    2069                 :   48863100 :   edge e;
    2070                 :   48863100 :   edge_iterator ei;
    2071                 :   48863100 :   unsigned i;
    2072                 :            : 
    2073                 :  116786000 :   FOR_EACH_EDGE (e, ei, bb->succs)
    2074                 :            :     {
    2075                 :   67922800 :       gphi *phi;
    2076                 :   67922800 :       vec<gphi *> phis;
    2077                 :            : 
    2078                 :   67922800 :       if (!bitmap_bit_p (blocks_with_phis_to_rewrite, e->dest->index))
    2079                 :   48803000 :         continue;
    2080                 :            : 
    2081                 :   19119800 :       phis = phis_to_rewrite[e->dest->index];
    2082                 :  110192000 :       FOR_EACH_VEC_ELT (phis, i, phi)
    2083                 :            :         {
    2084                 :   23149200 :           tree arg, lhs_sym, reaching_def = NULL;
    2085                 :   23149200 :           use_operand_p arg_p;
    2086                 :            : 
    2087                 :   23149200 :           gcc_checking_assert (rewrite_uses_p (phi));
    2088                 :            : 
    2089                 :   23149200 :           arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
    2090                 :   23149200 :           arg = USE_FROM_PTR (arg_p);
    2091                 :            : 
    2092                 :   23149200 :           if (arg && !DECL_P (arg) && TREE_CODE (arg) != SSA_NAME)
    2093                 :     346917 :             continue;
    2094                 :            : 
    2095                 :   22802300 :           lhs_sym = SSA_NAME_VAR (gimple_phi_result (phi));
    2096                 :            : 
    2097                 :   22802300 :           if (arg == NULL_TREE)
    2098                 :            :             {
    2099                 :            :               /* When updating a PHI node for a recently introduced
    2100                 :            :                  symbol we may find NULL arguments.  That's why we
    2101                 :            :                  take the symbol from the LHS of the PHI node.  */
    2102                 :    2934470 :               reaching_def = get_reaching_def (lhs_sym);
    2103                 :            : 
    2104                 :            :             }
    2105                 :            :           else
    2106                 :            :             {
    2107                 :   39703100 :               tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
    2108                 :            : 
    2109                 :   19867800 :               if (marked_for_renaming (sym))
    2110                 :   10929700 :                 reaching_def = get_reaching_def (sym);
    2111                 :    8938080 :               else if (is_old_name (arg))
    2112                 :    7904440 :                 reaching_def = get_reaching_def (arg);
    2113                 :            :             }
    2114                 :            : 
    2115                 :            :           /* Update the argument if there is a reaching def.  */
    2116                 :   21768700 :           if (reaching_def)
    2117                 :            :             {
    2118                 :   21768700 :               location_t locus;
    2119                 :   21768700 :               int arg_i = PHI_ARG_INDEX_FROM_USE (arg_p);
    2120                 :            : 
    2121                 :   21768700 :               SET_USE (arg_p, reaching_def);
    2122                 :            : 
    2123                 :            :               /* Virtual operands do not need a location.  */
    2124                 :   43537300 :               if (virtual_operand_p (reaching_def))
    2125                 :            :                 locus = UNKNOWN_LOCATION;
    2126                 :            :               else
    2127                 :            :                 {
    2128                 :    6514480 :                   gimple *stmt = SSA_NAME_DEF_STMT (reaching_def);
    2129                 :    6514480 :                   gphi *other_phi = dyn_cast <gphi *> (stmt);
    2130                 :            : 
    2131                 :            :                   /* Single element PHI nodes  behave like copies, so get the
    2132                 :            :                      location from the phi argument.  */
    2133                 :    3552060 :                   if (other_phi
    2134                 :    3552060 :                       && gimple_phi_num_args (other_phi) == 1)
    2135                 :    1829660 :                     locus = gimple_phi_arg_location (other_phi, 0);
    2136                 :            :                   else
    2137                 :    4684820 :                     locus = gimple_location (stmt);
    2138                 :            :                 }
    2139                 :            : 
    2140                 :   21768700 :               gimple_phi_arg_set_location (phi, arg_i, locus);
    2141                 :            :             }
    2142                 :            : 
    2143                 :            : 
    2144                 :   22802300 :           if (e->flags & EDGE_ABNORMAL)
    2145                 :       3820 :             SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
    2146                 :            :         }
    2147                 :            :     }
    2148                 :   48863100 : }
    2149                 :            : 
    2150                 :    2709660 : class rewrite_update_dom_walker : public dom_walker
    2151                 :            : {
    2152                 :            : public:
    2153                 :    2709660 :   rewrite_update_dom_walker (cdi_direction direction)
    2154                 :    5419320 :     : dom_walker (direction, ALL_BLOCKS, NULL) {}
    2155                 :            : 
    2156                 :            :   virtual edge before_dom_children (basic_block);
    2157                 :            :   virtual void after_dom_children (basic_block);
    2158                 :            : };
    2159                 :            : 
    2160                 :            : /* Initialization of block data structures for the incremental SSA
    2161                 :            :    update pass.  Create a block local stack of reaching definitions
    2162                 :            :    for new SSA names produced in this block (BLOCK_DEFS).  Register
    2163                 :            :    new definitions for every PHI node in the block.  */
    2164                 :            : 
    2165                 :            : edge
    2166                 :   64571600 : rewrite_update_dom_walker::before_dom_children (basic_block bb)
    2167                 :            : {
    2168                 :   64571600 :   bool is_abnormal_phi;
    2169                 :            : 
    2170                 :   64571600 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2171                 :      25712 :     fprintf (dump_file, "Registering new PHI nodes in block #%d\n",
    2172                 :            :              bb->index);
    2173                 :            : 
    2174                 :            :   /* Mark the unwind point for this block.  */
    2175                 :   64571600 :   block_defs_stack.safe_push (NULL_TREE);
    2176                 :            : 
    2177                 :   64571600 :   if (!bitmap_bit_p (blocks_to_update, bb->index))
    2178                 :            :     return NULL;
    2179                 :            : 
    2180                 :            :   /* Mark the LHS if any of the arguments flows through an abnormal
    2181                 :            :      edge.  */
    2182                 :   48863100 :   is_abnormal_phi = bb_has_abnormal_pred (bb);
    2183                 :            : 
    2184                 :            :   /* If any of the PHI nodes is a replacement for a name in
    2185                 :            :      OLD_SSA_NAMES or it's one of the names in NEW_SSA_NAMES, then
    2186                 :            :      register it as a new definition for its corresponding name.  Also
    2187                 :            :      register definitions for names whose underlying symbols are
    2188                 :            :      marked for renaming.  */
    2189                 :   71851600 :   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
    2190                 :   22988500 :        gsi_next (&gsi))
    2191                 :            :     {
    2192                 :   22988500 :       tree lhs, lhs_sym;
    2193                 :   22988500 :       gphi *phi = gsi.phi ();
    2194                 :            : 
    2195                 :   22988500 :       if (!register_defs_p (phi))
    2196                 :   10855500 :         continue;
    2197                 :            : 
    2198                 :   12133000 :       lhs = gimple_phi_result (phi);
    2199                 :   12133000 :       lhs_sym = SSA_NAME_VAR (lhs);
    2200                 :            : 
    2201                 :   12133000 :       if (marked_for_renaming (lhs_sym))
    2202                 :    4886960 :         register_new_update_single (lhs, lhs_sym);
    2203                 :            :       else
    2204                 :            :         {
    2205                 :            : 
    2206                 :            :           /* If LHS is a new name, register a new definition for all
    2207                 :            :              the names replaced by LHS.  */
    2208                 :    7246030 :           if (is_new_name (lhs))
    2209                 :    4710390 :             register_new_update_set (lhs, names_replaced_by (lhs));
    2210                 :            : 
    2211                 :            :           /* If LHS is an OLD name, register it as a new definition
    2212                 :            :              for itself.  */
    2213                 :    7246030 :           if (is_old_name (lhs))
    2214                 :    2488710 :             register_new_update_single (lhs, lhs);
    2215                 :            :         }
    2216                 :            : 
    2217                 :   12133000 :       if (is_abnormal_phi)
    2218                 :       1875 :         SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs) = 1;
    2219                 :            :     }
    2220                 :            : 
    2221                 :            :   /* Step 2.  Rewrite every variable used in each statement in the block.  */
    2222                 :   48863100 :   if (bitmap_bit_p (interesting_blocks, bb->index))
    2223                 :            :     {
    2224                 :   48863100 :       gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
    2225                 :  450730000 :       for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); )
    2226                 :  353003000 :         if (rewrite_update_stmt (gsi_stmt (gsi), gsi))
    2227                 :    1242940 :           gsi_remove (&gsi, true);
    2228                 :            :         else
    2229                 :  351760000 :           gsi_next (&gsi);
    2230                 :            :     }
    2231                 :            : 
    2232                 :            :   /* Step 3.  Update PHI nodes.  */
    2233                 :   48863100 :   rewrite_update_phi_arguments (bb);
    2234                 :            : 
    2235                 :   48863100 :   return NULL;
    2236                 :            : }
    2237                 :            : 
    2238                 :            : /* Called after visiting block BB.  Unwind BLOCK_DEFS_STACK to restore
    2239                 :            :    the current reaching definition of every name re-written in BB to
    2240                 :            :    the original reaching definition before visiting BB.  This
    2241                 :            :    unwinding must be done in the opposite order to what is done in
    2242                 :            :    register_new_update_set.  */
    2243                 :            : 
    2244                 :            : void
    2245                 :   64571600 : rewrite_update_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
    2246                 :            : {
    2247                 :  124340000 :   while (block_defs_stack.length () > 0)
    2248                 :            :     {
    2249                 :  124340000 :       tree var = block_defs_stack.pop ();
    2250                 :  124340000 :       tree saved_def;
    2251                 :            : 
    2252                 :            :       /* NULL indicates the unwind stop point for this block (see
    2253                 :            :          rewrite_update_enter_block).  */
    2254                 :  124340000 :       if (var == NULL)
    2255                 :            :         return;
    2256                 :            : 
    2257                 :   59768300 :       saved_def = block_defs_stack.pop ();
    2258                 :   59768300 :       get_common_info (var)->current_def = saved_def;
    2259                 :            :     }
    2260                 :            : }
    2261                 :            : 
    2262                 :            : 
    2263                 :            : /* Rewrite the actual blocks, statements, and PHI arguments, to be in SSA
    2264                 :            :    form.
    2265                 :            : 
    2266                 :            :    ENTRY indicates the block where to start.  Every block dominated by
    2267                 :            :       ENTRY will be rewritten.
    2268                 :            : 
    2269                 :            :    WHAT indicates what actions will be taken by the renamer (see enum
    2270                 :            :       rewrite_mode).
    2271                 :            : 
    2272                 :            :    BLOCKS are the set of interesting blocks for the dominator walker
    2273                 :            :       to process.  If this set is NULL, then all the nodes dominated
    2274                 :            :       by ENTRY are walked.  Otherwise, blocks dominated by ENTRY that
    2275                 :            :       are not present in BLOCKS are ignored.  */
    2276                 :            : 
    2277                 :            : static void
    2278                 :    4556720 : rewrite_blocks (basic_block entry, enum rewrite_mode what)
    2279                 :            : {
    2280                 :            :   /* Rewrite all the basic blocks in the program.  */
    2281                 :    4556720 :   timevar_push (TV_TREE_SSA_REWRITE_BLOCKS);
    2282                 :            : 
    2283                 :    4556720 :   block_defs_stack.create (10);
    2284                 :            : 
    2285                 :            :   /* Recursively walk the dominator tree rewriting each statement in
    2286                 :            :      each basic block.  */
    2287                 :    4556720 :   if (what == REWRITE_ALL)
    2288                 :    1847060 :       rewrite_dom_walker (CDI_DOMINATORS).walk (entry);
    2289                 :    2709660 :   else if (what == REWRITE_UPDATE)
    2290                 :    2709660 :       rewrite_update_dom_walker (CDI_DOMINATORS).walk (entry);
    2291                 :            :   else
    2292                 :          0 :     gcc_unreachable ();
    2293                 :            : 
    2294                 :            :   /* Debugging dumps.  */
    2295                 :    4556720 :   if (dump_file && (dump_flags & TDF_STATS))
    2296                 :            :     {
    2297                 :        339 :       dump_dfa_stats (dump_file);
    2298                 :        339 :       if (var_infos)
    2299                 :         78 :         dump_tree_ssa_stats (dump_file);
    2300                 :            :     }
    2301                 :            : 
    2302                 :    4556720 :   block_defs_stack.release ();
    2303                 :            : 
    2304                 :    4556720 :   timevar_pop (TV_TREE_SSA_REWRITE_BLOCKS);
    2305                 :    4556720 : }
    2306                 :            : 
    2307                 :            : class mark_def_dom_walker : public dom_walker
    2308                 :            : {
    2309                 :            : public:
    2310                 :            :   mark_def_dom_walker (cdi_direction direction);
    2311                 :            :   ~mark_def_dom_walker ();
    2312                 :            : 
    2313                 :            :   virtual edge before_dom_children (basic_block);
    2314                 :            : 
    2315                 :            : private:
    2316                 :            :   /* Notice that this bitmap is indexed using variable UIDs, so it must be
    2317                 :            :      large enough to accommodate all the variables referenced in the
    2318                 :            :      function, not just the ones we are renaming.  */
    2319                 :            :   bitmap m_kills;
    2320                 :            : };
    2321                 :            : 
    2322                 :    1847060 : mark_def_dom_walker::mark_def_dom_walker (cdi_direction direction)
    2323                 :    1847060 :   : dom_walker (direction, ALL_BLOCKS, NULL), m_kills (BITMAP_ALLOC (NULL))
    2324                 :            : {
    2325                 :    1847060 : }
    2326                 :            : 
    2327                 :    5541180 : mark_def_dom_walker::~mark_def_dom_walker ()
    2328                 :            : {
    2329                 :    1847060 :   BITMAP_FREE (m_kills);
    2330                 :    1847060 : }
    2331                 :            : 
    2332                 :            : /* Block processing routine for mark_def_sites.  Clear the KILLS bitmap
    2333                 :            :    at the start of each block, and call mark_def_sites for each statement.  */
    2334                 :            : 
    2335                 :            : edge
    2336                 :   13290300 : mark_def_dom_walker::before_dom_children (basic_block bb)
    2337                 :            : {
    2338                 :   13290300 :   gimple_stmt_iterator gsi;
    2339                 :            : 
    2340                 :   13290300 :   bitmap_clear (m_kills);
    2341                 :   69614600 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2342                 :   43034100 :     mark_def_sites (bb, gsi_stmt (gsi), m_kills);
    2343                 :   13290300 :   return NULL;
    2344                 :            : }
    2345                 :            : 
    2346                 :            : /* Initialize internal data needed during renaming.  */
    2347                 :            : 
    2348                 :            : static void
    2349                 :    1847060 : init_ssa_renamer (void)
    2350                 :            : {
    2351                 :    1847060 :   cfun->gimple_df->in_ssa_p = false;
    2352                 :            : 
    2353                 :            :   /* Allocate memory for the DEF_BLOCKS hash table.  */
    2354                 :    1847060 :   gcc_assert (!var_infos);
    2355                 :    3694120 :   var_infos = new hash_table<var_info_hasher>
    2356                 :    3220010 :     (vec_safe_length (cfun->local_decls));
    2357                 :            : 
    2358                 :    1847060 :   bitmap_obstack_initialize (&update_ssa_obstack);
    2359                 :    1847060 : }
    2360                 :            : 
    2361                 :            : 
    2362                 :            : /* Deallocate internal data structures used by the renamer.  */
    2363                 :            : 
    2364                 :            : static void
    2365                 :    4569600 : fini_ssa_renamer (void)
    2366                 :            : {
    2367                 :    4569600 :   delete var_infos;
    2368                 :    4569600 :     var_infos = NULL;
    2369                 :            : 
    2370                 :    4569600 :   bitmap_obstack_release (&update_ssa_obstack);
    2371                 :            : 
    2372                 :    4569600 :   cfun->gimple_df->ssa_renaming_needed = 0;
    2373                 :    4569600 :   cfun->gimple_df->rename_vops = 0;
    2374                 :    4569600 :   cfun->gimple_df->in_ssa_p = true;
    2375                 :    4569600 : }
    2376                 :            : 
    2377                 :            : /* Main entry point into the SSA builder.  The renaming process
    2378                 :            :    proceeds in four main phases:
    2379                 :            : 
    2380                 :            :    1- Compute dominance frontier and immediate dominators, needed to
    2381                 :            :       insert PHI nodes and rename the function in dominator tree
    2382                 :            :       order.
    2383                 :            : 
    2384                 :            :    2- Find and mark all the blocks that define variables.
    2385                 :            : 
    2386                 :            :    3- Insert PHI nodes at dominance frontiers (insert_phi_nodes).
    2387                 :            : 
    2388                 :            :    4- Rename all the blocks (rewrite_blocks) and statements in the program.
    2389                 :            : 
    2390                 :            :    Steps 3 and 4 are done using the dominator tree walker
    2391                 :            :    (walk_dominator_tree).  */
    2392                 :            : 
    2393                 :            : namespace {
    2394                 :            : 
    2395                 :            : const pass_data pass_data_build_ssa =
    2396                 :            : {
    2397                 :            :   GIMPLE_PASS, /* type */
    2398                 :            :   "ssa", /* name */
    2399                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    2400                 :            :   TV_TREE_SSA_OTHER, /* tv_id */
    2401                 :            :   PROP_cfg, /* properties_required */
    2402                 :            :   PROP_ssa, /* properties_provided */
    2403                 :            :   0, /* properties_destroyed */
    2404                 :            :   0, /* todo_flags_start */
    2405                 :            :   TODO_remove_unused_locals, /* todo_flags_finish */
    2406                 :            : };
    2407                 :            : 
    2408                 :            : class pass_build_ssa : public gimple_opt_pass
    2409                 :            : {
    2410                 :            : public:
    2411                 :     200777 :   pass_build_ssa (gcc::context *ctxt)
    2412                 :     401554 :     : gimple_opt_pass (pass_data_build_ssa, ctxt)
    2413                 :            :   {}
    2414                 :            : 
    2415                 :            :   /* opt_pass methods: */
    2416                 :    1847350 :   virtual bool gate (function *fun)
    2417                 :            :     {
    2418                 :            :       /* Do nothing for funcions that was produced already in SSA form.  */
    2419                 :    1847350 :       return !(fun->curr_properties & PROP_ssa);
    2420                 :            :     }
    2421                 :            : 
    2422                 :            :   virtual unsigned int execute (function *);
    2423                 :            : 
    2424                 :            : }; // class pass_build_ssa
    2425                 :            : 
    2426                 :            : unsigned int
    2427                 :    1847060 : pass_build_ssa::execute (function *fun)
    2428                 :            : {
    2429                 :    1847060 :   bitmap_head *dfs;
    2430                 :    1847060 :   basic_block bb;
    2431                 :            : 
    2432                 :            :   /* Increase the set of variables we can rewrite into SSA form
    2433                 :            :      by clearing TREE_ADDRESSABLE and setting DECL_GIMPLE_REG_P
    2434                 :            :      and transform the IL to support this.  */
    2435                 :    1847060 :   if (optimize)
    2436                 :    1590590 :     execute_update_addresses_taken ();
    2437                 :            : 
    2438                 :            :   /* Initialize operand data structures.  */
    2439                 :    1847060 :   init_ssa_operands (fun);
    2440                 :            : 
    2441                 :            :   /* Initialize internal data needed by the renamer.  */
    2442                 :    1847060 :   init_ssa_renamer ();
    2443                 :            : 
    2444                 :            :   /* Initialize the set of interesting blocks.  The callback
    2445                 :            :      mark_def_sites will add to this set those blocks that the renamer
    2446                 :            :      should process.  */
    2447                 :    1847060 :   interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (fun));
    2448                 :    1847060 :   bitmap_clear (interesting_blocks);
    2449                 :            : 
    2450                 :            :   /* Initialize dominance frontier.  */
    2451                 :    1847060 :   dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (fun));
    2452                 :   13290300 :   FOR_EACH_BB_FN (bb, fun)
    2453                 :   11443200 :     bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
    2454                 :            : 
    2455                 :            :   /* 1- Compute dominance frontiers.  */
    2456                 :    1847060 :   calculate_dominance_info (CDI_DOMINATORS);
    2457                 :    1847060 :   compute_dominance_frontiers (dfs);
    2458                 :            : 
    2459                 :            :   /* 2- Find and mark definition sites.  */
    2460                 :    1847060 :   mark_def_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
    2461                 :            : 
    2462                 :            :   /* 3- Insert PHI nodes at dominance frontiers of definition blocks.  */
    2463                 :    1847060 :   insert_phi_nodes (dfs);
    2464                 :            : 
    2465                 :            :   /* 4- Rename all the blocks.  */
    2466                 :    1847060 :   rewrite_blocks (ENTRY_BLOCK_PTR_FOR_FN (fun), REWRITE_ALL);
    2467                 :            : 
    2468                 :            :   /* Free allocated memory.  */
    2469                 :   13290300 :   FOR_EACH_BB_FN (bb, fun)
    2470                 :   11443200 :     bitmap_clear (&dfs[bb->index]);
    2471                 :    1847060 :   free (dfs);
    2472                 :            : 
    2473                 :    1847060 :   sbitmap_free (interesting_blocks);
    2474                 :            : 
    2475                 :    1847060 :   fini_ssa_renamer ();
    2476                 :            : 
    2477                 :            :   /* Try to get rid of all gimplifier generated temporaries by making
    2478                 :            :      its SSA names anonymous.  This way we can garbage collect them
    2479                 :            :      all after removing unused locals which we do in our TODO.  */
    2480                 :    1847060 :   unsigned i;
    2481                 :    1847060 :   tree name;
    2482                 :            : 
    2483                 :   45768100 :   FOR_EACH_SSA_NAME (i, name, cfun)
    2484                 :            :     {
    2485                 :   43899400 :       if (SSA_NAME_IS_DEFAULT_DEF (name))
    2486                 :    4426880 :         continue;
    2487                 :   70329800 :       tree decl = SSA_NAME_VAR (name);
    2488                 :   26408700 :       if (decl
    2489                 :   26408700 :           && VAR_P (decl)
    2490                 :   26309300 :           && !VAR_DECL_IS_VIRTUAL_OPERAND (decl)
    2491                 :   10202300 :           && DECL_IGNORED_P (decl))
    2492                 :    7358980 :         SET_SSA_NAME_VAR_OR_IDENTIFIER (name, DECL_NAME (decl));
    2493                 :            :     }
    2494                 :            : 
    2495                 :            :   /* Initialize SSA_NAME_POINTS_TO_READONLY_MEMORY.  */
    2496                 :    5541180 :   tree fnspec = lookup_attribute ("fn spec",
    2497                 :    1847060 :                                   TYPE_ATTRIBUTES (TREE_TYPE (fun->decl)));
    2498                 :    1847060 :   if (fnspec)
    2499                 :            :     {
    2500                 :      60711 :       fnspec = TREE_VALUE (TREE_VALUE (fnspec));
    2501                 :      60711 :       unsigned i = 1;
    2502                 :     129739 :       for (tree arg = DECL_ARGUMENTS (cfun->decl);
    2503                 :     129739 :            arg; arg = DECL_CHAIN (arg), ++i)
    2504                 :            :         {
    2505                 :      75012 :           if (i >= (unsigned) TREE_STRING_LENGTH (fnspec))
    2506                 :            :             break;
    2507                 :      69028 :           if (TREE_STRING_POINTER (fnspec)[i]  == 'R'
    2508                 :      69028 :               || TREE_STRING_POINTER (fnspec)[i] == 'r')
    2509                 :            :             {
    2510                 :      18784 :               tree name = ssa_default_def (fun, arg);
    2511                 :      18784 :               if (name)
    2512                 :      15117 :                 SSA_NAME_POINTS_TO_READONLY_MEMORY (name) = 1;
    2513                 :            :             }
    2514                 :            :         }
    2515                 :            :     }
    2516                 :            : 
    2517                 :    1847060 :   return 0;
    2518                 :            : }
    2519                 :            : 
    2520                 :            : } // anon namespace
    2521                 :            : 
    2522                 :            : gimple_opt_pass *
    2523                 :     200777 : make_pass_build_ssa (gcc::context *ctxt)
    2524                 :            : {
    2525                 :     200777 :   return new pass_build_ssa (ctxt);
    2526                 :            : }
    2527                 :            : 
    2528                 :            : 
    2529                 :            : /* Mark the definition of VAR at STMT and BB as interesting for the
    2530                 :            :    renamer.  BLOCKS is the set of blocks that need updating.  */
    2531                 :            : 
    2532                 :            : static void
    2533                 :   57138600 : mark_def_interesting (tree var, gimple *stmt, basic_block bb,
    2534                 :            :                       bool insert_phi_p)
    2535                 :            : {
    2536                 :   57138600 :   gcc_checking_assert (bitmap_bit_p (blocks_to_update, bb->index));
    2537                 :   57138600 :   set_register_defs (stmt, true);
    2538                 :            : 
    2539                 :   57138600 :   if (insert_phi_p)
    2540                 :            :     {
    2541                 :   48411100 :       bool is_phi_p = gimple_code (stmt) == GIMPLE_PHI;
    2542                 :            : 
    2543                 :   48411100 :       set_def_block (var, bb, is_phi_p);
    2544                 :            : 
    2545                 :            :       /* If VAR is an SSA name in NEW_SSA_NAMES, this is a definition
    2546                 :            :          site for both itself and all the old names replaced by it.  */
    2547                 :   48411100 :       if (TREE_CODE (var) == SSA_NAME && is_new_name (var))
    2548                 :            :         {
    2549                 :    5851150 :           bitmap_iterator bi;
    2550                 :    5851150 :           unsigned i;
    2551                 :    5851150 :           bitmap set = names_replaced_by (var);
    2552                 :    5851150 :           if (set)
    2553                 :   11860700 :             EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
    2554                 :    6009590 :               set_def_block (ssa_name (i), bb, is_phi_p);
    2555                 :            :         }
    2556                 :            :     }
    2557                 :   57138600 : }
    2558                 :            : 
    2559                 :            : 
    2560                 :            : /* Mark the use of VAR at STMT and BB as interesting for the
    2561                 :            :    renamer.  INSERT_PHI_P is true if we are going to insert new PHI
    2562                 :            :    nodes.  */
    2563                 :            : 
    2564                 :            : static inline void
    2565                 :  108940000 : mark_use_interesting (tree var, gimple *stmt, basic_block bb,
    2566                 :            :                       bool insert_phi_p)
    2567                 :            : {
    2568                 :  108940000 :   basic_block def_bb = gimple_bb (stmt);
    2569                 :            : 
    2570                 :  108940000 :   mark_block_for_update (def_bb);
    2571                 :  108940000 :   mark_block_for_update (bb);
    2572                 :            : 
    2573                 :  108940000 :   if (gimple_code (stmt) == GIMPLE_PHI)
    2574                 :   16102600 :     mark_phi_for_rewrite (def_bb, as_a <gphi *> (stmt));
    2575                 :            :   else
    2576                 :            :     {
    2577                 :   92837200 :       set_rewrite_uses (stmt, true);
    2578                 :            : 
    2579                 :   92837200 :       if (is_gimple_debug (stmt))
    2580                 :            :         return;
    2581                 :            :     }
    2582                 :            : 
    2583                 :            :   /* If VAR has not been defined in BB, then it is live-on-entry
    2584                 :            :      to BB.  Note that we cannot just use the block holding VAR's
    2585                 :            :      definition because if VAR is one of the names in OLD_SSA_NAMES,
    2586                 :            :      it will have several definitions (itself and all the names that
    2587                 :            :      replace it).  */
    2588                 :  101730000 :   if (insert_phi_p)
    2589                 :            :     {
    2590                 :   74837700 :       def_blocks *db_p = get_def_blocks_for (get_common_info (var));
    2591                 :   74837700 :       if (!bitmap_bit_p (db_p->def_blocks, bb->index))
    2592                 :   33189900 :         set_livein_block (var, bb);
    2593                 :            :     }
    2594                 :            : }
    2595                 :            : 
    2596                 :            : /* Processing statements in BB that reference symbols in SSA operands.
    2597                 :            :    This is very similar to mark_def_sites, but the scan handles
    2598                 :            :    statements whose operands may already be SSA names.
    2599                 :            : 
    2600                 :            :    If INSERT_PHI_P is true, mark those uses as live in the
    2601                 :            :    corresponding block.  This is later used by the PHI placement
    2602                 :            :    algorithm to make PHI pruning decisions.
    2603                 :            : 
    2604                 :            :    FIXME.  Most of this would be unnecessary if we could associate a
    2605                 :            :            symbol to all the SSA names that reference it.  But that
    2606                 :            :            sounds like it would be expensive to maintain.  Still, it
    2607                 :            :            would be interesting to see if it makes better sense to do
    2608                 :            :            that.  */
    2609                 :            : 
    2610                 :            : static void
    2611                 :   32161800 : prepare_block_for_update_1 (basic_block bb, bool insert_phi_p)
    2612                 :            : {
    2613                 :   32161800 :   edge e;
    2614                 :   32161800 :   edge_iterator ei;
    2615                 :            : 
    2616                 :   32161800 :   mark_block_for_update (bb);
    2617                 :            : 
    2618                 :            :   /* Process PHI nodes marking interesting those that define or use
    2619                 :            :      the symbols that we are interested in.  */
    2620                 :   40481200 :   for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
    2621                 :    8319410 :        gsi_next (&si))
    2622                 :            :     {
    2623                 :    8319410 :       gphi *phi = si.phi ();
    2624                 :    8319410 :       tree lhs_sym, lhs = gimple_phi_result (phi);
    2625                 :            : 
    2626                 :   12922500 :       if (TREE_CODE (lhs) == SSA_NAME
    2627                 :    8319410 :           && (! virtual_operand_p (lhs)
    2628                 :    4135920 :               || ! cfun->gimple_df->rename_vops))
    2629                 :    4603120 :         continue;
    2630                 :            : 
    2631                 :    7432580 :       lhs_sym = DECL_P (lhs) ? lhs : SSA_NAME_VAR (lhs);
    2632                 :    3716290 :       mark_for_renaming (lhs_sym);
    2633                 :    3716290 :       mark_def_interesting (lhs_sym, phi, bb, insert_phi_p);
    2634                 :            : 
    2635                 :            :       /* Mark the uses in phi nodes as interesting.  It would be more correct
    2636                 :            :          to process the arguments of the phi nodes of the successor edges of
    2637                 :            :          BB at the end of prepare_block_for_update, however, that turns out
    2638                 :            :          to be significantly more expensive.  Doing it here is conservatively
    2639                 :            :          correct -- it may only cause us to believe a value to be live in a
    2640                 :            :          block that also contains its definition, and thus insert a few more
    2641                 :            :          phi nodes for it.  */
    2642                 :   14646100 :       FOR_EACH_EDGE (e, ei, bb->preds)
    2643                 :   10929900 :         mark_use_interesting (lhs_sym, phi, e->src, insert_phi_p);
    2644                 :            :     }
    2645                 :            : 
    2646                 :            :   /* Process the statements.  */
    2647                 :  280610000 :   for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
    2648                 :  216287000 :        gsi_next (&si))
    2649                 :            :     {
    2650                 :  216287000 :       gimple *stmt;
    2651                 :  216287000 :       ssa_op_iter i;
    2652                 :  216287000 :       use_operand_p use_p;
    2653                 :  216287000 :       def_operand_p def_p;
    2654                 :            : 
    2655                 :  216287000 :       stmt = gsi_stmt (si);
    2656                 :            : 
    2657                 :  216287000 :       if (cfun->gimple_df->rename_vops
    2658                 :  283497000 :           && gimple_vuse (stmt))
    2659                 :            :         {
    2660                 :   43153600 :           tree use = gimple_vuse (stmt);
    2661                 :   74534700 :           tree sym = DECL_P (use) ? use : SSA_NAME_VAR (use);
    2662                 :   43153600 :           mark_for_renaming (sym);
    2663                 :   43153600 :           mark_use_interesting (sym, stmt, bb, insert_phi_p);
    2664                 :            :         }
    2665                 :            : 
    2666                 :  307364000 :       FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_USE)
    2667                 :            :         {
    2668                 :   91077700 :           tree use = USE_FROM_PTR (use_p);
    2669                 :   91077700 :           if (!DECL_P (use))
    2670                 :   84923900 :             continue;
    2671                 :    6153780 :           mark_for_renaming (use);
    2672                 :    6153780 :           mark_use_interesting (use, stmt, bb, insert_phi_p);
    2673                 :            :         }
    2674                 :            : 
    2675                 :  216287000 :       if (cfun->gimple_df->rename_vops
    2676                 :  283497000 :           && gimple_vdef (stmt))
    2677                 :            :         {
    2678                 :   28873400 :           tree def = gimple_vdef (stmt);
    2679                 :   50380300 :           tree sym = DECL_P (def) ? def : SSA_NAME_VAR (def);
    2680                 :   28873400 :           mark_for_renaming (sym);
    2681                 :   28873400 :           mark_def_interesting (sym, stmt, bb, insert_phi_p);
    2682                 :            :         }
    2683                 :            : 
    2684                 :  261774000 :       FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, i, SSA_OP_DEF)
    2685                 :            :         {
    2686                 :   45487500 :           tree def = DEF_FROM_PTR (def_p);
    2687                 :   45487500 :           if (!DECL_P (def))
    2688                 :   38781300 :             continue;
    2689                 :    6706190 :           mark_for_renaming (def);
    2690                 :    6706190 :           mark_def_interesting (def, stmt, bb, insert_phi_p);
    2691                 :            :         }
    2692                 :            :     }
    2693                 :            : 
    2694                 :   32161800 : }
    2695                 :            : 
    2696                 :            : /* Do a dominator walk starting at BB processing statements that
    2697                 :            :    reference symbols in SSA operands.  This is very similar to
    2698                 :            :    mark_def_sites, but the scan handles statements whose operands may
    2699                 :            :    already be SSA names.
    2700                 :            : 
    2701                 :            :    If INSERT_PHI_P is true, mark those uses as live in the
    2702                 :            :    corresponding block.  This is later used by the PHI placement
    2703                 :            :    algorithm to make PHI pruning decisions.
    2704                 :            : 
    2705                 :            :    FIXME.  Most of this would be unnecessary if we could associate a
    2706                 :            :            symbol to all the SSA names that reference it.  But that
    2707                 :            :            sounds like it would be expensive to maintain.  Still, it
    2708                 :            :            would be interesting to see if it makes better sense to do
    2709                 :            :            that.  */
    2710                 :            : static void
    2711                 :    1535090 : prepare_block_for_update (basic_block bb, bool insert_phi_p)
    2712                 :            : {
    2713                 :    1535090 :   size_t sp = 0;
    2714                 :    1535090 :   basic_block *worklist;
    2715                 :            : 
    2716                 :            :   /* Allocate the worklist.  */
    2717                 :    1535090 :   worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun));
    2718                 :            :   /* Add the BB to the worklist.  */
    2719                 :    1535090 :   worklist[sp++] = bb;
    2720                 :            : 
    2721                 :   33696900 :   while (sp)
    2722                 :            :     {
    2723                 :   32161800 :       basic_block bb;
    2724                 :   32161800 :       basic_block son;
    2725                 :            : 
    2726                 :            :       /* Pick a block from the worklist.  */
    2727                 :   32161800 :       bb = worklist[--sp];
    2728                 :            : 
    2729                 :   32161800 :       prepare_block_for_update_1 (bb, insert_phi_p);
    2730                 :            : 
    2731                 :            :       /* Now add all the blocks dominated by BB to the worklist.  */
    2732                 :   32161800 :       for (son = first_dom_son (CDI_DOMINATORS, bb);
    2733                 :   62788400 :            son;
    2734                 :   30626700 :            son = next_dom_son (CDI_DOMINATORS, son))
    2735                 :   30626700 :         worklist[sp++] = son;
    2736                 :            :     }
    2737                 :    1535090 :   free (worklist);
    2738                 :    1535090 : }
    2739                 :            : 
    2740                 :            : /* Helper for prepare_names_to_update.  Mark all the use sites for
    2741                 :            :    NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
    2742                 :            :    prepare_names_to_update.  */
    2743                 :            : 
    2744                 :            : static void
    2745                 :    7365290 : prepare_use_sites_for (tree name, bool insert_phi_p)
    2746                 :            : {
    2747                 :    7365290 :   use_operand_p use_p;
    2748                 :    7365290 :   imm_use_iterator iter;
    2749                 :            : 
    2750                 :            :   /* If we rename virtual operands do not update them.  */
    2751                 :    7365290 :   if (virtual_operand_p (name)
    2752                 :    7365290 :       && cfun->gimple_df->rename_vops)
    2753                 :       1564 :     return;
    2754                 :            : 
    2755                 :   56066300 :   FOR_EACH_IMM_USE_FAST (use_p, iter, name)
    2756                 :            :     {
    2757                 :   48702600 :       gimple *stmt = USE_STMT (use_p);
    2758                 :   48702600 :       basic_block bb = gimple_bb (stmt);
    2759                 :            : 
    2760                 :   48702600 :       if (gimple_code (stmt) == GIMPLE_PHI)
    2761                 :            :         {
    2762                 :    5172750 :           int ix = PHI_ARG_INDEX_FROM_USE (use_p);
    2763                 :    5172750 :           edge e = gimple_phi_arg_edge (as_a <gphi *> (stmt), ix);
    2764                 :    5172750 :           mark_use_interesting (name, stmt, e->src, insert_phi_p);
    2765                 :            :         }
    2766                 :            :       else
    2767                 :            :         {
    2768                 :            :           /* For regular statements, mark this as an interesting use
    2769                 :            :              for NAME.  */
    2770                 :   43529800 :           mark_use_interesting (name, stmt, bb, insert_phi_p);
    2771                 :            :         }
    2772                 :            :     }
    2773                 :            : }
    2774                 :            : 
    2775                 :            : 
    2776                 :            : /* Helper for prepare_names_to_update.  Mark the definition site for
    2777                 :            :    NAME as interesting.  BLOCKS and INSERT_PHI_P are as in
    2778                 :            :    prepare_names_to_update.  */
    2779                 :            : 
    2780                 :            : static void
    2781                 :   18343200 : prepare_def_site_for (tree name, bool insert_phi_p)
    2782                 :            : {
    2783                 :   18343200 :   gimple *stmt;
    2784                 :   18343200 :   basic_block bb;
    2785                 :            : 
    2786                 :   19835800 :   gcc_checking_assert (names_to_release == NULL
    2787                 :            :                        || !bitmap_bit_p (names_to_release,
    2788                 :            :                                          SSA_NAME_VERSION (name)));
    2789                 :            : 
    2790                 :            :   /* If we rename virtual operands do not update them.  */
    2791                 :   18343200 :   if (virtual_operand_p (name)
    2792                 :   18343200 :       && cfun->gimple_df->rename_vops)
    2793                 :            :     return;
    2794                 :            : 
    2795                 :   18340600 :   stmt = SSA_NAME_DEF_STMT (name);
    2796                 :   18340600 :   bb = gimple_bb (stmt);
    2797                 :   18340600 :   if (bb)
    2798                 :            :     {
    2799                 :   17842700 :       gcc_checking_assert (bb->index < last_basic_block_for_fn (cfun));
    2800                 :   17842700 :       mark_block_for_update (bb);
    2801                 :   17842700 :       mark_def_interesting (name, stmt, bb, insert_phi_p);
    2802                 :            :     }
    2803                 :            : }
    2804                 :            : 
    2805                 :            : 
    2806                 :            : /* Mark definition and use sites of names in NEW_SSA_NAMES and
    2807                 :            :    OLD_SSA_NAMES.  INSERT_PHI_P is true if the caller wants to insert
    2808                 :            :    PHI nodes for newly created names.  */
    2809                 :            : 
    2810                 :            : static void
    2811                 :    1175220 : prepare_names_to_update (bool insert_phi_p)
    2812                 :            : {
    2813                 :    1175220 :   unsigned i = 0;
    2814                 :    1175220 :   bitmap_iterator bi;
    2815                 :    1175220 :   sbitmap_iterator sbi;
    2816                 :            : 
    2817                 :            :   /* If a name N from NEW_SSA_NAMES is also marked to be released,
    2818                 :            :      remove it from NEW_SSA_NAMES so that we don't try to visit its
    2819                 :            :      defining basic block (which most likely doesn't exist).  Notice
    2820                 :            :      that we cannot do the same with names in OLD_SSA_NAMES because we
    2821                 :            :      want to replace existing instances.  */
    2822                 :    1175220 :   if (names_to_release)
    2823                 :     482434 :     EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
    2824                 :     387283 :       bitmap_clear_bit (new_ssa_names, i);
    2825                 :            : 
    2826                 :            :   /* First process names in NEW_SSA_NAMES.  Otherwise, uses of old
    2827                 :            :      names may be considered to be live-in on blocks that contain
    2828                 :            :      definitions for their replacements.  */
    2829                 :   13704900 :   EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
    2830                 :   11354500 :     prepare_def_site_for (ssa_name (i), insert_phi_p);
    2831                 :            : 
    2832                 :            :   /* If an old name is in NAMES_TO_RELEASE, we cannot remove it from
    2833                 :            :      OLD_SSA_NAMES, but we have to ignore its definition site.  */
    2834                 :    9715720 :   EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
    2835                 :            :     {
    2836                 :    7365290 :       if (names_to_release == NULL || !bitmap_bit_p (names_to_release, i))
    2837                 :    6988670 :         prepare_def_site_for (ssa_name (i), insert_phi_p);
    2838                 :    7365290 :       prepare_use_sites_for (ssa_name (i), insert_phi_p);
    2839                 :            :     }
    2840                 :    1175220 : }
    2841                 :            : 
    2842                 :            : 
    2843                 :            : /* Dump all the names replaced by NAME to FILE.  */
    2844                 :            : 
    2845                 :            : void
    2846                 :      21177 : dump_names_replaced_by (FILE *file, tree name)
    2847                 :            : {
    2848                 :      21177 :   unsigned i;
    2849                 :      21177 :   bitmap old_set;
    2850                 :      21177 :   bitmap_iterator bi;
    2851                 :            : 
    2852                 :      21177 :   print_generic_expr (file, name);
    2853                 :      21177 :   fprintf (file, " -> { ");
    2854                 :            : 
    2855                 :      21177 :   old_set = names_replaced_by (name);
    2856                 :      42415 :   EXECUTE_IF_SET_IN_BITMAP (old_set, 0, i, bi)
    2857                 :            :     {
    2858                 :      21238 :       print_generic_expr (file, ssa_name (i));
    2859                 :      21238 :       fprintf (file, " ");
    2860                 :            :     }
    2861                 :            : 
    2862                 :      21177 :   fprintf (file, "}\n");
    2863                 :      21177 : }
    2864                 :            : 
    2865                 :            : 
    2866                 :            : /* Dump all the names replaced by NAME to stderr.  */
    2867                 :            : 
    2868                 :            : DEBUG_FUNCTION void
    2869                 :          0 : debug_names_replaced_by (tree name)
    2870                 :            : {
    2871                 :          0 :   dump_names_replaced_by (stderr, name);
    2872                 :          0 : }
    2873                 :            : 
    2874                 :            : 
    2875                 :            : /* Dump SSA update information to FILE.  */
    2876                 :            : 
    2877                 :            : void
    2878                 :       3054 : dump_update_ssa (FILE *file)
    2879                 :            : {
    2880                 :       3054 :   unsigned i = 0;
    2881                 :       3054 :   bitmap_iterator bi;
    2882                 :            : 
    2883                 :       3054 :   if (!need_ssa_update_p (cfun))
    2884                 :          0 :     return;
    2885                 :            : 
    2886                 :       3054 :   if (new_ssa_names && bitmap_first_set_bit (new_ssa_names) >= 0)
    2887                 :            :     {
    2888                 :       1779 :       sbitmap_iterator sbi;
    2889                 :            : 
    2890                 :       1779 :       fprintf (file, "\nSSA replacement table\n");
    2891                 :       1779 :       fprintf (file, "N_i -> { O_1 ... O_j } means that N_i replaces "
    2892                 :            :                      "O_1, ..., O_j\n\n");
    2893                 :            : 
    2894                 :      24735 :       EXECUTE_IF_SET_IN_BITMAP (new_ssa_names, 0, i, sbi)
    2895                 :      21177 :         dump_names_replaced_by (file, ssa_name (i));
    2896                 :            :     }
    2897                 :            : 
    2898                 :       3054 :   if (symbols_to_rename_set && !bitmap_empty_p (symbols_to_rename_set))
    2899                 :            :     {
    2900                 :       1368 :       fprintf (file, "\nSymbols to be put in SSA form\n");
    2901                 :       1368 :       dump_decl_set (file, symbols_to_rename_set);
    2902                 :       1368 :       fprintf (file, "\n");
    2903                 :            :     }
    2904                 :            : 
    2905                 :       3054 :   if (names_to_release && !bitmap_empty_p (names_to_release))
    2906                 :            :     {
    2907                 :         36 :       fprintf (file, "\nSSA names to release after updating the SSA web\n\n");
    2908                 :        134 :       EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
    2909                 :            :         {
    2910                 :         98 :           print_generic_expr (file, ssa_name (i));
    2911                 :         98 :           fprintf (file, " ");
    2912                 :            :         }
    2913                 :         36 :       fprintf (file, "\n");
    2914                 :            :     }
    2915                 :            : }
    2916                 :            : 
    2917                 :            : 
    2918                 :            : /* Dump SSA update information to stderr.  */
    2919                 :            : 
    2920                 :            : DEBUG_FUNCTION void
    2921                 :          0 : debug_update_ssa (void)
    2922                 :            : {
    2923                 :          0 :   dump_update_ssa (stderr);
    2924                 :          0 : }
    2925                 :            : 
    2926                 :            : 
    2927                 :            : /* Initialize data structures used for incremental SSA updates.  */
    2928                 :            : 
    2929                 :            : static void
    2930                 :    2722530 : init_update_ssa (struct function *fn)
    2931                 :            : {
    2932                 :            :   /* Reserve more space than the current number of names.  The calls to
    2933                 :            :      add_new_name_mapping are typically done after creating new SSA
    2934                 :            :      names, so we'll need to reallocate these arrays.  */
    2935                 :    5445070 :   old_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
    2936                 :    2722530 :   bitmap_clear (old_ssa_names);
    2937                 :            : 
    2938                 :    5445070 :   new_ssa_names = sbitmap_alloc (num_ssa_names + NAME_SETS_GROWTH_FACTOR);
    2939                 :    2722530 :   bitmap_clear (new_ssa_names);
    2940                 :            : 
    2941                 :    2722530 :   bitmap_obstack_initialize (&update_ssa_obstack);
    2942                 :            : 
    2943                 :    2722530 :   names_to_release = NULL;
    2944                 :    2722530 :   update_ssa_initialized_fn = fn;
    2945                 :    2722530 : }
    2946                 :            : 
    2947                 :            : 
    2948                 :            : /* Deallocate data structures used for incremental SSA updates.  */
    2949                 :            : 
    2950                 :            : void
    2951                 :    2722530 : delete_update_ssa (void)
    2952                 :            : {
    2953                 :    2722530 :   unsigned i;
    2954                 :    2722530 :   bitmap_iterator bi;
    2955                 :            : 
    2956                 :    2722530 :   sbitmap_free (old_ssa_names);
    2957                 :    2722530 :   old_ssa_names = NULL;
    2958                 :            : 
    2959                 :    2722530 :   sbitmap_free (new_ssa_names);
    2960                 :    2722530 :   new_ssa_names = NULL;
    2961                 :            : 
    2962                 :    2722530 :   BITMAP_FREE (symbols_to_rename_set);
    2963                 :    2722530 :   symbols_to_rename_set = NULL;
    2964                 :    2722530 :   symbols_to_rename.release ();
    2965                 :            : 
    2966                 :    2722530 :   if (names_to_release)
    2967                 :            :     {
    2968                 :     482434 :       EXECUTE_IF_SET_IN_BITMAP (names_to_release, 0, i, bi)
    2969                 :     387283 :         release_ssa_name (ssa_name (i));
    2970                 :      95151 :       BITMAP_FREE (names_to_release);
    2971                 :            :     }
    2972                 :            : 
    2973                 :    2722530 :   clear_ssa_name_info ();
    2974                 :            : 
    2975                 :    2722530 :   fini_ssa_renamer ();
    2976                 :            : 
    2977                 :    2722530 :   if (blocks_with_phis_to_rewrite)
    2978                 :   10798600 :     EXECUTE_IF_SET_IN_BITMAP (blocks_with_phis_to_rewrite, 0, i, bi)
    2979                 :   16177900 :       phis_to_rewrite[i].release ();
    2980                 :            : 
    2981                 :    2722530 :   BITMAP_FREE (blocks_with_phis_to_rewrite);
    2982                 :    2722530 :   BITMAP_FREE (blocks_to_update);
    2983                 :            : 
    2984                 :    2722530 :   update_ssa_initialized_fn = NULL;
    2985                 :    2722530 : }
    2986                 :            : 
    2987                 :            : 
    2988                 :            : /* Create a new name for OLD_NAME in statement STMT and replace the
    2989                 :            :    operand pointed to by DEF_P with the newly created name.  If DEF_P
    2990                 :            :    is NULL then STMT should be a GIMPLE assignment.
    2991                 :            :    Return the new name and register the replacement mapping <NEW, OLD> in
    2992                 :            :    update_ssa's tables.  */
    2993                 :            : 
    2994                 :            : tree
    2995                 :   11593000 : create_new_def_for (tree old_name, gimple *stmt, def_operand_p def)
    2996                 :            : {
    2997                 :   11593000 :   tree new_name;
    2998                 :            : 
    2999                 :   11593000 :   timevar_push (TV_TREE_SSA_INCREMENTAL);
    3000                 :            : 
    3001                 :   11593000 :   if (!update_ssa_initialized_fn)
    3002                 :    1188040 :     init_update_ssa (cfun);
    3003                 :            : 
    3004                 :   11593000 :   gcc_assert (update_ssa_initialized_fn == cfun);
    3005                 :            : 
    3006                 :   11593000 :   new_name = duplicate_ssa_name (old_name, stmt);
    3007                 :   11593000 :   if (def)
    3008                 :    5932140 :     SET_DEF (def, new_name);
    3009                 :            :   else
    3010                 :    5660870 :     gimple_assign_set_lhs (stmt, new_name);
    3011                 :            : 
    3012                 :   11593000 :   if (gimple_code (stmt) == GIMPLE_PHI)
    3013                 :            :     {
    3014                 :    3455650 :       basic_block bb = gimple_bb (stmt);
    3015                 :            : 
    3016                 :            :       /* If needed, mark NEW_NAME as occurring in an abnormal PHI node. */
    3017                 :    3455650 :       SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) = bb_has_abnormal_pred (bb);
    3018                 :            :     }
    3019                 :            : 
    3020                 :   11593000 :   add_new_name_mapping (new_name, old_name);
    3021                 :            : 
    3022                 :            :   /* For the benefit of passes that will be updating the SSA form on
    3023                 :            :      their own, set the current reaching definition of OLD_NAME to be
    3024                 :            :      NEW_NAME.  */
    3025                 :   11593000 :   get_ssa_name_ann (old_name)->info.current_def = new_name;
    3026                 :            : 
    3027                 :   11593000 :   timevar_pop (TV_TREE_SSA_INCREMENTAL);
    3028                 :            : 
    3029                 :   11593000 :   return new_name;
    3030                 :            : }
    3031                 :            : 
    3032                 :            : 
    3033                 :            : /* Mark virtual operands of FN for renaming by update_ssa.  */
    3034                 :            : 
    3035                 :            : void
    3036                 :     252539 : mark_virtual_operands_for_renaming (struct function *fn)
    3037                 :            : {
    3038                 :     252539 :   fn->gimple_df->ssa_renaming_needed = 1;
    3039                 :     252539 :   fn->gimple_df->rename_vops = 1;
    3040                 :     252539 : }
    3041                 :            : 
    3042                 :            : /* Replace all uses of NAME by underlying variable and mark it
    3043                 :            :    for renaming.  This assumes the defining statement of NAME is
    3044                 :            :    going to be removed.  */
    3045                 :            : 
    3046                 :            : void
    3047                 :     207235 : mark_virtual_operand_for_renaming (tree name)
    3048                 :            : {
    3049                 :     207235 :   tree name_var = SSA_NAME_VAR (name);
    3050                 :     207235 :   bool used = false;
    3051                 :     207235 :   imm_use_iterator iter;
    3052                 :     207235 :   use_operand_p use_p;
    3053                 :     207235 :   gimple *stmt;
    3054                 :            : 
    3055                 :     207235 :   gcc_assert (VAR_DECL_IS_VIRTUAL_OPERAND (name_var));
    3056                 :     280065 :   FOR_EACH_IMM_USE_STMT (stmt, iter, name)
    3057                 :            :     {
    3058                 :     291438 :       FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
    3059                 :      72889 :         SET_USE (use_p, name_var);
    3060                 :      72830 :       used = true;
    3061                 :            :     }
    3062                 :     207235 :   if (used)
    3063                 :      56416 :     mark_virtual_operands_for_renaming (cfun);
    3064                 :     207235 : }
    3065                 :            : 
    3066                 :            : /* Replace all uses of the virtual PHI result by its underlying variable
    3067                 :            :    and mark it for renaming.  This assumes the PHI node is going to be
    3068                 :            :    removed.  */
    3069                 :            : 
    3070                 :            : void
    3071                 :      30089 : mark_virtual_phi_result_for_renaming (gphi *phi)
    3072                 :            : {
    3073                 :      30089 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3074                 :            :     {
    3075                 :         39 :       fprintf (dump_file, "Marking result for renaming : ");
    3076                 :         39 :       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
    3077                 :         39 :       fprintf (dump_file, "\n");
    3078                 :            :     }
    3079                 :            : 
    3080                 :      30089 :   mark_virtual_operand_for_renaming (gimple_phi_result (phi));
    3081                 :      30089 : }
    3082                 :            : 
    3083                 :            : /* Return true if there is any work to be done by update_ssa
    3084                 :            :    for function FN.  */
    3085                 :            : 
    3086                 :            : bool
    3087                 :  895820000 : need_ssa_update_p (struct function *fn)
    3088                 :            : {
    3089                 :  895820000 :   gcc_assert (fn != NULL);
    3090                 :  895820000 :   return (update_ssa_initialized_fn == fn
    3091                 :  895820000 :           || (fn->gimple_df && fn->gimple_df->ssa_renaming_needed));
    3092                 :            : }
    3093                 :            : 
    3094                 :            : /* Return true if name N has been registered in the replacement table.  */
    3095                 :            : 
    3096                 :            : bool
    3097                 :  133337000 : name_registered_for_update_p (tree n ATTRIBUTE_UNUSED)
    3098                 :            : {
    3099                 :  133337000 :   if (!update_ssa_initialized_fn)
    3100                 :            :     return false;
    3101                 :            : 
    3102                 :    2662960 :   gcc_assert (update_ssa_initialized_fn == cfun);
    3103                 :            : 
    3104                 :    2662960 :   return is_new_name (n) || is_old_name (n);
    3105                 :            : }
    3106                 :            : 
    3107                 :            : 
    3108                 :            : /* Mark NAME to be released after update_ssa has finished.  */
    3109                 :            : 
    3110                 :            : void
    3111                 :     387283 : release_ssa_name_after_update_ssa (tree name)
    3112                 :            : {
    3113                 :     387283 :   gcc_assert (cfun && update_ssa_initialized_fn == cfun);
    3114                 :            : 
    3115                 :     387283 :   if (names_to_release == NULL)
    3116                 :      95151 :     names_to_release = BITMAP_ALLOC (NULL);
    3117                 :            : 
    3118                 :     387283 :   bitmap_set_bit (names_to_release, SSA_NAME_VERSION (name));
    3119                 :     387283 : }
    3120                 :            : 
    3121                 :            : 
    3122                 :            : /* Insert new PHI nodes to replace VAR.  DFS contains dominance
    3123                 :            :    frontier information.  BLOCKS is the set of blocks to be updated.
    3124                 :            : 
    3125                 :            :    This is slightly different than the regular PHI insertion
    3126                 :            :    algorithm.  The value of UPDATE_FLAGS controls how PHI nodes for
    3127                 :            :    real names (i.e., GIMPLE registers) are inserted:
    3128                 :            : 
    3129                 :            :    - If UPDATE_FLAGS == TODO_update_ssa, we are only interested in PHI
    3130                 :            :      nodes inside the region affected by the block that defines VAR
    3131                 :            :      and the blocks that define all its replacements.  All these
    3132                 :            :      definition blocks are stored in DEF_BLOCKS[VAR]->DEF_BLOCKS.
    3133                 :            : 
    3134                 :            :      First, we compute the entry point to the region (ENTRY).  This is
    3135                 :            :      given by the nearest common dominator to all the definition
    3136                 :            :      blocks. When computing the iterated dominance frontier (IDF), any
    3137                 :            :      block not strictly dominated by ENTRY is ignored.
    3138                 :            : 
    3139                 :            :      We then call the standard PHI insertion algorithm with the pruned
    3140                 :            :      IDF.
    3141                 :            : 
    3142                 :            :    - If UPDATE_FLAGS == TODO_update_ssa_full_phi, the IDF for real
    3143                 :            :      names is not pruned.  PHI nodes are inserted at every IDF block.  */
    3144                 :            : 
    3145                 :            : static void
    3146                 :    9796960 : insert_updated_phi_nodes_for (tree var, bitmap_head *dfs, bitmap blocks,
    3147                 :            :                               unsigned update_flags)
    3148                 :            : {
    3149                 :    9796960 :   basic_block entry;
    3150                 :    9796960 :   def_blocks *db;
    3151                 :    9796960 :   bitmap idf, pruned_idf;
    3152                 :    9796960 :   bitmap_iterator bi;
    3153                 :    9796960 :   unsigned i;
    3154                 :            : 
    3155                 :    9796960 :   if (TREE_CODE (var) == SSA_NAME)
    3156                 :    3800900 :     gcc_checking_assert (is_old_name (var));
    3157                 :            :   else
    3158                 :    5996060 :     gcc_checking_assert (marked_for_renaming (var));
    3159                 :            : 
    3160                 :            :   /* Get all the definition sites for VAR.  */
    3161                 :    9796960 :   db = find_def_blocks_for (var);
    3162                 :            : 
    3163                 :            :   /* No need to do anything if there were no definitions to VAR.  */
    3164                 :    9794850 :   if (db == NULL || bitmap_empty_p (db->def_blocks))
    3165                 :     141740 :     return;
    3166                 :            : 
    3167                 :            :   /* Compute the initial iterated dominance frontier.  */
    3168                 :    9655220 :   idf = compute_idf (db->def_blocks, dfs);
    3169                 :    9655220 :   pruned_idf = BITMAP_ALLOC (NULL);
    3170                 :            : 
    3171                 :    9655220 :   if (TREE_CODE (var) == SSA_NAME)
    3172                 :            :     {
    3173                 :    3798800 :       if (update_flags == TODO_update_ssa)
    3174                 :            :         {
    3175                 :            :           /* If doing regular SSA updates for GIMPLE registers, we are
    3176                 :            :              only interested in IDF blocks dominated by the nearest
    3177                 :            :              common dominator of all the definition blocks.  */
    3178                 :    3798800 :           entry = nearest_common_dominator_for_set (CDI_DOMINATORS,
    3179                 :            :                                                     db->def_blocks);
    3180                 :    3798800 :           if (entry != ENTRY_BLOCK_PTR_FOR_FN (cfun))
    3181                 :   16964900 :             EXECUTE_IF_SET_IN_BITMAP (idf, 0, i, bi)
    3182                 :   13166100 :               if (BASIC_BLOCK_FOR_FN (cfun, i) != entry
    3183                 :   13166100 :                   && dominated_by_p (CDI_DOMINATORS,
    3184                 :   12477800 :                                      BASIC_BLOCK_FOR_FN (cfun, i), entry))
    3185                 :    5452010 :                 bitmap_set_bit (pruned_idf, i);
    3186                 :            :         }
    3187                 :            :       else
    3188                 :            :         {
    3189                 :            :           /* Otherwise, do not prune the IDF for VAR.  */
    3190                 :          0 :           gcc_checking_assert (update_flags == TODO_update_ssa_full_phi);
    3191                 :          0 :           bitmap_copy (pruned_idf, idf);
    3192                 :            :         }
    3193                 :            :     }
    3194                 :            :   else
    3195                 :            :     {
    3196                 :            :       /* Otherwise, VAR is a symbol that needs to be put into SSA form
    3197                 :            :          for the first time, so we need to compute the full IDF for
    3198                 :            :          it.  */
    3199                 :    5856410 :       bitmap_copy (pruned_idf, idf);
    3200                 :            :     }
    3201                 :            : 
    3202                 :    9655220 :   if (!bitmap_empty_p (pruned_idf))
    3203                 :            :     {
    3204                 :            :       /* Make sure that PRUNED_IDF blocks and all their feeding blocks
    3205                 :            :          are included in the region to be updated.  The feeding blocks
    3206                 :            :          are important to guarantee that the PHI arguments are renamed
    3207                 :            :          properly.  */
    3208                 :            : 
    3209                 :            :       /* FIXME, this is not needed if we are updating symbols.  We are
    3210                 :            :          already starting at the ENTRY block anyway.  */
    3211                 :    5866200 :       bitmap_ior_into (blocks, pruned_idf);
    3212                 :   22923700 :       EXECUTE_IF_SET_IN_BITMAP (pruned_idf, 0, i, bi)
    3213                 :            :         {
    3214                 :   17057500 :           edge e;
    3215                 :   17057500 :           edge_iterator ei;
    3216                 :   17057500 :           basic_block bb = BASIC_BLOCK_FOR_FN (cfun, i);
    3217                 :            : 
    3218                 :  125334000 :           FOR_EACH_EDGE (e, ei, bb->preds)
    3219                 :  108277000 :             if (e->src->index >= 0)
    3220                 :  108277000 :               bitmap_set_bit (blocks, e->src->index);
    3221                 :            :         }
    3222                 :            : 
    3223                 :    5866200 :       insert_phi_nodes_for (var, pruned_idf, true);
    3224                 :            :     }
    3225                 :            : 
    3226                 :    9655220 :   BITMAP_FREE (pruned_idf);
    3227                 :    9655220 :   BITMAP_FREE (idf);
    3228                 :            : }
    3229                 :            : 
    3230                 :            : /* Sort symbols_to_rename after their DECL_UID.  */
    3231                 :            : 
    3232                 :            : static int
    3233                 :  106560000 : insert_updated_phi_nodes_compare_uids (const void *a, const void *b)
    3234                 :            : {
    3235                 :  106560000 :   const_tree syma = *(const const_tree *)a;
    3236                 :  106560000 :   const_tree symb = *(const const_tree *)b;
    3237                 :  106560000 :   if (DECL_UID (syma) == DECL_UID (symb))
    3238                 :            :     return 0;
    3239                 :  106560000 :   return DECL_UID (syma) < DECL_UID (symb) ? -1 : 1;
    3240                 :            : }
    3241                 :            : 
    3242                 :            : /* Given a set of newly created SSA names (NEW_SSA_NAMES) and a set of
    3243                 :            :    existing SSA names (OLD_SSA_NAMES), update the SSA form so that:
    3244                 :            : 
    3245                 :            :    1- The names in OLD_SSA_NAMES dominated by the definitions of
    3246                 :            :       NEW_SSA_NAMES are all re-written to be reached by the
    3247                 :            :       appropriate definition from NEW_SSA_NAMES.
    3248                 :            : 
    3249                 :            :    2- If needed, new PHI nodes are added to the iterated dominance
    3250                 :            :       frontier of the blocks where each of NEW_SSA_NAMES are defined.
    3251                 :            : 
    3252                 :            :    The mapping between OLD_SSA_NAMES and NEW_SSA_NAMES is setup by
    3253                 :            :    calling create_new_def_for to create new defs for names that the
    3254                 :            :    caller wants to replace.
    3255                 :            : 
    3256                 :            :    The caller cretaes the new names to be inserted and the names that need
    3257                 :            :    to be replaced by calling create_new_def_for for each old definition
    3258                 :            :    to be replaced.  Note that the function assumes that the
    3259                 :            :    new defining statement has already been inserted in the IL.
    3260                 :            : 
    3261                 :            :    For instance, given the following code:
    3262                 :            : 
    3263                 :            :      1  L0:
    3264                 :            :      2  x_1 = PHI (0, x_5)
    3265                 :            :      3  if (x_1 < 10)
    3266                 :            :      4    if (x_1 > 7)
    3267                 :            :      5      y_2 = 0
    3268                 :            :      6    else
    3269                 :            :      7      y_3 = x_1 + x_7
    3270                 :            :      8    endif
    3271                 :            :      9    x_5 = x_1 + 1
    3272                 :            :      10   goto L0;
    3273                 :            :      11 endif
    3274                 :            : 
    3275                 :            :    Suppose that we insert new names x_10 and x_11 (lines 4 and 8).
    3276                 :            : 
    3277                 :            :      1  L0:
    3278                 :            :      2  x_1 = PHI (0, x_5)
    3279                 :            :      3  if (x_1 < 10)
    3280                 :            :      4    x_10 = ...
    3281                 :            :      5    if (x_1 > 7)
    3282                 :            :      6      y_2 = 0
    3283                 :            :      7    else
    3284                 :            :      8      x_11 = ...
    3285                 :            :      9      y_3 = x_1 + x_7
    3286                 :            :      10   endif
    3287                 :            :      11   x_5 = x_1 + 1
    3288                 :            :      12   goto L0;
    3289                 :            :      13 endif
    3290                 :            : 
    3291                 :            :    We want to replace all the uses of x_1 with the new definitions of
    3292                 :            :    x_10 and x_11.  Note that the only uses that should be replaced are
    3293                 :            :    those at lines 5, 9 and 11.  Also, the use of x_7 at line 9 should
    3294                 :            :    *not* be replaced (this is why we cannot just mark symbol 'x' for
    3295                 :            :    renaming).
    3296                 :            : 
    3297                 :            :    Additionally, we may need to insert a PHI node at line 11 because
    3298                 :            :    that is a merge point for x_10 and x_11.  So the use of x_1 at line
    3299                 :            :    11 will be replaced with the new PHI node.  The insertion of PHI
    3300                 :            :    nodes is optional.  They are not strictly necessary to preserve the
    3301                 :            :    SSA form, and depending on what the caller inserted, they may not
    3302                 :            :    even be useful for the optimizers.  UPDATE_FLAGS controls various
    3303                 :            :    aspects of how update_ssa operates, see the documentation for
    3304                 :            :    TODO_update_ssa*.  */
    3305                 :            : 
    3306                 :            : void
    3307                 :   41981900 : update_ssa (unsigned update_flags)
    3308                 :            : {
    3309                 :   41981900 :   basic_block bb, start_bb;
    3310                 :   41981900 :   bitmap_iterator bi;
    3311                 :   41981900 :   unsigned i = 0;
    3312                 :   41981900 :   bool insert_phi_p;
    3313                 :   41981900 :   sbitmap_iterator sbi;
    3314                 :   41981900 :   tree sym;
    3315                 :            : 
    3316                 :            :   /* Only one update flag should be set.  */
    3317                 :   41981900 :   gcc_assert (update_flags == TODO_update_ssa
    3318                 :            :               || update_flags == TODO_update_ssa_no_phi
    3319                 :            :               || update_flags == TODO_update_ssa_full_phi
    3320                 :            :               || update_flags == TODO_update_ssa_only_virtuals);
    3321                 :            : 
    3322                 :   41981900 :   if (!need_ssa_update_p (cfun))
    3323                 :   39272200 :     return;
    3324                 :            : 
    3325                 :    2709710 :   if (flag_checking)
    3326                 :            :     {
    3327                 :    2709640 :       timevar_push (TV_TREE_STMT_VERIFY);
    3328                 :            : 
    3329                 :    2709640 :       bool err = false;
    3330                 :            : 
    3331                 :   72643800 :       FOR_EACH_BB_FN (bb, cfun)
    3332                 :            :         {
    3333                 :   69934200 :           gimple_stmt_iterator gsi;
    3334                 :  645319000 :           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3335                 :            :             {
    3336                 :  505451000 :               gimple *stmt = gsi_stmt (gsi);
    3337                 :            : 
    3338                 :  505451000 :               ssa_op_iter i;
    3339                 :  505451000 :               use_operand_p use_p;
    3340                 :  856917000 :               FOR_EACH_SSA_USE_OPERAND (use_p, stmt, i, SSA_OP_ALL_USES)
    3341                 :            :                 {
    3342                 :  351466000 :                   tree use = USE_FROM_PTR (use_p);
    3343                 :  351466000 :                   if (TREE_CODE (use) != SSA_NAME)
    3344                 :   17926100 :                     continue;
    3345                 :            : 
    3346                 :  333540000 :                   if (SSA_NAME_IN_FREE_LIST (use))
    3347                 :            :                     {
    3348                 :          0 :                       error ("statement uses released SSA name");
    3349                 :          0 :                       debug_gimple_stmt (stmt);
    3350                 :          0 :                       fprintf (stderr, "The use of ");
    3351                 :          0 :                       print_generic_expr (stderr, use);
    3352                 :          0 :                       fprintf (stderr," should have been replaced\n");
    3353                 :          0 :                       err = true;
    3354                 :            :                     }
    3355                 :            :                 }
    3356                 :            :             }
    3357                 :            :         }
    3358                 :            : 
    3359                 :    2709640 :       if (err)
    3360                 :          0 :         internal_error ("cannot update SSA form");
    3361                 :            : 
    3362                 :    2709640 :       timevar_pop (TV_TREE_STMT_VERIFY);
    3363                 :            :     }
    3364                 :            : 
    3365                 :    2709710 :   timevar_push (TV_TREE_SSA_INCREMENTAL);
    3366                 :            : 
    3367                 :    2709710 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3368                 :       1863 :     fprintf (dump_file, "\nUpdating SSA:\n");
    3369                 :            : 
    3370                 :    2709710 :   if (!update_ssa_initialized_fn)
    3371                 :    1534500 :     init_update_ssa (cfun);
    3372                 :    1175220 :   else if (update_flags == TODO_update_ssa_only_virtuals)
    3373                 :            :     {
    3374                 :            :       /* If we only need to update virtuals, remove all the mappings for
    3375                 :            :          real names before proceeding.  The caller is responsible for
    3376                 :            :          having dealt with the name mappings before calling update_ssa.  */
    3377                 :          0 :       bitmap_clear (old_ssa_names);
    3378                 :          0 :       bitmap_clear (new_ssa_names);
    3379                 :            :     }
    3380                 :            : 
    3381                 :    2709710 :   gcc_assert (update_ssa_initialized_fn == cfun);
    3382                 :            : 
    3383                 :    2709710 :   blocks_with_phis_to_rewrite = BITMAP_ALLOC (NULL);
    3384                 :    2709710 :   if (!phis_to_rewrite.exists ())
    3385                 :      90757 :     phis_to_rewrite.create (last_basic_block_for_fn (cfun) + 1);
    3386                 :    2709710 :   blocks_to_update = BITMAP_ALLOC (NULL);
    3387                 :            : 
    3388                 :            :   /* Ensure that the dominance information is up-to-date.  */
    3389                 :    2709710 :   calculate_dominance_info (CDI_DOMINATORS);
    3390                 :            : 
    3391                 :    2709710 :   insert_phi_p = (update_flags != TODO_update_ssa_no_phi);
    3392                 :            : 
    3393                 :            :   /* If there are names defined in the replacement table, prepare
    3394                 :            :      definition and use sites for all the names in NEW_SSA_NAMES and
    3395                 :            :      OLD_SSA_NAMES.  */
    3396                 :    2709710 :   if (bitmap_first_set_bit (new_ssa_names) >= 0)
    3397                 :            :     {
    3398                 :    1175220 :       statistics_counter_event (cfun, "Incremental SSA update", 1);
    3399                 :            : 
    3400                 :    1175220 :       prepare_names_to_update (insert_phi_p);
    3401                 :            : 
    3402                 :            :       /* If all the names in NEW_SSA_NAMES had been marked for
    3403                 :            :          removal, and there are no symbols to rename, then there's
    3404                 :            :          nothing else to do.  */
    3405                 :    1175220 :       if (bitmap_first_set_bit (new_ssa_names) < 0
    3406                 :    1175220 :           && !cfun->gimple_df->ssa_renaming_needed)
    3407                 :         52 :         goto done;
    3408                 :            :     }
    3409                 :            : 
    3410                 :            :   /* Next, determine the block at which to start the renaming process.  */
    3411                 :    2709660 :   if (cfun->gimple_df->ssa_renaming_needed)
    3412                 :            :     {
    3413                 :    1535090 :       statistics_counter_event (cfun, "Symbol to SSA rewrite", 1);
    3414                 :            : 
    3415                 :            :       /* If we rename bare symbols initialize the mapping to
    3416                 :            :          auxiliar info we need to keep track of.  */
    3417                 :    1535090 :       var_infos = new hash_table<var_info_hasher> (47);
    3418                 :            : 
    3419                 :            :       /* If we have to rename some symbols from scratch, we need to
    3420                 :            :          start the process at the root of the CFG.  FIXME, it should
    3421                 :            :          be possible to determine the nearest block that had a
    3422                 :            :          definition for each of the symbols that are marked for
    3423                 :            :          updating.  For now this seems more work than it's worth.  */
    3424                 :    1535090 :       start_bb = ENTRY_BLOCK_PTR_FOR_FN (cfun);
    3425                 :            : 
    3426                 :            :       /* Traverse the CFG looking for existing definitions and uses of
    3427                 :            :          symbols in SSA operands.  Mark interesting blocks and
    3428                 :            :          statements and set local live-in information for the PHI
    3429                 :            :          placement heuristics.  */
    3430                 :    1535090 :       prepare_block_for_update (start_bb, insert_phi_p);
    3431                 :            : 
    3432                 :    1535090 :       tree name;
    3433                 :            : 
    3434                 :    1535090 :       if (flag_checking)
    3435                 :  100288000 :         FOR_EACH_SSA_NAME (i, name, cfun)
    3436                 :            :           {
    3437                 :  152109000 :             if (virtual_operand_p (name))
    3438                 :   30091600 :               continue;
    3439                 :            : 
    3440                 :            :             /* For all but virtual operands, which do not have SSA names
    3441                 :            :                with overlapping life ranges, ensure that symbols marked
    3442                 :            :                for renaming do not have existing SSA names associated with
    3443                 :            :                them as we do not re-write them out-of-SSA before going
    3444                 :            :                into SSA for the remaining symbol uses.  */
    3445                 :   56430300 :             if (marked_for_renaming (SSA_NAME_VAR (name)))
    3446                 :            :               {
    3447                 :          0 :                 fprintf (stderr, "Existing SSA name for symbol marked for "
    3448                 :            :                          "renaming: ");
    3449                 :          0 :                 print_generic_expr (stderr, name, TDF_SLIM);
    3450                 :          0 :                 fprintf (stderr, "\n");
    3451                 :          0 :                 internal_error ("SSA corruption");
    3452                 :            :               }
    3453                 :            :           }
    3454                 :            :     }
    3455                 :            :   else
    3456                 :            :     {
    3457                 :            :       /* Otherwise, the entry block to the region is the nearest
    3458                 :            :          common dominator for the blocks in BLOCKS.  */
    3459                 :    1174570 :       start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
    3460                 :            :                                                    blocks_to_update);
    3461                 :            :     }
    3462                 :            : 
    3463                 :            :   /* If requested, insert PHI nodes at the iterated dominance frontier
    3464                 :            :      of every block, creating new definitions for names in OLD_SSA_NAMES
    3465                 :            :      and for symbols found.  */
    3466                 :    2709660 :   if (insert_phi_p)
    3467                 :            :     {
    3468                 :    2123900 :       bitmap_head *dfs;
    3469                 :            : 
    3470                 :            :       /* If the caller requested PHI nodes to be added, compute
    3471                 :            :          dominance frontiers.  */
    3472                 :    2123900 :       dfs = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
    3473                 :   60261300 :       FOR_EACH_BB_FN (bb, cfun)
    3474                 :   58137400 :         bitmap_initialize (&dfs[bb->index], &bitmap_default_obstack);
    3475                 :    2123900 :       compute_dominance_frontiers (dfs);
    3476                 :            : 
    3477                 :    2123900 :       if (bitmap_first_set_bit (old_ssa_names) >= 0)
    3478                 :            :         {
    3479                 :     589464 :           sbitmap_iterator sbi;
    3480                 :            : 
    3481                 :            :           /* insert_update_phi_nodes_for will call add_new_name_mapping
    3482                 :            :              when inserting new PHI nodes, so the set OLD_SSA_NAMES
    3483                 :            :              will grow while we are traversing it (but it will not
    3484                 :            :              gain any new members).  Copy OLD_SSA_NAMES to a temporary
    3485                 :            :              for traversal.  */
    3486                 :    1178930 :           auto_sbitmap tmp (SBITMAP_SIZE (old_ssa_names));
    3487                 :     589464 :           bitmap_copy (tmp, old_ssa_names);
    3488                 :    4979830 :           EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, sbi)
    3489                 :    3800900 :             insert_updated_phi_nodes_for (ssa_name (i), dfs, blocks_to_update,
    3490                 :            :                                           update_flags);
    3491                 :            :         }
    3492                 :            : 
    3493                 :    2123900 :       symbols_to_rename.qsort (insert_updated_phi_nodes_compare_uids);
    3494                 :    8119960 :       FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
    3495                 :    5996060 :         insert_updated_phi_nodes_for (sym, dfs, blocks_to_update,
    3496                 :            :                                       update_flags);
    3497                 :            : 
    3498                 :   60261300 :       FOR_EACH_BB_FN (bb, cfun)
    3499                 :   58137400 :         bitmap_clear (&dfs[bb->index]);
    3500                 :    2123900 :       free (dfs);
    3501                 :            : 
    3502                 :            :       /* Insertion of PHI nodes may have added blocks to the region.
    3503                 :            :          We need to re-compute START_BB to include the newly added
    3504                 :            :          blocks.  */
    3505                 :    2123900 :       if (start_bb != ENTRY_BLOCK_PTR_FOR_FN (cfun))
    3506                 :     588874 :         start_bb = nearest_common_dominator_for_set (CDI_DOMINATORS,
    3507                 :            :                                                      blocks_to_update);
    3508                 :            :     }
    3509                 :            : 
    3510                 :            :   /* Reset the current definition for name and symbol before renaming
    3511                 :            :      the sub-graph.  */
    3512                 :   12784400 :   EXECUTE_IF_SET_IN_BITMAP (old_ssa_names, 0, i, sbi)
    3513                 :    7365070 :     get_ssa_name_ann (ssa_name (i))->info.current_def = NULL_TREE;
    3514                 :            : 
    3515                 :    8705800 :   FOR_EACH_VEC_ELT (symbols_to_rename, i, sym)
    3516                 :    5996140 :     get_var_info (sym)->info.current_def = NULL_TREE;
    3517                 :            : 
    3518                 :            :   /* Now start the renaming process at START_BB.  */
    3519                 :    2709660 :   interesting_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun));
    3520                 :    2709660 :   bitmap_clear (interesting_blocks);
    3521                 :   51572800 :   EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
    3522                 :   48863100 :     bitmap_set_bit (interesting_blocks, i);
    3523                 :            : 
    3524                 :    2709660 :   rewrite_blocks (start_bb, REWRITE_UPDATE);
    3525                 :            : 
    3526                 :    2709660 :   sbitmap_free (interesting_blocks);
    3527                 :            : 
    3528                 :            :   /* Debugging dumps.  */
    3529                 :    2709660 :   if (dump_file)
    3530                 :            :     {
    3531                 :       3054 :       int c;
    3532                 :       3054 :       unsigned i;
    3533                 :            : 
    3534                 :       3054 :       dump_update_ssa (dump_file);
    3535                 :            : 
    3536                 :       3054 :       fprintf (dump_file, "Incremental SSA update started at block: %d\n",
    3537                 :            :                start_bb->index);
    3538                 :            : 
    3539                 :       3054 :       c = 0;
    3540                 :      30361 :       EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
    3541                 :      27307 :         c++;
    3542                 :       3054 :       fprintf (dump_file, "Number of blocks in CFG: %d\n",
    3543                 :       3054 :                last_basic_block_for_fn (cfun));
    3544                 :       3054 :       fprintf (dump_file, "Number of blocks to update: %d (%3.0f%%)\n",
    3545                 :       3054 :                c, PERCENT (c, last_basic_block_for_fn (cfun)));
    3546                 :            : 
    3547                 :       3054 :       if (dump_flags & TDF_DETAILS)
    3548                 :            :         {
    3549                 :       1863 :           fprintf (dump_file, "Affected blocks:");
    3550                 :      20964 :           EXECUTE_IF_SET_IN_BITMAP (blocks_to_update, 0, i, bi)
    3551                 :      19101 :             fprintf (dump_file, " %u", i);
    3552                 :       1863 :           fprintf (dump_file, "\n");
    3553                 :            :         }
    3554                 :            : 
    3555                 :       3054 :       fprintf (dump_file, "\n\n");
    3556                 :            :     }
    3557                 :            : 
    3558                 :            :   /* Free allocated memory.  */
    3559                 :    2706610 : done:
    3560                 :    2709710 :   delete_update_ssa ();
    3561                 :            : 
    3562                 :    2711110 :   timevar_pop (TV_TREE_SSA_INCREMENTAL);
    3563                 :            : }

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.