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