1 /* Classes for representing the state of interest at a given path of analysis.
2 Copyright (C) 2019-2023 Free Software Foundation, Inc.
3 Contributed by David Malcolm <dmalcolm@redhat.com>.
5 This file is part of GCC.
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)
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.
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/>. */
21 #ifndef GCC_ANALYZER_PROGRAM_STATE_H
22 #define GCC_ANALYZER_PROGRAM_STATE_H
26 /* Data shared by all program_state instances. */
31 extrinsic_state (auto_delete_vec
<state_machine
> &checkers
,
33 logger
*logger
= NULL
)
34 : m_checkers (checkers
), m_logger (logger
), m_engine (eng
)
38 const state_machine
&get_sm (int idx
) const
40 return *m_checkers
[idx
];
43 const char *get_name (int idx
) const
45 return m_checkers
[idx
]->get_name ();
48 unsigned get_num_checkers () const { return m_checkers
.length (); }
50 logger
*get_logger () const { return m_logger
; }
52 void dump_to_pp (pretty_printer
*pp
) const;
53 void dump_to_file (FILE *outf
) const;
56 json::object
*to_json () const;
58 engine
*get_engine () const { return m_engine
; }
59 region_model_manager
*get_model_manager () const;
61 bool get_sm_idx_by_name (const char *name
, unsigned *out
) const;
64 /* The state machines. */
65 auto_delete_vec
<state_machine
> &m_checkers
;
71 /* Map from svalue * to state machine state, also capturing the origin of
77 /* An entry in the hash_map. */
80 /* Default ctor needed by hash_map::empty. */
82 : m_state (0), m_origin (NULL
)
86 entry_t (state_machine::state_t state
,
88 : m_state (state
), m_origin (origin
)
91 bool operator== (const entry_t
&other
) const
93 return (m_state
== other
.m_state
94 && m_origin
== other
.m_origin
);
96 bool operator!= (const entry_t
&other
) const
98 return !(*this == other
);
101 static int cmp (const entry_t
&entry_a
, const entry_t
&entry_b
);
103 state_machine::state_t m_state
;
104 const svalue
*m_origin
;
106 typedef hash_map
<const svalue
*, entry_t
> map_t
;
107 typedef map_t::iterator iterator_t
;
109 sm_state_map (const state_machine
&sm
);
111 sm_state_map
*clone () const;
113 void print (const region_model
*model
,
114 bool simple
, bool multiline
,
115 pretty_printer
*pp
) const;
116 void dump (bool simple
) const;
118 json::object
*to_json () const;
120 bool is_empty_p () const;
122 hashval_t
hash () const;
124 bool operator== (const sm_state_map
&other
) const;
125 bool operator!= (const sm_state_map
&other
) const
127 return !(*this == other
);
130 state_machine::state_t
get_state (const svalue
*sval
,
131 const extrinsic_state
&ext_state
) const;
132 const svalue
*get_origin (const svalue
*sval
,
133 const extrinsic_state
&ext_state
) const;
135 void set_state (region_model
*model
,
137 state_machine::state_t state
,
138 const svalue
*origin
,
139 const extrinsic_state
&ext_state
);
140 bool set_state (const equiv_class
&ec
,
141 state_machine::state_t state
,
142 const svalue
*origin
,
143 const extrinsic_state
&ext_state
);
144 bool impl_set_state (const svalue
*sval
,
145 state_machine::state_t state
,
146 const svalue
*origin
,
147 const extrinsic_state
&ext_state
);
148 void clear_any_state (const svalue
*sval
);
150 void set_global_state (state_machine::state_t state
);
151 state_machine::state_t
get_global_state () const;
153 void on_svalue_leak (const svalue
*sval
,
154 impl_region_model_context
*ctxt
);
155 void on_liveness_change (const svalue_set
&live_svalues
,
156 const region_model
*model
,
157 impl_region_model_context
*ctxt
);
159 void on_unknown_change (const svalue
*sval
,
161 const extrinsic_state
&ext_state
);
163 void purge_state_involving (const svalue
*sval
,
164 const extrinsic_state
&ext_state
);
166 iterator_t
begin () const { return m_map
.begin (); }
167 iterator_t
end () const { return m_map
.end (); }
168 size_t elements () const { return m_map
.elements (); }
170 static int cmp (const sm_state_map
&smap_a
, const sm_state_map
&smap_b
);
172 static const svalue
*
173 canonicalize_svalue (const svalue
*sval
, const extrinsic_state
&ext_state
);
175 bool replay_call_summary (call_summary_replay
&r
,
176 const sm_state_map
&summary
);
178 bool can_merge_with_p (const sm_state_map
&other
,
179 const state_machine
&sm
,
180 const extrinsic_state
&ext_state
,
181 sm_state_map
**out
) const;
184 const state_machine
&m_sm
;
186 state_machine::state_t m_global_state
;
189 /* A class for representing the state of interest at a given path of
192 Currently this is a combination of:
193 (a) a region_model, giving:
194 (a.1) a hierarchy of memory regions
195 (a.2) values for the regions
196 (a.3) inequalities between values
197 (b) sm_state_maps per state machine, giving a sparse mapping of
203 program_state (const extrinsic_state
&ext_state
);
204 program_state (const program_state
&other
);
205 program_state
& operator= (const program_state
&other
);
206 program_state (program_state
&&other
);
209 hashval_t
hash () const;
210 bool operator== (const program_state
&other
) const;
211 bool operator!= (const program_state
&other
) const
213 return !(*this == other
);
216 void print (const extrinsic_state
&ext_state
,
217 pretty_printer
*pp
) const;
219 void dump_to_pp (const extrinsic_state
&ext_state
, bool simple
,
220 bool multiline
, pretty_printer
*pp
) const;
221 void dump_to_file (const extrinsic_state
&ext_state
, bool simple
,
222 bool multiline
, FILE *outf
) const;
223 void dump (const extrinsic_state
&ext_state
, bool simple
) const;
225 json::object
*to_json (const extrinsic_state
&ext_state
) const;
227 void push_frame (const extrinsic_state
&ext_state
, function
*fun
);
228 function
* get_current_function () const;
230 void push_call (exploded_graph
&eg
,
231 exploded_node
*enode
,
232 const gcall
*call_stmt
,
233 uncertainty_t
*uncertainty
);
235 void returning_call (exploded_graph
&eg
,
236 exploded_node
*enode
,
237 const gcall
*call_stmt
,
238 uncertainty_t
*uncertainty
);
241 bool on_edge (exploded_graph
&eg
,
242 exploded_node
*enode
,
243 const superedge
*succ
,
244 uncertainty_t
*uncertainty
);
246 program_state
prune_for_point (exploded_graph
&eg
,
247 const program_point
&point
,
248 exploded_node
*enode_for_diag
,
249 uncertainty_t
*uncertainty
) const;
251 tree
get_representative_tree (const svalue
*sval
) const;
253 bool can_purge_p (const extrinsic_state
&ext_state
,
254 const svalue
*sval
) const
256 /* Don't purge vars that have non-purgeable sm state, to avoid
257 generating false "leak" complaints. */
260 FOR_EACH_VEC_ELT (m_checker_states
, i
, smap
)
262 const state_machine
&sm
= ext_state
.get_sm (i
);
263 if (!sm
.can_purge_p (smap
->get_state (sval
, ext_state
)))
269 bool can_purge_base_region_p (const extrinsic_state
&ext_state
,
270 const region
*base_reg
) const;
272 bool can_merge_with_p (const program_state
&other
,
273 const extrinsic_state
&ext_state
,
274 const program_point
&point
,
275 program_state
*out
) const;
277 void validate (const extrinsic_state
&ext_state
) const;
279 static void detect_leaks (const program_state
&src_state
,
280 const program_state
&dest_state
,
281 const svalue
*extra_sval
,
282 const extrinsic_state
&ext_state
,
283 region_model_context
*ctxt
);
285 bool replay_call_summary (call_summary_replay
&r
,
286 const program_state
&summary
);
288 void impl_call_analyzer_dump_state (const gcall
*call
,
289 const extrinsic_state
&ext_state
,
290 region_model_context
*ctxt
);
292 /* TODO: lose the pointer here (const-correctness issues?). */
293 region_model
*m_region_model
;
294 auto_delete_vec
<sm_state_map
> m_checker_states
;
296 /* If false, then don't attempt to explore further states along this path.
297 For use in "handling" lvalues for tree codes we haven't yet
302 /* An abstract base class for use with for_each_state_change. */
304 class state_change_visitor
307 virtual ~state_change_visitor () {}
309 /* Return true for early exit, false to keep iterating. */
310 virtual bool on_global_state_change (const state_machine
&sm
,
311 state_machine::state_t src_sm_val
,
312 state_machine::state_t dst_sm_val
) = 0;
314 /* Return true for early exit, false to keep iterating. */
315 virtual bool on_state_change (const state_machine
&sm
,
316 state_machine::state_t src_sm_val
,
317 state_machine::state_t dst_sm_val
,
318 const svalue
*dst_sval
,
319 const svalue
*dst_origin_sval
) = 0;
322 extern bool for_each_state_change (const program_state
&src_state
,
323 const program_state
&dst_state
,
324 const extrinsic_state
&ext_state
,
325 state_change_visitor
*visitor
);
329 #endif /* GCC_ANALYZER_PROGRAM_STATE_H */