]>
Commit | Line | Data |
---|---|---|
757bf1df DM |
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>. | |
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 | ||
28 | /* Abstract base class for specifying how state should be purged. */ | |
29 | ||
30 | class purge_criteria | |
31 | { | |
32 | public: | |
33 | virtual ~purge_criteria () {} | |
34 | virtual bool should_purge_p (svalue_id sid) const = 0; | |
35 | }; | |
36 | ||
37 | /* An equivalence class within a constraint manager: a set of | |
38 | svalue_ids that are known to all be equal to each other, | |
39 | together with an optional tree constant that they are equal to. */ | |
40 | ||
41 | class equiv_class | |
42 | { | |
43 | public: | |
44 | equiv_class (); | |
45 | equiv_class (const equiv_class &other); | |
46 | ||
47 | hashval_t hash () const; | |
48 | bool operator== (const equiv_class &other); | |
49 | ||
50 | void add (svalue_id sid, const constraint_manager &cm); | |
51 | bool del (svalue_id sid); | |
52 | ||
53 | tree get_any_constant () const { return m_constant; } | |
54 | ||
55 | svalue_id get_representative () const; | |
56 | ||
57 | void remap_svalue_ids (const svalue_id_map &map); | |
58 | ||
59 | void canonicalize (); | |
60 | ||
61 | void print (pretty_printer *pp) const; | |
62 | ||
63 | /* An equivalence class can contain multiple constants (e.g. multiple | |
64 | different zeroes, for different types); these are just for the last | |
65 | constant added. */ | |
66 | tree m_constant; | |
67 | svalue_id m_cst_sid; | |
68 | ||
69 | // TODO: should this be a set rather than a vec? | |
70 | auto_vec<svalue_id> m_vars; | |
71 | }; | |
72 | ||
73 | /* The various kinds of constraint. */ | |
74 | ||
75 | enum constraint_op | |
76 | { | |
77 | CONSTRAINT_NE, | |
78 | CONSTRAINT_LT, | |
79 | CONSTRAINT_LE | |
80 | }; | |
81 | ||
82 | const char *constraint_op_code (enum constraint_op c_op); | |
83 | ||
84 | /* An ID for an equiv_class within a constraint_manager. Internally, this | |
85 | is an index into a vector of equiv_class * within the constraint_manager. */ | |
86 | ||
87 | class equiv_class_id | |
88 | { | |
89 | public: | |
90 | static equiv_class_id null () { return equiv_class_id (-1); } | |
91 | ||
92 | equiv_class_id (unsigned idx) : m_idx (idx) {} | |
93 | const equiv_class &get_obj (const constraint_manager &cm) const; | |
94 | equiv_class &get_obj (constraint_manager &cm) const; | |
95 | ||
96 | bool operator== (const equiv_class_id &other) const | |
97 | { | |
98 | return m_idx == other.m_idx; | |
99 | } | |
100 | bool operator!= (const equiv_class_id &other) const | |
101 | { | |
102 | return m_idx != other.m_idx; | |
103 | } | |
104 | ||
105 | bool null_p () const { return m_idx == -1; } | |
106 | ||
107 | static equiv_class_id from_int (int idx) { return equiv_class_id (idx); } | |
108 | int as_int () const { return m_idx; } | |
109 | ||
110 | void print (pretty_printer *pp) const; | |
111 | ||
112 | void update_for_removal (equiv_class_id other) | |
113 | { | |
114 | if (m_idx > other.m_idx) | |
115 | m_idx--; | |
116 | } | |
117 | ||
118 | int m_idx; | |
119 | }; | |
120 | ||
121 | /* A relationship between two equivalence classes in a constraint_manager. */ | |
122 | ||
123 | class constraint | |
124 | { | |
125 | public: | |
126 | constraint (equiv_class_id lhs, enum constraint_op c_op, equiv_class_id rhs) | |
127 | : m_lhs (lhs), m_op (c_op), m_rhs (rhs) | |
128 | { | |
129 | gcc_assert (!lhs.null_p ()); | |
130 | gcc_assert (!rhs.null_p ()); | |
131 | } | |
132 | ||
133 | void print (pretty_printer *pp, const constraint_manager &cm) const; | |
134 | ||
135 | hashval_t hash () const; | |
136 | bool operator== (const constraint &other) const; | |
137 | ||
138 | /* Is this an ordering, rather than a "!=". */ | |
139 | bool is_ordering_p () const | |
140 | { | |
141 | return m_op != CONSTRAINT_NE; | |
142 | } | |
143 | ||
144 | equiv_class_id m_lhs; | |
145 | enum constraint_op m_op; | |
146 | equiv_class_id m_rhs; | |
147 | }; | |
148 | ||
149 | /* An abstract base class for use with constraint_manager::for_each_fact. */ | |
150 | ||
151 | class fact_visitor | |
152 | { | |
153 | public: | |
154 | virtual ~fact_visitor () {} | |
155 | virtual void on_fact (svalue_id lhs, enum tree_code, svalue_id rhs) = 0; | |
156 | }; | |
157 | ||
158 | /* A collection of equivalence classes and constraints on them. | |
159 | ||
160 | Given N svalues, this can be thought of as representing a subset of | |
161 | N-dimensional space. When we call add_constraint, | |
162 | we are effectively taking an intersection with that constraint. */ | |
163 | ||
164 | class constraint_manager | |
165 | { | |
166 | public: | |
167 | constraint_manager () {} | |
168 | constraint_manager (const constraint_manager &other); | |
169 | virtual ~constraint_manager () {} | |
170 | ||
171 | virtual constraint_manager *clone (region_model *) const = 0; | |
172 | virtual tree maybe_get_constant (svalue_id sid) const = 0; | |
173 | virtual svalue_id get_sid_for_constant (tree cst) const = 0; | |
174 | virtual int get_num_svalues () const = 0; | |
175 | ||
176 | constraint_manager& operator= (const constraint_manager &other); | |
177 | ||
178 | hashval_t hash () const; | |
179 | bool operator== (const constraint_manager &other) const; | |
180 | bool operator!= (const constraint_manager &other) const | |
181 | { | |
182 | return !(*this == other); | |
183 | } | |
184 | ||
185 | void print (pretty_printer *pp) const; | |
186 | void dump_to_pp (pretty_printer *pp) const; | |
187 | void dump (FILE *fp) const; | |
188 | void dump () const; | |
189 | ||
190 | const equiv_class &get_equiv_class_by_index (unsigned idx) const | |
191 | { | |
192 | return *m_equiv_classes[idx]; | |
193 | } | |
194 | equiv_class &get_equiv_class_by_index (unsigned idx) | |
195 | { | |
196 | return *m_equiv_classes[idx]; | |
197 | } | |
198 | ||
199 | equiv_class &get_equiv_class (svalue_id sid) | |
200 | { | |
201 | equiv_class_id ec_id = get_or_add_equiv_class (sid); | |
202 | return ec_id.get_obj (*this); | |
203 | } | |
204 | ||
205 | bool add_constraint (svalue_id lhs, enum tree_code op, svalue_id rhs); | |
206 | ||
207 | bool add_constraint (equiv_class_id lhs_ec_id, | |
208 | enum tree_code op, | |
209 | equiv_class_id rhs_ec_id); | |
210 | ||
211 | bool get_equiv_class_by_sid (svalue_id sid, equiv_class_id *out) const; | |
212 | equiv_class_id get_or_add_equiv_class (svalue_id sid); | |
213 | tristate eval_condition (equiv_class_id lhs, | |
214 | enum tree_code op, | |
215 | equiv_class_id rhs); | |
216 | tristate eval_condition (svalue_id lhs, | |
217 | enum tree_code op, | |
218 | svalue_id rhs); | |
219 | ||
220 | void purge (const purge_criteria &p, purge_stats *stats); | |
221 | ||
222 | void remap_svalue_ids (const svalue_id_map &map); | |
223 | ||
224 | void canonicalize (unsigned num_svalue_ids); | |
225 | ||
226 | static void merge (const constraint_manager &cm_a, | |
227 | const constraint_manager &cm_b, | |
228 | constraint_manager *out, | |
229 | const model_merger &merger); | |
230 | ||
231 | void for_each_fact (fact_visitor *) const; | |
232 | ||
233 | void validate () const; | |
234 | ||
235 | auto_delete_vec<equiv_class> m_equiv_classes; | |
236 | auto_vec<constraint> m_constraints; | |
237 | ||
238 | private: | |
239 | static void clean_merger_input (const constraint_manager &cm_in, | |
240 | const one_way_svalue_id_map &map_sid_to_m, | |
241 | constraint_manager *out); | |
242 | ||
243 | void add_constraint_internal (equiv_class_id lhs_id, | |
244 | enum constraint_op c_op, | |
245 | equiv_class_id rhs_id); | |
246 | }; | |
247 | ||
75038aa6 DM |
248 | } // namespace ana |
249 | ||
757bf1df | 250 | #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */ |