/* Classes for representing the state of interest at a given path of analysis. Copyright (C) 2019-2020 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-core.h" #include "diagnostic.h" #include "function.h" #include "analyzer/analyzer.h" #include "analyzer/analyzer-logging.h" #include "analyzer/sm.h" #include "sbitmap.h" #include "bitmap.h" #include "tristate.h" #include "ordered-hash-map.h" #include "selftest.h" #include "analyzer/region-model.h" #include "analyzer/program-state.h" #include "analyzer/constraint-manager.h" #include "alloc-pool.h" #include "fibonacci_heap.h" #include "shortest-paths.h" #include "analyzer/constraint-manager.h" #include "diagnostic-event-id.h" #include "analyzer/pending-diagnostic.h" #include "analyzer/diagnostic-manager.h" #include "cfg.h" #include "basic-block.h" #include "gimple.h" #include "gimple-iterator.h" #include "cgraph.h" #include "digraph.h" #include "analyzer/supergraph.h" #include "analyzer/call-string.h" #include "analyzer/program-point.h" #include "analyzer/program-state.h" #include "analyzer/exploded-graph.h" #include "analyzer/state-purge.h" #include "analyzer/analyzer-selftests.h" #if ENABLE_ANALYZER namespace ana { /* class extrinsic_state. */ /* Dump a multiline representation of this state to PP. */ void extrinsic_state::dump_to_pp (pretty_printer *pp) const { pp_printf (pp, "extrinsic_state: %i checker(s)\n", get_num_checkers ()); unsigned i; state_machine *checker; FOR_EACH_VEC_ELT (m_checkers, i, checker) { pp_printf (pp, "m_checkers[%i]: %qs\n", i, checker->get_name ()); checker->dump_to_pp (pp); } } /* Dump a multiline representation of this state to OUTF. */ void extrinsic_state::dump_to_file (FILE *outf) const { pretty_printer pp; if (outf == stderr) pp_show_color (&pp) = pp_show_color (global_dc->printer); pp.buffer->stream = outf; dump_to_pp (&pp); pp_flush (&pp); } /* Dump a multiline representation of this state to stderr. */ DEBUG_FUNCTION void extrinsic_state::dump () const { dump_to_file (stderr); } /* 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 (); result->m_global_state = m_global_state; for (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. If MODEL is non-NULL, print representative tree values where available. */ void sm_state_map::print (const state_machine &sm, const region_model *model, 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 (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", sm.get_state_name (e.m_state)); if (model) if (tree rep = model->get_representative_tree (sid)) { pp_string (pp, " ("); dump_quoted_tree (pp, rep); pp_character (pp, ')'); } if (!e.m_origin.null_p ()) { pp_string (pp, " (origin: "); e.m_origin.print (pp); if (model) if (tree rep = model->get_representative_tree (e.m_origin)) { pp_string (pp, " ("); dump_quoted_tree (pp, rep); pp_character (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, NULL, &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 (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 (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); if (!set_state (ec, state, origin)) return; /* 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. Return true if any states of svalue_ids within EC changed. */ bool sm_state_map::set_state (const equiv_class &ec, state_machine::state_t state, svalue_id origin) { int i; svalue_id *sid; bool any_changed = false; FOR_EACH_VEC_ELT (ec.m_vars, i, sid) any_changed |= impl_set_state (*sid, state, origin); return any_changed; } /* Set state of SID to STATE, bypassing equivalence classes. Return true if the state changed. */ bool sm_state_map::impl_set_state (svalue_id sid, state_machine::state_t state, svalue_id origin) { if (get_state (sid) == state) return false; /* Special-case state 0 as the default value. */ if (state == 0) { if (m_map.get (sid)) m_map.remove (sid); return true; } gcc_assert (!sid.null_p ()); m_map.put (sid, entry_t (state, origin)); return true; } /* 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, region_model_context *ctxt) { 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, ctxt); 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, ctxt); 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, ctxt); 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 (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 (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 (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); } else if ((*iter).second.m_origin.as_int () >= first_unused_sid.as_int ()) { /* If the origin svalue is being purged, then reset it to null. */ (*iter).second.m_origin = svalue_id::null (); } } 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)); } /* Purge state from SID (in response to a call to an unknown function). */ void sm_state_map::on_unknown_change (svalue_id sid) { impl_set_state (sid, (state_machine::state_t)0, svalue_id::null ()); } /* 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 (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.get_num_checkers ()), m_valid (true) { int num_states = ext_state.get_num_checkers (); 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 ()), m_valid (true) { 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 ()); m_valid = other.m_valid; 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); m_valid = other.m_valid; } #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), m_region_model, pp); pp_newline (pp); } } if (!m_valid) { pp_printf (pp, "invalid state"); pp_newline (pp); } } /* Dump a representation of this state to PP. If SUMMARIZE is true, print a one-line summary; if false, print a detailed multiline representation. */ 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 ()) { if (summarize) pp_space (pp); pp_printf (pp, "%s: ", ext_state.get_name (i)); smap->print (ext_state.get_sm (i), m_region_model, pp); if (!summarize) pp_newline (pp); } } if (!m_valid) { if (summarize) pp_space (pp); pp_printf (pp, "invalid state"); if (!summarize) 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 extrinsic_state &ext_state) const { gcc_assert ((unsigned)m_sm_idx < ext_state.get_num_checkers ()); const state_machine &sm = ext_state.get_sm (m_sm_idx); sm.validate (m_old_state); sm.validate (m_new_state); 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 extrinsic_state &ext_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, ext_state); } #if CHECKING_P namespace selftest { /* Implementation detail of ASSERT_DUMP_EQ. */ static void assert_dump_eq (const location &loc, const program_state &state, const extrinsic_state &ext_state, bool summarize, const char *expected) { auto_fix_quotes sentinel; pretty_printer pp; pp_format_decoder (&pp) = default_tree_printer; state.dump_to_pp (ext_state, summarize, &pp); ASSERT_STREQ_AT (loc, pp_formatted_text (&pp), expected); } /* Assert that STATE.dump_to_pp (SUMMARIZE) is EXPECTED. */ #define ASSERT_DUMP_EQ(STATE, EXT_STATE, SUMMARIZE, EXPECTED) \ SELFTEST_BEGIN_STMT \ assert_dump_eq ((SELFTEST_LOCATION), (STATE), (EXT_STATE), (SUMMARIZE), \ (EXPECTED)); \ SELFTEST_END_STMT /* 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_state::dump_to_pp works as expected. */ static void test_program_state_dumping () { /* 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); state_machine *sm = make_malloc_state_machine (NULL); const state_machine::state_t UNCHECKED_STATE = sm->get_state_by_name ("unchecked"); auto_delete_vec checkers; checkers.safe_push (sm); extrinsic_state ext_state (checkers); program_state s (ext_state); region_model *model = s.m_region_model; region_id new_rid = model->add_new_malloc_region (); svalue_id ptr_sid = model->get_or_create_ptr_svalue (ptr_type_node, new_rid); model->set_value (model->get_lvalue (p, NULL), ptr_sid, NULL); sm_state_map *smap = s.m_checker_states[0]; smap->impl_set_state (ptr_sid, UNCHECKED_STATE, svalue_id::null ()); ASSERT_EQ (smap->get_state (ptr_sid), UNCHECKED_STATE); ASSERT_DUMP_EQ (s, ext_state, false, "rmodel: r0: {kind: `root', parent: null, sval: null}\n" "|-heap: r1: {kind: `heap', parent: r0, sval: null}\n" "| `-r2: {kind: `symbolic', parent: r1, sval: null, possibly_null: true}\n" "`-globals: r3: {kind: `globals', parent: r0, sval: null, map: {`p': r4}}\n" " `-`p': r4: {kind: `primitive', parent: r3, sval: sv0, type: `void *'}\n" " |: sval: sv0: {type: `void *', &r2}\n" " |: type: `void *'\n" "svalues:\n" " sv0: {type: `void *', &r2}\n" "constraint manager:\n" " equiv classes:\n" " constraints:\n" "malloc: {sv0: unchecked (`p')}\n"); ASSERT_DUMP_EQ (s, ext_state, true, "rmodel: p: &r2 malloc: {sv0: unchecked (`p')}"); } /* Verify that program_state::dump_to_pp works for string literals. */ static void test_program_state_dumping_2 () { /* Create a program_state for a global ptr "p" that points to a string constant. */ tree p = build_global_decl ("p", ptr_type_node); tree string_cst_ptr = build_string_literal (4, "foo"); auto_delete_vec checkers; extrinsic_state ext_state (checkers); program_state s (ext_state); region_model *model = s.m_region_model; region_id p_rid = model->get_lvalue (p, NULL); svalue_id str_sid = model->get_rvalue (string_cst_ptr, NULL); model->set_value (p_rid, str_sid, NULL); ASSERT_DUMP_EQ (s, ext_state, false, "rmodel: r0: {kind: `root', parent: null, sval: null}\n" "|-globals: r1: {kind: `globals', parent: r0, sval: null, map: {`p': r2}}\n" "| `-`p': r2: {kind: `primitive', parent: r1, sval: sv3, type: `void *'}\n" "| |: sval: sv3: {type: `void *', &r4}\n" "| |: type: `void *'\n" "`-r3: {kind: `array', parent: r0, sval: sv0, type: `const char[4]', array: {[0]: r4}}\n" " |: sval: sv0: {type: `const char[4]', `\"foo\"'}\n" " |: type: `const char[4]'\n" " `-[0]: r4: {kind: `primitive', parent: r3, sval: null, type: `const char'}\n" " |: type: `const char'\n" "svalues:\n" " sv0: {type: `const char[4]', `\"foo\"'}\n" " sv1: {type: `int', `0'}\n" " sv2: {type: `const char *', &r4}\n" " sv3: {type: `void *', &r4}\n" "constraint manager:\n" " equiv classes:\n" " constraints:\n"); ASSERT_DUMP_EQ (s, ext_state, true, "rmodel: p: &\"foo\"[0]"); } /* 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); } /* Verify that program_states with different global-state in an sm-state can't be merged. */ static void test_program_state_merging_2 () { auto_delete_vec checkers; checkers.safe_push (make_signal_state_machine (NULL)); extrinsic_state ext_state (checkers); program_state s0 (ext_state); { sm_state_map *smap0 = s0.m_checker_states[0]; const state_machine::state_t TEST_STATE_0 = 0; smap0->set_global_state (TEST_STATE_0); ASSERT_EQ (smap0->get_global_state (), TEST_STATE_0); } program_state s1 (ext_state); { sm_state_map *smap1 = s1.m_checker_states[0]; const state_machine::state_t TEST_STATE_1 = 1; smap1->set_global_state (TEST_STATE_1); ASSERT_EQ (smap1->get_global_state (), TEST_STATE_1); } ASSERT_NE (s0, s1); /* They ought to not be mergeable. */ program_state merged (ext_state); ASSERT_FALSE (s0.can_merge_with_p (s1, ext_state, &merged)); } /* Run all of the selftests within this file. */ void analyzer_program_state_cc_tests () { test_sm_state_map (); test_program_state_dumping (); test_program_state_dumping_2 (); test_program_state_merging (); test_program_state_merging_2 (); } } // namespace selftest #endif /* CHECKING_P */ } // namespace ana #endif /* #if ENABLE_ANALYZER */