Branch data Line data Source code
1 : : /* Utility functions for the analyzer.
2 : : Copyright (C) 2019-2024 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_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 : :
29 : : class graphviz_out;
30 : :
31 : : namespace ana {
32 : :
33 : : /* Forward decls of common types, with indentation to show inheritance. */
34 : :
35 : : class supergraph;
36 : : class supernode;
37 : : class superedge;
38 : : class cfg_superedge;
39 : : class switch_cfg_superedge;
40 : : class callgraph_superedge;
41 : : class call_superedge;
42 : : class return_superedge;
43 : :
44 : : class 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;
63 : : typedef hash_set<const svalue *> svalue_set;
64 : : class 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;
78 : : class region_model_manager;
79 : : class conjured_purge;
80 : : struct model_merger;
81 : : class store_manager;
82 : : class store;
83 : : class region_model;
84 : : class region_model_context;
85 : : class impl_region_model_context;
86 : : class call_details;
87 : : class rejected_constraint;
88 : : class constraint_manager;
89 : : class equiv_class;
90 : : class reachable_regions;
91 : : class bounded_ranges;
92 : : class bounded_ranges_manager;
93 : :
94 : : struct pending_location;
95 : : class pending_diagnostic;
96 : : class pending_note;
97 : : class saved_diagnostic;
98 : : struct event_loc_info;
99 : : class checker_event;
100 : : class state_change_event;
101 : : class warning_event;
102 : : class checker_path;
103 : : class extrinsic_state;
104 : : class sm_state_map;
105 : : class stmt_finder;
106 : : class program_point;
107 : : class function_point;
108 : : class program_state;
109 : : class exploded_graph;
110 : : class exploded_node;
111 : : class exploded_edge;
112 : : class feasibility_problem;
113 : : class exploded_cluster;
114 : : class exploded_path;
115 : : class analysis_plan;
116 : : class state_purge_map;
117 : : class state_purge_per_ssa_name;
118 : : class state_purge_per_decl;
119 : : class state_change;
120 : : class rewind_info_t;
121 : :
122 : : class engine;
123 : : class state_machine;
124 : : class logger;
125 : : class visitor;
126 : : class known_function_manager;
127 : : class call_summary;
128 : : class call_summary_replay;
129 : : struct per_function_data;
130 : : struct interesting_t;
131 : :
132 : : class feasible_node;
133 : :
134 : : class known_function;
135 : : class builtin_known_function;
136 : : class internal_known_function;
137 : :
138 : : /* Forward decls of functions. */
139 : :
140 : : extern void dump_tree (pretty_printer *pp, tree t);
141 : : extern void dump_quoted_tree (pretty_printer *pp, tree t);
142 : : extern void print_quoted_type (pretty_printer *pp, tree t);
143 : : extern void print_expr_for_user (pretty_printer *pp, tree t);
144 : : extern int readability_comparator (const void *p1, const void *p2);
145 : : extern int tree_cmp (const void *p1, const void *p2);
146 : : extern tree fixup_tree_for_diagnostic (tree);
147 : : extern 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 : :
153 : : class path_var
154 : : {
155 : : public:
156 : 27103 : path_var (tree t, int stack_depth)
157 : 4299420 : : m_tree (t), m_stack_depth (stack_depth)
158 : : {
159 : : // TODO: ignore stack depth for globals and constants
160 : : }
161 : :
162 : 40 : bool operator== (const path_var &other) const
163 : : {
164 : 40 : return (m_tree == other.m_tree
165 : 40 : && m_stack_depth == other.m_stack_depth);
166 : : }
167 : :
168 : 10929 : operator bool () const
169 : : {
170 : 10929 : 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 : :
179 : : typedef offset_int bit_offset_t;
180 : : typedef offset_int bit_size_t;
181 : : typedef offset_int byte_offset_t;
182 : : typedef offset_int byte_size_t;
183 : :
184 : : extern bool int_size_in_bits (const_tree type, bit_size_t *out);
185 : :
186 : : extern 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 : :
191 : : class region_offset
192 : : {
193 : : public:
194 : 1291 : region_offset ()
195 : 1291 : : m_base_region (NULL), m_offset (0), m_sym_offset (NULL)
196 : : {
197 : : }
198 : :
199 : 135004 : static region_offset make_concrete (const region *base_region,
200 : : bit_offset_t offset)
201 : : {
202 : 135004 : return region_offset (base_region, offset, NULL);
203 : : }
204 : 4327 : static region_offset make_symbolic (const region *base_region,
205 : : const svalue *sym_offset)
206 : : {
207 : 4327 : 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 : 683249 : const region *get_base_region () const { return m_base_region; }
213 : :
214 : 2039 : bool concrete_p () const { return m_sym_offset == NULL; }
215 : 4547441 : bool symbolic_p () const { return m_sym_offset != NULL; }
216 : :
217 : 3015713 : bit_offset_t get_bit_offset () const
218 : : {
219 : 3015713 : gcc_assert (!symbolic_p ());
220 : 3015713 : return m_offset;
221 : : }
222 : :
223 : 8033 : bool get_concrete_byte_offset (byte_offset_t *out) const
224 : : {
225 : 8033 : gcc_assert (!symbolic_p ());
226 : 8033 : if (m_offset % BITS_PER_UNIT == 0)
227 : : {
228 : 8033 : *out = m_offset / BITS_PER_UNIT;
229 : 8033 : return true;
230 : : }
231 : : return false;
232 : : }
233 : :
234 : 15155 : const svalue *get_symbolic_byte_offset () const
235 : : {
236 : 15155 : gcc_assert (symbolic_p ());
237 : 15155 : 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 : :
253 : : private:
254 : 135773 : region_offset (const region *base_region, bit_offset_t offset,
255 : : const svalue *sym_offset)
256 : 133551 : : 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 : :
264 : : extern bool operator< (const region_offset &, const region_offset &);
265 : : extern bool operator<= (const region_offset &, const region_offset &);
266 : : extern bool operator> (const region_offset &, const region_offset &);
267 : : extern bool operator>= (const region_offset &, const region_offset &);
268 : :
269 : : extern location_t get_stmt_location (const gimple *stmt, function *fun);
270 : :
271 : : extern 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 : :
277 : 147154 : class known_function
278 : : {
279 : : public:
280 : 513 : virtual ~known_function () {}
281 : : virtual bool matches_call_types_p (const call_details &cd) const = 0;
282 : 18846 : virtual void impl_call_pre (const call_details &) const
283 : : {
284 : 18846 : return;
285 : : }
286 : 30699 : virtual void impl_call_post (const call_details &) const
287 : : {
288 : 30699 : return;
289 : : }
290 : :
291 : : virtual const builtin_known_function *
292 : 46944 : dyn_cast_builtin_kf () const { return NULL; }
293 : : };
294 : :
295 : : /* Subclass of known_function for builtin functions. */
296 : :
297 : 150353 : class builtin_known_function : public known_function
298 : : {
299 : : public:
300 : : virtual enum built_in_function builtin_code () const = 0;
301 : 67450 : tree builtin_decl () const {
302 : 67450 : gcc_assert (builtin_code () < END_BUILTINS);
303 : 67450 : return builtin_info[builtin_code ()].decl;
304 : : }
305 : :
306 : : const builtin_known_function *
307 : 67450 : dyn_cast_builtin_kf () const final override { return this; }
308 : : };
309 : :
310 : : /* Subclass of known_function for IFN_* functions. */
311 : :
312 : 476651 : class internal_known_function : public known_function
313 : : {
314 : : public:
315 : 0 : bool matches_call_types_p (const call_details &) const final override
316 : : {
317 : : /* Types are assumed to be correct. */
318 : 0 : 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 : :
326 : 86373 : class pure_known_function_with_default_return : public known_function
327 : : {
328 : : public:
329 : : void impl_call_pre (const call_details &cd) const override;
330 : : };
331 : :
332 : : extern void register_known_functions (known_function_manager &kfm,
333 : : region_model_manager &rmm);
334 : : extern void register_known_analyzer_functions (known_function_manager &kfm);
335 : : extern void register_known_fd_functions (known_function_manager &kfm);
336 : : extern void register_known_file_functions (known_function_manager &kfm);
337 : : extern void register_known_functions_lang_cp (known_function_manager &kfm);
338 : : extern void register_varargs_builtins (known_function_manager &kfm);
339 : :
340 : : /* Passed by pointer to PLUGIN_ANALYZER_INIT callbacks. */
341 : :
342 : 3199 : class plugin_analyzer_init_iface
343 : : {
344 : : public:
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 : :
353 : : enum 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 : :
366 : 7105 : class custom_edge_info
367 : : {
368 : : public:
369 : 25 : 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 : :
398 : 240023 : class path_context
399 : : {
400 : : public:
401 : 124107 : 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 : :
414 : : extern tree get_stashed_constant_by_name (const char *name);
415 : : extern void log_stashed_constants (logger *logger);
416 : :
417 : : extern FILE *get_or_create_any_logfile ();
418 : :
419 : : extern std::unique_ptr<json::value>
420 : : tree_to_json (tree node);
421 : :
422 : : extern std::unique_ptr<json::value>
423 : : diagnostic_event_id_to_json (const diagnostic_event_id_t &);
424 : :
425 : : extern std::unique_ptr<json::value>
426 : : bit_offset_to_json (const bit_offset_t &offset);
427 : :
428 : : extern std::unique_ptr<json::value>
429 : : byte_offset_to_json (const byte_offset_t &offset);
430 : :
431 : : extern tristate
432 : : compare_constants (tree lhs_const, enum tree_code op, tree rhs_const);
433 : :
434 : : extern tree
435 : : get_string_cst_size (const_tree string_cst);
436 : :
437 : : extern tree
438 : : get_ssa_default_def (const function &fun, tree var);
439 : :
440 : : extern const svalue *
441 : : strip_types (const svalue *sval, region_model_manager &mgr);
442 : :
443 : : extern region_offset
444 : : strip_types (const region_offset &offset, region_model_manager &mgr);
445 : :
446 : : extern tree remove_ssa_names (tree expr);
447 : :
448 : : } // namespace ana
449 : :
450 : : extern bool is_special_named_call_p (const gcall *call, const char *funcname,
451 : : unsigned int num_args,
452 : : bool look_in_std = false);
453 : : extern bool is_named_call_p (const_tree fndecl, const char *funcname);
454 : : extern bool is_named_call_p (const_tree fndecl, const char *funcname,
455 : : const gcall *call, unsigned int num_args);
456 : : extern bool is_std_function_p (const_tree fndecl);
457 : : extern bool is_std_named_call_p (const_tree fndecl, const char *funcname);
458 : : extern bool is_std_named_call_p (const_tree fndecl, const char *funcname,
459 : : const gcall *call, unsigned int num_args);
460 : : extern bool is_setjmp_call_p (const gcall *call);
461 : : extern bool is_longjmp_call_p (const gcall *call);
462 : : extern bool is_placement_new_p (const gcall *call);
463 : :
464 : : extern const char *get_user_facing_name (const gcall *call);
465 : :
466 : : extern void register_analyzer_pass ();
467 : :
468 : : extern label_text make_label_text (bool can_colorize, const char *fmt, ...);
469 : : extern label_text make_label_text_n (bool can_colorize,
470 : : unsigned HOST_WIDE_INT n,
471 : : const char *singular_fmt,
472 : : const char *plural_fmt, ...);
473 : :
474 : : extern bool fndecl_has_gimple_body_p (tree fndecl);
475 : :
476 : : /* An RAII-style class for pushing/popping cfun within a scope.
477 : : Doing so ensures we get "In function " announcements
478 : : from the diagnostics subsystem. */
479 : :
480 : : class auto_cfun
481 : : {
482 : : public:
483 : 802644 : auto_cfun (function *fun) { push_cfun (fun); }
484 : 802644 : ~auto_cfun () { pop_cfun (); }
485 : : };
486 : :
487 : : /* A template for creating hash traits for a POD type. */
488 : :
489 : : template <typename Type>
490 : : struct pod_hash_traits : typed_noop_remove<Type>
491 : : {
492 : : typedef Type value_type;
493 : : typedef Type compare_type;
494 : : static inline hashval_t hash (value_type);
495 : : static inline bool equal (const value_type &existing,
496 : : const value_type &candidate);
497 : : static inline void mark_deleted (Type &);
498 : : static inline void mark_empty (Type &);
499 : : static inline bool is_deleted (Type);
500 : : static inline bool is_empty (Type);
501 : : };
502 : :
503 : : /* A hash traits class that uses member functions to implement
504 : : the various required ops. */
505 : :
506 : : template <typename Type>
507 : : struct member_function_hash_traits : public typed_noop_remove<Type>
508 : : {
509 : : typedef Type value_type;
510 : : typedef Type compare_type;
511 : 40478110 : static inline hashval_t hash (value_type v) { return v.hash (); }
512 : 38270409 : static inline bool equal (const value_type &existing,
513 : : const value_type &candidate)
514 : : {
515 : 58181338 : return existing == candidate;
516 : : }
517 : : static inline void mark_deleted (Type &t) { t.mark_deleted (); }
518 : 830612 : static inline void mark_empty (Type &t) { t.mark_empty (); }
519 : 11986351 : static inline bool is_deleted (Type t) { return t.is_deleted (); }
520 : 116083974 : static inline bool is_empty (Type t) { return t.is_empty (); }
521 : : };
522 : :
523 : : /* A map from T::key_t to T* for use in consolidating instances of T.
524 : : Owns all instances of T.
525 : : T::key_t should have operator== and be hashable. */
526 : :
527 : : template <typename T>
528 : : class consolidation_map
529 : : {
530 : : public:
531 : : typedef typename T::key_t key_t;
532 : : typedef T instance_t;
533 : : typedef hash_map<key_t, instance_t *> inner_map_t;
534 : : typedef typename inner_map_t::iterator iterator;
535 : :
536 : : /* Delete all instances of T. */
537 : :
538 : 41489 : ~consolidation_map ()
539 : : {
540 : 113414 : for (typename inner_map_t::iterator iter = m_inner_map.begin ();
541 : 185339 : iter != m_inner_map.end (); ++iter)
542 : 71925 : delete (*iter).second;
543 : 41489 : }
544 : :
545 : : /* Get the instance of T for K if one exists, or NULL. */
546 : :
547 : 3823794 : T *get (const key_t &k) const
548 : : {
549 : 3823794 : if (instance_t **slot = const_cast<inner_map_t &> (m_inner_map).get (k))
550 : 3751869 : return *slot;
551 : : return NULL;
552 : : }
553 : :
554 : : /* Take ownership of INSTANCE. */
555 : :
556 : 71925 : void put (const key_t &k, T *instance)
557 : : {
558 : 71925 : m_inner_map.put (k, instance);
559 : : }
560 : :
561 : 44 : size_t elements () const { return m_inner_map.elements (); }
562 : :
563 : 45 : iterator begin () const { return m_inner_map.begin (); }
564 : 68 : iterator end () const { return m_inner_map.end (); }
565 : :
566 : : private:
567 : : inner_map_t m_inner_map;
568 : : };
569 : :
570 : : /* Disable -Wformat-diag; we want to be able to use pp_printf
571 : : for logging/dumping without complying with the rules for diagnostics. */
572 : : #if __GNUC__ >= 10
573 : : #pragma GCC diagnostic ignored "-Wformat-diag"
574 : : #endif
575 : :
576 : : #if !ENABLE_ANALYZER
577 : : extern void sorry_no_analyzer ();
578 : : #endif /* #if !ENABLE_ANALYZER */
579 : :
580 : : #endif /* GCC_ANALYZER_ANALYZER_H */
|
