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