#include <loops.hpp>

Collaboration diagram for Loops:

Public Member Functions
	Loops (const FunctionBehaviorRef FB, const ParameterConstRef parameter)
	The constructor builds the loop forest for the given method. More...

size_t	NumLoops () const
	Returns the number of loops. More...

const std::list< LoopConstRef > &	GetList () const
	Returns the list of loops (const) More...

const std::list< LoopRef > &	GetModifiableList () const
	Return the list of loops. More...

const LoopConstRef	CGetLoop (unsigned int id) const
	Returns a loop given the id. More...

const LoopRef	GetLoop (unsigned int id)
	Returns a loop given the id. More...

void	WriteDot (const std::string &file_name) const
	Write dot files representing the loop forest. More...

Private Types
using	vertex_pair = std::pair< vertex, vertex >

Private Member Functions
bool	is_edge_in_list (CustomUnorderedSet< vertex_pair > &l, vertex source, vertex target)

	Loops ()=delete

void	DetectLoops ()
	Computes the loops of the control flow graph. More...

void	DetectReducibleLoop (const BBGraphRef djg, CustomOrderedSet< vertex > &visited, LoopRef loop, vertex node, vertex header)
	Reducible loop construction. More...

void	DetectIrreducibleLoop (const BBGraphRef djg, unsigned int min_level, unsigned int max_level, std::vector< std::list< vertex >> &level_vertices_rel)

void	tarjan_scc (const BBGraphRef djg, vertex v, CustomUnorderedMap< vertex, unsigned int > &dfs_order, CustomUnorderedMap< vertex, unsigned int > &lowlink, std::list< vertex > &s, CustomOrderedSet< vertex > &u, unsigned int &max_dfs)

bool	stack_contains (std::list< vertex > stack, vertex v)

void	BuildZeroLoop ()
	Creates Loop zero data structure. More...

void	computeDepth (const LoopConstRef loop)
	Sets depth for each loop in the forest starting from loop. More...

Private Attributes
const FunctionBehaviorRef	FB
	The function behavior. More...

const ParameterConstRef	Param
	class containing all the parameters More...

int	debug_level
	Debug level. More...

CustomUnorderedMap< vertex, LoopRef >	block_to_loop
	Maps between basic block and loop to which it belongs. More...

std::list< LoopRef >	modifiable_loops_list
	List of found loops. More...

std::list< LoopConstRef >	const_loops_list

Detailed Description

Definition at line 90 of file loops.hpp.

Member Typedef Documentation

◆ vertex_pair

using Loops::vertex_pair = std::pair<vertex, vertex>

private

Definition at line 109 of file loops.hpp.

Constructor & Destructor Documentation

◆ Loops() [1/2]

Loops::Loops ( )

privatedelete

◆ Loops() [2/2]

Loops::Loops	(	const FunctionBehaviorRef	FB,
		const ParameterConstRef	parameter
	)

The constructor builds the loop forest for the given method.

Parameters

FB	is the function behavior of the control flow graph to be analyzed
parameter	is the set of input parameters

Detect loops

Build Zero Loop

compute depth

compute landing pads

Definition at line 184 of file loops.cpp.

References BuildZeroLoop(), computeDepth(), DetectLoops(), GetLoop(), and modifiable_loops_list.

Here is the call graph for this function:

Member Function Documentation

◆ BuildZeroLoop()

void Loops::BuildZeroLoop ( )

private

Creates Loop zero data structure.

Putting all the basic blocks in blocks

Definition at line 754 of file loops.cpp.

References FunctionBehavior::BB, Loop::blocks, BBGraph::CGetBBGraphInfo(), Loop::children, const_loops_list, FB, Loop::is_innermost_loop, and modifiable_loops_list.

Referenced by Loops().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ CGetLoop()

const LoopConstRef Loops::CGetLoop ( unsigned int id ) const

Returns a loop given the id.

Parameters

id	is the id of the loop

Definition at line 632 of file loops.cpp.

References const_loops_list, and THROW_UNREACHABLE.

◆ computeDepth()

void Loops::computeDepth ( const LoopConstRef loop )

private

Sets depth for each loop in the forest starting from loop.

Parameters

loop	is the root of the loop forest

Definition at line 742 of file loops.cpp.

References test_panda::children, and Loop::depth.

Referenced by Loops().

Here is the caller graph for this function:

◆ DetectIrreducibleLoop()

void Loops::DetectIrreducibleLoop	(	const BBGraphRef	djg,
		unsigned int	min_level,
		unsigned int	max_level,
		std::vector< std::list< vertex >> &	level_vertices_rel
	)

