gcc/pointer-query.h

   1 /* Definitions of the pointer_query and related classes.
   2
   3    Copyright (C) 2020-2023 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.  */
  64   access_ref ();
  65
  66   /* Return the PHI node REF refers to or null if it doesn't.  */
  67   gphi *phi () const;
  68
  69   /* Merge the result for a pointer with *THIS.  */
  70   void merge_ref (vec<access_ref> *all_refs, tree, gimple *, int, bool,
  71                   ssa_name_limit_t &, pointer_query &);
  72
  73   /* Return the object to which REF refers.  */
  74   tree get_ref (vec<access_ref> *, access_ref * = nullptr, int = 1,
  75                 ssa_name_limit_t * = nullptr, pointer_query * = nullptr) const;
  76
  77   /* Return true if OFFRNG is the constant zero.  */
  78   bool offset_zero () const
  79   {
  80     return offrng[0] == 0 && offrng[1] == 0;
  81   }
  82
  83   /* Return true if OFFRNG is bounded to a subrange of offset values
  84      valid for the largest possible object.  */
  85   bool offset_bounded () const;
  86
  87   /* Return the maximum amount of space remaining and if non-null, set
  88      argument to the minimum.  */
  89   offset_int size_remaining (offset_int * = nullptr) const;
  90
  91   /* Return true if the offset and object size are in range for SIZE.  */
  92   bool offset_in_range (const offset_int &) const;
  93
  94   /* Return true if *THIS is an access to a declared object.  */
  95   bool ref_declared () const
  96   {
  97     return DECL_P (ref) && base0 && deref < 1;
  98   }
  99
 100   /* Set the size range to the maximum.  */
 101   void set_max_size_range ()
 102   {
 103     sizrng[0] = 0;
 104     sizrng[1] = wi::to_offset (max_object_size ());
 105   }
 106
 107   /* Add OFF to the offset range.  */
 108   void add_offset (const offset_int &off)
 109   {
 110     add_offset (off, off);
 111   }
 112
 113   /* Add the range [MIN, MAX] to the offset range.  */
 114   void add_offset (const offset_int &, const offset_int &);
 115
 116   /* Add the maximum representable offset to the offset range.  */
 117   void add_max_offset ()
 118   {
 119     offset_int maxoff = wi::to_offset (TYPE_MAX_VALUE (ptrdiff_type_node));
 120     add_offset (-maxoff - 1, maxoff);
 121   }
 122
 123   /* Issue an informational message describing the target of an access
 124      with the given mode.  */
 125   void inform_access (access_mode, int = 1) const;
 126
 127   /* Dump *THIS to a file.  */
 128   void dump (FILE *) const;
 129
 130   /* Reference to the accessed object(s).  */
 131   tree ref;
 132
 133   /* Range of byte offsets into and sizes of the object(s).  */
 134   offset_int offrng[2];
 135   offset_int sizrng[2];
 136   /* The minimum and maximum offset computed.  */
 137   offset_int offmax[2];
 138
 139   /* Used to fold integer expressions when called from front ends.  */
 140   tree (*eval)(tree);
 141   /* Positive when REF is dereferenced, negative when its address is
 142      taken.  */
 143   int deref;
 144   /* The following indicates if heuristics interpreted 'ref' is interpreted
 145      as (offsetted) nullptr.  */
 146   bool ref_nullptr_p;
 147   /* Set if trailing one-element arrays should be treated as flexible
 148      array members.  */
 149   bool trail1special;
 150   /* Set if valid offsets must start at zero (for declared and allocated
 151      objects but not for others referenced by pointers).  */
 152   bool base0;
 153   /* Set if REF refers to a function array parameter not declared
 154      static.  */
 155   bool parmarray;
 156 };
 157
 158 class range_query;
 159
 160 /* Queries and caches compute_objsize results.  */
 161 class pointer_query
 162 {
 163   DISABLE_COPY_AND_ASSIGN (pointer_query);
 164
 165   /* Type of the two-level cache object defined by clients of the class
 166      to have pointer SSA_NAMEs cached for speedy access.  */
 167   struct cache_type
 168   {
 169     /* 1-based indices into cache.  */
 170     auto_vec<unsigned> indices;
 171     /* The cache itself.  */
 172     auto_vec<access_ref> access_refs;
 173   };
 174
 175 public:
 176   /* Construct an object with the given Ranger instance.  */
 177   explicit pointer_query (range_query * = nullptr);
 178
 179   /* Retrieve the access_ref for a variable from cache if it's there.  */
 180   const access_ref* get_ref (tree, int = 1) const;
 181
 182   /* Retrieve the access_ref for a variable from cache or compute it.  */
 183   bool get_ref (tree, gimple *, access_ref*, int = 1);
 184
 185   /* Add an access_ref for the SSA_NAME to the cache.  */
 186   void put_ref (tree, const access_ref&, int = 1);
 187
 188   /* Flush the cache.  */
 189   void flush_cache ();
 190
 191   /* Dump statistics and optionally cache contents to DUMP_FILE.  */
 192   void dump (FILE *, bool = false);
 193
 194   /* A Ranger instance.  May be null to use global ranges.  */
 195   range_query *rvals;
 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 private:
 205   /* Cache of SSA_NAMEs.  May be null to disable caching.  */
 206   cache_type var_cache;
 207 };
 208
 209 /* Describes a pair of references used in an access by built-in
 210    functions like memcpy.  */
 211 struct access_data
 212 {
 213   /* Set the access to at most MAXWRITE and MAXREAD bytes, and
 214      at least 1 when MINWRITE or MINREAD, respectively, is set.  */
 215   access_data (range_query *, gimple *, access_mode,
 216                tree = NULL_TREE, bool = false,
 217                tree = NULL_TREE, bool = false);
 218
 219   /* Set the access to at most MAXWRITE and MAXREAD bytes, and
 220      at least 1 when MINWRITE or MINREAD, respectively, is set.  */
 221   access_data (range_query *, tree, access_mode,
 222                tree = NULL_TREE, bool = false,
 223                tree = NULL_TREE, bool = false);
 224
 225   /* Constructor helper.  */
 226   static void set_bound (offset_int[2], tree, bool, range_query *, gimple *);
 227
 228   /* Access statement.  */
 229   gimple *stmt;
 230   /* Built-in function call.  */
 231   tree call;
 232   /* Destination and source of the access.  */
 233   access_ref dst, src;
 234
 235   /* Range of the bound of the access: denotes that the access is at
 236      least XXX_BNDRNG[0] bytes but no more than XXX_BNDRNG[1].  For
 237      string functions the size of the actual access is further
 238      constrained by the length of the string.  */
 239   offset_int dst_bndrng[2];
 240   offset_int src_bndrng[2];
 241
 242   /* Read-only for functions like memcmp or strlen, write-only
 243      for memset, read-write for memcpy or strcat.  */
 244   access_mode mode;
 245   /* The object size type.  */
 246   int ostype;
 247 };
 248
 249 enum size_range_flags
 250   {
 251    /* Set to consider zero a valid range.  */
 252    SR_ALLOW_ZERO = 1,
 253    /* Set to use the largest subrange of a set of ranges as opposed
 254       to the smallest.  */
 255    SR_USE_LARGEST = 2
 256   };
 257 extern bool get_size_range (tree, tree[2], int = 0);
 258 extern bool get_size_range (range_query *, tree, gimple *, tree[2], int = 0);
 259
 260 class range_query;
 261 extern tree gimple_call_alloc_size (gimple *, wide_int[2] = nullptr,
 262                                     range_query * = nullptr);
 263
 264 /* Compute the size of an object referenced by the first argument in
 265    a statement given by second argument, using Object Size Type given
 266    by third argument.  Store result in an access_ref.  */
 267 extern tree compute_objsize (tree, gimple *, int, access_ref *,
 268                              range_query * = nullptr);
 269 extern tree compute_objsize (tree, gimple *, int, access_ref *,
 270                              pointer_query *);
 271 inline tree compute_objsize (tree ptr, int ostype, access_ref *pref)
 272 {
 273   return compute_objsize (ptr, nullptr, ostype, pref, (range_query *)nullptr);
 274 }
 275
 276 /* Legacy/transitional API.  Should not be used in new code.  */
 277 extern tree compute_objsize (tree, gimple *, int, tree * = nullptr,
 278                              tree * = nullptr, range_query * = nullptr);
 279 inline tree compute_objsize (tree ptr, int ostype, tree *pdecl = nullptr,
 280                              tree *poff = nullptr, range_query *rvals = nullptr)
 281 {
 282   return compute_objsize (ptr, nullptr, ostype, pdecl, poff, rvals);
 283 }
 284
 285 /* Return the field at the constant offset.  */
 286 extern tree field_at_offset (tree, tree, HOST_WIDE_INT,
 287                              HOST_WIDE_INT * = nullptr,
 288                              HOST_WIDE_INT * = nullptr);
 289 /* Return the array at the constant offset.  */
 290 extern tree array_elt_at_offset (tree, HOST_WIDE_INT,
 291                                  HOST_WIDE_INT * = nullptr,
 292                                  HOST_WIDE_INT * = nullptr);
 293
 294 /* Helper to build an array type that can be printed.  */
 295 extern tree build_printable_array_type (tree, unsigned HOST_WIDE_INT);
 296
 297 #endif   // GCC_POINTER_QUERY_H