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
ssa_name_limit_t()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. */
offset_zeroaccess_ref78 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. */
ref_declaredaccess_ref95 bool ref_declared () const
96 {
97 return DECL_P (ref) && base0 && deref < 1;
98 }
99
100 /* Set the size range to the maximum. */
set_max_size_rangeaccess_ref101 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. */
add_offsetaccess_ref108 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. */
add_max_offsetaccess_ref117 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 *);
compute_objsize(tree ptr,int ostype,access_ref * pref)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
295