gcc/pointer-query.h

   1 /* Definitions of the pointer_query and related classes.
   2
   3    Copyright (C) 2020-2021 Free Software Foundation, Inc.
   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 #ifndef GCC_POINTER_QUERY_H
  22 #define GCC_POINTER_QUERY_H
  23
  24 /* Describes recursion limits used by functions that follow use-def
  25    chains of SSA_NAMEs.  */
  26
  27 class ssa_name_limit_t
  28 {
  29   bitmap visited;         /* Bitmap of visited SSA_NAMEs.  */
  30   unsigned ssa_def_max;   /* Longest chain of SSA_NAMEs to follow.  */
  31
  32   /* Not copyable or assignable.  */
  33   DISABLE_COPY_AND_ASSIGN (ssa_name_limit_t);
  34
  35 public:
  36
  37   ssa_name_limit_t ()
  38     : visited (),
  39       ssa_def_max (param_ssa_name_def_chain_limit) { }
  40
  41   /* Set a bit for the PHI in VISITED and return true if it wasn't
  42      already set.  */
  43   bool visit_phi (tree);
  44   /* Clear a bit for the PHI in VISITED.  */
  45   void leave_phi (tree);
  46   /* Return false if the SSA_NAME chain length counter has reached
  47      the limit, otherwise increment the counter and return true.  */
  48   bool next ();
  49
  50   /* If the SSA_NAME has already been "seen" return a positive value.
  51      Otherwise add it to VISITED.  If the SSA_NAME limit has been
  52      reached, return a negative value.  Otherwise return zero.  */
  53   int next_phi (tree);
  54
  55   ~ssa_name_limit_t ();
  56 };
  57
  58 class pointer_query;
  59
  60 /* Describes a reference to an object used in an access.  */
  61 struct access_ref
  62 {
  63   /* Set the bounds of the reference to at most as many bytes
  64      as the first argument or unknown when null, and at least
  65      one when the second argument is true unless the first one
  66      is a constant zero.  */
  67   access_ref (tree = NULL_TREE, bool = false);
  68
  69   /* Return the PHI node REF refers to or null if it doesn't.  */
  70   gphi *phi () const;
  71
  72   /* Return the object to which REF refers.  */
  73   tree get_ref (vec<access_ref> *, access_ref * = NULL, int = 1,
  74                 ssa_name_limit_t * = NULL, pointer_query * = NULL) const;
  75
  76   /* Return true if OFFRNG is the constant zero.  */
  77   bool offset_zero () const
  78   {
  79     return offrng[0] == 0 && offrng[1] == 0;
  80   }
  81
  82   /* Return true if OFFRNG is bounded to a subrange of offset values
  83      valid for the largest possible object.  */
  84   bool offset_bounded () const;
  85
  86   /* Return the maximum amount of space remaining and if non-null, set
  87      argument to the minimum.  */
  88   offset_int size_remaining (offset_int * = NULL) const;
  89
  90 /* Return true if the offset and object size are in range for SIZE.  */
  91   bool offset_in_range (const offset_int &) const;
  92
  93   /* Return true if *THIS is an access to a declared object.  */
  94   bool ref_declared () const
  95   {
  96     return DECL_P (ref) && base0 && deref < 1;
  97   }
  98
  99   /* Set the size range to the maximum.  */
 100   void set_max_size_range ()
 101   {
 102     sizrng[0] = 0;
 103     sizrng[1] = wi::to_offset (max_object_size ());
 104   }
 105
 106   /* Add OFF to the offset range.  */
 107   void add_offset (const offset_int &off)
 108   {
 109     add_offset (off, off);
 110   }
 111
 112   /* Add the range [MIN, MAX] to the offset range.  */
 113   void add_offset (const offset_int &, const offset_int &);
 114
 115   /* Add the maximum representable offset to the offset range.  */
 116   void add_max_offset ()
 117   {
 118     offset_int maxoff = wi::to_offset (TYPE_MAX_VALUE (ptrdiff_type_node));
 119     add_offset (-maxoff - 1, maxoff);
 120   }
 121
 122   /* Issue an informational message describing the target of an access
 123      with the given mode.  */
 124   void inform_access (access_mode) const;
 125
 126   /* Reference to the accessed object(s).  */
 127   tree ref;
 128
 129   /* Range of byte offsets into and sizes of the object(s).  */
 130   offset_int offrng[2];
 131   offset_int sizrng[2];
 132   /* The minimum and maximum offset computed.  */
 133   offset_int offmax[2];
 134   /* Range of the bound of the access: denotes that the access
 135      is at least BNDRNG[0] bytes but no more than BNDRNG[1].
 136      For string functions the size of the actual access is
 137      further constrained by the length of the string.  */
 138   offset_int bndrng[2];
 139
 140   /* Used to fold integer expressions when called from front ends.  */
 141   tree (*eval)(tree);
 142   /* Positive when REF is dereferenced, negative when its address is
 143      taken.  */
 144   int deref;
 145   /* Set if trailing one-element arrays should be treated as flexible
 146      array members.  */
 147   bool trail1special;
 148   /* Set if valid offsets must start at zero (for declared and allocated
 149      objects but not for others referenced by pointers).  */
 150   bool base0;
 151   /* Set if REF refers to a function array parameter not declared
 152      static.  */
 153   bool parmarray;
 154 };
 155
 156 class range_query;
 157
 158 /* Queries and caches compute_objsize results.  */
 159 class pointer_query
 160 {
 161   DISABLE_COPY_AND_ASSIGN (pointer_query);
 162
 163 public:
 164   /* Type of the two-level cache object defined by clients of the class
 165      to have pointer SSA_NAMEs cached for speedy access.  */
 166   struct cache_type
 167   {
 168     /* 1-based indices into cache.  */
 169     vec<unsigned> indices;
 170     /* The cache itself.  */
 171     vec<access_ref> access_refs;
 172   };
 173
 174   /* Construct an object with the given Ranger instance and cache.  */
 175   explicit pointer_query (range_query * = NULL, cache_type * = NULL);
 176
 177   /* Retrieve the access_ref for a variable from cache if it's there.  */
 178   const access_ref* get_ref (tree, int = 1) const;
 179
 180   /* Retrieve the access_ref for a variable from cache or compute it.  */
 181   bool get_ref (tree, access_ref*, int = 1);
 182
 183   /* Add an access_ref for the SSA_NAME to the cache.  */
 184   void put_ref (tree, const access_ref&, int = 1);
 185
 186   /* Flush the cache.  */
 187   void flush_cache ();
 188
 189   /* Dump statistics and optionally cache contents to DUMP_FILE.  */
 190   void dump (FILE *, bool = false);
 191
 192   /* A Ranger instance.  May be null to use global ranges.  */
 193   range_query *rvals;
 194   /* Cache of SSA_NAMEs.  May be null to disable caching.  */
 195   cache_type *var_cache;
 196
 197   /* Cache performance counters.  */
 198   mutable unsigned hits;
 199   mutable unsigned misses;
 200   mutable unsigned failures;
 201   mutable unsigned depth;
 202   mutable unsigned max_depth;
 203 };
 204
 205 /* Describes a pair of references used in an access by built-in
 206    functions like memcpy.  */
 207 struct access_data
 208 {
 209   /* Set the access to at most MAXWRITE and MAXREAD bytes, and
 210      at least 1 when MINWRITE or MINREAD, respectively, is set.  */
 211   access_data (gimple *stmt, access_mode mode,
 212                tree maxwrite = NULL_TREE, bool minwrite = false,
 213                tree maxread = NULL_TREE, bool minread = false)
 214     : stmt (stmt), call (),
 215       dst (maxwrite, minwrite), src (maxread, minread), mode (mode) { }
 216
 217   /* Set the access to at most MAXWRITE and MAXREAD bytes, and
 218      at least 1 when MINWRITE or MINREAD, respectively, is set.  */
 219   access_data (tree expr, access_mode mode,
 220                tree maxwrite = NULL_TREE, bool minwrite = false,
 221                tree maxread = NULL_TREE, bool minread = false)
 222     : stmt (), call (expr),
 223       dst (maxwrite, minwrite), src (maxread, minread), mode (mode) { }
 224
 225   /* Access statement.  */
 226   gimple *stmt;
 227   /* Built-in function call.  */
 228   tree call;
 229   /* Destination and source of the access.  */
 230   access_ref dst, src;
 231   /* Read-only for functions like memcmp or strlen, write-only
 232      for memset, read-write for memcpy or strcat.  */
 233   access_mode mode;
 234 };
 235
 236 enum size_range_flags
 237   {
 238    /* Set to consider zero a valid range.  */
 239    SR_ALLOW_ZERO = 1,
 240    /* Set to use the largest subrange of a set of ranges as opposed
 241       to the smallest.  */
 242    SR_USE_LARGEST = 2
 243   };
 244 extern bool get_size_range (tree, tree[2], int = 0);
 245 extern bool get_size_range (range_query *, tree, gimple *, tree[2], int = 0);
 246
 247 class range_query;
 248 extern tree gimple_call_alloc_size (gimple *, wide_int[2] = NULL,
 249                                     range_query * = NULL);
 250 extern tree gimple_parm_array_size (tree, wide_int[2], bool * = NULL);
 251
 252 extern tree compute_objsize (tree, int, access_ref *, range_query * = NULL);
 253 /* Legacy/transitional API.  Should not be used in new code.  */
 254 extern tree compute_objsize (tree, int, access_ref *, pointer_query *);
 255 extern tree compute_objsize (tree, int, tree * = NULL, tree * = NULL,
 256                              range_query * = NULL);
 257
 258 #endif   // GCC_POINTER_QUERY_H