LCOV - code coverage report
Current view: top level - gcc - ipa-cp.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 100.0 % 18 18
Test Date: 2024-11-30 13:30:02 Functions: - 0 0
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Interprocedural constant propagation
       2                 :             :    Copyright (C) 2024 Free Software Foundation, Inc.
       3                 :             : 
       4                 :             : This file is part of GCC.
       5                 :             : 
       6                 :             : GCC is free software; you can redistribute it and/or modify it under
       7                 :             : the terms of the GNU General Public License as published by the Free
       8                 :             : Software Foundation; either version 3, or (at your option) any later
       9                 :             : version.
      10                 :             : 
      11                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :             : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :             : for more details.
      15                 :             : 
      16                 :             : You should have received a copy of the GNU General Public License
      17                 :             : along with GCC; see the file COPYING3.  If not see
      18                 :             : <http://www.gnu.org/licenses/>.  */
      19                 :             : 
      20                 :             : #ifndef IPA_CP_H
      21                 :             : #define IPA_CP_H
      22                 :             : 
      23                 :             : template <typename valtype> class ipcp_value;
      24                 :             : 
      25                 :             : /* Describes a particular source for an IPA-CP value.  */
      26                 :             : 
      27                 :             : template <typename valtype>
      28                 :             : struct ipcp_value_source
      29                 :             : {
      30                 :             : public:
      31                 :             :   /* Aggregate offset of the source, negative if the source is scalar value of
      32                 :             :      the argument itself.  */
      33                 :             :   HOST_WIDE_INT offset;
      34                 :             :   /* The incoming edge that brought the value.  */
      35                 :             :   cgraph_edge *cs;
      36                 :             :   /* If the jump function that resulted into his value was a pass-through or an
      37                 :             :      ancestor, this is the ipcp_value of the caller from which the described
      38                 :             :      value has been derived.  Otherwise it is NULL.  */
      39                 :             :   ipcp_value<valtype> *val;
      40                 :             :   /* Next pointer in a linked list of sources of a value.  */
      41                 :             :   ipcp_value_source *next;
      42                 :             :   /* If the jump function that resulted into his value was a pass-through or an
      43                 :             :      ancestor, this is the index of the parameter of the caller the jump
      44                 :             :      function references.  */
      45                 :             :   int index;
      46                 :             : };
      47                 :             : 
      48                 :             : /* Common ancestor for all ipcp_value instantiations.  */
      49                 :             : 
      50                 :             : class ipcp_value_base
      51                 :             : {
      52                 :             : public:
      53                 :             :   /* Time benefit and that specializing the function for this value would bring
      54                 :             :      about in this function alone.  */
      55                 :             :   sreal local_time_benefit = 0;
      56                 :             :   /* Time benefit that specializing the function for this value can bring about
      57                 :             :      in it's callees.  */
      58                 :             :   sreal prop_time_benefit = 0;
      59                 :             :   /* Size cost that specializing the function for this value would bring about
      60                 :             :      in this function alone.  */
      61                 :             :   int local_size_cost = 0;
      62                 :             :   /* Size cost that specializing the function for this value can bring about in
      63                 :             :      it's callees.  */
      64                 :             :   int prop_size_cost = 0;
      65                 :             : };
      66                 :             : 
      67                 :             : /* Describes one particular value stored in struct ipcp_lattice.  */
      68                 :             : 
      69                 :             : template <typename valtype>
      70                 :             : class ipcp_value : public ipcp_value_base
      71                 :             : {
      72                 :             : public:
      73                 :             :   /* The actual value for the given parameter.  */
      74                 :             :   valtype value;
      75                 :             :   /* The list of sources from which this value originates.  */
      76                 :             :   ipcp_value_source <valtype> *sources = nullptr;
      77                 :             :   /* Next pointers in a linked list of all values in a lattice.  */
      78                 :             :   ipcp_value *next = nullptr;
      79                 :             :   /* Next pointers in a linked list of values in a strongly connected component
      80                 :             :      of values. */
      81                 :             :   ipcp_value *scc_next = nullptr;
      82                 :             :   /* Next pointers in a linked list of SCCs of values sorted topologically
      83                 :             :      according their sources.  */
      84                 :             :   ipcp_value  *topo_next = nullptr;
      85                 :             :   /* A specialized node created for this value, NULL if none has been (so far)
      86                 :             :      created.  */
      87                 :             :   cgraph_node *spec_node = nullptr;
      88                 :             :   /* Depth first search number and low link for topological sorting of
      89                 :             :      values.  */
      90                 :             :   int dfs = 0;
      91                 :             :   int low_link = 0;
      92                 :             :   /* SCC number to identify values which recursively feed into each other.
      93                 :             :      Values in the same SCC have the same SCC number.  */
      94                 :             :   int scc_no = 0;
      95                 :             :   /* Non zero if the value is generated from another value in the same lattice
      96                 :             :      for a self-recursive call, the actual number is how many times the
      97                 :             :      operation has been performed.  In the unlikely event of the value being
      98                 :             :      present in two chains fo self-recursive value generation chains, it is the
      99                 :             :      maximum.  */
     100                 :             :   unsigned self_recursion_generated_level = 0;
     101                 :             :   /* True if this value is currently on the topo-sort stack.  */
     102                 :             :   bool on_stack = false;
     103                 :             : 
     104                 :             :   void add_source (cgraph_edge *cs, ipcp_value *src_val, int src_idx,
     105                 :             :                    HOST_WIDE_INT offset);
     106                 :             : 
     107                 :             :   /* Return true if both THIS value and O feed into each other.  */
     108                 :             : 
     109                 :       14127 :   bool same_scc (const ipcp_value<valtype> *o)
     110                 :             :   {
     111                 :       14127 :     return o->scc_no == scc_no;
     112                 :             :   }
     113                 :             : 
     114                 :             : /* Return true, if a this value has been generated for a self-recursive call as
     115                 :             :    a result of an arithmetic pass-through jump-function acting on a value in
     116                 :             :    the same lattice function.  */
     117                 :             : 
     118                 :       62465 :   bool self_recursion_generated_p ()
     119                 :             :   {
     120                 :       62465 :     return self_recursion_generated_level > 0;
     121                 :             :   }
     122                 :             : };
     123                 :             : 
     124                 :             : /* Lattice describing potential values of a formal parameter of a function, or
     125                 :             :    a part of an aggregate.  TOP is represented by a lattice with zero values
     126                 :             :    and with contains_variable and bottom flags cleared.  BOTTOM is represented
     127                 :             :    by a lattice with the bottom flag set.  In that case, values and
     128                 :             :    contains_variable flag should be disregarded.  */
     129                 :             : 
     130                 :             : template <typename valtype>
     131                 :       44588 : struct ipcp_lattice
     132                 :             : {
     133                 :             : public:
     134                 :             :   /* The list of known values and types in this lattice.  Note that values are
     135                 :             :      not deallocated if a lattice is set to bottom because there may be value
     136                 :             :      sources referencing them.  */
     137                 :             :   ipcp_value<valtype> *values = nullptr;
     138                 :             :   /* Number of known values and types in this lattice.  */
     139                 :             :   int values_count = 0;
     140                 :             :   /* The lattice contains a variable component (in addition to values).  */
     141                 :             :   bool contains_variable = false;
     142                 :             :   /* The value of the lattice is bottom (i.e. variable and unusable for any
     143                 :             :      propagation).  */
     144                 :             :   bool bottom = false;
     145                 :             : 
     146                 :             :   inline bool is_single_const ();
     147                 :             :   inline bool set_to_bottom ();
     148                 :             :   inline bool set_contains_variable ();
     149                 :             :   bool add_value (valtype newval, cgraph_edge *cs,
     150                 :             :                   ipcp_value<valtype> *src_val = NULL,
     151                 :             :                   int src_idx = 0, HOST_WIDE_INT offset = -1,
     152                 :             :                   ipcp_value<valtype> **val_p = NULL,
     153                 :             :                   unsigned same_lat_gen_level = 0);
     154                 :             :   void print (FILE * f, bool dump_sources, bool dump_benefits);
     155                 :             : };
     156                 :             : 
     157                 :             : /* Lattice of tree values with an offset to describe a part of an
     158                 :             :    aggregate.  */
     159                 :             : 
     160                 :       44588 : struct ipcp_agg_lattice : public ipcp_lattice<tree>
     161                 :             : {
     162                 :             : public:
     163                 :             :   /* Offset that is being described by this lattice. */
     164                 :             :   HOST_WIDE_INT offset = 0;
     165                 :             :   /* Size so that we don't have to re-compute it every time we traverse the
     166                 :             :      list.  Must correspond to TYPE_SIZE of all lat values.  */
     167                 :             :   HOST_WIDE_INT size = 0;
     168                 :             :   /* Next element of the linked list.  */
     169                 :             :   struct ipcp_agg_lattice *next = nullptr;
     170                 :             : };
     171                 :             : 
     172                 :             : /* Lattice of known bits, only capable of holding one value.
     173                 :             :    Bitwise constant propagation propagates which bits of a
     174                 :             :    value are constant.
     175                 :             :    For eg:
     176                 :             :    int f(int x)
     177                 :             :    {
     178                 :             :      return some_op (x);
     179                 :             :    }
     180                 :             : 
     181                 :             :    int f1(int y)
     182                 :             :    {
     183                 :             :      if (cond)
     184                 :             :       return f (y & 0xff);
     185                 :             :      else
     186                 :             :       return f (y & 0xf);
     187                 :             :    }
     188                 :             : 
     189                 :             :    In the above case, the param 'x' will always have all
     190                 :             :    the bits (except the bits in lsb) set to 0.
     191                 :             :    Hence the mask of 'x' would be 0xff. The mask
     192                 :             :    reflects that the bits in lsb are unknown.
     193                 :             :    The actual propagated value is given by m_value & ~m_mask.  */
     194                 :             : 
     195                 :             : class ipcp_bits_lattice
     196                 :             : {
     197                 :             : public:
     198                 :     6159901 :   bool bottom_p () const { return m_lattice_val == IPA_BITS_VARYING; }
     199                 :       82103 :   bool top_p () const { return m_lattice_val == IPA_BITS_UNDEFINED; }
     200                 :     2509439 :   bool constant_p () const { return m_lattice_val == IPA_BITS_CONSTANT; }
     201                 :             :   bool set_to_bottom ();
     202                 :             :   bool set_to_constant (widest_int, widest_int);
     203                 :             :   bool known_nonzero_p () const;
     204                 :             : 
     205                 :      102938 :   widest_int get_value () const { return m_value; }
     206                 :      102938 :   widest_int get_mask () const { return m_mask; }
     207                 :             : 
     208                 :             :   bool meet_with (ipcp_bits_lattice& other, unsigned, signop,
     209                 :             :                   enum tree_code, tree, bool);
     210                 :             : 
     211                 :             :   bool meet_with (widest_int, widest_int, unsigned);
     212                 :             : 
     213                 :             :   void print (FILE *);
     214                 :             : 
     215                 :             : private:
     216                 :             :   enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING }
     217                 :             :     m_lattice_val = IPA_BITS_UNDEFINED;
     218                 :             : 
     219                 :             :   /* Similar to ccp_lattice_t, mask represents which bits of value are constant.
     220                 :             :      If a bit in mask is set to 0, then the corresponding bit in
     221                 :             :      value is known to be constant.  */
     222                 :             :   widest_int m_value, m_mask;
     223                 :             : 
     224                 :             :   bool meet_with_1 (widest_int, widest_int, unsigned, bool);
     225                 :             :   void get_value_and_mask (tree, widest_int *, widest_int *);
     226                 :             : };
     227                 :             : 
     228                 :             : /* Lattice of value ranges.  */
     229                 :             : 
     230                 :     4316984 : class ipcp_vr_lattice
     231                 :             : {
     232                 :             : public:
     233                 :             :   value_range m_vr;
     234                 :             : 
     235                 :             :   inline bool bottom_p () const;
     236                 :             :   inline bool top_p () const;
     237                 :             :   inline bool set_to_bottom ();
     238                 :             :   bool meet_with (const vrange &p_vr);
     239                 :             :   bool meet_with (const ipcp_vr_lattice &other);
     240                 :             :   void init (tree type);
     241                 :             :   void print (FILE * f);
     242                 :             : 
     243                 :             : private:
     244                 :             :   bool meet_with_1 (const vrange &other_vr);
     245                 :             : };
     246                 :             : 
     247                 :             : inline void
     248                 :     2158492 : ipcp_vr_lattice::init (tree type)
     249                 :             : {
     250                 :     1968511 :   if (type)
     251                 :     2158492 :     m_vr.set_type (type);
     252                 :             : 
     253                 :             :   // Otherwise m_vr will default to unsupported_range.
     254                 :             : }
     255                 :             : 
     256                 :             : /* Structure containing lattices for a parameter itself and for pieces of
     257                 :             :    aggregates that are passed in the parameter or by a reference in a parameter
     258                 :             :    plus some other useful flags.
     259                 :             : 
     260                 :             :    Even after construction, m_value_range parts still need to be initialized
     261                 :             :    with the type they represent with the init method.  */
     262                 :             : 
     263                 :     2158492 : class ipcp_param_lattices
     264                 :             : {
     265                 :             : public:
     266                 :             :   /* Lattice describing the value of the parameter itself.  */
     267                 :             :   ipcp_lattice<tree> itself;
     268                 :             :   /* Lattice describing the polymorphic contexts of a parameter.  */
     269                 :             :   ipcp_lattice<ipa_polymorphic_call_context> ctxlat;
     270                 :             :   /* Lattices describing aggregate parts.  */
     271                 :             :   ipcp_agg_lattice *aggs = nullptr;
     272                 :             :   /* Lattice describing known bits.  */
     273                 :             :   ipcp_bits_lattice bits_lattice;
     274                 :             :   /* Lattice describing value range.  */
     275                 :             :   ipcp_vr_lattice m_value_range;
     276                 :             :   /* Number of aggregate lattices */
     277                 :             :   int aggs_count = 0;
     278                 :             :   /* True if aggregate data were passed by reference (as opposed to by
     279                 :             :      value).  */
     280                 :             :   bool aggs_by_ref = false;
     281                 :             :   /* All aggregate lattices contain a variable component (in addition to
     282                 :             :      values).  */
     283                 :             :   bool aggs_contain_variable = false;
     284                 :             :   /* The value of all aggregate lattices is bottom (i.e. variable and unusable
     285                 :             :      for any propagation).  */
     286                 :             :   bool aggs_bottom = false;
     287                 :             : 
     288                 :             :   /* There is a virtual call based on this parameter.  */
     289                 :             :   bool virt_call = false;
     290                 :             : };
     291                 :             : 
     292                 :             : bool values_equal_for_ipcp_p (tree x, tree y);
     293                 :             : 
     294                 :             : /* Return TRUE if IPA supports ranges of TYPE.  */
     295                 :             : 
     296                 :             : static inline bool
     297                 :    18239198 : ipa_vr_supported_type_p (tree type)
     298                 :             : {
     299                 :     9739546 :   return irange::supports_p (type) || prange::supports_p (type);
     300                 :             : }
     301                 :             : 
     302                 :             : #endif /* IPA_CP_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.