gcc/analyzer/analyzer.h

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