1 /* Tracking equivalence classes and constraints at a point on an execution path.
2 Copyright (C) 2019-2021 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
;
28 /* One of the end-points of a range. */
32 bound () : m_constant (NULL_TREE
), m_closed (false) {}
33 bound (tree constant
, bool closed
)
34 : m_constant (constant
), m_closed (closed
) {}
36 void ensure_closed (bool is_upper
);
38 const char * get_relation_as_str () const;
44 /* A range of values, used for determining if a value has been
45 constrained to just one possible constant value. */
49 range () : m_lower_bound (), m_upper_bound () {}
50 range (const bound
&lower
, const bound
&upper
)
51 : m_lower_bound (lower
), m_upper_bound (upper
) {}
53 void dump_to_pp (pretty_printer
*pp
) const;
56 tree
constrained_to_single_element ();
58 tristate
eval_condition (enum tree_code op
,
59 tree rhs_const
) const;
60 bool below_lower_bound (tree rhs_const
) const;
61 bool above_upper_bound (tree rhs_const
) const;
67 /* A closed range of values with constant integer bounds
68 e.g. [3, 5] for the set {3, 4, 5}. */
72 bounded_range (const_tree lower
, const_tree upper
);
74 void dump_to_pp (pretty_printer
*pp
, bool show_types
) const;
75 void dump (bool show_types
) const;
77 json::object
*to_json () const;
79 bool contains_p (tree cst
) const;
81 bool intersects_p (const bounded_range
&other
,
82 bounded_range
*out
) const;
84 bool operator== (const bounded_range
&other
) const;
85 bool operator!= (const bounded_range
&other
) const
87 return !(*this == other
);
90 static int cmp (const bounded_range
&a
, const bounded_range
&b
);
96 static void set_json_attr (json::object
*obj
, const char *name
, tree value
);
99 /* A collection of bounded_range instances, suitable
100 for representing the ranges on a case label within a switch
103 struct bounded_ranges
106 typedef bounded_ranges key_t
;
108 bounded_ranges (const bounded_range
&range
);
109 bounded_ranges (const vec
<bounded_range
> &ranges
);
110 bounded_ranges (enum tree_code op
, tree rhs_const
);
112 bool operator== (const bounded_ranges
&other
) const;
114 hashval_t
get_hash () const { return m_hash
; }
116 void dump_to_pp (pretty_printer
*pp
, bool show_types
) const;
117 void dump (bool show_types
) const;
119 json::value
*to_json () const;
121 tristate
eval_condition (enum tree_code op
,
123 bounded_ranges_manager
*mgr
) const;
125 bool contain_p (tree cst
) const;
126 bool empty_p () const { return m_ranges
.length () == 0; }
128 static int cmp (const bounded_ranges
*a
, const bounded_ranges
*b
);
131 void canonicalize ();
132 void validate () const;
134 friend class bounded_ranges_manager
;
136 auto_vec
<bounded_range
> m_ranges
;
142 template <> struct default_hash_traits
<bounded_ranges::key_t
>
143 : public member_function_hash_traits
<bounded_ranges::key_t
>
145 static const bool empty_zero_p
= true;
150 /* An object to own and consolidate bounded_ranges instances.
151 This also caches the mapping from switch_cfg_superedge
152 bounded_ranges instances, so that get_or_create_ranges_for_switch is
155 class bounded_ranges_manager
158 ~bounded_ranges_manager ();
160 const bounded_ranges
*
161 get_or_create_ranges_for_switch (const switch_cfg_superedge
*edge
,
162 const gswitch
*switch_stmt
);
164 const bounded_ranges
*get_or_create_empty ();
165 const bounded_ranges
*get_or_create_point (const_tree value
);
166 const bounded_ranges
*get_or_create_range (const_tree lower_bound
,
167 const_tree upper_bound
);
168 const bounded_ranges
*
169 get_or_create_union (const vec
<const bounded_ranges
*> &others
);
170 const bounded_ranges
*
171 get_or_create_intersection (const bounded_ranges
*a
,
172 const bounded_ranges
*b
);
173 const bounded_ranges
*
174 get_or_create_inverse (const bounded_ranges
*other
, tree type
);
176 void log_stats (logger
*logger
, bool show_objs
) const;
179 const bounded_ranges
*
180 create_ranges_for_switch (const switch_cfg_superedge
&edge
,
181 const gswitch
*switch_stmt
);
183 const bounded_ranges
*
184 make_case_label_ranges (const gswitch
*switch_stmt
,
187 const bounded_ranges
*consolidate (bounded_ranges
*);
189 struct hash_traits_t
: public typed_noop_remove
<bounded_ranges
*>
191 typedef bounded_ranges
*key_type
;
192 typedef bounded_ranges
*value_type
;
195 equal (const key_type
&k1
, const key_type
&k2
)
199 static inline hashval_t
200 hash (const key_type
&k
)
202 return k
->get_hash ();
204 static inline bool is_empty (key_type k
) { return k
== NULL
; }
205 static inline void mark_empty (key_type
&k
) { k
= NULL
; }
206 static inline bool is_deleted (key_type k
)
208 return k
== reinterpret_cast<key_type
> (1);
211 static const bool empty_zero_p
= true;
213 struct traits_t
: public simple_hashmap_traits
<hash_traits_t
,
217 typedef hash_map
<bounded_ranges
*, bounded_ranges
*, traits_t
> map_t
;
220 typedef hash_map
<const switch_cfg_superedge
*,
221 const bounded_ranges
*> edge_cache_t
;
222 edge_cache_t m_edge_cache
;
225 /* An equivalence class within a constraint manager: a set of
226 svalues that are known to all be equal to each other,
227 together with an optional tree constant that they are equal to. */
233 equiv_class (const equiv_class
&other
);
235 hashval_t
hash () const;
236 bool operator== (const equiv_class
&other
);
238 void add (const svalue
*sval
);
239 bool del (const svalue
*sval
);
241 tree
get_any_constant () const { return m_constant
; }
243 const svalue
*get_representative () const;
245 void canonicalize ();
247 void print (pretty_printer
*pp
) const;
249 json::object
*to_json () const;
251 /* An equivalence class can contain multiple constants (e.g. multiple
252 different zeroes, for different types); these are just for the last
255 const svalue
*m_cst_sval
;
257 // TODO: should this be a set rather than a vec?
258 auto_vec
<const svalue
*> m_vars
;
261 /* The various kinds of constraint. */
270 const char *constraint_op_code (enum constraint_op c_op
);
272 /* An ID for an equiv_class within a constraint_manager. Internally, this
273 is an index into a vector of equiv_class * within the constraint_manager. */
278 static equiv_class_id
null () { return equiv_class_id (-1); }
280 equiv_class_id (unsigned idx
) : m_idx (idx
) {}
281 const equiv_class
&get_obj (const constraint_manager
&cm
) const;
282 equiv_class
&get_obj (constraint_manager
&cm
) const;
284 bool operator== (const equiv_class_id
&other
) const
286 return m_idx
== other
.m_idx
;
288 bool operator!= (const equiv_class_id
&other
) const
290 return m_idx
!= other
.m_idx
;
293 bool null_p () const { return m_idx
== -1; }
295 static equiv_class_id
from_int (int idx
) { return equiv_class_id (idx
); }
296 int as_int () const { return m_idx
; }
298 void print (pretty_printer
*pp
) const;
300 void update_for_removal (equiv_class_id other
)
302 if (m_idx
> other
.m_idx
)
309 /* A relationship between two equivalence classes in a constraint_manager. */
314 constraint (equiv_class_id lhs
, enum constraint_op c_op
, equiv_class_id rhs
)
315 : m_lhs (lhs
), m_op (c_op
), m_rhs (rhs
)
317 gcc_assert (!lhs
.null_p ());
318 gcc_assert (!rhs
.null_p ());
321 void print (pretty_printer
*pp
, const constraint_manager
&cm
) const;
323 json::object
*to_json () const;
325 hashval_t
hash () const;
326 bool operator== (const constraint
&other
) const;
328 /* Is this an ordering, rather than a "!=". */
329 bool is_ordering_p () const
331 return m_op
!= CONSTRAINT_NE
;
334 bool implied_by (const constraint
&other
,
335 const constraint_manager
&cm
) const;
337 equiv_class_id m_lhs
;
338 enum constraint_op m_op
;
339 equiv_class_id m_rhs
;
342 /* An abstract base class for use with constraint_manager::for_each_fact. */
347 virtual ~fact_visitor () {}
348 virtual void on_fact (const svalue
*lhs
,
350 const svalue
*rhs
) = 0;
351 virtual void on_ranges (const svalue
*lhs
,
352 const bounded_ranges
*ranges
) = 0;
355 class bounded_ranges_constraint
358 bounded_ranges_constraint (equiv_class_id ec_id
,
359 const bounded_ranges
*ranges
)
360 : m_ec_id (ec_id
), m_ranges (ranges
)
364 void print (pretty_printer
*pp
, const constraint_manager
&cm
) const;
366 json::object
*to_json () const;
368 bool operator== (const bounded_ranges_constraint
&other
) const;
369 bool operator!= (const bounded_ranges_constraint
&other
) const
371 return !(*this == other
);
374 void add_to_hash (inchash::hash
*hstate
) const;
376 equiv_class_id m_ec_id
;
377 const bounded_ranges
*m_ranges
;
380 /* A collection of equivalence classes and constraints on them.
382 Given N svalues, this can be thought of as representing a subset of
383 N-dimensional space. When we call add_constraint,
384 we are effectively taking an intersection with that constraint. */
386 class constraint_manager
389 constraint_manager (region_model_manager
*mgr
) : m_mgr (mgr
) {}
390 constraint_manager (const constraint_manager
&other
);
391 virtual ~constraint_manager () {}
393 constraint_manager
& operator= (const constraint_manager
&other
);
395 hashval_t
hash () const;
396 bool operator== (const constraint_manager
&other
) const;
397 bool operator!= (const constraint_manager
&other
) const
399 return !(*this == other
);
402 void print (pretty_printer
*pp
) const;
403 void dump_to_pp (pretty_printer
*pp
, bool multiline
) const;
404 void dump (FILE *fp
) const;
407 json::object
*to_json () const;
409 const equiv_class
&get_equiv_class_by_index (unsigned idx
) const
411 return *m_equiv_classes
[idx
];
413 equiv_class
&get_equiv_class_by_index (unsigned idx
)
415 return *m_equiv_classes
[idx
];
418 equiv_class
&get_equiv_class (const svalue
*sval
)
420 equiv_class_id ec_id
= get_or_add_equiv_class (sval
);
421 return ec_id
.get_obj (*this);
424 bool add_constraint (const svalue
*lhs
,
428 bool add_constraint (equiv_class_id lhs_ec_id
,
430 equiv_class_id rhs_ec_id
);
432 void add_unknown_constraint (equiv_class_id lhs_ec_id
,
434 equiv_class_id rhs_ec_id
);
436 bool add_bounded_ranges (const svalue
*sval
,
437 const bounded_ranges
*ranges
);
439 bool get_equiv_class_by_svalue (const svalue
*sval
,
440 equiv_class_id
*out
) const;
441 equiv_class_id
get_or_add_equiv_class (const svalue
*sval
);
442 tristate
eval_condition (equiv_class_id lhs
,
444 equiv_class_id rhs
) const;
445 tristate
eval_condition (equiv_class_id lhs_ec
,
447 tree rhs_const
) const;
448 tristate
eval_condition (const svalue
*lhs
,
450 const svalue
*rhs
) const;
451 range
get_ec_bounds (equiv_class_id ec_id
) const;
453 /* PurgeCriteria should have:
454 bool should_purge_p (const svalue *sval) const. */
455 template <typename PurgeCriteria
>
456 void purge (const PurgeCriteria
&p
, purge_stats
*stats
);
458 void on_liveness_change (const svalue_set
&live_svalues
,
459 const region_model
*model
);
460 void purge_state_involving (const svalue
*sval
);
462 void canonicalize ();
464 static void merge (const constraint_manager
&cm_a
,
465 const constraint_manager
&cm_b
,
466 constraint_manager
*out
);
468 void for_each_fact (fact_visitor
*) const;
470 void validate () const;
472 bounded_ranges_manager
*get_range_manager () const;
474 auto_delete_vec
<equiv_class
> m_equiv_classes
;
475 auto_vec
<constraint
> m_constraints
;
476 auto_vec
<bounded_ranges_constraint
> m_bounded_ranges_constraints
;
479 void add_constraint_internal (equiv_class_id lhs_id
,
480 enum constraint_op c_op
,
481 equiv_class_id rhs_id
);
483 region_model_manager
*m_mgr
;
488 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */