Branch data Line data Source code
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 : 12981 : bound () : m_constant (NULL_TREE), m_closed (false) {}
39 : 12727 : bound (tree constant, bool closed)
40 : 12683 : : 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 : 12981 : range () : m_lower_bound (), m_upper_bound () {}
57 : 104 : range (const bound &lower, const bound &upper)
58 : 104 : : 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 : 62091 : bool operator!= (const bounded_range &other) const
100 : : {
101 : 62091 : return !(*this == other);
102 : : }
103 : :
104 : : static int cmp (const bounded_range &a, const bounded_range &b);
105 : :
106 : 7263 : bool singleton_p () const
107 : : {
108 : 7263 : 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 : 12112 : 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 : 96630 : 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 : 12924 : bool empty_p () const { return m_ranges.length () == 0; }
149 : :
150 : : static int cmp (const bounded_ranges *a, const bounded_ranges *b);
151 : :
152 : 15073 : unsigned get_count () const { return m_ranges.length (); }
153 : 19831 : 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 : : This also caches the mapping from switch_cfg_superedge
177 : : bounded_ranges instances, so that get_or_create_ranges_for_switch is
178 : : memoized. */
179 : :
180 : : class bounded_ranges_manager
181 : : {
182 : : public:
183 : : ~bounded_ranges_manager ();
184 : :
185 : : const bounded_ranges *
186 : : get_or_create_ranges_for_switch (const switch_cfg_superedge *edge,
187 : : const gswitch *switch_stmt);
188 : :
189 : : const bounded_ranges *get_or_create_empty ();
190 : : const bounded_ranges *get_or_create_point (const_tree value);
191 : : const bounded_ranges *get_or_create_range (const_tree lower_bound,
192 : : const_tree upper_bound);
193 : : const bounded_ranges *
194 : : get_or_create_union (const vec <const bounded_ranges *> &others);
195 : : const bounded_ranges *
196 : : get_or_create_intersection (const bounded_ranges *a,
197 : : const bounded_ranges *b);
198 : : const bounded_ranges *
199 : : get_or_create_inverse (const bounded_ranges *other, tree type);
200 : :
201 : : void log_stats (logger *logger, bool show_objs) const;
202 : :
203 : : private:
204 : : const bounded_ranges *
205 : : create_ranges_for_switch (const switch_cfg_superedge &edge,
206 : : const gswitch *switch_stmt);
207 : :
208 : : const bounded_ranges *
209 : : make_case_label_ranges (const gswitch *switch_stmt,
210 : : tree case_label);
211 : :
212 : : const bounded_ranges *consolidate (bounded_ranges *);
213 : :
214 : : struct hash_traits_t : public typed_noop_remove<bounded_ranges *>
215 : : {
216 : : typedef bounded_ranges *key_type;
217 : : typedef bounded_ranges *value_type;
218 : :
219 : : static inline bool
220 : 78352 : equal (const key_type &k1, const key_type &k2)
221 : : {
222 : 78352 : return *k1 == *k2;
223 : : }
224 : : static inline hashval_t
225 : 81216 : hash (const key_type &k)
226 : : {
227 : 81216 : return k->get_hash ();
228 : : }
229 : : static inline bool is_empty (key_type k) { return k == NULL; }
230 : 0 : static inline void mark_empty (key_type &k) { k = NULL; }
231 : 92937 : static inline bool is_deleted (key_type k)
232 : : {
233 : 92937 : return k == reinterpret_cast<key_type> (1);
234 : : }
235 : :
236 : : static const bool empty_zero_p = true;
237 : : };
238 : : struct traits_t : public simple_hashmap_traits<hash_traits_t,
239 : : bounded_ranges *>
240 : : {
241 : : };
242 : : typedef hash_map<bounded_ranges *, bounded_ranges *, traits_t> map_t;
243 : : map_t m_map;
244 : :
245 : : typedef hash_map<const switch_cfg_superedge *,
246 : : const bounded_ranges *> edge_cache_t;
247 : : edge_cache_t m_edge_cache;
248 : : };
249 : :
250 : : /* An equivalence class within a constraint manager: a set of
251 : : svalues that are known to all be equal to each other,
252 : : together with an optional tree constant that they are equal to. */
253 : :
254 : 11721948 : class equiv_class
255 : : {
256 : : public:
257 : : equiv_class ();
258 : : equiv_class (const equiv_class &other);
259 : :
260 : : hashval_t hash () const;
261 : : bool operator== (const equiv_class &other);
262 : :
263 : : void add (const svalue *sval);
264 : : bool del (const svalue *sval);
265 : :
266 : 781768 : tree get_any_constant () const { return m_constant; }
267 : :
268 : : const svalue *get_representative () const;
269 : :
270 : : void canonicalize ();
271 : :
272 : : void print (pretty_printer *pp) const;
273 : :
274 : : std::unique_ptr<json::object> to_json () const;
275 : :
276 : : std::unique_ptr<text_art::tree_widget>
277 : : make_dump_widget (const text_art::dump_widget_info &dwi,
278 : : unsigned id) const;
279 : :
280 : : bool contains_non_constant_p () const;
281 : :
282 : : /* An equivalence class can contain multiple constants (e.g. multiple
283 : : different zeroes, for different types); these are just for the last
284 : : constant added. */
285 : : tree m_constant;
286 : : const svalue *m_cst_sval;
287 : :
288 : : // TODO: should this be a set rather than a vec?
289 : : auto_vec<const svalue *> m_vars;
290 : : };
291 : :
292 : : /* The various kinds of constraint. */
293 : :
294 : : enum constraint_op
295 : : {
296 : : CONSTRAINT_NE,
297 : : CONSTRAINT_LT,
298 : : CONSTRAINT_LE
299 : : };
300 : :
301 : : const char *constraint_op_code (enum constraint_op c_op);
302 : :
303 : : /* An ID for an equiv_class within a constraint_manager. Internally, this
304 : : is an index into a vector of equiv_class * within the constraint_manager. */
305 : :
306 : : class equiv_class_id
307 : : {
308 : : public:
309 : 2915056 : static equiv_class_id null () { return equiv_class_id (-1); }
310 : :
311 : 11480258 : equiv_class_id (unsigned idx) : m_idx (idx) {}
312 : : const equiv_class &get_obj (const constraint_manager &cm) const;
313 : : equiv_class &get_obj (constraint_manager &cm) const;
314 : :
315 : 4911977 : bool operator== (const equiv_class_id &other) const
316 : : {
317 : 2998142 : return m_idx == other.m_idx;
318 : : }
319 : 1460613 : bool operator!= (const equiv_class_id &other) const
320 : : {
321 : 1460613 : return m_idx != other.m_idx;
322 : : }
323 : :
324 : 9018067 : bool null_p () const { return m_idx == -1; }
325 : :
326 : 0 : static equiv_class_id from_int (int idx) { return equiv_class_id (idx); }
327 : 18127209 : int as_int () const { return m_idx; }
328 : :
329 : : void print (pretty_printer *pp) const;
330 : :
331 : 137979 : void update_for_removal (equiv_class_id other)
332 : : {
333 : 86535 : if (m_idx > other.m_idx)
334 : 25568 : m_idx--;
335 : : }
336 : :
337 : : int m_idx;
338 : : };
339 : :
340 : : /* A relationship between two equivalence classes in a constraint_manager. */
341 : :
342 : : class constraint
343 : : {
344 : : public:
345 : 166017 : constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs)
346 : 166017 : : m_lhs (lhs), m_op (c_op), m_rhs (rhs)
347 : : {
348 : 166017 : gcc_assert (!lhs.null_p ());
349 : 166017 : gcc_assert (!rhs.null_p ());
350 : 166017 : }
351 : :
352 : : void print (pretty_printer *pp, const constraint_manager &cm) const;
353 : :
354 : : std::unique_ptr<json::object> to_json () const;
355 : :
356 : : std::unique_ptr<text_art::widget>
357 : : make_dump_widget (const text_art::dump_widget_info &dwi,
358 : : const constraint_manager &cm) const;
359 : :
360 : : hashval_t hash () const;
361 : : bool operator== (const constraint &other) const;
362 : :
363 : : /* Is this an ordering, rather than a "!=". */
364 : 15810 : bool is_ordering_p () const
365 : : {
366 : 15810 : return m_op != CONSTRAINT_NE;
367 : : }
368 : :
369 : : bool implied_by (const constraint &other,
370 : : const constraint_manager &cm) const;
371 : :
372 : : equiv_class_id m_lhs;
373 : : enum constraint_op m_op;
374 : : equiv_class_id m_rhs;
375 : : };
376 : :
377 : : /* An abstract base class for use with constraint_manager::for_each_fact. */
378 : :
379 : 63934 : class fact_visitor
380 : : {
381 : : public:
382 : 63934 : virtual ~fact_visitor () {}
383 : : virtual void on_fact (const svalue *lhs,
384 : : enum tree_code,
385 : : const svalue *rhs) = 0;
386 : : virtual void on_ranges (const svalue *lhs,
387 : : const bounded_ranges *ranges) = 0;
388 : : };
389 : :
390 : : class bounded_ranges_constraint
391 : : {
392 : : public:
393 : 1530 : bounded_ranges_constraint (equiv_class_id ec_id,
394 : : const bounded_ranges *ranges)
395 : 1530 : : m_ec_id (ec_id), m_ranges (ranges)
396 : : {
397 : : }
398 : :
399 : : void print (pretty_printer *pp, const constraint_manager &cm) const;
400 : :
401 : : std::unique_ptr<json::object> to_json () const;
402 : :
403 : : bool operator== (const bounded_ranges_constraint &other) const;
404 : 5057 : bool operator!= (const bounded_ranges_constraint &other) const
405 : : {
406 : 5057 : return !(*this == other);
407 : : }
408 : :
409 : : void add_to_hash (inchash::hash *hstate) const;
410 : :
411 : : std::unique_ptr<text_art::tree_widget>
412 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
413 : :
414 : : equiv_class_id m_ec_id;
415 : : const bounded_ranges *m_ranges;
416 : : };
417 : :
418 : : /* A collection of equivalence classes and constraints on them.
419 : :
420 : : Given N svalues, this can be thought of as representing a subset of
421 : : N-dimensional space. When we call add_constraint,
422 : : we are effectively taking an intersection with that constraint. */
423 : :
424 : : class constraint_manager
425 : : {
426 : : public:
427 : 338548 : constraint_manager (region_model_manager *mgr) : m_mgr (mgr) {}
428 : : constraint_manager (const constraint_manager &other);
429 : 7766728 : virtual ~constraint_manager () {}
430 : :
431 : : constraint_manager& operator= (const constraint_manager &other);
432 : :
433 : : hashval_t hash () const;
434 : : bool operator== (const constraint_manager &other) const;
435 : 371686 : bool operator!= (const constraint_manager &other) const
436 : : {
437 : 371686 : return !(*this == other);
438 : : }
439 : :
440 : : void print (pretty_printer *pp) const;
441 : : void dump_to_pp (pretty_printer *pp, bool multiline) const;
442 : : void dump (FILE *fp) const;
443 : : void dump () const;
444 : :
445 : : std::unique_ptr<json::object> to_json () const;
446 : :
447 : : std::unique_ptr<text_art::tree_widget>
448 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
449 : :
450 : 1545050 : const equiv_class &get_equiv_class_by_index (unsigned idx) const
451 : : {
452 : 1545050 : return *m_equiv_classes[idx];
453 : : }
454 : 163527 : equiv_class &get_equiv_class_by_index (unsigned idx)
455 : : {
456 : 163527 : return *m_equiv_classes[idx];
457 : : }
458 : :
459 : 37096 : equiv_class &get_equiv_class (const svalue *sval)
460 : : {
461 : 37096 : equiv_class_id ec_id = get_or_add_equiv_class (sval);
462 : 37096 : return ec_id.get_obj (*this);
463 : : }
464 : :
465 : : bool add_constraint (const svalue *lhs,
466 : : enum tree_code op,
467 : : const svalue *rhs);
468 : :
469 : : bool add_constraint (equiv_class_id lhs_ec_id,
470 : : enum tree_code op,
471 : : equiv_class_id rhs_ec_id);
472 : :
473 : : void add_unknown_constraint (equiv_class_id lhs_ec_id,
474 : : enum tree_code op,
475 : : equiv_class_id rhs_ec_id);
476 : :
477 : : bool add_bounded_ranges (const svalue *sval,
478 : : const bounded_ranges *ranges);
479 : :
480 : : bool get_equiv_class_by_svalue (const svalue *sval,
481 : : equiv_class_id *out) const;
482 : : bool sval_constrained_p (const svalue *sval) const;
483 : : equiv_class_id get_or_add_equiv_class (const svalue *sval);
484 : : tristate eval_condition (equiv_class_id lhs,
485 : : enum tree_code op,
486 : : equiv_class_id rhs) const;
487 : : tristate eval_condition (equiv_class_id lhs_ec,
488 : : enum tree_code op,
489 : : tree rhs_const) const;
490 : : tristate eval_condition (const svalue *lhs,
491 : : enum tree_code op,
492 : : const svalue *rhs) const;
493 : : range get_ec_bounds (equiv_class_id ec_id) const;
494 : :
495 : : /* PurgeCriteria should have:
496 : : bool should_purge_p (const svalue *sval) const. */
497 : : template <typename PurgeCriteria>
498 : : void purge (const PurgeCriteria &p, purge_stats *stats);
499 : :
500 : : void on_liveness_change (const svalue_set &live_svalues,
501 : : const region_model *model);
502 : : void purge_state_involving (const svalue *sval);
503 : :
504 : : void canonicalize ();
505 : :
506 : : static void merge (const constraint_manager &cm_a,
507 : : const constraint_manager &cm_b,
508 : : constraint_manager *out);
509 : :
510 : : void for_each_fact (fact_visitor *) const;
511 : :
512 : : void validate () const;
513 : :
514 : : bounded_ranges_manager *get_range_manager () const;
515 : :
516 : : bool replay_call_summary (call_summary_replay &r,
517 : : const constraint_manager &summary);
518 : :
519 : : auto_delete_vec<equiv_class> m_equiv_classes;
520 : : auto_vec<constraint> m_constraints;
521 : : auto_vec<bounded_ranges_constraint> m_bounded_ranges_constraints;
522 : :
523 : : private:
524 : : void add_constraint_internal (equiv_class_id lhs_id,
525 : : enum constraint_op c_op,
526 : : equiv_class_id rhs_id);
527 : : bool impossible_derived_conditions_p (const svalue *lhs,
528 : : const svalue *rhs) const;
529 : :
530 : : region_model_manager *m_mgr;
531 : : };
532 : :
533 : : } // namespace ana
534 : :
535 : : #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */
|
