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