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 16964 : bound () : m_constant (NULL_TREE), m_closed (false) {}
39 17071 : bound (tree constant, bool closed)
40 17027 : : 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 16964 : 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 53377 : bool operator!= (const bounded_range &other) const
100 : {
101 53377 : return !(*this == other);
102 : }
103 :
104 : static int cmp (const bounded_range &a, const bounded_range &b);
105 :
106 7330 : bool singleton_p () const
107 : {
108 7330 : 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 12159 : 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 89273 : 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 12358 : bool empty_p () const { return m_ranges.length () == 0; }
149 :
150 : static int cmp (const bounded_ranges *a, const bounded_ranges *b);
151 :
152 14631 : unsigned get_count () const { return m_ranges.length (); }
153 19323 : 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 69528 : equal (const key_type &k1, const key_type &k2)
210 : {
211 69528 : return *k1 == *k2;
212 : }
213 : static inline hashval_t
214 73981 : hash (const key_type &k)
215 : {
216 73981 : 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 84242 : static inline bool is_deleted (key_type k)
221 : {
222 84242 : 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 13501829 : 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 727956 : 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 3268163 : static equiv_class_id null () { return equiv_class_id (-1); }
295 :
296 12570296 : 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 5935919 : bool operator== (const equiv_class_id &other) const
301 : {
302 3576772 : return m_idx == other.m_idx;
303 : }
304 2308804 : bool operator!= (const equiv_class_id &other) const
305 : {
306 2308804 : return m_idx != other.m_idx;
307 : }
308 :
309 10403687 : 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 24823254 : int as_int () const { return m_idx; }
313 :
314 : void print (pretty_printer *pp) const;
315 :
316 437256 : void update_for_removal (equiv_class_id other)
317 : {
318 251297 : if (m_idx > other.m_idx)
319 45873 : 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 157715 : constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs)
331 157715 : : m_lhs (lhs), m_op (c_op), m_rhs (rhs)
332 : {
333 157715 : gcc_assert (!lhs.null_p ());
334 157715 : gcc_assert (!rhs.null_p ());
335 157715 : }
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 41872 : class fact_visitor
365 : {
366 : public:
367 41872 : 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 1457 : bounded_ranges_constraint (equiv_class_id ec_id,
379 : const bounded_ranges *ranges)
380 1457 : : 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 5087 : bool operator!= (const bounded_ranges_constraint &other) const
390 : {
391 5087 : 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 370385 : constraint_manager (region_model_manager *mgr) : m_mgr (mgr) {}
413 : constraint_manager (const constraint_manager &other);
414 7231558 : 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 404927 : bool operator!= (const constraint_manager &other) const
421 : {
422 404927 : 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 1409613 : const equiv_class &get_equiv_class_by_index (unsigned idx) const
436 : {
437 1409613 : return *m_equiv_classes[idx];
438 : }
439 140765 : equiv_class &get_equiv_class_by_index (unsigned idx)
440 : {
441 140765 : return *m_equiv_classes[idx];
442 : }
443 :
444 32663 : equiv_class &get_equiv_class (const svalue *sval)
445 : {
446 32663 : equiv_class_id ec_id = get_or_add_equiv_class (sval);
447 32663 : 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 */
|
