Mercurial > hg > CbC > CbC_gcc
comparison gcc/analyzer/constraint-manager.h @ 145:1830386684a0
gcc-9.2.0
author | anatofuz |
---|---|
date | Thu, 13 Feb 2020 11:34:05 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
131:84e7813d76e9 | 145:1830386684a0 |
---|---|
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 | |
24 namespace ana { | |
25 | |
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 | |
248 } // namespace ana | |
249 | |
250 #endif /* GCC_ANALYZER_CONSTRAINT_MANAGER_H */ |