gcc/analyzer/analyzer.h

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