gcc/analyzer/diagnostic-manager.cc

   1 /* Classes for saving, deduplicating, and emitting analyzer diagnostics.
   2    Copyright (C) 2019-2020 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 #include "config.h"
  22 #include "system.h"
  23 #include "coretypes.h"
  24 #include "tree.h"
  25 #include "pretty-print.h"
  26 #include "gcc-rich-location.h"
  27 #include "gimple-pretty-print.h"
  28 #include "function.h"
  29 #include "diagnostic-core.h"
  30 #include "diagnostic-event-id.h"
  31 #include "diagnostic-path.h"
  32 #include "alloc-pool.h"
  33 #include "fibonacci_heap.h"
  34 #include "shortest-paths.h"
  35 #include "sbitmap.h"
  36 #include "tristate.h"
  37 #include "selftest.h"
  38 #include "ordered-hash-map.h"
  39 #include "analyzer/analyzer.h"
  40 #include "analyzer/analyzer-logging.h"
  41 #include "analyzer/sm.h"
  42 #include "analyzer/pending-diagnostic.h"
  43 #include "analyzer/diagnostic-manager.h"
  44 #include "analyzer/region-model.h"
  45 #include "analyzer/constraint-manager.h"
  46 #include "cfg.h"
  47 #include "basic-block.h"
  48 #include "gimple.h"
  49 #include "gimple-iterator.h"
  50 #include "cgraph.h"
  51 #include "digraph.h"
  52 #include "analyzer/supergraph.h"
  53 #include "analyzer/call-string.h"
  54 #include "analyzer/program-point.h"
  55 #include "analyzer/program-state.h"
  56 #include "analyzer/exploded-graph.h"
  57 #include "analyzer/checker-path.h"
  58
  59 #if ENABLE_ANALYZER
  60
  61 /* class saved_diagnostic.  */
  62
  63 /* saved_diagnostic's ctor.
  64    Take ownership of D and STMT_FINDER.  */
  65
  66 saved_diagnostic::saved_diagnostic (const state_machine *sm,
  67                                     const exploded_node *enode,
  68                                     const supernode *snode, const gimple *stmt,
  69                                     stmt_finder *stmt_finder,
  70                                     tree var, state_machine::state_t state,
  71                                     pending_diagnostic *d)
  72 : m_sm (sm), m_enode (enode), m_snode (snode), m_stmt (stmt),
  73  /* stmt_finder could be on-stack; we want our own copy that can
  74     outlive that.  */
  75   m_stmt_finder (stmt_finder ? stmt_finder->clone () : NULL),
  76   m_var (var), m_state (state),
  77   m_d (d), m_trailing_eedge (NULL)
  78 {
  79   gcc_assert (m_stmt || m_stmt_finder);
  80
  81   /* We must have an enode in order to be able to look for paths
  82      through the exploded_graph to this diagnostic.  */
  83   gcc_assert (m_enode);
  84 }
  85
  86 /* saved_diagnostic's dtor.  */
  87
  88 saved_diagnostic::~saved_diagnostic ()
  89 {
  90   delete m_stmt_finder;
  91   delete m_d;
  92 }
  93
  94 bool
  95 saved_diagnostic::operator== (const saved_diagnostic &other) const
  96 {
  97   return (m_sm == other.m_sm
  98           /* We don't compare m_enode.  */
  99           && m_snode == other.m_snode
 100           && m_stmt == other.m_stmt
 101           /* We don't compare m_stmt_finder.  */
 102           && pending_diagnostic::same_tree_p (m_var, other.m_var)
 103           && m_state == other.m_state
 104           && m_d->equal_p (*other.m_d)
 105           && m_trailing_eedge == other.m_trailing_eedge);
 106 }
 107
 108 /* class diagnostic_manager.  */
 109
 110 /* diagnostic_manager's ctor.  */
 111
 112 diagnostic_manager::diagnostic_manager (logger *logger, int verbosity)
 113 : log_user (logger), m_verbosity (verbosity)
 114 {
 115 }
 116
 117 /* Queue pending_diagnostic D at ENODE for later emission.  */
 118
 119 void
 120 diagnostic_manager::add_diagnostic (const state_machine *sm,
 121                                     const exploded_node *enode,
 122                                     const supernode *snode, const gimple *stmt,
 123                                     stmt_finder *finder,
 124                                     tree var, state_machine::state_t state,
 125                                     pending_diagnostic *d)
 126 {
 127   LOG_FUNC (get_logger ());
 128
 129   /* We must have an enode in order to be able to look for paths
 130      through the exploded_graph to the diagnostic.  */
 131   gcc_assert (enode);
 132
 133   saved_diagnostic *sd
 134     = new saved_diagnostic (sm, enode, snode, stmt, finder, var, state, d);
 135   m_saved_diagnostics.safe_push (sd);
 136   if (get_logger ())
 137     log ("adding saved diagnostic %i at SN %i: %qs",
 138          m_saved_diagnostics.length () - 1,
 139          snode->m_index, d->get_kind ());
 140 }
 141
 142 /* Queue pending_diagnostic D at ENODE for later emission.  */
 143
 144 void
 145 diagnostic_manager::add_diagnostic (const exploded_node *enode,
 146                                     const supernode *snode, const gimple *stmt,
 147                                     stmt_finder *finder,
 148                                     pending_diagnostic *d)
 149 {
 150   gcc_assert (enode);
 151   add_diagnostic (NULL, enode, snode, stmt, finder, NULL_TREE, 0, d);
 152 }
 153
 154 /* A class for identifying sets of duplicated pending_diagnostic.
 155
 156    We want to find the simplest dedupe_candidate amongst those that share a
 157    dedupe_key.  */
 158
 159 class dedupe_key
 160 {
 161 public:
 162   dedupe_key (const saved_diagnostic &sd,
 163               const exploded_path &epath)
 164   : m_sd (sd), m_stmt (sd.m_stmt)
 165   {
 166     /* Support deferring the choice of stmt until after an emission path has
 167      been built, using an optional stmt_finder.  */
 168     if (m_stmt == NULL)
 169       {
 170         gcc_assert (sd.m_stmt_finder);
 171         m_stmt = sd.m_stmt_finder->find_stmt (epath);
 172       }
 173     gcc_assert (m_stmt);
 174   }
 175
 176   hashval_t hash () const
 177   {
 178     inchash::hash hstate;
 179     hstate.add_ptr (m_stmt);
 180     // TODO: m_sd
 181     return hstate.end ();
 182   }
 183   bool operator== (const dedupe_key &other) const
 184   {
 185     return (m_sd == other.m_sd
 186             && m_stmt == other.m_stmt);
 187   }
 188
 189   location_t get_location () const
 190   {
 191     return m_stmt->location;
 192   }
 193
 194   /* A qsort comparator for use by dedupe_winners::emit_best
 195      to sort them into location_t order.  */
 196
 197   static int
 198   comparator (const void *p1, const void *p2)
 199   {
 200     const dedupe_key *pk1 = *(const dedupe_key * const *)p1;
 201     const dedupe_key *pk2 = *(const dedupe_key * const *)p2;
 202
 203     location_t loc1 = pk1->get_location ();
 204     location_t loc2 = pk2->get_location ();
 205
 206     return linemap_compare_locations (line_table, loc2, loc1);
 207   }
 208
 209   const saved_diagnostic &m_sd;
 210   const gimple *m_stmt;
 211 };
 212
 213 /* The value of a slot for a dedupe_key within dedupe_winners:
 214    the exploded_path for the best candidate for that key, and the
 215    number of duplicates seen so far.  */
 216
 217 class dedupe_candidate
 218 {
 219 public:
 220   // has the exploded_path
 221   dedupe_candidate (const shortest_exploded_paths &sp,
 222                     const saved_diagnostic &sd)
 223   : m_epath (sp.get_shortest_path (sd.m_enode)),
 224     m_num_dupes (0)
 225   {
 226   }
 227
 228   unsigned length () const { return m_epath.length (); }
 229   const exploded_path &get_path () const { return m_epath; }
 230
 231   void add_duplicate () { m_num_dupes++; }
 232   int get_num_dupes () const { return m_num_dupes; }
 233
 234 private:
 235   exploded_path m_epath;
 236 public:
 237   int m_num_dupes;
 238 };
 239
 240 /* Traits for use by dedupe_winners.  */
 241
 242 class dedupe_hash_map_traits
 243 {
 244 public:
 245   typedef const dedupe_key *key_type;
 246   typedef dedupe_candidate *value_type;
 247   typedef dedupe_candidate *compare_type;
 248
 249   static inline hashval_t hash (const key_type &v)
 250   {
 251     return v->hash ();
 252   }
 253   static inline bool equal_keys (const key_type &k1, const key_type &k2)
 254   {
 255     return *k1 == *k2;
 256   }
 257   template <typename T>
 258   static inline void remove (T &)
 259   {
 260     // TODO
 261   }
 262   template <typename T>
 263   static inline void mark_deleted (T &entry)
 264   {
 265     entry.m_key = reinterpret_cast<key_type> (1);
 266   }
 267   template <typename T>
 268   static inline void mark_empty (T &entry)
 269   {
 270     entry.m_key = NULL;
 271   }
 272   template <typename T>
 273   static inline bool is_deleted (const T &entry)
 274   {
 275     return entry.m_key == reinterpret_cast<key_type> (1);
 276   }
 277   template <typename T>
 278   static inline bool is_empty (const T &entry)
 279   {
 280     return entry.m_key == NULL;
 281   }
 282   static const bool empty_zero_p = true;
 283 };
 284
 285 /* A class for deduplicating diagnostics and finding (and emitting) the
 286    best diagnostic within each partition.  */
 287
 288 class dedupe_winners
 289 {
 290 public:
 291   ~dedupe_winners ()
 292   {
 293     /* Delete all keys and candidates.  */
 294     for (map_t::iterator iter = m_map.begin ();
 295          iter != m_map.end ();
 296          ++iter)
 297       {
 298         delete (*iter).first;
 299         delete (*iter).second;
 300       }
 301   }
 302
 303   /* Determine an exploded_path for SD using SP and, if it's feasible,
 304      determine if it's the best seen so far for its dedupe_key.
 305      Retain the winner for each dedupe_key, and discard the rest.  */
 306
 307   void add (logger *logger,
 308             const shortest_exploded_paths &sp,
 309             const saved_diagnostic &sd)
 310   {
 311     /* Build a dedupe_candidate for SD.
 312        This uses SP to build an exploded_path.  */
 313     dedupe_candidate *dc = new dedupe_candidate (sp, sd);
 314
 315     /* Verify that the epath is feasible.
 316        State-merging means that not every path in the epath corresponds
 317        to a feasible one w.r.t. states.
 318        Here we simply check each duplicate saved_diagnostic's
 319        shortest_path, and reject any that aren't feasible.
 320        This could introduce false negatives, as there could be longer
 321        feasible paths within the egraph.  */
 322     if (logger)
 323       logger->log ("considering %qs at SN: %i",
 324                    sd.m_d->get_kind (), sd.m_snode->m_index);
 325     if (!dc->get_path ().feasible_p (logger))
 326       {
 327         if (logger)
 328           logger->log ("rejecting %qs at SN: %i"
 329                        " due to infeasible path",
 330                        sd.m_d->get_kind (), sd.m_snode->m_index);
 331         delete dc;
 332         return;
 333       }
 334     else
 335       if (logger)
 336         logger->log ("accepting %qs at SN: %i with feasible path",
 337                      sd.m_d->get_kind (), sd.m_snode->m_index);
 338
 339     dedupe_key *key = new dedupe_key (sd, dc->get_path ());
 340     if (dedupe_candidate **slot = m_map.get (key))
 341       {
 342         if (logger)
 343           logger->log ("already have this dedupe_key");
 344
 345         (*slot)->add_duplicate ();
 346
 347         if (dc->length () < (*slot)->length ())
 348           {
 349             /* We've got a shorter path for the key; replace
 350                the current candidate.  */
 351             if (logger)
 352               logger->log ("length %i is better than existing length %i;"
 353                            " taking over this dedupe_key",
 354                            dc->length (), (*slot)->length ());
 355             dc->m_num_dupes = (*slot)->get_num_dupes ();
 356             delete *slot;
 357             *slot = dc;
 358           }
 359         else
 360           /* We haven't beaten the current best candidate;
 361              drop the new candidate.  */
 362           {
 363             if (logger)
 364               logger->log ("length %i isn't better than existing length %i;"
 365                            " dropping this candidate",
 366                            dc->length (), (*slot)->length ());
 367             delete dc;
 368           }
 369         delete key;
 370       }
 371     else
 372       {
 373         /* This is the first candidate for this key.  */
 374         m_map.put (key, dc);
 375         if (logger)
 376           logger->log ("first candidate for this dedupe_key");
 377       }
 378   }
 379
 380  /* Emit the simplest diagnostic within each set.  */
 381
 382   void emit_best (diagnostic_manager *dm,
 383                   const exploded_graph &eg)
 384   {
 385     LOG_SCOPE (dm->get_logger ());
 386
 387     /* Get keys into a vec for sorting.  */
 388     auto_vec<const dedupe_key *> keys (m_map.elements ());
 389     for (map_t::iterator iter = m_map.begin ();
 390          iter != m_map.end ();
 391          ++iter)
 392       keys.quick_push ((*iter).first);
 393
 394     dm->log ("# keys after de-duplication: %i", keys.length ());
 395
 396     /* Sort into a good emission order.  */
 397     keys.qsort (dedupe_key::comparator);
 398
 399     /* Emit the best candidate for each key.  */
 400     int i;
 401     const dedupe_key *key;
 402     FOR_EACH_VEC_ELT (keys, i, key)
 403       {
 404         dedupe_candidate **slot = m_map.get (key);
 405         gcc_assert (*slot);
 406         const dedupe_candidate &dc = **slot;
 407
 408         dm->emit_saved_diagnostic (eg, key->m_sd,
 409                                    dc.get_path (), key->m_stmt,
 410                                    dc.get_num_dupes ());
 411       }
 412   }
 413
 414 private:
 415
 416   /* This maps from each dedupe_key to a current best dedupe_candidate.  */
 417
 418   typedef hash_map<const dedupe_key *, dedupe_candidate *,
 419                    dedupe_hash_map_traits> map_t;
 420   map_t m_map;
 421 };
 422
 423 /* Emit all saved diagnostics.  */
 424
 425 void
 426 diagnostic_manager::emit_saved_diagnostics (const exploded_graph &eg)
 427 {
 428   LOG_SCOPE (get_logger ());
 429   auto_timevar tv (TV_ANALYZER_DIAGNOSTICS);
 430   log ("# saved diagnostics: %i", m_saved_diagnostics.length ());
 431
 432   if (m_saved_diagnostics.length () == 0)
 433     return;
 434
 435   /* Compute the shortest_paths once, sharing it between all diagnostics.  */
 436   shortest_exploded_paths sp (eg, eg.get_origin ());
 437
 438   /* Iterate through all saved diagnostics, adding them to a dedupe_winners
 439      instance.  This partitions the saved diagnostics by dedupe_key,
 440      generating exploded_paths for them, and retaining the best one in each
 441      partition.  */
 442   dedupe_winners best_candidates;
 443
 444   int i;
 445   saved_diagnostic *sd;
 446   FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd)
 447     best_candidates.add (get_logger (), sp, *sd);
 448
 449   /* For each dedupe-key, call emit_saved_diagnostic on the "best"
 450      saved_diagnostic.  */
 451   best_candidates.emit_best (this, eg);
 452 }
 453
 454 /* Given a saved_diagnostic SD at STMT with feasible path EPATH through EG,
 455    create an checker_path of suitable events and use it to call
 456    SD's underlying pending_diagnostic "emit" vfunc to emit a diagnostic.  */
 457
 458 void
 459 diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg,
 460                                            const saved_diagnostic &sd,
 461                                            const exploded_path &epath,
 462                                            const gimple *stmt,
 463                                            int num_dupes)
 464 {
 465   LOG_SCOPE (get_logger ());
 466   log ("sd: %qs at SN: %i", sd.m_d->get_kind (), sd.m_snode->m_index);
 467   log ("num dupes: %i", num_dupes);
 468
 469   pretty_printer *pp = global_dc->printer->clone ();
 470
 471   checker_path emission_path;
 472
 473   /* Populate emission_path with a full description of EPATH.  */
 474   build_emission_path (eg, epath, &emission_path);
 475
 476   /* Now prune it to just cover the most pertinent events.  */
 477   prune_path (&emission_path, sd.m_sm, sd.m_var, sd.m_state);
 478
 479   /* Add a final event to the path, covering the diagnostic itself.
 480      We use the final enode from the epath, which might be different from
 481      the sd.m_enode, as the dedupe code doesn't care about enodes, just
 482      snodes.  */
 483   emission_path.add_final_event (sd.m_sm, epath.get_final_enode (), stmt,
 484                                  sd.m_var, sd.m_state);
 485
 486   /* The "final" event might not be final; if the saved_diagnostic has a
 487      trailing eedge stashed, add any events for it.  This is for use
 488      in handling longjmp, to show where a longjmp is rewinding to.  */
 489   if (sd.m_trailing_eedge)
 490     add_events_for_eedge (*sd.m_trailing_eedge, eg.get_ext_state (),
 491                           &emission_path);
 492
 493   emission_path.prepare_for_emission (sd.m_d);
 494
 495   gcc_rich_location rich_loc (stmt->location);
 496   rich_loc.set_path (&emission_path);
 497
 498   auto_diagnostic_group d;
 499   auto_cfun sentinel (sd.m_snode->m_fun);
 500   if (sd.m_d->emit (&rich_loc))
 501     {
 502       if (num_dupes > 0)
 503         inform_n (stmt->location, num_dupes,
 504                   "%i duplicate", "%i duplicates",
 505                   num_dupes);
 506     }
 507   delete pp;
 508 }
 509
 510 /* Given a state change to DST_REP, determine a tree that gives the origin
 511    of that state at STMT, using DST_STATE's region model, so that state
 512    changes based on assignments can be tracked back to their origins.
 513
 514    For example, if we have
 515
 516      (S1) _1 = malloc (64);
 517      (S2) EXPR = _1;
 518
 519    then at stmt S2 we can get the origin of EXPR's state as being _1,
 520    and thus track the allocation back to S1.  */
 521
 522 static tree
 523 get_any_origin (const gimple *stmt,
 524                 tree dst_rep,
 525                 const program_state &dst_state)
 526 {
 527   if (!stmt)
 528     return NULL_TREE;
 529
 530   gcc_assert (dst_rep);
 531
 532   if (const gassign *assign = dyn_cast <const gassign *> (stmt))
 533     {
 534       tree lhs = gimple_assign_lhs (assign);
 535       /* Use region IDs to compare lhs with DST_REP.  */
 536       if (dst_state.m_region_model->get_lvalue (lhs, NULL)
 537           == dst_state.m_region_model->get_lvalue (dst_rep, NULL))
 538         {
 539           tree rhs1 = gimple_assign_rhs1 (assign);
 540           enum tree_code op = gimple_assign_rhs_code (assign);
 541           switch (op)
 542             {
 543             default:
 544               //gcc_unreachable ();  // TODO
 545               break;
 546             case COMPONENT_REF:
 547             case SSA_NAME:
 548               return rhs1;
 549             }
 550         }
 551     }
 552   return NULL_TREE;
 553 }
 554
 555 /* Emit a "path" of events to EMISSION_PATH describing the exploded path
 556    EPATH within EG.  */
 557
 558 void
 559 diagnostic_manager::build_emission_path (const exploded_graph &eg,
 560                                          const exploded_path &epath,
 561                                          checker_path *emission_path) const
 562 {
 563   LOG_SCOPE (get_logger ());
 564   const extrinsic_state &ext_state = eg.get_ext_state ();
 565   for (unsigned i = 0; i < epath.m_edges.length (); i++)
 566     {
 567       const exploded_edge *eedge = epath.m_edges[i];
 568       add_events_for_eedge (*eedge, ext_state, emission_path);
 569     }
 570 }
 571
 572 /* Subclass of state_change_visitor that creates state_change_event
 573    instances.  */
 574
 575 class state_change_event_creator : public state_change_visitor
 576 {
 577 public:
 578   state_change_event_creator (const exploded_edge &eedge,
 579                               checker_path *emission_path)
 580     : m_eedge (eedge),
 581       m_emission_path (emission_path)
 582   {}
 583
 584   bool on_global_state_change (const state_machine &sm,
 585                                state_machine::state_t src_sm_val,
 586                                state_machine::state_t dst_sm_val)
 587     FINAL OVERRIDE
 588   {
 589     const exploded_node *src_node = m_eedge.m_src;
 590     const program_point &src_point = src_node->get_point ();
 591     const int src_stack_depth = src_point.get_stack_depth ();
 592     const exploded_node *dst_node = m_eedge.m_dest;
 593     const gimple *stmt = src_point.get_stmt ();
 594     const supernode *supernode = src_point.get_supernode ();
 595     const program_state &dst_state = dst_node->get_state ();
 596
 597     int stack_depth = src_stack_depth;
 598
 599     m_emission_path->add_event (new state_change_event (supernode,
 600                                                         stmt,
 601                                                         stack_depth,
 602                                                         sm,
 603                                                         NULL_TREE,
 604                                                         src_sm_val,
 605                                                         dst_sm_val,
 606                                                         NULL_TREE,
 607                                                         dst_state));
 608     return false;
 609   }
 610
 611   bool on_state_change (const state_machine &sm,
 612                         state_machine::state_t src_sm_val,
 613                         state_machine::state_t dst_sm_val,
 614                         tree dst_rep,
 615                         svalue_id dst_origin_sid) FINAL OVERRIDE
 616   {
 617     const exploded_node *src_node = m_eedge.m_src;
 618     const program_point &src_point = src_node->get_point ();
 619     const int src_stack_depth = src_point.get_stack_depth ();
 620     const exploded_node *dst_node = m_eedge.m_dest;
 621     const gimple *stmt = src_point.get_stmt ();
 622     const supernode *supernode = src_point.get_supernode ();
 623     const program_state &dst_state = dst_node->get_state ();
 624
 625     int stack_depth = src_stack_depth;
 626
 627     if (m_eedge.m_sedge
 628         && m_eedge.m_sedge->m_kind == SUPEREDGE_CFG_EDGE)
 629       {
 630         supernode = src_point.get_supernode ();
 631         stmt = supernode->get_last_stmt ();
 632         stack_depth = src_stack_depth;
 633       }
 634
 635     /* Bulletproofing for state changes at calls/returns;
 636        TODO: is there a better way? */
 637     if (!stmt)
 638       return false;
 639
 640     tree origin_rep
 641       = dst_state.get_representative_tree (dst_origin_sid);
 642
 643     if (origin_rep == NULL_TREE)
 644       origin_rep = get_any_origin (stmt, dst_rep, dst_state);
 645     m_emission_path->add_event (new state_change_event (supernode,
 646                                                         stmt,
 647                                                         stack_depth,
 648                                                         sm,
 649                                                         dst_rep,
 650                                                         src_sm_val,
 651                                                         dst_sm_val,
 652                                                         origin_rep,
 653                                                         dst_state));
 654     return false;
 655   }
 656
 657   const exploded_edge &m_eedge;
 658   checker_path *m_emission_path;
 659 };
 660
 661 /* Compare SRC_STATE and DST_STATE (which use EXT_STATE), and call
 662    VISITOR's on_state_change for every sm-state change that occurs
 663    to a tree, and on_global_state_change for every global state change
 664    that occurs.
 665
 666    This determines the state changes that ought to be reported to
 667    the user: a combination of the effects of changes to sm_state_map
 668    (which maps svalues to sm-states), and of region_model changes
 669    (which map trees to svalues).
 670
 671    Bail out early and return true if any call to on_global_state_change
 672    or on_state_change returns true, otherwise return false.
 673
 674    This is split out to make it easier to experiment with changes to
 675    exploded_node granularity (so that we can observe what state changes
 676    lead to state_change_events being emitted).  */
 677
 678 bool
 679 for_each_state_change (const program_state &src_state,
 680                        const program_state &dst_state,
 681                        const extrinsic_state &ext_state,
 682                        state_change_visitor *visitor)
 683 {
 684   gcc_assert (src_state.m_checker_states.length ()
 685               == ext_state.m_checkers.length ());
 686   gcc_assert (dst_state.m_checker_states.length ()
 687               == ext_state.m_checkers.length ());
 688   for (unsigned i = 0; i < ext_state.m_checkers.length (); i++)
 689     {
 690       const state_machine &sm = ext_state.get_sm (i);
 691       const sm_state_map &src_smap = *src_state.m_checker_states[i];
 692       const sm_state_map &dst_smap = *dst_state.m_checker_states[i];
 693
 694       /* Add events for any global state changes.  */
 695       if (src_smap.get_global_state () != dst_smap.get_global_state ())
 696         if (visitor->on_global_state_change (sm,
 697                                              src_smap.get_global_state (),
 698                                              dst_smap.get_global_state ()))
 699           return true;
 700
 701       /* Add events for per-svalue state changes.  */
 702       for (sm_state_map::iterator_t iter = dst_smap.begin ();
 703            iter != dst_smap.end ();
 704            ++iter)
 705         {
 706           /* Ideally we'd directly compare the SM state between src state
 707              and dst state, but there's no guarantee that the IDs can
 708              be meaningfully compared.  */
 709           svalue_id dst_sid = (*iter).first;
 710           state_machine::state_t dst_sm_val = (*iter).second.m_state;
 711
 712           auto_vec<path_var> dst_pvs;
 713           dst_state.m_region_model->get_path_vars_for_svalue (dst_sid,
 714                                                               &dst_pvs);
 715
 716           unsigned j;
 717           path_var *dst_pv;
 718           FOR_EACH_VEC_ELT (dst_pvs, j, dst_pv)
 719             {
 720               tree dst_rep = dst_pv->m_tree;
 721               gcc_assert (dst_rep);
 722               if (dst_pv->m_stack_depth
 723                   >= src_state.m_region_model->get_stack_depth ())
 724                 continue;
 725               svalue_id src_sid
 726                 = src_state.m_region_model->get_rvalue (*dst_pv, NULL);
 727               if (src_sid.null_p ())
 728                 continue;
 729               state_machine::state_t src_sm_val = src_smap.get_state (src_sid);
 730               if (dst_sm_val != src_sm_val)
 731                 {
 732                   svalue_id dst_origin_sid = (*iter).second.m_origin;
 733                   if (visitor->on_state_change (sm, src_sm_val, dst_sm_val,
 734                                                 dst_rep, dst_origin_sid))
 735                     return true;
 736                 }
 737             }
 738         }
 739     }
 740   return false;
 741 }
 742
 743 /* Subroutine of diagnostic_manager::build_emission_path.
 744    Add any events for EEDGE to EMISSION_PATH.  */
 745
 746 void
 747 diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge,
 748                                           const extrinsic_state &ext_state,
 749                                           checker_path *emission_path) const
 750 {
 751   const exploded_node *src_node = eedge.m_src;
 752   const program_point &src_point = src_node->get_point ();
 753   const exploded_node *dst_node = eedge.m_dest;
 754   const program_point &dst_point = dst_node->get_point ();
 755   const int dst_stack_depth = dst_point.get_stack_depth ();
 756   if (get_logger ())
 757     {
 758       get_logger ()->start_log_line ();
 759       pretty_printer *pp = get_logger ()->get_printer ();
 760       pp_printf (pp, "EN %i -> EN %i: ",
 761                  eedge.m_src->m_index,
 762                  eedge.m_dest->m_index);
 763       src_point.print (pp, format (false));
 764       pp_string (pp, "-> ");
 765       dst_point.print (pp, format (false));
 766       get_logger ()->end_log_line ();
 767     }
 768   const program_state &src_state = src_node->get_state ();
 769   const program_state &dst_state = dst_node->get_state ();
 770
 771   /* Add state change events for the states that have changed.
 772      We add these before events for superedges, so that if we have a
 773      state_change_event due to following an edge, we'll get this sequence
 774      of events:
 775
 776       | if (!ptr)
 777       |    ~
 778       |    |
 779       |    (1) assuming 'ptr' is non-NULL  (state_change_event)
 780       |    (2) following 'false' branch... (start_cfg_edge_event)
 781      ...
 782       | do_something (ptr);
 783       | ~~~~~~~~~~~~~^~~~~
 784       |              |
 785       |              (3) ...to here        (end_cfg_edge_event).  */
 786   state_change_event_creator visitor (eedge, emission_path);
 787   for_each_state_change (src_state, dst_state, ext_state,
 788                          &visitor);
 789
 790   /* Allow non-standard edges to add events, e.g. when rewinding from
 791      longjmp to a setjmp.  */
 792   if (eedge.m_custom_info)
 793     eedge.m_custom_info->add_events_to_path (emission_path, eedge);
 794
 795   /* Add events for superedges, function entries, and for statements.  */
 796   switch (dst_point.get_kind ())
 797     {
 798     default:
 799       break;
 800     case PK_BEFORE_SUPERNODE:
 801       if (src_point.get_kind () == PK_AFTER_SUPERNODE)
 802         {
 803           if (eedge.m_sedge)
 804             add_events_for_superedge (eedge, emission_path);
 805         }
 806       /* Add function entry events.  */
 807       if (dst_point.get_supernode ()->entry_p ())
 808         {
 809           emission_path->add_event
 810             (new function_entry_event
 811              (dst_point.get_supernode ()->get_start_location (),
 812               dst_point.get_fndecl (),
 813               dst_stack_depth));
 814         }
 815       break;
 816     case PK_BEFORE_STMT:
 817       {
 818         const gimple *stmt = dst_point.get_stmt ();
 819         if (is_setjmp_call_p (stmt))
 820           emission_path->add_event
 821             (new setjmp_event (stmt->location,
 822                                dst_node,
 823                                dst_point.get_fndecl (),
 824                                dst_stack_depth));
 825         else
 826           emission_path->add_event
 827             (new statement_event (stmt,
 828                                   dst_point.get_fndecl (),
 829                                   dst_stack_depth, dst_state));
 830       }
 831       break;
 832     }
 833 }
 834
 835 /* Subroutine of diagnostic_manager::add_events_for_eedge
 836    where EEDGE has an underlying superedge i.e. a CFG edge,
 837    or an interprocedural call/return.
 838    Add any events for the superedge to EMISSION_PATH.  */
 839
 840 void
 841 diagnostic_manager::add_events_for_superedge (const exploded_edge &eedge,
 842                                               checker_path *emission_path)
 843   const
 844 {
 845   gcc_assert (eedge.m_sedge);
 846
 847   const exploded_node *src_node = eedge.m_src;
 848   const program_point &src_point = src_node->get_point ();
 849   const exploded_node *dst_node = eedge.m_dest;
 850   const program_point &dst_point = dst_node->get_point ();
 851   const int src_stack_depth = src_point.get_stack_depth ();
 852   const int dst_stack_depth = dst_point.get_stack_depth ();
 853   const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt ();
 854
 855   switch (eedge.m_sedge->m_kind)
 856     {
 857     case SUPEREDGE_CFG_EDGE:
 858       {
 859         emission_path->add_event
 860           (new start_cfg_edge_event (eedge,
 861                                (last_stmt
 862                                 ? last_stmt->location
 863                                 : UNKNOWN_LOCATION),
 864                                src_point.get_fndecl (),
 865                                src_stack_depth));
 866         emission_path->add_event
 867           (new end_cfg_edge_event (eedge,
 868                                    dst_point.get_supernode ()->get_start_location (),
 869                                    dst_point.get_fndecl (),
 870                                    dst_stack_depth));
 871       }
 872       break;
 873
 874     case SUPEREDGE_CALL:
 875       {
 876         emission_path->add_event
 877           (new call_event (eedge,
 878                            (last_stmt
 879                             ? last_stmt->location
 880                             : UNKNOWN_LOCATION),
 881                            src_point.get_fndecl (),
 882                            src_stack_depth));
 883       }
 884       break;
 885
 886     case SUPEREDGE_INTRAPROCEDURAL_CALL:
 887       {
 888         /* TODO: add a subclass for this, or generate events for the
 889            summary.  */
 890         emission_path->add_event
 891           (new debug_event ((last_stmt
 892                              ? last_stmt->location
 893                              : UNKNOWN_LOCATION),
 894                             src_point.get_fndecl (),
 895                             src_stack_depth,
 896                             "call summary"));
 897       }
 898       break;
 899
 900     case SUPEREDGE_RETURN:
 901       {
 902         const return_superedge *return_edge
 903           = as_a <const return_superedge *> (eedge.m_sedge);
 904
 905         const gcall *call_stmt = return_edge->get_call_stmt ();
 906         emission_path->add_event
 907           (new return_event (eedge,
 908                              (call_stmt
 909                               ? call_stmt->location
 910                               : UNKNOWN_LOCATION),
 911                              dst_point.get_fndecl (),
 912                              dst_stack_depth));
 913       }
 914       break;
 915     }
 916 }
 917
 918 /* Prune PATH, based on the verbosity level, to the most pertinent
 919    events for a diagnostic that involves VAR ending in state STATE
 920    (for state machine SM).
 921
 922    PATH is updated in place, and the redundant checker_events are deleted.
 923
 924    As well as deleting events, call record_critical_state on events in
 925    which state critical to the pending_diagnostic is being handled; see
 926    the comment for diagnostic_manager::prune_for_sm_diagnostic.  */
 927
 928 void
 929 diagnostic_manager::prune_path (checker_path *path,
 930                                 const state_machine *sm,
 931                                 tree var,
 932                                 state_machine::state_t state) const
 933 {
 934   LOG_FUNC (get_logger ());
 935   path->maybe_log (get_logger (), "path");
 936   prune_for_sm_diagnostic (path, sm, var, state);
 937   prune_interproc_events (path);
 938   finish_pruning (path);
 939   path->maybe_log (get_logger (), "pruned");
 940 }
 941
 942 /* First pass of diagnostic_manager::prune_path: apply verbosity level,
 943    pruning unrelated state change events.
 944
 945    Iterate backwards through PATH, skipping state change events that aren't
 946    VAR but update the pertinent VAR when state-copying occurs.
 947
 948    As well as deleting events, call record_critical_state on events in
 949    which state critical to the pending_diagnostic is being handled, so
 950    that the event's get_desc vfunc can potentially supply a more precise
 951    description of the event to the user.
 952    e.g. improving
 953      "calling 'foo' from 'bar'"
 954    to
 955      "passing possibly-NULL pointer 'ptr' to 'foo' from 'bar' as param 1"
 956    when the diagnostic relates to later dereferencing 'ptr'.  */
 957
 958 void
 959 diagnostic_manager::prune_for_sm_diagnostic (checker_path *path,
 960                                              const state_machine *sm,
 961                                              tree var,
 962                                              state_machine::state_t state) const
 963 {
 964   int idx = path->num_events () - 1;
 965   while (idx >= 0 && idx < (signed)path->num_events ())
 966     {
 967       checker_event *base_event = path->get_checker_event (idx);
 968       if (get_logger ())
 969         {
 970           if (sm)
 971             {
 972               if (var)
 973                 log ("considering event %i, with var: %qE, state: %qs",
 974                      idx, var, sm->get_state_name (state));
 975               else
 976                 log ("considering event %i, with global state: %qs",
 977                      idx, sm->get_state_name (state));
 978             }
 979           else
 980             log ("considering event %i", idx);
 981         }
 982       switch (base_event->m_kind)
 983         {
 984         default:
 985           gcc_unreachable ();
 986
 987         case EK_DEBUG:
 988           if (m_verbosity < 3)
 989             {
 990               log ("filtering event %i: debug event", idx);
 991               path->delete_event (idx);
 992             }
 993           break;
 994
 995         case EK_CUSTOM:
 996           /* Don't filter custom events.  */
 997           break;
 998
 999         case EK_STMT:
1000           {
1001             /* If this stmt is the origin of "var", update var.  */
1002             if (var)
1003               {
1004                 statement_event *stmt_event = (statement_event *)base_event;
1005                 tree new_var = get_any_origin (stmt_event->m_stmt, var,
1006                                                stmt_event->m_dst_state);
1007                 if (new_var)
1008                   {
1009                     log ("event %i: switching var of interest from %qE to %qE",
1010                          idx, var, new_var);
1011                     var = new_var;
1012                   }
1013               }
1014             if (m_verbosity < 3)
1015               {
1016                 log ("filtering event %i: statement event", idx);
1017                 path->delete_event (idx);
1018               }
1019           }
1020           break;
1021
1022         case EK_FUNCTION_ENTRY:
1023           if (m_verbosity < 1)
1024             {
1025               log ("filtering event %i: function entry", idx);
1026               path->delete_event (idx);
1027             }
1028           break;
1029
1030         case EK_STATE_CHANGE:
1031           {
1032             state_change_event *state_change = (state_change_event *)base_event;
1033             if (state_change->get_lvalue (state_change->m_var)
1034                 == state_change->get_lvalue (var))
1035               {
1036                 if (state_change->m_origin)
1037                   {
1038                     log ("event %i: switching var of interest from %qE to %qE",
1039                          idx, var, state_change->m_origin);
1040                     var = state_change->m_origin;
1041                   }
1042                 log ("event %i: switching state of interest from %qs to %qs",
1043                      idx, sm->get_state_name (state_change->m_to),
1044                      sm->get_state_name (state_change->m_from));
1045                 state = state_change->m_from;
1046               }
1047             else if (m_verbosity < 3)
1048               {
1049                 if (var)
1050                   log ("filtering event %i:"
1051                        " state change to %qE unrelated to %qE",
1052                        idx, state_change->m_var, var);
1053                 else
1054                   log ("filtering event %i: state change to %qE",
1055                        idx, state_change->m_var);
1056                 path->delete_event (idx);
1057               }
1058           }
1059           break;
1060
1061         case EK_START_CFG_EDGE:
1062           {
1063             cfg_edge_event *event = (cfg_edge_event *)base_event;
1064             const cfg_superedge& cfg_superedge
1065               = event->get_cfg_superedge ();
1066             const supernode *dest = event->m_sedge->m_dest;
1067             /* Do we have an SSA_NAME defined via a phi node in
1068                the dest CFG node?  */
1069             if (var && TREE_CODE (var) == SSA_NAME)
1070               if (SSA_NAME_DEF_STMT (var)->bb == dest->m_bb)
1071                 {
1072                   if (gphi *phi
1073                       = dyn_cast <gphi *> (SSA_NAME_DEF_STMT (var)))
1074                     {
1075                       /* Update var based on its phi node.  */
1076                       tree old_var = var;
1077                       var = cfg_superedge.get_phi_arg (phi);
1078                       log ("updating from %qE to %qE based on phi node",
1079                            old_var, var);
1080                       if (get_logger ())
1081                         {
1082                           pretty_printer pp;
1083                           pp_gimple_stmt_1 (&pp, phi, 0, (dump_flags_t)0);
1084                           log ("  phi: %s", pp_formatted_text (&pp));
1085                         }
1086                     }
1087                 }
1088
1089             /* TODO: is this edge significant to var?
1090                See if var can be in other states in the dest, but not
1091                in other states in the src?
1092                Must have multiple sibling edges.  */
1093
1094             if (event->should_filter_p (m_verbosity))
1095               {
1096                 log ("filtering event %i: CFG edge", idx);
1097                 path->delete_event (idx);
1098                 /* Also delete the corresponding EK_END_CFG_EDGE.  */
1099                 gcc_assert (path->get_checker_event (idx)->m_kind
1100                             == EK_END_CFG_EDGE);
1101                 path->delete_event (idx);
1102               }
1103           }
1104           break;
1105
1106         case EK_END_CFG_EDGE:
1107           /* These come in pairs with EK_START_CFG_EDGE events and are
1108              filtered when their start event is filtered.  */
1109           break;
1110
1111         case EK_CALL_EDGE:
1112           {
1113             call_event *event = (call_event *)base_event;
1114             const callgraph_superedge& cg_superedge
1115               = event->get_callgraph_superedge ();
1116             callsite_expr expr;
1117             tree caller_var
1118               = cg_superedge.map_expr_from_callee_to_caller (var, &expr);
1119             if (caller_var)
1120               {
1121                 log ("event %i:"
1122                      " switching var of interest"
1123                      " from %qE in callee to %qE in caller",
1124                      idx, var, caller_var);
1125                 var = caller_var;
1126                 if (expr.param_p ())
1127                   event->record_critical_state (var, state);
1128               }
1129           }
1130           break;
1131
1132         case EK_RETURN_EDGE:
1133           // TODO: potentially update var/state based on return value,
1134           // args etc
1135           {
1136             if (var)
1137               {
1138                 return_event *event = (return_event *)base_event;
1139                 const callgraph_superedge& cg_superedge
1140                   = event->get_callgraph_superedge ();
1141                 callsite_expr expr;
1142                 tree callee_var
1143                   = cg_superedge.map_expr_from_caller_to_callee (var, &expr);
1144                 if (callee_var)
1145                   {
1146                     log ("event %i:"
1147                          " switching var of interest"
1148                          " from %qE in caller to %qE in callee",
1149                          idx, var, callee_var);
1150                     var = callee_var;
1151                     if (expr.return_value_p ())
1152                       event->record_critical_state (var, state);
1153                   }
1154               }
1155           }
1156           break;
1157
1158         case EK_SETJMP:
1159           /* TODO: only show setjmp_events that matter i.e. those for which
1160              there is a later rewind event using them.  */
1161         case EK_REWIND_FROM_LONGJMP:
1162         case EK_REWIND_TO_SETJMP:
1163           break;
1164
1165         case EK_WARNING:
1166           /* Always show the final "warning" event in the path.  */
1167           break;
1168         }
1169       idx--;
1170     }
1171 }
1172
1173 /* Second pass of diagnostic_manager::prune_path: remove redundant
1174    interprocedural information.
1175
1176    For example, given:
1177      (1)- calling "f2" from "f1"
1178      (2)--- entry to "f2"
1179      (3)--- calling "f3" from "f2"
1180      (4)----- entry to "f3"
1181      (5)--- returning to "f2" to "f3"
1182      (6)- returning to "f1" to "f2"
1183    with no other intervening events, then none of these events are
1184    likely to be interesting to the user.
1185
1186    Prune [..., call, function-entry, return, ...] triples repeatedly
1187    until nothing has changed.  For the example above, this would
1188    remove events (3, 4, 5), and then remove events (1, 2, 6).  */
1189
1190 void
1191 diagnostic_manager::prune_interproc_events (checker_path *path) const
1192 {
1193   bool changed = false;
1194   do
1195     {
1196       changed = false;
1197       int idx = path->num_events () - 1;
1198       while (idx >= 0)
1199         {
1200           /* Prune [..., call, function-entry, return, ...] triples.  */
1201           if (idx + 2 < (signed)path->num_events ()
1202               && path->get_checker_event (idx)->is_call_p ()
1203               && path->get_checker_event (idx + 1)->is_function_entry_p ()
1204               && path->get_checker_event (idx + 2)->is_return_p ())
1205             {
1206               if (get_logger ())
1207                 {
1208                   label_text desc
1209                     (path->get_checker_event (idx)->get_desc (false));
1210                   log ("filtering events %i-%i:"
1211                        " irrelevant call/entry/return: %s",
1212                        idx, idx + 2, desc.m_buffer);
1213                   desc.maybe_free ();
1214                 }
1215               path->delete_event (idx + 2);
1216               path->delete_event (idx + 1);
1217               path->delete_event (idx);
1218               changed = true;
1219               idx--;
1220               continue;
1221             }
1222
1223           /* Prune [..., call, return, ...] pairs
1224              (for -fanalyzer-verbosity=0).  */
1225           if (idx + 1 < (signed)path->num_events ()
1226               && path->get_checker_event (idx)->is_call_p ()
1227               && path->get_checker_event (idx + 1)->is_return_p ())
1228             {
1229               if (get_logger ())
1230                 {
1231                   label_text desc
1232                     (path->get_checker_event (idx)->get_desc (false));
1233                   log ("filtering events %i-%i:"
1234                        " irrelevant call/return: %s",
1235                        idx, idx + 1, desc.m_buffer);
1236                   desc.maybe_free ();
1237                 }
1238               path->delete_event (idx + 1);
1239               path->delete_event (idx);
1240               changed = true;
1241               idx--;
1242               continue;
1243             }
1244
1245           idx--;
1246         }
1247
1248     }
1249   while (changed);
1250 }
1251
1252 /* Final pass of diagnostic_manager::prune_path.
1253
1254    If all we're left with is in one function, then filter function entry
1255    events.  */
1256
1257 void
1258 diagnostic_manager::finish_pruning (checker_path *path) const
1259 {
1260   if (!path->interprocedural_p ())
1261     {
1262       int idx = path->num_events () - 1;
1263       while (idx >= 0 && idx < (signed)path->num_events ())
1264         {
1265           checker_event *base_event = path->get_checker_event (idx);
1266           if (base_event->m_kind == EK_FUNCTION_ENTRY)
1267             {
1268               log ("filtering event %i:"
1269                    " function entry for purely intraprocedural path", idx);
1270               path->delete_event (idx);
1271             }
1272           idx--;
1273         }
1274     }
1275 }
1276
1277 #endif /* #if ENABLE_ANALYZER */