LCOV - code coverage report
Current view: top level - gcc - tree-ssa-ter.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 89.5 % 287 257
Test Date: 2024-11-30 13:30:02 Functions: 94.1 % 17 16
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Routines for performing Temporary Expression Replacement (TER) in SSA trees.
       2                 :             :    Copyright (C) 2003-2024 Free Software Foundation, Inc.
       3                 :             :    Contributed by Andrew MacLeod  <amacleod@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                 :             : 
      22                 :             : #include "config.h"
      23                 :             : #include "system.h"
      24                 :             : #include "coretypes.h"
      25                 :             : #include "backend.h"
      26                 :             : #include "tree.h"
      27                 :             : #include "gimple.h"
      28                 :             : #include "ssa.h"
      29                 :             : #include "gimple-pretty-print.h"
      30                 :             : #include "gimple-iterator.h"
      31                 :             : #include "dumpfile.h"
      32                 :             : #include "tree-ssa-live.h"
      33                 :             : #include "tree-ssa-ter.h"
      34                 :             : #include "tree-outof-ssa.h"
      35                 :             : #include "gimple-walk.h"
      36                 :             : 
      37                 :             : 
      38                 :             : /* Temporary Expression Replacement (TER)
      39                 :             : 
      40                 :             :    Replace SSA version variables during out-of-ssa with their defining
      41                 :             :    expression if there is only one use of the variable.
      42                 :             : 
      43                 :             :    This pass is required in order for the RTL expansion pass to see larger
      44                 :             :    chunks of code.  This allows it to make better choices on RTL pattern
      45                 :             :    selection.  When expand is rewritten and merged with out-of-ssa, and
      46                 :             :    understands SSA, this should be eliminated.
      47                 :             : 
      48                 :             :    A pass is made through the function, one block at a time.  No cross block
      49                 :             :    information is tracked.
      50                 :             : 
      51                 :             :    Variables which only have one use, and whose defining stmt is considered
      52                 :             :    a replaceable expression (see ssa_is_replaceable_p) are tracked to see whether
      53                 :             :    they can be replaced at their use location.
      54                 :             : 
      55                 :             :    n_12 = C * 10
      56                 :             :    a_2 = b_5 + 6
      57                 :             :    v_9 = a_2 * n_12
      58                 :             : 
      59                 :             :    if there are the only use of n_12 and a_2, TER will substitute in their
      60                 :             :    expressions in v_9, and end up with:
      61                 :             : 
      62                 :             :    v_9 = (b_5 + 6) * (C * 10)
      63                 :             : 
      64                 :             :    which will then have the ssa_name assigned to regular variables, and the
      65                 :             :    resulting code which will be passed to the expander looks something like:
      66                 :             : 
      67                 :             :    v = (b + 6) * (C * 10)
      68                 :             : 
      69                 :             : 
      70                 :             :    This requires ensuring that none of the variables used by the expression
      71                 :             :    change between the def point and where it is used.  Furthermore, if any
      72                 :             :    of the ssa_names used in this expression are themselves replaceable, we
      73                 :             :    have to ensure none of that expressions' arguments change either.
      74                 :             :    Although SSA_NAMES themselves don't change, this pass is performed after
      75                 :             :    coalescing has coalesced different SSA_NAMES together, so there could be a
      76                 :             :    definition of an SSA_NAME which is coalesced with a use that causes a
      77                 :             :    problem, i.e.,
      78                 :             : 
      79                 :             :    PHI b_5 = <b_8(2), b_14(1)>
      80                 :             :    <...>
      81                 :             :    a_2 = b_5 + 6
      82                 :             :    b_8 = c_4 + 4
      83                 :             :    v_9 = a_2 * n_12
      84                 :             :    <...>
      85                 :             : 
      86                 :             :    If b_5, b_8 and b_14 are all coalesced together...
      87                 :             :    The expression b_5 + 6 CANNOT replace the use in the statement defining v_9
      88                 :             :    because b_8 is in fact killing the value of b_5 since they share a partition
      89                 :             :    and will be assigned the same memory or register location.
      90                 :             : 
      91                 :             :    TER implements this but stepping through the instructions in a block and
      92                 :             :    tracking potential expressions for replacement, and the partitions they are
      93                 :             :    dependent on.  Expressions are represented by the SSA_NAME_VERSION of the
      94                 :             :    DEF on the LHS of a GIMPLE_ASSIGN and the expression is the RHS.
      95                 :             : 
      96                 :             :    When a stmt is determined to be a possible replacement expression, the
      97                 :             :    following steps are taken:
      98                 :             : 
      99                 :             :    EXPR_DECL_UID bitmap is allocated and set to the base variable UID of the
     100                 :             :    def and any uses in the expression.  non-NULL means the expression is being
     101                 :             :    tracked.  The UID's themselves are used to prevent TER substitution into
     102                 :             :    accumulating sequences, i.e.,
     103                 :             : 
     104                 :             :    x = x + y
     105                 :             :    x = x + z
     106                 :             :    x = x + w
     107                 :             :    etc.
     108                 :             :    this can result in very large expressions which don't accomplish anything
     109                 :             :    see PR tree-optimization/17549.
     110                 :             : 
     111                 :             :    PARTITION_DEPENDENCIES is another bitmap array, and it has a bit set for any
     112                 :             :    partition which is used in the expression.  This is primarily used to remove
     113                 :             :    an expression from the partition kill lists when a decision is made whether
     114                 :             :    to replace it or not.  This is indexed by ssa version number as well, and
     115                 :             :    indicates a partition number.  virtual operands are not tracked individually,
     116                 :             :    but they are summarized by an artificial partition called VIRTUAL_PARTITION.
     117                 :             :    This means a MAY or MUST def will kill *ALL* expressions that are dependent
     118                 :             :    on a virtual operand.
     119                 :             :    Note that the EXPR_DECL_UID and this bitmap represent very similar
     120                 :             :    information, but the info in one is not easy to obtain from the other.
     121                 :             : 
     122                 :             :    KILL_LIST is yet another bitmap array, this time it is indexed by partition
     123                 :             :    number, and represents a list of active expressions which will no
     124                 :             :    longer be valid if a definition into this partition takes place.
     125                 :             : 
     126                 :             :    PARTITION_IN_USE is simply a bitmap which is used to track which partitions
     127                 :             :    currently have something in their kill list.  This is used at the end of
     128                 :             :    a block to clear out the KILL_LIST bitmaps at the end of each block.
     129                 :             : 
     130                 :             :    NEW_REPLACEABLE_DEPENDENCIES is used as a temporary place to store
     131                 :             :    dependencies which will be reused by the current definition. All the uses
     132                 :             :    on an expression are processed before anything else is done. If a use is
     133                 :             :    determined to be a replaceable expression AND the current stmt is also going
     134                 :             :    to be replaceable, all the dependencies of this replaceable use will be
     135                 :             :    picked up by the current stmt's expression. Rather than recreate them, they
     136                 :             :    are simply copied here and then copied into the new expression when it is
     137                 :             :    processed.
     138                 :             : 
     139                 :             :    a_2 = b_5 + 6
     140                 :             :    v_8 = a_2 + c_4
     141                 :             : 
     142                 :             :    a_2's expression 'b_5 + 6' is determined to be replaceable at the use
     143                 :             :    location. It is dependent on the partition 'b_5' is in. This is cached into
     144                 :             :    the NEW_REPLACEABLE_DEPENDENCIES bitmap, and when v_8 is examined for
     145                 :             :    replaceability, it is a candidate, and it is dependent on the partition
     146                 :             :    b_5 is in *NOT* a_2, as well as c_4's partition.
     147                 :             : 
     148                 :             :    if v_8 is also replaceable:
     149                 :             : 
     150                 :             :    x_9 = v_8 * 5
     151                 :             : 
     152                 :             :    x_9 is dependent on partitions b_5, and c_4
     153                 :             : 
     154                 :             :    if a statement is found which has either of those partitions written to
     155                 :             :    before x_9 is used, then x_9 itself is NOT replaceable.  */
     156                 :             : 
     157                 :             : 
     158                 :             : /* Temporary Expression Replacement (TER) table information.  */
     159                 :             : 
     160                 :             : struct temp_expr_table
     161                 :             : {
     162                 :             :   var_map map;
     163                 :             :   bitmap *partition_dependencies;       /* Partitions expr is dependent on.  */
     164                 :             :   bitmap replaceable_expressions;       /* Replacement expression table.  */
     165                 :             :   bitmap *expr_decl_uids;               /* Base uids of exprs.  */
     166                 :             :   bitmap *kill_list;                    /* Expr's killed by a partition.  */
     167                 :             :   int virtual_partition;                /* Pseudo partition for virtual ops.  */
     168                 :             :   bitmap partition_in_use;              /* Partitions with kill entries.  */
     169                 :             :   bitmap new_replaceable_dependencies;  /* Holding place for pending dep's.  */
     170                 :             :   int *num_in_part;                     /* # of ssa_names in a partition.  */
     171                 :             :   int *call_cnt;                        /* Call count at definition.  */
     172                 :             :   int *reg_vars_cnt;                    /* Number of register variable
     173                 :             :                                            definitions encountered.  */
     174                 :             : };
     175                 :             : 
     176                 :             : /* Used to indicate a dependency on VDEFs.  */
     177                 :             : #define VIRTUAL_PARTITION(table)        (table->virtual_partition)
     178                 :             : 
     179                 :             : /* A place for the many, many bitmaps we create.  */
     180                 :             : static bitmap_obstack ter_bitmap_obstack;
     181                 :             : 
     182                 :             : extern void debug_ter (FILE *, temp_expr_table *);
     183                 :             : 
     184                 :             : 
     185                 :             : /* Create a new TER table for MAP.  */
     186                 :             : 
     187                 :             : static temp_expr_table *
     188                 :     1051505 : new_temp_expr_table (var_map map)
     189                 :             : {
     190                 :     1051505 :   temp_expr_table *t = XNEW (struct temp_expr_table);
     191                 :     1051505 :   t->map = map;
     192                 :             : 
     193                 :     2103010 :   t->partition_dependencies = XCNEWVEC (bitmap, num_ssa_names + 1);
     194                 :     2103010 :   t->expr_decl_uids = XCNEWVEC (bitmap, num_ssa_names + 1);
     195                 :     1051505 :   t->kill_list = XCNEWVEC (bitmap, num_var_partitions (map) + 1);
     196                 :             : 
     197                 :     1051505 :   t->partition_in_use = BITMAP_ALLOC (&ter_bitmap_obstack);
     198                 :             : 
     199                 :     1051505 :   t->virtual_partition = num_var_partitions (map);
     200                 :     1051505 :   t->new_replaceable_dependencies = BITMAP_ALLOC (&ter_bitmap_obstack);
     201                 :             : 
     202                 :     1051505 :   t->replaceable_expressions = NULL;
     203                 :     1051505 :   t->num_in_part = XCNEWVEC (int, num_var_partitions (map));
     204                 :             : 
     205                 :     1051505 :   unsigned x;
     206                 :     1051505 :   tree name;
     207                 :             : 
     208                 :    56158360 :   FOR_EACH_SSA_NAME (x, name, cfun)
     209                 :             :     {
     210                 :    34903540 :       int p;
     211                 :    34903540 :       p = var_to_partition (map, name);
     212                 :    34903540 :       if (p != NO_PARTITION)
     213                 :    22315780 :         t->num_in_part[p]++;
     214                 :             :     }
     215                 :     1051505 :   t->call_cnt = XCNEWVEC (int, num_ssa_names + 1);
     216                 :     2103010 :   t->reg_vars_cnt = XCNEWVEC (int, num_ssa_names + 1);
     217                 :             : 
     218                 :     1051505 :   return t;
     219                 :             : }
     220                 :             : 
     221                 :             : 
     222                 :             : /* Free TER table T.  If there are valid replacements, return the expression
     223                 :             :    vector.  */
     224                 :             : 
     225                 :             : static bitmap
     226                 :     1051505 : free_temp_expr_table (temp_expr_table *t)
     227                 :             : {
     228                 :     1051505 :   bitmap ret = NULL;
     229                 :             : 
     230                 :     1051505 :   if (flag_checking)
     231                 :             :     {
     232                 :    20340883 :       for (unsigned x = 0; x <= num_var_partitions (t->map); x++)
     233                 :    19289396 :         gcc_assert (!t->kill_list[x]);
     234                 :    57209515 :       for (unsigned x = 0; x < num_ssa_names; x++)
     235                 :             :         {
     236                 :    56158028 :           gcc_assert (t->expr_decl_uids[x] == NULL);
     237                 :    56158028 :           gcc_assert (t->partition_dependencies[x] == NULL);
     238                 :             :         }
     239                 :             :     }
     240                 :             : 
     241                 :     1051505 :   BITMAP_FREE (t->partition_in_use);
     242                 :     1051505 :   BITMAP_FREE (t->new_replaceable_dependencies);
     243                 :             : 
     244                 :     1051505 :   free (t->expr_decl_uids);
     245                 :     1051505 :   free (t->kill_list);
     246                 :     1051505 :   free (t->partition_dependencies);
     247                 :     1051505 :   free (t->num_in_part);
     248                 :     1051505 :   free (t->call_cnt);
     249                 :     1051505 :   free (t->reg_vars_cnt);
     250                 :             : 
     251                 :     1051505 :   if (t->replaceable_expressions)
     252                 :             :     ret = t->replaceable_expressions;
     253                 :             : 
     254                 :     1051505 :   free (t);
     255                 :     1051505 :   return ret;
     256                 :             : }
     257                 :             : 
     258                 :             : 
     259                 :             : /* Return TRUE if VERSION is to be replaced by an expression in TAB.  */
     260                 :             : 
     261                 :             : static inline bool
     262                 :     9352104 : version_to_be_replaced_p (temp_expr_table *tab, int version)
     263                 :             : {
     264                 :     9352104 :   if (!tab->replaceable_expressions)
     265                 :             :     return false;
     266                 :     8555743 :   return bitmap_bit_p (tab->replaceable_expressions, version);
     267                 :             : }
     268                 :             : 
     269                 :             : 
     270                 :             : /* Add partition P to the list if partitions VERSION is dependent on.  TAB is
     271                 :             :    the expression table */
     272                 :             : 
     273                 :             : static inline void
     274                 :     4659728 : make_dependent_on_partition (temp_expr_table *tab, int version, int p)
     275                 :             : {
     276                 :     4659728 :   if (!tab->partition_dependencies[version])
     277                 :     3867598 :     tab->partition_dependencies[version] = BITMAP_ALLOC (&ter_bitmap_obstack);
     278                 :             : 
     279                 :     4659728 :   bitmap_set_bit (tab->partition_dependencies[version], p);
     280                 :     4659728 : }
     281                 :             : 
     282                 :             : 
     283                 :             : /* Add VER to the kill list for P.  TAB is the expression table */
     284                 :             : 
     285                 :             : static inline void
     286                 :     6723701 : add_to_partition_kill_list (temp_expr_table *tab, int p, int ver)
     287                 :             : {
     288                 :     6723701 :   if (!tab->kill_list[p])
     289                 :             :     {
     290                 :     5663094 :       tab->kill_list[p] = BITMAP_ALLOC (&ter_bitmap_obstack);
     291                 :     5663094 :       bitmap_set_bit (tab->partition_in_use, p);
     292                 :             :     }
     293                 :     6723701 :   bitmap_set_bit (tab->kill_list[p], ver);
     294                 :     6723701 : }
     295                 :             : 
     296                 :             : 
     297                 :             : /* Remove VER from the partition kill list for P.  TAB is the expression
     298                 :             :    table.  */
     299                 :             : 
     300                 :             : static inline void
     301                 :     6604512 : remove_from_partition_kill_list (temp_expr_table *tab, int p, int version)
     302                 :             : {
     303                 :     6604512 :   gcc_checking_assert (tab->kill_list[p]);
     304                 :     6604512 :   bitmap_clear_bit (tab->kill_list[p], version);
     305                 :     6604512 :   if (bitmap_empty_p (tab->kill_list[p]))
     306                 :             :     {
     307                 :     5663094 :       bitmap_clear_bit (tab->partition_in_use, p);
     308                 :     5663094 :       BITMAP_FREE (tab->kill_list[p]);
     309                 :             :     }
     310                 :     6604512 : }
     311                 :             : 
     312                 :             : 
     313                 :             : /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is
     314                 :             :    replaceable by an expression, add a dependence each of the elements of the
     315                 :             :    expression.  These are contained in the new_replaceable list.  TAB is the
     316                 :             :    expression table.  */
     317                 :             : 
     318                 :             : static void
     319                 :     9352104 : add_dependence (temp_expr_table *tab, int version, tree var)
     320                 :             : {
     321                 :     9352104 :   int i;
     322                 :     9352104 :   bitmap_iterator bi;
     323                 :     9352104 :   unsigned x;
     324                 :             : 
     325                 :     9352104 :   i = SSA_NAME_VERSION (var);
     326                 :    17907847 :   if (version_to_be_replaced_p (tab, i))
     327                 :             :     {
     328                 :     3582827 :       if (!bitmap_empty_p (tab->new_replaceable_dependencies))
     329                 :             :         {
     330                 :             :           /* Version will now be killed by a write to any partition the
     331                 :             :              substituted expression would have been killed by.  */
     332                 :     3794624 :           EXECUTE_IF_SET_IN_BITMAP (tab->new_replaceable_dependencies, 0, x, bi)
     333                 :     2063973 :             add_to_partition_kill_list (tab, x, version);
     334                 :             : 
     335                 :             :           /* Rather than set partition_dependencies and in_use lists bit by
     336                 :             :              bit, simply OR in the new_replaceable_dependencies bits.  */
     337                 :     1730651 :           if (!tab->partition_dependencies[version])
     338                 :     1696525 :             tab->partition_dependencies[version] =
     339                 :     1696525 :               BITMAP_ALLOC (&ter_bitmap_obstack);
     340                 :     1730651 :           bitmap_ior_into (tab->partition_dependencies[version],
     341                 :     1730651 :                            tab->new_replaceable_dependencies);
     342                 :     1730651 :           bitmap_ior_into (tab->partition_in_use,
     343                 :     1730651 :                            tab->new_replaceable_dependencies);
     344                 :             :           /* It is only necessary to add these once.  */
     345                 :     1730651 :           bitmap_clear (tab->new_replaceable_dependencies);
     346                 :             :         }
     347                 :             :     }
     348                 :             :   else
     349                 :             :     {
     350                 :     5769277 :       i = var_to_partition (tab->map, var);
     351                 :     5769277 :       gcc_checking_assert (i != NO_PARTITION);
     352                 :     5769277 :       gcc_checking_assert (tab->num_in_part[i] != 0);
     353                 :             :       /* Only dependencies on ssa_names which are coalesced with something need
     354                 :             :          to be tracked.  Partitions with containing only a single SSA_NAME
     355                 :             :          *cannot* have their value changed.  */
     356                 :     5769277 :       if (tab->num_in_part[i] > 1)
     357                 :             :         {
     358                 :     1521338 :           add_to_partition_kill_list (tab, i, version);
     359                 :     1521338 :           make_dependent_on_partition (tab, version, i);
     360                 :             :         }
     361                 :             :     }
     362                 :     9352104 : }
     363                 :             : 
     364                 :             : 
     365                 :             : /* This function will remove the expression for VERSION from replacement
     366                 :             :    consideration in table TAB.  If FREE_EXPR is true, then remove the
     367                 :             :    expression from consideration as well by freeing the decl uid bitmap.  */
     368                 :             : 
     369                 :             : static void
     370                 :     9140812 : finished_with_expr (temp_expr_table *tab, int version, bool free_expr)
     371                 :             : {
     372                 :     9140812 :   unsigned i;
     373                 :     9140812 :   bitmap_iterator bi;
     374                 :             : 
     375                 :             :   /* Remove this expression from its dependent lists.  The partition dependence
     376                 :             :      list is retained and transferred later to whomever uses this version.  */
     377                 :     9140812 :   if (tab->partition_dependencies[version])
     378                 :             :     {
     379                 :    12168635 :       EXECUTE_IF_SET_IN_BITMAP (tab->partition_dependencies[version], 0, i, bi)
     380                 :     6604512 :         remove_from_partition_kill_list (tab, i, version);
     381                 :     5564123 :       BITMAP_FREE (tab->partition_dependencies[version]);
     382                 :             :     }
     383                 :     9140812 :   if (free_expr)
     384                 :     5557985 :     BITMAP_FREE (tab->expr_decl_uids[version]);
     385                 :     9140812 : }
     386                 :             : 
     387                 :             : 
     388                 :             : /* Return TRUE if expression STMT is suitable for replacement.
     389                 :             :    In addition to ssa_is_replaceable_p, require the same bb, and for -O0
     390                 :             :    same locus and same BLOCK), Considers memory loads as replaceable if aliasing
     391                 :             :    is available.  */
     392                 :             : 
     393                 :             : static inline bool
     394                 :    42193288 : ter_is_replaceable_p (gimple *stmt)
     395                 :             : {
     396                 :             : 
     397                 :    42193288 :   if (ssa_is_replaceable_p (stmt))
     398                 :             :     {
     399                 :    18757871 :       use_operand_p use_p;
     400                 :    18757871 :       tree def;
     401                 :    18757871 :       gimple *use_stmt;
     402                 :    18757871 :       location_t locus1, locus2;
     403                 :    18757871 :       tree block1, block2;
     404                 :             : 
     405                 :             :       /* Only consider definitions which have a single use.  ssa_is_replaceable_p
     406                 :             :          already performed this check, but the use stmt pointer is required for
     407                 :             :          further checks.  */
     408                 :    18757871 :       def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
     409                 :    18757871 :       if (!single_imm_use (def, &use_p, &use_stmt))
     410                 :             :           return false;
     411                 :             : 
     412                 :             :       /* If the use isn't in this block, it wont be replaced either.  */
     413                 :    18757871 :       if (gimple_bb (use_stmt) != gimple_bb (stmt))
     414                 :             :         return false;
     415                 :             : 
     416                 :    18286661 :       locus1 = gimple_location (stmt);
     417                 :    18286661 :       block1 = LOCATION_BLOCK (locus1);
     418                 :    14460793 :       locus1 = LOCATION_LOCUS (locus1);
     419                 :             : 
     420                 :    18286661 :       if (gphi *phi = dyn_cast <gphi *> (use_stmt))
     421                 :           0 :         locus2 = gimple_phi_arg_location (phi,
     422                 :           0 :                                           PHI_ARG_INDEX_FROM_USE (use_p));
     423                 :             :       else
     424                 :    18286661 :         locus2 = gimple_location (use_stmt);
     425                 :    18286661 :       block2 = LOCATION_BLOCK (locus2);
     426                 :    15565551 :       locus2 = LOCATION_LOCUS (locus2);
     427                 :             : 
     428                 :    18286661 :       if ((!optimize || optimize_debug)
     429                 :       18159 :           && ((locus1 != UNKNOWN_LOCATION && locus1 != locus2)
     430                 :       13122 :               || (block1 != NULL_TREE && block1 != block2)))
     431                 :             :         return false;
     432                 :             : 
     433                 :             :       return true;
     434                 :             :     }
     435                 :             :   return false;
     436                 :             : }
     437                 :             : 
     438                 :             : 
     439                 :             : /* Create an expression entry for a replaceable expression.  */
     440                 :             : 
     441                 :             : static void
     442                 :     9140812 : process_replaceable (temp_expr_table *tab, gimple *stmt, int call_cnt,
     443                 :             :                      int reg_vars_cnt)
     444                 :             : {
     445                 :     9140812 :   tree var, def, basevar;
     446                 :     9140812 :   int version;
     447                 :     9140812 :   ssa_op_iter iter;
     448                 :     9140812 :   bitmap def_vars, use_vars;
     449                 :             : 
     450                 :     9140812 :   gcc_checking_assert (ter_is_replaceable_p (stmt));
     451                 :             : 
     452                 :     9140812 :   def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
     453                 :     9140812 :   version = SSA_NAME_VERSION (def);
     454                 :     9140812 :   def_vars = BITMAP_ALLOC (&ter_bitmap_obstack);
     455                 :             : 
     456                 :     9140812 :   basevar = SSA_NAME_VAR (def);
     457                 :      775260 :   if (basevar)
     458                 :      775260 :     bitmap_set_bit (def_vars, DECL_UID (basevar));
     459                 :             : 
     460                 :             :   /* Add this expression to the dependency list for each use partition.  */
     461                 :    18492916 :   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
     462                 :             :     {
     463                 :     9352104 :       int var_version = SSA_NAME_VERSION (var);
     464                 :             : 
     465                 :     9352104 :       use_vars = tab->expr_decl_uids[var_version];
     466                 :     9352104 :       add_dependence (tab, version, var);
     467                 :     9352104 :       if (use_vars)
     468                 :             :         {
     469                 :     3582827 :           bitmap_ior_into (def_vars, use_vars);
     470                 :     3582827 :           BITMAP_FREE (tab->expr_decl_uids[var_version]);
     471                 :             :         }
     472                 :     5769277 :       else if (SSA_NAME_VAR (var))
     473                 :     3238961 :         bitmap_set_bit (def_vars, DECL_UID (SSA_NAME_VAR (var)));
     474                 :             :     }
     475                 :     9140812 :   tab->expr_decl_uids[version] = def_vars;
     476                 :             : 
     477                 :             :   /* If there are VUSES, add a dependence on virtual defs.  */
     478                 :    18281624 :   if (gimple_vuse (stmt))
     479                 :             :     {
     480                 :     3138390 :       make_dependent_on_partition (tab, version, VIRTUAL_PARTITION (tab));
     481                 :     3138390 :       add_to_partition_kill_list (tab, VIRTUAL_PARTITION (tab), version);
     482                 :             :     }
     483                 :             : 
     484                 :     9140812 :   tab->call_cnt[version] = call_cnt;
     485                 :     9140812 :   tab->reg_vars_cnt[version] = reg_vars_cnt;
     486                 :     9140812 : }
     487                 :             : 
     488                 :             : 
     489                 :             : /* This function removes any expression in TAB which is dependent on PARTITION
     490                 :             :    from consideration, making it not replaceable.  */
     491                 :             : 
     492                 :             : static inline void
     493                 :    11247579 : kill_expr (temp_expr_table *tab, int partition)
     494                 :             : {
     495                 :    11247579 :   unsigned version;
     496                 :             : 
     497                 :             :   /* Mark every active expr dependent on this var as not replaceable.
     498                 :             :      finished_with_expr can modify the bitmap, so we can't execute over it.  */
     499                 :    11478546 :   while (tab->kill_list[partition])
     500                 :             :     {
     501                 :      230967 :       version = bitmap_first_set_bit (tab->kill_list[partition]);
     502                 :      230967 :       finished_with_expr (tab, version, true);
     503                 :             :     }
     504                 :             : 
     505                 :    11247579 :   gcc_checking_assert (!tab->kill_list[partition]);
     506                 :    11247579 : }
     507                 :             : 
     508                 :             : 
     509                 :             : /* This function kills all expressions in TAB which are dependent on virtual
     510                 :             :    partitions.  */
     511                 :             : 
     512                 :             : static inline void
     513                 :    11220302 : kill_virtual_exprs (temp_expr_table *tab)
     514                 :             : {
     515                 :    11220302 :   kill_expr (tab, VIRTUAL_PARTITION (tab));
     516                 :    11220302 : }
     517                 :             : 
     518                 :             : 
     519                 :             : /* Mark the expression associated with VAR as replaceable, and enter
     520                 :             :    the defining stmt into the partition_dependencies table TAB.  If
     521                 :             :    MORE_REPLACING is true, accumulate the pending partition dependencies.  */
     522                 :             : 
     523                 :             : static void
     524                 :     8691415 : mark_replaceable (temp_expr_table *tab, tree var, bool more_replacing)
     525                 :             : {
     526                 :     8691415 :   int version = SSA_NAME_VERSION (var);
     527                 :             : 
     528                 :             :   /* Move the dependence list to the pending listpending.  */
     529                 :     8691415 :   if (more_replacing && tab->partition_dependencies[version])
     530                 :     1941850 :     bitmap_ior_into (tab->new_replaceable_dependencies,
     531                 :             :                      tab->partition_dependencies[version]);
     532                 :             : 
     533                 :     8691415 :   finished_with_expr (tab, version, !more_replacing);
     534                 :             : 
     535                 :             :   /* Set the replaceable expression.
     536                 :             :      The bitmap for this "escapes" from this file so it's allocated
     537                 :             :      on the default obstack.  */
     538                 :     8691415 :   if (!tab->replaceable_expressions)
     539                 :      703323 :     tab->replaceable_expressions = BITMAP_ALLOC (NULL);
     540                 :     8691415 :   bitmap_set_bit (tab->replaceable_expressions, version);
     541                 :     8691415 : }
     542                 :             : 
     543                 :             : 
     544                 :             : /* Helper function for find_ssaname_in_stores.  Called via walk_tree to
     545                 :             :    find a SSA_NAME DATA somewhere in *TP.  */
     546                 :             : 
     547                 :             : static tree
     548                 :       26088 : find_ssaname (tree *tp, int *walk_subtrees, void *data)
     549                 :             : {
     550                 :       26088 :   tree var = (tree) data;
     551                 :       26088 :   if (*tp == var)
     552                 :             :     return var;
     553                 :       26047 :   else if (IS_TYPE_OR_DECL_P (*tp))
     554                 :       20347 :     *walk_subtrees = 0;
     555                 :             :   return NULL_TREE;
     556                 :             : }
     557                 :             : 
     558                 :             : /* Helper function for find_replaceable_in_bb.  Return true if SSA_NAME DATA
     559                 :             :    is used somewhere in T, which is a store in the statement.  Called via
     560                 :             :    walk_stmt_load_store_addr_ops.  */
     561                 :             : 
     562                 :             : static bool
     563                 :       21283 : find_ssaname_in_store (gimple *, tree, tree t, void *data)
     564                 :             : {
     565                 :       21283 :   return walk_tree (&t, find_ssaname, data, NULL) != NULL_TREE;
     566                 :             : }
     567                 :             : 
     568                 :             : /* This function processes basic block BB, and looks for variables which can
     569                 :             :    be replaced by their expressions.  Results are stored in the table TAB.  */
     570                 :             : 
     571                 :             : static void
     572                 :     9224345 : find_replaceable_in_bb (temp_expr_table *tab, basic_block bb)
     573                 :             : {
     574                 :     9224345 :   gimple_stmt_iterator bsi;
     575                 :     9224345 :   gimple *stmt;
     576                 :     9224345 :   tree def, use, fndecl;
     577                 :     9224345 :   int partition;
     578                 :     9224345 :   var_map map = tab->map;
     579                 :     9224345 :   ssa_op_iter iter;
     580                 :     9224345 :   bool stmt_replaceable;
     581                 :     9224345 :   int cur_call_cnt = 0;
     582                 :     9224345 :   int cur_reg_vars_cnt = 0;
     583                 :             : 
     584                 :    91293572 :   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
     585                 :             :     {
     586                 :    72844882 :       stmt = gsi_stmt (bsi);
     587                 :             : 
     588                 :    72844882 :       if (is_gimple_debug (stmt))
     589                 :    39792406 :         continue;
     590                 :             : 
     591                 :    33052476 :       stmt_replaceable = ter_is_replaceable_p (stmt);
     592                 :             : 
     593                 :             :       /* Determine if this stmt finishes an existing expression.  */
     594                 :    62267702 :       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
     595                 :             :         {
     596                 :    29215226 :           unsigned ver = SSA_NAME_VERSION (use);
     597                 :             : 
     598                 :             :           /* If this use is a potential replacement variable, process it.  */
     599                 :    29215226 :           if (tab->expr_decl_uids[ver])
     600                 :             :             {
     601                 :     8909845 :               bool same_root_var = false;
     602                 :     8909845 :               ssa_op_iter iter2;
     603                 :     8909845 :               bitmap vars = tab->expr_decl_uids[ver];
     604                 :             : 
     605                 :             :               /* See if the root variables are the same.  If they are, we
     606                 :             :                  do not want to do the replacement to avoid problems with
     607                 :             :                  code size, see PR tree-optimization/17549.  */
     608                 :     8909845 :               if (!bitmap_empty_p (vars))
     609                 :     7633153 :                 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF)
     610                 :             :                   {
     611                 :     3012214 :                     if (SSA_NAME_VAR (def)
     612                 :      663930 :                         && bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def))))
     613                 :             :                       {
     614                 :             :                         same_root_var = true;
     615                 :             :                         break;
     616                 :             :                       }
     617                 :             :                   }
     618                 :             : 
     619                 :             :               /* If the stmt does a memory store and the replacement
     620                 :             :                  is a load aliasing it avoid creating overlapping
     621                 :             :                  assignments which we cannot expand correctly.  */
     622                 :    16178462 :               if (gimple_vdef (stmt))
     623                 :             :                 {
     624                 :     2043169 :                   gimple *def_stmt = SSA_NAME_DEF_STMT (use);
     625                 :     2043386 :                   while (is_gimple_assign (def_stmt)
     626                 :     2043386 :                          && gimple_assign_rhs_code (def_stmt) == SSA_NAME)
     627                 :         217 :                     def_stmt
     628                 :         217 :                       = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (def_stmt));
     629                 :    10953014 :                   if (gimple_vuse (def_stmt)
     630                 :      670359 :                       && gimple_assign_single_p (def_stmt)
     631                 :     2713352 :                       && stmt_may_clobber_ref_p (stmt,
     632                 :             :                                                  gimple_assign_rhs1 (def_stmt)))
     633                 :             :                     {
     634                 :             :                       /* For calls, it is not a problem if USE is among
     635                 :             :                          call's arguments or say OBJ_TYPE_REF argument,
     636                 :             :                          all those necessarily need to be evaluated before
     637                 :             :                          the call that may clobber the memory.  But if
     638                 :             :                          LHS of the call refers to USE, expansion might
     639                 :             :                          evaluate it after the call, prevent TER in that
     640                 :             :                          case.
     641                 :             :                          For inline asm, allow TER of loads into input
     642                 :             :                          arguments, but disallow TER for USEs that occur
     643                 :             :                          somewhere in outputs.  */
     644                 :      386154 :                       if (is_gimple_call (stmt)
     645                 :      386154 :                           || gimple_code (stmt) == GIMPLE_ASM)
     646                 :             :                         {
     647                 :      320795 :                           if (walk_stmt_load_store_ops (stmt, use, NULL,
     648                 :             :                                                         find_ssaname_in_store))
     649                 :       65400 :                             same_root_var = true;
     650                 :             :                         }
     651                 :             :                       else
     652                 :             :                         same_root_var = true;
     653                 :             :                     }
     654                 :             :                 }
     655                 :             : 
     656                 :             :               /* Mark expression as replaceable unless stmt is volatile, or the
     657                 :             :                  def variable has the same root variable as something in the
     658                 :             :                  substitution list, or the def and use span a call such that
     659                 :             :                  we'll expand lifetimes across a call.  We also don't want to
     660                 :             :                  replace across these expressions that may call libcalls that
     661                 :             :                  clobber the register involved.  See PR 70184.  Neither
     662                 :             :                  do we want to move possibly trapping expressions across
     663                 :             :                  a call.  See PRs 102129 and 33593.  */
     664                 :    16126165 :               if (gimple_has_volatile_ops (stmt) || same_root_var
     665                 :     8740520 :                   || (tab->call_cnt[ver] != cur_call_cnt
     666                 :       80781 :                       && (SINGLE_SSA_USE_OPERAND (SSA_NAME_DEF_STMT (use),
     667                 :             :                                                   SSA_OP_USE)
     668                 :             :                             == NULL_USE_OPERAND_P
     669                 :       34168 :                           || gimple_could_trap_p (SSA_NAME_DEF_STMT (use))))
     670                 :    15960045 :                   || tab->reg_vars_cnt[ver] != cur_reg_vars_cnt)
     671                 :      218430 :                 finished_with_expr (tab, ver, true);
     672                 :             :               else
     673                 :     8691415 :                 mark_replaceable (tab, use, stmt_replaceable);
     674                 :             :             }
     675                 :             :         }
     676                 :             : 
     677                 :             :       /* Next, see if this stmt kills off an active expression.  */
     678                 :    50142280 :       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
     679                 :             :         {
     680                 :    17089804 :           partition = var_to_partition (map, def);
     681                 :    17089804 :           if (partition != NO_PARTITION && tab->kill_list[partition])
     682                 :       27277 :             kill_expr (tab, partition);
     683                 :             :         }
     684                 :             : 
     685                 :             :       /* Increment counter if this is a non BUILT_IN call. We allow
     686                 :             :          replacement over BUILT_IN calls since many will expand to inline
     687                 :             :          insns instead of a true call.  */
     688                 :    33052476 :       if (is_gimple_call (stmt)
     689                 :    37985678 :           && !((fndecl = gimple_call_fndecl (stmt))
     690                 :     4933202 :                && fndecl_built_in_p (fndecl)))
     691                 :     3672869 :         cur_call_cnt++;
     692                 :             : 
     693                 :             :       /* Increment counter if this statement sets a local
     694                 :             :          register variable.  */
     695                 :    33052476 :       if (gimple_assign_single_p (stmt)
     696                 :    33052476 :           && (VAR_P (gimple_assign_lhs (stmt))
     697                 :     1602410 :           && DECL_HARD_REGISTER (gimple_assign_lhs (stmt))))
     698                 :        1004 :         cur_reg_vars_cnt++;
     699                 :             : 
     700                 :             :       /* Now see if we are creating a new expression or not.  */
     701                 :    33052476 :       if (stmt_replaceable)
     702                 :     9140812 :         process_replaceable (tab, stmt, cur_call_cnt, cur_reg_vars_cnt);
     703                 :             : 
     704                 :             :       /* Free any unused dependency lists.  */
     705                 :    33052476 :       bitmap_clear (tab->new_replaceable_dependencies);
     706                 :             : 
     707                 :             :       /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand,
     708                 :             :          including the current stmt.  */
     709                 :   134223629 :       if (gimple_vdef (stmt))
     710                 :    11220302 :         kill_virtual_exprs (tab);
     711                 :             :     }
     712                 :     9224345 : }
     713                 :             : 
     714                 :             : 
     715                 :             : /* This function is the driver routine for replacement of temporary expressions
     716                 :             :    in the SSA->normal phase, operating on MAP.  If there are replaceable
     717                 :             :    expressions, a table is returned which maps SSA versions to the
     718                 :             :    expressions they should be replaced with.  A NULL_TREE indicates no
     719                 :             :    replacement should take place.  If there are no replacements at all,
     720                 :             :    NULL is returned by the function, otherwise an expression vector indexed
     721                 :             :    by SSA_NAME version numbers.  */
     722                 :             : 
     723                 :             : bitmap
     724                 :     1051505 : find_replaceable_exprs (var_map map)
     725                 :             : {
     726                 :     1051505 :   basic_block bb;
     727                 :     1051505 :   temp_expr_table *table;
     728                 :     1051505 :   bitmap ret;
     729                 :             : 
     730                 :     1051505 :   bitmap_obstack_initialize (&ter_bitmap_obstack);
     731                 :     1051505 :   table = new_temp_expr_table (map);
     732                 :    10275850 :   FOR_EACH_BB_FN (bb, cfun)
     733                 :             :     {
     734                 :     9224345 :       find_replaceable_in_bb (table, bb);
     735                 :     9224345 :       gcc_checking_assert (bitmap_empty_p (table->partition_in_use));
     736                 :             :     }
     737                 :     1051505 :   ret = free_temp_expr_table (table);
     738                 :     1051505 :   bitmap_obstack_release (&ter_bitmap_obstack);
     739                 :     1051505 :   return ret;
     740                 :             : }
     741                 :             : 
     742                 :             : /* Dump TER expression table EXPR to file F.  */
     743                 :             : 
     744                 :             : void
     745                 :          12 : dump_replaceable_exprs (FILE *f, bitmap expr)
     746                 :             : {
     747                 :          12 :   tree var;
     748                 :          12 :   unsigned x;
     749                 :             : 
     750                 :          12 :   fprintf (f, "\nReplacing Expressions\n");
     751                 :         218 :   for (x = 0; x < num_ssa_names; x++)
     752                 :         194 :     if (bitmap_bit_p (expr, x))
     753                 :             :       {
     754                 :          39 :         var = ssa_name (x);
     755                 :          39 :         print_generic_expr (f, var, TDF_SLIM);
     756                 :          39 :         fprintf (f, " replace with --> ");
     757                 :          39 :         print_gimple_stmt (f, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM);
     758                 :          39 :         fprintf (f, "\n");
     759                 :             :       }
     760                 :          12 :   fprintf (f, "\n");
     761                 :          12 : }
     762                 :             : 
     763                 :             : 
     764                 :             : /* Dump the status of the various tables in the expression table.  This is used
     765                 :             :    exclusively to debug TER.  F is the place to send debug info and T is the
     766                 :             :    table being debugged.  */
     767                 :             : 
     768                 :             : DEBUG_FUNCTION void
     769                 :           0 : debug_ter (FILE *f, temp_expr_table *t)
     770                 :             : {
     771                 :           0 :   unsigned x, y;
     772                 :           0 :   bitmap_iterator bi;
     773                 :             : 
     774                 :           0 :   fprintf (f, "\nDumping current state of TER\n virtual partition = %d\n",
     775                 :             :            VIRTUAL_PARTITION (t));
     776                 :           0 :   if (t->replaceable_expressions)
     777                 :           0 :     dump_replaceable_exprs (f, t->replaceable_expressions);
     778                 :           0 :   fprintf (f, "Currently tracking the following expressions:\n");
     779                 :             : 
     780                 :           0 :   for (x = 1; x < num_ssa_names; x++)
     781                 :           0 :     if (t->expr_decl_uids[x])
     782                 :             :       {
     783                 :           0 :         print_generic_expr (f, ssa_name (x), TDF_SLIM);
     784                 :           0 :         fprintf (f, " dep-parts : ");
     785                 :           0 :         if (t->partition_dependencies[x]
     786                 :           0 :             && !bitmap_empty_p (t->partition_dependencies[x]))
     787                 :             :           {
     788                 :           0 :             EXECUTE_IF_SET_IN_BITMAP (t->partition_dependencies[x], 0, y, bi)
     789                 :           0 :               fprintf (f, "P%d ",y);
     790                 :             :           }
     791                 :           0 :         fprintf (f, "   basedecls: ");
     792                 :           0 :         EXECUTE_IF_SET_IN_BITMAP (t->expr_decl_uids[x], 0, y, bi)
     793                 :           0 :           fprintf (f, "%d ",y);
     794                 :           0 :         fprintf (f, "   call_cnt : %d",t->call_cnt[x]);
     795                 :           0 :         fprintf (f, "\n");
     796                 :             :       }
     797                 :             : 
     798                 :           0 :   bitmap_print (f, t->partition_in_use, "Partitions in use ",
     799                 :             :                 "\npartition KILL lists:\n");
     800                 :             : 
     801                 :           0 :   for (x = 0; x <= num_var_partitions (t->map); x++)
     802                 :           0 :     if (t->kill_list[x])
     803                 :             :       {
     804                 :           0 :         fprintf (f, "Partition %d : ", x);
     805                 :           0 :         EXECUTE_IF_SET_IN_BITMAP (t->kill_list[x], 0, y, bi)
     806                 :           0 :           fprintf (f, "_%d ",y);
     807                 :             :       }
     808                 :             : 
     809                 :           0 :   fprintf (f, "\n----------\n");
     810                 :           0 : }
        

Generated by: LCOV version 2.1-beta

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