Branch data Line data Source code
1 : : /* Classes for representing the state of interest at a given path of analysis.
2 : : Copyright (C) 2019-2024 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_PROGRAM_STATE_H
22 : : #define GCC_ANALYZER_PROGRAM_STATE_H
23 : :
24 : : #include "text-art/widget.h"
25 : :
26 : : namespace ana {
27 : :
28 : : /* Data shared by all program_state instances. */
29 : :
30 : : class extrinsic_state
31 : : {
32 : : public:
33 : 3219 : extrinsic_state (auto_delete_vec <state_machine> &checkers,
34 : : engine *eng,
35 : : logger *logger = NULL)
36 : 3219 : : m_checkers (checkers), m_logger (logger), m_engine (eng)
37 : : {
38 : : }
39 : :
40 : 13528789 : const state_machine &get_sm (int idx) const
41 : : {
42 : 17520232 : return *m_checkers[idx];
43 : : }
44 : :
45 : 498 : const char *get_name (int idx) const
46 : : {
47 : 498 : return m_checkers[idx]->get_name ();
48 : : }
49 : :
50 : 5321993 : unsigned get_num_checkers () const { return m_checkers.length (); }
51 : :
52 : 573833 : logger *get_logger () const { return m_logger; }
53 : :
54 : : void dump_to_pp (pretty_printer *pp) const;
55 : : void dump_to_file (FILE *outf) const;
56 : : void dump () const;
57 : :
58 : : std::unique_ptr<json::object> to_json () const;
59 : :
60 : 655170 : engine *get_engine () const { return m_engine; }
61 : : region_model_manager *get_model_manager () const;
62 : :
63 : : bool get_sm_idx_by_name (const char *name, unsigned *out) const;
64 : :
65 : : private:
66 : : /* The state machines. */
67 : : auto_delete_vec <state_machine> &m_checkers;
68 : :
69 : : logger *m_logger;
70 : : engine *m_engine;
71 : : };
72 : :
73 : : /* Map from svalue * to state machine state, also capturing the origin of
74 : : each state. */
75 : :
76 : 25810294 : class sm_state_map
77 : : {
78 : : public:
79 : : /* An entry in the hash_map. */
80 : : struct entry_t
81 : : {
82 : : /* Default ctor needed by hash_map::empty. */
83 : : entry_t ()
84 : : : m_state (0), m_origin (NULL)
85 : : {
86 : : }
87 : :
88 : 154715 : entry_t (state_machine::state_t state,
89 : : const svalue *origin)
90 : 154715 : : m_state (state), m_origin (origin)
91 : : {}
92 : :
93 : 417876 : bool operator== (const entry_t &other) const
94 : : {
95 : 417876 : return (m_state == other.m_state
96 : 406029 : && m_origin == other.m_origin);
97 : : }
98 : 417876 : bool operator!= (const entry_t &other) const
99 : : {
100 : 845119 : return !(*this == other);
101 : : }
102 : :
103 : : static int cmp (const entry_t &entry_a, const entry_t &entry_b);
104 : :
105 : : state_machine::state_t m_state;
106 : : const svalue *m_origin;
107 : : };
108 : : typedef hash_map <const svalue *, entry_t> map_t;
109 : : typedef map_t::iterator iterator_t;
110 : :
111 : : sm_state_map (const state_machine &sm);
112 : :
113 : : sm_state_map *clone () const;
114 : :
115 : : void print (const region_model *model,
116 : : bool simple, bool multiline,
117 : : pretty_printer *pp) const;
118 : : void dump (bool simple) const;
119 : :
120 : : std::unique_ptr<json::object> to_json () const;
121 : :
122 : : std::unique_ptr<text_art::tree_widget>
123 : : make_dump_widget (const text_art::dump_widget_info &dwi,
124 : : const region_model *model) const;
125 : :
126 : : bool is_empty_p () const;
127 : :
128 : : hashval_t hash () const;
129 : :
130 : : bool operator== (const sm_state_map &other) const;
131 : 1465372 : bool operator!= (const sm_state_map &other) const
132 : : {
133 : 1465372 : return !(*this == other);
134 : : }
135 : :
136 : : state_machine::state_t get_state (const svalue *sval,
137 : : const extrinsic_state &ext_state) const;
138 : : const svalue *get_origin (const svalue *sval,
139 : : const extrinsic_state &ext_state) const;
140 : :
141 : : void set_state (region_model *model,
142 : : const svalue *sval,
143 : : state_machine::state_t state,
144 : : const svalue *origin,
145 : : const extrinsic_state &ext_state);
146 : : bool set_state (const equiv_class &ec,
147 : : state_machine::state_t state,
148 : : const svalue *origin,
149 : : const extrinsic_state &ext_state);
150 : : bool impl_set_state (const svalue *sval,
151 : : state_machine::state_t state,
152 : : const svalue *origin,
153 : : const extrinsic_state &ext_state);
154 : : void clear_any_state (const svalue *sval);
155 : : void clear_all_per_svalue_state ();
156 : :
157 : : void set_global_state (state_machine::state_t state);
158 : : state_machine::state_t get_global_state () const;
159 : :
160 : : void on_svalue_leak (const svalue *sval,
161 : : impl_region_model_context *ctxt);
162 : : void on_liveness_change (const svalue_set &live_svalues,
163 : : const region_model *model,
164 : : const extrinsic_state &ext_state,
165 : : impl_region_model_context *ctxt);
166 : :
167 : : void on_unknown_change (const svalue *sval,
168 : : bool is_mutable,
169 : : const extrinsic_state &ext_state);
170 : :
171 : : void purge_state_involving (const svalue *sval,
172 : : const extrinsic_state &ext_state);
173 : :
174 : 1603539 : iterator_t begin () const { return m_map.begin (); }
175 : 1910264 : iterator_t end () const { return m_map.end (); }
176 : 939992 : size_t elements () const { return m_map.elements (); }
177 : :
178 : : static int cmp (const sm_state_map &smap_a, const sm_state_map &smap_b);
179 : :
180 : : static const svalue *
181 : : canonicalize_svalue (const svalue *sval, const extrinsic_state &ext_state);
182 : :
183 : : bool replay_call_summary (call_summary_replay &r,
184 : : const sm_state_map &summary);
185 : :
186 : : bool can_merge_with_p (const sm_state_map &other,
187 : : const state_machine &sm,
188 : : const extrinsic_state &ext_state,
189 : : sm_state_map **out) const;
190 : :
191 : : private:
192 : : const state_machine &m_sm;
193 : : map_t m_map;
194 : : state_machine::state_t m_global_state;
195 : : };
196 : :
197 : : /* A class for representing the state of interest at a given path of
198 : : analysis.
199 : :
200 : : Currently this is a combination of:
201 : : (a) a region_model, giving:
202 : : (a.1) a hierarchy of memory regions
203 : : (a.2) values for the regions
204 : : (a.3) inequalities between values
205 : : (b) sm_state_maps per state machine, giving a sparse mapping of
206 : : values to states. */
207 : :
208 : : class program_state
209 : : {
210 : : public:
211 : : program_state (const extrinsic_state &ext_state);
212 : : program_state (const program_state &other);
213 : : program_state& operator= (const program_state &other);
214 : : program_state (program_state &&other);
215 : : ~program_state ();
216 : :
217 : : hashval_t hash () const;
218 : : bool operator== (const program_state &other) const;
219 : 31919 : bool operator!= (const program_state &other) const
220 : : {
221 : 31919 : return !(*this == other);
222 : : }
223 : :
224 : : void print (const extrinsic_state &ext_state,
225 : : pretty_printer *pp) const;
226 : :
227 : : void dump_to_pp (const extrinsic_state &ext_state, bool simple,
228 : : bool multiline, pretty_printer *pp) const;
229 : : void dump_to_file (const extrinsic_state &ext_state, bool simple,
230 : : bool multiline, FILE *outf) const;
231 : : void dump (const extrinsic_state &ext_state, bool simple) const;
232 : : void dump () const;
233 : :
234 : : std::unique_ptr<json::object>
235 : : to_json (const extrinsic_state &ext_state) const;
236 : :
237 : : std::unique_ptr<text_art::tree_widget>
238 : : make_dump_widget (const text_art::dump_widget_info &dwi) const;
239 : :
240 : : void push_frame (const extrinsic_state &ext_state, const function &fun);
241 : : const function * get_current_function () const;
242 : :
243 : : void push_call (exploded_graph &eg,
244 : : exploded_node *enode,
245 : : const gcall *call_stmt,
246 : : uncertainty_t *uncertainty);
247 : :
248 : : void returning_call (exploded_graph &eg,
249 : : exploded_node *enode,
250 : : const gcall *call_stmt,
251 : : uncertainty_t *uncertainty);
252 : :
253 : :
254 : : bool on_edge (exploded_graph &eg,
255 : : exploded_node *enode,
256 : : const superedge *succ,
257 : : uncertainty_t *uncertainty);
258 : :
259 : : program_state prune_for_point (exploded_graph &eg,
260 : : const program_point &point,
261 : : exploded_node *enode_for_diag,
262 : : uncertainty_t *uncertainty) const;
263 : :
264 : : tree get_representative_tree (const svalue *sval) const;
265 : :
266 : 982237 : bool can_purge_p (const extrinsic_state &ext_state,
267 : : const svalue *sval) const
268 : : {
269 : : /* Don't purge vars that have non-purgeable sm state, to avoid
270 : : generating false "leak" complaints. */
271 : 982237 : int i;
272 : 982237 : sm_state_map *smap;
273 : 7497901 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
274 : : {
275 : 6567623 : const state_machine &sm = ext_state.get_sm (i);
276 : 6567623 : if (!sm.can_purge_p (smap->get_state (sval, ext_state)))
277 : : return false;
278 : : }
279 : : return true;
280 : : }
281 : :
282 : : bool can_purge_base_region_p (const extrinsic_state &ext_state,
283 : : const region *base_reg) const;
284 : :
285 : : bool can_merge_with_p (const program_state &other,
286 : : const extrinsic_state &ext_state,
287 : : const program_point &point,
288 : : program_state *out) const;
289 : :
290 : : void validate (const extrinsic_state &ext_state) const;
291 : :
292 : : static void detect_leaks (const program_state &src_state,
293 : : const program_state &dest_state,
294 : : const svalue *extra_sval,
295 : : const extrinsic_state &ext_state,
296 : : region_model_context *ctxt);
297 : :
298 : : bool replay_call_summary (call_summary_replay &r,
299 : : const program_state &summary);
300 : :
301 : : void impl_call_analyzer_dump_state (const gcall *call,
302 : : const extrinsic_state &ext_state,
303 : : region_model_context *ctxt);
304 : :
305 : : /* TODO: lose the pointer here (const-correctness issues?). */
306 : : region_model *m_region_model;
307 : : auto_delete_vec<sm_state_map> m_checker_states;
308 : :
309 : : /* If false, then don't attempt to explore further states along this path.
310 : : For use in "handling" lvalues for tree codes we haven't yet
311 : : implemented. */
312 : : bool m_valid;
313 : : };
314 : :
315 : : /* An abstract base class for use with for_each_state_change. */
316 : :
317 : 49199 : class state_change_visitor
318 : : {
319 : : public:
320 : 49199 : virtual ~state_change_visitor () {}
321 : :
322 : : /* Return true for early exit, false to keep iterating. */
323 : : virtual bool on_global_state_change (const state_machine &sm,
324 : : state_machine::state_t src_sm_val,
325 : : state_machine::state_t dst_sm_val) = 0;
326 : :
327 : : /* Return true for early exit, false to keep iterating. */
328 : : virtual bool on_state_change (const state_machine &sm,
329 : : state_machine::state_t src_sm_val,
330 : : state_machine::state_t dst_sm_val,
331 : : const svalue *dst_sval,
332 : : const svalue *dst_origin_sval) = 0;
333 : : };
334 : :
335 : : extern bool for_each_state_change (const program_state &src_state,
336 : : const program_state &dst_state,
337 : : const extrinsic_state &ext_state,
338 : : state_change_visitor *visitor);
339 : :
340 : : } // namespace ana
341 : :
342 : : #endif /* GCC_ANALYZER_PROGRAM_STATE_H */
|
