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