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>.
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
);
103 bool singleton_p () const
105 return tree_int_cst_equal (m_lower
, m_upper
);
112 static void set_json_attr (json::object
*obj
, const char *name
, tree value
);
115 /* A collection of bounded_range instances, suitable
116 for representing the ranges on a case label within a switch
119 struct bounded_ranges
122 typedef bounded_ranges key_t
;
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
);
128 bool operator== (const bounded_ranges
&other
) const;
130 hashval_t
get_hash () const { return m_hash
; }
132 void dump_to_pp (pretty_printer
*pp
, bool show_types
) const;
133 void dump (bool show_types
) const;
135 json::value
*to_json () const;
137 tristate
eval_condition (enum tree_code op
,
139 bounded_ranges_manager
*mgr
) const;
141 bool contain_p (tree cst
) const;
142 bool empty_p () const { return m_ranges
.length () == 0; }
144 static int cmp (const bounded_ranges
*a
, const bounded_ranges
*b
);
146 unsigned get_count () const { return m_ranges
.length (); }
147 const bounded_range
&get_range (unsigned idx
) const { return m_ranges
[idx
]; }
150 void canonicalize ();
151 void validate () const;
153 friend class bounded_ranges_manager
;
155 auto_vec
<bounded_range
> m_ranges
;
161 template <> struct default_hash_traits
<bounded_ranges::key_t
>
162 : public member_function_hash_traits
<bounded_ranges::key_t
>
164 static const bool empty_zero_p
= true;
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
174 class bounded_ranges_manager
177 ~bounded_ranges_manager ();
179 const bounded_ranges
*
180 get_or_create_ranges_for_switch (const switch_cfg_superedge
*edge
,
181 const gswitch
*switch_stmt
);
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
);
195 void log_stats (logger
*logger
, bool show_objs
) const;
198 const bounded_ranges
*
199 create_ranges_for_switch (const switch_cfg_superedge
&edge
,
200 const gswitch
*switch_stmt
);
202 const bounded_ranges
*
203 make_case_label_ranges (const gswitch
*switch_stmt
,
206 const bounded_ranges
*consolidate (bounded_ranges
*);
208 struct hash_traits_t
: public typed_noop_remove
<bounded_ranges
*>
210 typedef bounded_ranges
*key_type
;
211 typedef bounded_ranges
*value_type
;
214 equal (const key_type
&k1
, const key_type
&k2
)
218 static inline hashval_t
219 hash (const key_type
&k
)
221 return k
->get_hash ();
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
)
227 return k
== reinterpret_cast<key_type
> (1);
230 static const bool empty_zero_p
= true;
232 struct traits_t
: public simple_hashmap_traits
<hash_traits_t
,
236 typedef hash_map
<bounded_ranges
*, bounded_ranges
*, traits_t
> map_t
;
239 typedef hash_map
<const switch_cfg_superedge
*,
240 const bounded_ranges
*> edge_cache_t
;
241 edge_cache_t m_edge_cache
;
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. */
252 equiv_class (const equiv_class
&other
);
254 hashval_t
hash () const;
255 bool operator== (const equiv_class
&other
);
257 void add (const svalue
*sval
);
258 bool del (const svalue
*sval
);
260 tree
get_any_constant () const { return m_constant
; }
262 const svalue
*get_representative () const;
264 void canonicalize ();
266 void print (pretty_printer
*pp
) const;
268 json::object
*to_json () const;
270 bool contains_non_constant_p () const;
272 /* An equivalence class can contain multiple constants (e.g. multiple
273 different zeroes, for different types); these are just for the last
276 const svalue
*m_cst_sval
;
278 // TODO: should this be a set rather than a vec?
279 auto_vec
<const svalue
*> m_vars
;
282 /* The various kinds of constraint. */
291 const char *constraint_op_code (enum constraint_op c_op
);
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. */
299 static equiv_class_id
null () { return equiv_class_id (-1); }
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;
305 bool operator== (const equiv_class_id
&other
) const
307 return m_idx
== other
.m_idx
;
309 bool operator!= (const equiv_class_id
&other
) const
311 return m_idx
!= other
.m_idx
;
314 bool null_p () const { return m_idx
== -1; }
316 static equiv_class_id
from_int (int idx
) { return equiv_class_id (idx
); }
317 int as_int () const { return m_idx
; }
319 void print (pretty_printer
*pp
) const;
321 void update_for_removal (equiv_class_id other
)
323 if (m_idx
> other
.m_idx
)
330 /* A relationship between two equivalence classes in a constraint_manager. */
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
)
338 gcc_assert (!lhs
.null_p ());
339 gcc_assert (!rhs
.null_p ());
342 void print (pretty_printer
*pp
, const constraint_manager
&cm
) const;
344 json::object
*to_json () const;
346 hashval_t
hash () const;
347 bool operator== (const constraint
&other
) const;
349 /* Is this an ordering, rather than a "!=". */
350 bool is_ordering_p () const
352 return m_op
!= CONSTRAINT_NE
;
355 bool implied_by (const constraint
&other
,
356 const constraint_manager
&cm
) const;
358 equiv_class_id m_lhs
;
359 enum constraint_op m_op
;
360 equiv_class_id m_rhs
;
363 /* An abstract base class for use with constraint_manager::for_each_fact. */
368 virtual ~fact_visitor () {}
369 virtual void on_fact (const svalue
*lhs
,
371 const svalue
*rhs
) = 0;
372 virtual void on_ranges (const svalue
*lhs
,
373 const bounded_ranges
*ranges
) = 0;
376 class bounded_ranges_constraint
379 bounded_ranges_constraint (equiv_class_id ec_id
,
380 const bounded_ranges
*ranges
)
381 : m_ec_id (ec_id
), m_ranges (ranges
)
385 void print (pretty_printer
*pp
, const constraint_manager
&cm
) const;
387 json::object
*to_json () const;
389 bool operator== (const bounded_ranges_constraint
&other
) const;
390 bool operator!= (const bounded_ranges_constraint
&other
) const
392 return !(*this == other
);
395 void add_to_hash (inchash::hash
*hstate
) const;
397 equiv_class_id m_ec_id
;
398 const bounded_ranges
*m_ranges
;
401 /* A collection of equivalence classes and constraints on them.
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. */
407 class constraint_manager
410 constraint_manager (region_model_manager
*mgr
) : m_mgr (mgr
) {}
411 constraint_manager (const constraint_manager
&other
);
412 virtual ~constraint_manager () {}
414 constraint_manager
& operator= (const constraint_manager
&other
);
416 hashval_t
hash () const;
417 bool operator== (const constraint_manager
&other
) const;
418 bool operator!= (const constraint_manager
&other
) const
420 return !(*this == other
);
423 void print (pretty_printer
*pp
) const;
424 void dump_to_pp (pretty_printer
*pp
, bool multiline
) const;
425 void dump (FILE *fp
) const;
428 json::object
*to_json () const;
430 const equiv_class
&get_equiv_class_by_index (unsigned idx
) const
432 return *m_equiv_classes
[idx
];
434 equiv_class
&get_equiv_class_by_index (unsigned idx
)
436 return *m_equiv_classes
[idx
];
439 equiv_class
&get_equiv_class (const svalue
*sval
)
441 equiv_class_id ec_id
= get_or_add_equiv_class (sval
);
442 return ec_id
.get_obj (*this);
445 bool add_constraint (const svalue
*lhs
,
449 bool add_constraint (equiv_class_id lhs_ec_id
,
451 equiv_class_id rhs_ec_id
);
453 void add_unknown_constraint (equiv_class_id lhs_ec_id
,
455 equiv_class_id rhs_ec_id
);
457 bool add_bounded_ranges (const svalue
*sval
,
458 const bounded_ranges
*ranges
);
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
,
466 equiv_class_id rhs
) const;
467 tristate
eval_condition (equiv_class_id lhs_ec
,
469 tree rhs_const
) const;
470 tristate
eval_condition (const svalue
*lhs
,
472 const svalue
*rhs
) const;
473 range
get_ec_bounds (equiv_class_id ec_id
) const;
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
);
480 void on_liveness_change (const svalue_set
&live_svalues
,
481 const region_model
*model
);
482 void purge_state_involving (const svalue
*sval
);
484 void canonicalize ();
486 static void merge (const constraint_manager
&cm_a
,
487 const constraint_manager
&cm_b
,
488 constraint_manager
*out
);
490 void for_each_fact (fact_visitor
*) const;
492 void validate () const;
494 bounded_ranges_manager
*get_range_manager () const;
496 bool replay_call_summary (call_summary_replay
&r
,
497 const constraint_manager
&summary
);
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
;
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;
510 region_model_manager
*m_mgr
;
515 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */