Branch data Line data Source code
1 : : /* Base header for the analyzer, plus utility functions.
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_COMMON_H
22 : : #define GCC_ANALYZER_COMMON_H
23 : :
24 : : #include "config.h"
25 : : #define INCLUDE_MAP
26 : : #define INCLUDE_STRING
27 : : #define INCLUDE_VECTOR
28 : : #include "system.h"
29 : : #include "coretypes.h"
30 : : #include "tree.h"
31 : : #include "function.h"
32 : : #include "basic-block.h"
33 : : #include "gimple.h"
34 : : #include "options.h"
35 : : #include "bitmap.h"
36 : : #include "diagnostic-core.h"
37 : : #include "diagnostics/paths.h"
38 : : #include "rich-location.h"
39 : : #include "function.h"
40 : : #include "json.h"
41 : : #include "tristate.h"
42 : :
43 : : class graphviz_out;
44 : :
45 : : namespace ana {
46 : :
47 : : /* Forward decls of common types, with indentation to show inheritance. */
48 : :
49 : : class supergraph;
50 : : class supernode;
51 : : class superedge;
52 : : class cfg_superedge;
53 : : class switch_cfg_superedge;
54 : : class eh_dispatch_cfg_superedge;
55 : : class eh_dispatch_try_cfg_superedge;
56 : : class eh_dispatch_allowed_cfg_superedge;
57 : : class callgraph_superedge;
58 : : class call_superedge;
59 : : class return_superedge;
60 : :
61 : : class svalue;
62 : : class region_svalue;
63 : : class constant_svalue;
64 : : class unknown_svalue;
65 : : class poisoned_svalue;
66 : : class setjmp_svalue;
67 : : class initial_svalue;
68 : : class unaryop_svalue;
69 : : class binop_svalue;
70 : : class sub_svalue;
71 : : class repeated_svalue;
72 : : class bits_within_svalue;
73 : : class unmergeable_svalue;
74 : : class placeholder_svalue;
75 : : class widening_svalue;
76 : : class compound_svalue;
77 : : class conjured_svalue;
78 : : class asm_output_svalue;
79 : : class const_fn_result_svalue;
80 : : typedef hash_set<const svalue *> svalue_set;
81 : : class region;
82 : : class frame_region;
83 : : class function_region;
84 : : class label_region;
85 : : class decl_region;
86 : : class symbolic_region;
87 : : class element_region;
88 : : class offset_region;
89 : : class sized_region;
90 : : class cast_region;
91 : : class field_region;
92 : : class string_region;
93 : : class bit_range_region;
94 : : class var_arg_region;
95 : : class region_model_manager;
96 : : class conjured_purge;
97 : : struct model_merger;
98 : : class store_manager;
99 : : class store;
100 : : class region_model;
101 : : class region_model_context;
102 : : class impl_region_model_context;
103 : : class call_details;
104 : : class rejected_constraint;
105 : : class constraint_manager;
106 : : class equiv_class;
107 : : class reachable_regions;
108 : : class bounded_ranges;
109 : : class bounded_ranges_manager;
110 : :
111 : : struct pending_location;
112 : : class pending_diagnostic;
113 : : class pending_note;
114 : : class saved_diagnostic;
115 : : struct event_loc_info;
116 : : class checker_event;
117 : : class state_change_event;
118 : : class warning_event;
119 : : class checker_path;
120 : : class extrinsic_state;
121 : : class sm_state_map;
122 : : class stmt_finder;
123 : : class program_point;
124 : : class function_point;
125 : : class program_state;
126 : : class exploded_graph;
127 : : class exploded_node;
128 : : class exploded_edge;
129 : : class feasibility_problem;
130 : : class exploded_cluster;
131 : : class exploded_path;
132 : : class analysis_plan;
133 : : class state_purge_map;
134 : : class state_purge_per_ssa_name;
135 : : class state_purge_per_decl;
136 : : class state_change;
137 : : class rewind_info_t;
138 : :
139 : : class engine;
140 : : class state_machine;
141 : : class logger;
142 : : class visitor;
143 : : class known_function_manager;
144 : : class call_summary;
145 : : class call_summary_replay;
146 : : struct per_function_data;
147 : : struct interesting_t;
148 : :
149 : : class feasible_node;
150 : :
151 : : class known_function;
152 : : class builtin_known_function;
153 : : class internal_known_function;
154 : :
155 : : /* Forward decls of functions. */
156 : :
157 : : extern void dump_tree (pretty_printer *pp, tree t);
158 : : extern void dump_quoted_tree (pretty_printer *pp, tree t);
159 : : extern void print_quoted_type (pretty_printer *pp, tree t);
160 : : extern void print_expr_for_user (pretty_printer *pp, tree t);
161 : : extern int readability_comparator (const void *p1, const void *p2);
162 : : extern int tree_cmp (const void *p1, const void *p2);
163 : : extern tree fixup_tree_for_diagnostic (tree);
164 : : extern tree get_diagnostic_tree_for_gassign (const gassign *);
165 : :
166 : : /* A tree, extended with stack frame information for locals, so that
167 : : we can distinguish between different values of locals within a potentially
168 : : recursive callstack. */
169 : :
170 : : class path_var
171 : : {
172 : : public:
173 : 27610 : path_var (tree t, int stack_depth)
174 : 4387952 : : m_tree (t), m_stack_depth (stack_depth)
175 : : {
176 : : // TODO: ignore stack depth for globals and constants
177 : : }
178 : :
179 : 40 : bool operator== (const path_var &other) const
180 : : {
181 : 40 : return (m_tree == other.m_tree
182 : 40 : && m_stack_depth == other.m_stack_depth);
183 : : }
184 : :
185 : 11058 : operator bool () const
186 : : {
187 : 11058 : return m_tree != NULL_TREE;
188 : : }
189 : :
190 : : void dump (pretty_printer *pp) const;
191 : :
192 : : tree m_tree;
193 : : int m_stack_depth; // or -1 for globals?
194 : : };
195 : :
196 : : typedef offset_int bit_offset_t;
197 : : typedef offset_int bit_size_t;
198 : : typedef offset_int byte_offset_t;
199 : : typedef offset_int byte_size_t;
200 : :
201 : : extern bool int_size_in_bits (const_tree type, bit_size_t *out);
202 : :
203 : : extern tree get_field_at_bit_offset (tree record_type, bit_offset_t bit_offset);
204 : :
205 : : /* The location of a region expressesd as an offset relative to a
206 : : base region. */
207 : :
208 : : class region_offset
209 : : {
210 : : public:
211 : 1291 : region_offset ()
212 : 1291 : : m_base_region (nullptr), m_offset (0), m_sym_offset (nullptr)
213 : : {
214 : : }
215 : :
216 : 141662 : static region_offset make_concrete (const region *base_region,
217 : : bit_offset_t offset)
218 : : {
219 : 141662 : return region_offset (base_region, offset, nullptr);
220 : : }
221 : 4116 : static region_offset make_symbolic (const region *base_region,
222 : : const svalue *sym_offset)
223 : : {
224 : 4116 : return region_offset (base_region, 0, sym_offset);
225 : : }
226 : : static region_offset make_byte_offset (const region *base_region,
227 : : const svalue *num_bytes_sval);
228 : :
229 : 697596 : const region *get_base_region () const { return m_base_region; }
230 : :
231 : 2990 : bool concrete_p () const { return m_sym_offset == nullptr; }
232 : 4573440 : bool symbolic_p () const { return m_sym_offset != nullptr; }
233 : :
234 : 3012449 : bit_offset_t get_bit_offset () const
235 : : {
236 : 3012449 : gcc_assert (!symbolic_p ());
237 : 3012449 : return m_offset;
238 : : }
239 : :
240 : 7970 : bool get_concrete_byte_offset (byte_offset_t *out) const
241 : : {
242 : 7970 : gcc_assert (!symbolic_p ());
243 : 7970 : if (m_offset % BITS_PER_UNIT == 0)
244 : : {
245 : 7970 : *out = m_offset / BITS_PER_UNIT;
246 : 7970 : return true;
247 : : }
248 : : return false;
249 : : }
250 : :
251 : 14950 : const svalue *get_symbolic_byte_offset () const
252 : : {
253 : 14950 : gcc_assert (symbolic_p ());
254 : 14950 : return m_sym_offset;
255 : : }
256 : :
257 : : const svalue &calc_symbolic_bit_offset (region_model_manager *mgr) const;
258 : : const svalue *calc_symbolic_byte_offset (region_model_manager *mgr) const;
259 : :
260 : : bool operator== (const region_offset &other) const
261 : : {
262 : : return (m_base_region == other.m_base_region
263 : : && m_offset == other.m_offset
264 : : && m_sym_offset == other.m_sym_offset);
265 : : }
266 : :
267 : : void dump_to_pp (pretty_printer *pp, bool) const;
268 : : void dump (bool) const;
269 : :
270 : : private:
271 : 142208 : region_offset (const region *base_region, bit_offset_t offset,
272 : : const svalue *sym_offset)
273 : 140209 : : m_base_region (base_region), m_offset (offset), m_sym_offset (sym_offset)
274 : : {}
275 : :
276 : : const region *m_base_region;
277 : : bit_offset_t m_offset;
278 : : const svalue *m_sym_offset;
279 : : };
280 : :
281 : : extern bool operator< (const region_offset &, const region_offset &);
282 : : extern bool operator<= (const region_offset &, const region_offset &);
283 : : extern bool operator> (const region_offset &, const region_offset &);
284 : : extern bool operator>= (const region_offset &, const region_offset &);
285 : :
286 : : extern location_t get_stmt_location (const gimple *stmt, function *fun);
287 : :
288 : : extern bool compat_types_p (tree src_type, tree dst_type);
289 : :
290 : : /* Abstract base class for simulating the behavior of known functions,
291 : : supplied by the core of the analyzer, or by plugins.
292 : : The former are typically implemented in the various kf*.cc */
293 : :
294 : 164050 : class known_function
295 : : {
296 : : public:
297 : 369 : virtual ~known_function () {}
298 : : virtual bool matches_call_types_p (const call_details &cd) const = 0;
299 : 18930 : virtual void impl_call_pre (const call_details &) const
300 : : {
301 : 18930 : return;
302 : : }
303 : 31758 : virtual void impl_call_post (const call_details &) const
304 : : {
305 : 31758 : return;
306 : : }
307 : :
308 : : virtual const builtin_known_function *
309 : 49794 : dyn_cast_builtin_kf () const { return nullptr; }
310 : : };
311 : :
312 : : /* Subclass of known_function for builtin functions. */
313 : :
314 : 157488 : class builtin_known_function : public known_function
315 : : {
316 : : public:
317 : : virtual enum built_in_function builtin_code () const = 0;
318 : 67928 : tree builtin_decl () const {
319 : 67928 : gcc_assert (builtin_code () < END_BUILTINS);
320 : 67928 : return builtin_info[builtin_code ()].decl;
321 : : }
322 : :
323 : : const builtin_known_function *
324 : 67928 : dyn_cast_builtin_kf () const final override { return this; }
325 : : };
326 : :
327 : : /* Subclass of known_function for IFN_* functions. */
328 : :
329 : 495431 : class internal_known_function : public known_function
330 : : {
331 : : public:
332 : 0 : bool matches_call_types_p (const call_details &) const final override
333 : : {
334 : : /* Types are assumed to be correct. */
335 : 0 : return true;
336 : : }
337 : : };
338 : :
339 : : /* Abstract subclass of known_function that merely sets the return
340 : : value of the function (based on function attributes), and assumes
341 : : it has no side-effects. */
342 : :
343 : 88587 : class pure_known_function_with_default_return : public known_function
344 : : {
345 : : public:
346 : : void impl_call_pre (const call_details &cd) const override;
347 : : };
348 : :
349 : : extern void register_known_functions (known_function_manager &kfm,
350 : : region_model_manager &rmm);
351 : : extern void register_known_analyzer_functions (known_function_manager &kfm);
352 : : extern void register_known_fd_functions (known_function_manager &kfm);
353 : : extern void register_known_file_functions (known_function_manager &kfm);
354 : : extern void register_known_functions_lang_cp (known_function_manager &kfm);
355 : : extern void register_varargs_builtins (known_function_manager &kfm);
356 : :
357 : : /* Passed by pointer to PLUGIN_ANALYZER_INIT callbacks. */
358 : :
359 : 3281 : class plugin_analyzer_init_iface
360 : : {
361 : : public:
362 : : virtual void register_state_machine (std::unique_ptr<state_machine>) = 0;
363 : : virtual void register_known_function (const char *name,
364 : : std::unique_ptr<known_function>) = 0;
365 : : virtual logger *get_logger () const = 0;
366 : : };
367 : :
368 : : /* An enum for describing the direction of an access to memory. */
369 : :
370 : : enum class access_direction
371 : : {
372 : : read,
373 : : write
374 : : };
375 : :
376 : : /* Abstract base class for associating custom data with an
377 : : exploded_edge, for handling non-standard edges such as
378 : : rewinding from a longjmp, signal handlers, etc.
379 : : Also used when "bifurcating" state: splitting the execution
380 : : path in non-standard ways (e.g. for simulating the various
381 : : outcomes of "realloc"). */
382 : :
383 : 20104 : class custom_edge_info
384 : : {
385 : : public:
386 : 25 : virtual ~custom_edge_info () {}
387 : :
388 : : /* Hook for making .dot label more readable. */
389 : : virtual void print (pretty_printer *pp) const = 0;
390 : :
391 : : /* Hook for updating STATE when handling bifurcation. */
392 : : virtual bool update_state (program_state *state,
393 : : const exploded_edge *eedge,
394 : : region_model_context *ctxt) const;
395 : :
396 : : /* Hook for updating MODEL within exploded_path::feasible_p
397 : : and when handling bifurcation. */
398 : : virtual bool update_model (region_model *model,
399 : : const exploded_edge *eedge,
400 : : region_model_context *ctxt) const = 0;
401 : :
402 : : virtual void add_events_to_path (checker_path *emission_path,
403 : : const exploded_edge &eedge) const = 0;
404 : :
405 : : virtual exploded_node *create_enode (exploded_graph &eg,
406 : : const program_point &point,
407 : : program_state &&state,
408 : : exploded_node *enode_for_diag,
409 : : region_model_context *ctxt) const;
410 : : };
411 : :
412 : : /* Abstract base class for splitting state.
413 : :
414 : : Most of the state-management code in the analyzer involves
415 : : modifying state objects in-place, which assumes a single outcome.
416 : :
417 : : This class provides an escape hatch to allow for multiple outcomes
418 : : for such updates e.g. for modelling multiple outcomes from function
419 : : calls, such as the various outcomes of "realloc". */
420 : :
421 : 249853 : class path_context
422 : : {
423 : : public:
424 : 125734 : virtual ~path_context () {}
425 : :
426 : : /* Hook for clients to split state with a non-standard path. */
427 : : virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
428 : :
429 : : /* Hook for clients to terminate the standard path. */
430 : : virtual void terminate_path () = 0;
431 : :
432 : : /* Hook for clients to determine if the standard path has been
433 : : terminated. */
434 : : virtual bool terminate_path_p () const = 0;
435 : : };
436 : :
437 : : extern tree get_stashed_constant_by_name (const char *name);
438 : : extern void log_stashed_constants (logger *logger);
439 : :
440 : : extern FILE *get_or_create_any_logfile ();
441 : :
442 : : extern std::unique_ptr<json::value>
443 : : tree_to_json (tree node);
444 : :
445 : : extern std::unique_ptr<json::value>
446 : : diagnostic_event_id_to_json (const diagnostics::paths::event_id_t &);
447 : :
448 : : extern std::unique_ptr<json::value>
449 : : bit_offset_to_json (const bit_offset_t &offset);
450 : :
451 : : extern std::unique_ptr<json::value>
452 : : byte_offset_to_json (const byte_offset_t &offset);
453 : :
454 : : extern tristate
455 : : compare_constants (tree lhs_const, enum tree_code op, tree rhs_const);
456 : :
457 : : extern tree
458 : : get_string_cst_size (const_tree string_cst);
459 : :
460 : : extern tree
461 : : get_ssa_default_def (const function &fun, tree var);
462 : :
463 : : extern const svalue *
464 : : strip_types (const svalue *sval, region_model_manager &mgr);
465 : :
466 : : extern region_offset
467 : : strip_types (const region_offset &offset, region_model_manager &mgr);
468 : :
469 : : extern tree remove_ssa_names (tree expr);
470 : :
471 : : } // namespace ana
472 : :
473 : : extern bool is_special_named_call_p (const gcall &call, const char *funcname,
474 : : unsigned int num_args,
475 : : bool look_in_std = false);
476 : : extern bool is_named_call_p (const_tree fndecl, const char *funcname);
477 : : extern bool is_named_call_p (const_tree fndecl, const char *funcname,
478 : : const gcall &call, unsigned int num_args);
479 : : extern bool is_std_function_p (const_tree fndecl);
480 : : extern bool is_std_named_call_p (const_tree fndecl, const char *funcname);
481 : : extern bool is_std_named_call_p (const_tree fndecl, const char *funcname,
482 : : const gcall &call, unsigned int num_args);
483 : : extern bool is_setjmp_call_p (const gcall &call);
484 : : extern bool is_longjmp_call_p (const gcall &call);
485 : : extern bool is_placement_new_p (const gcall &call);
486 : : extern bool is_cxa_throw_p (const gcall &call);
487 : : extern bool is_cxa_rethrow_p (const gcall &call);
488 : :
489 : : extern const char *get_user_facing_name (const gcall &call);
490 : :
491 : : extern void register_analyzer_pass ();
492 : :
493 : : extern label_text make_label_text (bool can_colorize, const char *fmt, ...);
494 : : extern label_text make_label_text_n (bool can_colorize,
495 : : unsigned HOST_WIDE_INT n,
496 : : const char *singular_fmt,
497 : : const char *plural_fmt, ...);
498 : :
499 : : extern bool fndecl_has_gimple_body_p (tree fndecl);
500 : :
501 : : /* An RAII-style class for pushing/popping cfun within a scope.
502 : : Doing so ensures we get "In function " announcements
503 : : from the diagnostics subsystem. */
504 : :
505 : : class auto_cfun
506 : : {
507 : : public:
508 : 839314 : auto_cfun (function *fun) { push_cfun (fun); }
509 : 839314 : ~auto_cfun () { pop_cfun (); }
510 : : };
511 : :
512 : : /* A template for creating hash traits for a POD type. */
513 : :
514 : : template <typename Type>
515 : : struct pod_hash_traits : typed_noop_remove<Type>
516 : : {
517 : : typedef Type value_type;
518 : : typedef Type compare_type;
519 : : static inline hashval_t hash (value_type);
520 : : static inline bool equal (const value_type &existing,
521 : : const value_type &candidate);
522 : : static inline void mark_deleted (Type &);
523 : : static inline void mark_empty (Type &);
524 : : static inline bool is_deleted (Type);
525 : : static inline bool is_empty (Type);
526 : : };
527 : :
528 : : /* A hash traits class that uses member functions to implement
529 : : the various required ops. */
530 : :
531 : : template <typename Type>
532 : : struct member_function_hash_traits : public typed_noop_remove<Type>
533 : : {
534 : : typedef Type value_type;
535 : : typedef Type compare_type;
536 : 41184072 : static inline hashval_t hash (value_type v) { return v.hash (); }
537 : 38766812 : static inline bool equal (const value_type &existing,
538 : : const value_type &candidate)
539 : : {
540 : 59234449 : return existing == candidate;
541 : : }
542 : : static inline void mark_deleted (Type &t) { t.mark_deleted (); }
543 : 848095 : static inline void mark_empty (Type &t) { t.mark_empty (); }
544 : 11798943 : static inline bool is_deleted (Type t) { return t.is_deleted (); }
545 : 117966680 : static inline bool is_empty (Type t) { return t.is_empty (); }
546 : : };
547 : :
548 : : /* A map from T::key_t to T* for use in consolidating instances of T.
549 : : Owns all instances of T.
550 : : T::key_t should have operator== and be hashable. */
551 : :
552 : : template <typename T>
553 : : class consolidation_map
554 : : {
555 : : public:
556 : : typedef typename T::key_t key_t;
557 : : typedef T instance_t;
558 : : typedef hash_map<key_t, instance_t *> inner_map_t;
559 : : typedef typename inner_map_t::iterator iterator;
560 : :
561 : : /* Delete all instances of T. */
562 : :
563 : 42391 : ~consolidation_map ()
564 : : {
565 : 118674 : for (typename inner_map_t::iterator iter = m_inner_map.begin ();
566 : 194957 : iter != m_inner_map.end (); ++iter)
567 : 76283 : delete (*iter).second;
568 : 42391 : }
569 : :
570 : : /* Get the instance of T for K if one exists, or nullptr. */
571 : :
572 : 3833710 : T *get (const key_t &k) const
573 : : {
574 : 3833710 : if (instance_t **slot = const_cast<inner_map_t &> (m_inner_map).get (k))
575 : 3757427 : return *slot;
576 : : return nullptr;
577 : : }
578 : :
579 : : /* Take ownership of INSTANCE. */
580 : :
581 : 76283 : void put (const key_t &k, T *instance)
582 : : {
583 : 76283 : m_inner_map.put (k, instance);
584 : : }
585 : :
586 : 44 : size_t elements () const { return m_inner_map.elements (); }
587 : :
588 : 45 : iterator begin () const { return m_inner_map.begin (); }
589 : 68 : iterator end () const { return m_inner_map.end (); }
590 : :
591 : : private:
592 : : inner_map_t m_inner_map;
593 : : };
594 : :
595 : : /* Disable -Wformat-diag; we want to be able to use pp_printf
596 : : for logging/dumping without complying with the rules for diagnostics. */
597 : : #if __GNUC__ >= 10
598 : : #pragma GCC diagnostic ignored "-Wformat-diag"
599 : : #endif
600 : :
601 : : #if !ENABLE_ANALYZER
602 : : extern void sorry_no_analyzer ();
603 : : #endif /* #if !ENABLE_ANALYZER */
604 : :
605 : : #endif /* GCC_ANALYZER_COMMON_H */
|
