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;
63typedef hash_set<const svalue *> svalue_set;
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;
78class region_model_manager;
79class conjured_purge;
80struct model_merger;
81class store_manager;
82class store;
83class region_model;
84class region_model_context;
85 class impl_region_model_context;
86class call_details;
87class rejected_constraint;
88class constraint_manager;
89class equiv_class;
90class reachable_regions;
91class bounded_ranges;
92class bounded_ranges_manager;
93
94struct pending_location;
95class pending_diagnostic;
96class pending_note;
97class saved_diagnostic;
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;
112class feasibility_problem;
113class exploded_cluster;
114class exploded_path;
115class analysis_plan;
116class state_purge_map;
117class state_purge_per_ssa_name;
118class state_purge_per_decl;
119class state_change;
120class rewind_info_t;
121
122class engine;
123class state_machine;
124class logger;
125class visitor;
126class known_function_manager;
127class call_summary;
128class call_summary_replay;
129struct per_function_data;
130struct interesting_t;
131
132class feasible_node;
133
134class known_function;
135 class builtin_known_function;
136 class internal_known_function;
137
138/* Forward decls of functions. */
139
140extern void dump_tree (pretty_printer *pp, tree t);
141extern void dump_quoted_tree (pretty_printer *pp, tree t);
142extern void print_quoted_type (pretty_printer *pp, tree t);
143extern void print_expr_for_user (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);
146extern tree fixup_tree_for_diagnostic (tree);
147extern tree get_diagnostic_tree_for_gassign (const gassign *);
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
153class path_var
154{
155public:
156 path_var (tree t, int stack_depth)
157 : m_tree (t), m_stack_depth (stack_depth)
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
175 tree m_tree;
176 int m_stack_depth; // or -1 for globals?
177};
178
179typedef offset_int bit_offset_t;
180typedef offset_int bit_size_t;
181typedef offset_int byte_offset_t;
182typedef offset_int byte_size_t;
183
184extern bool int_size_in_bits (const_tree type, bit_size_t *out);
185
186extern tree get_field_at_bit_offset (tree record_type, bit_offset_t bit_offset);
187
188/* The location of a region expressesd as an offset relative to a
189 base region. */
190
191class region_offset
192{
193public:
194 region_offset ()
195 : m_base_region (NULL), m_offset (0), m_sym_offset (NULL)
196 {
197 }
198
199 static region_offset make_concrete (const region *base_region,
200 bit_offset_t offset)
201 {
202 return region_offset (base_region, offset, NULL);
203 }
204 static region_offset make_symbolic (const region *base_region,
205 const svalue *sym_offset)
206 {
207 return region_offset (base_region, 0, sym_offset);
208 }
209 static region_offset make_byte_offset (const region *base_region,
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
217 bit_offset_t get_bit_offset () const
218 {
219 gcc_assert (!symbolic_p ());
220 return m_offset;
221 }
222
223 bool get_concrete_byte_offset (byte_offset_t *out) const
224 {
225 gcc_assert (!symbolic_p ());
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
234 const svalue *get_symbolic_byte_offset () const
235 {
236 gcc_assert (symbolic_p ());
237 return m_sym_offset;
238 }
239
240 const svalue &calc_symbolic_bit_offset (region_model_manager *mgr) const;
241 const svalue *calc_symbolic_byte_offset (region_model_manager *mgr) const;
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:
254 region_offset (const region *base_region, bit_offset_t offset,
255 const svalue *sym_offset)
256 : m_base_region (base_region), m_offset (offset), m_sym_offset (sym_offset)
257 {}
258
259 const region *m_base_region;
260 bit_offset_t m_offset;
261 const svalue *m_sym_offset;
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
271extern bool compat_types_p (tree src_type, tree dst_type);
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
277class known_function
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
297class builtin_known_function : public known_function
298{
299public:
300 virtual enum built_in_function builtin_code () const = 0;
301 tree builtin_decl () const {
302 gcc_assert (builtin_code () < END_BUILTINS);
303 return builtin_info[builtin_code ()].decl;
304 }
305
306 const builtin_known_function *
307 dyn_cast_builtin_kf () const final override { return this; }
308};
309
310/* Subclass of known_function for IFN_* functions. */
311
312class internal_known_function : public known_function
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
326class pure_known_function_with_default_return : public known_function
327{
328public:
329 void impl_call_pre (const call_details &cd) const override;
330};
331
332extern void register_known_functions (known_function_manager &kfm,
333 region_model_manager &rmm);
334extern void register_known_analyzer_functions (known_function_manager &kfm);
335extern void register_known_fd_functions (known_function_manager &kfm);
336extern void register_known_file_functions (known_function_manager &kfm);
337extern void register_known_functions_lang_cp (known_function_manager &kfm);
338extern void register_varargs_builtins (known_function_manager &kfm);
339
340/* Passed by pointer to PLUGIN_ANALYZER_INIT callbacks. */
341
342class plugin_analyzer_init_iface
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
353enum access_direction
354{
355 DIR_READ,
356 DIR_WRITE
357};
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
366class custom_edge_info
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. */
375 virtual bool update_state (program_state *state,
376 const exploded_edge *eedge,
377 region_model_context *ctxt) const;
378
379 /* Hook for updating MODEL within exploded_path::feasible_p
380 and when handling bifurcation. */
381 virtual bool update_model (region_model *model,
382 const exploded_edge *eedge,
383 region_model_context *ctxt) const = 0;
384
385 virtual void add_events_to_path (checker_path *emission_path,
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
398class path_context
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);
415extern void log_stashed_constants (logger *logger);
416
417extern FILE *get_or_create_any_logfile ();
418
419extern json::value *
420tree_to_json (tree node);
421
422extern json::value *
423diagnostic_event_id_to_json (const diagnostic_event_id_t &);
424
425extern json::value *
426bit_offset_to_json (const bit_offset_t &offset);
427
428extern json::value *
429byte_offset_to_json (const byte_offset_t &offset);
430
431extern tristate
432compare_constants (tree lhs_const, enum tree_code op, tree rhs_const);
433
434extern tree
435get_string_cst_size (const_tree string_cst);
436
437extern tree
438get_ssa_default_def (const function &fun, tree var);
439
440extern const svalue *
441strip_types (const svalue *sval, region_model_manager &mgr);
442
443extern region_offset
444strip_types (const region_offset &offset, region_model_manager &mgr);
445
446extern tree remove_ssa_names (tree expr);
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
464extern void register_analyzer_pass ();
465
466extern label_text make_label_text (bool can_colorize, const char *fmt, ...);
467extern label_text make_label_text_n (bool can_colorize,
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
478class auto_cfun
479{
480public:
481 auto_cfun (function *fun) { push_cfun (new_cfun: fun); }
482 ~auto_cfun () { pop_cfun (); }
483};
484
485/* A template for creating hash traits for a POD type. */
486
487template <typename Type>
488struct pod_hash_traits : typed_noop_remove<Type>
489{
490 typedef Type value_type;
491 typedef Type compare_type;
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>
505struct member_function_hash_traits : public typed_noop_remove<Type>
506{
507 typedef Type value_type;
508 typedef Type compare_type;
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>
526class consolidation_map
527{
528public:
529 typedef typename T::key_t key_t;
530 typedef T instance_t;
531 typedef hash_map<key_t, instance_t *> inner_map_t;
532 typedef typename inner_map_t::iterator iterator;
533
534 /* Delete all instances of T. */
535
536 ~consolidation_map ()
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:
565 inner_map_t m_inner_map;
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 */
579

source code of gcc/analyzer/analyzer.h