gcc/pointer-query.h

   1 /* Definitions of the pointer_query and related classes.
   2
   3    Copyright (C) 2020-2022 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   /* Set if trailing one-element arrays should be treated as flexible
 145      array members.  */
 146   bool trail1special;
 147   /* Set if valid offsets must start at zero (for declared and allocated
 148      objects but not for others referenced by pointers).  */
 149   bool base0;
 150   /* Set if REF refers to a function array parameter not declared
 151      static.  */
 152   bool parmarray;
 153 };
 154
 155 class range_query;
 156
 157 /* Queries and caches compute_objsize results.  */
 158 class pointer_query
 159 {
 160   DISABLE_COPY_AND_ASSIGN (pointer_query);
 161
 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     auto_vec<unsigned> indices;
 168     /* The cache itself.  */
 169     auto_vec<access_ref> access_refs;
 170   };
 171
 172 public:
 173   /* Construct an object with the given Ranger instance.  */
 174   explicit pointer_query (range_query * = nullptr);
 175
 176   /* Retrieve the access_ref for a variable from cache if it's there.  */
 177   const access_ref* get_ref (tree, int = 1) const;
 178
 179   /* Retrieve the access_ref for a variable from cache or compute it.  */
 180   bool get_ref (tree, gimple *, access_ref*, int = 1);
 181
 182   /* Add an access_ref for the SSA_NAME to the cache.  */
 183   void put_ref (tree, const access_ref&, int = 1);
 184
 185   /* Flush the cache.  */
 186   void flush_cache ();
 187
 188   /* Dump statistics and optionally cache contents to DUMP_FILE.  */
 189   void dump (FILE *, bool = false);
 190
 191   /* A Ranger instance.  May be null to use global ranges.  */
 192   range_query *rvals;
 193
 194   /* Cache performance counters.  */
 195   mutable unsigned hits;
 196   mutable unsigned misses;
 197   mutable unsigned failures;
 198   mutable unsigned depth;
 199   mutable unsigned max_depth;
 200
 201 private:
 202   /* Cache of SSA_NAMEs.  May be null to disable caching.  */
 203   cache_type var_cache;
 204 };
 205
 206 /* Describes a pair of references used in an access by built-in
 207    functions like memcpy.  */
 208 struct access_data
 209 {
 210   /* Set the access to at most MAXWRITE and MAXREAD bytes, and
 211      at least 1 when MINWRITE or MINREAD, respectively, is set.  */
 212   access_data (range_query *, gimple *, access_mode,
 213                tree = NULL_TREE, bool = false,
 214                tree = NULL_TREE, bool = false);
 215
 216   /* Set the access to at most MAXWRITE and MAXREAD bytes, and
 217      at least 1 when MINWRITE or MINREAD, respectively, is set.  */
 218   access_data (range_query *, tree, access_mode,
 219                tree = NULL_TREE, bool = false,
 220                tree = NULL_TREE, bool = false);
 221
 222   /* Constructor helper.  */
 223   static void set_bound (offset_int[2], tree, bool, range_query *, gimple *);
 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
 232   /* Range of the bound of the access: denotes that the access is at
 233      least XXX_BNDRNG[0] bytes but no more than XXX_BNDRNG[1].  For
 234      string functions the size of the actual access is further
 235      constrained by the length of the string.  */
 236   offset_int dst_bndrng[2];
 237   offset_int src_bndrng[2];
 238
 239   /* Read-only for functions like memcmp or strlen, write-only
 240      for memset, read-write for memcpy or strcat.  */
 241   access_mode mode;
 242   /* The object size type.  */
 243   int ostype;
 244 };
 245
 246 enum size_range_flags
 247   {
 248    /* Set to consider zero a valid range.  */
 249    SR_ALLOW_ZERO = 1,
 250    /* Set to use the largest subrange of a set of ranges as opposed
 251       to the smallest.  */
 252    SR_USE_LARGEST = 2
 253   };
 254 extern bool get_size_range (tree, tree[2], int = 0);
 255 extern bool get_size_range (range_query *, tree, gimple *, tree[2], int = 0);
 256
 257 class range_query;
 258 extern tree gimple_call_alloc_size (gimple *, wide_int[2] = nullptr,
 259                                     range_query * = nullptr);
 260
 261 /* Compute the size of an object referenced by the first argument in
 262    a statement given by second argument, using Object Size Type given
 263    by third argument.  Store result in an access_ref.  */
 264 extern tree compute_objsize (tree, gimple *, int, access_ref *,
 265                              range_query * = nullptr);
 266 extern tree compute_objsize (tree, gimple *, int, access_ref *,
 267                              pointer_query *);
 268 inline tree compute_objsize (tree ptr, int ostype, access_ref *pref)
 269 {
 270   return compute_objsize (ptr, nullptr, ostype, pref, (range_query *)nullptr);
 271 }
 272
 273 /* Legacy/transitional API.  Should not be used in new code.  */
 274 extern tree compute_objsize (tree, gimple *, int, tree * = nullptr,
 275                              tree * = nullptr, range_query * = nullptr);
 276 inline tree compute_objsize (tree ptr, int ostype, tree *pdecl = nullptr,
 277                              tree *poff = nullptr, range_query *rvals = nullptr)
 278 {
 279   return compute_objsize (ptr, nullptr, ostype, pdecl, poff, rvals);
 280 }
 281
 282 /* Return the field at the constant offset.  */
 283 extern tree field_at_offset (tree, tree, HOST_WIDE_INT,
 284                              HOST_WIDE_INT * = nullptr,
 285                              HOST_WIDE_INT * = nullptr);
 286 /* Return the array at the constant offset.  */
 287 extern tree array_elt_at_offset (tree, HOST_WIDE_INT,
 288                                  HOST_WIDE_INT * = nullptr,
 289                                  HOST_WIDE_INT * = nullptr);
 290
 291 /* Helper to build an array type that can be printed.  */
 292 extern tree build_printable_array_type (tree, unsigned HOST_WIDE_INT);
 293
 294 #endif   // GCC_POINTER_QUERY_H