GCC Middle and Back End API Reference
program-state.h
Go to the documentation of this file.
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
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along 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"
26
27#include "analyzer/store.h"
28
29namespace ana {
30
31/* Data shared by all program_state instances. */
32
34{
35public:
36 extrinsic_state (std::vector<std::unique_ptr<state_machine>> &&checkers,
37 engine *eng,
38 logger *logger = nullptr)
39 : m_checkers (std::move (checkers)),
41 m_engine (eng)
42 {
43 }
44
45 // For use in selftests that use just one state machine
46 extrinsic_state (std::unique_ptr<state_machine> sm,
47 engine *eng,
48 logger *logger = nullptr)
49 : m_logger (logger),
50 m_engine (eng)
51 {
52 m_checkers.push_back (std::move (sm));
53 }
54
55 const state_machine &get_sm (int idx) const
56 {
57 return *m_checkers[idx];
58 }
59
60 const char *get_name (int idx) const
61 {
62 return m_checkers[idx]->get_name ();
63 }
64
65 unsigned get_num_checkers () const { return m_checkers.size (); }
66
67 logger *get_logger () const { return m_logger; }
68
69 void dump_to_logger (logger &) const;
70 void dump () const;
71
72 std::unique_ptr<text_art::tree_widget>
74
75 std::unique_ptr<json::object> to_json () const;
76
77 engine *get_engine () const { return m_engine; }
78
81
83
84 bool get_sm_idx_by_name (const char *name, unsigned *out) const;
85
86private:
87 /* The state machines. */
88 std::vector<std::unique_ptr<state_machine>> m_checkers;
89
92};
93
94/* Map from svalue * to state machine state, also capturing the origin of
95 each state. */
96
98{
99public:
100 /* An entry in the hash_map. */
101 struct entry_t
102 {
103 /* Default ctor needed by hash_map::empty. */
105 : m_state (0), m_origin (nullptr)
106 {
107 }
108
110 const svalue *origin)
111 : m_state (state), m_origin (origin)
112 {}
113
114 bool operator== (const entry_t &other) const
115 {
116 return (m_state == other.m_state
117 && m_origin == other.m_origin);
118 }
119 bool operator!= (const entry_t &other) const
120 {
121 return !(*this == other);
122 }
123
124 static int cmp (const entry_t &entry_a, const entry_t &entry_b);
125
128 };
129 typedef hash_map <const svalue *, entry_t> map_t;
130 typedef map_t::iterator iterator_t;
131
133
135
136 void print (const region_model *model,
137 bool simple, bool multiline,
138 pretty_printer *pp) const;
139 void dump (bool simple) const;
140
141 std::unique_ptr<json::object> to_json () const;
142
143 std::unique_ptr<text_art::tree_widget>
145 const region_model *model = nullptr) const;
146 void dump () const;
147
148 bool is_empty_p () const;
149
150 hashval_t hash () const;
151
152 bool operator== (const sm_state_map &other) const;
153 bool operator!= (const sm_state_map &other) const
154 {
155 return !(*this == other);
156 }
157
159 const extrinsic_state &ext_state) const;
160 const svalue *get_origin (const svalue *sval,
161 const extrinsic_state &ext_state) const;
162
164 const svalue *sval,
166 const svalue *origin,
168 bool set_state (const equiv_class &ec,
170 const svalue *origin,
172 bool impl_set_state (const svalue *sval,
174 const svalue *origin,
176 void clear_any_state (const svalue *sval);
178
181
182 void on_svalue_leak (const svalue *sval,
187
189 bool is_mutable,
191
194
195 iterator_t begin () const { return m_map.begin (); }
196 iterator_t end () const { return m_map.end (); }
197 size_t elements () const { return m_map.elements (); }
198
199 static int cmp (const sm_state_map &smap_a, const sm_state_map &smap_b);
200
201 static const svalue *
203
205 const sm_state_map &summary);
206
207 bool can_merge_with_p (const sm_state_map &other,
208 const state_machine &sm,
210 sm_state_map **out) const;
211
212 void validate (const extrinsic_state &ext_state) const;
213
214private:
218 region_model_manager &rmm) const;
219
223 std::map<const symbolic::unfoldable_bit_contents *,
225};
226
227/* A class for representing the state of interest at a given path of
228 analysis.
229
230 Currently this is a combination of:
231 (a) a region_model, giving:
232 (a.1) a hierarchy of memory regions
233 (a.2) values for the regions
234 (a.3) inequalities between values
235 (b) sm_state_maps per state machine, giving a sparse mapping of
236 values to states. */
237
239{
240public:
247
248 hashval_t hash () const;
249 bool operator== (const program_state &other) const;
250 bool operator!= (const program_state &other) const
251 {
252 return !(*this == other);
253 }
254
256 pretty_printer *pp) const;
257
258 void dump_to_logger (logger &, const char *label = nullptr) const;
259 void dump () const;
260
261 std::unique_ptr<diagnostics::digraphs::digraph>
263
264 void
266
267 void
269
270 std::unique_ptr<json::object>
272
273 std::unique_ptr<text_art::tree_widget>
275 const char *label = nullptr) const;
276
277 void push_frame (const extrinsic_state &ext_state, const function &fun);
279
281 const program_point &point,
282 exploded_node *enode_for_diag,
283 uncertainty_t *uncertainty) const;
284
286
288 const svalue *sval) const
289 {
290 /* Don't purge vars that have non-purgeable sm state, to avoid
291 generating false "leak" complaints. */
292 int i;
293 sm_state_map *smap;
295 {
296 const state_machine &sm = ext_state.get_sm (i);
297 if (!sm.can_purge_p (smap->get_state (sval, ext_state)))
298 return false;
299 }
300 return true;
301 }
302
304 const region *base_reg) const;
305
306 bool can_merge_with_p (const program_state &other,
308 const program_point &point,
309 program_state *out) const;
310
311 void validate (const extrinsic_state &ext_state) const;
312
313 static void detect_leaks (const program_state &src_state,
314 const program_state &dest_state,
315 const svalue *extra_sval,
318
320 const program_state &summary);
321
325
326 /* TODO: lose the pointer here (const-correctness issues?). */
329
330 /* If false, then don't attempt to explore further states along this path.
331 For use in "handling" lvalues for tree codes we haven't yet
332 implemented. */
334};
335
336/* An abstract base class for use with for_each_state_change. */
337
339{
340public:
342
343 /* Return true for early exit, false to keep iterating. */
344 virtual bool on_global_state_change (const state_machine &sm,
345 state_machine::state_t src_sm_val,
346 state_machine::state_t dst_sm_val) = 0;
347
348 /* Return true for early exit, false to keep iterating. */
349 virtual bool on_state_change (const state_machine &sm,
350 state_machine::state_t src_sm_val,
351 state_machine::state_t dst_sm_val,
352 const svalue *dst_sval,
353 const svalue *dst_origin_sval) = 0;
354};
355
356extern bool for_each_state_change (const program_state &src_state,
357 const program_state &dst_state,
360
361} // namespace ana
362
363#endif /* GCC_ANALYZER_PROGRAM_STATE_H */
Definition call-summary.h:68
Definition region-model.h:1412
Definition constraint-manager.h:240
Definition exploded-graph.h:809
Definition exploded-graph.h:221
Definition program-state.h:34
bool get_sm_idx_by_name(const char *name, unsigned *out) const
std::vector< std::unique_ptr< state_machine > > m_checkers
Definition program-state.h:88
unsigned get_num_checkers() const
Definition program-state.h:65
void dump_to_logger(logger &) const
logger * get_logger() const
Definition program-state.h:67
std::unique_ptr< json::object > to_json() const
std::unique_ptr< text_art::tree_widget > make_dump_widget(symbolic::node_dump_state &nds) const
symbolic::node_manager & get_node_manager() const
const char * get_name(int idx) const
Definition program-state.h:60
logger * m_logger
Definition program-state.h:90
region_model_manager * get_model_manager() const
engine * m_engine
Definition program-state.h:91
extrinsic_state(std::vector< std::unique_ptr< state_machine > > &&checkers, engine *eng, logger *logger=nullptr)
Definition program-state.h:36
engine * get_engine() const
Definition program-state.h:77
const state_machine & get_sm(int idx) const
Definition program-state.h:55
extrinsic_state(std::unique_ptr< state_machine > sm, engine *eng, logger *logger=nullptr)
Definition program-state.h:46
Definition exploded-graph.h:40
Definition analyzer-logging.h:36
Definition program-point.h:54
Definition program-state.h:239
bool can_purge_base_region_p(const extrinsic_state &ext_state, const region *base_reg) const
program_state prune_for_point(exploded_graph &eg, const program_point &point, exploded_node *enode_for_diag, uncertainty_t *uncertainty) const
void dump() const
void dump_to_logger(logger &, const char *label=nullptr) const
std::unique_ptr< json::object > to_json(const extrinsic_state &ext_state) const
bool operator!=(const program_state &other) const
Definition program-state.h:250
program_state(const program_state &other)
void push_frame(const extrinsic_state &ext_state, const function &fun)
void dump_dot(const extrinsic_state &ext_state) const
bool operator==(const program_state &other) const
static void detect_leaks(const program_state &src_state, const program_state &dest_state, const svalue *extra_sval, const extrinsic_state &ext_state, region_model_context *ctxt)
std::unique_ptr< text_art::tree_widget > make_dump_widget(symbolic::node_dump_state &nds, const char *label=nullptr) const
void print(const extrinsic_state &ext_state, pretty_printer *pp) const
bool replay_call_summary(call_summary_replay &r, const program_state &summary)
program_state & operator=(const program_state &other)
program_state(program_state &&other)
void validate(const extrinsic_state &ext_state) const
auto_delete_vec< sm_state_map > m_checker_states
Definition program-state.h:328
std::unique_ptr< diagnostics::digraphs::digraph > make_diagnostic_state_graph(const extrinsic_state &ext_state) const
bool can_merge_with_p(const program_state &other, const extrinsic_state &ext_state, const program_point &point, program_state *out) const
region_model * m_region_model
Definition program-state.h:327
bool can_purge_p(const extrinsic_state &ext_state, const svalue *sval) const
Definition program-state.h:287
const function * get_current_function() const
tree get_representative_tree(const svalue *sval) const
hashval_t hash() const
void impl_call_analyzer_dump_state(const gcall &call, const extrinsic_state &ext_state, region_model_context *ctxt)
void dump_sarif(const extrinsic_state &ext_state) const
bool m_valid
Definition program-state.h:333
program_state(const extrinsic_state &ext_state)
Definition region-model.h:840
Definition region-model-manager.h:36
Definition region-model.h:289
Definition region.h:130
Definition program-state.h:98
map_t::iterator iterator_t
Definition program-state.h:130
bool operator==(const sm_state_map &other) const
bool can_merge_with_p(const sm_state_map &other, const state_machine &sm, const extrinsic_state &ext_state, sm_state_map **out) const
state_machine::state_t get_any_inherited_state_of_bit_vector(const symbolic::bit_vector &bv, const extrinsic_state &ext_state, region_model_manager &rmm) const
static const svalue * canonicalize_svalue(const svalue *sval, const extrinsic_state &ext_state)
static int cmp(const sm_state_map &smap_a, const sm_state_map &smap_b)
void validate(const extrinsic_state &ext_state) const
iterator_t begin() const
Definition program-state.h:195
std::unique_ptr< text_art::tree_widget > make_dump_widget(symbolic::node_dump_state &nds, const region_model *model=nullptr) const
state_machine::state_t m_global_state
Definition program-state.h:222
state_machine::state_t get_state(const svalue *sval, const extrinsic_state &ext_state) const
void on_unknown_change(const symbolic::value_node &val, bool is_mutable, const extrinsic_state &ext_state)
const state_machine & m_sm
Definition program-state.h:220
sm_state_map * clone() const
size_t elements() const
Definition program-state.h:197
hash_map< const svalue *, entry_t > map_t
Definition program-state.h:129
void purge_state_involving(const symbolic::node &node, const extrinsic_state &ext_state)
void print(const region_model *model, bool simple, bool multiline, pretty_printer *pp) const
map_t m_map
Definition program-state.h:221
std::unique_ptr< json::object > to_json() const
void set_state(region_model *model, const svalue *sval, state_machine::state_t state, const svalue *origin, const extrinsic_state &ext_state)
bool operator!=(const sm_state_map &other) const
Definition program-state.h:153
bool impl_set_state(const svalue *sval, state_machine::state_t state, const svalue *origin, const extrinsic_state &ext_state)
hashval_t hash() const
void clear_any_state(const svalue *sval)
void on_svalue_leak(const svalue *sval, impl_region_model_context *ctxt)
state_machine::state_t get_global_state() const
const svalue * get_origin(const svalue *sval, const extrinsic_state &ext_state) const
iterator_t end() const
Definition program-state.h:196
void on_liveness_change(symbolic::liveness_context &liveness_ctxt, const extrinsic_state &ext_state, impl_region_model_context *ctxt)
std::map< const symbolic::unfoldable_bit_contents *, state_machine::state_t > m_map_ubc_to_state
Definition program-state.h:224
void dump() const
void clear_all_per_svalue_state()
bool set_state(const equiv_class &ec, state_machine::state_t state, const svalue *origin, const extrinsic_state &ext_state)
void set_global_state(state_machine::state_t state)
bool is_empty_p() const
bool replay_call_summary(call_summary_replay &r, const sm_state_map &summary)
sm_state_map(const state_machine &sm)
void dump(bool simple) const
Definition program-state.h:339
virtual bool on_state_change(const state_machine &sm, state_machine::state_t src_sm_val, state_machine::state_t dst_sm_val, const svalue *dst_sval, const svalue *dst_origin_sval)=0
virtual ~state_change_visitor()
Definition program-state.h:341
virtual bool on_global_state_change(const state_machine &sm, state_machine::state_t src_sm_val, state_machine::state_t dst_sm_val)=0
Definition sm.h:43
const state_machine::state * state_t
Definition sm.h:63
virtual bool can_purge_p(state_t s) const =0
Definition svalue.h:82
Definition symbolic-bit-vectors.h:107
Definition liveness-context.h:33
Definition symbolic-nodes.h:48
Definition symbolic-nodes.h:116
Definition symbolic-bit-contents.h:476
Definition symbolic-nodes.h:468
Definition store.h:357
Definition region-model.h:222
Definition vec.h:1813
Definition ree.cc:583
iterator begin() const
Definition hash-map.h:302
size_t elements() const
Definition hash-map.h:247
iterator end() const
Definition hash-map.h:303
Definition pretty-print.h:241
union tree_node * tree
Definition coretypes.h:97
Definition access-diagram.h:30
@ other
Definition common.h:535
bool for_each_state_change(const program_state &src_state, const program_state &dst_state, const extrinsic_state &ext_state, state_change_visitor *visitor)
Definition custom-sarif-properties/state-graphs.h:33
poly_int< N, C > r
Definition poly-int.h:774
i
Definition poly-int.h:776
static int cmp(const entry_t &entry_a, const entry_t &entry_b)
bool operator==(const entry_t &other) const
Definition program-state.h:114
entry_t(state_machine::state_t state, const svalue *origin)
Definition program-state.h:109
entry_t()
Definition program-state.h:104
state_machine::state_t m_state
Definition program-state.h:126
bool operator!=(const entry_t &other) const
Definition program-state.h:119
const svalue * m_origin
Definition program-state.h:127
Definition symbolic-nodes.h:276
Definition function.h:249
Definition gimple.h:356
Definition ira-emit.cc:158
Definition genautomata.cc:669
#define FOR_EACH_VEC_ELT(V, I, P)
Definition vec.h:1895