LCOV - code coverage report
Current view: top level - gcc - tree-ssa-live.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 98.0 % 49 48
Test Date: 2024-09-28 13:20:55 Functions: 100.0 % 8 8
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Routines for liveness 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                 :             : #ifndef _TREE_SSA_LIVE_H
      23                 :             : #define _TREE_SSA_LIVE_H 1
      24                 :             : 
      25                 :             : #include "partition.h"
      26                 :             : 
      27                 :             : /* Used to create the variable mapping when we go out of SSA form.
      28                 :             : 
      29                 :             :    Mapping from an ssa_name to a partition number is maintained, as well as
      30                 :             :    partition number back to ssa_name.
      31                 :             : 
      32                 :             :    This data structure also supports "views", which work on a subset of all
      33                 :             :    partitions.  This allows the coalescer to decide what partitions are
      34                 :             :    interesting to it, and only work with those partitions.  Whenever the view
      35                 :             :    is changed, the partition numbers change, but none of the partition groupings
      36                 :             :    change. (ie, it is truly a view since it doesn't change anything)
      37                 :             : 
      38                 :             :    The final component of the data structure is the basevar map.  This provides
      39                 :             :    a list of all the different base variables which occur in a partition view,
      40                 :             :    and a unique index for each one. Routines are provided to quickly produce
      41                 :             :    the base variable of a partition.
      42                 :             : 
      43                 :             :    Note that members of a partition MUST all have the same base variable.  */
      44                 :             : 
      45                 :             : typedef struct _var_map
      46                 :             : {
      47                 :             :   /* The partition manager of all variables.  */
      48                 :             :   partition var_partition;
      49                 :             : 
      50                 :             :   /* Vector for managing partitions views.  */
      51                 :             :   int *partition_to_view;
      52                 :             :   int *view_to_partition;
      53                 :             : 
      54                 :             :   /* Current number of partitions in var_map based on the current view.  */
      55                 :             :   unsigned int num_partitions;
      56                 :             : 
      57                 :             :   /* Original full partition size.  */
      58                 :             :   unsigned int partition_size;
      59                 :             : 
      60                 :             :   /* Number of base variables in the base var list.  */
      61                 :             :   int num_basevars;
      62                 :             : 
      63                 :             :   /* Map of partitions numbers to base variable table indexes.  */
      64                 :             :   int *partition_to_base_index;
      65                 :             : 
      66                 :             :   /* Bitmap of basic block.  It describes the region within which the analysis
      67                 :             :      is done.  Using pointer avoids allocating memory in out-of-ssa case.  */
      68                 :             :   bitmap bmp_bbs;
      69                 :             : 
      70                 :             :   /* Vector of basic block in the region.  */
      71                 :             :   vec<basic_block> vec_bbs;
      72                 :             : 
      73                 :             :   /* If non-NULL, only coalesce SSA_NAMEs from this bitmap, and try harder
      74                 :             :      for those (for bitint lowering pass).  */
      75                 :             :   bitmap bitint;
      76                 :             : 
      77                 :             :   /* True if this map is for out-of-ssa, otherwise for live range
      78                 :             :      computation.  When for out-of-ssa, it also means the var map is computed
      79                 :             :      for whole current function.  */
      80                 :             :   bool outofssa_p;
      81                 :             : } *var_map;
      82                 :             : 
      83                 :             : 
      84                 :             : /* Value used to represent no partition number.  */
      85                 :             : #define NO_PARTITION            -1
      86                 :             : 
      87                 :             : extern var_map init_var_map (int, class loop * = NULL, bitmap = NULL);
      88                 :             : extern void delete_var_map (var_map);
      89                 :             : extern int var_union (var_map, tree, tree);
      90                 :             : extern void partition_view_normal (var_map);
      91                 :             : extern void partition_view_bitmap (var_map, bitmap);
      92                 :             : extern void dump_scope_blocks (FILE *, dump_flags_t);
      93                 :             : extern void debug_scope_block (tree, dump_flags_t);
      94                 :             : extern void debug_scope_blocks (dump_flags_t);
      95                 :             : extern void remove_unused_locals (void);
      96                 :             : extern void dump_var_map (FILE *, var_map);
      97                 :             : extern void debug (_var_map &ref);
      98                 :             : extern void debug (_var_map *ptr);
      99                 :             : 
     100                 :             : 
     101                 :             : /* Return TRUE if region of the MAP contains basic block BB.  */
     102                 :             : 
     103                 :             : inline bool
     104                 :    68014722 : region_contains_p (var_map map, basic_block bb)
     105                 :             : {
     106                 :             :   /* It's possible that the function is called with ENTRY_BLOCK/EXIT_BLOCK.  */
     107                 :    68014722 :   if (map->outofssa_p || map->bitint)
     108                 :    68014722 :     return (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK);
     109                 :             : 
     110                 :           0 :   return bitmap_bit_p (map->bmp_bbs, bb->index);
     111                 :             : }
     112                 :             : 
     113                 :             : 
     114                 :             : /* Return number of partitions in MAP.  */
     115                 :             : 
     116                 :             : inline unsigned
     117                 :   113337121 : num_var_partitions (var_map map)
     118                 :             : {
     119                 :    48698248 :   return map->num_partitions;
     120                 :             : }
     121                 :             : 
     122                 :             : 
     123                 :             : /* Given partition index I from MAP, return the variable which represents that
     124                 :             :    partition.  */
     125                 :             : 
     126                 :             : inline tree
     127                 :    55589553 : partition_to_var (var_map map, int i)
     128                 :             : {
     129                 :    55589553 :   tree name;
     130                 :    55589553 :   if (map->view_to_partition)
     131                 :    55589392 :     i = map->view_to_partition[i];
     132                 :    55589553 :   i = partition_find (map->var_partition, i);
     133                 :    55589553 :   name = ssa_name (i);
     134                 :    55589553 :   return name;
     135                 :             : }
     136                 :             : 
     137                 :             : 
     138                 :             : /* Given ssa_name VERSION, if it has a partition in MAP,  return the var it
     139                 :             :    is associated with.  Otherwise return NULL.  */
     140                 :             : 
     141                 :             : inline tree
     142                 :        1410 : version_to_var (var_map map, int version)
     143                 :             : {
     144                 :        1410 :   int part;
     145                 :        1410 :   part = partition_find (map->var_partition, version);
     146                 :        1410 :   if (map->partition_to_view)
     147                 :        1410 :     part = map->partition_to_view[part];
     148                 :        1410 :   if (part == NO_PARTITION)
     149                 :             :     return NULL_TREE;
     150                 :             : 
     151                 :         460 :   return partition_to_var (map, part);
     152                 :             : }
     153                 :             : 
     154                 :             : 
     155                 :             : /* Given VAR, return the partition number in MAP which contains it.
     156                 :             :    NO_PARTITION is returned if it's not in any partition.  */
     157                 :             : 
     158                 :             : inline int
     159                 :   496763895 : var_to_partition (var_map map, tree var)
     160                 :             : {
     161                 :   496763895 :   int part;
     162                 :             : 
     163                 :   496763895 :   part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
     164                 :   496763895 :   if (map->partition_to_view)
     165                 :   496763895 :     part = map->partition_to_view[part];
     166                 :   496763895 :   return part;
     167                 :             : }
     168                 :             : 
     169                 :             : 
     170                 :             : /* Given VAR, return the variable which represents the entire partition
     171                 :             :    it is a member of in MAP.  NULL is returned if it is not in a partition.  */
     172                 :             : 
     173                 :             : inline tree
     174                 :     2629005 : var_to_partition_to_var (var_map map, tree var)
     175                 :             : {
     176                 :     2629005 :   int part;
     177                 :             : 
     178                 :     2629005 :   part = var_to_partition (map, var);
     179                 :     2629005 :   if (part == NO_PARTITION)
     180                 :             :     return NULL_TREE;
     181                 :     2629005 :   return partition_to_var (map, part);
     182                 :             : }
     183                 :             : 
     184                 :             : 
     185                 :             : /* Return the index into the basevar table for PARTITION's base in MAP.  */
     186                 :             : 
     187                 :             : inline int
     188                 :    63642167 : basevar_index (var_map map, int partition)
     189                 :             : {
     190                 :    63642167 :   gcc_checking_assert (partition >= 0
     191                 :             :                        && partition <= (int) num_var_partitions (map));
     192                 :    63642167 :   return map->partition_to_base_index[partition];
     193                 :             : }
     194                 :             : 
     195                 :             : 
     196                 :             : /* Return the number of different base variables in MAP.  */
     197                 :             : 
     198                 :             : inline int
     199                 :     1247749 : num_basevars (var_map map)
     200                 :             : {
     201                 :     1247749 :   return map->num_basevars;
     202                 :             : }
     203                 :             : 
     204                 :             : 
     205                 :             : /*  ---------------- live on entry/exit info ------------------------------
     206                 :             : 
     207                 :             :     This structure is used to represent live range information on SSA based
     208                 :             :     trees. A partition map must be provided, and based on the active partitions,
     209                 :             :     live-on-entry information and live-on-exit information can be calculated.
     210                 :             :     As well, partitions are marked as to whether they are global (live
     211                 :             :     outside the basic block they are defined in).
     212                 :             : 
     213                 :             :     The live-on-entry information is per block.  It provide a bitmap for
     214                 :             :     each block which has a bit set for each partition that is live on entry to
     215                 :             :     that block.
     216                 :             : 
     217                 :             :     The live-on-exit information is per block.  It provides a bitmap for each
     218                 :             :     block indicating which partitions are live on exit from the block.
     219                 :             : 
     220                 :             :     For the purposes of this implementation, we treat the elements of a PHI
     221                 :             :     as follows:
     222                 :             : 
     223                 :             :        Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
     224                 :             :        originate. They are *NOT* considered live on entry to the block
     225                 :             :        containing the PHI node.
     226                 :             : 
     227                 :             :        The Def of a PHI node is *not* considered live on entry to the block.
     228                 :             :        It is considered to be "define early" in the block. Picture it as each
     229                 :             :        block having a stmt (or block-preheader) before the first real stmt in
     230                 :             :        the block which defines all the variables that are defined by PHIs.
     231                 :             : 
     232                 :             :     -----------------------------------------------------------------------  */
     233                 :             : 
     234                 :             : 
     235                 :             : typedef struct tree_live_info_d
     236                 :             : {
     237                 :             :   /* Var map this relates to.  */
     238                 :             :   var_map map;
     239                 :             : 
     240                 :             :   /* Bitmaps of live on entry blocks for partition elements.  */
     241                 :             :   bitmap_head *livein;
     242                 :             : 
     243                 :             :   /* Bitmaps of what variables are live on exit for a basic blocks.  */
     244                 :             :   bitmap_head *liveout;
     245                 :             : 
     246                 :             :   /* Number of basic blocks when live on exit calculated.  */
     247                 :             :   int num_blocks;
     248                 :             : 
     249                 :             :   /* Vector used when creating live ranges as a visited stack.  */
     250                 :             :   int *work_stack;
     251                 :             : 
     252                 :             :   /* Top of workstack.  */
     253                 :             :   int *stack_top;
     254                 :             : 
     255                 :             :   /* Obstacks to allocate the bitmaps on.  */
     256                 :             :   bitmap_obstack livein_obstack;
     257                 :             :   bitmap_obstack liveout_obstack;
     258                 :             : } *tree_live_info_p;
     259                 :             : 
     260                 :             : 
     261                 :             : #define LIVEDUMP_ENTRY  0x01
     262                 :             : #define LIVEDUMP_EXIT   0x02
     263                 :             : #define LIVEDUMP_ALL    (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
     264                 :             : extern void delete_tree_live_info (tree_live_info_p);
     265                 :             : extern tree_live_info_p calculate_live_ranges (var_map, bool);
     266                 :             : extern void debug (tree_live_info_d &ref);
     267                 :             : extern void debug (tree_live_info_d *ptr);
     268                 :             : extern void dump_live_info (FILE *, tree_live_info_p, int);
     269                 :             : 
     270                 :             : typedef hash_map<int_hash <unsigned int, -1U>, unsigned int> live_vars_map;
     271                 :             : extern vec<bitmap_head> compute_live_vars (struct function *, live_vars_map *);
     272                 :             : extern bitmap live_vars_at_stmt (vec<bitmap_head> &, live_vars_map *,
     273                 :             :                                  gimple *);
     274                 :             : extern void destroy_live_vars (vec<bitmap_head> &);
     275                 :             : 
     276                 :             : 
     277                 :             : /* Return the bitmap from LIVE representing the live on entry blocks for
     278                 :             :    partition P.  */
     279                 :             : 
     280                 :             : inline bitmap
     281                 :    53839570 : live_on_entry (tree_live_info_p live, basic_block bb)
     282                 :             : {
     283                 :    53839570 :   gcc_checking_assert (live->livein
     284                 :             :                        && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     285                 :             :                        && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
     286                 :             : 
     287                 :    53839570 :   return &live->livein[bb->index];
     288                 :             : }
     289                 :             : 
     290                 :             : 
     291                 :             : /* Return the bitmap from LIVE representing the live on exit partitions from
     292                 :             :    block BB.  */
     293                 :             : 
     294                 :             : inline bitmap
     295                 :    10839147 : live_on_exit (tree_live_info_p live, basic_block bb)
     296                 :             : {
     297                 :    10839147 :   gcc_checking_assert (live->liveout
     298                 :             :                        && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     299                 :             :                        && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
     300                 :             : 
     301                 :    10839147 :   return &live->liveout[bb->index];
     302                 :             : }
     303                 :             : 
     304                 :             : 
     305                 :             : /* Return the partition map which the information in LIVE utilizes.  */
     306                 :             : 
     307                 :             : inline var_map
     308                 :     1247749 : live_var_map (tree_live_info_p live)
     309                 :             : {
     310                 :     1247749 :   return live->map;
     311                 :             : }
     312                 :             : 
     313                 :             : 
     314                 :             : /* Mark partition P as live on entry to basic block BB in LIVE.  */
     315                 :             : 
     316                 :             : inline void
     317                 :             : make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
     318                 :             : {
     319                 :             :   bitmap_set_bit (&live->livein[bb->index], p);
     320                 :             : }
     321                 :             : 
     322                 :             : 
     323                 :             : /* On-demand virtual operand global live analysis.  There is at most
     324                 :             :    a single virtual operand live at a time, the following computes and
     325                 :             :    caches the virtual operand live at the exit of a basic block
     326                 :             :    supporting related live-in and live-on-edge queries.  It requires
     327                 :             :    up-to-date marked backedges.  */
     328                 :             : 
     329                 :             : class virtual_operand_live
     330                 :             : {
     331                 :             : public:
     332                 :     1988303 :   virtual_operand_live() : liveout (nullptr) {}
     333                 :     1988303 :   ~virtual_operand_live()
     334                 :             :   {
     335                 :     1988303 :     if (liveout)
     336                 :      183052 :       free (liveout);
     337                 :     1988303 :   }
     338                 :             : 
     339                 :             :   tree get_live_in (basic_block bb);
     340                 :             :   tree get_live_out (basic_block bb);
     341                 :             :   tree get_live_on_edge (edge e) { return get_live_out (e->src); }
     342                 :             : 
     343                 :             : private:
     344                 :             :   void init ();
     345                 :             : 
     346                 :             :   tree *liveout;
     347                 :             : };
     348                 :             : 
     349                 :             : 
     350                 :             : #endif /* _TREE_SSA_LIVE_H  */
        

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.