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