LCOV - code coverage report
Current view: top level - gcc - tree-ssa-live.h (source / functions) Hit Total Coverage
Test: gcc.info Lines: 24 25 96.0 %
Date: 2020-03-28 11:57:23 Functions: 3 3 100.0 %
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-2020 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                 :            :   /* True if this map is for out-of-ssa, otherwise for live range
      74                 :            :      computation.  When for out-of-ssa, it also means the var map is computed
      75                 :            :      for whole current function.  */
      76                 :            :   bool outofssa_p;
      77                 :            : } *var_map;
      78                 :            : 
      79                 :            : 
      80                 :            : /* Value used to represent no partition number.  */
      81                 :            : #define NO_PARTITION            -1
      82                 :            : 
      83                 :            : extern var_map init_var_map (int, class loop* = NULL);
      84                 :            : extern void delete_var_map (var_map);
      85                 :            : extern int var_union (var_map, tree, tree);
      86                 :            : extern void partition_view_normal (var_map);
      87                 :            : extern void partition_view_bitmap (var_map, bitmap);
      88                 :            : extern void dump_scope_blocks (FILE *, dump_flags_t);
      89                 :            : extern void debug_scope_block (tree, dump_flags_t);
      90                 :            : extern void debug_scope_blocks (dump_flags_t);
      91                 :            : extern void remove_unused_locals (void);
      92                 :            : extern void dump_var_map (FILE *, var_map);
      93                 :            : extern void debug (_var_map &ref);
      94                 :            : extern void debug (_var_map *ptr);
      95                 :            : 
      96                 :            : 
      97                 :            : /* Return TRUE if region of the MAP contains basic block BB.  */
      98                 :            : 
      99                 :            : inline bool
     100                 :   44468600 : region_contains_p (var_map map, basic_block bb)
     101                 :            : {
     102                 :            :   /* It's possible that the function is called with ENTRY_BLOCK/EXIT_BLOCK.  */
     103                 :   44468600 :   if (map->outofssa_p)
     104                 :   44468600 :     return (bb->index != ENTRY_BLOCK && bb->index != EXIT_BLOCK);
     105                 :            : 
     106                 :          0 :   return bitmap_bit_p (map->bmp_bbs, bb->index);
     107                 :            : }
     108                 :            : 
     109                 :            : 
     110                 :            : /* Return number of partitions in MAP.  */
     111                 :            : 
     112                 :            : static inline unsigned
     113                 :   72106900 : num_var_partitions (var_map map)
     114                 :            : {
     115                 :   31891210 :   return map->num_partitions;
     116                 :            : }
     117                 :            : 
     118                 :            : 
     119                 :            : /* Given partition index I from MAP, return the variable which represents that
     120                 :            :    partition.  */
     121                 :            : 
     122                 :            : static inline tree
     123                 :            : partition_to_var (var_map map, int i)
     124                 :            : {
     125                 :            :   tree name;
     126                 :            :   if (map->view_to_partition)
     127                 :            :     i = map->view_to_partition[i];
     128                 :            :   i = partition_find (map->var_partition, i);
     129                 :            :   name = ssa_name (i);
     130                 :            :   return name;
     131                 :            : }
     132                 :            : 
     133                 :            : 
     134                 :            : /* Given ssa_name VERSION, if it has a partition in MAP,  return the var it
     135                 :            :    is associated with.  Otherwise return NULL.  */
     136                 :            : 
     137                 :            : static inline tree
     138                 :       1253 : version_to_var (var_map map, int version)
     139                 :            : {
     140                 :       1253 :   int part;
     141                 :       1253 :   part = partition_find (map->var_partition, version);
     142                 :       1253 :   if (map->partition_to_view)
     143                 :       1253 :     part = map->partition_to_view[part];
     144                 :       1253 :   if (part == NO_PARTITION)
     145                 :            :     return NULL_TREE;
     146                 :            : 
     147                 :        356 :   return partition_to_var (map, part);
     148                 :            : }
     149                 :            : 
     150                 :            : 
     151                 :            : /* Given VAR, return the partition number in MAP which contains it.
     152                 :            :    NO_PARTITION is returned if it's not in any partition.  */
     153                 :            : 
     154                 :            : static inline int
     155                 :            : var_to_partition (var_map map, tree var)
     156                 :            : {
     157                 :            :   int part;
     158                 :            : 
     159                 :            :   part = partition_find (map->var_partition, SSA_NAME_VERSION (var));
     160                 :            :   if (map->partition_to_view)
     161                 :            :     part = map->partition_to_view[part];
     162                 :            :   return part;
     163                 :            : }
     164                 :            : 
     165                 :            : 
     166                 :            : /* Given VAR, return the variable which represents the entire partition
     167                 :            :    it is a member of in MAP.  NULL is returned if it is not in a partition.  */
     168                 :            : 
     169                 :            : static inline tree
     170                 :    1584190 : var_to_partition_to_var (var_map map, tree var)
     171                 :            : {
     172                 :    1584190 :   int part;
     173                 :            : 
     174                 :    1584190 :   part = var_to_partition (map, var);
     175                 :    1584190 :   if (part == NO_PARTITION)
     176                 :            :     return NULL_TREE;
     177                 :    1584190 :   return partition_to_var (map, part);
     178                 :            : }
     179                 :            : 
     180                 :            : 
     181                 :            : /* Return the index into the basevar table for PARTITION's base in MAP.  */
     182                 :            : 
     183                 :            : static inline int
     184                 :   39528100 : basevar_index (var_map map, int partition)
     185                 :            : {
     186                 :   39528100 :   gcc_checking_assert (partition >= 0
     187                 :            :                        && partition <= (int) num_var_partitions (map));
     188                 :   39528100 :   return map->partition_to_base_index[partition];
     189                 :            : }
     190                 :            : 
     191                 :            : 
     192                 :            : /* Return the number of different base variables in MAP.  */
     193                 :            : 
     194                 :            : static inline int
     195                 :     831566 : num_basevars (var_map map)
     196                 :            : {
     197                 :     831566 :   return map->num_basevars;
     198                 :            : }
     199                 :            : 
     200                 :            : 
     201                 :            : /*  ---------------- live on entry/exit info ------------------------------
     202                 :            : 
     203                 :            :     This structure is used to represent live range information on SSA based
     204                 :            :     trees. A partition map must be provided, and based on the active partitions,
     205                 :            :     live-on-entry information and live-on-exit information can be calculated.
     206                 :            :     As well, partitions are marked as to whether they are global (live
     207                 :            :     outside the basic block they are defined in).
     208                 :            : 
     209                 :            :     The live-on-entry information is per block.  It provide a bitmap for
     210                 :            :     each block which has a bit set for each partition that is live on entry to
     211                 :            :     that block.
     212                 :            : 
     213                 :            :     The live-on-exit information is per block.  It provides a bitmap for each
     214                 :            :     block indicating which partitions are live on exit from the block.
     215                 :            : 
     216                 :            :     For the purposes of this implementation, we treat the elements of a PHI
     217                 :            :     as follows:
     218                 :            : 
     219                 :            :        Uses in a PHI are considered LIVE-ON-EXIT to the block from which they
     220                 :            :        originate. They are *NOT* considered live on entry to the block
     221                 :            :        containing the PHI node.
     222                 :            : 
     223                 :            :        The Def of a PHI node is *not* considered live on entry to the block.
     224                 :            :        It is considered to be "define early" in the block. Picture it as each
     225                 :            :        block having a stmt (or block-preheader) before the first real stmt in
     226                 :            :        the block which defines all the variables that are defined by PHIs.
     227                 :            : 
     228                 :            :     -----------------------------------------------------------------------  */
     229                 :            : 
     230                 :            : 
     231                 :            : typedef struct tree_live_info_d
     232                 :            : {
     233                 :            :   /* Var map this relates to.  */
     234                 :            :   var_map map;
     235                 :            : 
     236                 :            :   /* Bitmap indicating which partitions are global.  */
     237                 :            :   bitmap global;
     238                 :            : 
     239                 :            :   /* Bitmaps of live on entry blocks for partition elements.  */
     240                 :            :   bitmap_head *livein;
     241                 :            : 
     242                 :            :   /* Bitmaps of what variables are live on exit for a basic blocks.  */
     243                 :            :   bitmap_head *liveout;
     244                 :            : 
     245                 :            :   /* Number of basic blocks when live on exit calculated.  */
     246                 :            :   int num_blocks;
     247                 :            : 
     248                 :            :   /* Vector used when creating live ranges as a visited stack.  */
     249                 :            :   int *work_stack;
     250                 :            : 
     251                 :            :   /* Top of workstack.  */
     252                 :            :   int *stack_top;
     253                 :            : 
     254                 :            :   /* Obstacks to allocate the bitmaps on.  */
     255                 :            :   bitmap_obstack livein_obstack;
     256                 :            :   bitmap_obstack liveout_obstack;
     257                 :            : } *tree_live_info_p;
     258                 :            : 
     259                 :            : 
     260                 :            : #define LIVEDUMP_ENTRY  0x01
     261                 :            : #define LIVEDUMP_EXIT   0x02
     262                 :            : #define LIVEDUMP_ALL    (LIVEDUMP_ENTRY | LIVEDUMP_EXIT)
     263                 :            : extern void delete_tree_live_info (tree_live_info_p);
     264                 :            : extern tree_live_info_p calculate_live_ranges (var_map, bool);
     265                 :            : extern void debug (tree_live_info_d &ref);
     266                 :            : extern void debug (tree_live_info_d *ptr);
     267                 :            : extern void dump_live_info (FILE *, tree_live_info_p, int);
     268                 :            : 
     269                 :            : typedef hash_map<int_hash <unsigned int, -1U>, unsigned int> live_vars_map;
     270                 :            : extern vec<bitmap_head> compute_live_vars (struct function *, live_vars_map *);
     271                 :            : extern bitmap live_vars_at_stmt (vec<bitmap_head> &, live_vars_map *,
     272                 :            :                                  gimple *);
     273                 :            : extern void destroy_live_vars (vec<bitmap_head> &);
     274                 :            : 
     275                 :            : /*  Return TRUE if P is marked as a global in LIVE.  */
     276                 :            : 
     277                 :            : static inline int
     278                 :            : partition_is_global (tree_live_info_p live, int p)
     279                 :            : {
     280                 :            :   gcc_checking_assert (live->global);
     281                 :            :   return bitmap_bit_p (live->global, p);
     282                 :            : }
     283                 :            : 
     284                 :            : 
     285                 :            : /* Return the bitmap from LIVE representing the live on entry blocks for
     286                 :            :    partition P.  */
     287                 :            : 
     288                 :            : static inline bitmap
     289                 :            : live_on_entry (tree_live_info_p live, basic_block bb)
     290                 :            : {
     291                 :            :   gcc_checking_assert (live->livein
     292                 :            :                        && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     293                 :            :                        && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
     294                 :            : 
     295                 :            :   return &live->livein[bb->index];
     296                 :            : }
     297                 :            : 
     298                 :            : 
     299                 :            : /* Return the bitmap from LIVE representing the live on exit partitions from
     300                 :            :    block BB.  */
     301                 :            : 
     302                 :            : static inline bitmap
     303                 :            : live_on_exit (tree_live_info_p live, basic_block bb)
     304                 :            : {
     305                 :            :   gcc_checking_assert (live->liveout
     306                 :            :                        && bb != ENTRY_BLOCK_PTR_FOR_FN (cfun)
     307                 :            :                        && bb != EXIT_BLOCK_PTR_FOR_FN (cfun));
     308                 :            : 
     309                 :            :   return &live->liveout[bb->index];
     310                 :            : }
     311                 :            : 
     312                 :            : 
     313                 :            : /* Return the partition map which the information in LIVE utilizes.  */
     314                 :            : 
     315                 :            : static inline var_map
     316                 :     831566 : live_var_map (tree_live_info_p live)
     317                 :            : {
     318                 :     831566 :   return live->map;
     319                 :            : }
     320                 :            : 
     321                 :            : 
     322                 :            : /* Mark partition P as live on entry to basic block BB in LIVE.  */
     323                 :            : 
     324                 :            : static inline void
     325                 :            : make_live_on_entry (tree_live_info_p live, basic_block bb , int p)
     326                 :            : {
     327                 :            :   bitmap_set_bit (&live->livein[bb->index], p);
     328                 :            :   bitmap_set_bit (live->global, p);
     329                 :            : }
     330                 :            : 
     331                 :            : #endif /* _TREE_SSA_LIVE_H  */

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.