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