GCC Middle and Back End API Reference
analyzer.h
Go to the documentation of this file.
1/* Utility functions for the analyzer.
2 Copyright (C) 2019-2024 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_ANALYZER_H
22#define GCC_ANALYZER_ANALYZER_H
23
24#include "rich-location.h"
25#include "function.h"
26#include "json.h"
27#include "tristate.h"
28
29class graphviz_out;
30
31namespace ana {
32
33/* Forward decls of common types, with indentation to show inheritance. */
34
35class supergraph;
36class supernode;
37class superedge;
38 class cfg_superedge;
39 class switch_cfg_superedge;
40 class callgraph_superedge;
41 class call_superedge;
42 class return_superedge;
43
44class svalue;
45 class region_svalue;
46 class constant_svalue;
47 class unknown_svalue;
48 class poisoned_svalue;
49 class setjmp_svalue;
50 class initial_svalue;
51 class unaryop_svalue;
52 class binop_svalue;
53 class sub_svalue;
54 class repeated_svalue;
55 class bits_within_svalue;
56 class unmergeable_svalue;
57 class placeholder_svalue;
58 class widening_svalue;
59 class compound_svalue;
60 class conjured_svalue;
61 class asm_output_svalue;
62 class const_fn_result_svalue;
64class region;
65 class frame_region;
66 class function_region;
67 class label_region;
68 class decl_region;
69 class symbolic_region;
70 class element_region;
71 class offset_region;
72 class sized_region;
73 class cast_region;
74 class field_region;
75 class string_region;
76 class bit_range_region;
77 class var_arg_region;
79class conjured_purge;
80struct model_merger;
81class store_manager;
82class store;
83class region_model;
86class call_details;
89class equiv_class;
91class bounded_ranges;
93
94struct pending_location;
96class pending_note;
98struct event_loc_info;
99class checker_event;
100 class state_change_event;
101 class warning_event;
102class checker_path;
103class extrinsic_state;
104class sm_state_map;
105class stmt_finder;
106class program_point;
107class function_point;
108class program_state;
109class exploded_graph;
110class exploded_node;
111class exploded_edge;
113class exploded_cluster;
114class exploded_path;
115class analysis_plan;
116class state_purge_map;
119class state_change;
120class rewind_info_t;
121
122class engine;
123class state_machine;
124class logger;
125class visitor;
127class call_summary;
129struct per_function_data;
130struct interesting_t;
131
132class feasible_node;
133
134class known_function;
137
138/* Forward decls of functions. */
139
140extern void dump_tree (pretty_printer *pp, tree t);
144extern int readability_comparator (const void *p1, const void *p2);
145extern int tree_cmp (const void *p1, const void *p2);
148
149/* A tree, extended with stack frame information for locals, so that
150 we can distinguish between different values of locals within a potentially
151 recursive callstack. */
152
154{
155public:
158 {
159 // TODO: ignore stack depth for globals and constants
160 }
161
162 bool operator== (const path_var &other) const
163 {
164 return (m_tree == other.m_tree
165 && m_stack_depth == other.m_stack_depth);
166 }
167
168 operator bool () const
169 {
170 return m_tree != NULL_TREE;
171 }
172
173 void dump (pretty_printer *pp) const;
174
176 int m_stack_depth; // or -1 for globals?
177};
178
183
185
187
188/* The location of a region expressesd as an offset relative to a
189 base region. */
190
192{
193public:
198
205 const svalue *sym_offset)
206 {
208 }
210 const svalue *num_bytes_sval);
211
212 const region *get_base_region () const { return m_base_region; }
213
214 bool concrete_p () const { return m_sym_offset == NULL; }
215 bool symbolic_p () const { return m_sym_offset != NULL; }
216
218 {
220 return m_offset;
221 }
222
224 {
226 if (m_offset % BITS_PER_UNIT == 0)
227 {
228 *out = m_offset / BITS_PER_UNIT;
229 return true;
230 }
231 return false;
232 }
233
235 {
237 return m_sym_offset;
238 }
239
242
243 bool operator== (const region_offset &other) const
244 {
245 return (m_base_region == other.m_base_region
246 && m_offset == other.m_offset
247 && m_sym_offset == other.m_sym_offset);
248 }
249
250 void dump_to_pp (pretty_printer *pp, bool) const;
251 void dump (bool) const;
252
253private:
258
262};
263
264extern bool operator< (const region_offset &, const region_offset &);
265extern bool operator<= (const region_offset &, const region_offset &);
266extern bool operator> (const region_offset &, const region_offset &);
267extern bool operator>= (const region_offset &, const region_offset &);
268
269extern location_t get_stmt_location (const gimple *stmt, function *fun);
270
272
273/* Abstract base class for simulating the behavior of known functions,
274 supplied by the core of the analyzer, or by plugins.
275 The former are typically implemented in the various kf*.cc */
276
278{
279public:
280 virtual ~known_function () {}
281 virtual bool matches_call_types_p (const call_details &cd) const = 0;
282 virtual void impl_call_pre (const call_details &) const
283 {
284 return;
285 }
286 virtual void impl_call_post (const call_details &) const
287 {
288 return;
289 }
290
291 virtual const builtin_known_function *
292 dyn_cast_builtin_kf () const { return NULL; }
293};
294
295/* Subclass of known_function for builtin functions. */
296
298{
299public:
300 virtual enum built_in_function builtin_code () const = 0;
303 return builtin_info[builtin_code ()].decl;
304 }
305
307 dyn_cast_builtin_kf () const final override { return this; }
308};
309
310/* Subclass of known_function for IFN_* functions. */
311
313{
314public:
315 bool matches_call_types_p (const call_details &) const final override
316 {
317 /* Types are assumed to be correct. */
318 return true;
319 }
320};
321
322/* Abstract subclass of known_function that merely sets the return
323 value of the function (based on function attributes), and assumes
324 it has no side-effects. */
325
327{
328public:
329 void impl_call_pre (const call_details &cd) const override;
330};
331
339
340/* Passed by pointer to PLUGIN_ANALYZER_INIT callbacks. */
341
343{
344public:
345 virtual void register_state_machine (std::unique_ptr<state_machine>) = 0;
346 virtual void register_known_function (const char *name,
347 std::unique_ptr<known_function>) = 0;
348 virtual logger *get_logger () const = 0;
349};
350
351/* An enum for describing the direction of an access to memory. */
352
358
359/* Abstract base class for associating custom data with an
360 exploded_edge, for handling non-standard edges such as
361 rewinding from a longjmp, signal handlers, etc.
362 Also used when "bifurcating" state: splitting the execution
363 path in non-standard ways (e.g. for simulating the various
364 outcomes of "realloc"). */
365
367{
368public:
369 virtual ~custom_edge_info () {}
370
371 /* Hook for making .dot label more readable. */
372 virtual void print (pretty_printer *pp) const = 0;
373
374 /* Hook for updating STATE when handling bifurcation. */
376 const exploded_edge *eedge,
378
379 /* Hook for updating MODEL within exploded_path::feasible_p
380 and when handling bifurcation. */
382 const exploded_edge *eedge,
383 region_model_context *ctxt) const = 0;
384
386 const exploded_edge &eedge) const = 0;
387};
388
389/* Abstract base class for splitting state.
390
391 Most of the state-management code in the analyzer involves
392 modifying state objects in-place, which assumes a single outcome.
393
394 This class provides an escape hatch to allow for multiple outcomes
395 for such updates e.g. for modelling multiple outcomes from function
396 calls, such as the various outcomes of "realloc". */
397
399{
400public:
401 virtual ~path_context () {}
402
403 /* Hook for clients to split state with a non-standard path. */
404 virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
405
406 /* Hook for clients to terminate the standard path. */
407 virtual void terminate_path () = 0;
408
409 /* Hook for clients to determine if the standard path has been
410 terminated. */
411 virtual bool terminate_path_p () const = 0;
412};
413
414extern tree get_stashed_constant_by_name (const char *name);
416
418
419extern json::value *
421
422extern json::value *
424
425extern json::value *
427
428extern json::value *
430
431extern tristate
433
434extern tree
436
437extern tree
439
440extern const svalue *
442
443extern region_offset
445
447
448} // namespace ana
449
450extern bool is_special_named_call_p (const gcall *call, const char *funcname,
451 unsigned int num_args);
452extern bool is_named_call_p (const_tree fndecl, const char *funcname);
453extern bool is_named_call_p (const_tree fndecl, const char *funcname,
454 const gcall *call, unsigned int num_args);
455extern bool is_std_named_call_p (const_tree fndecl, const char *funcname);
456extern bool is_std_named_call_p (const_tree fndecl, const char *funcname,
457 const gcall *call, unsigned int num_args);
458extern bool is_setjmp_call_p (const gcall *call);
459extern bool is_longjmp_call_p (const gcall *call);
460extern bool is_placement_new_p (const gcall *call);
461
462extern const char *get_user_facing_name (const gcall *call);
463
465
466extern label_text make_label_text (bool can_colorize, const char *fmt, ...);
468 unsigned HOST_WIDE_INT n,
469 const char *singular_fmt,
470 const char *plural_fmt, ...);
471
472extern bool fndecl_has_gimple_body_p (tree fndecl);
473
474/* An RAII-style class for pushing/popping cfun within a scope.
475 Doing so ensures we get "In function " announcements
476 from the diagnostics subsystem. */
477
479{
480public:
481 auto_cfun (function *fun) { push_cfun (fun); }
483};
484
485/* A template for creating hash traits for a POD type. */
486
487template <typename Type>
489{
492 static inline hashval_t hash (value_type);
493 static inline bool equal (const value_type &existing,
494 const value_type &candidate);
495 static inline void mark_deleted (Type &);
496 static inline void mark_empty (Type &);
497 static inline bool is_deleted (Type);
498 static inline bool is_empty (Type);
499};
500
501/* A hash traits class that uses member functions to implement
502 the various required ops. */
503
504template <typename Type>
506{
509 static inline hashval_t hash (value_type v) { return v.hash (); }
510 static inline bool equal (const value_type &existing,
511 const value_type &candidate)
512 {
513 return existing == candidate;
514 }
515 static inline void mark_deleted (Type &t) { t.mark_deleted (); }
516 static inline void mark_empty (Type &t) { t.mark_empty (); }
517 static inline bool is_deleted (Type t) { return t.is_deleted (); }
518 static inline bool is_empty (Type t) { return t.is_empty (); }
519};
520
521/* A map from T::key_t to T* for use in consolidating instances of T.
522 Owns all instances of T.
523 T::key_t should have operator== and be hashable. */
524
525template <typename T>
527{
528public:
529 typedef typename T::key_t key_t;
530 typedef T instance_t;
532 typedef typename inner_map_t::iterator iterator;
533
534 /* Delete all instances of T. */
535
537 {
538 for (typename inner_map_t::iterator iter = m_inner_map.begin ();
539 iter != m_inner_map.end (); ++iter)
540 delete (*iter).second;
541 }
542
543 /* Get the instance of T for K if one exists, or NULL. */
544
545 T *get (const key_t &k) const
546 {
547 if (instance_t **slot = const_cast<inner_map_t &> (m_inner_map).get (k))
548 return *slot;
549 return NULL;
550 }
551
552 /* Take ownership of INSTANCE. */
553
554 void put (const key_t &k, T *instance)
555 {
556 m_inner_map.put (k, instance);
557 }
558
559 size_t elements () const { return m_inner_map.elements (); }
560
561 iterator begin () const { return m_inner_map.begin (); }
562 iterator end () const { return m_inner_map.end (); }
563
564private:
566};
567
568/* Disable -Wformat-diag; we want to be able to use pp_printf
569 for logging/dumping without complying with the rules for diagnostics. */
570#if __GNUC__ >= 10
571#pragma GCC diagnostic ignored "-Wformat-diag"
572#endif
573
574#if !ENABLE_ANALYZER
575extern void sorry_no_analyzer ();
576#endif /* #if !ENABLE_ANALYZER */
577
578#endif /* GCC_ANALYZER_ANALYZER_H */
bool is_named_call_p(const_tree fndecl, const char *funcname)
const char * get_user_facing_name(const gcall *call)
bool is_special_named_call_p(const gcall *call, const char *funcname, unsigned int num_args)
void sorry_no_analyzer()
Definition analyzer-pass.cc:110
bool is_longjmp_call_p(const gcall *call)
bool is_std_named_call_p(const_tree fndecl, const char *funcname)
bool is_setjmp_call_p(const gcall *call)
label_text make_label_text_n(bool can_colorize, unsigned HOST_WIDE_INT n, const char *singular_fmt, const char *plural_fmt,...)
bool fndecl_has_gimple_body_p(tree fndecl)
label_text make_label_text(bool can_colorize, const char *fmt,...)
bool is_placement_new_p(const gcall *call)
void register_analyzer_pass()
Definition analysis-plan.h:35
Definition region.h:1264
Definition constraint-manager.h:175
Definition analyzer.h:298
virtual enum built_in_function builtin_code() const =0
const builtin_known_function * dyn_cast_builtin_kf() const final override
Definition analyzer.h:307
tree builtin_decl() const
Definition analyzer.h:301
Definition call-details.h:29
Definition call-summary.h:68
Definition call-summary.h:34
Definition region.h:1114
Definition checker-event.h:101
Definition checker-path.h:31
Definition svalue.h:1370
Definition constraint-manager.h:408
Definition analyzer.h:367
virtual bool update_state(program_state *state, const exploded_edge *eedge, region_model_context *ctxt) const
virtual bool update_model(region_model *model, const exploded_edge *eedge, region_model_context *ctxt) const =0
virtual void print(pretty_printer *pp) const =0
virtual void add_events_to_path(checker_path *emission_path, const exploded_edge &eedge) const =0
virtual ~custom_edge_info()
Definition analyzer.h:369
Definition region.h:713
Definition region.h:845
Definition region-model.h:1225
Definition constraint-manager.h:249
Definition exploded-graph.h:381
Definition exploded-graph.h:791
Definition exploded-graph.h:203
Definition exploded-graph.h:947
Definition program-state.h:29
Definition exploded-graph.h:975
Definition feasible-graph.h:84
Definition region.h:770
Definition region.h:306
Definition program-point.h:73
Definition region.h:464
Definition exploded-graph.h:39
Definition analyzer.h:313
bool matches_call_types_p(const call_details &) const final override
Definition analyzer.h:315
Definition known-function-manager.h:41
Definition analyzer.h:278
virtual void impl_call_post(const call_details &) const
Definition analyzer.h:286
virtual void impl_call_pre(const call_details &) const
Definition analyzer.h:282
virtual bool matches_call_types_p(const call_details &cd) const =0
virtual const builtin_known_function * dyn_cast_builtin_kf() const
Definition analyzer.h:292
virtual ~known_function()
Definition analyzer.h:280
Definition region.h:501
Definition analyzer-logging.h:34
Definition region.h:932
Definition analyzer.h:399
virtual bool terminate_path_p() const =0
virtual void bifurcate(std::unique_ptr< custom_edge_info > info)=0
virtual void terminate_path()=0
virtual ~path_context()
Definition analyzer.h:401
Definition analyzer.h:154
bool operator==(const path_var &other) const
Definition analyzer.h:162
int m_stack_depth
Definition analyzer.h:176
path_var(tree t, int stack_depth)
Definition analyzer.h:156
void dump(pretty_printer *pp) const
tree m_tree
Definition analyzer.h:175
Definition pending-diagnostic.h:208
Definition pending-diagnostic.h:441
Definition analyzer.h:343
virtual void register_state_machine(std::unique_ptr< state_machine >)=0
virtual logger * get_logger() const =0
virtual void register_known_function(const char *name, std::unique_ptr< known_function >)=0
Definition program-point.h:175
Definition program-state.h:203
void impl_call_pre(const call_details &cd) const override
Definition region-model-reachability.h:36
Definition region-model.h:702
Definition region-model-manager.h:32
Definition region-model.h:258
Definition analyzer.h:192
bit_offset_t get_bit_offset() const
Definition analyzer.h:217
bool symbolic_p() const
Definition analyzer.h:215
const region * get_base_region() const
Definition analyzer.h:212
bit_offset_t m_offset
Definition analyzer.h:260
static region_offset make_byte_offset(const region *base_region, const svalue *num_bytes_sval)
const svalue * m_sym_offset
Definition analyzer.h:261
static region_offset make_concrete(const region *base_region, bit_offset_t offset)
Definition analyzer.h:199
void dump_to_pp(pretty_printer *pp, bool) const
region_offset()
Definition analyzer.h:194
const svalue * calc_symbolic_byte_offset(region_model_manager *mgr) const
region_offset(const region *base_region, bit_offset_t offset, const svalue *sym_offset)
Definition analyzer.h:254
void dump(bool) const
bool operator==(const region_offset &other) const
Definition analyzer.h:243
const svalue & calc_symbolic_bit_offset(region_model_manager *mgr) const
const region * m_base_region
Definition analyzer.h:259
bool get_concrete_byte_offset(byte_offset_t *out) const
Definition analyzer.h:223
static region_offset make_symbolic(const region *base_region, const svalue *sym_offset)
Definition analyzer.h:204
const svalue * get_symbolic_byte_offset() const
Definition analyzer.h:234
bool concrete_p() const
Definition analyzer.h:214
Definition region.h:125
Definition region-model.h:1165
Definition exploded-graph.h:457
Definition diagnostic-manager.h:31
Definition region.h:1019
Definition program-state.h:75
Definition checker-event.h:358
Definition sm.h:40
Definition state-purge.h:78
Definition state-purge.h:194
Definition state-purge.h:162
Definition exploded-graph.h:1033
Definition store.h:846
Definition store.h:726
Definition region.h:1225
Definition svalue.h:90
Definition region.h:639
Definition region.h:1353
Definition region-model.h:217
Definition checker-event.h:683
Definition analyzer.h:479
~auto_cfun()
Definition analyzer.h:482
auto_cfun(function *fun)
Definition analyzer.h:481
Definition analyzer.h:527
inner_map_t::iterator iterator
Definition analyzer.h:532
inner_map_t m_inner_map
Definition analyzer.h:565
T * get(const key_t &k) const
Definition analyzer.h:545
T::key_t key_t
Definition analyzer.h:529
~consolidation_map()
Definition analyzer.h:536
iterator begin() const
Definition analyzer.h:561
T instance_t
Definition analyzer.h:530
hash_map< key_t, instance_t * > inner_map_t
Definition analyzer.h:531
void put(const key_t &k, T *instance)
Definition analyzer.h:554
size_t elements() const
Definition analyzer.h:559
iterator end() const
Definition analyzer.h:562
Definition diagnostic-event-id.h:37
Definition genmatch.cc:845
Definition graphviz.h:29
Definition hash-map.h:40
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
bool put(const Key &k, const Value &v)
Definition hash-map.h:168
Definition hash-set.h:37
Definition json.h:79
Definition pretty-print.h:244
Definition lra-spills.cc:101
Definition tristate.h:26
const union tree_node * const_tree
Definition coretypes.h:98
union tree_node * tree
Definition coretypes.h:97
void final(rtx_insn *first, FILE *file, int optimize_p)
Definition final.cc:2002
void push_cfun(struct function *new_cfun)
Definition function.cc:4726
void pop_cfun(void)
Definition function.cc:4738
static void record_type(type_p type)
Definition gengtype-state.cc:1426
built_in_function
Definition genmatch.cc:354
@ END_BUILTINS
Definition genmatch.cc:356
tree_code
Definition genmatch.cc:347
T * ggc_alloc(ALONE_CXX_MEM_STAT_INFO)
Definition ggc.h:184
Definition access-diagram.h:30
bool compat_types_p(tree src_type, tree dst_type)
void register_known_functions_lang_cp(known_function_manager &kfm)
void register_known_functions(known_function_manager &kfm, region_model_manager &rmm)
offset_int byte_size_t
Definition analyzer.h:182
bool operator>(const region_offset &, const region_offset &)
offset_int bit_offset_t
Definition analyzer.h:179
tree fixup_tree_for_diagnostic(tree)
void dump_tree(pretty_printer *pp, tree t)
bool operator>=(const region_offset &, const region_offset &)
tree get_string_cst_size(const_tree string_cst)
bool operator<(const region_offset &, const region_offset &)
void register_known_analyzer_functions(known_function_manager &kfm)
access_direction
Definition analyzer.h:354
@ DIR_WRITE
Definition analyzer.h:356
@ DIR_READ
Definition analyzer.h:355
bool operator<=(const region_offset &, const region_offset &)
tree get_field_at_bit_offset(tree record_type, bit_offset_t bit_offset)
void print_expr_for_user(pretty_printer *pp, tree t)
tristate compare_constants(tree lhs_const, enum tree_code op, tree rhs_const)
tree get_stashed_constant_by_name(const char *name)
json::value * diagnostic_event_id_to_json(const diagnostic_event_id_t &)
bool int_size_in_bits(const_tree type, bit_size_t *out)
tree get_ssa_default_def(const function &fun, tree var)
offset_int byte_offset_t
Definition analyzer.h:181
json::value * bit_offset_to_json(const bit_offset_t &offset)
location_t get_stmt_location(const gimple *stmt, function *fun)
const svalue * strip_types(const svalue *sval, region_model_manager &mgr)
FILE * get_or_create_any_logfile()
void dump_quoted_tree(pretty_printer *pp, tree t)
void log_stashed_constants(logger *logger)
offset_int bit_size_t
Definition analyzer.h:180
int tree_cmp(const void *p1, const void *p2)
json::value * tree_to_json(tree node)
tree remove_ssa_names(tree expr)
tree get_diagnostic_tree_for_gassign(const gassign *)
hash_set< const svalue * > svalue_set
Definition analyzer.h:63
void register_varargs_builtins(known_function_manager &kfm)
void register_known_fd_functions(known_function_manager &kfm)
int readability_comparator(const void *p1, const void *p2)
void register_known_file_functions(known_function_manager &kfm)
json::value * byte_offset_to_json(const byte_offset_t &offset)
void print_quoted_type(pretty_printer *pp, tree t)
rtx offset
Definition postreload.cc:691
Definition constraint-manager.h:120
Definition checker-event.h:32
Definition pending-diagnostic.h:38
Definition region-model.h:1116
Definition diagnostic-manager.h:108
Definition exploded-graph.h:665
Definition tree-loop-distribution.cc:240
Definition function.h:249
Definition gimple.h:903
Definition gimple.h:352
Definition gimple.h:225
Definition analyzer.h:506
static void mark_empty(Type &t)
Definition analyzer.h:516
static hashval_t hash(value_type v)
Definition analyzer.h:509
Type compare_type
Definition analyzer.h:508
Type value_type
Definition analyzer.h:507
static bool equal(const value_type &existing, const value_type &candidate)
Definition analyzer.h:510
static void mark_deleted(Type &t)
Definition analyzer.h:515
static bool is_empty(Type t)
Definition analyzer.h:518
static bool is_deleted(Type t)
Definition analyzer.h:517
Definition analyzer.h:489
static void mark_deleted(Type &)
Type compare_type
Definition analyzer.h:491
static bool is_empty(Type)
static bool equal(const value_type &existing, const value_type &candidate)
static bool is_deleted(Type)
Type value_type
Definition analyzer.h:490
static hashval_t hash(value_type)
static void mark_empty(Type &)
Definition genautomata.cc:669
Definition gengtype.h:252
Definition hash-traits.h:75
#define NULL
Definition system.h:50
#define gcc_assert(EXPR)
Definition system.h:821
#define bool
Definition system.h:893
static tree candidate(unsigned uid)
Definition tree-sra.cc:325
static control_dependences * cd
Definition tree-ssa-dce.cc:102
#define NULL_TREE
Definition tree.h:317