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