1 /* Tracking equivalence classes and constraints at a point on an execution path.
2 Copyright (C) 2019-2022 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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)
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.
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/>. */
21 #ifndef GCC_ANALYZER_CONSTRAINT_MANAGER_H
22 #define GCC_ANALYZER_CONSTRAINT_MANAGER_H
26 class constraint_manager
;
34 /* One of the end-points of a range. */
38 bound () : m_constant (NULL_TREE
), m_closed (false) {}
39 bound (tree constant
, bool closed
)
40 : m_constant (constant
), m_closed (closed
) {}
42 void ensure_closed (enum bound_kind bound_kind
);
44 const char * get_relation_as_str () const;
50 /* A range of values, used for determining if a value has been
51 constrained to just one possible constant value. */
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
) {}
60 void dump_to_pp (pretty_printer
*pp
) const;
63 tree
constrained_to_single_element ();
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;
70 bool add_bound (bound b
, enum bound_kind bound_kind
);
71 bool add_bound (enum tree_code op
, tree rhs_const
);
78 /* A closed range of values with constant integer bounds
79 e.g. [3, 5] for the set {3, 4, 5}. */
83 bounded_range (const_tree lower
, const_tree upper
);
85 void dump_to_pp (pretty_printer
*pp
, bool show_types
) const;
86 void dump (bool show_types
) const;
88 json::object
*to_json () const;
90 bool contains_p (tree cst
) const;
92 bool intersects_p (const bounded_range
&other
,
93 bounded_range
*out
) const;
95 bool operator== (const bounded_range
&other
) const;
96 bool operator!= (const bounded_range
&other
) const
98 return !(*this == other
);
101 static int cmp (const bounded_range
&a
, const bounded_range
&b
);
107 static void set_json_attr (json::object
*obj
, const char *name
, tree value
);
110 /* A collection of bounded_range instances, suitable
111 for representing the ranges on a case label within a switch
114 struct bounded_ranges
117 typedef bounded_ranges key_t
;
119 bounded_ranges (const bounded_range
&range
);
120 bounded_ranges (const vec
<bounded_range
> &ranges
);
121 bounded_ranges (enum tree_code op
, tree rhs_const
);
123 bool operator== (const bounded_ranges
&other
) const;
125 hashval_t
get_hash () const { return m_hash
; }
127 void dump_to_pp (pretty_printer
*pp
, bool show_types
) const;
128 void dump (bool show_types
) const;
130 json::value
*to_json () const;
132 tristate
eval_condition (enum tree_code op
,
134 bounded_ranges_manager
*mgr
) const;
136 bool contain_p (tree cst
) const;
137 bool empty_p () const { return m_ranges
.length () == 0; }
139 static int cmp (const bounded_ranges
*a
, const bounded_ranges
*b
);
141 unsigned get_count () const { return m_ranges
.length (); }
142 const bounded_range
&get_range (unsigned idx
) const { return m_ranges
[idx
]; }
145 void canonicalize ();
146 void validate () const;
148 friend class bounded_ranges_manager
;
150 auto_vec
<bounded_range
> m_ranges
;
156 template <> struct default_hash_traits
<bounded_ranges::key_t
>
157 : public member_function_hash_traits
<bounded_ranges::key_t
>
159 static const bool empty_zero_p
= true;
164 /* An object to own and consolidate bounded_ranges instances.
165 This also caches the mapping from switch_cfg_superedge
166 bounded_ranges instances, so that get_or_create_ranges_for_switch is
169 class bounded_ranges_manager
172 ~bounded_ranges_manager ();
174 const bounded_ranges
*
175 get_or_create_ranges_for_switch (const switch_cfg_superedge
*edge
,
176 const gswitch
*switch_stmt
);
178 const bounded_ranges
*get_or_create_empty ();
179 const bounded_ranges
*get_or_create_point (const_tree value
);
180 const bounded_ranges
*get_or_create_range (const_tree lower_bound
,
181 const_tree upper_bound
);
182 const bounded_ranges
*
183 get_or_create_union (const vec
<const bounded_ranges
*> &others
);
184 const bounded_ranges
*
185 get_or_create_intersection (const bounded_ranges
*a
,
186 const bounded_ranges
*b
);
187 const bounded_ranges
*
188 get_or_create_inverse (const bounded_ranges
*other
, tree type
);
190 void log_stats (logger
*logger
, bool show_objs
) const;
193 const bounded_ranges
*
194 create_ranges_for_switch (const switch_cfg_superedge
&edge
,
195 const gswitch
*switch_stmt
);
197 const bounded_ranges
*
198 make_case_label_ranges (const gswitch
*switch_stmt
,
201 const bounded_ranges
*consolidate (bounded_ranges
*);
203 struct hash_traits_t
: public typed_noop_remove
<bounded_ranges
*>
205 typedef bounded_ranges
*key_type
;
206 typedef bounded_ranges
*value_type
;
209 equal (const key_type
&k1
, const key_type
&k2
)
213 static inline hashval_t
214 hash (const key_type
&k
)
216 return k
->get_hash ();
218 static inline bool is_empty (key_type k
) { return k
== NULL
; }
219 static inline void mark_empty (key_type
&k
) { k
= NULL
; }
220 static inline bool is_deleted (key_type k
)
222 return k
== reinterpret_cast<key_type
> (1);
225 static const bool empty_zero_p
= true;
227 struct traits_t
: public simple_hashmap_traits
<hash_traits_t
,
231 typedef hash_map
<bounded_ranges
*, bounded_ranges
*, traits_t
> map_t
;
234 typedef hash_map
<const switch_cfg_superedge
*,
235 const bounded_ranges
*> edge_cache_t
;
236 edge_cache_t m_edge_cache
;
239 /* An equivalence class within a constraint manager: a set of
240 svalues that are known to all be equal to each other,
241 together with an optional tree constant that they are equal to. */
247 equiv_class (const equiv_class
&other
);
249 hashval_t
hash () const;
250 bool operator== (const equiv_class
&other
);
252 void add (const svalue
*sval
);
253 bool del (const svalue
*sval
);
255 tree
get_any_constant () const { return m_constant
; }
257 const svalue
*get_representative () const;
259 void canonicalize ();
261 void print (pretty_printer
*pp
) const;
263 json::object
*to_json () const;
265 bool contains_non_constant_p () const;
267 /* An equivalence class can contain multiple constants (e.g. multiple
268 different zeroes, for different types); these are just for the last
271 const svalue
*m_cst_sval
;
273 // TODO: should this be a set rather than a vec?
274 auto_vec
<const svalue
*> m_vars
;
277 /* The various kinds of constraint. */
286 const char *constraint_op_code (enum constraint_op c_op
);
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. */
294 static equiv_class_id
null () { return equiv_class_id (-1); }
296 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;
300 bool operator== (const equiv_class_id
&other
) const
302 return m_idx
== other
.m_idx
;
304 bool operator!= (const equiv_class_id
&other
) const
306 return m_idx
!= other
.m_idx
;
309 bool null_p () const { return m_idx
== -1; }
311 static equiv_class_id
from_int (int idx
) { return equiv_class_id (idx
); }
312 int as_int () const { return m_idx
; }
314 void print (pretty_printer
*pp
) const;
316 void update_for_removal (equiv_class_id other
)
318 if (m_idx
> other
.m_idx
)
325 /* A relationship between two equivalence classes in a constraint_manager. */
330 constraint (equiv_class_id lhs
, enum constraint_op c_op
, equiv_class_id rhs
)
331 : m_lhs (lhs
), m_op (c_op
), m_rhs (rhs
)
333 gcc_assert (!lhs
.null_p ());
334 gcc_assert (!rhs
.null_p ());
337 void print (pretty_printer
*pp
, const constraint_manager
&cm
) const;
339 json::object
*to_json () const;
341 hashval_t
hash () const;
342 bool operator== (const constraint
&other
) const;
344 /* Is this an ordering, rather than a "!=". */
345 bool is_ordering_p () const
347 return m_op
!= CONSTRAINT_NE
;
350 bool implied_by (const constraint
&other
,
351 const constraint_manager
&cm
) const;
353 equiv_class_id m_lhs
;
354 enum constraint_op m_op
;
355 equiv_class_id m_rhs
;
358 /* An abstract base class for use with constraint_manager::for_each_fact. */
363 virtual ~fact_visitor () {}
364 virtual void on_fact (const svalue
*lhs
,
366 const svalue
*rhs
) = 0;
367 virtual void on_ranges (const svalue
*lhs
,
368 const bounded_ranges
*ranges
) = 0;
371 class bounded_ranges_constraint
374 bounded_ranges_constraint (equiv_class_id ec_id
,
375 const bounded_ranges
*ranges
)
376 : m_ec_id (ec_id
), m_ranges (ranges
)
380 void print (pretty_printer
*pp
, const constraint_manager
&cm
) const;
382 json::object
*to_json () const;
384 bool operator== (const bounded_ranges_constraint
&other
) const;
385 bool operator!= (const bounded_ranges_constraint
&other
) const
387 return !(*this == other
);
390 void add_to_hash (inchash::hash
*hstate
) const;
392 equiv_class_id m_ec_id
;
393 const bounded_ranges
*m_ranges
;
396 /* A collection of equivalence classes and constraints on them.
398 Given N svalues, this can be thought of as representing a subset of
399 N-dimensional space. When we call add_constraint,
400 we are effectively taking an intersection with that constraint. */
402 class constraint_manager
405 constraint_manager (region_model_manager
*mgr
) : m_mgr (mgr
) {}
406 constraint_manager (const constraint_manager
&other
);
407 virtual ~constraint_manager () {}
409 constraint_manager
& operator= (const constraint_manager
&other
);
411 hashval_t
hash () const;
412 bool operator== (const constraint_manager
&other
) const;
413 bool operator!= (const constraint_manager
&other
) const
415 return !(*this == other
);
418 void print (pretty_printer
*pp
) const;
419 void dump_to_pp (pretty_printer
*pp
, bool multiline
) const;
420 void dump (FILE *fp
) const;
423 json::object
*to_json () const;
425 const equiv_class
&get_equiv_class_by_index (unsigned idx
) const
427 return *m_equiv_classes
[idx
];
429 equiv_class
&get_equiv_class_by_index (unsigned idx
)
431 return *m_equiv_classes
[idx
];
434 equiv_class
&get_equiv_class (const svalue
*sval
)
436 equiv_class_id ec_id
= get_or_add_equiv_class (sval
);
437 return ec_id
.get_obj (*this);
440 bool add_constraint (const svalue
*lhs
,
444 bool add_constraint (equiv_class_id lhs_ec_id
,
446 equiv_class_id rhs_ec_id
);
448 void add_unknown_constraint (equiv_class_id lhs_ec_id
,
450 equiv_class_id rhs_ec_id
);
452 bool add_bounded_ranges (const svalue
*sval
,
453 const bounded_ranges
*ranges
);
455 bool get_equiv_class_by_svalue (const svalue
*sval
,
456 equiv_class_id
*out
) const;
457 equiv_class_id
get_or_add_equiv_class (const svalue
*sval
);
458 tristate
eval_condition (equiv_class_id lhs
,
460 equiv_class_id rhs
) const;
461 tristate
eval_condition (equiv_class_id lhs_ec
,
463 tree rhs_const
) const;
464 tristate
eval_condition (const svalue
*lhs
,
466 const svalue
*rhs
) const;
467 range
get_ec_bounds (equiv_class_id ec_id
) const;
469 /* PurgeCriteria should have:
470 bool should_purge_p (const svalue *sval) const. */
471 template <typename PurgeCriteria
>
472 void purge (const PurgeCriteria
&p
, purge_stats
*stats
);
474 void on_liveness_change (const svalue_set
&live_svalues
,
475 const region_model
*model
);
476 void purge_state_involving (const svalue
*sval
);
478 void canonicalize ();
480 static void merge (const constraint_manager
&cm_a
,
481 const constraint_manager
&cm_b
,
482 constraint_manager
*out
);
484 void for_each_fact (fact_visitor
*) const;
486 void validate () const;
488 bounded_ranges_manager
*get_range_manager () const;
490 bool replay_call_summary (call_summary_replay
&r
,
491 const constraint_manager
&summary
);
493 auto_delete_vec
<equiv_class
> m_equiv_classes
;
494 auto_vec
<constraint
> m_constraints
;
495 auto_vec
<bounded_ranges_constraint
> m_bounded_ranges_constraints
;
498 void add_constraint_internal (equiv_class_id lhs_id
,
499 enum constraint_op c_op
,
500 equiv_class_id rhs_id
);
502 region_model_manager
*m_mgr
;
507 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */