1 /* Tracking equivalence classes and constraints at a point on an execution path.
2 Copyright (C) 2019-2020 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 /* An equivalence class within a constraint manager: a set of
68 svalues that are known to all be equal to each other,
69 together with an optional tree constant that they are equal to. */
75 equiv_class (const equiv_class
&other
);
77 hashval_t
hash () const;
78 bool operator== (const equiv_class
&other
);
80 void add (const svalue
*sval
);
81 bool del (const svalue
*sval
);
83 tree
get_any_constant () const { return m_constant
; }
85 const svalue
*get_representative () const;
89 void print (pretty_printer
*pp
) const;
91 json::object
*to_json () const;
93 /* An equivalence class can contain multiple constants (e.g. multiple
94 different zeroes, for different types); these are just for the last
97 const svalue
*m_cst_sval
;
99 // TODO: should this be a set rather than a vec?
100 auto_vec
<const svalue
*> m_vars
;
103 /* The various kinds of constraint. */
112 const char *constraint_op_code (enum constraint_op c_op
);
114 /* An ID for an equiv_class within a constraint_manager. Internally, this
115 is an index into a vector of equiv_class * within the constraint_manager. */
120 static equiv_class_id
null () { return equiv_class_id (-1); }
122 equiv_class_id (unsigned idx
) : m_idx (idx
) {}
123 const equiv_class
&get_obj (const constraint_manager
&cm
) const;
124 equiv_class
&get_obj (constraint_manager
&cm
) const;
126 bool operator== (const equiv_class_id
&other
) const
128 return m_idx
== other
.m_idx
;
130 bool operator!= (const equiv_class_id
&other
) const
132 return m_idx
!= other
.m_idx
;
135 bool null_p () const { return m_idx
== -1; }
137 static equiv_class_id
from_int (int idx
) { return equiv_class_id (idx
); }
138 int as_int () const { return m_idx
; }
140 void print (pretty_printer
*pp
) const;
142 void update_for_removal (equiv_class_id other
)
144 if (m_idx
> other
.m_idx
)
151 /* A relationship between two equivalence classes in a constraint_manager. */
156 constraint (equiv_class_id lhs
, enum constraint_op c_op
, equiv_class_id rhs
)
157 : m_lhs (lhs
), m_op (c_op
), m_rhs (rhs
)
159 gcc_assert (!lhs
.null_p ());
160 gcc_assert (!rhs
.null_p ());
163 void print (pretty_printer
*pp
, const constraint_manager
&cm
) const;
165 json::object
*to_json () const;
167 hashval_t
hash () const;
168 bool operator== (const constraint
&other
) const;
170 /* Is this an ordering, rather than a "!=". */
171 bool is_ordering_p () const
173 return m_op
!= CONSTRAINT_NE
;
176 bool implied_by (const constraint
&other
,
177 const constraint_manager
&cm
) const;
179 equiv_class_id m_lhs
;
180 enum constraint_op m_op
;
181 equiv_class_id m_rhs
;
184 /* An abstract base class for use with constraint_manager::for_each_fact. */
189 virtual ~fact_visitor () {}
190 virtual void on_fact (const svalue
*lhs
,
192 const svalue
*rhs
) = 0;
195 /* A collection of equivalence classes and constraints on them.
197 Given N svalues, this can be thought of as representing a subset of
198 N-dimensional space. When we call add_constraint,
199 we are effectively taking an intersection with that constraint. */
201 class constraint_manager
204 constraint_manager (region_model_manager
*mgr
) : m_mgr (mgr
) {}
205 constraint_manager (const constraint_manager
&other
);
206 virtual ~constraint_manager () {}
208 constraint_manager
& operator= (const constraint_manager
&other
);
210 hashval_t
hash () const;
211 bool operator== (const constraint_manager
&other
) const;
212 bool operator!= (const constraint_manager
&other
) const
214 return !(*this == other
);
217 void print (pretty_printer
*pp
) const;
218 void dump_to_pp (pretty_printer
*pp
, bool multiline
) const;
219 void dump (FILE *fp
) const;
222 json::object
*to_json () const;
224 const equiv_class
&get_equiv_class_by_index (unsigned idx
) const
226 return *m_equiv_classes
[idx
];
228 equiv_class
&get_equiv_class_by_index (unsigned idx
)
230 return *m_equiv_classes
[idx
];
233 equiv_class
&get_equiv_class (const svalue
*sval
)
235 equiv_class_id ec_id
= get_or_add_equiv_class (sval
);
236 return ec_id
.get_obj (*this);
239 bool add_constraint (const svalue
*lhs
,
243 bool add_constraint (equiv_class_id lhs_ec_id
,
245 equiv_class_id rhs_ec_id
);
247 void add_unknown_constraint (equiv_class_id lhs_ec_id
,
249 equiv_class_id rhs_ec_id
);
251 bool get_equiv_class_by_svalue (const svalue
*sval
,
252 equiv_class_id
*out
) const;
253 equiv_class_id
get_or_add_equiv_class (const svalue
*sval
);
254 tristate
eval_condition (equiv_class_id lhs
,
256 equiv_class_id rhs
) const;
257 tristate
eval_condition (equiv_class_id lhs_ec
,
259 tree rhs_const
) const;
260 tristate
eval_condition (const svalue
*lhs
,
262 const svalue
*rhs
) const;
263 range
get_ec_bounds (equiv_class_id ec_id
) const;
265 /* PurgeCriteria should have:
266 bool should_purge_p (const svalue *sval) const. */
267 template <typename PurgeCriteria
>
268 void purge (const PurgeCriteria
&p
, purge_stats
*stats
);
270 void on_liveness_change (const svalue_set
&live_svalues
,
271 const region_model
*model
);
273 void canonicalize ();
275 static void merge (const constraint_manager
&cm_a
,
276 const constraint_manager
&cm_b
,
277 constraint_manager
*out
,
278 const model_merger
&merger
);
280 void for_each_fact (fact_visitor
*) const;
282 void validate () const;
284 auto_delete_vec
<equiv_class
> m_equiv_classes
;
285 auto_vec
<constraint
> m_constraints
;
288 void add_constraint_internal (equiv_class_id lhs_id
,
289 enum constraint_op c_op
,
290 equiv_class_id rhs_id
);
292 region_model_manager
*m_mgr
;
297 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */