@@ -25,7 +25,6 @@ along with GCC; see the file COPYING3. If not see
#include "tree.h"
#include "options.h"
#include "json.h"
-#include "analyzer/call-string.h"
#include "ordered-hash-map.h"
#include "options.h"
#include "cgraph.h"
@@ -35,6 +34,9 @@ along with GCC; see the file COPYING3. If not see
#include "gimple.h"
#include "gimple-iterator.h"
#include "digraph.h"
+#include "analyzer/analyzer.h"
+#include "analyzer/analyzer-logging.h"
+#include "analyzer/call-string.h"
#include "analyzer/supergraph.h"
#if ENABLE_ANALYZER
@@ -74,45 +76,6 @@ call_string::element_t::get_callee_function () const
return m_callee->get_function ();
}
-/* call_string's copy ctor. */
-
-call_string::call_string (const call_string &other)
-: m_elements (other.m_elements.length ())
-{
- for (const call_string::element_t &e : other.m_elements)
- m_elements.quick_push (e);
-}
-
-/* call_string's assignment operator. */
-
-call_string&
-call_string::operator= (const call_string &other)
-{
- // would be much simpler if we could rely on vec<> assignment op
- m_elements.truncate (0);
- m_elements.reserve (other.m_elements.length (), true);
- call_string::element_t *e;
- int i;
- FOR_EACH_VEC_ELT (other.m_elements, i, e)
- m_elements.quick_push (*e);
- return *this;
-}
-
-/* call_string's equality operator. */
-
-bool
-call_string::operator== (const call_string &other) const
-{
- if (m_elements.length () != other.m_elements.length ())
- return false;
- call_string::element_t *e;
- int i;
- FOR_EACH_VEC_ELT (m_elements, i, e)
- if (*e != other.m_elements[i])
- return false;
- return true;
-}
-
/* Print this to PP. */
void
@@ -160,43 +123,34 @@ call_string::to_json () const
return arr;
}
-/* Generate a hash value for this call_string. */
+/* Get or create the call_string resulting from pushing the return
+ superedge for CALL_SEDGE onto the end of this call_string. */
-hashval_t
-call_string::hash () const
-{
- inchash::hash hstate;
- for (const call_string::element_t &e : m_elements)
- hstate.add_ptr (e.m_caller);
- return hstate.end ();
-}
-
-/* Push the return superedge for CALL_SEDGE onto the end of this
- call_string. */
-
-void
+const call_string *
call_string::push_call (const supergraph &sg,
- const call_superedge *call_sedge)
+ const call_superedge *call_sedge) const
{
gcc_assert (call_sedge);
const return_superedge *return_sedge = call_sedge->get_edge_for_return (sg);
gcc_assert (return_sedge);
- call_string::element_t e (return_sedge->m_dest, return_sedge->m_src);
- m_elements.safe_push (e);
+ return push_call (return_sedge->m_dest, return_sedge->m_src);
}
-void
+/* Get or create the call_string resulting from pushing the call
+ (caller, callee) onto the end of this call_string. */
+
+const call_string *
call_string::push_call (const supernode *caller,
- const supernode *callee)
+ const supernode *callee) const
{
call_string::element_t e (caller, callee);
- m_elements.safe_push (e);
-}
-call_string::element_t
-call_string::pop ()
-{
- return m_elements.pop();
+ if (const call_string **slot = m_children.get (e))
+ return *slot;
+
+ call_string *result = new call_string (*this, e);
+ m_children.put (e, result);
+ return result;
}
/* Count the number of times the top-most call site appears in the
@@ -260,6 +214,16 @@ call_string::cmp (const call_string &a,
}
}
+/* Comparator for use by vec<const call_string *>::qsort. */
+
+int
+call_string::cmp_ptr_ptr (const void *pa, const void *pb)
+{
+ const call_string *cs_a = *static_cast <const call_string * const *> (pa);
+ const call_string *cs_b = *static_cast <const call_string * const *> (pb);
+ return cmp (*cs_a, *cs_b);
+}
+
/* Return the pointer to callee of the topmost call in the stack,
or NULL if stack is empty. */
const supernode *
@@ -290,6 +254,8 @@ call_string::validate () const
return;
#endif
+ gcc_assert (m_parent || m_elements.length () == 0);
+
/* Each entry's "caller" should be the "callee" of the previous entry. */
call_string::element_t *e;
int i;
@@ -299,4 +265,68 @@ call_string::validate () const
m_elements[i - 1].get_callee_function ());
}
+/* ctor for the root/empty call_string. */
+
+call_string::call_string ()
+: m_parent (NULL), m_elements ()
+{
+}
+
+/* ctor for a child call_string. */
+
+call_string::call_string (const call_string &parent, const element_t &to_push)
+: m_parent (&parent),
+ m_elements (parent.m_elements.length () + 1)
+{
+ m_elements.splice (parent.m_elements);
+ m_elements.quick_push (to_push);
+}
+
+/* dtor for call_string: recursively delete children. */
+
+call_string::~call_string ()
+{
+ for (auto child_iter : m_children)
+ delete child_iter.second;
+}
+
+/* Log this call_string and all its descendents recursively to LOGGER,
+ using indentation and elision to highlight the hierarchy. */
+
+void
+call_string::recursive_log (logger *logger) const
+{
+ logger->start_log_line ();
+ pretty_printer *pp = logger->get_printer ();
+ for (unsigned i = 0; i < length (); i++)
+ pp_string (pp, " ");
+ if (length () > 0)
+ {
+ pp_string (pp, "[");
+ /* Elide all but the final element, since they are shared with
+ the parent call_string. */
+ for (unsigned i = 0; i < length (); i++)
+ pp_string (pp, "..., ");
+ /* Log the final element in detail. */
+ const element_t *e = &m_elements[m_elements.length () - 1];
+ pp_printf (pp, "(SN: %i -> SN: %i in %s)]",
+ e->m_callee->m_index, e->m_caller->m_index,
+ function_name (e->m_caller->m_fun));
+ }
+ else
+ pp_string (pp, "[]");
+ logger->end_log_line ();
+
+ /* Recurse into children. */
+ {
+ auto_vec<const call_string *> children (m_children.elements ());
+ for (auto iter : m_children)
+ children.safe_push (iter.second);
+ children.qsort (call_string::cmp_ptr_ptr);
+
+ for (auto iter : children)
+ iter->recursive_log (logger);
+ }
+}
+
#endif /* #if ENABLE_ANALYZER */
@@ -36,8 +36,13 @@ class return_superedge;
i.e. that we return to the same callsite that called us.
The class stores returning calls ( which may be represented by a
- returning superedge ). We do so because this is what we need to compare
- against. */
+ returning superedge ). We do so because this is what we need to compare
+ against.
+
+ Instances of call_string are consolidated by the region_model_manager,
+ which effectively owns them: it 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. */
class call_string
{
@@ -60,38 +65,31 @@ public:
/* Accessors */
function *get_caller_function () const;
function *get_callee_function () const;
-
+
const supernode *m_caller;
const supernode *m_callee;
};
- call_string () : m_elements () {}
- call_string (const call_string &other);
- call_string& operator= (const call_string &other);
-
- bool operator== (const call_string &other) const;
-
void print (pretty_printer *pp) const;
json::value *to_json () const;
- hashval_t hash () const;
-
bool empty_p () const { return m_elements.is_empty (); }
- void push_call (const supergraph &sg,
- const call_superedge *sedge);
-
- void push_call (const supernode *src,
- const supernode *dest);
+ const call_string *push_call (const supergraph &sg,
+ const call_superedge *sedge) const;
- element_t pop ();
+ const call_string *push_call (const supernode *src,
+ const supernode *dest) const;
+ const call_string *get_parent () const { return m_parent; }
int calc_recursion_depth () const;
static int cmp (const call_string &a,
const call_string &b);
+ static int cmp_ptr_ptr (const void *, const void *);
+
/* Accessors */
const supernode *get_callee_node () const;
@@ -101,11 +99,69 @@ public:
{
return m_elements[idx];
}
+ const element_t &get_top_of_stack () const
+ {
+ gcc_assert (m_elements.length () > 0);
+ return m_elements[m_elements.length () - 1];
+ }
void validate () const;
private:
+ struct hashmap_traits_t
+ {
+ typedef element_t key_type;
+ typedef const call_string *value_type;
+
+ static const bool maybe_mx = false;
+ static inline hashval_t hash (const key_type &k)
+ {
+ inchash::hash hstate;
+ hstate.add_ptr (k.m_caller);
+ hstate.add_ptr (k.m_callee);
+ return hstate.end ();
+ }
+ static inline bool equal_keys (const key_type &k1, const key_type &k2)
+ {
+ return k1 == k2;
+ }
+ template <typename T> static inline void remove (T &entry)
+ {
+ entry.m_key = element_t (NULL, NULL);
+ }
+ static const bool empty_zero_p = true;
+ template <typename T> static inline bool is_empty (const T &entry)
+ {
+ return entry.m_key.m_caller == NULL;
+ }
+ template <typename T> static inline bool is_deleted (const T &entry)
+ {
+ return entry.m_key.m_caller == reinterpret_cast<const supernode *> (1);
+ }
+ template <typename T> static inline void mark_empty (T &entry)
+ {
+ entry.m_key = element_t (NULL, NULL);
+ entry.m_value = NULL;
+ }
+ template <typename T> static inline void mark_deleted (T &entry)
+ {
+ entry.m_key.m_caller = reinterpret_cast<const supernode *> (1);
+ }
+ };
+
+ friend class region_model_manager;
+
+ DISABLE_COPY_AND_ASSIGN (call_string);
+
+ call_string ();
+ call_string (const call_string &parent, const element_t &to_push);
+ ~call_string ();
+
+ void recursive_log (logger *logger) const;
+
+ const call_string *m_parent;
auto_vec<element_t> m_elements;
+ mutable hash_map<element_t, const call_string *, hashmap_traits_t> m_children;
};
} // namespace ana
@@ -3923,10 +3923,10 @@ test_equality ()
static void
test_many_constants ()
{
- program_point point (program_point::origin ());
+ region_model_manager mgr;
+ program_point point (program_point::origin (mgr));
tree a = build_global_decl ("a", integer_type_node);
- region_model_manager mgr;
region_model model (&mgr);
auto_vec<tree> constants;
for (int i = 0; i < 20; i++)
@@ -2374,8 +2374,9 @@ exploded_graph::exploded_graph (const supergraph &sg, logger *logger,
m_functionless_stats (m_sg.num_nodes ()),
m_PK_AFTER_SUPERNODE_per_snode (m_sg.num_nodes ())
{
- m_origin = get_or_create_node (program_point::origin (),
- program_state (ext_state), NULL);
+ m_origin = get_or_create_node
+ (program_point::origin (*ext_state.get_model_manager ()),
+ program_state (ext_state), NULL);
for (int i = 0; i < m_sg.num_nodes (); i++)
m_PK_AFTER_SUPERNODE_per_snode.quick_push (i);
}
@@ -2526,7 +2527,9 @@ exploded_graph::add_function_entry (function *fun)
return NULL;
}
- program_point point = program_point::from_function_entry (m_sg, fun);
+ program_point point
+ = program_point::from_function_entry (*m_ext_state.get_model_manager (),
+ m_sg, fun);
program_state state (m_ext_state);
state.push_frame (m_ext_state, fun);
@@ -2979,7 +2982,8 @@ add_tainted_args_callback (exploded_graph *eg, tree field, tree fndecl,
gcc_assert (fun);
program_point point
- = program_point::from_function_entry (eg->get_supergraph (), fun);
+ = program_point::from_function_entry (*ext_state.get_model_manager (),
+ eg->get_supergraph (), fun);
program_state state (ext_state);
state.push_frame (ext_state, fun);
@@ -3341,7 +3345,7 @@ maybe_process_run_of_before_supernode_enodes (exploded_node *enode)
if (point_2.get_kind () == PK_BEFORE_SUPERNODE
&& point_2.get_supernode () == snode
- && point_2.get_call_string () == point.get_call_string ())
+ && &point_2.get_call_string () == &point.get_call_string ())
{
enodes.safe_push (enode_2);
m_worklist.take_next ();
@@ -4048,7 +4052,7 @@ exploded_graph::process_node (exploded_node *node)
if ((is_an_exit_block && !found_a_superedge)
&& (!point.get_call_string ().empty_p ()))
{
- const call_string cs = point.get_call_string ();
+ const call_string &cs = point.get_call_string ();
program_point next_point
= program_point::before_supernode (cs.get_caller_node (),
NULL,
@@ -4736,7 +4740,7 @@ private:
class function_call_string_cluster : public exploded_cluster
{
public:
- function_call_string_cluster (function *fun, call_string cs)
+ function_call_string_cluster (function *fun, const call_string &cs)
: m_fun (fun), m_cs (cs) {}
~function_call_string_cluster ()
@@ -4811,7 +4815,7 @@ public:
private:
function *m_fun;
- call_string m_cs;
+ const call_string &m_cs;
typedef ordered_hash_map<const supernode *, supernode_cluster *> map_t;
map_t m_map;
};
@@ -4820,14 +4824,15 @@ private:
struct function_call_string
{
- function_call_string (function *fun, call_string cs)
+ function_call_string (function *fun, const call_string *cs)
: m_fun (fun), m_cs (cs)
{
gcc_assert (fun);
+ gcc_assert (cs);
}
function *m_fun;
- call_string m_cs;
+ const call_string *m_cs;
};
} // namespace ana
@@ -4842,7 +4847,8 @@ template <>
inline hashval_t
pod_hash_traits<function_call_string>::hash (value_type v)
{
- return pointer_hash <function>::hash (v.m_fun) ^ v.m_cs.hash ();
+ return (pointer_hash <function>::hash (v.m_fun)
+ ^ pointer_hash <const call_string>::hash (v.m_cs));
}
template <>
@@ -4850,7 +4856,7 @@ inline bool
pod_hash_traits<function_call_string>::equal (const value_type &existing,
const value_type &candidate)
{
- return existing.m_fun == candidate.m_fun && existing.m_cs == candidate.m_cs;
+ return existing.m_fun == candidate.m_fun && &existing.m_cs == &candidate.m_cs;
}
template <>
inline void
@@ -4925,7 +4931,7 @@ public:
}
const call_string &cs = en->get_point ().get_call_string ();
- function_call_string key (fun, cs);
+ function_call_string key (fun, &cs);
function_call_string_cluster **slot = m_map.get (key);
if (slot)
(*slot)->add_node (en);
@@ -4939,11 +4945,6 @@ public:
}
private:
- /* This can't be an ordered_hash_map, as we can't store vec<call_string>,
- since it's not a POD; vec<>::quick_push has:
- *slot = obj;
- and the slot isn't initialized, so the assignment op dies when cleaning up
- un-inited *slot (within the truncate call). */
typedef hash_map<function_call_string, function_call_string_cluster *> map_t;
map_t m_map;
@@ -5319,7 +5320,7 @@ public:
FOR_EACH_VEC_ELT (args.m_eg->m_nodes, i, enode)
{
if (enode->get_point ().get_function () == m_fun
- && enode->get_point ().get_call_string () == *cs)
+ && &enode->get_point ().get_call_string () == cs)
num_enodes++;
}
if (num_enodes > 0)
@@ -599,65 +599,10 @@ struct per_call_string_data
: m_key (key), m_stats (num_supernodes)
{}
- const call_string m_key;
+ const call_string &m_key;
stats m_stats;
};
-/* Traits class for storing per-call_string data within
- an exploded_graph. */
-
-struct eg_call_string_hash_map_traits
-{
- typedef const call_string *key_type;
- typedef per_call_string_data *value_type;
- typedef per_call_string_data *compare_type;
-
- static inline hashval_t hash (const key_type &k)
- {
- gcc_assert (k != NULL);
- gcc_assert (k != reinterpret_cast<key_type> (1));
- return k->hash ();
- }
- static inline bool equal_keys (const key_type &k1, const key_type &k2)
- {
- gcc_assert (k1 != NULL);
- gcc_assert (k2 != NULL);
- gcc_assert (k1 != reinterpret_cast<key_type> (1));
- gcc_assert (k2 != reinterpret_cast<key_type> (1));
- if (k1 && k2)
- return *k1 == *k2;
- else
- /* Otherwise they must both be non-NULL. */
- return k1 == k2;
- }
- template <typename T>
- static inline void remove (T &)
- {
- /* empty; the nodes are handled elsewhere. */
- }
- template <typename T>
- static inline void mark_deleted (T &entry)
- {
- entry.m_key = reinterpret_cast<key_type> (1);
- }
- template <typename T>
- static inline void mark_empty (T &entry)
- {
- entry.m_key = NULL;
- }
- template <typename T>
- static inline bool is_deleted (const T &entry)
- {
- return entry.m_key == reinterpret_cast<key_type> (1);
- }
- template <typename T>
- static inline bool is_empty (const T &entry)
- {
- return entry.m_key == NULL;
- }
- static const bool empty_zero_p = false;
-};
-
/* Data about a particular function within an exploded_graph. */
struct per_function_data
@@ -791,8 +736,8 @@ private:
class exploded_graph : public digraph<eg_traits>
{
public:
- typedef hash_map <const call_string *, per_call_string_data *,
- eg_call_string_hash_map_traits> call_string_data_map_t;
+ typedef hash_map <const call_string *,
+ per_call_string_data *> call_string_data_map_t;
exploded_graph (const supergraph &sg, logger *logger,
const extrinsic_state &ext_state,
@@ -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);
@@ -174,7 +174,7 @@ public:
program_point (const function_point &fn_point,
const call_string &call_string)
: m_function_point (fn_point),
- m_call_string (call_string)
+ m_call_string (&call_string)
{
}
@@ -197,7 +197,7 @@ public:
/* Accessors. */
const function_point &get_function_point () const { return m_function_point; }
- const call_string &get_call_string () const { return m_call_string; }
+ const call_string &get_call_string () const { return *m_call_string; }
const supernode *get_supernode () const
{
@@ -242,23 +242,14 @@ public:
{
if (get_kind () == PK_ORIGIN)
return 0;
- return m_call_string.length () + 1;
+ return get_call_string ().length () + 1;
}
/* Factory functions for making various kinds of program_point. */
- static program_point origin ()
- {
- return program_point (function_point (NULL, NULL,
- 0, PK_ORIGIN),
- call_string ());
- }
-
- static program_point from_function_entry (const supergraph &sg,
- function *fun)
- {
- return program_point (function_point::from_function_entry (sg, fun),
- call_string ());
- }
+ static program_point origin (const region_model_manager &mgr);
+ static program_point from_function_entry (const region_model_manager &mgr,
+ const supergraph &sg,
+ function *fun);
static program_point before_supernode (const supernode *supernode,
const superedge *from_edge,
@@ -288,11 +279,11 @@ public:
static program_point empty ()
{
- return program_point (function_point::empty (), call_string ());
+ return program_point (function_point::empty ());
}
static program_point deleted ()
{
- return program_point (function_point::deleted (), call_string ());
+ return program_point (function_point::deleted ());
}
bool on_edge (exploded_graph &eg, const superedge *succ);
@@ -306,8 +297,14 @@ public:
program_point get_next () const;
private:
+ program_point (const function_point &fn_point)
+ : m_function_point (fn_point),
+ m_call_string (NULL)
+ {
+ }
+
function_point m_function_point;
- call_string m_call_string;
+ const call_string *m_call_string;
};
} // namespace ana
@@ -1668,12 +1668,12 @@ test_program_state_merging ()
malloc sm-state, pointing to a region on the heap. */
tree p = build_global_decl ("p", ptr_type_node);
- program_point point (program_point::origin ());
+ engine eng;
+ region_model_manager *mgr = eng.get_model_manager ();
+ program_point point (program_point::origin (*mgr));
auto_delete_vec <state_machine> checkers;
checkers.safe_push (make_malloc_state_machine (NULL));
- engine eng;
extrinsic_state ext_state (checkers, &eng);
- region_model_manager *mgr = eng.get_model_manager ();
program_state s0 (ext_state);
uncertainty_t uncertainty;
@@ -1736,10 +1736,11 @@ test_program_state_merging ()
static void
test_program_state_merging_2 ()
{
- program_point point (program_point::origin ());
+ engine eng;
+ region_model_manager *mgr = eng.get_model_manager ();
+ program_point point (program_point::origin (*mgr));
auto_delete_vec <state_machine> checkers;
checkers.safe_push (make_signal_state_machine (NULL));
- engine eng;
extrinsic_state ext_state (checkers, &eng);
const state_machine::state test_state_0 ("test state 0", 0);
@@ -68,6 +68,7 @@ namespace ana {
region_model_manager::region_model_manager (logger *logger)
: m_logger (logger),
+ m_empty_call_string (),
m_next_region_id (0),
m_root_region (alloc_region_id ()),
m_stack_region (alloc_region_id (), &m_root_region),
@@ -1748,6 +1749,8 @@ void
region_model_manager::log_stats (logger *logger, bool show_objs) const
{
LOG_SCOPE (logger);
+ logger->log ("call string consolidation");
+ m_empty_call_string.recursive_log (logger);
logger->log ("svalue consolidation");
log_uniq_map (logger, show_objs, "constant_svalue", m_constants_map);
log_uniq_map (logger, show_objs, "unknown_svalue", m_unknowns_map);
@@ -5460,9 +5460,9 @@ assert_region_models_merge (tree expr, tree val_a, tree val_b,
region_model *out_merged_model,
const svalue **out_merged_svalue)
{
- program_point point (program_point::origin ());
- test_region_model_context ctxt;
region_model_manager *mgr = out_merged_model->get_manager ();
+ program_point point (program_point::origin (*mgr));
+ test_region_model_context ctxt;
region_model model0 (mgr);
region_model model1 (mgr);
if (val_a)
@@ -5511,8 +5511,8 @@ test_state_merging ()
ptr_type_node);
DECL_CONTEXT (q) = test_fndecl;
- program_point point (program_point::origin ());
region_model_manager mgr;
+ program_point point (program_point::origin (mgr));
{
region_model model0 (&mgr);
@@ -5852,7 +5852,7 @@ test_constraint_merging ()
/* They should be mergeable; the merged constraints should
be: (0 <= x < n). */
- program_point point (program_point::origin ());
+ program_point point (program_point::origin (mgr));
region_model merged (&mgr);
ASSERT_TRUE (model0.can_merge_with_p (model1, point, &merged));
@@ -5873,12 +5873,12 @@ test_constraint_merging ()
static void
test_widening_constraints ()
{
- program_point point (program_point::origin ());
+ region_model_manager mgr;
+ program_point point (program_point::origin (mgr));
tree int_0 = build_int_cst (integer_type_node, 0);
tree int_m1 = build_int_cst (integer_type_node, -1);
tree int_1 = build_int_cst (integer_type_node, 1);
tree int_256 = build_int_cst (integer_type_node, 256);
- region_model_manager mgr;
test_region_model_context ctxt;
const svalue *int_0_sval = mgr.get_or_create_constant_svalue (int_0);
const svalue *int_1_sval = mgr.get_or_create_constant_svalue (int_1);
@@ -5988,7 +5988,8 @@ test_widening_constraints ()
static void
test_iteration_1 ()
{
- program_point point (program_point::origin ());
+ region_model_manager mgr;
+ program_point point (program_point::origin (mgr));
tree int_0 = build_int_cst (integer_type_node, 0);
tree int_1 = build_int_cst (integer_type_node, 1);
@@ -5996,7 +5997,6 @@ test_iteration_1 ()
tree int_257 = build_int_cst (integer_type_node, 257);
tree i = build_global_decl ("i", integer_type_node);
- region_model_manager mgr;
test_region_model_context ctxt;
/* model0: i: 0. */
@@ -244,6 +244,12 @@ public:
region_model_manager (logger *logger = NULL);
~region_model_manager ();
+ /* call_string consolidation. */
+ const call_string &get_empty_call_string () const
+ {
+ return m_empty_call_string;
+ }
+
/* svalue consolidation. */
const svalue *get_or_create_constant_svalue (tree cst_expr);
const svalue *get_or_create_int_cst (tree type, poly_int64);
@@ -381,6 +387,8 @@ private:
logger *m_logger;
+ const call_string m_empty_call_string;
+
unsigned m_next_region_id;
root_region m_root_region;
stack_region m_stack_region;
@@ -266,11 +266,13 @@ public:
function *handler_fun = DECL_STRUCT_FUNCTION (m_fndecl);
if (!handler_fun)
return;
+ const extrinsic_state &ext_state = eg->get_ext_state ();
program_point entering_handler
- = program_point::from_function_entry (eg->get_supergraph (),
+ = program_point::from_function_entry (*ext_state.get_model_manager (),
+ eg->get_supergraph (),
handler_fun);
- program_state state_entering_handler (eg->get_ext_state ());
+ program_state state_entering_handler (ext_state);
update_model_for_signal_handler (state_entering_handler.m_region_model,
handler_fun);
state_entering_handler.m_checker_states[sm_idx]->set_global_state
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). Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as r13-1250-gbb8e93eb1acae3. 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<function_call_string>::hash): Use pointer_hash for m_cs. (pod_hash_traits<function_call_string>::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 <dmalcolm@redhat.com> --- gcc/analyzer/call-string.cc | 160 ++++++++++++++++----------- gcc/analyzer/call-string.h | 90 ++++++++++++--- gcc/analyzer/constraint-manager.cc | 4 +- gcc/analyzer/engine.cc | 39 +++---- gcc/analyzer/exploded-graph.h | 61 +--------- gcc/analyzer/program-point.cc | 63 +++++++---- gcc/analyzer/program-point.h | 35 +++--- gcc/analyzer/program-state.cc | 11 +- gcc/analyzer/region-model-manager.cc | 3 + gcc/analyzer/region-model.cc | 16 +-- gcc/analyzer/region-model.h | 8 ++ gcc/analyzer/sm-signal.cc | 6 +- 12 files changed, 282 insertions(+), 214 deletions(-)