Branch data Line data Source code
1 : : /* Definitions of the pointer_query and related classes.
2 : :
3 : : Copyright (C) 2020-2024 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 : 11041584 : ssa_name_limit_t ()
38 : 11041584 : : visited (),
39 : 11041584 : 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 : 102476 : bool ref_declared () const
96 : : {
97 : 102476 : return DECL_P (ref) && base0 && deref < 1;
98 : : }
99 : :
100 : : /* Set the size range to the maximum. */
101 : 3024417 : void set_max_size_range ()
102 : : {
103 : 3024417 : sizrng[0] = 0;
104 : 3024417 : sizrng[1] = wi::to_offset (max_object_size ());
105 : 3024417 : }
106 : :
107 : : /* Add OFF to the offset range. */
108 : 3001430 : void add_offset (const offset_int &off)
109 : : {
110 : 3001430 : 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 : 387710 : void add_max_offset ()
118 : : {
119 : 387710 : offset_int maxoff = wi::to_offset (TYPE_MAX_VALUE (ptrdiff_type_node));
120 : 387710 : add_offset (-maxoff - 1, maxoff);
121 : 387710 : }
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 : 24861688 : 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 : 12430844 : 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 : 105754 : inline tree compute_objsize (tree ptr, int ostype, access_ref *pref)
272 : : {
273 : 105754 : 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
|
