Branch data Line data Source code
1 : : /* Classes for representing the state of interest at a given path of analysis.
2 : : Copyright (C) 2019-2025 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 : 3328 : class extrinsic_state
34 : : {
35 : : public:
36 : 3316 : extrinsic_state (std::vector<std::unique_ptr<state_machine>> &&checkers,
37 : : engine *eng,
38 : : logger *logger = nullptr)
39 : 3316 : : m_checkers (std::move (checkers)),
40 : 3316 : m_logger (logger),
41 : 3316 : 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 : 13996097 : const state_machine &get_sm (int idx) const
56 : : {
57 : 12733811 : return *m_checkers[idx];
58 : : }
59 : :
60 : 498 : const char *get_name (int idx) const
61 : : {
62 : 498 : return m_checkers[idx]->get_name ();
63 : : }
64 : :
65 : 3097166 : unsigned get_num_checkers () const { return m_checkers.size (); }
66 : :
67 : 588961 : 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 : 672904 : 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 : 26910268 : 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 : 150646 : entry_t (state_machine::state_t state,
104 : : const svalue *origin)
105 : 150646 : : m_state (state), m_origin (origin)
106 : : {}
107 : :
108 : 421421 : bool operator== (const entry_t &other) const
109 : : {
110 : 421421 : return (m_state == other.m_state
111 : 409581 : && m_origin == other.m_origin);
112 : : }
113 : 421421 : bool operator!= (const entry_t &other) const
114 : : {
115 : 850199 : 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 : 1488324 : bool operator!= (const sm_state_map &other) const
147 : : {
148 : 1488324 : 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 : 1678900 : iterator_t begin () const { return m_map.begin (); }
190 : 1989884 : iterator_t end () const { return m_map.end (); }
191 : 987096 : 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 : 32357 : bool operator!= (const program_state &other) const
235 : : {
236 : 32357 : 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 : : void push_call (exploded_graph &eg,
268 : : exploded_node *enode,
269 : : const gcall &call_stmt,
270 : : uncertainty_t *uncertainty);
271 : :
272 : : void returning_call (exploded_graph &eg,
273 : : exploded_node *enode,
274 : : const gcall &call_stmt,
275 : : uncertainty_t *uncertainty);
276 : :
277 : :
278 : : bool on_edge (exploded_graph &eg,
279 : : exploded_node *enode,
280 : : const superedge *succ,
281 : : uncertainty_t *uncertainty);
282 : :
283 : : program_state prune_for_point (exploded_graph &eg,
284 : : const program_point &point,
285 : : exploded_node *enode_for_diag,
286 : : uncertainty_t *uncertainty) const;
287 : :
288 : : tree get_representative_tree (const svalue *sval) const;
289 : :
290 : 1005369 : bool can_purge_p (const extrinsic_state &ext_state,
291 : : const svalue *sval) const
292 : : {
293 : : /* Don't purge vars that have non-purgeable sm state, to avoid
294 : : generating false "leak" complaints. */
295 : 1005369 : int i;
296 : 1005369 : sm_state_map *smap;
297 : 7696161 : FOR_EACH_VEC_ELT (m_checker_states, i, smap)
298 : : {
299 : 6740803 : const state_machine &sm = ext_state.get_sm (i);
300 : 6740803 : if (!sm.can_purge_p (smap->get_state (sval, ext_state)))
301 : : return false;
302 : : }
303 : : return true;
304 : : }
305 : :
306 : : bool can_purge_base_region_p (const extrinsic_state &ext_state,
307 : : const region *base_reg) const;
308 : :
309 : : bool can_merge_with_p (const program_state &other,
310 : : const extrinsic_state &ext_state,
311 : : const program_point &point,
312 : : program_state *out) const;
313 : :
314 : : void validate (const extrinsic_state &ext_state) const;
315 : :
316 : : static void detect_leaks (const program_state &src_state,
317 : : const program_state &dest_state,
318 : : const svalue *extra_sval,
319 : : const extrinsic_state &ext_state,
320 : : region_model_context *ctxt);
321 : :
322 : : bool replay_call_summary (call_summary_replay &r,
323 : : const program_state &summary);
324 : :
325 : : void impl_call_analyzer_dump_state (const gcall &call,
326 : : const extrinsic_state &ext_state,
327 : : region_model_context *ctxt);
328 : :
329 : : /* TODO: lose the pointer here (const-correctness issues?). */
330 : : region_model *m_region_model;
331 : : auto_delete_vec<sm_state_map> m_checker_states;
332 : :
333 : : /* If false, then don't attempt to explore further states along this path.
334 : : For use in "handling" lvalues for tree codes we haven't yet
335 : : implemented. */
336 : : bool m_valid;
337 : : };
338 : :
339 : : /* An abstract base class for use with for_each_state_change. */
340 : :
341 : 52290 : class state_change_visitor
342 : : {
343 : : public:
344 : 52290 : virtual ~state_change_visitor () {}
345 : :
346 : : /* Return true for early exit, false to keep iterating. */
347 : : virtual bool on_global_state_change (const state_machine &sm,
348 : : state_machine::state_t src_sm_val,
349 : : state_machine::state_t dst_sm_val) = 0;
350 : :
351 : : /* Return true for early exit, false to keep iterating. */
352 : : virtual bool on_state_change (const state_machine &sm,
353 : : state_machine::state_t src_sm_val,
354 : : state_machine::state_t dst_sm_val,
355 : : const svalue *dst_sval,
356 : : const svalue *dst_origin_sval) = 0;
357 : : };
358 : :
359 : : extern bool for_each_state_change (const program_state &src_state,
360 : : const program_state &dst_state,
361 : : const extrinsic_state &ext_state,
362 : : state_change_visitor *visitor);
363 : :
364 : : } // namespace ana
365 : :
366 : : #endif /* GCC_ANALYZER_PROGRAM_STATE_H */
|
