1 | /* Tracking equivalence classes and constraints at a point on an execution path. |
2 | Copyright (C) 2019-2024 Free Software Foundation, Inc. |
3 | Contributed by David Malcolm <dmalcolm@redhat.com>. |
4 | |
5 | This file is part of GCC. |
6 | |
7 | GCC is free software; you can redistribute it and/or modify it |
8 | under the terms of the GNU General Public License as published by |
9 | the Free Software Foundation; either version 3, or (at your option) |
10 | any later version. |
11 | |
12 | GCC is distributed in the hope that it will be useful, but |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
15 | General Public License 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_ANALYZER_CONSTRAINT_MANAGER_H |
22 | #define GCC_ANALYZER_CONSTRAINT_MANAGER_H |
23 | |
24 | namespace ana { |
25 | |
26 | class constraint_manager; |
27 | |
28 | enum bound_kind |
29 | { |
30 | BK_LOWER, |
31 | BK_UPPER |
32 | }; |
33 | |
34 | /* One of the end-points of a range. */ |
35 | |
36 | struct bound |
37 | { |
38 | bound () : m_constant (NULL_TREE), m_closed (false) {} |
39 | bound (tree constant, bool closed) |
40 | : m_constant (constant), m_closed (closed) {} |
41 | |
42 | void ensure_closed (enum bound_kind bound_kind); |
43 | |
44 | const char * get_relation_as_str () const; |
45 | |
46 | tree m_constant; |
47 | bool m_closed; |
48 | }; |
49 | |
50 | /* A range of values, used for determining if a value has been |
51 | constrained to just one possible constant value. */ |
52 | |
53 | class range |
54 | { |
55 | public: |
56 | range () : m_lower_bound (), m_upper_bound () {} |
57 | range (const bound &lower, const bound &upper) |
58 | : m_lower_bound (lower), m_upper_bound (upper) {} |
59 | |
60 | void dump_to_pp (pretty_printer *pp) const; |
61 | void dump () const; |
62 | |
63 | tree constrained_to_single_element (); |
64 | |
65 | tristate eval_condition (enum tree_code op, |
66 | tree rhs_const) const; |
67 | bool below_lower_bound (tree rhs_const) const; |
68 | bool above_upper_bound (tree rhs_const) const; |
69 | |
70 | bool add_bound (bound b, enum bound_kind bound_kind); |
71 | bool add_bound (enum tree_code op, tree rhs_const); |
72 | |
73 | private: |
74 | bound m_lower_bound; |
75 | bound m_upper_bound; |
76 | }; |
77 | |
78 | /* A closed range of values with constant integer bounds |
79 | e.g. [3, 5] for the set {3, 4, 5}. */ |
80 | |
81 | struct bounded_range |
82 | { |
83 | bounded_range (const_tree lower, const_tree upper); |
84 | |
85 | void dump_to_pp (pretty_printer *pp, bool show_types) const; |
86 | void dump (bool show_types) const; |
87 | |
88 | json::object *to_json () const; |
89 | |
90 | bool contains_p (tree cst) const; |
91 | |
92 | bool intersects_p (const bounded_range &other, |
93 | bounded_range *out) const; |
94 | |
95 | bool operator== (const bounded_range &other) const; |
96 | bool operator!= (const bounded_range &other) const |
97 | { |
98 | return !(*this == other); |
99 | } |
100 | |
101 | static int cmp (const bounded_range &a, const bounded_range &b); |
102 | |
103 | bool singleton_p () const |
104 | { |
105 | return tree_int_cst_equal (m_lower, m_upper); |
106 | } |
107 | |
108 | tree m_lower; |
109 | tree m_upper; |
110 | |
111 | private: |
112 | static void set_json_attr (json::object *obj, const char *name, tree value); |
113 | }; |
114 | |
115 | /* A collection of bounded_range instances, suitable |
116 | for representing the ranges on a case label within a switch |
117 | statement. */ |
118 | |
119 | struct bounded_ranges |
120 | { |
121 | public: |
122 | typedef bounded_ranges key_t; |
123 | |
124 | bounded_ranges (const bounded_range &range); |
125 | bounded_ranges (const vec<bounded_range> &ranges); |
126 | bounded_ranges (enum tree_code op, tree rhs_const); |
127 | |
128 | bool operator== (const bounded_ranges &other) const; |
129 | |
130 | hashval_t get_hash () const { return m_hash; } |
131 | |
132 | void dump_to_pp (pretty_printer *pp, bool show_types) const; |
133 | void dump (bool show_types) const; |
134 | |
135 | json::value *to_json () const; |
136 | |
137 | tristate eval_condition (enum tree_code op, |
138 | tree rhs_const, |
139 | bounded_ranges_manager *mgr) const; |
140 | |
141 | bool contain_p (tree cst) const; |
142 | bool empty_p () const { return m_ranges.length () == 0; } |
143 | |
144 | static int cmp (const bounded_ranges *a, const bounded_ranges *b); |
145 | |
146 | unsigned get_count () const { return m_ranges.length (); } |
147 | const bounded_range &get_range (unsigned idx) const { return m_ranges[idx]; } |
148 | |
149 | private: |
150 | void canonicalize (); |
151 | void validate () const; |
152 | |
153 | friend class bounded_ranges_manager; |
154 | |
155 | auto_vec<bounded_range> m_ranges; |
156 | hashval_t m_hash; |
157 | }; |
158 | |
159 | } // namespace ana |
160 | |
161 | template <> struct default_hash_traits<bounded_ranges::key_t> |
162 | : public member_function_hash_traits<bounded_ranges::key_t> |
163 | { |
164 | static const bool empty_zero_p = true; |
165 | }; |
166 | |
167 | namespace ana { |
168 | |
169 | /* An object to own and consolidate bounded_ranges instances. |
170 | This also caches the mapping from switch_cfg_superedge |
171 | bounded_ranges instances, so that get_or_create_ranges_for_switch is |
172 | memoized. */ |
173 | |
174 | class bounded_ranges_manager |
175 | { |
176 | public: |
177 | ~bounded_ranges_manager (); |
178 | |
179 | const bounded_ranges * |
180 | get_or_create_ranges_for_switch (const switch_cfg_superedge *edge, |
181 | const gswitch *switch_stmt); |
182 | |
183 | const bounded_ranges *get_or_create_empty (); |
184 | const bounded_ranges *get_or_create_point (const_tree value); |
185 | const bounded_ranges *get_or_create_range (const_tree lower_bound, |
186 | const_tree upper_bound); |
187 | const bounded_ranges * |
188 | get_or_create_union (const vec <const bounded_ranges *> &others); |
189 | const bounded_ranges * |
190 | get_or_create_intersection (const bounded_ranges *a, |
191 | const bounded_ranges *b); |
192 | const bounded_ranges * |
193 | get_or_create_inverse (const bounded_ranges *other, tree type); |
194 | |
195 | void log_stats (logger *logger, bool show_objs) const; |
196 | |
197 | private: |
198 | const bounded_ranges * |
199 | create_ranges_for_switch (const switch_cfg_superedge &edge, |
200 | const gswitch *switch_stmt); |
201 | |
202 | const bounded_ranges * |
203 | make_case_label_ranges (const gswitch *switch_stmt, |
204 | tree case_label); |
205 | |
206 | const bounded_ranges *consolidate (bounded_ranges *); |
207 | |
208 | struct hash_traits_t : public typed_noop_remove<bounded_ranges *> |
209 | { |
210 | typedef bounded_ranges *key_type; |
211 | typedef bounded_ranges *value_type; |
212 | |
213 | static inline bool |
214 | equal (const key_type &k1, const key_type &k2) |
215 | { |
216 | return *k1 == *k2; |
217 | } |
218 | static inline hashval_t |
219 | hash (const key_type &k) |
220 | { |
221 | return k->get_hash (); |
222 | } |
223 | static inline bool is_empty (key_type k) { return k == NULL; } |
224 | static inline void mark_empty (key_type &k) { k = NULL; } |
225 | static inline bool is_deleted (key_type k) |
226 | { |
227 | return k == reinterpret_cast<key_type> (1); |
228 | } |
229 | |
230 | static const bool empty_zero_p = true; |
231 | }; |
232 | struct traits_t : public simple_hashmap_traits<hash_traits_t, |
233 | bounded_ranges *> |
234 | { |
235 | }; |
236 | typedef hash_map<bounded_ranges *, bounded_ranges *, traits_t> map_t; |
237 | map_t m_map; |
238 | |
239 | typedef hash_map<const switch_cfg_superedge *, |
240 | const bounded_ranges *> edge_cache_t; |
241 | edge_cache_t m_edge_cache; |
242 | }; |
243 | |
244 | /* An equivalence class within a constraint manager: a set of |
245 | svalues that are known to all be equal to each other, |
246 | together with an optional tree constant that they are equal to. */ |
247 | |
248 | class equiv_class |
249 | { |
250 | public: |
251 | equiv_class (); |
252 | equiv_class (const equiv_class &other); |
253 | |
254 | hashval_t hash () const; |
255 | bool operator== (const equiv_class &other); |
256 | |
257 | void add (const svalue *sval); |
258 | bool del (const svalue *sval); |
259 | |
260 | tree get_any_constant () const { return m_constant; } |
261 | |
262 | const svalue *get_representative () const; |
263 | |
264 | void canonicalize (); |
265 | |
266 | void print (pretty_printer *pp) const; |
267 | |
268 | json::object *to_json () const; |
269 | |
270 | bool contains_non_constant_p () const; |
271 | |
272 | /* An equivalence class can contain multiple constants (e.g. multiple |
273 | different zeroes, for different types); these are just for the last |
274 | constant added. */ |
275 | tree m_constant; |
276 | const svalue *m_cst_sval; |
277 | |
278 | // TODO: should this be a set rather than a vec? |
279 | auto_vec<const svalue *> m_vars; |
280 | }; |
281 | |
282 | /* The various kinds of constraint. */ |
283 | |
284 | enum constraint_op |
285 | { |
286 | CONSTRAINT_NE, |
287 | CONSTRAINT_LT, |
288 | CONSTRAINT_LE |
289 | }; |
290 | |
291 | const char *constraint_op_code (enum constraint_op c_op); |
292 | |
293 | /* An ID for an equiv_class within a constraint_manager. Internally, this |
294 | is an index into a vector of equiv_class * within the constraint_manager. */ |
295 | |
296 | class equiv_class_id |
297 | { |
298 | public: |
299 | static equiv_class_id null () { return equiv_class_id (-1); } |
300 | |
301 | equiv_class_id (unsigned idx) : m_idx (idx) {} |
302 | const equiv_class &get_obj (const constraint_manager &cm) const; |
303 | equiv_class &get_obj (constraint_manager &cm) const; |
304 | |
305 | bool operator== (const equiv_class_id &other) const |
306 | { |
307 | return m_idx == other.m_idx; |
308 | } |
309 | bool operator!= (const equiv_class_id &other) const |
310 | { |
311 | return m_idx != other.m_idx; |
312 | } |
313 | |
314 | bool null_p () const { return m_idx == -1; } |
315 | |
316 | static equiv_class_id from_int (int idx) { return equiv_class_id (idx); } |
317 | int as_int () const { return m_idx; } |
318 | |
319 | void print (pretty_printer *pp) const; |
320 | |
321 | void update_for_removal (equiv_class_id other) |
322 | { |
323 | if (m_idx > other.m_idx) |
324 | m_idx--; |
325 | } |
326 | |
327 | int m_idx; |
328 | }; |
329 | |
330 | /* A relationship between two equivalence classes in a constraint_manager. */ |
331 | |
332 | class constraint |
333 | { |
334 | public: |
335 | constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs) |
336 | : m_lhs (lhs), m_op (c_op), m_rhs (rhs) |
337 | { |
338 | gcc_assert (!lhs.null_p ()); |
339 | gcc_assert (!rhs.null_p ()); |
340 | } |
341 | |
342 | void print (pretty_printer *pp, const constraint_manager &cm) const; |
343 | |
344 | json::object *to_json () const; |
345 | |
346 | hashval_t hash () const; |
347 | bool operator== (const constraint &other) const; |
348 | |
349 | /* Is this an ordering, rather than a "!=". */ |
350 | bool is_ordering_p () const |
351 | { |
352 | return m_op != CONSTRAINT_NE; |
353 | } |
354 | |
355 | bool implied_by (const constraint &other, |
356 | const constraint_manager &cm) const; |
357 | |
358 | equiv_class_id m_lhs; |
359 | enum constraint_op m_op; |
360 | equiv_class_id m_rhs; |
361 | }; |
362 | |
363 | /* An abstract base class for use with constraint_manager::for_each_fact. */ |
364 | |
365 | class fact_visitor |
366 | { |
367 | public: |
368 | virtual ~fact_visitor () {} |
369 | virtual void on_fact (const svalue *lhs, |
370 | enum tree_code, |
371 | const svalue *rhs) = 0; |
372 | virtual void on_ranges (const svalue *lhs, |
373 | const bounded_ranges *ranges) = 0; |
374 | }; |
375 | |
376 | class bounded_ranges_constraint |
377 | { |
378 | public: |
379 | bounded_ranges_constraint (equiv_class_id ec_id, |
380 | const bounded_ranges *ranges) |
381 | : m_ec_id (ec_id), m_ranges (ranges) |
382 | { |
383 | } |
384 | |
385 | void print (pretty_printer *pp, const constraint_manager &cm) const; |
386 | |
387 | json::object *to_json () const; |
388 | |
389 | bool operator== (const bounded_ranges_constraint &other) const; |
390 | bool operator!= (const bounded_ranges_constraint &other) const |
391 | { |
392 | return !(*this == other); |
393 | } |
394 | |
395 | void add_to_hash (inchash::hash *hstate) const; |
396 | |
397 | equiv_class_id m_ec_id; |
398 | const bounded_ranges *m_ranges; |
399 | }; |
400 | |
401 | /* A collection of equivalence classes and constraints on them. |
402 | |
403 | Given N svalues, this can be thought of as representing a subset of |
404 | N-dimensional space. When we call add_constraint, |
405 | we are effectively taking an intersection with that constraint. */ |
406 | |
407 | class constraint_manager |
408 | { |
409 | public: |
410 | constraint_manager (region_model_manager *mgr) : m_mgr (mgr) {} |
411 | constraint_manager (const constraint_manager &other); |
412 | virtual ~constraint_manager () {} |
413 | |
414 | constraint_manager& operator= (const constraint_manager &other); |
415 | |
416 | hashval_t hash () const; |
417 | bool operator== (const constraint_manager &other) const; |
418 | bool operator!= (const constraint_manager &other) const |
419 | { |
420 | return !(*this == other); |
421 | } |
422 | |
423 | void print (pretty_printer *pp) const; |
424 | void dump_to_pp (pretty_printer *pp, bool multiline) const; |
425 | void dump (FILE *fp) const; |
426 | void dump () const; |
427 | |
428 | json::object *to_json () const; |
429 | |
430 | const equiv_class &get_equiv_class_by_index (unsigned idx) const |
431 | { |
432 | return *m_equiv_classes[idx]; |
433 | } |
434 | equiv_class &get_equiv_class_by_index (unsigned idx) |
435 | { |
436 | return *m_equiv_classes[idx]; |
437 | } |
438 | |
439 | equiv_class &get_equiv_class (const svalue *sval) |
440 | { |
441 | equiv_class_id ec_id = get_or_add_equiv_class (sval); |
442 | return ec_id.get_obj (cm&: *this); |
443 | } |
444 | |
445 | bool add_constraint (const svalue *lhs, |
446 | enum tree_code op, |
447 | const svalue *rhs); |
448 | |
449 | bool add_constraint (equiv_class_id lhs_ec_id, |
450 | enum tree_code op, |
451 | equiv_class_id rhs_ec_id); |
452 | |
453 | void add_unknown_constraint (equiv_class_id lhs_ec_id, |
454 | enum tree_code op, |
455 | equiv_class_id rhs_ec_id); |
456 | |
457 | bool add_bounded_ranges (const svalue *sval, |
458 | const bounded_ranges *ranges); |
459 | |
460 | bool get_equiv_class_by_svalue (const svalue *sval, |
461 | equiv_class_id *out) const; |
462 | bool sval_constrained_p (const svalue *sval) const; |
463 | equiv_class_id get_or_add_equiv_class (const svalue *sval); |
464 | tristate eval_condition (equiv_class_id lhs, |
465 | enum tree_code op, |
466 | equiv_class_id rhs) const; |
467 | tristate eval_condition (equiv_class_id lhs_ec, |
468 | enum tree_code op, |
469 | tree rhs_const) const; |
470 | tristate eval_condition (const svalue *lhs, |
471 | enum tree_code op, |
472 | const svalue *rhs) const; |
473 | range get_ec_bounds (equiv_class_id ec_id) const; |
474 | |
475 | /* PurgeCriteria should have: |
476 | bool should_purge_p (const svalue *sval) const. */ |
477 | template <typename PurgeCriteria> |
478 | void purge (const PurgeCriteria &p, purge_stats *stats); |
479 | |
480 | void on_liveness_change (const svalue_set &live_svalues, |
481 | const region_model *model); |
482 | void purge_state_involving (const svalue *sval); |
483 | |
484 | void canonicalize (); |
485 | |
486 | static void merge (const constraint_manager &cm_a, |
487 | const constraint_manager &cm_b, |
488 | constraint_manager *out); |
489 | |
490 | void for_each_fact (fact_visitor *) const; |
491 | |
492 | void validate () const; |
493 | |
494 | bounded_ranges_manager *get_range_manager () const; |
495 | |
496 | bool replay_call_summary (call_summary_replay &r, |
497 | const constraint_manager &summary); |
498 | |
499 | auto_delete_vec<equiv_class> m_equiv_classes; |
500 | auto_vec<constraint> m_constraints; |
501 | auto_vec<bounded_ranges_constraint> m_bounded_ranges_constraints; |
502 | |
503 | private: |
504 | void add_constraint_internal (equiv_class_id lhs_id, |
505 | enum constraint_op c_op, |
506 | equiv_class_id rhs_id); |
507 | bool impossible_derived_conditions_p (const svalue *lhs, |
508 | const svalue *rhs) const; |
509 | |
510 | region_model_manager *m_mgr; |
511 | }; |
512 | |
513 | } // namespace ana |
514 | |
515 | #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */ |
516 | |