1 /* Utility functions for the analyzer.
2 Copyright (C) 2019-2023 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 "function.h"
25 #include "json.h"
26 #include "tristate.h"
27
28 class graphviz_out;
29
30 namespace ana {
31
32 /* Forward decls of common types, with indentation to show inheritance. */
33
34 class supergraph;
35 class supernode;
36 class superedge;
37 class cfg_superedge;
38 class switch_cfg_superedge;
39 class callgraph_superedge;
40 class call_superedge;
41 class return_superedge;
42
43 class svalue;
44 class region_svalue;
45 class constant_svalue;
46 class unknown_svalue;
47 class poisoned_svalue;
48 class setjmp_svalue;
49 class initial_svalue;
50 class unaryop_svalue;
51 class binop_svalue;
52 class sub_svalue;
53 class repeated_svalue;
54 class bits_within_svalue;
55 class unmergeable_svalue;
56 class placeholder_svalue;
57 class widening_svalue;
58 class compound_svalue;
59 class conjured_svalue;
60 class asm_output_svalue;
61 class const_fn_result_svalue;
62 typedef hash_set<const svalue *> svalue_set;
63 class region;
64 class frame_region;
65 class function_region;
66 class label_region;
67 class decl_region;
68 class symbolic_region;
69 class element_region;
70 class offset_region;
71 class sized_region;
72 class cast_region;
73 class field_region;
74 class string_region;
75 class bit_range_region;
76 class var_arg_region;
77 class region_model_manager;
78 class conjured_purge;
79 struct model_merger;
80 class store_manager;
81 class store;
82 class region_model;
83 class region_model_context;
84 class impl_region_model_context;
85 class call_details;
86 class rejected_constraint;
87 class constraint_manager;
88 class equiv_class;
89 class reachable_regions;
90 class bounded_ranges;
91 class bounded_ranges_manager;
92
93 class pending_diagnostic;
94 class pending_note;
95 struct event_loc_info;
96 class checker_event;
97 class state_change_event;
98 class warning_event;
99 class checker_path;
100 class extrinsic_state;
101 class sm_state_map;
102 class stmt_finder;
103 class program_point;
104 class function_point;
105 class program_state;
106 class exploded_graph;
107 class exploded_node;
108 class exploded_edge;
109 class feasibility_problem;
110 class exploded_cluster;
111 class exploded_path;
112 class analysis_plan;
113 class state_purge_map;
114 class state_purge_per_ssa_name;
115 class state_purge_per_decl;
116 class state_change;
117 class rewind_info_t;
118
119 class engine;
120 class state_machine;
121 class logger;
122 class visitor;
123 class known_function_manager;
124 class call_summary;
125 class call_summary_replay;
126 struct per_function_data;
127 struct interesting_t;
128
129 class feasible_node;
130
131 /* Forward decls of functions. */
132
133 extern void dump_tree (pretty_printer *pp, tree t);
134 extern void dump_quoted_tree (pretty_printer *pp, tree t);
135 extern void print_quoted_type (pretty_printer *pp, tree t);
136 extern int readability_comparator (const void *p1, const void *p2);
137 extern int tree_cmp (const void *p1, const void *p2);
138 extern tree fixup_tree_for_diagnostic (tree);
139 extern tree get_diagnostic_tree_for_gassign (const gassign *);
140
141 /* A tree, extended with stack frame information for locals, so that
142 we can distinguish between different values of locals within a potentially
143 recursive callstack. */
144
145 class path_var
146 {
147 public:
148 path_var (tree t, int stack_depth)
149 : m_tree (t), m_stack_depth (stack_depth)
150 {
151 // TODO: ignore stack depth for globals and constants
152 }
153
154 bool operator== (const path_var &other) const
155 {
156 return (m_tree == other.m_tree
157 && m_stack_depth == other.m_stack_depth);
158 }
159
160 operator bool () const
161 {
162 return m_tree != NULL_TREE;
163 }
164
165 void dump (pretty_printer *pp) const;
166
167 tree m_tree;
168 int m_stack_depth; // or -1 for globals?
169 };
170
171 typedef offset_int bit_offset_t;
172 typedef offset_int bit_size_t;
173 typedef offset_int byte_offset_t;
174 typedef offset_int byte_size_t;
175
176 extern bool int_size_in_bits (const_tree type, bit_size_t *out);
177
178 extern tree get_field_at_bit_offset (tree record_type, bit_offset_t bit_offset);
179
180 /* The location of a region expressesd as an offset relative to a
181 base region. */
182
183 class region_offset
184 {
185 public:
186 static region_offset make_concrete (const region *base_region,
187 bit_offset_t offset)
188 {
189 return region_offset (base_region, offset, NULL);
190 }
191 static region_offset make_symbolic (const region *base_region,
192 const svalue *sym_offset)
193 {
194 return region_offset (base_region, 0, sym_offset);
195 }
196
197 const region *get_base_region () const { return m_base_region; }
198
199 bool symbolic_p () const { return m_sym_offset != NULL; }
200
201 bit_offset_t get_bit_offset () const
202 {
203 gcc_assert (!symbolic_p ());
204 return m_offset;
205 }
206
207 const svalue *get_symbolic_byte_offset () const
208 {
209 gcc_assert (symbolic_p ());
210 return m_sym_offset;
211 }
212
213 bool operator== (const region_offset &other) const
214 {
215 return (m_base_region == other.m_base_region
216 && m_offset == other.m_offset
217 && m_sym_offset == other.m_sym_offset);
218 }
219
220 private:
221 region_offset (const region *base_region, bit_offset_t offset,
222 const svalue *sym_offset)
223 : m_base_region (base_region), m_offset (offset), m_sym_offset (sym_offset)
224 {}
225
226 const region *m_base_region;
227 bit_offset_t m_offset;
228 const svalue *m_sym_offset;
229 };
230
231 extern location_t get_stmt_location (const gimple *stmt, function *fun);
232
233 extern bool compat_types_p (tree src_type, tree dst_type);
234
235 /* Abstract base class for simulating the behavior of known functions,
236 supplied by the core of the analyzer, or by plugins.
237 The former are typically implemented in the various kf*.cc */
238
239 class known_function
240 {
241 public:
242 virtual ~known_function () {}
243 virtual bool matches_call_types_p (const call_details &cd) const = 0;
244 virtual void impl_call_pre (const call_details &) const
245 {
246 return;
247 }
248 virtual void impl_call_post (const call_details &) const
249 {
250 return;
251 }
252 };
253
254 /* Subclass of known_function for IFN_* functions. */
255
256 class internal_known_function : public known_function
257 {
258 public:
259 bool matches_call_types_p (const call_details &) const final override
260 {
261 /* Types are assumed to be correct. */
262 return true;
263 }
264 };
265
266 extern void register_known_functions (known_function_manager &mgr);
267 extern void register_known_analyzer_functions (known_function_manager &kfm);
268 extern void register_known_fd_functions (known_function_manager &kfm);
269 extern void register_known_file_functions (known_function_manager &kfm);
270 extern void register_known_functions_lang_cp (known_function_manager &kfm);
271 extern void register_varargs_builtins (known_function_manager &kfm);
272
273 /* Passed by pointer to PLUGIN_ANALYZER_INIT callbacks. */
274
275 class plugin_analyzer_init_iface
276 {
277 public:
278 virtual void register_state_machine (std::unique_ptr<state_machine>) = 0;
279 virtual void register_known_function (const char *name,
280 std::unique_ptr<known_function>) = 0;
281 virtual logger *get_logger () const = 0;
282 };
283
284 /* An enum for describing the direction of an access to memory. */
285
286 enum access_direction
287 {
288 DIR_READ,
289 DIR_WRITE
290 };
291
292 /* Abstract base class for associating custom data with an
293 exploded_edge, for handling non-standard edges such as
294 rewinding from a longjmp, signal handlers, etc.
295 Also used when "bifurcating" state: splitting the execution
296 path in non-standard ways (e.g. for simulating the various
297 outcomes of "realloc"). */
298
299 class custom_edge_info
300 {
301 public:
302 virtual ~custom_edge_info () {}
303
304 /* Hook for making .dot label more readable. */
305 virtual void print (pretty_printer *pp) const = 0;
306
307 /* Hook for updating STATE when handling bifurcation. */
308 virtual bool update_state (program_state *state,
309 const exploded_edge *eedge,
310 region_model_context *ctxt) const;
311
312 /* Hook for updating MODEL within exploded_path::feasible_p
313 and when handling bifurcation. */
314 virtual bool update_model (region_model *model,
315 const exploded_edge *eedge,
316 region_model_context *ctxt) const = 0;
317
318 virtual void add_events_to_path (checker_path *emission_path,
319 const exploded_edge &eedge) const = 0;
320 };
321
322 /* Abstract base class for splitting state.
323
324 Most of the state-management code in the analyzer involves
325 modifying state objects in-place, which assumes a single outcome.
326
327 This class provides an escape hatch to allow for multiple outcomes
328 for such updates e.g. for modelling multiple outcomes from function
329 calls, such as the various outcomes of "realloc". */
330
331 class path_context
332 {
333 public:
334 virtual ~path_context () {}
335
336 /* Hook for clients to split state with a non-standard path. */
337 virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
338
339 /* Hook for clients to terminate the standard path. */
340 virtual void terminate_path () = 0;
341
342 /* Hook for clients to determine if the standard path has been
343 terminated. */
344 virtual bool terminate_path_p () const = 0;
345 };
346
347 extern tree get_stashed_constant_by_name (const char *name);
348 extern void log_stashed_constants (logger *logger);
349
350 extern FILE *get_or_create_any_logfile ();
351
352 } // namespace ana
353
354 extern bool is_special_named_call_p (const gcall *call, const char *funcname,
355 unsigned int num_args);
356 extern bool is_named_call_p (const_tree fndecl, const char *funcname);
357 extern bool is_named_call_p (const_tree fndecl, const char *funcname,
358 const gcall *call, unsigned int num_args);
359 extern bool is_std_named_call_p (const_tree fndecl, const char *funcname);
360 extern bool is_std_named_call_p (const_tree fndecl, const char *funcname,
361 const gcall *call, unsigned int num_args);
362 extern bool is_setjmp_call_p (const gcall *call);
363 extern bool is_longjmp_call_p (const gcall *call);
364
365 extern const char *get_user_facing_name (const gcall *call);
366
367 extern void register_analyzer_pass ();
368
369 extern label_text make_label_text (bool can_colorize, const char *fmt, ...);
370 extern label_text make_label_text_n (bool can_colorize,
371 unsigned HOST_WIDE_INT n,
372 const char *singular_fmt,
373 const char *plural_fmt, ...);
374
375 extern bool fndecl_has_gimple_body_p (tree fndecl);
376
377 /* An RAII-style class for pushing/popping cfun within a scope.
378 Doing so ensures we get "In function " announcements
379 from the diagnostics subsystem. */
380
381 class auto_cfun
382 {
383 public:
384 auto_cfun (function *fun) { push_cfun (fun); }
385 ~auto_cfun () { pop_cfun (); }
386 };
387
388 /* A template for creating hash traits for a POD type. */
389
390 template <typename Type>
391 struct pod_hash_traits : typed_noop_remove<Type>
392 {
393 typedef Type value_type;
394 typedef Type compare_type;
395 static inline hashval_t hash (value_type);
396 static inline bool equal (const value_type &existing,
397 const value_type &candidate);
398 static inline void mark_deleted (Type &);
399 static inline void mark_empty (Type &);
400 static inline bool is_deleted (Type);
401 static inline bool is_empty (Type);
402 };
403
404 /* A hash traits class that uses member functions to implement
405 the various required ops. */
406
407 template <typename Type>
408 struct member_function_hash_traits : public typed_noop_remove<Type>
409 {
410 typedef Type value_type;
411 typedef Type compare_type;
412 static inline hashval_t hash (value_type v) { return v.hash (); }
413 static inline bool equal (const value_type &existing,
414 const value_type &candidate)
415 {
416 return existing == candidate;
417 }
418 static inline void mark_deleted (Type &t) { t.mark_deleted (); }
419 static inline void mark_empty (Type &t) { t.mark_empty (); }
420 static inline bool is_deleted (Type t) { return t.is_deleted (); }
421 static inline bool is_empty (Type t) { return t.is_empty (); }
422 };
423
424 /* A map from T::key_t to T* for use in consolidating instances of T.
425 Owns all instances of T.
426 T::key_t should have operator== and be hashable. */
427
428 template <typename T>
429 class consolidation_map
430 {
431 public:
432 typedef typename T::key_t key_t;
433 typedef T instance_t;
434 typedef hash_map<key_t, instance_t *> inner_map_t;
435 typedef typename inner_map_t::iterator iterator;
436
437 /* Delete all instances of T. */
438
439 ~consolidation_map ()
440 {
441 for (typename inner_map_t::iterator iter = m_inner_map.begin ();
442 iter != m_inner_map.end (); ++iter)
443 delete (*iter).second;
444 }
445
446 /* Get the instance of T for K if one exists, or NULL. */
447
448 T *get (const key_t &k) const
449 {
450 if (instance_t **slot = const_cast<inner_map_t &> (m_inner_map).get (k))
451 return *slot;
452 return NULL;
453 }
454
455 /* Take ownership of INSTANCE. */
456
457 void put (const key_t &k, T *instance)
458 {
459 m_inner_map.put (k, instance);
460 }
461
462 size_t elements () const { return m_inner_map.elements (); }
463
464 iterator begin () const { return m_inner_map.begin (); }
465 iterator end () const { return m_inner_map.end (); }
466
467 private:
468 inner_map_t m_inner_map;
469 };
470
471 /* Disable -Wformat-diag; we want to be able to use pp_printf
472 for logging/dumping without complying with the rules for diagnostics. */
473 #if __GNUC__ >= 10
474 #pragma GCC diagnostic ignored "-Wformat-diag"
475 #endif
476
477 #if !ENABLE_ANALYZER
478 extern void sorry_no_analyzer ();
479 #endif /* #if !ENABLE_ANALYZER */
480
481 #endif /* GCC_ANALYZER_ANALYZER_H */