gcc/analyzer/analyzer.h

   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 "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 int readability_comparator (const void *p1, const void *p2);
 144 extern int tree_cmp (const void *p1, const void *p2);
 145 extern tree fixup_tree_for_diagnostic (tree);
 146 extern tree get_diagnostic_tree_for_gassign (const gassign *);
 147
 148 /* A tree, extended with stack frame information for locals, so that
 149    we can distinguish between different values of locals within a potentially
 150    recursive callstack.  */
 151
 152 class path_var
 153 {
 154 public:
 155   path_var (tree t, int stack_depth)
 156   : m_tree (t), m_stack_depth (stack_depth)
 157   {
 158     // TODO: ignore stack depth for globals and constants
 159   }
 160
 161   bool operator== (const path_var &other) const
 162   {
 163     return (m_tree == other.m_tree
 164             && m_stack_depth == other.m_stack_depth);
 165   }
 166
 167   operator bool () const
 168   {
 169     return m_tree != NULL_TREE;
 170   }
 171
 172   void dump (pretty_printer *pp) const;
 173
 174   tree m_tree;
 175   int m_stack_depth; // or -1 for globals?
 176 };
 177
 178 typedef offset_int bit_offset_t;
 179 typedef offset_int bit_size_t;
 180 typedef offset_int byte_offset_t;
 181 typedef offset_int byte_size_t;
 182
 183 extern bool int_size_in_bits (const_tree type, bit_size_t *out);
 184
 185 extern tree get_field_at_bit_offset (tree record_type, bit_offset_t bit_offset);
 186
 187 /* The location of a region expressesd as an offset relative to a
 188    base region.  */
 189
 190 class region_offset
 191 {
 192 public:
 193   region_offset ()
 194   : m_base_region (NULL), m_offset (0), m_sym_offset (NULL)
 195   {
 196   }
 197
 198   static region_offset make_concrete (const region *base_region,
 199                                       bit_offset_t offset)
 200   {
 201     return region_offset (base_region, offset, NULL);
 202   }
 203   static region_offset make_symbolic (const region *base_region,
 204                                       const svalue *sym_offset)
 205   {
 206     return region_offset (base_region, 0, sym_offset);
 207   }
 208   static region_offset make_byte_offset (const region *base_region,
 209                                          const svalue *num_bytes_sval);
 210
 211   const region *get_base_region () const { return m_base_region; }
 212
 213   bool concrete_p () const { return m_sym_offset == NULL; }
 214   bool symbolic_p () const { return m_sym_offset != NULL; }
 215
 216   bit_offset_t get_bit_offset () const
 217   {
 218     gcc_assert (!symbolic_p ());
 219     return m_offset;
 220   }
 221
 222   bool get_concrete_byte_offset (byte_offset_t *out) const
 223   {
 224     gcc_assert (!symbolic_p ());
 225     if (m_offset % BITS_PER_UNIT == 0)
 226       {
 227         *out = m_offset / BITS_PER_UNIT;
 228         return true;
 229       }
 230     return false;
 231   }
 232
 233   const svalue *get_symbolic_byte_offset () const
 234   {
 235     gcc_assert (symbolic_p ());
 236     return m_sym_offset;
 237   }
 238
 239   tree calc_symbolic_bit_offset (const region_model &model) const;
 240   const svalue *calc_symbolic_byte_offset (region_model_manager *mgr) const;
 241
 242   bool operator== (const region_offset &other) const
 243   {
 244     return (m_base_region == other.m_base_region
 245             && m_offset == other.m_offset
 246             && m_sym_offset == other.m_sym_offset);
 247   }
 248
 249   void dump_to_pp (pretty_printer *pp, bool) const;
 250   void dump (bool) const;
 251
 252 private:
 253   region_offset (const region *base_region, bit_offset_t offset,
 254                  const svalue *sym_offset)
 255   : m_base_region (base_region), m_offset (offset), m_sym_offset (sym_offset)
 256   {}
 257
 258   const region *m_base_region;
 259   bit_offset_t m_offset;
 260   const svalue *m_sym_offset;
 261 };
 262
 263 extern bool operator< (const region_offset &, const region_offset &);
 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
 268 extern location_t get_stmt_location (const gimple *stmt, function *fun);
 269
 270 extern bool compat_types_p (tree src_type, tree dst_type);
 271
 272 /* Abstract base class for simulating the behavior of known functions,
 273    supplied by the core of the analyzer, or by plugins.
 274    The former are typically implemented in the various kf*.cc  */
 275
 276 class known_function
 277 {
 278 public:
 279   virtual ~known_function () {}
 280   virtual bool matches_call_types_p (const call_details &cd) const = 0;
 281   virtual void impl_call_pre (const call_details &) const
 282   {
 283     return;
 284   }
 285   virtual void impl_call_post (const call_details &) const
 286   {
 287     return;
 288   }
 289
 290   virtual const builtin_known_function *
 291   dyn_cast_builtin_kf () const { return NULL; }
 292 };
 293
 294 /* Subclass of known_function for builtin functions.  */
 295
 296 class builtin_known_function : public known_function
 297 {
 298 public:
 299   virtual enum built_in_function builtin_code () const = 0;
 300   tree builtin_decl () const {
 301     gcc_assert (builtin_code () < END_BUILTINS);
 302     return builtin_info[builtin_code ()].decl;
 303   }
 304
 305   const builtin_known_function *
 306   dyn_cast_builtin_kf () const final override { return this; }
 307 };
 308
 309 /* Subclass of known_function for IFN_* functions.  */
 310
 311 class internal_known_function : public known_function
 312 {
 313 public:
 314   bool matches_call_types_p (const call_details &) const final override
 315   {
 316     /* Types are assumed to be correct.  */
 317     return true;
 318   }
 319 };
 320
 321 /* Abstract subclass of known_function that merely sets the return
 322    value of the function (based on function attributes), and assumes
 323    it has no side-effects.  */
 324
 325 class pure_known_function_with_default_return : public known_function
 326 {
 327 public:
 328   void impl_call_pre (const call_details &cd) const override;
 329 };
 330
 331 extern void register_known_functions (known_function_manager &kfm,
 332                                       region_model_manager &rmm);
 333 extern void register_known_analyzer_functions (known_function_manager &kfm);
 334 extern void register_known_fd_functions (known_function_manager &kfm);
 335 extern void register_known_file_functions (known_function_manager &kfm);
 336 extern void register_known_functions_lang_cp (known_function_manager &kfm);
 337 extern void register_varargs_builtins (known_function_manager &kfm);
 338
 339 /* Passed by pointer to PLUGIN_ANALYZER_INIT callbacks.  */
 340
 341 class plugin_analyzer_init_iface
 342 {
 343 public:
 344   virtual void register_state_machine (std::unique_ptr<state_machine>) = 0;
 345   virtual void register_known_function (const char *name,
 346                                         std::unique_ptr<known_function>) = 0;
 347   virtual logger *get_logger () const = 0;
 348 };
 349
 350 /* An enum for describing the direction of an access to memory.  */
 351
 352 enum access_direction
 353 {
 354   DIR_READ,
 355   DIR_WRITE
 356 };
 357
 358 /* Abstract base class for associating custom data with an
 359    exploded_edge, for handling non-standard edges such as
 360    rewinding from a longjmp, signal handlers, etc.
 361    Also used when "bifurcating" state: splitting the execution
 362    path in non-standard ways (e.g. for simulating the various
 363    outcomes of "realloc").  */
 364
 365 class custom_edge_info
 366 {
 367 public:
 368   virtual ~custom_edge_info () {}
 369
 370   /* Hook for making .dot label more readable.  */
 371   virtual void print (pretty_printer *pp) const = 0;
 372
 373   /* Hook for updating STATE when handling bifurcation.  */
 374   virtual bool update_state (program_state *state,
 375                              const exploded_edge *eedge,
 376                              region_model_context *ctxt) const;
 377
 378   /* Hook for updating MODEL within exploded_path::feasible_p
 379      and when handling bifurcation.  */
 380   virtual bool update_model (region_model *model,
 381                              const exploded_edge *eedge,
 382                              region_model_context *ctxt) const = 0;
 383
 384   virtual void add_events_to_path (checker_path *emission_path,
 385                                    const exploded_edge &eedge) const = 0;
 386 };
 387
 388 /* Abstract base class for splitting state.
 389
 390    Most of the state-management code in the analyzer involves
 391    modifying state objects in-place, which assumes a single outcome.
 392
 393    This class provides an escape hatch to allow for multiple outcomes
 394    for such updates e.g. for modelling multiple outcomes from function
 395    calls, such as the various outcomes of "realloc".  */
 396
 397 class path_context
 398 {
 399 public:
 400   virtual ~path_context () {}
 401
 402   /* Hook for clients to split state with a non-standard path.  */
 403   virtual void bifurcate (std::unique_ptr<custom_edge_info> info) = 0;
 404
 405   /* Hook for clients to terminate the standard path.  */
 406   virtual void terminate_path () = 0;
 407
 408   /* Hook for clients to determine if the standard path has been
 409      terminated.  */
 410   virtual bool terminate_path_p () const = 0;
 411 };
 412
 413 extern tree get_stashed_constant_by_name (const char *name);
 414 extern void log_stashed_constants (logger *logger);
 415
 416 extern FILE *get_or_create_any_logfile ();
 417
 418 } // namespace ana
 419
 420 extern bool is_special_named_call_p (const gcall *call, const char *funcname,
 421                                      unsigned int num_args);
 422 extern bool is_named_call_p (const_tree fndecl, const char *funcname);
 423 extern bool is_named_call_p (const_tree fndecl, const char *funcname,
 424                              const gcall *call, unsigned int num_args);
 425 extern bool is_std_named_call_p (const_tree fndecl, const char *funcname);
 426 extern bool is_std_named_call_p (const_tree fndecl, const char *funcname,
 427                                  const gcall *call, unsigned int num_args);
 428 extern bool is_setjmp_call_p (const gcall *call);
 429 extern bool is_longjmp_call_p (const gcall *call);
 430 extern bool is_placement_new_p (const gcall *call);
 431
 432 extern const char *get_user_facing_name (const gcall *call);
 433
 434 extern void register_analyzer_pass ();
 435
 436 extern label_text make_label_text (bool can_colorize, const char *fmt, ...);
 437 extern label_text make_label_text_n (bool can_colorize,
 438                                      unsigned HOST_WIDE_INT n,
 439                                      const char *singular_fmt,
 440                                      const char *plural_fmt, ...);
 441
 442 extern bool fndecl_has_gimple_body_p (tree fndecl);
 443
 444 /* An RAII-style class for pushing/popping cfun within a scope.
 445    Doing so ensures we get "In function " announcements
 446    from the diagnostics subsystem.  */
 447
 448 class auto_cfun
 449 {
 450 public:
 451   auto_cfun (function *fun) { push_cfun (fun); }
 452   ~auto_cfun () { pop_cfun (); }
 453 };
 454
 455 /* A template for creating hash traits for a POD type.  */
 456
 457 template <typename Type>
 458 struct pod_hash_traits : typed_noop_remove<Type>
 459 {
 460   typedef Type value_type;
 461   typedef Type compare_type;
 462   static inline hashval_t hash (value_type);
 463   static inline bool equal (const value_type &existing,
 464                             const value_type &candidate);
 465   static inline void mark_deleted (Type &);
 466   static inline void mark_empty (Type &);
 467   static inline bool is_deleted (Type);
 468   static inline bool is_empty (Type);
 469 };
 470
 471 /* A hash traits class that uses member functions to implement
 472    the various required ops.  */
 473
 474 template <typename Type>
 475 struct member_function_hash_traits : public typed_noop_remove<Type>
 476 {
 477   typedef Type value_type;
 478   typedef Type compare_type;
 479   static inline hashval_t hash (value_type v) { return v.hash (); }
 480   static inline bool equal (const value_type &existing,
 481                             const value_type &candidate)
 482   {
 483     return existing == candidate;
 484   }
 485   static inline void mark_deleted (Type &t) { t.mark_deleted (); }
 486   static inline void mark_empty (Type &t) { t.mark_empty (); }
 487   static inline bool is_deleted (Type t) { return t.is_deleted (); }
 488   static inline bool is_empty (Type t) { return t.is_empty (); }
 489 };
 490
 491 /* A map from T::key_t to T* for use in consolidating instances of T.
 492    Owns all instances of T.
 493    T::key_t should have operator== and be hashable.  */
 494
 495 template <typename T>
 496 class consolidation_map
 497 {
 498 public:
 499   typedef typename T::key_t key_t;
 500   typedef T instance_t;
 501   typedef hash_map<key_t, instance_t *> inner_map_t;
 502   typedef typename inner_map_t::iterator iterator;
 503
 504   /* Delete all instances of T.  */
 505
 506   ~consolidation_map ()
 507   {
 508     for (typename inner_map_t::iterator iter = m_inner_map.begin ();
 509          iter != m_inner_map.end (); ++iter)
 510       delete (*iter).second;
 511   }
 512
 513   /* Get the instance of T for K if one exists, or NULL.  */
 514
 515   T *get (const key_t &k) const
 516   {
 517     if (instance_t **slot = const_cast<inner_map_t &> (m_inner_map).get (k))
 518       return *slot;
 519     return NULL;
 520   }
 521
 522   /* Take ownership of INSTANCE.  */
 523
 524   void put (const key_t &k, T *instance)
 525   {
 526     m_inner_map.put (k, instance);
 527   }
 528
 529   size_t elements () const { return m_inner_map.elements (); }
 530
 531   iterator begin () const { return m_inner_map.begin (); }
 532   iterator end () const { return m_inner_map.end (); }
 533
 534 private:
 535   inner_map_t m_inner_map;
 536 };
 537
 538 /* Disable -Wformat-diag; we want to be able to use pp_printf
 539    for logging/dumping without complying with the rules for diagnostics.  */
 540 #if __GNUC__ >= 10
 541 #pragma GCC diagnostic ignored "-Wformat-diag"
 542 #endif
 543
 544 #if !ENABLE_ANALYZER
 545 extern void sorry_no_analyzer ();
 546 #endif /* #if !ENABLE_ANALYZER */
 547
 548 #endif /* GCC_ANALYZER_ANALYZER_H */