gcc/analyzer/analyzer.h

   1 /* Utility functions for the analyzer.
   2    Copyright (C) 2019-2024 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 extern json::value *
 419 tree_to_json (tree node);
 420
 421 extern json::value *
 422 diagnostic_event_id_to_json (const diagnostic_event_id_t &);
 423
 424 extern json::value *
 425 bit_offset_to_json (const bit_offset_t &offset);
 426
 427 extern json::value *
 428 byte_offset_to_json (const byte_offset_t &offset);
 429
 430 } // namespace ana
 431
 432 extern bool is_special_named_call_p (const gcall *call, const char *funcname,
 433                                      unsigned int num_args);
 434 extern bool is_named_call_p (const_tree fndecl, const char *funcname);
 435 extern bool is_named_call_p (const_tree fndecl, const char *funcname,
 436                              const gcall *call, unsigned int num_args);
 437 extern bool is_std_named_call_p (const_tree fndecl, const char *funcname);
 438 extern bool is_std_named_call_p (const_tree fndecl, const char *funcname,
 439                                  const gcall *call, unsigned int num_args);
 440 extern bool is_setjmp_call_p (const gcall *call);
 441 extern bool is_longjmp_call_p (const gcall *call);
 442 extern bool is_placement_new_p (const gcall *call);
 443
 444 extern const char *get_user_facing_name (const gcall *call);
 445
 446 extern void register_analyzer_pass ();
 447
 448 extern label_text make_label_text (bool can_colorize, const char *fmt, ...);
 449 extern label_text make_label_text_n (bool can_colorize,
 450                                      unsigned HOST_WIDE_INT n,
 451                                      const char *singular_fmt,
 452                                      const char *plural_fmt, ...);
 453
 454 extern bool fndecl_has_gimple_body_p (tree fndecl);
 455
 456 /* An RAII-style class for pushing/popping cfun within a scope.
 457    Doing so ensures we get "In function " announcements
 458    from the diagnostics subsystem.  */
 459
 460 class auto_cfun
 461 {
 462 public:
 463   auto_cfun (function *fun) { push_cfun (fun); }
 464   ~auto_cfun () { pop_cfun (); }
 465 };
 466
 467 /* A template for creating hash traits for a POD type.  */
 468
 469 template <typename Type>
 470 struct pod_hash_traits : typed_noop_remove<Type>
 471 {
 472   typedef Type value_type;
 473   typedef Type compare_type;
 474   static inline hashval_t hash (value_type);
 475   static inline bool equal (const value_type &existing,
 476                             const value_type &candidate);
 477   static inline void mark_deleted (Type &);
 478   static inline void mark_empty (Type &);
 479   static inline bool is_deleted (Type);
 480   static inline bool is_empty (Type);
 481 };
 482
 483 /* A hash traits class that uses member functions to implement
 484    the various required ops.  */
 485
 486 template <typename Type>
 487 struct member_function_hash_traits : public typed_noop_remove<Type>
 488 {
 489   typedef Type value_type;
 490   typedef Type compare_type;
 491   static inline hashval_t hash (value_type v) { return v.hash (); }
 492   static inline bool equal (const value_type &existing,
 493                             const value_type &candidate)
 494   {
 495     return existing == candidate;
 496   }
 497   static inline void mark_deleted (Type &t) { t.mark_deleted (); }
 498   static inline void mark_empty (Type &t) { t.mark_empty (); }
 499   static inline bool is_deleted (Type t) { return t.is_deleted (); }
 500   static inline bool is_empty (Type t) { return t.is_empty (); }
 501 };
 502
 503 /* A map from T::key_t to T* for use in consolidating instances of T.
 504    Owns all instances of T.
 505    T::key_t should have operator== and be hashable.  */
 506
 507 template <typename T>
 508 class consolidation_map
 509 {
 510 public:
 511   typedef typename T::key_t key_t;
 512   typedef T instance_t;
 513   typedef hash_map<key_t, instance_t *> inner_map_t;
 514   typedef typename inner_map_t::iterator iterator;
 515
 516   /* Delete all instances of T.  */
 517
 518   ~consolidation_map ()
 519   {
 520     for (typename inner_map_t::iterator iter = m_inner_map.begin ();
 521          iter != m_inner_map.end (); ++iter)
 522       delete (*iter).second;
 523   }
 524
 525   /* Get the instance of T for K if one exists, or NULL.  */
 526
 527   T *get (const key_t &k) const
 528   {
 529     if (instance_t **slot = const_cast<inner_map_t &> (m_inner_map).get (k))
 530       return *slot;
 531     return NULL;
 532   }
 533
 534   /* Take ownership of INSTANCE.  */
 535
 536   void put (const key_t &k, T *instance)
 537   {
 538     m_inner_map.put (k, instance);
 539   }
 540
 541   size_t elements () const { return m_inner_map.elements (); }
 542
 543   iterator begin () const { return m_inner_map.begin (); }
 544   iterator end () const { return m_inner_map.end (); }
 545
 546 private:
 547   inner_map_t m_inner_map;
 548 };
 549
 550 /* Disable -Wformat-diag; we want to be able to use pp_printf
 551    for logging/dumping without complying with the rules for diagnostics.  */
 552 #if __GNUC__ >= 10
 553 #pragma GCC diagnostic ignored "-Wformat-diag"
 554 #endif
 555
 556 #if !ENABLE_ANALYZER
 557 extern void sorry_no_analyzer ();
 558 #endif /* #if !ENABLE_ANALYZER */
 559
 560 #endif /* GCC_ANALYZER_ANALYZER_H */