GCC Middle and Back End API Reference
pointer-query.h
Go to the documentation of this file.
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
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. */
34
35public:
36
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
56};
57
58class pointer_query;
59
60/* Describes a reference to an object used in an access. */
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,
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. */
102 {
103 sizrng[0] = 0;
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. */
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). */
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. */
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. */
147 /* Set if trailing one-element arrays should be treated as flexible
148 array members. */
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. */
156};
157
158class range_query;
159
160/* Queries and caches compute_objsize results. */
162{
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. */
168 {
169 /* 1-based indices into cache. */
171 /* The cache itself. */
173 };
174
175public:
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. */
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
204private:
205 /* Cache of SSA_NAMEs. May be null to disable caching. */
207};
208
209/* Describes a pair of references used in an access by built-in
210 functions like memcpy. */
212{
213 /* Set the access to at most MAXWRITE and MAXREAD bytes, and
214 at least 1 when MINWRITE or MINREAD, respectively, is set. */
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. */
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. */
230 /* Built-in function call. */
232 /* Destination and source of the access. */
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. */
245 /* The object size type. */
247};
248
250 {
251 /* Set to consider zero a valid range. */
253 /* Set to use the largest subrange of a set of ranges as opposed
254 to the smallest. */
256 };
257extern bool get_size_range (tree, tree[2], int = 0);
258extern bool get_size_range (range_query *, tree, gimple *, tree[2], int = 0);
259
260class range_query;
261extern 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. */
267extern tree compute_objsize (tree, gimple *, int, access_ref *,
268 range_query * = nullptr);
269extern tree compute_objsize (tree, gimple *, int, access_ref *,
270 pointer_query *);
271inline 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. */
277extern tree compute_objsize (tree, gimple *, int, tree * = nullptr,
278 tree * = nullptr, range_query * = nullptr);
279inline 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. */
286extern 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. */
290extern 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. */
295extern tree build_printable_array_type (tree, unsigned HOST_WIDE_INT);
296
297#endif // GCC_POINTER_QUERY_H
Definition vec.h:1656
Definition pointer-query.h:162
range_query * rvals
Definition pointer-query.h:195
unsigned depth
Definition pointer-query.h:201
void dump(FILE *, bool=false)
Definition pointer-query.cc:1577
const access_ref * get_ref(tree, int=1) const
Definition pointer-query.cc:1460
unsigned max_depth
Definition pointer-query.h:202
unsigned hits
Definition pointer-query.h:198
pointer_query(range_query *=nullptr)
Definition pointer-query.cc:1449
unsigned misses
Definition pointer-query.h:199
void put_ref(tree, const access_ref &, int=1)
Definition pointer-query.cc:1529
unsigned failures
Definition pointer-query.h:200
DISABLE_COPY_AND_ASSIGN(pointer_query)
cache_type var_cache
Definition pointer-query.h:206
void flush_cache()
Definition pointer-query.cc:1568
Definition value-query.h:55
Definition pointer-query.h:28
int next_phi(tree)
Definition pointer-query.cc:1420
unsigned ssa_def_max
Definition pointer-query.h:30
bool next()
Definition pointer-query.cc:1404
bool visit_phi(tree)
Definition pointer-query.cc:1382
bitmap visited
Definition pointer-query.h:29
~ssa_name_limit_t()
Definition pointer-query.cc:1440
DISABLE_COPY_AND_ASSIGN(ssa_name_limit_t)
ssa_name_limit_t()
Definition pointer-query.h:37
void leave_phi(tree)
Definition pointer-query.cc:1394
class bitmap_head * bitmap
Definition coretypes.h:51
union tree_node * tree
Definition coretypes.h:97
static enum reg_class * pref
Definition ira-costs.cc:94
tree_to_offset_ref to_offset(const_tree)
Definition tree.h:6358
size_range_flags
Definition pointer-query.h:250
@ SR_USE_LARGEST
Definition pointer-query.h:255
@ SR_ALLOW_ZERO
Definition pointer-query.h:252
tree array_elt_at_offset(tree, HOST_WIDE_INT, HOST_WIDE_INT *=nullptr, HOST_WIDE_INT *=nullptr)
Definition pointer-query.cc:2543
tree field_at_offset(tree, tree, HOST_WIDE_INT, HOST_WIDE_INT *=nullptr, HOST_WIDE_INT *=nullptr)
Definition pointer-query.cc:2421
tree gimple_call_alloc_size(gimple *, wide_int[2]=nullptr, range_query *=nullptr)
Definition pointer-query.cc:449
tree build_printable_array_type(tree, unsigned HOST_WIDE_INT)
Definition pointer-query.cc:2588
tree compute_objsize(tree, gimple *, int, access_ref *, range_query *=nullptr)
Definition pointer-query.cc:2381
bool get_size_range(tree, tree[2], int=0)
Definition pointer-query.cc:436
Definition pointer-query.h:212
static void set_bound(offset_int[2], tree, bool, range_query *, gimple *)
Definition pointer-query.cc:1359
access_ref dst
Definition pointer-query.h:233
gimple * stmt
Definition pointer-query.h:229
offset_int dst_bndrng[2]
Definition pointer-query.h:239
tree call
Definition pointer-query.h:231
access_ref src
Definition pointer-query.h:233
int ostype
Definition pointer-query.h:246
access_data(range_query *, gimple *, access_mode, tree=NULL_TREE, bool=false, tree=NULL_TREE, bool=false)
Definition pointer-query.cc:1332
offset_int src_bndrng[2]
Definition pointer-query.h:240
access_mode mode
Definition pointer-query.h:244
Definition pointer-query.h:62
void add_offset(const offset_int &off)
Definition pointer-query.h:108
int deref
Definition pointer-query.h:143
offset_int sizrng[2]
Definition pointer-query.h:135
void set_max_size_range()
Definition pointer-query.h:101
bool ref_declared() const
Definition pointer-query.h:95
bool trail1special
Definition pointer-query.h:149
void add_max_offset()
Definition pointer-query.h:117
bool offset_zero() const
Definition pointer-query.h:78
tree(* eval)(tree)
Definition pointer-query.h:140
bool parmarray
Definition pointer-query.h:155
void inform_access(access_mode, int=1) const
Definition pointer-query.cc:1021
gphi * phi() const
Definition pointer-query.cc:617
tree ref
Definition pointer-query.h:131
bool offset_bounded() const
Definition builtins.cc:12388
bool base0
Definition pointer-query.h:152
offset_int offrng[2]
Definition pointer-query.h:134
offset_int offmax[2]
Definition pointer-query.h:137
bool ref_nullptr_p
Definition pointer-query.h:146
tree get_ref(vec< access_ref > *, access_ref *=nullptr, int=1, ssa_name_limit_t *=nullptr, pointer_query *=nullptr) const
Definition pointer-query.cc:739
bool offset_in_range(const offset_int &) const
Definition pointer-query.cc:924
void dump(FILE *) const
Definition pointer-query.cc:1276
void merge_ref(vec< access_ref > *all_refs, tree, gimple *, int, bool, ssa_name_limit_t &, pointer_query &)
Definition pointer-query.cc:635
access_ref()
Definition pointer-query.cc:603
offset_int size_remaining(offset_int *=nullptr) const
Definition pointer-query.cc:860
Definition gimple.h:225
Definition gimple.h:462
Definition pointer-query.h:168
auto_vec< unsigned > indices
Definition pointer-query.h:170
auto_vec< access_ref > access_refs
Definition pointer-query.h:172
Definition vec.h:450
tree max_object_size(void)
Definition tree.cc:14958
#define TYPE_MAX_VALUE(NODE)
Definition tree.h:2549
access_mode
Definition tree.h:5846
#define ptrdiff_type_node
Definition tree.h:4506
#define NULL_TREE
Definition tree.h:317
#define DECL_P(NODE)
Definition tree.h:231