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