private

Populate u with all the non-visited node whose level is >= min_level

Definition at line 464 of file loops.cpp.

References FunctionBehavior::BB, BBGraph::CGetBBNodeInfo(), debug_level, DEBUG_LEVEL_VERY_PEDANTIC, FB, INDENT_DBG_MEX, level, PRINT_DBG_MEX, STR, tarjan_scc(), and THROW_ASSERT.

Referenced by DetectLoops().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DetectLoops()

void Loops::DetectLoops ( )

private

Computes the loops of the control flow graph.

Retrieve dominator tree and dominance relation

Create the DJ graph. This is done in two steps: 1) build the dominator tree 2) add the "J" edges

Add J edges (and detect CJ ones) D edges are already there since we use boost filtered graphs

Check for CJ and BJ edges

This is a BJ edge, and we mark it as such

This is a CJ edge, and we mark it as such

Build the spanning tree and detect the sp-back edges

spanning tree ancestor data structure

initialization

spanning tree construction and vertex labeling

compute the level_vertices_rel

Detect the sp-back edges

This is a sp-back edge

Detect this Loop (n is the header)

Identify SCCs for the subgraphs induced by nodes at level greater or equal than lev

Definition at line 216 of file loops.cpp.

References block_to_loop, BBGraph::CGetBBGraphInfo(), BBGraph::CGetBBNodeInfo(), check_ancestor(), const_loops_list, debug_level, DEBUG_LEVEL_PEDANTIC, DEBUG_LEVEL_VERY_PEDANTIC, DetectIrreducibleLoop(), DetectReducibleLoop(), FunctionBehavior::DJ, edges, FB, FunctionBehavior::FBB, BehavioralHelper::get_function_name(), dominance< GraphObj >::get_immediate_dominator(), dominance< GraphObj >::getAllDominated(), index, is_edge_in_list(), J_SELECTOR, modifiable_loops_list, Param, PRINT_DBG_MEX, lenet_tvm::target, THROW_ASSERT, and BBGraph::WriteDot().

Referenced by Loops().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ DetectReducibleLoop()

void Loops::DetectReducibleLoop	(	const BBGraphRef	djg,
		CustomOrderedSet< vertex > &	visited,
		LoopRef	loop,
		vertex	node,
		vertex	header
	)

private

Reducible loop construction.

Parameters

djg	is the DJ graph
visited	is the set of vertex visited
loop	is the current loop
node	is current vertex
header	is the entry of the reducible loop

Definition at line 421 of file loops.cpp.

References Loop::add_block(), Loop::AddChild(), block_to_loop, Loop::Parent(), and Loop::SetParent().

Referenced by DetectLoops().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ GetList()

const std::list< LoopConstRef > & Loops::GetList ( ) const

Returns the list of loops (const)

Parameters

return the const list of loops

Definition at line 622 of file loops.cpp.

References const_loops_list.

◆ GetLoop()

const LoopRef Loops::GetLoop ( unsigned int id )

Returns a loop given the id.

Parameters

id	is the id of the loop

Definition at line 647 of file loops.cpp.

References modifiable_loops_list, and THROW_UNREACHABLE.

Referenced by Loops().

Here is the caller graph for this function:

◆ GetModifiableList()

const std::list< LoopRef > & Loops::GetModifiableList ( ) const

Return the list of loops.

Parameters

return the const list of loops

Definition at line 627 of file loops.cpp.

References modifiable_loops_list.

◆ is_edge_in_list()

bool Loops::is_edge_in_list	(	CustomUnorderedSet< vertex_pair > &	l,
		vertex	source,
		vertex	target
	)

private

Definition at line 203 of file loops.cpp.

Referenced by DetectLoops().

Here is the caller graph for this function:

◆ NumLoops()

size_t Loops::NumLoops ( ) const

Returns the number of loops.

Definition at line 662 of file loops.cpp.

References const_loops_list.

◆ stack_contains()

bool Loops::stack_contains	(	std::list< vertex >	stack,
		vertex	v
	)

private

Definition at line 502 of file loops.cpp.

Referenced by tarjan_scc().

Here is the caller graph for this function:

◆ tarjan_scc()

void Loops::tarjan_scc	(	const BBGraphRef	djg,
		vertex	v,
		CustomUnorderedMap< vertex, unsigned int > &	dfs_order,
		CustomUnorderedMap< vertex, unsigned int > &	lowlink,
		std::list< vertex > &	s,
		CustomOrderedSet< vertex > &	u,
		unsigned int &	max_dfs
	)