#include <exploded-graph.h>

Inheritance diagram for ana::exploded_graph:

[legend]

Collaboration diagram for ana::exploded_graph:

[legend]

Public Types
typedef hash_map< const call_string , per_call_string_data >	call_string_data_map_t
typedef eg_traits::node_t	node_t
typedef eg_traits::edge_t	edge_t
typedef eg_traits::dump_args_t	dump_args_t
typedef eg_traits::cluster_t	cluster_t

Public Member Functions
	exploded_graph (const supergraph &sg, logger logger, const extrinsic_state &ext_state, const state_purge_map purge_map, const analysis_plan &plan, int verbosity)
	~exploded_graph ()
logger *	get_logger () const
const supergraph &	get_supergraph () const
const extrinsic_state &	get_ext_state () const
engine *	get_engine () const
const state_purge_map *	get_purge_map () const
const analysis_plan &	get_analysis_plan () const
exploded_node *	get_origin () const
exploded_node *	add_function_entry (const function &fun)
void	build_initial_worklist ()
void	process_worklist ()
bool	maybe_process_run_of_before_supernode_enodes (exploded_node *node)
void	process_node (exploded_node *node)
bool	maybe_create_dynamic_call (const gcall &call, tree fn_decl, exploded_node node, program_state next_state, program_point &next_point, uncertainty_t uncertainty, logger *logger)
exploded_node *	get_or_create_node (const program_point &point, const program_state &state, exploded_node *enode_for_diag, bool add_to_worklist=true)
exploded_edge *	add_edge (exploded_node src, exploded_node dest, const superedge *sedge, bool could_do_work, std::unique_ptr< custom_edge_info > custom=NULL)
per_program_point_data *	get_or_create_per_program_point_data (const program_point &)
per_program_point_data *	get_per_program_point_data (const program_point &) const
per_call_string_data *	get_or_create_per_call_string_data (const call_string &)
per_function_data *	get_or_create_per_function_data (function *)
per_function_data *	get_per_function_data (function *) const
void	save_diagnostic (const state_machine &sm, const exploded_node enode, const supernode node, const gimple stmt, stmt_finder finder, tree var, state_machine::state_t state, pending_diagnostic *d)
diagnostic_manager &	get_diagnostic_manager ()
const diagnostic_manager &	get_diagnostic_manager () const
stats *	get_global_stats ()
stats *	get_or_create_function_stats (function *fn)
void	log_stats () const
void	dump_stats (FILE *) const
void	dump_states_for_supernode (FILE , const supernode snode) const
void	dump_exploded_nodes () const
std::unique_ptr< json::object >	to_json () const
exploded_node *	get_node_by_index (int idx) const
const call_string_data_map_t *	get_per_call_string_data () const
int	get_scc_id (const supernode &node) const
void	on_escaped_function (tree fndecl)
void	unwind_from_exception (exploded_node &enode, const gimple stmt, region_model_context ctxt)
void	detect_infinite_loops ()
void	detect_infinite_recursion (exploded_node *enode)
exploded_node *	find_previous_entry_to (function top_of_stack_fun, exploded_node enode) const
void	dump_dot_to_pp (pretty_printer pp, cluster_t root_cluster, const dump_args_t &args) const
void	dump_dot_to_file (FILE fp, cluster_t root_cluster, const dump_args_t &args) const
void	dump_dot (const char path, cluster_t root_cluster, const dump_args_t &args) const
void	add_node (node_t *node)
void	add_edge (edge_t *edge)

Data Fields
auto_delete_vec< node_t >	m_nodes
auto_delete_vec< edge_t >	m_edges

Private Types
typedef hash_map< const point_and_state , exploded_node , eg_hash_map_traits >	map_t
typedef hash_map< const program_point , per_program_point_data , eg_point_hash_map_traits >	point_map_t
typedef hash_map< function , per_function_data >	per_function_data_t
typedef ordered_hash_map< function , stats >	function_stat_map_t

Private Member Functions
void	print_bar_charts (pretty_printer *pp) const
	DISABLE_COPY_AND_ASSIGN (exploded_graph)

Private Attributes
const supergraph &	m_sg
log_user	m_logger
map_t	m_point_and_state_to_node
point_map_t	m_per_point_data
worklist	m_worklist
exploded_node *	m_origin
const extrinsic_state &	m_ext_state
const state_purge_map *const	m_purge_map
const analysis_plan &	m_plan
per_function_data_t	m_per_function_data
diagnostic_manager	m_diagnostic_manager
stats	m_global_stats
function_stat_map_t	m_per_function_stats
stats	m_functionless_stats
call_string_data_map_t	m_per_call_string_data
auto_vec< int >	m_PK_AFTER_SUPERNODE_per_snode
hash_set< function * >	m_functions_with_enodes

Detailed Description

An exploded_graph is a directed graph of unique <point, state> pairs.
It also has a worklist of nodes that are waiting for their successors
to be added to the graph.

Member Typedef Documentation

◆ call_string_data_map_t

typedef hash_map<const call_string *, per_call_string_data *> ana::exploded_graph::call_string_data_map_t

◆ cluster_t

typedef eg_traits::cluster_t digraph< eg_traits >::cluster_t

inherited

◆ dump_args_t

typedef eg_traits::dump_args_t digraph< eg_traits >::dump_args_t

inherited

◆ edge_t

typedef eg_traits::edge_t digraph< eg_traits >::edge_t

inherited

◆ function_stat_map_t

typedef ordered_hash_map<function *, stats *> ana::exploded_graph::function_stat_map_t

private

◆ map_t

typedef hash_map<const point_and_state *, exploded_node *, eg_hash_map_traits> ana::exploded_graph::map_t

private

◆ node_t

typedef eg_traits::node_t digraph< eg_traits >::node_t

inherited

◆ per_function_data_t

typedef hash_map<function *, per_function_data *> ana::exploded_graph::per_function_data_t

private

◆ point_map_t

typedef hash_map<const program_point *, per_program_point_data *, eg_point_hash_map_traits> ana::exploded_graph::point_map_t

private

Constructor & Destructor Documentation

◆ exploded_graph()

ana::exploded_graph::exploded_graph	(	const supergraph &	sg,
		logger *	logger,
		const extrinsic_state &	ext_state,
		const state_purge_map *	purge_map,
		const analysis_plan &	plan,
		int	verbosity )

Referenced by DISABLE_COPY_AND_ASSIGN().

◆ ~exploded_graph()

ana::exploded_graph::~exploded_graph ( )

Member Function Documentation

◆ add_edge() [1/2]

exploded_edge * ana::exploded_graph::add_edge	(	exploded_node *	src,
		exploded_node *	dest,
		const superedge *	sedge,
		bool	could_do_work,
		std::unique_ptr< custom_edge_info >	custom = NULL )

References ana::custom, and NULL.

◆ add_edge() [2/2]

void digraph< eg_traits >::add_edge ( edge_t * edge )

inlineinherited

Add EDGE to this digraph, and to the preds/succs of its endpoints.
Take ownership of EDGE.

◆ add_function_entry()

exploded_node * ana::exploded_graph::add_function_entry ( const function & fun )

◆ add_node()

void digraph< eg_traits >::add_node ( node_t * node )

inlineinherited


Add NODE to this DIGRAPH, taking ownership.

◆ build_initial_worklist()

void ana::exploded_graph::build_initial_worklist ( )

◆ detect_infinite_loops()

void exploded_graph::detect_infinite_loops ( )


Implementation of -Wanalyzer-infinite-loop.

References hash_set< KeyId, Lazy, Traits >::add(), ana::diagnostic_manager::add_diagnostic(), hash_set< KeyId, Lazy, Traits >::contains(), hash_set< KeyId, Lazy, Traits >::elements(), gcc_assert, get_diagnostic_manager(), get_logger(), ana::logger::log(), LOG_FUNC, digraph< eg_traits >::m_nodes, starts_infinite_loop_p(), and UNKNOWN_LOCATION.

◆ detect_infinite_recursion()

void exploded_graph::detect_infinite_recursion ( exploded_node * enode )

Implementation of -Wanalyzer-infinite-recursion.

Called when adding ENODE to the graph, after adding its first in-edge.

For function entrypoints, see if recursion has occurred, and, if so,
check if the state of memory changed between the recursion levels,
which would suggest some kind of decreasing variant that leads to
termination.

For recursive calls where the state of memory is effectively unchanged
between recursion levels, warn with -Wanalyzer-infinite-recursion.

References ana::diagnostic_manager::add_diagnostic(), ana::call_string::count_occurrences_of_function(), function::decl, find_previous_entry_to(), gcc_assert, ana::program_point::get_call_string(), get_diagnostic_manager(), ana::exploded_node::get_function(), get_logger(), ana::exploded_node::get_point(), ana::exploded_node::get_supernode(), ana::call_string::get_top_of_stack(), is_entrypoint_p(), ana::logger::log(), ana::call_string::element_t::m_caller, ana::exploded_node::m_index, ana::supernode::m_returning_call, and sufficiently_different_p().

◆ DISABLE_COPY_AND_ASSIGN()

ana::exploded_graph::DISABLE_COPY_AND_ASSIGN ( exploded_graph )

private

References exploded_graph().

◆ dump_dot()

void digraph< eg_traits >::dump_dot	(	const char *	path,
		cluster_t *	root_cluster,
		const dump_args_t &	args ) const

inlineinherited

Write .dot information for this graph to a file at PATH, passing ARGS
to the nodes and edges.
If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters.

References path.

◆ dump_dot_to_file()

void digraph< eg_traits >::dump_dot_to_file	(	FILE *	fp,
		cluster_t *	root_cluster,
		const dump_args_t &	args ) const

inlineinherited

Write .dot information for this graph to FP, passing ARGS to the nodes
and edges.
If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters.

◆ dump_dot_to_pp()

void digraph< eg_traits >::dump_dot_to_pp	(	pretty_printer *	pp,
		cluster_t *	root_cluster,
		const dump_args_t &	args ) const

inlineinherited

Write .dot information for this graph to PP, passing ARGS to the nodes
and edges.
If ROOT_CLUSTER is non-NULL, use it to organize the nodes into clusters.

◆ dump_exploded_nodes()

void ana::exploded_graph::dump_exploded_nodes ( ) const

◆ dump_states_for_supernode()

void ana::exploded_graph::dump_states_for_supernode	(	FILE *	,
		const supernode *	snode ) const

◆ dump_stats()

void ana::exploded_graph::dump_stats ( FILE * ) const

◆ find_previous_entry_to()

exploded_node * exploded_graph::find_previous_entry_to	(	function *	top_of_stack_fun,
		exploded_node *	enode ) const

Walk backwards through the eg, looking for the first
enode we find that's also the entrypoint of the same function.

References ana::exploded_node::get_function(), is_entrypoint_p(), ana::worklist::length(), dnode< GraphTraits >::m_preds, NULL, and visited.

Referenced by detect_infinite_recursion().

◆ get_analysis_plan()

const analysis_plan & ana::exploded_graph::get_analysis_plan ( ) const

inline

References m_plan.

◆ get_diagnostic_manager() [1/2]

diagnostic_manager & ana::exploded_graph::get_diagnostic_manager ( )

inline

References m_diagnostic_manager.

Referenced by detect_infinite_loops(), and detect_infinite_recursion().

◆ get_diagnostic_manager() [2/2]

const diagnostic_manager & ana::exploded_graph::get_diagnostic_manager ( ) const

inline

References m_diagnostic_manager.

◆ get_engine()

engine * ana::exploded_graph::get_engine ( ) const

inline

References m_ext_state.

◆ get_ext_state()

const extrinsic_state & ana::exploded_graph::get_ext_state ( ) const

inline

References m_ext_state.

◆ get_global_stats()

stats * ana::exploded_graph::get_global_stats ( )

inline

References m_global_stats.

◆ get_logger()

logger * ana::exploded_graph::get_logger ( ) const

inline

References m_logger.

Referenced by detect_infinite_loops(), and detect_infinite_recursion().

◆ get_node_by_index()

exploded_node * ana::exploded_graph::get_node_by_index ( int idx ) const

◆ get_or_create_function_stats()

stats * ana::exploded_graph::get_or_create_function_stats ( function * fn )

◆ get_or_create_node()

exploded_node * ana::exploded_graph::get_or_create_node	(	const program_point &	point,
		const program_state &	state,
		exploded_node *	enode_for_diag,
		bool	add_to_worklist = true )

References add_to_worklist().

◆ get_or_create_per_call_string_data()

per_call_string_data * ana::exploded_graph::get_or_create_per_call_string_data ( const call_string & )

◆ get_or_create_per_function_data()

per_function_data * ana::exploded_graph::get_or_create_per_function_data ( function * )

◆ get_or_create_per_program_point_data()

per_program_point_data * ana::exploded_graph::get_or_create_per_program_point_data ( const program_point & )

◆ get_origin()

exploded_node * ana::exploded_graph::get_origin ( ) const

inline

References m_origin.

◆ get_per_call_string_data()

const call_string_data_map_t * ana::exploded_graph::get_per_call_string_data ( ) const

inline

References m_per_call_string_data.

◆ get_per_function_data()

per_function_data * ana::exploded_graph::get_per_function_data ( function * ) const

◆ get_per_program_point_data()

per_program_point_data * ana::exploded_graph::get_per_program_point_data ( const program_point & ) const

◆ get_purge_map()

const state_purge_map * ana::exploded_graph::get_purge_map ( ) const

inline

References m_purge_map.

◆ get_scc_id()

int ana::exploded_graph::get_scc_id ( const supernode & node ) const

inline

References m_worklist.

◆ get_supergraph()

const supergraph & ana::exploded_graph::get_supergraph ( ) const

inline

References m_sg.

Referenced by starts_infinite_loop_p().

◆ log_stats()

void ana::exploded_graph::log_stats ( ) const

◆ maybe_create_dynamic_call()

bool ana::exploded_graph::maybe_create_dynamic_call	(	const gcall &	call,
		tree	fn_decl,
		exploded_node *	node,
		program_state	next_state,
		program_point &	next_point,
		uncertainty_t *	uncertainty,
		logger *	logger )

◆ maybe_process_run_of_before_supernode_enodes()

bool ana::exploded_graph::maybe_process_run_of_before_supernode_enodes ( exploded_node * node )

◆ on_escaped_function()

void ana::exploded_graph::on_escaped_function ( tree fndecl )

◆ print_bar_charts()

void ana::exploded_graph::print_bar_charts ( pretty_printer * pp ) const

private

◆ process_node()

void ana::exploded_graph::process_node ( exploded_node * node )

◆ process_worklist()

void ana::exploded_graph::process_worklist ( )

◆ save_diagnostic()

void ana::exploded_graph::save_diagnostic	(	const state_machine &	sm,
		const exploded_node *	enode,
		const supernode *	node,
		const gimple *	stmt,
		stmt_finder *	finder,
		tree	var,
		state_machine::state_t	state,
		pending_diagnostic *	d )

References ana::stmt.

◆ to_json()

std::unique_ptr< json::object > ana::exploded_graph::to_json ( ) const

◆ unwind_from_exception()

void ana::exploded_graph::unwind_from_exception	(	exploded_node &	enode,
		const gimple *	stmt,
		region_model_context *	ctxt )

References ana::stmt.

Field Documentation

◆ m_diagnostic_manager

diagnostic_manager ana::exploded_graph::m_diagnostic_manager

private

Referenced by get_diagnostic_manager(), and get_diagnostic_manager().

◆ m_edges

auto_delete_vec<edge_t> digraph< eg_traits >::m_edges

inherited

◆ m_ext_state

const extrinsic_state& ana::exploded_graph::m_ext_state

private

Referenced by get_engine(), and get_ext_state().

◆ m_functionless_stats

stats ana::exploded_graph::m_functionless_stats

private

◆ m_functions_with_enodes

hash_set<function *> ana::exploded_graph::m_functions_with_enodes

private

◆ m_global_stats

stats ana::exploded_graph::m_global_stats

private

Referenced by get_global_stats().

◆ m_logger

log_user ana::exploded_graph::m_logger

private

Referenced by get_logger().

◆ m_nodes

auto_delete_vec<node_t> digraph< eg_traits >::m_nodes

inherited

Referenced by ana::exploded_graph::detect_infinite_loops().

◆ m_origin

exploded_node* ana::exploded_graph::m_origin

private

Referenced by get_origin().

◆ m_per_call_string_data

call_string_data_map_t ana::exploded_graph::m_per_call_string_data

private

Referenced by get_per_call_string_data().

◆ m_per_function_data

per_function_data_t ana::exploded_graph::m_per_function_data

private

◆ m_per_function_stats

function_stat_map_t ana::exploded_graph::m_per_function_stats

private

◆ m_per_point_data

point_map_t ana::exploded_graph::m_per_point_data

private

◆ m_PK_AFTER_SUPERNODE_per_snode

auto_vec<int> ana::exploded_graph::m_PK_AFTER_SUPERNODE_per_snode

private

◆ m_plan

const analysis_plan& ana::exploded_graph::m_plan

private

Referenced by get_analysis_plan().

◆ m_point_and_state_to_node

map_t ana::exploded_graph::m_point_and_state_to_node

private

◆ m_purge_map

const state_purge_map* const ana::exploded_graph::m_purge_map

private

Referenced by get_purge_map().

◆ m_sg

const supergraph& ana::exploded_graph::m_sg

private

Referenced by get_supergraph().

◆ m_worklist

worklist ana::exploded_graph::m_worklist

private

Referenced by get_scc_id().

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Data Fields

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ call_string_data_map_t

◆ cluster_t

◆ dump_args_t

◆ edge_t

◆ function_stat_map_t

◆ map_t

◆ node_t

◆ per_function_data_t

◆ point_map_t

Constructor & Destructor Documentation

◆ exploded_graph()

◆ ~exploded_graph()

Member Function Documentation

◆ add_edge() [1/2]

◆ add_edge() [2/2]

◆ add_function_entry()

◆ add_node()

◆ build_initial_worklist()

◆ detect_infinite_loops()

◆ detect_infinite_recursion()

◆ DISABLE_COPY_AND_ASSIGN()

◆ dump_dot()

◆ dump_dot_to_file()

◆ dump_dot_to_pp()

◆ dump_exploded_nodes()

◆ dump_states_for_supernode()

◆ dump_stats()

◆ find_previous_entry_to()

◆ get_analysis_plan()

◆ get_diagnostic_manager() [1/2]

◆ get_diagnostic_manager() [2/2]

◆ get_engine()

◆ get_ext_state()

◆ get_global_stats()

◆ get_logger()

◆ get_node_by_index()

◆ get_or_create_function_stats()

◆ get_or_create_node()

◆ get_or_create_per_call_string_data()

◆ get_or_create_per_function_data()

◆ get_or_create_per_program_point_data()

◆ get_origin()

◆ get_per_call_string_data()

◆ get_per_function_data()

◆ get_per_program_point_data()

◆ get_purge_map()

◆ get_scc_id()

◆ get_supergraph()

◆ log_stats()

◆ maybe_create_dynamic_call()

◆ maybe_process_run_of_before_supernode_enodes()

◆ on_escaped_function()

◆ print_bar_charts()

◆ process_node()

◆ process_worklist()

◆ save_diagnostic()

◆ to_json()

◆ unwind_from_exception()

Field Documentation

◆ m_diagnostic_manager

◆ m_edges

◆ m_ext_state

◆ m_functionless_stats

◆ m_functions_with_enodes

◆ m_global_stats

◆ m_logger

◆ m_nodes

◆ m_origin

◆ m_per_call_string_data

◆ m_per_function_data

◆ m_per_function_stats

◆ m_per_point_data