LCOV - code coverage report
Current view: top level - gcc - ipa-modref-tree.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 93.0 % 244 227
Test Date: 2024-03-23 14:05:01 Functions: 100.0 % 32 32
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Data structure for the modref pass.
       2                 :             :    Copyright (C) 2020-2024 Free Software Foundation, Inc.
       3                 :             :    Contributed by David Cepelik and Jan Hubicka
       4                 :             : 
       5                 :             : This file is part of GCC.
       6                 :             : 
       7                 :             : GCC is free software; you can redistribute it and/or modify it under
       8                 :             : the terms of the GNU General Public License as published by the Free
       9                 :             : Software Foundation; either version 3, or (at your option) any later
      10                 :             : version.
      11                 :             : 
      12                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :             : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :             : 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                 :             : /* modref_tree represent a decision tree that can be used by alias analysis
      22                 :             :    oracle to determine whether given memory access can be affected by a function
      23                 :             :    call.  For every function we collect two trees, one for loads and other
      24                 :             :    for stores.  Tree consist of following levels:
      25                 :             : 
      26                 :             :    1) Base: this level represent base alias set of the access and refers
      27                 :             :       to sons (ref nodes). Flag all_refs means that all possible references
      28                 :             :       are aliasing.
      29                 :             : 
      30                 :             :       Because for LTO streaming we need to stream types rather than alias sets
      31                 :             :       modref_base_node is implemented as a template.
      32                 :             :    2) Ref: this level represent ref alias set and links to accesses unless
      33                 :             :       all_refs flag is set.
      34                 :             :       Again ref is an template to allow LTO streaming.
      35                 :             :    3) Access: this level represent info about individual accesses.  Presently
      36                 :             :       we record whether access is through a dereference of a function parameter
      37                 :             :       and if so we record the access range.
      38                 :             : */
      39                 :             : 
      40                 :             : #ifndef GCC_MODREF_TREE_H
      41                 :             : #define GCC_MODREF_TREE_H
      42                 :             : 
      43                 :             : struct ipa_modref_summary;
      44                 :             : 
      45                 :             : /* parm indexes greater than 0 are normal parms.
      46                 :             :    Some negative values have special meaning.  */
      47                 :             : enum modref_special_parms {
      48                 :             :   MODREF_UNKNOWN_PARM = -1,
      49                 :             :   MODREF_STATIC_CHAIN_PARM = -2,
      50                 :             :   MODREF_RETSLOT_PARM = -3,
      51                 :             :   /* Used for bases that points to memory that escapes from function.  */
      52                 :             :   MODREF_GLOBAL_MEMORY_PARM = -4,
      53                 :             :   /* Used in modref_parm_map to take references which can be removed
      54                 :             :      from the summary during summary update since they now points to local
      55                 :             :      memory.  */
      56                 :             :   MODREF_LOCAL_MEMORY_PARM = -5
      57                 :             : };
      58                 :             : 
      59                 :             : /* Modref record accesses relative to function parameters.
      60                 :             :    This is entry for single access specifying its base and access range.
      61                 :             : 
      62                 :             :    Accesses can be collected to boundedly sized arrays using
      63                 :             :    modref_access_node::insert.  */
      64                 :             : struct GTY(()) modref_access_node
      65                 :             : {
      66                 :             :   /* Access range information (in bits).  */
      67                 :             :   poly_int64 offset;
      68                 :             :   poly_int64 size;
      69                 :             :   poly_int64 max_size;
      70                 :             : 
      71                 :             :   /* Offset from parameter pointer to the base of the access (in bytes).  */
      72                 :             :   poly_int64 parm_offset;
      73                 :             : 
      74                 :             :   /* Index of parameter which specifies the base of access. -1 if base is not
      75                 :             :      a function parameter.  */
      76                 :             :   int parm_index;
      77                 :             :   bool parm_offset_known;
      78                 :             :   /* Number of times interval was extended during dataflow.
      79                 :             :      This has to be limited in order to keep dataflow finite.  */
      80                 :             :   unsigned char adjustments;
      81                 :             : 
      82                 :             :   /* Return true if access node holds some useful info.  */
      83                 :     9340716 :   bool useful_p () const
      84                 :             :     {
      85                 :     9340716 :       return parm_index != MODREF_UNKNOWN_PARM;
      86                 :             :     }
      87                 :             :   /* Return true if access can be used to determine a kill.  */
      88                 :     4563039 :   bool useful_for_kill_p () const
      89                 :             :     {
      90                 :     4016106 :       return parm_offset_known && parm_index != MODREF_UNKNOWN_PARM
      91                 :     4016106 :              && parm_index != MODREF_GLOBAL_MEMORY_PARM
      92                 :     4016106 :              && parm_index != MODREF_RETSLOT_PARM && known_size_p (size)
      93                 :     4016089 :              && known_eq (max_size, size)
      94                 :     8577335 :              && known_gt (size, 0);
      95                 :             :     }
      96                 :             :   /* Dump range to debug OUT.  */
      97                 :             :   void dump (FILE *out);
      98                 :             :   /* Return true if both accesses are the same.  */
      99                 :             :   bool operator == (modref_access_node &a) const;
     100                 :             :   /* Return true if range info is useful.  */
     101                 :             :   bool range_info_useful_p () const;
     102                 :             :   /* Return tree corresponding to parameter of the range in STMT.  */
     103                 :             :   tree get_call_arg (const gcall *stmt) const;
     104                 :             :   /* Build ao_ref corresponding to the access and return true if successful.  */
     105                 :             :   bool get_ao_ref (const gcall *stmt, class ao_ref *ref) const;
     106                 :             :   /* Stream access to OB.  */
     107                 :             :   void stream_out (struct output_block *ob) const;
     108                 :             :   /* Stream access in from IB.  */
     109                 :             :   static modref_access_node stream_in (struct lto_input_block *ib);
     110                 :             :   /* Insert A into vector ACCESSES.  Limit size of vector to MAX_ACCESSES and
     111                 :             :      if RECORD_ADJUSTMENT is true keep track of adjustment counts.
     112                 :             :      Return 0 if nothing changed, 1 is insertion succeeded and -1 if failed.  */
     113                 :             :   static int insert (vec <modref_access_node, va_gc> *&accesses,
     114                 :             :                      modref_access_node a, size_t max_accesses,
     115                 :             :                      bool record_adjustments);
     116                 :             :   /* Same as insert but for kills where we are conservative the other way
     117                 :             :      around: if information is lost, the kill is lost.  */
     118                 :             :   static bool insert_kill (vec<modref_access_node> &kills,
     119                 :             :                            modref_access_node &a, bool record_adjustments);
     120                 :             : private:
     121                 :             :   bool contains (const modref_access_node &) const;
     122                 :             :   bool contains_for_kills (const modref_access_node &) const;
     123                 :             :   void update (poly_int64, poly_int64, poly_int64, poly_int64, bool);
     124                 :             :   bool update_for_kills (poly_int64, poly_int64, poly_int64,
     125                 :             :                          poly_int64, poly_int64, bool);
     126                 :             :   bool merge (const modref_access_node &, bool);
     127                 :             :   bool merge_for_kills (const modref_access_node &, bool);
     128                 :             :   static bool closer_pair_p (const modref_access_node &,
     129                 :             :                              const modref_access_node &,
     130                 :             :                              const modref_access_node &,
     131                 :             :                              const modref_access_node &);
     132                 :             :   void forced_merge (const modref_access_node &, bool);
     133                 :             :   void update2 (poly_int64, poly_int64, poly_int64, poly_int64,
     134                 :             :                 poly_int64, poly_int64, poly_int64, bool);
     135                 :             :   bool combined_offsets (const modref_access_node &,
     136                 :             :                          poly_int64 *, poly_int64 *, poly_int64 *) const;
     137                 :             :   static void try_merge_with (vec <modref_access_node, va_gc> *&, size_t);
     138                 :             : };
     139                 :             : 
     140                 :             : /* Access node specifying no useful info.  */
     141                 :             : const modref_access_node unspecified_modref_access_node
     142                 :             :                  = {0, -1, -1, 0, MODREF_UNKNOWN_PARM, false, 0};
     143                 :             : 
     144                 :             : template <typename T>
     145                 :             : struct GTY((user)) modref_ref_node
     146                 :             : {
     147                 :             :   T ref;
     148                 :             :   bool every_access;
     149                 :             :   vec <modref_access_node, va_gc> *accesses;
     150                 :             : 
     151                 :     7147140 :   modref_ref_node (T ref):
     152                 :     7147140 :     ref (ref),
     153                 :     7147140 :     every_access (false),
     154                 :     7147140 :     accesses (NULL)
     155                 :             :   {}
     156                 :             : 
     157                 :             :   /* Collapse the tree.  */
     158                 :     9417463 :   void collapse ()
     159                 :             :   {
     160                 :     9417463 :     vec_free (accesses);
     161                 :     9417463 :     accesses = NULL;
     162                 :     9417463 :     every_access = true;
     163                 :     9417463 :   }
     164                 :             : 
     165                 :             :   /* Insert access with OFFSET and SIZE.
     166                 :             :      Collapse tree if it has more than MAX_ACCESSES entries.
     167                 :             :      If RECORD_ADJUSTMENTs is true avoid too many interval extensions.
     168                 :             :      Return true if record was changed.  */
     169                 :    10448172 :   bool insert_access (modref_access_node a, size_t max_accesses,
     170                 :             :                       bool record_adjustments)
     171                 :             :   {
     172                 :             :     /* If this base->ref pair has no access information, bail out.  */
     173                 :    10448172 :     if (every_access)
     174                 :             :       return false;
     175                 :             : 
     176                 :             :     /* Only the following kind of parameters needs to be tracked.
     177                 :             :        We do not track return slots because they are seen as a direct store
     178                 :             :        in the caller.  */
     179                 :    10448161 :     gcc_checking_assert (a.parm_index >= 0
     180                 :             :                          || a.parm_index == MODREF_STATIC_CHAIN_PARM
     181                 :             :                          || a.parm_index == MODREF_GLOBAL_MEMORY_PARM
     182                 :             :                          || a.parm_index == MODREF_UNKNOWN_PARM);
     183                 :             : 
     184                 :    10448161 :     if (!a.useful_p ())
     185                 :             :       {
     186                 :             :         if (!every_access)
     187                 :             :           {
     188                 :     2221811 :             collapse ();
     189                 :     2221811 :             return true;
     190                 :             :           }
     191                 :             :         return false;
     192                 :             :       }
     193                 :             : 
     194                 :     8226350 :     int ret = modref_access_node::insert (accesses, a, max_accesses,
     195                 :             :                                           record_adjustments);
     196                 :     8226350 :     if (ret == -1)
     197                 :             :       {
     198                 :           3 :         if (dump_file)
     199                 :           0 :           fprintf (dump_file,
     200                 :             :                    "--param modref-max-accesses limit reached; collapsing\n");
     201                 :           3 :         collapse ();
     202                 :             :       }
     203                 :     8226350 :     return ret != 0;
     204                 :             :   }
     205                 :             : };
     206                 :             : 
     207                 :             : /* Base of an access.  */
     208                 :             : template <typename T>
     209                 :             : struct GTY((user)) modref_base_node
     210                 :             : {
     211                 :             :   T base;
     212                 :             :   vec <modref_ref_node <T> *, va_gc> *refs;
     213                 :             :   bool every_ref;
     214                 :             : 
     215                 :     5991744 :   modref_base_node (T base):
     216                 :     5991744 :     base (base),
     217                 :     5991744 :     refs (NULL),
     218                 :     5991744 :     every_ref (false) {}
     219                 :             : 
     220                 :             :   /* Search REF; return NULL if failed.  */
     221                 :    13187921 :   modref_ref_node <T> *search (T ref)
     222                 :             :   {
     223                 :             :     size_t i;
     224                 :             :     modref_ref_node <T> *n;
     225                 :    15866157 :     FOR_EACH_VEC_SAFE_ELT (refs, i, n)
     226                 :     8718899 :       if (n->ref == ref)
     227                 :     6040663 :         return n;
     228                 :             :     return NULL;
     229                 :             :   }
     230                 :             : 
     231                 :             :   /* Insert REF; collapse tree if there are more than MAX_REFS.
     232                 :             :      Return inserted ref and if CHANGED is non-null set it to true if
     233                 :             :      something changed.  */
     234                 :    13187787 :   modref_ref_node <T> *insert_ref (T ref, size_t max_refs,
     235                 :             :                                    bool *changed = NULL)
     236                 :             :   {
     237                 :             :     modref_ref_node <T> *ref_node;
     238                 :             : 
     239                 :             :     /* If the node is collapsed, don't do anything.  */
     240                 :    13187787 :     if (every_ref)
     241                 :             :       return NULL;
     242                 :             : 
     243                 :             :     /* Otherwise, insert a node for the ref of the access under the base.  */
     244                 :    13187787 :     ref_node = search (ref);
     245                 :    13187787 :     if (ref_node)
     246                 :             :       return ref_node;
     247                 :             : 
     248                 :             :     /* We always allow inserting ref 0.  For non-0 refs there is upper
     249                 :             :        limit on number of entries and if exceeded,
     250                 :             :        drop ref conservatively to 0.  */
     251                 :     7147200 :     if (ref && refs && refs->length () >= max_refs)
     252                 :             :       {
     253                 :          98 :         if (dump_file)
     254                 :           0 :           fprintf (dump_file, "--param modref-max-refs limit reached;"
     255                 :             :                    " using 0\n");
     256                 :          98 :         ref = 0;
     257                 :          98 :         ref_node = search (ref);
     258                 :          98 :         if (ref_node)
     259                 :             :           return ref_node;
     260                 :             :       }
     261                 :             : 
     262                 :     7147140 :     if (changed)
     263                 :     7084111 :       *changed = true;
     264                 :             : 
     265                 :     7147140 :     ref_node = new (ggc_alloc <modref_ref_node <T> > ())modref_ref_node <T>
     266                 :             :                                                                  (ref);
     267                 :     7147140 :     vec_safe_push (refs, ref_node);
     268                 :     7147140 :     return ref_node;
     269                 :             :   }
     270                 :             : 
     271                 :     6006867 :   void collapse ()
     272                 :             :   {
     273                 :             :     size_t i;
     274                 :             :     modref_ref_node <T> *r;
     275                 :             : 
     276                 :     6006867 :     if (refs)
     277                 :             :       {
     278                 :    13125774 :         FOR_EACH_VEC_SAFE_ELT (refs, i, r)
     279                 :             :           {
     280                 :     7146508 :             r->collapse ();
     281                 :     7146508 :             ggc_free (r);
     282                 :             :           }
     283                 :    11958532 :         vec_free (refs);
     284                 :             :       }
     285                 :     6006867 :     refs = NULL;
     286                 :     6006867 :     every_ref = true;
     287                 :     6006867 :   }
     288                 :             : };
     289                 :             : 
     290                 :             : /* Map translating parameters across function call.  */
     291                 :             : 
     292                 :             : struct modref_parm_map
     293                 :             : {
     294                 :             :   /* Default constructor.  */
     295                 :    24572978 :   modref_parm_map ()
     296                 :    24572978 :   : parm_index (MODREF_UNKNOWN_PARM), parm_offset_known (false), parm_offset ()
     297                 :             :   {}
     298                 :             : 
     299                 :             :   /* Index of parameter we translate to.
     300                 :             :      Values from special_params enum are permitted too.  */
     301                 :             :   int parm_index;
     302                 :             :   bool parm_offset_known;
     303                 :             :   poly_int64 parm_offset;
     304                 :             : };
     305                 :             : 
     306                 :             : /* Access tree for a single function.  */
     307                 :             : template <typename T>
     308                 :             : struct GTY((user)) modref_tree
     309                 :             : {
     310                 :             :   vec <modref_base_node <T> *, va_gc> *bases;
     311                 :             :   bool every_base;
     312                 :             : 
     313                 :    10243516 :   modref_tree ():
     314                 :    10243516 :     bases (NULL),
     315                 :    10243516 :     every_base (false) {}
     316                 :             : 
     317                 :             :   /* Insert BASE; collapse tree if there are more than MAX_REFS.
     318                 :             :      Return inserted base and if CHANGED is non-null set it to true if
     319                 :             :      something changed.
     320                 :             :      If table gets full, try to insert REF instead.  */
     321                 :             : 
     322                 :    13223367 :   modref_base_node <T> *insert_base (T base, T ref,
     323                 :             :                                      unsigned int max_bases,
     324                 :             :                                      bool *changed = NULL)
     325                 :             :   {
     326                 :             :     modref_base_node <T> *base_node;
     327                 :             : 
     328                 :             :     /* If the node is collapsed, don't do anything.  */
     329                 :    13223367 :     if (every_base)
     330                 :             :       return NULL;
     331                 :             : 
     332                 :             :     /* Otherwise, insert a node for the base of the access into the tree.  */
     333                 :    13223355 :     base_node = search (base);
     334                 :    13223355 :     if (base_node)
     335                 :             :       return base_node;
     336                 :             : 
     337                 :             :     /* We always allow inserting base 0.  For non-0 base there is upper
     338                 :             :        limit on number of entries and if exceeded,
     339                 :             :        drop base conservatively to ref and if it still does not fit to 0.  */
     340                 :     6068534 :     if (base && bases && bases->length () >= max_bases)
     341                 :             :       {
     342                 :       77597 :         base_node = search (ref);
     343                 :       77597 :         if (base_node)
     344                 :             :           {
     345                 :        2591 :             if (dump_file)
     346                 :           0 :               fprintf (dump_file, "--param modref-max-bases"
     347                 :             :                        " limit reached; using ref\n");
     348                 :        2591 :             return base_node;
     349                 :             :           }
     350                 :       75006 :         if (dump_file)
     351                 :           0 :           fprintf (dump_file, "--param modref-max-bases"
     352                 :             :                    " limit reached; using 0\n");
     353                 :       75006 :         base = 0;
     354                 :       75006 :         base_node = search (base);
     355                 :       75006 :         if (base_node)
     356                 :             :           return base_node;
     357                 :             :       }
     358                 :             : 
     359                 :     5991744 :     if (changed)
     360                 :     5930438 :       *changed = true;
     361                 :             : 
     362                 :     5991744 :     base_node = new (ggc_alloc <modref_base_node <T> > ())
     363                 :             :                          modref_base_node <T> (base);
     364                 :     5991744 :     vec_safe_push (bases, base_node);
     365                 :     5991744 :     return base_node;
     366                 :             :   }
     367                 :             : 
     368                 :             :   /* Insert memory access to the tree.
     369                 :             :      Return true if something changed.  */
     370                 :    18161101 :   bool insert (unsigned int max_bases,
     371                 :             :                unsigned int max_refs,
     372                 :             :                unsigned int max_accesses,
     373                 :             :                T base, T ref, modref_access_node a,
     374                 :             :                bool record_adjustments)
     375                 :             :   {
     376                 :    18161101 :     if (every_base)
     377                 :             :       return false;
     378                 :             : 
     379                 :    13668139 :     bool changed = false;
     380                 :             : 
     381                 :             :     /* We may end up with max_size being less than size for accesses past the
     382                 :             :        end of array.  Those are undefined and safe to ignore.  */
     383                 :    13668139 :     if (a.range_info_useful_p ()
     384                 :     6202090 :         && known_size_p (a.size) && known_size_p (a.max_size)
     385                 :    19611483 :         && known_lt (a.max_size, a.size))
     386                 :             :       {
     387                 :          14 :         if (dump_file)
     388                 :           0 :           fprintf (dump_file,
     389                 :             :                    "   - Paradoxical range. Ignoring\n");
     390                 :          14 :         return false;
     391                 :             :       }
     392                 :    13668125 :     if (known_size_p (a.size)
     393                 :    13668125 :         && known_eq (a.size, 0))
     394                 :             :       {
     395                 :         127 :         if (dump_file)
     396                 :           0 :           fprintf (dump_file,
     397                 :             :                    "   - Zero size. Ignoring\n");
     398                 :         127 :         return false;
     399                 :             :       }
     400                 :    13667998 :     if (known_size_p (a.max_size)
     401                 :    13667998 :         && known_eq (a.max_size, 0))
     402                 :             :       {
     403                 :         672 :         if (dump_file)
     404                 :           0 :           fprintf (dump_file,
     405                 :             :                    "   - Zero max_size. Ignoring\n");
     406                 :         672 :         return false;
     407                 :             :       }
     408                 :    13667326 :     gcc_checking_assert (!known_size_p (a.max_size)
     409                 :             :                          || !known_le (a.max_size, 0));
     410                 :             : 
     411                 :             :     /* No useful information tracked; collapse everything.  */
     412                 :    13667326 :     if (!base && !ref && !a.useful_p ())
     413                 :             :       {
     414                 :      513226 :         collapse ();
     415                 :      513226 :         return true;
     416                 :             :       }
     417                 :             : 
     418                 :             :     modref_base_node <T> *base_node
     419                 :    13154100 :       = insert_base (base, ref, max_bases, &changed);
     420                 :    13154100 :     base = base_node->base;
     421                 :             :     /* If table got full we may end up with useless base.  */
     422                 :    13154100 :     if (!base && !ref && !a.useful_p ())
     423                 :             :       {
     424                 :           4 :         collapse ();
     425                 :           4 :         return true;
     426                 :             :       }
     427                 :    13154096 :     if (base_node->every_ref)
     428                 :       20685 :       return changed;
     429                 :    13133411 :     gcc_checking_assert (search (base) != NULL);
     430                 :             : 
     431                 :             :     /* No useful ref info tracked; collapse base.  */
     432                 :    13133411 :     if (!ref && !a.useful_p ())
     433                 :             :       {
     434                 :        9913 :         base_node->collapse ();
     435                 :        9913 :         return true;
     436                 :             :       }
     437                 :             : 
     438                 :             :     modref_ref_node <T> *ref_node
     439                 :    13123498 :             = base_node->insert_ref (ref, max_refs, &changed);
     440                 :    13123498 :     ref = ref_node->ref;
     441                 :             : 
     442                 :    13123498 :     if (ref_node->every_access)
     443                 :     2691225 :       return changed;
     444                 :    10432273 :     changed |= ref_node->insert_access (a, max_accesses,
     445                 :             :                                         record_adjustments);
     446                 :             :     /* See if we failed to add useful access.  */
     447                 :    10432273 :     if (ref_node->every_access)
     448                 :             :       {
     449                 :             :         /* Collapse everything if there is no useful base and ref.  */
     450                 :     2221705 :         if (!base && !ref)
     451                 :             :           {
     452                 :           0 :             collapse ();
     453                 :           0 :             gcc_checking_assert (changed);
     454                 :             :           }
     455                 :             :         /* Collapse base if there is no useful ref.  */
     456                 :     2221705 :         else if (!ref)
     457                 :             :           {
     458                 :           8 :             base_node->collapse ();
     459                 :           8 :             gcc_checking_assert (changed);
     460                 :             :           }
     461                 :             :       }
     462                 :             :     return changed;
     463                 :             :   }
     464                 :             : 
     465                 :             :   /* Insert memory access to the tree.
     466                 :             :      Return true if something changed.  */
     467                 :    14064107 :   bool insert (tree fndecl,
     468                 :             :                T base, T ref, const modref_access_node &a,
     469                 :             :                bool record_adjustments)
     470                 :             :   {
     471                 :    28128214 :      return insert (opt_for_fn (fndecl, param_modref_max_bases),
     472                 :    14064107 :                     opt_for_fn (fndecl, param_modref_max_refs),
     473                 :    14064107 :                     opt_for_fn (fndecl, param_modref_max_accesses),
     474                 :    14064107 :                     base, ref, a, record_adjustments);
     475                 :             :   }
     476                 :             : 
     477                 :             :  /* Remove tree branches that are not useful (i.e. they will always pass).  */
     478                 :             : 
     479                 :      163991 :  void cleanup ()
     480                 :             :  {
     481                 :             :    size_t i, j;
     482                 :             :    modref_base_node <T> *base_node;
     483                 :             :    modref_ref_node <T> *ref_node;
     484                 :             : 
     485                 :      163991 :    if (!bases)
     486                 :      163991 :      return;
     487                 :             : 
     488                 :      130041 :    for (i = 0; vec_safe_iterate (bases, i, &base_node);)
     489                 :             :      {
     490                 :       73968 :        if (base_node->refs)
     491                 :      138385 :          for (j = 0; vec_safe_iterate (base_node->refs, j, &ref_node);)
     492                 :             :            {
     493                 :       71855 :              if (!ref_node->every_access
     494                 :       71855 :                  && (!ref_node->accesses
     495                 :       21863 :                      || !ref_node->accesses->length ()))
     496                 :             :                {
     497                 :           0 :                  base_node->refs->unordered_remove (j);
     498                 :           0 :                  vec_free (ref_node->accesses);
     499                 :           0 :                  ggc_delete (ref_node);
     500                 :             :                }
     501                 :             :              else
     502                 :       71855 :                j++;
     503                 :             :            }
     504                 :       73968 :        if (!base_node->every_ref
     505                 :       73968 :            && (!base_node->refs || !base_node->refs->length ()))
     506                 :             :          {
     507                 :           0 :            bases->unordered_remove (i);
     508                 :           0 :            vec_free (base_node->refs);
     509                 :           0 :            ggc_delete (base_node);
     510                 :             :          }
     511                 :             :        else
     512                 :       73968 :          i++;
     513                 :             :      }
     514                 :       56073 :    if (bases && !bases->length ())
     515                 :             :      {
     516                 :           0 :        vec_free (bases);
     517                 :           0 :        bases = NULL;
     518                 :             :      }
     519                 :             :  }
     520                 :             : 
     521                 :             :   /* Merge OTHER into the tree.
     522                 :             :      PARM_MAP, if non-NULL, maps parm indexes of callee to caller.
     523                 :             :      Similar CHAIN_MAP, if non-NULL, maps static chain of callee to caller.
     524                 :             :      Return true if something has changed.  */
     525                 :     6651159 :   bool merge (unsigned int max_bases,
     526                 :             :               unsigned int max_refs,
     527                 :             :               unsigned int max_accesses,
     528                 :             :               modref_tree <T> *other, vec <modref_parm_map> *parm_map,
     529                 :             :               modref_parm_map *static_chain_map,
     530                 :             :               bool record_accesses,
     531                 :             :               bool promote_unknown_to_global = false)
     532                 :             :   {
     533                 :     6651159 :     if (!other || every_base)
     534                 :             :       return false;
     535                 :     4660169 :     if (other->every_base)
     536                 :             :       {
     537                 :      867802 :         collapse ();
     538                 :      867802 :         return true;
     539                 :             :       }
     540                 :             : 
     541                 :     3792367 :     bool changed = false;
     542                 :             :     size_t i, j, k;
     543                 :             :     modref_base_node <T> *base_node, *my_base_node;
     544                 :             :     modref_ref_node <T> *ref_node;
     545                 :             :     modref_access_node *access_node;
     546                 :     3792367 :     bool release = false;
     547                 :             : 
     548                 :             :     /* For self-recursive functions we may end up merging summary into itself;
     549                 :             :        produce copy first so we do not modify summary under our own hands.  */
     550                 :     3792367 :     if (other == this)
     551                 :             :       {
     552                 :        9830 :         release = true;
     553                 :        9830 :         other = modref_tree<T>::create_ggc ();
     554                 :        9830 :         other->copy_from (this);
     555                 :             :       }
     556                 :             : 
     557                 :     7536214 :     FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node)
     558                 :             :       {
     559                 :     3743847 :         if (base_node->every_ref)
     560                 :             :           {
     561                 :        6857 :             my_base_node = insert_base (base_node->base, 0,
     562                 :             :                                         max_bases, &changed);
     563                 :        6857 :             if (my_base_node && !my_base_node->every_ref)
     564                 :             :               {
     565                 :        5705 :                 my_base_node->collapse ();
     566                 :        5705 :                 cleanup ();
     567                 :        5705 :                 changed = true;
     568                 :             :               }
     569                 :             :           }
     570                 :             :         else
     571                 :    11918459 :           FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
     572                 :             :             {
     573                 :     4437622 :               if (ref_node->every_access)
     574                 :             :                 {
     575                 :     1558271 :                   changed |= insert (max_bases, max_refs, max_accesses,
     576                 :             :                                      base_node->base,
     577                 :             :                                      ref_node->ref,
     578                 :             :                                      unspecified_modref_access_node,
     579                 :             :                                      record_accesses);
     580                 :             :                 }
     581                 :             :               else
     582                 :    10547711 :                 FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
     583                 :             :                   {
     584                 :     3230738 :                     modref_access_node a = *access_node;
     585                 :             : 
     586                 :     3230738 :                     if (a.parm_index != MODREF_UNKNOWN_PARM
     587                 :     3230738 :                         && a.parm_index != MODREF_GLOBAL_MEMORY_PARM
     588                 :     3093721 :                         && parm_map)
     589                 :             :                       {
     590                 :     4027002 :                         if (a.parm_index >= (int)parm_map->length ())
     591                 :             :                           a.parm_index = MODREF_UNKNOWN_PARM;
     592                 :             :                         else
     593                 :             :                           {
     594                 :     2013459 :                             modref_parm_map &m
     595                 :             :                                     = a.parm_index == MODREF_STATIC_CHAIN_PARM
     596                 :     2013459 :                                       ? *static_chain_map
     597                 :             :                                       : (*parm_map) [a.parm_index];
     598                 :     2013459 :                             if (m.parm_index == MODREF_LOCAL_MEMORY_PARM)
     599                 :      692095 :                               continue;
     600                 :     1321364 :                             a.parm_offset += m.parm_offset;
     601                 :     1321364 :                             a.parm_offset_known &= m.parm_offset_known;
     602                 :     1321364 :                             a.parm_index = m.parm_index;
     603                 :             :                           }
     604                 :             :                       }
     605                 :     2538643 :                     if (a.parm_index == MODREF_UNKNOWN_PARM
     606                 :      629002 :                         && promote_unknown_to_global)
     607                 :         266 :                       a.parm_index = MODREF_GLOBAL_MEMORY_PARM;
     608                 :     2538643 :                     changed |= insert (max_bases, max_refs, max_accesses,
     609                 :             :                                        base_node->base, ref_node->ref,
     610                 :             :                                        a, record_accesses);
     611                 :             :                   }
     612                 :             :             }
     613                 :             :       }
     614                 :     3792367 :     if (release)
     615                 :        9830 :       ggc_delete (other);
     616                 :     3792367 :     return changed;
     617                 :             :   }
     618                 :             : 
     619                 :             :   /* Merge OTHER into the tree.
     620                 :             :      PARM_MAP, if non-NULL, maps parm indexes of callee to caller.
     621                 :             :      Similar CHAIN_MAP, if non-NULL, maps static chain of callee to caller.
     622                 :             :      Return true if something has changed.  */
     623                 :     5370285 :   bool merge (tree fndecl,
     624                 :             :               modref_tree <T> *other, vec <modref_parm_map> *parm_map,
     625                 :             :               modref_parm_map *static_chain_map,
     626                 :             :               bool record_accesses,
     627                 :             :               bool promote_unknown_to_global = false)
     628                 :             :   {
     629                 :    10740570 :      return merge (opt_for_fn (fndecl, param_modref_max_bases),
     630                 :     5370285 :                    opt_for_fn (fndecl, param_modref_max_refs),
     631                 :     5370285 :                    opt_for_fn (fndecl, param_modref_max_accesses),
     632                 :             :                    other, parm_map, static_chain_map, record_accesses,
     633                 :     5370285 :                    promote_unknown_to_global);
     634                 :             :   }
     635                 :             : 
     636                 :             :   /* Copy OTHER to THIS.  */
     637                 :     1280870 :   void copy_from (modref_tree <T> *other)
     638                 :             :   {
     639                 :     1280870 :     merge (INT_MAX, INT_MAX, INT_MAX, other, NULL, NULL, false);
     640                 :     1280870 :   }
     641                 :             : 
     642                 :             :   /* Search BASE in tree; return NULL if failed.  */
     643                 :    26509421 :   modref_base_node <T> *search (T base)
     644                 :             :   {
     645                 :             :     size_t i;
     646                 :             :     modref_base_node <T> *n;
     647                 :    53028967 :     FOR_EACH_VEC_SAFE_ELT (bases, i, n)
     648                 :    46884604 :       if (n->base == base)
     649                 :    20365058 :         return n;
     650                 :             :     return NULL;
     651                 :             :   }
     652                 :             : 
     653                 :             :   /* Return true if tree contains access to global memory.  */
     654                 :     7920838 :   bool global_access_p ()
     655                 :             :   {
     656                 :             :     size_t i, j, k;
     657                 :             :     modref_base_node <T> *base_node;
     658                 :             :     modref_ref_node <T> *ref_node;
     659                 :             :     modref_access_node *access_node;
     660                 :     7920838 :     if (every_base)
     661                 :             :       return true;
     662                 :     7202331 :     FOR_EACH_VEC_SAFE_ELT (bases, i, base_node)
     663                 :             :       {
     664                 :     3020720 :         if (base_node->every_ref)
     665                 :             :           return true;
     666                 :     6779979 :         FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
     667                 :             :           {
     668                 :     3482851 :             if (ref_node->every_access)
     669                 :             :               return true;
     670                 :     7119047 :             FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
     671                 :     2887889 :               if (access_node->parm_index == MODREF_UNKNOWN_PARM
     672                 :     2887889 :                   || access_node->parm_index == MODREF_GLOBAL_MEMORY_PARM)
     673                 :             :                 return true;
     674                 :             :           }
     675                 :             :       }
     676                 :             :     return false;
     677                 :             :   }
     678                 :             : 
     679                 :             :   /* Return ggc allocated instance.  We explicitly call destructors via
     680                 :             :      ggc_delete and do not want finalizers to be registered and
     681                 :             :      called at the garbage collection time.  */
     682                 :    10243504 :   static modref_tree<T> *create_ggc ()
     683                 :             :   {
     684                 :     5205810 :     return new (ggc_alloc_no_dtor<modref_tree<T>> ())
     685                 :             :          modref_tree<T> ();
     686                 :             :   }
     687                 :             : 
     688                 :             :   /* Remove all records and mark tree to alias with everything.  */
     689                 :    14467718 :   void collapse ()
     690                 :             :   {
     691                 :             :     size_t i;
     692                 :             :     modref_base_node <T> *n;
     693                 :             : 
     694                 :    14467718 :     if (bases)
     695                 :             :       {
     696                 :    10280363 :         FOR_EACH_VEC_SAFE_ELT (bases, i, n)
     697                 :             :           {
     698                 :     5991112 :             n->collapse ();
     699                 :     5991112 :             ggc_free (n);
     700                 :             :           }
     701                 :     8578502 :         vec_free (bases);
     702                 :             :       }
     703                 :    14467718 :     bases = NULL;
     704                 :    14467718 :     every_base = true;
     705                 :    14467718 :   }
     706                 :             : 
     707                 :             :   /* Release memory.  */
     708                 :    10242300 :   ~modref_tree ()
     709                 :             :   {
     710                 :    10242300 :     collapse ();
     711                 :    10242300 :   }
     712                 :             : 
     713                 :             :   /* Update parameter indexes in TT according to MAP.  */
     714                 :             :   void
     715                 :       37574 :   remap_params (vec <int> *map)
     716                 :             :   {
     717                 :             :     size_t i;
     718                 :             :     modref_base_node <T> *base_node;
     719                 :       67710 :     FOR_EACH_VEC_SAFE_ELT (bases, i, base_node)
     720                 :             :       {
     721                 :             :         size_t j;
     722                 :             :         modref_ref_node <T> *ref_node;
     723                 :       63743 :         FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node)
     724                 :             :           {
     725                 :             :             size_t k;
     726                 :             :             modref_access_node *access_node;
     727                 :       41108 :             FOR_EACH_VEC_SAFE_ELT (ref_node->accesses, k, access_node)
     728                 :       13122 :               if (access_node->parm_index >= 0)
     729                 :             :                 {
     730                 :       25998 :                   if (access_node->parm_index < (int)map->length ())
     731                 :       11852 :                     access_node->parm_index = (*map)[access_node->parm_index];
     732                 :             :                   else
     733                 :        1147 :                     access_node->parm_index = MODREF_UNKNOWN_PARM;
     734                 :             :                 }
     735                 :             :           }
     736                 :             :       }
     737                 :       37574 :   }
     738                 :             : };
     739                 :             : 
     740                 :             : void gt_ggc_mx (modref_tree <int>* const&);
     741                 :             : void gt_ggc_mx (modref_tree <tree_node*>* const&);
     742                 :             : void gt_pch_nx (modref_tree <int>* const&);
     743                 :             : void gt_pch_nx (modref_tree <tree_node*>* const&);
     744                 :             : void gt_pch_nx (modref_tree <int>* const&, gt_pointer_operator op, void *cookie);
     745                 :             : void gt_pch_nx (modref_tree <tree_node*>* const&, gt_pointer_operator op,
     746                 :             :                 void *cookie);
     747                 :             : 
     748                 :             : void gt_ggc_mx (modref_base_node <int>*);
     749                 :             : void gt_ggc_mx (modref_base_node <tree_node*>* &);
     750                 :             : void gt_pch_nx (modref_base_node <int>* const&);
     751                 :             : void gt_pch_nx (modref_base_node <tree_node*>* const&);
     752                 :             : void gt_pch_nx (modref_base_node <int>* const&, gt_pointer_operator op,
     753                 :             :                 void *cookie);
     754                 :             : void gt_pch_nx (modref_base_node <tree_node*>* const&, gt_pointer_operator op,
     755                 :             :                 void *cookie);
     756                 :             : 
     757                 :             : void gt_ggc_mx (modref_ref_node <int>*);
     758                 :             : void gt_ggc_mx (modref_ref_node <tree_node*>* &);
     759                 :             : void gt_pch_nx (modref_ref_node <int>* const&);
     760                 :             : void gt_pch_nx (modref_ref_node <tree_node*>* const&);
     761                 :             : void gt_pch_nx (modref_ref_node <int>* const&, gt_pointer_operator op,
     762                 :             :                 void *cookie);
     763                 :             : void gt_pch_nx (modref_ref_node <tree_node*>* const&, gt_pointer_operator op,
     764                 :             :                 void *cookie);
     765                 :             : 
     766                 :             : #endif
        

Generated by: LCOV version 2.0-1

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.