Branch data Line data Source code
1 : : /* Tracking equivalence classes and constraints at a point on an execution path.
2 : : Copyright (C) 2019-2026 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 class bound_kind
29 : : {
30 : : lower,
31 : : upper
32 : : };
33 : :
34 : : /* One of the end-points of a range. */
35 : :
36 : : struct bound
37 : : {
38 : 16866 : bound () : m_constant (NULL_TREE), m_closed (false) {}
39 : 16945 : bound (tree constant, bool closed)
40 : 16901 : : 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 : 16866 : range () : m_lower_bound (), m_upper_bound () {}
57 : 112 : range (const bound &lower, const bound &upper)
58 : 112 : : 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 : : std::unique_ptr<json::object> to_json () const;
89 : :
90 : : std::unique_ptr<text_art::widget>
91 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
92 : :
93 : : bool contains_p (tree cst) const;
94 : :
95 : : bool intersects_p (const bounded_range &other,
96 : : bounded_range *out) const;
97 : :
98 : : bool operator== (const bounded_range &other) const;
99 : 53278 : bool operator!= (const bounded_range &other) const
100 : : {
101 : 53278 : return !(*this == other);
102 : : }
103 : :
104 : : static int cmp (const bounded_range &a, const bounded_range &b);
105 : :
106 : 7136 : bool singleton_p () const
107 : : {
108 : 7136 : return tree_int_cst_equal (m_lower, m_upper);
109 : : }
110 : :
111 : : tree m_lower;
112 : : tree m_upper;
113 : :
114 : : private:
115 : : static void set_json_attr (json::object &obj, const char *name, tree value);
116 : : };
117 : :
118 : : /* A collection of bounded_range instances, suitable
119 : : for representing the ranges on a case label within a switch
120 : : statement. */
121 : :
122 : 12138 : struct bounded_ranges
123 : : {
124 : : public:
125 : : typedef bounded_ranges key_t;
126 : :
127 : : bounded_ranges (const bounded_range &range);
128 : : bounded_ranges (const vec<bounded_range> &ranges);
129 : : bounded_ranges (enum tree_code op, tree rhs_const);
130 : :
131 : : bool operator== (const bounded_ranges &other) const;
132 : :
133 : 89062 : hashval_t get_hash () const { return m_hash; }
134 : :
135 : : void dump_to_pp (pretty_printer *pp, bool show_types) const;
136 : : void dump (bool show_types) const;
137 : :
138 : : std::unique_ptr<json::value> to_json () const;
139 : :
140 : : void add_to_dump_widget (text_art::tree_widget &parent,
141 : : const text_art::dump_widget_info &dwi) const;
142 : :
143 : : tristate eval_condition (enum tree_code op,
144 : : tree rhs_const,
145 : : bounded_ranges_manager *mgr) const;
146 : :
147 : : bool contain_p (tree cst) const;
148 : 12350 : bool empty_p () const { return m_ranges.length () == 0; }
149 : :
150 : : static int cmp (const bounded_ranges *a, const bounded_ranges *b);
151 : :
152 : 14615 : unsigned get_count () const { return m_ranges.length (); }
153 : 19309 : const bounded_range &get_range (unsigned idx) const { return m_ranges[idx]; }
154 : :
155 : : private:
156 : : void canonicalize ();
157 : : void validate () const;
158 : :
159 : : friend class bounded_ranges_manager;
160 : :
161 : : auto_vec<bounded_range> m_ranges;
162 : : hashval_t m_hash;
163 : : };
164 : :
165 : : } // namespace ana
166 : :
167 : : template <> struct default_hash_traits<bounded_ranges::key_t>
168 : : : public member_function_hash_traits<bounded_ranges::key_t>
169 : : {
170 : : static const bool empty_zero_p = true;
171 : : };
172 : :
173 : : namespace ana {
174 : :
175 : : /* An object to own and consolidate bounded_ranges instances. */
176 : :
177 : : class bounded_ranges_manager
178 : : {
179 : : public:
180 : : ~bounded_ranges_manager ();
181 : :
182 : : const bounded_ranges *get_or_create_empty ();
183 : : const bounded_ranges *get_or_create_point (const_tree value);
184 : : const bounded_ranges *get_or_create_range (const_tree lower_bound,
185 : : const_tree upper_bound);
186 : : const bounded_ranges *
187 : : get_or_create_union (const vec <const bounded_ranges *> &others);
188 : : const bounded_ranges *
189 : : get_or_create_intersection (const bounded_ranges *a,
190 : : const bounded_ranges *b);
191 : : const bounded_ranges *
192 : : get_or_create_inverse (const bounded_ranges *other, tree type);
193 : :
194 : : void log_stats (logger *logger, bool show_objs) const;
195 : :
196 : : const bounded_ranges *
197 : : make_case_label_ranges (const gswitch *switch_stmt,
198 : : tree case_label);
199 : :
200 : : private:
201 : : const bounded_ranges *consolidate (bounded_ranges *);
202 : :
203 : : struct hash_traits_t : public typed_noop_remove<bounded_ranges *>
204 : : {
205 : : typedef bounded_ranges *key_type;
206 : : typedef bounded_ranges *value_type;
207 : :
208 : : static inline bool
209 : 69378 : equal (const key_type &k1, const key_type &k2)
210 : : {
211 : 69378 : return *k1 == *k2;
212 : : }
213 : : static inline hashval_t
214 : 73811 : hash (const key_type &k)
215 : : {
216 : 73811 : return k->get_hash ();
217 : : }
218 : : static inline bool is_empty (key_type k) { return k == nullptr; }
219 : 0 : static inline void mark_empty (key_type &k) { k = nullptr; }
220 : 84046 : static inline bool is_deleted (key_type k)
221 : : {
222 : 84046 : return k == reinterpret_cast<key_type> (1);
223 : : }
224 : :
225 : : static const bool empty_zero_p = true;
226 : : };
227 : : struct traits_t : public simple_hashmap_traits<hash_traits_t,
228 : : bounded_ranges *>
229 : : {
230 : : };
231 : : typedef hash_map<bounded_ranges *, bounded_ranges *, traits_t> map_t;
232 : : map_t m_map;
233 : : };
234 : :
235 : : /* An equivalence class within a constraint manager: a set of
236 : : svalues that are known to all be equal to each other,
237 : : together with an optional tree constant that they are equal to. */
238 : :
239 : 13547377 : class equiv_class
240 : : {
241 : : public:
242 : : equiv_class ();
243 : : equiv_class (const equiv_class &other);
244 : :
245 : : hashval_t hash () const;
246 : : bool operator== (const equiv_class &other) const;
247 : :
248 : : void add (const svalue *sval);
249 : : bool del (const svalue *sval);
250 : :
251 : 728311 : tree get_any_constant () const { return m_constant; }
252 : :
253 : : const svalue *get_representative () const;
254 : :
255 : : void canonicalize ();
256 : :
257 : : void print (pretty_printer *pp) const;
258 : :
259 : : std::unique_ptr<json::object> to_json () const;
260 : :
261 : : std::unique_ptr<text_art::tree_widget>
262 : : make_dump_widget (const text_art::dump_widget_info &dwi,
263 : : unsigned id) const;
264 : :
265 : : bool contains_non_constant_p () const;
266 : :
267 : : /* An equivalence class can contain multiple constants (e.g. multiple
268 : : different zeroes, for different types); these are just for the last
269 : : constant added. */
270 : : tree m_constant;
271 : : const svalue *m_cst_sval;
272 : :
273 : : // TODO: should this be a set rather than a vec?
274 : : auto_vec<const svalue *> m_vars;
275 : : };
276 : :
277 : : /* The various kinds of constraint. */
278 : :
279 : : enum constraint_op
280 : : {
281 : : CONSTRAINT_NE,
282 : : CONSTRAINT_LT,
283 : : CONSTRAINT_LE
284 : : };
285 : :
286 : : const char *constraint_op_code (enum constraint_op c_op);
287 : :
288 : : /* An ID for an equiv_class within a constraint_manager. Internally, this
289 : : is an index into a vector of equiv_class * within the constraint_manager. */
290 : :
291 : : class equiv_class_id
292 : : {
293 : : public:
294 : 3265241 : static equiv_class_id null () { return equiv_class_id (-1); }
295 : :
296 : 12562931 : equiv_class_id (unsigned idx) : m_idx (idx) {}
297 : : const equiv_class &get_obj (const constraint_manager &cm) const;
298 : : equiv_class &get_obj (constraint_manager &cm) const;
299 : :
300 : 5961881 : bool operator== (const equiv_class_id &other) const
301 : : {
302 : 3590891 : return m_idx == other.m_idx;
303 : : }
304 : 2307801 : bool operator!= (const equiv_class_id &other) const
305 : : {
306 : 2307801 : return m_idx != other.m_idx;
307 : : }
308 : :
309 : 10434488 : bool null_p () const { return m_idx == -1; }
310 : :
311 : 0 : static equiv_class_id from_int (int idx) { return equiv_class_id (idx); }
312 : 24816952 : int as_int () const { return m_idx; }
313 : :
314 : : void print (pretty_printer *pp) const;
315 : :
316 : 437414 : void update_for_removal (equiv_class_id other)
317 : : {
318 : 251462 : if (m_idx > other.m_idx)
319 : 46046 : m_idx--;
320 : : }
321 : :
322 : : int m_idx;
323 : : };
324 : :
325 : : /* A relationship between two equivalence classes in a constraint_manager. */
326 : :
327 : : class constraint
328 : : {
329 : : public:
330 : 157852 : constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs)
331 : 157852 : : m_lhs (lhs), m_op (c_op), m_rhs (rhs)
332 : : {
333 : 157852 : gcc_assert (!lhs.null_p ());
334 : 157852 : gcc_assert (!rhs.null_p ());
335 : 157852 : }
336 : :
337 : : void print (pretty_printer *pp, const constraint_manager &cm) const;
338 : :
339 : : std::unique_ptr<json::object> to_json () const;
340 : :
341 : : std::unique_ptr<text_art::widget>
342 : : make_dump_widget (const text_art::dump_widget_info &dwi,
343 : : const constraint_manager &cm) const;
344 : :
345 : : hashval_t hash () const;
346 : : bool operator== (const constraint &other) const;
347 : :
348 : : /* Is this an ordering, rather than a "!=". */
349 : 9068 : bool is_ordering_p () const
350 : : {
351 : 9068 : return m_op != CONSTRAINT_NE;
352 : : }
353 : :
354 : : bool implied_by (const constraint &other,
355 : : const constraint_manager &cm) const;
356 : :
357 : : equiv_class_id m_lhs;
358 : : enum constraint_op m_op;
359 : : equiv_class_id m_rhs;
360 : : };
361 : :
362 : : /* An abstract base class for use with constraint_manager::for_each_fact. */
363 : :
364 : 41224 : class fact_visitor
365 : : {
366 : : public:
367 : 41224 : virtual ~fact_visitor () {}
368 : : virtual void on_fact (const svalue *lhs,
369 : : enum tree_code,
370 : : const svalue *rhs) = 0;
371 : : virtual void on_ranges (const svalue *lhs,
372 : : const bounded_ranges *ranges) = 0;
373 : : };
374 : :
375 : : class bounded_ranges_constraint
376 : : {
377 : : public:
378 : 1451 : bounded_ranges_constraint (equiv_class_id ec_id,
379 : : const bounded_ranges *ranges)
380 : 1451 : : m_ec_id (ec_id), m_ranges (ranges)
381 : : {
382 : : }
383 : :
384 : : void print (pretty_printer *pp, const constraint_manager &cm) const;
385 : :
386 : : std::unique_ptr<json::object> to_json () const;
387 : :
388 : : bool operator== (const bounded_ranges_constraint &other) const;
389 : 5066 : bool operator!= (const bounded_ranges_constraint &other) const
390 : : {
391 : 5066 : return !(*this == other);
392 : : }
393 : :
394 : : void add_to_hash (inchash::hash *hstate) const;
395 : :
396 : : std::unique_ptr<text_art::tree_widget>
397 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
398 : :
399 : : equiv_class_id m_ec_id;
400 : : const bounded_ranges *m_ranges;
401 : : };
402 : :
403 : : /* A collection of equivalence classes and constraints on them.
404 : :
405 : : Given N svalues, this can be thought of as representing a subset of
406 : : N-dimensional space. When we call add_constraint,
407 : : we are effectively taking an intersection with that constraint. */
408 : :
409 : : class constraint_manager
410 : : {
411 : : public:
412 : 369219 : constraint_manager (region_model_manager *mgr) : m_mgr (mgr) {}
413 : : constraint_manager (const constraint_manager &other);
414 : 7217016 : virtual ~constraint_manager () {}
415 : :
416 : : constraint_manager& operator= (const constraint_manager &other);
417 : :
418 : : hashval_t hash () const;
419 : : bool operator== (const constraint_manager &other) const;
420 : 402909 : bool operator!= (const constraint_manager &other) const
421 : : {
422 : 402909 : return !(*this == other);
423 : : }
424 : :
425 : : void print (pretty_printer *pp) const;
426 : : void dump_to_pp (pretty_printer *pp, bool multiline) const;
427 : : void dump (FILE *fp) const;
428 : : void dump () const;
429 : :
430 : : std::unique_ptr<json::object> to_json () const;
431 : :
432 : : std::unique_ptr<text_art::tree_widget>
433 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
434 : :
435 : 1409068 : const equiv_class &get_equiv_class_by_index (unsigned idx) const
436 : : {
437 : 1409068 : return *m_equiv_classes[idx];
438 : : }
439 : 141241 : equiv_class &get_equiv_class_by_index (unsigned idx)
440 : : {
441 : 141241 : return *m_equiv_classes[idx];
442 : : }
443 : :
444 : 32661 : equiv_class &get_equiv_class (const svalue *sval)
445 : : {
446 : 32661 : equiv_class_id ec_id = get_or_add_equiv_class (sval);
447 : 32661 : return ec_id.get_obj (*this);
448 : : }
449 : :
450 : : bool add_constraint (const svalue *lhs,
451 : : enum tree_code op,
452 : : const svalue *rhs);
453 : :
454 : : bool add_constraint (equiv_class_id lhs_ec_id,
455 : : enum tree_code op,
456 : : equiv_class_id rhs_ec_id);
457 : :
458 : : void add_unknown_constraint (equiv_class_id lhs_ec_id,
459 : : enum tree_code op,
460 : : equiv_class_id rhs_ec_id);
461 : :
462 : : bool add_bounded_ranges (const svalue *sval,
463 : : const bounded_ranges *ranges);
464 : :
465 : : bool get_equiv_class_by_svalue (const svalue *sval,
466 : : equiv_class_id *out) const;
467 : : bool sval_constrained_p (const svalue *sval) const;
468 : : equiv_class_id get_or_add_equiv_class (const svalue *sval);
469 : : tristate eval_condition (equiv_class_id lhs,
470 : : enum tree_code op,
471 : : equiv_class_id rhs) const;
472 : : tristate eval_condition (equiv_class_id lhs_ec,
473 : : enum tree_code op,
474 : : tree rhs_const) const;
475 : : tristate eval_condition (const svalue *lhs,
476 : : enum tree_code op,
477 : : const svalue *rhs) const;
478 : : range get_ec_bounds (equiv_class_id ec_id) const;
479 : :
480 : : /* PurgeCriteria should have:
481 : : bool should_purge_p (const svalue *sval) const. */
482 : : template <typename PurgeCriteria>
483 : : void purge (const PurgeCriteria &p, purge_stats *stats);
484 : :
485 : : void on_liveness_change (const svalue_set &live_svalues,
486 : : const region_model *model);
487 : : void purge_state_involving (const svalue *sval);
488 : :
489 : : void canonicalize ();
490 : :
491 : : static void merge (const constraint_manager &cm_a,
492 : : const constraint_manager &cm_b,
493 : : constraint_manager *out);
494 : :
495 : : void for_each_fact (fact_visitor *) const;
496 : :
497 : : void validate () const;
498 : :
499 : : bounded_ranges_manager *get_range_manager () const;
500 : :
501 : : bool replay_call_summary (call_summary_replay &r,
502 : : const constraint_manager &summary);
503 : :
504 : : auto_delete_vec<equiv_class> m_equiv_classes;
505 : : auto_vec<constraint> m_constraints;
506 : : auto_vec<bounded_ranges_constraint> m_bounded_ranges_constraints;
507 : :
508 : : private:
509 : : void add_constraint_internal (equiv_class_id lhs_id,
510 : : enum constraint_op c_op,
511 : : equiv_class_id rhs_id);
512 : : bool impossible_derived_conditions_p (const svalue *lhs,
513 : : const svalue *rhs) const;
514 : :
515 : : region_model_manager *m_mgr;
516 : : };
517 : :
518 : : } // namespace ana
519 : :
520 : : #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */
|
