]>
Commit | Line | Data |
---|---|---|
757bf1df | 1 | /* Tracking equivalence classes and constraints at a point on an execution path. |
99dee823 | 2 | Copyright (C) 2019-2021 Free Software Foundation, Inc. |
757bf1df DM |
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 | ||
75038aa6 DM |
24 | namespace ana { |
25 | ||
757bf1df DM |
26 | class constraint_manager; |
27 | ||
808f4dfe | 28 | /* One of the end-points of a range. */ |
757bf1df | 29 | |
808f4dfe | 30 | struct bound |
757bf1df | 31 | { |
808f4dfe DM |
32 | bound () : m_constant (NULL_TREE), m_closed (false) {} |
33 | bound (tree constant, bool closed) | |
34 | : m_constant (constant), m_closed (closed) {} | |
35 | ||
36 | void ensure_closed (bool is_upper); | |
37 | ||
38 | const char * get_relation_as_str () const; | |
39 | ||
40 | tree m_constant; | |
41 | bool m_closed; | |
42 | }; | |
43 | ||
44 | /* A range of values, used for determining if a value has been | |
45 | constrained to just one possible constant value. */ | |
46 | ||
47 | struct range | |
48 | { | |
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) {} | |
52 | ||
53 | void dump_to_pp (pretty_printer *pp) const; | |
54 | void dump () const; | |
55 | ||
56 | tree constrained_to_single_element (); | |
57 | ||
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; | |
62 | ||
63 | bound m_lower_bound; | |
64 | bound m_upper_bound; | |
757bf1df DM |
65 | }; |
66 | ||
67 | /* An equivalence class within a constraint manager: a set of | |
808f4dfe | 68 | svalues that are known to all be equal to each other, |
757bf1df DM |
69 | together with an optional tree constant that they are equal to. */ |
70 | ||
71 | class equiv_class | |
72 | { | |
73 | public: | |
74 | equiv_class (); | |
75 | equiv_class (const equiv_class &other); | |
76 | ||
77 | hashval_t hash () const; | |
78 | bool operator== (const equiv_class &other); | |
79 | ||
808f4dfe DM |
80 | void add (const svalue *sval); |
81 | bool del (const svalue *sval); | |
757bf1df DM |
82 | |
83 | tree get_any_constant () const { return m_constant; } | |
84 | ||
808f4dfe | 85 | const svalue *get_representative () const; |
757bf1df DM |
86 | |
87 | void canonicalize (); | |
88 | ||
89 | void print (pretty_printer *pp) const; | |
90 | ||
809192e7 DM |
91 | json::object *to_json () const; |
92 | ||
757bf1df DM |
93 | /* An equivalence class can contain multiple constants (e.g. multiple |
94 | different zeroes, for different types); these are just for the last | |
95 | constant added. */ | |
96 | tree m_constant; | |
808f4dfe | 97 | const svalue *m_cst_sval; |
757bf1df DM |
98 | |
99 | // TODO: should this be a set rather than a vec? | |
808f4dfe | 100 | auto_vec<const svalue *> m_vars; |
757bf1df DM |
101 | }; |
102 | ||
103 | /* The various kinds of constraint. */ | |
104 | ||
105 | enum constraint_op | |
106 | { | |
107 | CONSTRAINT_NE, | |
108 | CONSTRAINT_LT, | |
109 | CONSTRAINT_LE | |
110 | }; | |
111 | ||
112 | const char *constraint_op_code (enum constraint_op c_op); | |
113 | ||
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. */ | |
116 | ||
117 | class equiv_class_id | |
118 | { | |
119 | public: | |
120 | static equiv_class_id null () { return equiv_class_id (-1); } | |
121 | ||
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; | |
125 | ||
126 | bool operator== (const equiv_class_id &other) const | |
127 | { | |
128 | return m_idx == other.m_idx; | |
129 | } | |
130 | bool operator!= (const equiv_class_id &other) const | |
131 | { | |
132 | return m_idx != other.m_idx; | |
133 | } | |
134 | ||
135 | bool null_p () const { return m_idx == -1; } | |
136 | ||
137 | static equiv_class_id from_int (int idx) { return equiv_class_id (idx); } | |
138 | int as_int () const { return m_idx; } | |
139 | ||
140 | void print (pretty_printer *pp) const; | |
141 | ||
142 | void update_for_removal (equiv_class_id other) | |
143 | { | |
144 | if (m_idx > other.m_idx) | |
145 | m_idx--; | |
146 | } | |
147 | ||
148 | int m_idx; | |
149 | }; | |
150 | ||
151 | /* A relationship between two equivalence classes in a constraint_manager. */ | |
152 | ||
153 | class constraint | |
154 | { | |
155 | public: | |
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) | |
158 | { | |
159 | gcc_assert (!lhs.null_p ()); | |
160 | gcc_assert (!rhs.null_p ()); | |
161 | } | |
162 | ||
163 | void print (pretty_printer *pp, const constraint_manager &cm) const; | |
164 | ||
809192e7 DM |
165 | json::object *to_json () const; |
166 | ||
757bf1df DM |
167 | hashval_t hash () const; |
168 | bool operator== (const constraint &other) const; | |
169 | ||
170 | /* Is this an ordering, rather than a "!=". */ | |
171 | bool is_ordering_p () const | |
172 | { | |
173 | return m_op != CONSTRAINT_NE; | |
174 | } | |
175 | ||
808f4dfe DM |
176 | bool implied_by (const constraint &other, |
177 | const constraint_manager &cm) const; | |
178 | ||
757bf1df DM |
179 | equiv_class_id m_lhs; |
180 | enum constraint_op m_op; | |
181 | equiv_class_id m_rhs; | |
182 | }; | |
183 | ||
184 | /* An abstract base class for use with constraint_manager::for_each_fact. */ | |
185 | ||
186 | class fact_visitor | |
187 | { | |
188 | public: | |
189 | virtual ~fact_visitor () {} | |
808f4dfe DM |
190 | virtual void on_fact (const svalue *lhs, |
191 | enum tree_code, | |
192 | const svalue *rhs) = 0; | |
757bf1df DM |
193 | }; |
194 | ||
195 | /* A collection of equivalence classes and constraints on them. | |
196 | ||
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. */ | |
200 | ||
201 | class constraint_manager | |
202 | { | |
203 | public: | |
808f4dfe | 204 | constraint_manager (region_model_manager *mgr) : m_mgr (mgr) {} |
757bf1df DM |
205 | constraint_manager (const constraint_manager &other); |
206 | virtual ~constraint_manager () {} | |
207 | ||
757bf1df DM |
208 | constraint_manager& operator= (const constraint_manager &other); |
209 | ||
210 | hashval_t hash () const; | |
211 | bool operator== (const constraint_manager &other) const; | |
212 | bool operator!= (const constraint_manager &other) const | |
213 | { | |
214 | return !(*this == other); | |
215 | } | |
216 | ||
217 | void print (pretty_printer *pp) const; | |
808f4dfe | 218 | void dump_to_pp (pretty_printer *pp, bool multiline) const; |
757bf1df DM |
219 | void dump (FILE *fp) const; |
220 | void dump () const; | |
221 | ||
809192e7 DM |
222 | json::object *to_json () const; |
223 | ||
757bf1df DM |
224 | const equiv_class &get_equiv_class_by_index (unsigned idx) const |
225 | { | |
226 | return *m_equiv_classes[idx]; | |
227 | } | |
228 | equiv_class &get_equiv_class_by_index (unsigned idx) | |
229 | { | |
230 | return *m_equiv_classes[idx]; | |
231 | } | |
232 | ||
808f4dfe | 233 | equiv_class &get_equiv_class (const svalue *sval) |
757bf1df | 234 | { |
808f4dfe | 235 | equiv_class_id ec_id = get_or_add_equiv_class (sval); |
757bf1df DM |
236 | return ec_id.get_obj (*this); |
237 | } | |
238 | ||
808f4dfe DM |
239 | bool add_constraint (const svalue *lhs, |
240 | enum tree_code op, | |
241 | const svalue *rhs); | |
757bf1df DM |
242 | |
243 | bool add_constraint (equiv_class_id lhs_ec_id, | |
244 | enum tree_code op, | |
245 | equiv_class_id rhs_ec_id); | |
246 | ||
808f4dfe DM |
247 | void add_unknown_constraint (equiv_class_id lhs_ec_id, |
248 | enum tree_code op, | |
249 | equiv_class_id rhs_ec_id); | |
250 | ||
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); | |
757bf1df DM |
254 | tristate eval_condition (equiv_class_id lhs, |
255 | enum tree_code op, | |
808f4dfe DM |
256 | equiv_class_id rhs) const; |
257 | tristate eval_condition (equiv_class_id lhs_ec, | |
258 | enum tree_code op, | |
259 | tree rhs_const) const; | |
260 | tristate eval_condition (const svalue *lhs, | |
757bf1df | 261 | enum tree_code op, |
808f4dfe DM |
262 | const svalue *rhs) const; |
263 | range get_ec_bounds (equiv_class_id ec_id) const; | |
757bf1df | 264 | |
808f4dfe DM |
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); | |
757bf1df | 269 | |
808f4dfe DM |
270 | void on_liveness_change (const svalue_set &live_svalues, |
271 | const region_model *model); | |
757bf1df | 272 | |
808f4dfe | 273 | void canonicalize (); |
757bf1df DM |
274 | |
275 | static void merge (const constraint_manager &cm_a, | |
276 | const constraint_manager &cm_b, | |
c710051a | 277 | constraint_manager *out); |
757bf1df DM |
278 | |
279 | void for_each_fact (fact_visitor *) const; | |
280 | ||
281 | void validate () const; | |
282 | ||
283 | auto_delete_vec<equiv_class> m_equiv_classes; | |
284 | auto_vec<constraint> m_constraints; | |
285 | ||
286 | private: | |
757bf1df DM |
287 | void add_constraint_internal (equiv_class_id lhs_id, |
288 | enum constraint_op c_op, | |
289 | equiv_class_id rhs_id); | |
808f4dfe DM |
290 | |
291 | region_model_manager *m_mgr; | |
757bf1df DM |
292 | }; |
293 | ||
75038aa6 DM |
294 | } // namespace ana |
295 | ||
757bf1df | 296 | #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */ |