1 /* Tracking equivalence classes and constraints at a point on an execution path.
2 Copyright (C) 2019-2023 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 (*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 equiv_class_id get_or_add_equiv_class (const svalue *sval);
463 tristate eval_condition (equiv_class_id lhs,
464 enum tree_code op,
465 equiv_class_id rhs) const;
466 tristate eval_condition (equiv_class_id lhs_ec,
467 enum tree_code op,
468 tree rhs_const) const;
469 tristate eval_condition (const svalue *lhs,
470 enum tree_code op,
471 const svalue *rhs) const;
472 range get_ec_bounds (equiv_class_id ec_id) const;
473
474 /* PurgeCriteria should have:
475 bool should_purge_p (const svalue *sval) const. */
476 template <typename PurgeCriteria>
477 void purge (const PurgeCriteria &p, purge_stats *stats);
478
479 void on_liveness_change (const svalue_set &live_svalues,
480 const region_model *model);
481 void purge_state_involving (const svalue *sval);
482
483 void canonicalize ();
484
485 static void merge (const constraint_manager &cm_a,
486 const constraint_manager &cm_b,
487 constraint_manager *out);
488
489 void for_each_fact (fact_visitor *) const;
490
491 void validate () const;
492
493 bounded_ranges_manager *get_range_manager () const;
494
495 bool replay_call_summary (call_summary_replay &r,
496 const constraint_manager &summary);
497
498 auto_delete_vec<equiv_class> m_equiv_classes;
499 auto_vec<constraint> m_constraints;
500 auto_vec<bounded_ranges_constraint> m_bounded_ranges_constraints;
501
502 private:
503 void add_constraint_internal (equiv_class_id lhs_id,
504 enum constraint_op c_op,
505 equiv_class_id rhs_id);
506 bool impossible_derived_conditions_p (const svalue *lhs,
507 const svalue *rhs) const;
508
509 region_model_manager *m_mgr;
510 };
511
512 } // namespace ana
513
514 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */