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 (t: 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 |
298 | |