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 : 14942 : bound () : m_constant (NULL_TREE), m_closed (false) {}
39 : 14864 : bound (tree constant, bool closed)
40 : 14811 : : 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 : 14942 : range () : m_lower_bound (), m_upper_bound () {}
57 : 121 : range (const bound &lower, const bound &upper)
58 : 121 : : 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 : 74633 : bool operator!= (const bounded_range &other) const
97 : : {
98 : 74633 : return !(*this == other);
99 : : }
100 : :
101 : : static int cmp (const bounded_range &a, const bounded_range &b);
102 : :
103 : 8598 : bool singleton_p () const
104 : : {
105 : 8598 : 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 : 14186 : 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 : 112407 : 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 : 23406 : bool empty_p () const { return m_ranges.length () == 0; }
143 : :
144 : : static int cmp (const bounded_ranges *a, const bounded_ranges *b);
145 : :
146 : 17985 : unsigned get_count () const { return m_ranges.length (); }
147 : 23805 : 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 : 92386 : equal (const key_type &k1, const key_type &k2)
215 : : {
216 : 92386 : return *k1 == *k2;
217 : : }
218 : : static inline hashval_t
219 : 95502 : hash (const key_type &k)
220 : : {
221 : 95502 : return k->get_hash ();
222 : : }
223 : : static inline bool is_empty (key_type k) { return k == NULL; }
224 : 0 : static inline void mark_empty (key_type &k) { k = NULL; }
225 : 109468 : static inline bool is_deleted (key_type k)
226 : : {
227 : 109468 : 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 : 14010024 : 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 : 930735 : 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 : 3509227 : static equiv_class_id null () { return equiv_class_id (-1); }
300 : :
301 : 13837484 : 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 : 5885871 : bool operator== (const equiv_class_id &other) const
306 : : {
307 : 3597885 : return m_idx == other.m_idx;
308 : : }
309 : 1761054 : bool operator!= (const equiv_class_id &other) const
310 : : {
311 : 1761054 : return m_idx != other.m_idx;
312 : : }
313 : :
314 : 10824298 : bool null_p () const { return m_idx == -1; }
315 : :
316 : 0 : static equiv_class_id from_int (int idx) { return equiv_class_id (idx); }
317 : 21842800 : int as_int () const { return m_idx; }
318 : :
319 : : void print (pretty_printer *pp) const;
320 : :
321 : 163826 : void update_for_removal (equiv_class_id other)
322 : : {
323 : 102844 : if (m_idx > other.m_idx)
324 : 30290 : 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 : 199708 : constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs)
336 : 199708 : : m_lhs (lhs), m_op (c_op), m_rhs (rhs)
337 : : {
338 : 199708 : gcc_assert (!lhs.null_p ());
339 : 199708 : gcc_assert (!rhs.null_p ());
340 : 199708 : }
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 : 19673 : bool is_ordering_p () const
351 : : {
352 : 19673 : 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 : 76953 : class fact_visitor
366 : : {
367 : : public:
368 : 76953 : 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 : 1738 : bounded_ranges_constraint (equiv_class_id ec_id,
380 : : const bounded_ranges *ranges)
381 : 1738 : : 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 : 5535 : bool operator!= (const bounded_ranges_constraint &other) const
391 : : {
392 : 5535 : 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 : 406614 : constraint_manager (region_model_manager *mgr) : m_mgr (mgr) {}
411 : : constraint_manager (const constraint_manager &other);
412 : 9270940 : 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 : 444765 : bool operator!= (const constraint_manager &other) const
419 : : {
420 : 444765 : 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 : 1857415 : const equiv_class &get_equiv_class_by_index (unsigned idx) const
431 : : {
432 : 1857415 : return *m_equiv_classes[idx];
433 : : }
434 : 198576 : equiv_class &get_equiv_class_by_index (unsigned idx)
435 : : {
436 : 198576 : return *m_equiv_classes[idx];
437 : : }
438 : :
439 : 44901 : equiv_class &get_equiv_class (const svalue *sval)
440 : : {
441 : 44901 : equiv_class_id ec_id = get_or_add_equiv_class (sval);
442 : 44901 : return ec_id.get_obj (*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 */
|
