From patchwork Fri Dec 13 18:11:32 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1209367 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=209.132.180.131; helo=sourceware.org; envelope-from=gcc-patches-return-515953-incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dmarc=fail (p=none dis=none) header.from=redhat.com Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="d+1jnOxm"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.b="cBX6F5Pk"; dkim-atps=neutral Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 47ZJs803pSz9sPJ for ; Sat, 14 Dec 2019 05:21:31 +1100 (AEDT) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; q=dns; s= default; b=gvNDf+AShsBnTZuTTPPHWxnU0y0GChmjE9Let8ihoNO3qvnyLvVkR f0mYICpMn39yyIZRyqeF+MSqJA2sS2pI2VQVPYxrDrpWcpoaYl3J/TZNz+YkZksR 8hqYDDOh+ryEXRj9s1HjMI0X3NmSG55GMsej6QLzH6u8SNg1+Wr2sw= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references :mime-version:content-type:content-transfer-encoding; s=default; bh=mTh7uGoWN+6ruWqyJrsIrcU/1do=; b=d+1jnOxmAbsJGlJEgI+0CdIRglBQ odQAoBXDVnEczFMOey9Nhhm+GcyLtdWkhdwYHF7IbfUwW0/dFpu4/HWf31XJ01q9 6bLbgLgm70PstWM7hwMgsrIQ5b/7k3L/XT5xiHcp7Pj08PaCOfWqswBrTrocnXDc jlxfokv4XLui0ww= Received: (qmail 118771 invoked by alias); 13 Dec 2019 18:14:40 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 104232 invoked by uid 89); 13 Dec 2019 18:12:30 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-23.0 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT autolearn=ham version=3.3.1 spammy=winner, amongst X-HELO: us-smtp-1.mimecast.com Received: from us-smtp-delivery-1.mimecast.com (HELO us-smtp-1.mimecast.com) (207.211.31.120) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Fri, 13 Dec 2019 18:12:11 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1576260730; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=FD4+bxNK8/sDOGpl4OM/q5Ev4MKl1rPXSz6Y1oR9rjU=; b=cBX6F5Pk4avgKHuzOgrtkzdy9Jy78PA5yuDkQ8qv0YdG1Q6USK2I1vQ8/3DaOQJFWO5b7F 5ovgRWXGcUMDgQueH54kuJ5FZZsPH+XbQPUfFsaFQLS1jLp4siQrfkzqMcV1qaEqtcYUSu r4FA6Yv3Zcoy58aynfyG5xI1R941zoE= Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-381-58oTF8pvMTCDCKAxDQ9Jww-1; Fri, 13 Dec 2019 13:12:08 -0500 Received: from smtp.corp.redhat.com (int-mx06.intmail.prod.int.phx2.redhat.com [10.5.11.16]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 5F194801E70 for ; Fri, 13 Dec 2019 18:12:07 +0000 (UTC) Received: from t470.redhat.com (ovpn-117-164.phx2.redhat.com [10.3.117.164]) by smtp.corp.redhat.com (Postfix) with ESMTP id D63E95C241; Fri, 13 Dec 2019 18:12:06 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [PATCH 43/45] analyzer: new files: diagnostic-manager.{cc|h} Date: Fri, 13 Dec 2019 13:11:32 -0500 Message-Id: <20191213181134.1830-44-dmalcolm@redhat.com> In-Reply-To: <20191213181134.1830-1-dmalcolm@redhat.com> References: <20191213181134.1830-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-IsSubscribed: yes Changed in v4: - Remove include of gcc-plugin.h, reworking includes accordingly. - Wrap everything in #if ENABLE_ANALYZER - Remove /// comment lines - Add custom events: https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00213.html - Generalize rewind_info_t to exploded_edge::custom_info_t https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00219.html - Add support for global state: https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00217.html - Show rewind destination for leaks due to longjmp https://gcc.gnu.org/ml/gcc-patches/2019-11/msg02029.html - Split diagnostic_manager::prune_path into subroutines - Add DISABLE_COPY_AND_ASSIGN (saved_diagnostic); This patch adds diagnostic_manager and related support classes for saving, deduplicating, and emitting analyzer diagnostics. gcc/ChangeLog: * analyzer/diagnostic-manager.cc: New file. * analyzer/diagnostic-manager.h: New file. --- gcc/analyzer/diagnostic-manager.cc | 1217 ++++++++++++++++++++++++++++ gcc/analyzer/diagnostic-manager.h | 137 ++++ 2 files changed, 1354 insertions(+) create mode 100644 gcc/analyzer/diagnostic-manager.cc create mode 100644 gcc/analyzer/diagnostic-manager.h diff --git a/gcc/analyzer/diagnostic-manager.cc b/gcc/analyzer/diagnostic-manager.cc new file mode 100644 index 000000000000..b8aae115ae67 --- /dev/null +++ b/gcc/analyzer/diagnostic-manager.cc @@ -0,0 +1,1217 @@ +/* Classes for saving, deduplicating, and emitting analyzer diagnostics. + Copyright (C) 2019 Free Software Foundation, Inc. + Contributed by David Malcolm . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "pretty-print.h" +#include "gcc-rich-location.h" +#include "gimple-pretty-print.h" +#include "analyzer/analyzer.h" +#include "analyzer/diagnostic-manager.h" +#include "analyzer/exploded-graph.h" +#include "analyzer/checker-path.h" + +#if ENABLE_ANALYZER + +/* class saved_diagnostic. */ + +/* saved_diagnostic's ctor. + Take ownership of D and STMT_FINDER. */ + +saved_diagnostic::saved_diagnostic (const state_machine *sm, + const exploded_node *enode, + const supernode *snode, const gimple *stmt, + stmt_finder *stmt_finder, + tree var, state_machine::state_t state, + pending_diagnostic *d) +: m_sm (sm), m_enode (enode), m_snode (snode), m_stmt (stmt), + /* stmt_finder could be on-stack; we want our own copy that can + outlive that. */ + m_stmt_finder (stmt_finder ? stmt_finder->clone () : NULL), + m_var (var), m_state (state), + m_d (d), m_trailing_eedge (NULL) +{ + gcc_assert (m_stmt || m_stmt_finder); + + /* We must have an enode in order to be able to look for paths + through the exploded_graph to this diagnostic. */ + gcc_assert (m_enode); +} + +/* saved_diagnostic's dtor. */ + +saved_diagnostic::~saved_diagnostic () +{ + delete m_stmt_finder; + delete m_d; +} + +/* class diagnostic_manager. */ + +/* diagnostic_manager's ctor. */ + +diagnostic_manager::diagnostic_manager (logger *logger, int verbosity) +: log_user (logger), m_verbosity (verbosity) +{ +} + +/* Queue pending_diagnostic D at ENODE for later emission. */ + +void +diagnostic_manager::add_diagnostic (const state_machine *sm, + const exploded_node *enode, + const supernode *snode, const gimple *stmt, + stmt_finder *finder, + tree var, state_machine::state_t state, + pending_diagnostic *d) +{ + LOG_FUNC (get_logger ()); + + /* We must have an enode in order to be able to look for paths + through the exploded_graph to the diagnostic. */ + gcc_assert (enode); + + saved_diagnostic *sd + = new saved_diagnostic (sm, enode, snode, stmt, finder, var, state, d); + m_saved_diagnostics.safe_push (sd); + if (get_logger ()) + log ("adding saved diagnostic %i at SN %i: %qs", + m_saved_diagnostics.length () - 1, + snode->m_index, d->get_kind ()); +} + +/* Queue pending_diagnostic D at ENODE for later emission. */ + +void +diagnostic_manager::add_diagnostic (const exploded_node *enode, + const supernode *snode, const gimple *stmt, + stmt_finder *finder, + pending_diagnostic *d) +{ + gcc_assert (enode); + add_diagnostic (NULL, enode, snode, stmt, finder, NULL_TREE, 0, d); +} + +/* A class for identifying sets of duplicated pending_diagnostic. + + We want to find the simplest dedupe_candidate amongst those that share a + dedupe_key. */ + +class dedupe_key +{ +public: + dedupe_key (const saved_diagnostic &sd, + const exploded_path &epath) + : m_sd (sd), m_stmt (sd.m_stmt) + { + /* Support deferring the choice of stmt until after an emission path has + been built, using an optional stmt_finder. */ + if (m_stmt == NULL) + { + gcc_assert (sd.m_stmt_finder); + m_stmt = sd.m_stmt_finder->find_stmt (epath); + } + gcc_assert (m_stmt); + } + + hashval_t hash () const + { + inchash::hash hstate; + hstate.add_ptr (m_stmt); + // TODO: m_sd + return hstate.end (); + } + bool operator== (const dedupe_key &other) const + { + return (m_sd == other.m_sd + && m_stmt == other.m_stmt); + } + + location_t get_location () const + { + return m_stmt->location; + } + + /* A qsort comparator for use by dedupe_winners::emit_best + to sort them into location_t order. */ + + static int + comparator (const void *p1, const void *p2) + { + const dedupe_key *pk1 = *(const dedupe_key * const *)p1; + const dedupe_key *pk2 = *(const dedupe_key * const *)p2; + + location_t loc1 = pk1->get_location (); + location_t loc2 = pk2->get_location (); + + return linemap_compare_locations (line_table, loc2, loc1); + } + + const saved_diagnostic &m_sd; + const gimple *m_stmt; +}; + +/* The value of a slot for a dedupe_key within dedupe_winners: + the exploded_path for the best candidate for that key, and the + number of duplicates seen so far. */ + +class dedupe_candidate +{ +public: + // has the exploded_path + dedupe_candidate (const shortest_exploded_paths &sp, + const saved_diagnostic &sd) + : m_epath (sp.get_shortest_path (sd.m_enode)), + m_num_dupes (0) + { + } + + unsigned length () const { return m_epath.length (); } + const exploded_path &get_path () const { return m_epath; } + + void add_duplicate () { m_num_dupes++; } + int get_num_dupes () const { return m_num_dupes; } + +private: + exploded_path m_epath; +public: + int m_num_dupes; +}; + +/* Traits for use by dedupe_winners. */ + +class dedupe_hash_map_traits +{ +public: + typedef const dedupe_key *key_type; + typedef dedupe_candidate *value_type; + typedef dedupe_candidate *compare_type; + + static inline hashval_t hash (const key_type &v) + { + return v->hash (); + } + static inline bool equal_keys (const key_type &k1, const key_type &k2) + { + return *k1 == *k2; + } + template + static inline void remove (T &) + { + // TODO + } + template + static inline void mark_deleted (T &entry) + { + entry.m_key = reinterpret_cast (1); + } + template + static inline void mark_empty (T &entry) + { + entry.m_key = NULL; + } + template + static inline bool is_deleted (const T &entry) + { + return entry.m_key == reinterpret_cast (1); + } + template + static inline bool is_empty (const T &entry) + { + return entry.m_key == NULL; + } + +}; + +/* A class for deduplicating diagnostics and finding (and emitting) the + best diagnostic within each partition. */ + +class dedupe_winners +{ +public: + ~dedupe_winners () + { + /* Delete all keys and candidates. */ + for (map_t::iterator iter = m_map.begin (); + iter != m_map.end (); + ++iter) + { + delete (*iter).first; + delete (*iter).second; + } + } + + /* Determine an exploded_path for SD using SP and, if it's feasible, + determine if it's the best seen so far for its dedupe_key. + Retain the winner for each dedupe_key, and discard the rest. */ + + void add (logger *logger, + const shortest_exploded_paths &sp, + const saved_diagnostic &sd) + { + /* Build a dedupe_candidate for SD. + This uses SP to build an exploded_path. */ + dedupe_candidate *dc = new dedupe_candidate (sp, sd); + + /* Verify that the epath is feasible. + State-merging means that not every path in the epath corresponds + to a feasible one w.r.t. states. + Here we simply check each duplicate saved_diagnostic's + shortest_path, and reject any that aren't feasible. + This could introduce false negatives, as there could be longer + feasible paths within the egraph. */ + if (logger) + logger->log ("considering %qs at SN: %i", + sd.m_d->get_kind (), sd.m_snode->m_index); + if (!dc->get_path ().feasible_p (logger)) + { + if (logger) + logger->log ("rejecting %qs at SN: %i" + " due to infeasible path", + sd.m_d->get_kind (), sd.m_snode->m_index); + delete dc; + return; + } + else + if (logger) + logger->log ("accepting %qs at SN: %i with feasible path", + sd.m_d->get_kind (), sd.m_snode->m_index); + + dedupe_key *key = new dedupe_key (sd, dc->get_path ()); + if (dedupe_candidate **slot = m_map.get (key)) + { + (*slot)->add_duplicate (); + + if (dc->length () < (*slot)->length ()) + { + /* We've got a shorter path for the key; replace + the current candidate. */ + dc->m_num_dupes = (*slot)->get_num_dupes (); + delete *slot; + *slot = dc; + } + else + /* We haven't beaten the current best candidate; + drop the new candidate. */ + delete dc; + delete key; + } + else + /* This is the first candidate for this key. */ + m_map.put (key, dc); + } + + /* Emit the simplest diagnostic within each set. */ + + void emit_best (diagnostic_manager *dm, + const exploded_graph &eg) + { + LOG_SCOPE (dm->get_logger ()); + + /* Get keys into a vec for sorting. */ + auto_vec keys (m_map.elements ()); + for (map_t::iterator iter = m_map.begin (); + iter != m_map.end (); + ++iter) + keys.quick_push ((*iter).first); + + dm->log ("# keys after de-duplication: %i", keys.length ()); + + /* Sort into a good emission order. */ + keys.qsort (dedupe_key::comparator); + + /* Emit the best candidate for each key. */ + int i; + const dedupe_key *key; + FOR_EACH_VEC_ELT (keys, i, key) + { + dedupe_candidate **slot = m_map.get (key); + gcc_assert (*slot); + const dedupe_candidate &dc = **slot; + + dm->emit_saved_diagnostic (eg, key->m_sd, + dc.get_path (), key->m_stmt, + dc.get_num_dupes ()); + } + } + +private: + + /* This maps from each dedupe_key to a current best dedupe_candidate. */ + + typedef hash_map map_t; + map_t m_map; +}; + +/* Emit all saved diagnostics. */ + +void +diagnostic_manager::emit_saved_diagnostics (const exploded_graph &eg) +{ + LOG_SCOPE (get_logger ()); + auto_timevar tv (TV_ANALYZER_DIAGNOSTICS); + log ("# saved diagnostics: %i", m_saved_diagnostics.length ()); + + if (m_saved_diagnostics.length () == 0) + return; + + /* Compute the shortest_paths once, sharing it between all diagnostics. */ + shortest_exploded_paths sp (eg, eg.get_origin ()); + + /* Iterate through all saved diagnostics, adding them to a dedupe_winners + instance. This partitions the saved diagnostics by dedupe_key, + generating exploded_paths for them, and retaining the best one in each + partition. */ + dedupe_winners best_candidates; + + int i; + saved_diagnostic *sd; + FOR_EACH_VEC_ELT (m_saved_diagnostics, i, sd) + best_candidates.add (get_logger (), sp, *sd); + + /* For each dedupe-key, call emit_saved_diagnostic on the "best" + saved_diagnostic. */ + best_candidates.emit_best (this, eg); +} + +/* Given a saved_diagnostic SD at STMT with feasible path EPATH through EG, + create an checker_path of suitable events and use it to call + SD's underlying pending_diagnostic "emit" vfunc to emit a diagnostic. */ + +void +diagnostic_manager::emit_saved_diagnostic (const exploded_graph &eg, + const saved_diagnostic &sd, + const exploded_path &epath, + const gimple *stmt, + int num_dupes) +{ + LOG_SCOPE (get_logger ()); + log ("sd: %qs at SN: %i", sd.m_d->get_kind (), sd.m_snode->m_index); + log ("num dupes: %i", num_dupes); + + pretty_printer *pp = global_dc->printer->clone (); + + checker_path emission_path; + + /* Populate emission_path with a full description of EPATH. */ + build_emission_path (eg, epath, &emission_path); + + /* Now prune it to just cover the most pertinent events. */ + prune_path (&emission_path, sd.m_sm, sd.m_var, sd.m_state); + + /* Add a final event to the path, covering the diagnostic itself. + We use the final enode from the epath, which might be different from + the sd.m_enode, as the dedupe code doesn't care about enodes, just + snodes. */ + emission_path.add_final_event (sd.m_sm, epath.get_final_enode (), stmt, + sd.m_var, sd.m_state); + + /* The "final" event might not be final; if the saved_diagnostic has a + trailing eedge stashed, add any events for it. This is for use + in handling longjmp, to show where a longjmp is rewinding to. */ + if (sd.m_trailing_eedge) + add_events_for_eedge (*sd.m_trailing_eedge, eg.get_ext_state (), + &emission_path); + + emission_path.prepare_for_emission (sd.m_d); + + gcc_rich_location rich_loc (stmt->location); + rich_loc.set_path (&emission_path); + + auto_diagnostic_group d; + auto_cfun sentinel (sd.m_snode->m_fun); + if (sd.m_d->emit (&rich_loc)) + { + if (num_dupes > 0) + inform_n (stmt->location, num_dupes, + "%i duplicate", "%i duplicates", + num_dupes); + } + delete pp; +} + +/* Given a state change to DST_REP, determine a tree that gives the origin + of that state at STMT, using DST_STATE's region model, so that state + changes based on assignments can be tracked back to their origins. + + For example, if we have + + (S1) _1 = malloc (64); + (S2) EXPR = _1; + + then at stmt S2 we can get the origin of EXPR's state as being _1, + and thus track the allocation back to S1. */ + +static tree +get_any_origin (const gimple *stmt, + tree dst_rep, + const program_state &dst_state) +{ + if (!stmt) + return NULL_TREE; + + gcc_assert (dst_rep); + + if (const gassign *assign = dyn_cast (stmt)) + { + tree lhs = gimple_assign_lhs (assign); + /* Use region IDs to compare lhs with DST_REP. */ + if (dst_state.m_region_model->get_lvalue (lhs, NULL) + == dst_state.m_region_model->get_lvalue (dst_rep, NULL)) + { + tree rhs1 = gimple_assign_rhs1 (assign); + enum tree_code op = gimple_assign_rhs_code (assign); + switch (op) + { + default: + //gcc_unreachable (); // TODO + break; + case COMPONENT_REF: + case SSA_NAME: + return rhs1; + } + } + } + return NULL_TREE; +} + +/* Emit a "path" of events to EMISSION_PATH describing the exploded path + EPATH within EG. */ + +void +diagnostic_manager::build_emission_path (const exploded_graph &eg, + const exploded_path &epath, + checker_path *emission_path) const +{ + LOG_SCOPE (get_logger ()); + const extrinsic_state &ext_state = eg.get_ext_state (); + for (unsigned i = 0; i < epath.m_edges.length (); i++) + { + const exploded_edge *eedge = epath.m_edges[i]; + add_events_for_eedge (*eedge, ext_state, emission_path); + } +} + +/* Subclass of state_change_visitor that creates state_change_event + instances. */ + +class state_change_event_creator : public state_change_visitor +{ +public: + state_change_event_creator (const exploded_edge &eedge, + checker_path *emission_path) + : m_eedge (eedge), + m_emission_path (emission_path) + {} + + bool on_global_state_change (const state_machine &sm, + state_machine::state_t src_sm_val, + state_machine::state_t dst_sm_val) + FINAL OVERRIDE + { + const exploded_node *src_node = m_eedge.m_src; + const program_point &src_point = src_node->get_point (); + const int src_stack_depth = src_point.get_stack_depth (); + const exploded_node *dst_node = m_eedge.m_dest; + const gimple *stmt = src_point.get_stmt (); + const supernode *supernode = src_point.get_supernode (); + const program_state &dst_state = dst_node->get_state (); + + int stack_depth = src_stack_depth; + + m_emission_path->add_event (new state_change_event (supernode, + stmt, + stack_depth, + sm, + NULL_TREE, + src_sm_val, + dst_sm_val, + NULL_TREE, + dst_state)); + return false; + } + + bool on_state_change (const state_machine &sm, + state_machine::state_t src_sm_val, + state_machine::state_t dst_sm_val, + tree dst_rep, + svalue_id dst_origin_sid) FINAL OVERRIDE + { + const exploded_node *src_node = m_eedge.m_src; + const program_point &src_point = src_node->get_point (); + const int src_stack_depth = src_point.get_stack_depth (); + const exploded_node *dst_node = m_eedge.m_dest; + const gimple *stmt = src_point.get_stmt (); + const supernode *supernode = src_point.get_supernode (); + const program_state &dst_state = dst_node->get_state (); + + int stack_depth = src_stack_depth; + + if (m_eedge.m_sedge + && m_eedge.m_sedge->m_kind == SUPEREDGE_CFG_EDGE) + { + supernode = src_point.get_supernode (); + stmt = supernode->get_last_stmt (); + stack_depth = src_stack_depth; + } + + /* Bulletproofing for state changes at calls/returns; + TODO: is there a better way? */ + if (!stmt) + return false; + + tree origin_rep + = dst_state.get_representative_tree (dst_origin_sid); + + if (origin_rep == NULL_TREE) + origin_rep = get_any_origin (stmt, dst_rep, dst_state); + m_emission_path->add_event (new state_change_event (supernode, + stmt, + stack_depth, + sm, + dst_rep, + src_sm_val, + dst_sm_val, + origin_rep, + dst_state)); + return false; + } + + const exploded_edge &m_eedge; + checker_path *m_emission_path; +}; + +/* Compare SRC_STATE and DST_STATE (which use EXT_STATE), and call + VISITOR's on_state_change for every sm-state change that occurs + to a tree, and on_global_state_change for every global state change + that occurs. + + This determines the state changes that ought to be reported to + the user: a combination of the effects of changes to sm_state_map + (which maps svalues to sm-states), and of region_model changes + (which map trees to svalues). + + Bail out early and return true if any call to on_global_state_change + or on_state_change returns true, otherwise return false. + + This is split out to make it easier to experiment with changes to + exploded_node granularity (so that we can observe what state changes + lead to state_change_events being emitted). */ + +bool +for_each_state_change (const program_state &src_state, + const program_state &dst_state, + const extrinsic_state &ext_state, + state_change_visitor *visitor) +{ + gcc_assert (src_state.m_checker_states.length () + == ext_state.m_checkers.length ()); + gcc_assert (dst_state.m_checker_states.length () + == ext_state.m_checkers.length ()); + for (unsigned i = 0; i < ext_state.m_checkers.length (); i++) + { + const state_machine &sm = ext_state.get_sm (i); + const sm_state_map &src_smap = *src_state.m_checker_states[i]; + const sm_state_map &dst_smap = *dst_state.m_checker_states[i]; + + /* Add events for any global state changes. */ + if (src_smap.get_global_state () != dst_smap.get_global_state ()) + if (visitor->on_global_state_change (sm, + src_smap.get_global_state (), + dst_smap.get_global_state ())) + return true; + + /* Add events for per-svalue state changes. */ + for (sm_state_map::iterator_t iter = dst_smap.begin (); + iter != dst_smap.end (); + ++iter) + { + /* Ideally we'd directly compare the SM state between src state + and dst state, but there's no guarantee that the IDs can + be meaningfully compared. */ + svalue_id dst_sid = (*iter).first; + state_machine::state_t dst_sm_val = (*iter).second.m_state; + + auto_vec dst_pvs; + dst_state.m_region_model->get_path_vars_for_svalue (dst_sid, + &dst_pvs); + + unsigned j; + path_var *dst_pv; + FOR_EACH_VEC_ELT (dst_pvs, j, dst_pv) + { + tree dst_rep = dst_pv->m_tree; + gcc_assert (dst_rep); + if (dst_pv->m_stack_depth + >= src_state.m_region_model->get_stack_depth ()) + continue; + svalue_id src_sid + = src_state.m_region_model->get_rvalue (*dst_pv, NULL); + if (src_sid.null_p ()) + continue; + state_machine::state_t src_sm_val = src_smap.get_state (src_sid); + if (dst_sm_val != src_sm_val) + { + svalue_id dst_origin_sid = (*iter).second.m_origin; + if (visitor->on_state_change (sm, src_sm_val, dst_sm_val, + dst_rep, dst_origin_sid)) + return true; + } + } + } + } + return false; +} + +/* Subroutine of diagnostic_manager::build_emission_path. + Add any events for EEDGE to EMISSION_PATH. */ + +void +diagnostic_manager::add_events_for_eedge (const exploded_edge &eedge, + const extrinsic_state &ext_state, + checker_path *emission_path) const +{ + const exploded_node *src_node = eedge.m_src; + const program_point &src_point = src_node->get_point (); + const exploded_node *dst_node = eedge.m_dest; + const program_point &dst_point = dst_node->get_point (); + const int dst_stack_depth = dst_point.get_stack_depth (); + if (get_logger ()) + { + get_logger ()->start_log_line (); + pretty_printer *pp = get_logger ()->get_printer (); + pp_printf (pp, "EN %i -> EN %i: ", + eedge.m_src->m_index, + eedge.m_dest->m_index); + src_point.print (pp, format (false)); + pp_string (pp, "-> "); + dst_point.print (pp, format (false)); + get_logger ()->end_log_line (); + } + const program_state &src_state = src_node->get_state (); + const program_state &dst_state = dst_node->get_state (); + + /* Add state change events for the states that have changed. + We add these before events for superedges, so that if we have a + state_change_event due to following an edge, we'll get this sequence + of events: + + | if (!ptr) + | ~ + | | + | (1) assuming 'ptr' is non-NULL (state_change_event) + | (2) following 'false' branch... (start_cfg_edge_event) + ... + | do_something (ptr); + | ~~~~~~~~~~~~~^~~~~ + | | + | (3) ...to here (end_cfg_edge_event). */ + state_change_event_creator visitor (eedge, emission_path); + for_each_state_change (src_state, dst_state, ext_state, + &visitor); + + /* Allow non-standard edges to add events, e.g. when rewinding from + longjmp to a setjmp. */ + if (eedge.m_custom_info) + eedge.m_custom_info->add_events_to_path (emission_path, eedge); + + /* Add events for superedges, function entries, and for statements. */ + switch (dst_point.get_kind ()) + { + default: + break; + case PK_BEFORE_SUPERNODE: + if (src_point.get_kind () == PK_AFTER_SUPERNODE) + { + if (eedge.m_sedge) + add_events_for_superedge (eedge, emission_path); + } + /* Add function entry events. */ + if (dst_point.get_supernode ()->entry_p ()) + { + emission_path->add_event + (new function_entry_event + (dst_point.get_supernode ()->get_start_location (), + dst_point.get_fndecl (), + dst_stack_depth)); + } + break; + case PK_BEFORE_STMT: + { + const gimple *stmt = dst_point.get_stmt (); + if (is_setjmp_call_p (stmt)) + emission_path->add_event + (new setjmp_event (stmt->location, + dst_node, + dst_point.get_fndecl (), + dst_stack_depth)); + else + emission_path->add_event + (new statement_event (stmt, + dst_point.get_fndecl (), + dst_stack_depth, dst_state)); + } + break; + } +} + +/* Subroutine of diagnostic_manager::add_events_for_eedge + where EEDGE has an underlying superedge i.e. a CFG edge, + or an interprocedural call/return. + Add any events for the superedge to EMISSION_PATH. */ + +void +diagnostic_manager::add_events_for_superedge (const exploded_edge &eedge, + checker_path *emission_path) + const +{ + gcc_assert (eedge.m_sedge); + + const exploded_node *src_node = eedge.m_src; + const program_point &src_point = src_node->get_point (); + const exploded_node *dst_node = eedge.m_dest; + const program_point &dst_point = dst_node->get_point (); + const int src_stack_depth = src_point.get_stack_depth (); + const int dst_stack_depth = dst_point.get_stack_depth (); + const gimple *last_stmt = src_point.get_supernode ()->get_last_stmt (); + + switch (eedge.m_sedge->m_kind) + { + case SUPEREDGE_CFG_EDGE: + { + emission_path->add_event + (new start_cfg_edge_event (eedge, + (last_stmt + ? last_stmt->location + : UNKNOWN_LOCATION), + src_point.get_fndecl (), + src_stack_depth)); + emission_path->add_event + (new end_cfg_edge_event (eedge, + dst_point.get_supernode ()->get_start_location (), + dst_point.get_fndecl (), + dst_stack_depth)); + } + break; + + case SUPEREDGE_CALL: + { + emission_path->add_event + (new call_event (eedge, + (last_stmt + ? last_stmt->location + : UNKNOWN_LOCATION), + src_point.get_fndecl (), + src_stack_depth)); + } + break; + + case SUPEREDGE_INTRAPROCEDURAL_CALL: + { + /* TODO: add a subclass for this, or generate events for the + summary. */ + emission_path->add_event + (new debug_event ((last_stmt + ? last_stmt->location + : UNKNOWN_LOCATION), + src_point.get_fndecl (), + src_stack_depth, + "call summary")); + } + break; + + case SUPEREDGE_RETURN: + { + const return_superedge *return_edge + = as_a (eedge.m_sedge); + + const gcall *call_stmt = return_edge->get_call_stmt (); + emission_path->add_event + (new return_event (eedge, + (call_stmt + ? call_stmt->location + : UNKNOWN_LOCATION), + dst_point.get_fndecl (), + dst_stack_depth)); + } + break; + } +} + +/* Prune PATH, based on the verbosity level, to the most pertinent + events for a diagnostic that involves VAR ending in state STATE + (for state machine SM). + + PATH is updated in place, and the redundant checker_events are deleted. + + As well as deleting events, call record_critical_state on events in + which state critical to the pending_diagnostic is being handled; see + the comment for diagnostic_manager::prune_for_sm_diagnostic. */ + +void +diagnostic_manager::prune_path (checker_path *path, + const state_machine *sm, + tree var, + state_machine::state_t state) const +{ + LOG_FUNC (get_logger ()); + path->maybe_log (get_logger (), "path"); + prune_for_sm_diagnostic (path, sm, var, state); + prune_interproc_events (path); + finish_pruning (path); + path->maybe_log (get_logger (), "pruned"); +} + +/* First pass of diagnostic_manager::prune_path: apply verbosity level, + pruning unrelated state change events. + + Iterate backwards through PATH, skipping state change events that aren't + VAR but update the pertinent VAR when state-copying occurs. + + As well as deleting events, call record_critical_state on events in + which state critical to the pending_diagnostic is being handled, so + that the event's get_desc vfunc can potentially supply a more precise + description of the event to the user. + e.g. improving + "calling 'foo' from 'bar'" + to + "passing possibly-NULL pointer 'ptr' to 'foo' from 'bar' as param 1" + when the diagnostic relates to later dereferencing 'ptr'. */ + +void +diagnostic_manager::prune_for_sm_diagnostic (checker_path *path, + const state_machine *sm, + tree var, + state_machine::state_t state) const +{ + int idx = path->m_events.length () - 1; + while (idx >= 0 && idx < (signed)path->m_events.length ()) + { + checker_event *base_event = path->m_events[idx]; + if (get_logger ()) + { + if (sm) + { + if (var) + log ("considering event %i, with var: %qE, state: %qs", + idx, var, sm->get_state_name (state)); + else + log ("considering event %i, with global state: %qs", + idx, sm->get_state_name (state)); + } + else + log ("considering event %i", idx); + } + switch (base_event->m_kind) + { + default: + gcc_unreachable (); + + case EK_DEBUG: + if (m_verbosity < 3) + { + log ("filtering event %i: debug event", idx); + path->delete_event (idx); + } + break; + + case EK_CUSTOM: + /* Don't filter custom events. */ + break; + + case EK_STMT: + { + /* If this stmt is the origin of "var", update var. */ + if (var) + { + statement_event *stmt_event = (statement_event *)base_event; + tree new_var = get_any_origin (stmt_event->m_stmt, var, + stmt_event->m_dst_state); + if (new_var) + { + log ("event %i: switching var of interest from %qE to %qE", + idx, var, new_var); + var = new_var; + } + } + if (m_verbosity < 3) + { + log ("filtering event %i: statement event", idx); + path->delete_event (idx); + } + } + break; + + case EK_FUNCTION_ENTRY: + if (m_verbosity < 1) + { + log ("filtering event %i: function entry", idx); + path->delete_event (idx); + } + break; + + case EK_STATE_CHANGE: + { + state_change_event *state_change = (state_change_event *)base_event; + if (state_change->get_lvalue (state_change->m_var) + == state_change->get_lvalue (var)) + { + if (state_change->m_origin) + { + log ("event %i: switching var of interest from %qE to %qE", + idx, var, state_change->m_origin); + var = state_change->m_origin; + } + log ("event %i: switching state of interest from %qs to %qs", + idx, sm->get_state_name (state_change->m_to), + sm->get_state_name (state_change->m_from)); + state = state_change->m_from; + } + else if (m_verbosity < 3) + { + if (var) + log ("filtering event %i:" + " state change to %qE unrelated to %qE", + idx, state_change->m_var, var); + else + log ("filtering event %i: state change to %qE", + idx, state_change->m_var); + path->delete_event (idx); + } + } + break; + + case EK_START_CFG_EDGE: + { + cfg_edge_event *event = (cfg_edge_event *)base_event; + const cfg_superedge& cfg_superedge + = event->get_cfg_superedge (); + const supernode *dest = event->m_sedge->m_dest; + /* Do we have an SSA_NAME defined via a phi node in + the dest CFG node? */ + if (var && TREE_CODE (var) == SSA_NAME) + if (SSA_NAME_DEF_STMT (var)->bb == dest->m_bb) + { + if (gphi *phi + = dyn_cast (SSA_NAME_DEF_STMT (var))) + { + /* Update var based on its phi node. */ + tree old_var = var; + var = cfg_superedge.get_phi_arg (phi); + log ("updating from %qE to %qE based on phi node", + old_var, var); + if (get_logger ()) + { + pretty_printer pp; + pp_gimple_stmt_1 (&pp, phi, 0, (dump_flags_t)0); + log (" phi: %s", pp_formatted_text (&pp)); + } + } + } + + /* TODO: is this edge significant to var? + See if var can be in other states in the dest, but not + in other states in the src? + Must have multiple sibling edges. */ + + if (event->should_filter_p (m_verbosity)) + { + log ("filtering event %i: CFG edge", idx); + path->delete_event (idx); + /* Also delete the corresponding EK_END_CFG_EDGE. */ + gcc_assert (path->m_events[idx]->m_kind == EK_END_CFG_EDGE); + path->delete_event (idx); + } + } + break; + + case EK_END_CFG_EDGE: + /* These come in pairs with EK_START_CFG_EDGE events and are + filtered when their start event is filtered. */ + break; + + case EK_CALL_EDGE: + { + call_event *event = (call_event *)base_event; + const callgraph_superedge& cg_superedge + = event->get_callgraph_superedge (); + callsite_expr expr; + tree caller_var + = cg_superedge.map_expr_from_callee_to_caller (var, &expr); + if (caller_var) + { + log ("event %i:" + " switching var of interest" + " from %qE in callee to %qE in caller", + idx, var, caller_var); + var = caller_var; + if (expr.param_p ()) + event->record_critical_state (var, state); + } + } + break; + + case EK_RETURN_EDGE: + // TODO: potentially update var/state based on return value, + // args etc + { + if (var) + { + return_event *event = (return_event *)base_event; + const callgraph_superedge& cg_superedge + = event->get_callgraph_superedge (); + callsite_expr expr; + tree callee_var + = cg_superedge.map_expr_from_caller_to_callee (var, &expr); + if (callee_var) + { + log ("event %i:" + " switching var of interest" + " from %qE in caller to %qE in callee", + idx, var, callee_var); + var = callee_var; + if (expr.return_value_p ()) + event->record_critical_state (var, state); + } + } + } + break; + + case EK_SETJMP: + /* TODO: only show setjmp_events that matter i.e. those for which + there is a later rewind event using them. */ + case EK_REWIND_FROM_LONGJMP: + case EK_REWIND_TO_SETJMP: + break; + + case EK_WARNING: + /* Always show the final "warning" event in the path. */ + break; + } + idx--; + } +} + +/* Second pass of diagnostic_manager::prune_path: remove redundant + interprocedural information. + + For example, given: + (1)- calling "f2" from "f1" + (2)--- entry to "f2" + (3)--- calling "f3" from "f2" + (4)----- entry to "f3" + (5)--- returning to "f2" to "f3" + (6)- returning to "f1" to "f2" + with no other intervening events, then none of these events are + likely to be interesting to the user. + + Prune [..., call, function-entry, return, ...] triples repeatedly + until nothing has changed. For the example above, this would + remove events (3, 4, 5), and then remove events (1, 2, 6). */ + +void +diagnostic_manager::prune_interproc_events (checker_path *path) const +{ + bool changed = false; + do + { + changed = false; + int idx = path->m_events.length () - 1; + while (idx >= 0) + { + /* Prune [..., call, function-entry, return, ...] triples. */ + if (idx + 2 < (signed)path->m_events.length () + && path->m_events[idx]->is_call_p () + && path->m_events[idx + 1]->is_function_entry_p () + && path->m_events[idx + 2]->is_return_p ()) + { + if (get_logger ()) + { + label_text desc (path->m_events[idx]->get_desc (false)); + log ("filtering events %i-%i:" + " irrelevant call/entry/return: %s", + idx, idx + 2, desc.m_buffer); + desc.maybe_free (); + } + path->delete_event (idx + 2); + path->delete_event (idx + 1); + path->delete_event (idx); + changed = true; + idx--; + continue; + } + + /* Prune [..., call, return, ...] pairs + (for -fanalyzer-verbosity=0). */ + if (idx + 1 < (signed)path->m_events.length () + && path->m_events[idx]->is_call_p () + && path->m_events[idx + 1]->is_return_p ()) + { + if (get_logger ()) + { + label_text desc (path->m_events[idx]->get_desc (false)); + log ("filtering events %i-%i:" + " irrelevant call/return: %s", + idx, idx + 1, desc.m_buffer); + desc.maybe_free (); + } + path->delete_event (idx + 1); + path->delete_event (idx); + changed = true; + idx--; + continue; + } + + idx--; + } + + } + while (changed); +} + +/* Final pass of diagnostic_manager::prune_path. + + If all we're left with is in one function, then filter function entry + events. */ + +void +diagnostic_manager::finish_pruning (checker_path *path) const +{ + if (!path->interprocedural_p ()) + { + int idx = path->m_events.length () - 1; + while (idx >= 0 && idx < (signed)path->m_events.length ()) + { + checker_event *base_event = path->m_events[idx]; + if (base_event->m_kind == EK_FUNCTION_ENTRY) + { + log ("filtering event %i:" + " function entry for purely intraprocedural path", idx); + path->delete_event (idx); + } + idx--; + } + } +} + +#endif /* #if ENABLE_ANALYZER */ diff --git a/gcc/analyzer/diagnostic-manager.h b/gcc/analyzer/diagnostic-manager.h new file mode 100644 index 000000000000..5490a2f4e233 --- /dev/null +++ b/gcc/analyzer/diagnostic-manager.h @@ -0,0 +1,137 @@ +/* Classes for saving, deduplicating, and emitting analyzer diagnostics. + Copyright (C) 2019 Free Software Foundation, Inc. + Contributed by David Malcolm . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 3, or (at your option) +any later version. + +GCC is distributed in the hope that it will be useful, but +WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#ifndef GCC_ANALYZER_DIAGNOSTIC_MANAGER_H +#define GCC_ANALYZER_DIAGNOSTIC_MANAGER_H + +#include "analyzer/pending-diagnostic.h" + +/* A to-be-emitted diagnostic stored within diagnostic_manager. */ + +class saved_diagnostic +{ +public: + saved_diagnostic (const state_machine *sm, + const exploded_node *enode, + const supernode *snode, const gimple *stmt, + stmt_finder *stmt_finder, + tree var, state_machine::state_t state, + pending_diagnostic *d); + ~saved_diagnostic (); + + bool operator== (const saved_diagnostic &other) const + { + return (m_sm == other.m_sm + /* We don't compare m_enode. */ + && m_snode == other.m_snode + && m_stmt == other.m_stmt + /* We don't compare m_stmt_finder. */ + && m_var == other.m_var + && m_state == other.m_state + && m_d->equal_p (*other.m_d) + && m_trailing_eedge == other.m_trailing_eedge); + } + + //private: + const state_machine *m_sm; + const exploded_node *m_enode; + const supernode *m_snode; + const gimple *m_stmt; + stmt_finder *m_stmt_finder; + tree m_var; + state_machine::state_t m_state; + pending_diagnostic *m_d; + exploded_edge *m_trailing_eedge; + +private: + DISABLE_COPY_AND_ASSIGN (saved_diagnostic); +}; + +/* A class with responsibility for saving pending diagnostics, so that + they can be emitted after the exploded_graph is complete. + This lets us de-duplicate diagnostics, and find the shortest path + for each similar diagnostic, potentially using edges that might + not have been found when each diagnostic was first saved. + + This also lets us compute shortest_paths once, rather than + per-diagnostic. */ + +class diagnostic_manager : public log_user +{ +public: + diagnostic_manager (logger *logger, int verbosity); + + void add_diagnostic (const state_machine *sm, + const exploded_node *enode, + const supernode *snode, const gimple *stmt, + stmt_finder *finder, + tree var, state_machine::state_t state, + pending_diagnostic *d); + + void add_diagnostic (const exploded_node *enode, + const supernode *snode, const gimple *stmt, + stmt_finder *finder, + pending_diagnostic *d); + + void emit_saved_diagnostics (const exploded_graph &eg); + + void emit_saved_diagnostic (const exploded_graph &eg, + const saved_diagnostic &sd, + const exploded_path &epath, + const gimple *stmt, + int num_dupes); + + unsigned get_num_diagnostics () const + { + return m_saved_diagnostics.length (); + } + saved_diagnostic *get_saved_diagnostic (unsigned idx) + { + return m_saved_diagnostics[idx]; + } + +private: + void build_emission_path (const exploded_graph &eg, + const exploded_path &epath, + checker_path *emission_path) const; + + void add_events_for_eedge (const exploded_edge &eedge, + const extrinsic_state &ext_state, + checker_path *emission_path) const; + + void add_events_for_superedge (const exploded_edge &eedge, + checker_path *emission_path) const; + + void prune_path (checker_path *path, + const state_machine *sm, + tree var, state_machine::state_t state) const; + + void prune_for_sm_diagnostic (checker_path *path, + const state_machine *sm, + tree var, + state_machine::state_t state) const; + void prune_interproc_events (checker_path *path) const; + void finish_pruning (checker_path *path) const; + + auto_delete_vec m_saved_diagnostics; + const int m_verbosity; +}; + +#endif /* GCC_ANALYZER_DIAGNOSTIC_MANAGER_H */