From bb8e93eb1acae30a5fbe7e13149493ce4ccd301a Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Fri, 24 Jun 2022 13:44:48 -0400 Subject: analyzer: consolidate call_string instances ana::call_string is a wrapper around an auto_vec of callsites, leading to non-trivial copying when copying around call_string instances, e.g. in ana::program_point. This patch consolidates call_string instances within the region_model_manager: it now owns the root/empty call_string, and each call_string instance tracks its children, lazily creating them on demand, so that the call_string instances form a tree-like hierarchy in memory. Doing this requires passing the region_model_manager to the various program_point factory methods, so that they can get at the root call_string. Instances of call_string become immutable (apart from their internal cache for looking up their children); operations that previously modified them now return the call_string for the result of the operation. I wasn't able to observe any performance impact of this, but it simplifies call_string and program_point management, and thus I hope will make it easier to improve call summarization. In particular, region_model_manager::log_stats will now print a hierarchical dump of all the call_string instances used in the analysis (in -fdump-analyzer and -fdump-analyzer-stderr). gcc/analyzer/ChangeLog: * call-string.cc: Add includes of "analyzer/analyzer.h" and "analyzer/analyzer-logging.h". (call_string::call_string): Delete copy ctor. (call_string::operator=): Delete. (call_string::operator==): Delete. (call_string::hash): Delete. (call_string::push_call): Make const, returning the resulting call_string. (call_string::pop): Delete. (call_string::cmp_ptr_ptr): New. (call_string::validate): Assert that m_parent is non-NULL, or m_elements is empty. (call_string::call_string): Move default ctor here from call-string.h and reimplement. Add ctor taking a parent and an element. (call_string::~call_string): New. (call_string::recursive_log): New. * call-string.h (call_string::call_string): Move default ctor's defn to call-string.cc. Delete copy ctor. Add ctor taking a parent and an element. (call_string::operator=): Delete. (call_string::operator==): Delete. (call_string::hash): Delete. (call_string::push_call): Make const, returning the resulting call_string. (call_string::pop): Delete decl. (call_string::get_parent): New. (call_string::cmp_ptr_ptr): New decl. (call_string::get_top_of_stack): New. (struct call_string::hashmap_traits_t): New. (class call_string): Add friend class region_model_manager. Add DISABLE_COPY_AND_ASSIGN. (call_string::~call_string): New decl. (call_string::recursive_log): New decl. (call_string::m_parent): New field. (call_string::m_children): New field. * constraint-manager.cc (selftest::test_many_constants): Pass model manager to program_point::origin. * engine.cc (exploded_graph::exploded_graph): Likewise. (exploded_graph::add_function_entry): Likewise for program_point::from_function_entry. (add_tainted_args_callback): Likewise. (exploded_graph::maybe_process_run_of_before_supernode_enodes): Update for change to program_point.get_call_string. (exploded_graph::process_node): Likewise. (class function_call_string_cluster): Convert m_cs from a call_string to a const call_string &. (struct function_call_string): Likewise. (pod_hash_traits::hash): Use pointer_hash for m_cs. (pod_hash_traits::equal): Update for change to m_cs. (root_cluster::add_node): Update for change to function_call_string. (viz_callgraph_node::dump_dot): Update for change to call_string. * exploded-graph.h (per_call_string_data::m_key): Convert to a reference. (struct eg_call_string_hash_map_traits): Delete. (exploded_graph::call_string_data_map_t): Remove traits class. * program-point.cc: Move include of "analyzer/call-string.h" to after "analyzer/analyzer-logging.h". (program_point::print): Update for conversion of m_call_string to a pointer. (program_point::to_json): Likewise. (program_point::push_to_call_stack): Update for immutability of call strings. (program_point::pop_from_call_stack): Likewise. (program_point::hash): Use pointer hashing for m_call_string. (program_point::get_function_at_depth): Update for change to m_call_string. (program_point::validate): Update for changes to call_string. (program_point::on_edge): Likewise. (program_point::origin): Move here from call-string.h. Add region_model_manager param and use it to get empty call string. (program_point::from_function_entry): Likewise. (selftest::test_function_point_ordering): Likewise. (selftest::test_function_point_ordering): Likewise. * program-point.h (program_point::program_point): Update for change to m_call_string. (program_point::get_call_string): Likewise. (program_point::get_stack_depth): Likewise. (program_point::origin): Add region_model_manager param, and move defn to call-string.cc. (program_point::from_function_entry): Likewise. (program_point::empty): Drop call_string. (program_point::deleted): Likewise. (program_point::program_point): New private ctor. (program_point::m_call_string): Convert from call_string to const call_string *. * program-state.cc (selftest::test_program_state_merging): Update for call_string changes. (selftest::test_program_state_merging_2): Likewise. * region-model-manager.cc (region_model_manager::region_model_manager): Construct m_empty_call_string. (region_model_manager::log_stats): Log the call strings. * region-model.cc (assert_region_models_merge): Pass the region_model_manager when creating program_point instances. (selftest::test_state_merging): Likewise. (selftest::test_constraint_merging): Likewise. (selftest::test_widening_constraints): Likewise. (selftest::test_iteration_1): Likewise. * region-model.h (region_model_manager::get_empty_call_string): New. (region_model_manager::m_empty_call_string): New. * sm-signal.cc (register_signal_handler::impl_transition): Update for changes to call_string. Signed-off-by: David Malcolm --- gcc/analyzer/program-point.cc | 63 ++++++++++++++++++++++++++++++------------- 1 file changed, 44 insertions(+), 19 deletions(-) (limited to 'gcc/analyzer/program-point.cc') diff --git a/gcc/analyzer/program-point.cc b/gcc/analyzer/program-point.cc index 8fa7066..6c296d5 100644 --- a/gcc/analyzer/program-point.cc +++ b/gcc/analyzer/program-point.cc @@ -25,7 +25,6 @@ along with GCC; see the file COPYING3. If not see #include "gimple-pretty-print.h" #include "gcc-rich-location.h" #include "json.h" -#include "analyzer/call-string.h" #include "ordered-hash-map.h" #include "options.h" #include "cgraph.h" @@ -37,6 +36,7 @@ along with GCC; see the file COPYING3. If not see #include "digraph.h" #include "analyzer/analyzer.h" #include "analyzer/analyzer-logging.h" +#include "analyzer/call-string.h" #include "analyzer/supergraph.h" #include "analyzer/program-point.h" #include "sbitmap.h" @@ -290,7 +290,7 @@ void program_point::print (pretty_printer *pp, const format &f) const { pp_string (pp, "callstring: "); - m_call_string.print (pp); + m_call_string->print (pp); f.spacer (pp); m_function_point.print (pp, f); @@ -340,7 +340,7 @@ program_point::to_json () const break; } - point_obj->set ("call_string", m_call_string.to_json ()); + point_obj->set ("call_string", m_call_string->to_json ()); return point_obj; } @@ -353,14 +353,15 @@ void program_point::push_to_call_stack (const supernode *caller, const supernode *callee) { - m_call_string.push_call (callee, caller); + m_call_string = m_call_string->push_call (callee, caller); } /* Pop the topmost call from the current callstack. */ void program_point::pop_from_call_stack () { - m_call_string.pop (); + m_call_string = m_call_string->get_parent (); + gcc_assert (m_call_string); } /* Generate a hash value for this program_point. */ @@ -370,7 +371,7 @@ program_point::hash () const { inchash::hash hstate; hstate.merge_hash (m_function_point.hash ()); - hstate.merge_hash (m_call_string.hash ()); + hstate.add_ptr (m_call_string); return hstate.end (); } @@ -379,11 +380,11 @@ program_point::hash () const function * program_point::get_function_at_depth (unsigned depth) const { - gcc_assert (depth <= m_call_string.length ()); - if (depth == m_call_string.length ()) + gcc_assert (depth <= m_call_string->length ()); + if (depth == m_call_string->length ()) return m_function_point.get_function (); else - return m_call_string[depth].get_caller_function (); + return get_call_string ()[depth].get_caller_function (); } /* Assert that this object is sane. */ @@ -396,12 +397,13 @@ program_point::validate () const return; #endif - m_call_string.validate (); + m_call_string->validate (); /* The "callee" of the final entry in the callstring should be the function of the m_function_point. */ - if (m_call_string.length () > 0) - gcc_assert (m_call_string[m_call_string.length () - 1].get_callee_function () - == get_function ()); + if (m_call_string->length () > 0) + gcc_assert + ((*m_call_string)[m_call_string->length () - 1].get_callee_function () + == get_function ()); } /* Check to see if SUCC is a valid edge to take (ensuring that we have @@ -444,14 +446,15 @@ program_point::on_edge (exploded_graph &eg, } /* Add the callsite to the call string. */ - m_call_string.push_call (eg.get_supergraph (), call_sedge); + m_call_string = m_call_string->push_call (eg.get_supergraph (), + call_sedge); /* Impose a maximum recursion depth and don't analyze paths that exceed it further. This is something of a blunt workaround, but it only applies to recursion (and mutual recursion), not to general call stacks. */ - if (m_call_string.calc_recursion_depth () + if (m_call_string->calc_recursion_depth () > param_analyzer_max_recursion_depth) { if (logger) @@ -465,13 +468,15 @@ program_point::on_edge (exploded_graph &eg, case SUPEREDGE_RETURN: { /* Require that we return to the call site in the call string. */ - if (m_call_string.empty_p ()) + if (m_call_string->empty_p ()) { if (logger) logger->log ("rejecting return edge: empty call string"); return false; } - const call_string::element_t top_of_stack = m_call_string.pop (); + const call_string::element_t &top_of_stack + = m_call_string->get_top_of_stack (); + m_call_string = m_call_string->get_parent (); call_string::element_t current_call_string_element (succ->m_dest, succ->m_src); if (top_of_stack != current_call_string_element) @@ -669,6 +674,25 @@ function_point::get_next () const } } +/* class program_point. */ + +program_point +program_point::origin (const region_model_manager &mgr) +{ + return program_point (function_point (NULL, NULL, + 0, PK_ORIGIN), + mgr.get_empty_call_string ()); +} + +program_point +program_point::from_function_entry (const region_model_manager &mgr, + const supergraph &sg, + function *fun) +{ + return program_point (function_point::from_function_entry (sg, fun), + mgr.get_empty_call_string ()); +} + /* For those program points for which there is a uniquely-defined successor, return it. */ @@ -721,7 +745,6 @@ static void test_function_point_ordering () { const supernode *snode = NULL; - const call_string call_string; /* Populate an array with various points within the same snode, in order. */ @@ -756,9 +779,11 @@ test_function_point_ordering () static void test_program_point_equality () { + region_model_manager mgr; + const supernode *snode = NULL; - const call_string cs; + const call_string &cs = mgr.get_empty_call_string (); program_point a = program_point::before_supernode (snode, NULL, cs); -- cgit v1.1