From patchwork Fri Dec 13 18:11:27 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1209379 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-515961-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="R2esCmRV"; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=redhat.com header.i=@redhat.com header.b="BZ67XCW/"; 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 47ZJy50hdKz9sR7 for ; Sat, 14 Dec 2019 05:25:48 +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=C9ZeOPNjikCI1fbGsonF4YCDt7qIr8ylmCeH+hQaFwVW0Km98oPZP VE6nM56+E2M/gK50vD2bql4Ut6Tlts4/trWphm1JVgk2EwDxrLMksnVARZ6ZdJiL KssyD72EP8VPLR29lzQhpwbcdjnyp7AhmDrqcIPitaPNM6ixZxb5UQ= 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=HggYSoUcRCi69ZbXc7PqKTrAkg8=; b=R2esCmRVQcthjvKUAeCH5/4NB30v yeESl5KNGpoBdVw54lHmfM83xjPuxENXlbSJNtJ61vfBkOl2ZNR2uvzMH2IrVlzv Xcn6jGM9vNqGFo0EoDpQ9hIZbWqFFa9sjmJ85pTvPQKYZMqeyHWgRhokwyV+evyQ BJk0wZfa2IZ5Zzc= Received: (qmail 1300 invoked by alias); 13 Dec 2019 18:16:14 -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 109974 invoked by uid 89); 13 Dec 2019 18:13:28 -0000 Authentication-Results: sourceware.org; auth=none X-Spam-SWARE-Status: No, score=-20.1 required=5.0 tests=AWL, BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, KAM_SHORT, SPAM_BODY autolearn=ham version=3.3.1 spammy=complaints, sm, first 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:13:18 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1576260796; 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=/fxiOWTPpcQTCAB4xBUsUAwirScxhbhRVJyCJ7SgiXw=; b=BZ67XCW/qLLeGP4Q7QUQqI1Jin4bk8gdwlPI6gltaQEQBiGzdFwwf7IwimuXqEP+03qT8c +LosYDl8HtFXSAIJoorPBxIwuWeQmTb7C2+tfuf/VBhEaNsOQ1Fwy+mn2nBYc7SMGjD3Jb DNv5PzoE1AJ/bEZyxD1D+pnxS/Hfhl0= 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-42-oqkLh4_3OxGHfKEG27y4Ng-1; Fri, 13 Dec 2019 13:12:02 -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 C3A13DBE6 for ; Fri, 13 Dec 2019 18:12:01 +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 5CFE95C219; Fri, 13 Dec 2019 18:12:01 +0000 (UTC) From: David Malcolm To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [PATCH 38/45] analyzer: new files: program-state.{cc|h} Date: Fri, 13 Dec 2019 13:11:27 -0500 Message-Id: <20191213181134.1830-39-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 support for global state: - https://gcc.gnu.org/ml/gcc-patches/2019-12/msg00217.html - Rework logging to avoid exploded_graph multiple-inheritance (moving log_user base to a member) This patch introduces classes for tracking the state at a particular path of analysis. gcc/ChangeLog: * analyzer/program-state.cc: New file. * analyzer/program-state.h: New file. --- gcc/analyzer/program-state.cc | 1331 +++++++++++++++++++++++++++++++++ gcc/analyzer/program-state.h | 365 +++++++++ 2 files changed, 1696 insertions(+) create mode 100644 gcc/analyzer/program-state.cc create mode 100644 gcc/analyzer/program-state.h diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc new file mode 100644 index 000000000000..6222ce9cd627 --- /dev/null +++ b/gcc/analyzer/program-state.cc @@ -0,0 +1,1331 @@ +/* Classes for representing the state of interest at a given path of analysis. + 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 "diagnostic.h" +#include "analyzer/analyzer.h" +#include "analyzer/program-state.h" +#include "analyzer/constraint-manager.h" +#include "analyzer/exploded-graph.h" +#include "analyzer/state-purge.h" +#include "analyzer/analyzer-selftests.h" + +#if ENABLE_ANALYZER + +/* class sm_state_map. */ + +/* sm_state_map's ctor. */ + +sm_state_map::sm_state_map () +: m_map (), m_global_state (0) +{ +} + +/* Clone the sm_state_map. */ + +sm_state_map * +sm_state_map::clone () const +{ + return new sm_state_map (*this); +} + +/* Clone this sm_state_map, remapping all svalue_ids within it with ID_MAP. + + Return NULL if there are any svalue_ids that have sm-state for which + ID_MAP maps them to svalue_id::null (and thus the clone would have lost + the sm-state information). */ + +sm_state_map * +sm_state_map::clone_with_remapping (const one_way_svalue_id_map &id_map) const +{ + sm_state_map *result = new sm_state_map (); + for (typename map_t::iterator iter = m_map.begin (); + iter != m_map.end (); + ++iter) + { + svalue_id sid = (*iter).first; + gcc_assert (!sid.null_p ()); + entry_t e = (*iter).second; + /* TODO: what should we do if the origin maps from non-null to null? + Is that loss of information acceptable? */ + id_map.update (&e.m_origin); + + svalue_id new_sid = id_map.get_dst_for_src (sid); + if (new_sid.null_p ()) + { + delete result; + return NULL; + } + result->m_map.put (new_sid, e); + } + return result; +} + +/* Print this sm_state_map (for SM) to PP. */ + +void +sm_state_map::print (const state_machine &sm, pretty_printer *pp) const +{ + bool first = true; + pp_string (pp, "{"); + if (m_global_state != 0) + { + pp_printf (pp, "global: %s", sm.get_state_name (m_global_state)); + first = false; + } + for (typename map_t::iterator iter = m_map.begin (); + iter != m_map.end (); + ++iter) + { + if (!first) + pp_string (pp, ", "); + first = false; + svalue_id sid = (*iter).first; + sid.print (pp); + + entry_t e = (*iter).second; + pp_printf (pp, ": %s (origin: ", + sm.get_state_name (e.m_state)); + e.m_origin.print (pp); + pp_string (pp, ")"); + } + pp_string (pp, "}"); +} + +/* Dump this object (for SM) to stderr. */ + +DEBUG_FUNCTION void +sm_state_map::dump (const state_machine &sm) const +{ + pretty_printer pp; + pp_show_color (&pp) = pp_show_color (global_dc->printer); + pp.buffer->stream = stderr; + print (sm, &pp); + pp_newline (&pp); + pp_flush (&pp); +} + +/* Return true if no states have been set within this map + (all expressions are for the start state). */ + +bool +sm_state_map::is_empty_p () const +{ + return m_map.elements () == 0 && m_global_state == 0; +} + +/* Generate a hash value for this sm_state_map. */ + +hashval_t +sm_state_map::hash () const +{ + hashval_t result = 0; + + /* Accumulate the result by xoring a hash for each slot, so that the + result doesn't depend on the ordering of the slots in the map. */ + + for (typename map_t::iterator iter = m_map.begin (); + iter != m_map.end (); + ++iter) + { + inchash::hash hstate; + inchash::add ((*iter).first, hstate); + entry_t e = (*iter).second; + hstate.add_int (e.m_state); + inchash::add (e.m_origin, hstate); + result ^= hstate.end (); + } + result ^= m_global_state; + + return result; +} + +/* Equality operator for sm_state_map. */ + +bool +sm_state_map::operator== (const sm_state_map &other) const +{ + if (m_global_state != other.m_global_state) + return false; + + if (m_map.elements () != other.m_map.elements ()) + return false; + + for (typename map_t::iterator iter = m_map.begin (); + iter != m_map.end (); + ++iter) + { + svalue_id sid = (*iter).first; + entry_t e = (*iter).second; + entry_t *other_slot = const_cast (other.m_map).get (sid); + if (other_slot == NULL) + return false; + if (e != *other_slot) + return false; + } + + gcc_checking_assert (hash () == other.hash ()); + + return true; +} + +/* Get the state of SID within this object. + States default to the start state. */ + +state_machine::state_t +sm_state_map::get_state (svalue_id sid) const +{ + gcc_assert (!sid.null_p ()); + + if (entry_t *slot + = const_cast (m_map).get (sid)) + return slot->m_state; + else + return 0; +} + +/* Get the "origin" svalue_id for any state of SID. */ + +svalue_id +sm_state_map::get_origin (svalue_id sid) const +{ + gcc_assert (!sid.null_p ()); + + entry_t *slot + = const_cast (m_map).get (sid); + if (slot) + return slot->m_origin; + else + return svalue_id::null (); +} + +/* Set the state of SID within MODEL to STATE, recording that + the state came from ORIGIN. */ + +void +sm_state_map::set_state (region_model *model, + svalue_id sid, + state_machine::state_t state, + svalue_id origin) +{ + if (model == NULL) + return; + equiv_class &ec = model->get_constraints ()->get_equiv_class (sid); + set_state (ec, state, origin); + + /* Also do it for all svalues that are equal via non-cm, so that + e.g. (void *)&r and (foo *)&r transition together. */ + for (unsigned i = 0; i < model->get_num_svalues (); i++) + { + svalue_id other_sid = svalue_id::from_int (i); + if (other_sid == sid) + continue; + + tristate eq = model->eval_condition_without_cm (sid, EQ_EXPR, other_sid); + if (eq.is_true ()) + impl_set_state (other_sid, state, origin); + } +} + +/* Set the state of EC to STATE, recording that the state came from + ORIGIN. */ + +void +sm_state_map::set_state (const equiv_class &ec, + state_machine::state_t state, + svalue_id origin) +{ + int i; + svalue_id *sid; + FOR_EACH_VEC_ELT (ec.m_vars, i, sid) + impl_set_state (*sid, state, origin); +} + +/* Set state of PV to STATE, bypassing equivalence classes. */ + +void +sm_state_map::impl_set_state (svalue_id sid, state_machine::state_t state, + svalue_id origin) +{ + /* Special-case state 0 as the default value. */ + if (state == 0) + { + if (m_map.get (sid)) + m_map.remove (sid); + return; + } + gcc_assert (!sid.null_p ()); + m_map.put (sid, entry_t (state, origin)); +} + +/* Set the "global" state within this state map to STATE. */ + +void +sm_state_map::set_global_state (state_machine::state_t state) +{ + m_global_state = state; +} + +/* Get the "global" state within this state map. */ + +state_machine::state_t +sm_state_map::get_global_state () const +{ + return m_global_state; +} + +/* Handle CALL to unknown FNDECL with an unknown function body, which + could do anything to the states passed to it. + Clear any state for SM for the params and any LHS. + Note that the function might be known to other state machines, but + not to this one. */ + +void +sm_state_map::purge_for_unknown_fncall (const exploded_graph &eg, + const state_machine &sm, + const gcall *call, + tree fndecl, + region_model *new_model) +{ + logger * const logger = eg.get_logger (); + if (logger) + { + if (fndecl) + logger->log ("function %qE is unknown to checker %qs", + fndecl, sm.get_name ()); + else + logger->log ("unknown function pointer for checker %qs", + sm.get_name ()); + } + + /* Purge any state for parms. */ + tree iter_param_types = NULL_TREE; + if (fndecl) + iter_param_types = TYPE_ARG_TYPES (TREE_TYPE (fndecl)); + for (unsigned arg_idx = 0; arg_idx < gimple_call_num_args (call); arg_idx++) + { + /* Track expected param type, where available. */ + if (iter_param_types) + { + tree param_type = TREE_VALUE (iter_param_types); + gcc_assert (param_type); + iter_param_types = TREE_CHAIN (iter_param_types); + + /* Don't purge state if it was passed as a const pointer + e.g. for things like strlen (PTR). */ + if (TREE_CODE (param_type) == POINTER_TYPE) + if (TYPE_READONLY (TREE_TYPE (param_type))) + continue; + } + tree parm = gimple_call_arg (call, arg_idx); + svalue_id parm_sid = new_model->get_rvalue (parm, NULL); + set_state (new_model, parm_sid, 0, svalue_id::null ()); + + /* Also clear sm-state from svalue_ids that are passed via a + pointer. */ + if (TREE_CODE (parm) == ADDR_EXPR) + { + tree pointee = TREE_OPERAND (parm, 0); + svalue_id parm_sid = new_model->get_rvalue (pointee, NULL); + set_state (new_model, parm_sid, 0, svalue_id::null ()); + } + } + + /* Purge any state for any LHS. */ + if (tree lhs = gimple_call_lhs (call)) + { + svalue_id lhs_sid = new_model->get_rvalue (lhs, NULL); + set_state (new_model, lhs_sid, 0, svalue_id::null ()); + } +} + +/* Update this map based on MAP. */ + +void +sm_state_map::remap_svalue_ids (const svalue_id_map &map) +{ + map_t tmp_map; + + /* Build an intermediate map, using the new sids. */ + for (typename map_t::iterator iter = m_map.begin (); + iter != m_map.end (); + ++iter) + { + svalue_id sid = (*iter).first; + entry_t e = (*iter).second; + + map.update (&sid); + map.update (&e.m_origin); + tmp_map.put (sid, e); + } + + /* Clear the existing values. */ + m_map.empty (); + + /* Copy over from intermediate map. */ + for (typename map_t::iterator iter = tmp_map.begin (); + iter != tmp_map.end (); + ++iter) + { + svalue_id sid = (*iter).first; + entry_t e = (*iter).second; + + impl_set_state (sid, e.m_state, e.m_origin); + } +} + +/* Purge any state for svalue_ids >= FIRST_UNUSED_SID. + If !SM::can_purge_p, then report the state as leaking, + using SM_IDX, CTXT, and MAP. + Return the number of states that were purged. */ + +int +sm_state_map::on_svalue_purge (const state_machine &sm, + int sm_idx, + svalue_id first_unused_sid, + const svalue_id_map &map, + impl_region_model_context *ctxt) +{ + /* TODO: ideally remove the slot directly; for now + do it in two stages. */ + auto_vec to_remove; + for (typename map_t::iterator iter = m_map.begin (); + iter != m_map.end (); + ++iter) + { + svalue_id dst_sid ((*iter).first); + if (dst_sid.as_int () >= first_unused_sid.as_int ()) + { + /* Complain about leaks here. */ + entry_t e = (*iter).second; + + if (!sm.can_purge_p (e.m_state)) + ctxt->on_state_leak (sm, sm_idx, dst_sid, first_unused_sid, + map, e.m_state); + + to_remove.safe_push (dst_sid); + } + } + + int i; + svalue_id *dst_sid; + FOR_EACH_VEC_ELT (to_remove, i, dst_sid) + m_map.remove (*dst_sid); + + return to_remove.length (); +} + +/* Set the state of CHILD_SID to that of PARENT_SID. */ + +void +sm_state_map::on_inherited_svalue (svalue_id parent_sid, + svalue_id child_sid) +{ + state_machine::state_t state = get_state (parent_sid); + impl_set_state (child_sid, state, parent_sid); +} + +/* Set the state of DST_SID to that of SRC_SID. */ + +void +sm_state_map::on_cast (svalue_id src_sid, + svalue_id dst_sid) +{ + state_machine::state_t state = get_state (src_sid); + impl_set_state (dst_sid, state, get_origin (src_sid)); +} + +/* Assert that this object is sane. */ + +void +sm_state_map::validate (const state_machine &sm, + int num_svalues) const +{ + /* Skip this in a release build. */ +#if !CHECKING_P + return; +#endif + + for (typename map_t::iterator iter = m_map.begin (); + iter != m_map.end (); + ++iter) + { + svalue_id sid = (*iter).first; + entry_t e = (*iter).second; + + gcc_assert (sid.as_int () < num_svalues); + sm.validate (e.m_state); + gcc_assert (e.m_origin.as_int () < num_svalues); + } +} + +/* class program_state. */ + +/* program_state's ctor. */ + +program_state::program_state (const extrinsic_state &ext_state) +: m_region_model (new region_model ()), + m_checker_states (ext_state.m_checkers.length ()) +{ + int num_states = ext_state.m_checkers.length (); + for (int i = 0; i < num_states; i++) + m_checker_states.quick_push (new sm_state_map ()); +} + +/* program_state's copy ctor. */ + +program_state::program_state (const program_state &other) +: m_region_model (new region_model (*other.m_region_model)), + m_checker_states (other.m_checker_states.length ()) +{ + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (other.m_checker_states, i, smap) + m_checker_states.quick_push (smap->clone ()); +} + +/* program_state's assignment operator. */ + +program_state& +program_state::operator= (const program_state &other) +{ + delete m_region_model; + m_region_model = new region_model (*other.m_region_model); + + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (m_checker_states, i, smap) + delete smap; + m_checker_states.truncate (0); + gcc_assert (m_checker_states.space (other.m_checker_states.length ())); + + FOR_EACH_VEC_ELT (other.m_checker_states, i, smap) + m_checker_states.quick_push (smap->clone ()); + + return *this; +} + +#if __cplusplus >= 201103 +/* Move constructor for program_state (when building with C++11). */ +program_state::program_state (program_state &&other) +: m_region_model (other.m_region_model), + m_checker_states (other.m_checker_states.length ()) +{ + other.m_region_model = NULL; + + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (other.m_checker_states, i, smap) + m_checker_states.quick_push (smap); + other.m_checker_states.truncate (0); +} +#endif + +/* program_state's dtor. */ + +program_state::~program_state () +{ + delete m_region_model; +} + +/* Generate a hash value for this program_state. */ + +hashval_t +program_state::hash () const +{ + hashval_t result = m_region_model->hash (); + + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (m_checker_states, i, smap) + result ^= smap->hash (); + return result; +} + +/* Equality operator for program_state. + All parts of the program_state (region model, checker states) must + equal their counterparts in OTHER for the two program_states to be + considered equal. */ + +bool +program_state::operator== (const program_state &other) const +{ + if (!(*m_region_model == *other.m_region_model)) + return false; + + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (m_checker_states, i, smap) + if (!(*smap == *other.m_checker_states[i])) + return false; + + gcc_checking_assert (hash () == other.hash ()); + + return true; +} + +/* Print a compact representation of this state to PP. */ + +void +program_state::print (const extrinsic_state &ext_state, + pretty_printer *pp) const +{ + pp_printf (pp, "rmodel: "); + m_region_model->print (pp); + pp_newline (pp); + + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (m_checker_states, i, smap) + { + if (!smap->is_empty_p ()) + { + pp_printf (pp, "%s: ", ext_state.get_name (i)); + smap->print (ext_state.get_sm (i), pp); + pp_newline (pp); + } + } +} + +/* Dump a multiline representation of this state to PP. */ + +void +program_state::dump_to_pp (const extrinsic_state &ext_state, + bool summarize, + pretty_printer *pp) const +{ + pp_printf (pp, "rmodel: "); + m_region_model->dump_to_pp (pp, summarize); + + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (m_checker_states, i, smap) + { + if (!smap->is_empty_p ()) + { + pp_printf (pp, "%s: ", ext_state.get_name (i)); + smap->print (ext_state.get_sm (i), pp); + pp_newline (pp); + } + } +} + +/* Dump a multiline representation of this state to OUTF. */ + +void +program_state::dump_to_file (const extrinsic_state &ext_state, + bool summarize, + FILE *outf) const +{ + pretty_printer pp; + pp_format_decoder (&pp) = default_tree_printer; + if (outf == stderr) + pp_show_color (&pp) = pp_show_color (global_dc->printer); + pp.buffer->stream = outf; + dump_to_pp (ext_state, summarize, &pp); + pp_flush (&pp); +} + +/* Dump a multiline representation of this state to stderr. */ + +DEBUG_FUNCTION void +program_state::dump (const extrinsic_state &ext_state, + bool summarize) const +{ + dump_to_file (ext_state, summarize, stderr); +} + +/* Determine if following edge SUCC from ENODE is valid within the graph EG + and update this state accordingly in-place. + + Return true if the edge can be followed, or false otherwise. + + Check for relevant conditionals and switch-values for conditionals + and switch statements, adding the relevant conditions to this state. + Push/pop frames for interprocedural edges and update params/returned + values. + + This is the "state" half of exploded_node::on_edge. */ + +bool +program_state::on_edge (exploded_graph &eg, + const exploded_node &enode, + const superedge *succ, + state_change *change) +{ + /* Update state. */ + const program_point &point = enode.get_point (); + const gimple *last_stmt = point.get_supernode ()->get_last_stmt (); + + /* For conditionals and switch statements, add the + relevant conditions (for the specific edge) to new_state; + skip edges for which the resulting constraints + are impossible. + This also updates frame information for call/return superedges. + Adding the relevant conditions for the edge could also trigger + sm-state transitions (e.g. transitions due to ptrs becoming known + to be NULL or non-NULL) */ + + impl_region_model_context ctxt (eg, &enode, + &enode.get_state (), + this, change, + last_stmt); + if (!m_region_model->maybe_update_for_edge (*succ, + last_stmt, + &ctxt)) + { + logger * const logger = eg.get_logger (); + if (logger) + logger->log ("edge to SN: %i is impossible" + " due to region_model constraints", + succ->m_dest->m_index); + return false; + } + + return true; +} + +/* Generate a simpler version of THIS, discarding state that's no longer + relevant at POINT. + The idea is that we're more likely to be able to consolidate + multiple (point, state) into single exploded_nodes if we discard + irrelevant state (e.g. at the end of functions). + + Retain state affected by CHANGE, to make it easier to generate + state_change_events. */ + +program_state +program_state::prune_for_point (exploded_graph &eg, + const program_point &point, + state_change *change) const +{ + logger * const logger = eg.get_logger (); + LOG_SCOPE (logger); + + function *fun = point.get_function (); + if (!fun) + return *this; + + program_state new_state (*this); + + purge_stats stats; + + const state_purge_map *pm = eg.get_purge_map (); + if (pm) + { + region_id_set purgeable_ssa_regions (new_state.m_region_model); + region_id frame_rid + = new_state.m_region_model->get_current_frame_id (); + frame_region *frame + = new_state.m_region_model->get_region (frame_rid); + + /* TODO: maybe move to a member of region_model? */ + + auto_vec ssa_names_to_purge; + for (frame_region::map_t::iterator iter = frame->begin (); + iter != frame->end (); + ++iter) + { + tree var = (*iter).first; + region_id rid = (*iter).second; + if (TREE_CODE (var) == SSA_NAME) + { + const state_purge_per_ssa_name &per_ssa + = pm->get_data_for_ssa_name (var); + if (!per_ssa.needed_at_point_p (point.get_function_point ())) + { + region *region + = new_state.m_region_model->get_region (rid); + svalue_id sid = region->get_value_direct (); + if (!sid.null_p ()) + { + if (!new_state.can_purge_p (eg.get_ext_state (), sid)) + { + /* (currently only state maps can keep things + alive). */ + if (logger) + logger->log ("not purging RID: %i for %qE" + " (used by state map)", + rid.as_int (), var); + continue; + } + + /* Don't purge regions containing svalues that + have a change of sm-state, to make it easier to + generate state_change_event messages. */ + if (change) + if (change->affects_p (sid)) + { + if (logger) + logger->log ("not purging RID: %i for %qE" + " (affected by change)", + rid.as_int (), var); + continue; + } + } + purgeable_ssa_regions.add_region (rid); + ssa_names_to_purge.safe_push (var); + if (logger) + logger->log ("purging RID: %i for %qE", rid.as_int (), var); + /* We also need to remove the region from the map. + We're in mid-traversal, so the removal is done in + unbind below. */ + } + } + } + + /* Unbind the regions from the frame's map of vars-to-regions. */ + unsigned i; + tree var; + FOR_EACH_VEC_ELT (ssa_names_to_purge, i, var) + frame->unbind (var); + + /* Purge the regions. Nothing should point to them, and they + should have no children, as they are for SSA names. */ + new_state.m_region_model->purge_regions (purgeable_ssa_regions, + &stats, + eg.get_logger ()); + } + + /* Purge unused svalues. */ + // TODO: which enode to use, if any? + impl_region_model_context ctxt (eg, NULL, + this, + &new_state, + change, + NULL); + new_state.m_region_model->purge_unused_svalues (&stats, &ctxt); + if (logger) + { + logger->log ("num svalues purged: %i", stats.m_num_svalues); + logger->log ("num regions purged: %i", stats.m_num_regions); + logger->log ("num equiv_classes purged: %i", stats.m_num_equiv_classes); + logger->log ("num constraints purged: %i", stats.m_num_constraints); + logger->log ("num sm map items purged: %i", stats.m_num_client_items); + } + + new_state.m_region_model->canonicalize (&ctxt); + + return new_state; +} + +/* Remap all svalue_ids in this state's m_checker_states according to MAP. + The svalues_ids in the region_model are assumed to already have been + remapped. */ + +void +program_state::remap_svalue_ids (const svalue_id_map &map) +{ + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (m_checker_states, i, smap) + smap->remap_svalue_ids (map); +} + +/* Attempt to return a tree that represents SID, or return NULL_TREE. + Find the first region that stores the value (e.g. a local) and + generate a representative tree for it. */ + +tree +program_state::get_representative_tree (svalue_id sid) const +{ + return m_region_model->get_representative_tree (sid); +} + +/* Attempt to merge this state with OTHER, both using EXT_STATE. + Write the result to *OUT. + If the states were merged successfully, return true. */ + +bool +program_state::can_merge_with_p (const program_state &other, + const extrinsic_state &ext_state, + program_state *out) const +{ + gcc_assert (out); + + /* TODO: initially I had an early reject here if there + are sm-differences between the states. However, this was + falsely rejecting merger opportunities for states where the + only difference was in svalue_id ordering. */ + + /* Attempt to merge the region_models. */ + + svalue_id_merger_mapping sid_mapping (*m_region_model, + *other.m_region_model); + if (!m_region_model->can_merge_with_p (*other.m_region_model, + out->m_region_model, + &sid_mapping)) + return false; + + /* Copy m_checker_states to result, remapping svalue_ids using + sid_mapping. */ + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (out->m_checker_states, i, smap) + delete smap; + out->m_checker_states.truncate (0); + + /* Remap this and other's m_checker_states using sid_mapping. + Only merge states that have equality between the two end-results: + sm-state differences are likely to be interesting to end-users, and + hence are worth exploring as separate paths in the exploded graph. */ + FOR_EACH_VEC_ELT (m_checker_states, i, smap) + { + sm_state_map *other_smap = other.m_checker_states[i]; + + /* If clone_with_remapping returns NULL for one of the input smaps, + then it has sm-state for an svalue_id where the svalue_id is + being mapped to svalue_id::null in its sid_mapping, meaning that + the svalue is to be dropped during the merger. We don't want + to lose sm-state during a state merger, so return false for these + cases. */ + sm_state_map *remapped_a_smap + = smap->clone_with_remapping (sid_mapping.m_map_from_a_to_m); + if (!remapped_a_smap) + return false; + sm_state_map *remapped_b_smap + = other_smap->clone_with_remapping (sid_mapping.m_map_from_b_to_m); + if (!remapped_b_smap) + { + delete remapped_a_smap; + return false; + } + + /* Both states have sm-state for the same values; now ensure that the + states are equal. */ + if (*remapped_a_smap == *remapped_b_smap) + { + out->m_checker_states.safe_push (remapped_a_smap); + delete remapped_b_smap; + } + else + { + /* Don't merge if there are sm-state differences. */ + delete remapped_a_smap; + delete remapped_b_smap; + return false; + } + } + + impl_region_model_context ctxt (out, NULL, ext_state); + out->m_region_model->canonicalize (&ctxt); + + return true; +} + +/* Assert that this object is valid. */ + +void +program_state::validate (const extrinsic_state &ext_state) const +{ + /* Skip this in a release build. */ +#if !CHECKING_P + return; +#endif + + m_region_model->validate (); + gcc_assert (m_checker_states.length () == ext_state.get_num_checkers ()); + int sm_idx; + sm_state_map *smap; + FOR_EACH_VEC_ELT (m_checker_states, sm_idx, smap) + { + const state_machine &sm = ext_state.get_sm (sm_idx); + smap->validate (sm, m_region_model->get_num_svalues ()); + } +} + +/* Dump this sm_change to PP. */ + +void +state_change::sm_change::dump (pretty_printer *pp, + const extrinsic_state &ext_state) const +{ + const state_machine &sm = get_sm (ext_state); + pp_string (pp, "("); + m_new_sid.print (pp); + pp_printf (pp, ": %s: %qs -> %qs)", + sm.get_name (), + sm.get_state_name (m_old_state), + sm.get_state_name (m_new_state)); +} + +/* Remap all svalue_ids in this change according to MAP. */ + +void +state_change::sm_change::remap_svalue_ids (const svalue_id_map &map) +{ + map.update (&m_new_sid); +} + +/* Purge any svalue_ids >= FIRST_UNUSED_SID. + Return the number of states that were purged. */ + +int +state_change::sm_change::on_svalue_purge (svalue_id first_unused_sid) +{ + if (m_new_sid.as_int () >= first_unused_sid.as_int ()) + { + m_new_sid = svalue_id::null (); + return 1; + } + + return 0; +} + +/* Assert that this object is sane. */ + +void +state_change::sm_change::validate (const program_state &new_state) const +{ + m_new_sid.validate (*new_state.m_region_model); +} + +/* state_change's ctor. */ + +state_change::state_change () +{ +} + +/* state_change's copy ctor. */ + +state_change::state_change (const state_change &other) +: m_sm_changes (other.m_sm_changes.length ()) +{ + unsigned i; + sm_change *change; + FOR_EACH_VEC_ELT (other.m_sm_changes, i, change) + m_sm_changes.quick_push (*change); +} + +/* Record a state-machine state change. */ + +void +state_change::add_sm_change (int sm_idx, + svalue_id new_sid, + state_machine::state_t old_state, + state_machine::state_t new_state) +{ + m_sm_changes.safe_push (sm_change (sm_idx, + new_sid, + old_state, new_state)); +} + +/* Return true if SID (in the new state) was affected by any + sm-state changes. */ + +bool +state_change::affects_p (svalue_id sid) const +{ + unsigned i; + sm_change *change; + FOR_EACH_VEC_ELT (m_sm_changes, i, change) + { + if (sid == change->m_new_sid) + return true; + } + return false; +} + +/* Dump this state_change to PP. */ + +void +state_change::dump (pretty_printer *pp, + const extrinsic_state &ext_state) const +{ + unsigned i; + sm_change *change; + FOR_EACH_VEC_ELT (m_sm_changes, i, change) + { + if (i > 0) + pp_string (pp, ", "); + change->dump (pp, ext_state); + } +} + +/* Dump this state_change to stderr. */ + +void +state_change::dump (const extrinsic_state &ext_state) const +{ + pretty_printer pp; + pp_show_color (&pp) = pp_show_color (global_dc->printer); + pp.buffer->stream = stderr; + dump (&pp, ext_state); + pp_newline (&pp); + pp_flush (&pp); +} + +/* Remap all svalue_ids in this state_change according to MAP. */ + +void +state_change::remap_svalue_ids (const svalue_id_map &map) +{ + unsigned i; + sm_change *change; + FOR_EACH_VEC_ELT (m_sm_changes, i, change) + change->remap_svalue_ids (map); +} + +/* Purge any svalue_ids >= FIRST_UNUSED_SID. + Return the number of states that were purged. */ + +int +state_change::on_svalue_purge (svalue_id first_unused_sid) +{ + int result = 0; + unsigned i; + sm_change *change; + FOR_EACH_VEC_ELT (m_sm_changes, i, change) + result += change->on_svalue_purge (first_unused_sid); + return result; +} + +/* Assert that this object is sane. */ + +void +state_change::validate (const program_state &new_state) const +{ + /* Skip this in a release build. */ +#if !CHECKING_P + return; +#endif + unsigned i; + sm_change *change; + FOR_EACH_VEC_ELT (m_sm_changes, i, change) + change->validate (new_state); +} + +#if CHECKING_P + +namespace selftest { + +/* Tests for sm_state_map. */ + +static void +test_sm_state_map () +{ + tree x = build_global_decl ("x", integer_type_node); + tree y = build_global_decl ("y", integer_type_node); + tree z = build_global_decl ("z", integer_type_node); + + /* Test setting states on svalue_id instances directly. */ + { + region_model model; + svalue_id sid_x = model.get_rvalue (x, NULL); + svalue_id sid_y = model.get_rvalue (y, NULL); + svalue_id sid_z = model.get_rvalue (z, NULL); + + sm_state_map map; + ASSERT_TRUE (map.is_empty_p ()); + ASSERT_EQ (map.get_state (sid_x), 0); + + map.impl_set_state (sid_x, 42, sid_z); + ASSERT_EQ (map.get_state (sid_x), 42); + ASSERT_EQ (map.get_origin (sid_x), sid_z); + ASSERT_EQ (map.get_state (sid_y), 0); + ASSERT_FALSE (map.is_empty_p ()); + + map.impl_set_state (sid_y, 0, sid_z); + ASSERT_EQ (map.get_state (sid_y), 0); + + map.impl_set_state (sid_x, 0, sid_z); + ASSERT_EQ (map.get_state (sid_x), 0); + ASSERT_TRUE (map.is_empty_p ()); + } + + /* Test setting states via equivalence classes. */ + { + region_model model; + svalue_id sid_x = model.get_rvalue (x, NULL); + svalue_id sid_y = model.get_rvalue (y, NULL); + svalue_id sid_z = model.get_rvalue (z, NULL); + + sm_state_map map; + ASSERT_TRUE (map.is_empty_p ()); + ASSERT_EQ (map.get_state (sid_x), 0); + ASSERT_EQ (map.get_state (sid_y), 0); + + model.add_constraint (x, EQ_EXPR, y, NULL); + + /* Setting x to a state should also update y, as they + are in the same equivalence class. */ + map.set_state (&model, sid_x, 5, sid_z); + ASSERT_EQ (map.get_state (sid_x), 5); + ASSERT_EQ (map.get_state (sid_y), 5); + ASSERT_EQ (map.get_origin (sid_x), sid_z); + ASSERT_EQ (map.get_origin (sid_y), sid_z); + } + + /* Test equality and hashing. */ + { + region_model model; + svalue_id sid_y = model.get_rvalue (y, NULL); + svalue_id sid_z = model.get_rvalue (z, NULL); + + sm_state_map map0; + sm_state_map map1; + sm_state_map map2; + + ASSERT_EQ (map0.hash (), map1.hash ()); + ASSERT_EQ (map0, map1); + + map1.impl_set_state (sid_y, 5, sid_z); + ASSERT_NE (map0.hash (), map1.hash ()); + ASSERT_NE (map0, map1); + + /* Make the same change to map2. */ + map2.impl_set_state (sid_y, 5, sid_z); + ASSERT_EQ (map1.hash (), map2.hash ()); + ASSERT_EQ (map1, map2); + } + + /* Equality and hashing shouldn't depend on ordering. */ + { + sm_state_map map0; + sm_state_map map1; + sm_state_map map2; + + ASSERT_EQ (map0.hash (), map1.hash ()); + ASSERT_EQ (map0, map1); + + map1.impl_set_state (svalue_id::from_int (14), 2, svalue_id::null ()); + map1.impl_set_state (svalue_id::from_int (16), 3, svalue_id::null ()); + map1.impl_set_state (svalue_id::from_int (1), 2, svalue_id::null ()); + map1.impl_set_state (svalue_id::from_int (9), 2, svalue_id::null ()); + + map2.impl_set_state (svalue_id::from_int (1), 2, svalue_id::null ()); + map2.impl_set_state (svalue_id::from_int (16), 3, svalue_id::null ()); + map2.impl_set_state (svalue_id::from_int (14), 2, svalue_id::null ()); + map2.impl_set_state (svalue_id::from_int (9), 2, svalue_id::null ()); + + ASSERT_EQ (map1.hash (), map2.hash ()); + ASSERT_EQ (map1, map2); + } + + /* Test sm_state_map::remap_svalue_ids. */ + { + sm_state_map map; + svalue_id sid_0 = svalue_id::from_int (0); + svalue_id sid_1 = svalue_id::from_int (1); + svalue_id sid_2 = svalue_id::from_int (2); + + map.impl_set_state (sid_0, 42, sid_2); + ASSERT_EQ (map.get_state (sid_0), 42); + ASSERT_EQ (map.get_origin (sid_0), sid_2); + ASSERT_EQ (map.get_state (sid_1), 0); + ASSERT_EQ (map.get_state (sid_2), 0); + + /* Apply a remapping to the IDs. */ + svalue_id_map remapping (3); + remapping.put (sid_0, sid_1); + remapping.put (sid_1, sid_2); + remapping.put (sid_2, sid_0); + map.remap_svalue_ids (remapping); + + /* Verify that the IDs have been remapped. */ + ASSERT_EQ (map.get_state (sid_1), 42); + ASSERT_EQ (map.get_origin (sid_1), sid_0); + ASSERT_EQ (map.get_state (sid_2), 0); + ASSERT_EQ (map.get_state (sid_0), 0); + } + + // TODO: coverage for purging +} + +/* Verify that program_states with identical sm-state can be merged, + and that the merged program_state preserves the sm-state. */ + +static void +test_program_state_merging () +{ + /* Create a program_state for a global ptr "p" that has + malloc sm-state, pointing to a region on the heap. */ + tree p = build_global_decl ("p", ptr_type_node); + + auto_delete_vec checkers; + checkers.safe_push (make_malloc_state_machine (NULL)); + extrinsic_state ext_state (checkers); + + program_state s0 (ext_state); + impl_region_model_context ctxt (&s0, NULL, ext_state); + + region_model *model0 = s0.m_region_model; + region_id new_rid = model0->add_new_malloc_region (); + svalue_id ptr_sid + = model0->get_or_create_ptr_svalue (ptr_type_node, new_rid); + model0->set_value (model0->get_lvalue (p, &ctxt), + ptr_sid, &ctxt); + sm_state_map *smap = s0.m_checker_states[0]; + const state_machine::state_t TEST_STATE = 3; + smap->impl_set_state (ptr_sid, TEST_STATE, svalue_id::null ()); + ASSERT_EQ (smap->get_state (ptr_sid), TEST_STATE); + + model0->canonicalize (&ctxt); + + /* Verify that canonicalization preserves sm-state. */ + ASSERT_EQ (smap->get_state (model0->get_rvalue (p, NULL)), TEST_STATE); + + /* Make a copy of the program_state. */ + program_state s1 (s0); + ASSERT_EQ (s0, s1); + + /* We have two identical states with "p" pointing to a heap region + with the given sm-state. + They ought to be mergeable, preserving the sm-state. */ + program_state merged (ext_state); + ASSERT_TRUE (s0.can_merge_with_p (s1, ext_state, &merged)); + merged.validate (ext_state); + + /* Verify that the merged state has the sm-state for "p". */ + region_model *merged_model = merged.m_region_model; + sm_state_map *merged_smap = merged.m_checker_states[0]; + ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL)), + TEST_STATE); + + /* Try canonicalizing. */ + impl_region_model_context merged_ctxt (&merged, NULL, ext_state); + merged.m_region_model->canonicalize (&merged_ctxt); + merged.validate (ext_state); + + /* Verify that the merged state still has the sm-state for "p". */ + ASSERT_EQ (merged_smap->get_state (merged_model->get_rvalue (p, NULL)), + TEST_STATE); + + /* After canonicalization, we ought to have equality with the inputs. */ + ASSERT_EQ (s0, merged); +} + +/* Run all of the selftests within this file. */ + +void +analyzer_program_state_cc_tests () +{ + test_sm_state_map (); + test_program_state_merging (); +} + +} // namespace selftest + +#endif /* CHECKING_P */ + +#endif /* #if ENABLE_ANALYZER */ diff --git a/gcc/analyzer/program-state.h b/gcc/analyzer/program-state.h new file mode 100644 index 000000000000..5aab319a84c2 --- /dev/null +++ b/gcc/analyzer/program-state.h @@ -0,0 +1,365 @@ +/* Classes for representing the state of interest at a given path of analysis. + 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_PROGRAM_STATE_H +#define GCC_ANALYZER_PROGRAM_STATE_H + +#include "analyzer/sm.h" +#include "analyzer/region-model.h" + +/* Data shared by all program_state instances. */ + +class extrinsic_state +{ +public: + extrinsic_state (auto_delete_vec &checkers) + : m_checkers (checkers) + { + } + + const state_machine &get_sm (int idx) const + { + return *m_checkers[idx]; + } + + const char *get_name (int idx) const + { + return m_checkers[idx]->get_name (); + } + + unsigned get_num_checkers () const { return m_checkers.length (); } + + /* The state machines. */ + auto_delete_vec &m_checkers; +}; + +template <> struct default_hash_traits +: public pod_hash_traits +{ +}; + +template <> +inline hashval_t +pod_hash_traits::hash (value_type v) +{ + return v.as_int (); +} + +template <> +inline bool +pod_hash_traits::equal (const value_type &existing, + const value_type &candidate) +{ + return existing == candidate; +} +template <> +inline void +pod_hash_traits::mark_deleted (value_type &v) +{ + v = svalue_id::from_int (-2); +} +template <> +inline void +pod_hash_traits::mark_empty (value_type &v) +{ + v = svalue_id::null (); +} +template <> +inline bool +pod_hash_traits::is_deleted (value_type v) +{ + return v.as_int () == -2; +} +template <> +inline bool +pod_hash_traits::is_empty (value_type v) +{ + return v.null_p (); +} + +/* Map from svalue_id to state machine state, also capturing the origin of + each state. */ + +class sm_state_map +{ +public: + /* An entry in the hash_map. */ + struct entry_t + { + /* Default ctor needed by hash_map::empty. */ + entry_t () + : m_state (0), m_origin (svalue_id::null ()) + { + } + + entry_t (state_machine::state_t state, + svalue_id origin) + : m_state (state), m_origin (origin) + {} + + bool operator== (const entry_t &other) const + { + return (m_state == other.m_state + && m_origin == other.m_origin); + } + bool operator!= (const entry_t &other) const + { + return !(*this == other); + } + + state_machine::state_t m_state; + svalue_id m_origin; + }; + typedef hash_map map_t; + typedef typename map_t::iterator iterator_t; + + sm_state_map (); + + sm_state_map *clone () const; + + sm_state_map * + clone_with_remapping (const one_way_svalue_id_map &id_map) const; + + void print (const state_machine &sm, pretty_printer *pp) const; + void dump (const state_machine &sm) const; + + bool is_empty_p () const; + + hashval_t hash () const; + + bool operator== (const sm_state_map &other) const; + bool operator!= (const sm_state_map &other) const + { + return !(*this == other); + } + + state_machine::state_t get_state (svalue_id sid) const; + svalue_id get_origin (svalue_id sid) const; + + void set_state (region_model *model, + svalue_id sid, + state_machine::state_t state, + svalue_id origin); + void set_state (const equiv_class &ec, + state_machine::state_t state, + svalue_id origin); + void impl_set_state (svalue_id sid, + state_machine::state_t state, + svalue_id origin); + + void set_global_state (state_machine::state_t state); + state_machine::state_t get_global_state () const; + + void purge_for_unknown_fncall (const exploded_graph &eg, + const state_machine &sm, + const gcall *call, tree fndecl, + region_model *new_model); + + void remap_svalue_ids (const svalue_id_map &map); + + int on_svalue_purge (const state_machine &sm, + int sm_idx, + svalue_id first_unused_sid, + const svalue_id_map &map, + impl_region_model_context *ctxt); + + void on_inherited_svalue (svalue_id parent_sid, + svalue_id child_sid); + + void on_cast (svalue_id src_sid, + svalue_id dst_sid); + + void validate (const state_machine &sm, int num_svalues) const; + + iterator_t begin () const { return m_map.begin (); } + iterator_t end () const { return m_map.end (); } + +private: + map_t m_map; + state_machine::state_t m_global_state; +}; + +/* A class for representing the state of interest at a given path of + analysis. + + Currently this is a combination of: + (a) a region_model, giving: + (a.1) a hierarchy of memory regions + (a.2) values for the regions + (a.3) inequalities between values + (b) sm_state_maps per state machine, giving a sparse mapping of + values to states. */ + +class program_state +{ +public: + program_state (const extrinsic_state &ext_state); + program_state (const program_state &other); + program_state& operator= (const program_state &other); + +#if __cplusplus >= 201103 + program_state (program_state &&other); + program_state& operator= (program_state &&other); // doesn't seem to be used +#endif + + ~program_state (); + + hashval_t hash () const; + bool operator== (const program_state &other) const; + bool operator!= (const program_state &other) const + { + return !(*this == other); + } + + void print (const extrinsic_state &ext_state, + pretty_printer *pp) const; + + void dump_to_pp (const extrinsic_state &ext_state, bool summarize, + pretty_printer *pp) const; + void dump_to_file (const extrinsic_state &ext_state, bool summarize, + FILE *outf) const; + void dump (const extrinsic_state &ext_state, bool summarize) const; + + bool on_edge (exploded_graph &eg, + const exploded_node &enode, + const superedge *succ, + state_change *change); + + program_state prune_for_point (exploded_graph &eg, + const program_point &point, + state_change *change) const; + + void remap_svalue_ids (const svalue_id_map &map); + + tree get_representative_tree (svalue_id sid) const; + + bool can_purge_p (const extrinsic_state &ext_state, + svalue_id sid) + { + /* Don't purge vars that have non-purgeable sm state, to avoid + generating false "leak" complaints. */ + int i; + sm_state_map *smap; + FOR_EACH_VEC_ELT (m_checker_states, i, smap) + { + const state_machine &sm = ext_state.get_sm (i); + if (!sm.can_purge_p (smap->get_state (sid))) + return false; + } + return true; + } + + bool can_merge_with_p (const program_state &other, + const extrinsic_state &ext_state, + program_state *out) const; + + void validate (const extrinsic_state &ext_state) const; + + /* TODO: lose the pointer here (const-correctness issues?). */ + region_model *m_region_model; + auto_delete_vec m_checker_states; +}; + +/* An abstract base class for use with for_each_state_change. */ + +class state_change_visitor +{ +public: + virtual ~state_change_visitor () {} + + /* Return true for early exit, false to keep iterating. */ + virtual bool on_global_state_change (const state_machine &sm, + state_machine::state_t src_sm_val, + state_machine::state_t dst_sm_val) = 0; + + /* Return true for early exit, false to keep iterating. */ + virtual 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) = 0; +}; + +extern bool for_each_state_change (const program_state &src_state, + const program_state &dst_state, + const extrinsic_state &ext_state, + state_change_visitor *visitor); + +/* A class for recording "interesting" state changes. + This is used for annotating edges in the GraphViz output of the + exploded_graph, and for recording sm-state-changes, so that + values that change aren't purged (to make it easier to generate + state_change_event instances in the diagnostic_path). */ + +class state_change +{ + public: + struct sm_change + { + sm_change (int sm_idx, + svalue_id new_sid, + state_machine::state_t old_state, + state_machine::state_t new_state) + : m_sm_idx (sm_idx), + m_new_sid (new_sid), + m_old_state (old_state), m_new_state (new_state) + {} + + const state_machine &get_sm (const extrinsic_state &ext_state) const + { + return ext_state.get_sm (m_sm_idx); + } + + void dump (pretty_printer *pp, const extrinsic_state &ext_state) const; + + void remap_svalue_ids (const svalue_id_map &map); + int on_svalue_purge (svalue_id first_unused_sid); + + void validate (const program_state &new_state) const; + + int m_sm_idx; + svalue_id m_new_sid; + state_machine::state_t m_old_state; + state_machine::state_t m_new_state; + }; + + state_change (); + state_change (const state_change &other); + + void add_sm_change (int sm_idx, + svalue_id new_sid, + state_machine::state_t old_state, + state_machine::state_t new_state); + + bool affects_p (svalue_id sid) const; + + void dump (pretty_printer *pp, const extrinsic_state &ext_state) const; + void dump (const extrinsic_state &ext_state) const; + + void remap_svalue_ids (const svalue_id_map &map); + int on_svalue_purge (svalue_id first_unused_sid); + + void validate (const program_state &new_state) const; + + private: + auto_vec m_sm_changes; +}; + +#endif /* GCC_ANALYZER_PROGRAM_STATE_H */