Provide liveness analysis. More...

#include <interference-graph.hh>

Inheritance diagram for liveness::InterferenceGraph:

Collaboration diagram for liveness::InterferenceGraph:

Public Types
typedef graph < boost::undirectedS, temp::Temp, empty >	super_type
typedef super_type::vertex_descriptor	vertex_descriptor
typedef graph < boost::undirectedS, temp::Temp, empty >	self_type

typedef boost::graph_traits < self_type >::vertex_iterator	vertex_iter_type
	Iterators.
typedef boost::graph_traits < self_type >::edge_iterator	edge_iter_type
	Iterator on the edges of a graph.

Public Member Functions
virtual void	edge_add (const vertex_descriptor &v1, const vertex_descriptor &v2) override
	Add an edge between two vertices.
Ctor & dtor.
	InterferenceGraph (const std::string &name, const assem::Instrs &instrs, const temp::TempMap &tempmap, bool trace=false)
	Construct an InterferenceGraph.
virtual	~InterferenceGraph ()

vertex_descriptor	vertex_add (const temp::Temp &l)
	Add a vertex to the graph.

virtual std::ostream &	print (std::ostream &ostr) const
virtual void	print (std::string file) const

const std::string &	name_get () const
void	name_set (const std::string &name)

Protected Member Functions
Liveness analysis engine.
void	compute_liveness (const liveness::Liveness &liveness)

Protected Attributes
Trace methods.
bool	trace_
	trace flag.

Private Attributes
Timer member.
misc::timer	timer_
	Interference timer.

Mapping from unique node decoration (the Temp) to
the vertex_descriptor.
typedef std::map< const temp::Temp, vertex_descriptor >	temp2vertex
	Converting a temp::Temp into a unique integer.
temp2vertex	temp2node
	The mapping from temp::Temp to vertex_descriptor (= integer).
const temp::TempMap &	tempmap_
	The mapping from pseudos to actual registers.
bool	has (const temp::Temp &t) const
	Is the Temp t already part of the InterferenceGraph?
vertex_descriptor	node_of (const temp::Temp &t)
	From Temp to vertex_descriptor. If t is not know yet, insert it.

Moves.
We keep track of all the moves so that we can try to coalesce destination and source.
typedef std::pair < vertex_descriptor, vertex_descriptor >	move_type
	A move is a pair (src, dst).
typedef misc::set< move_type >	move_set_type
	Sets of moves.
move_set_type	moves_
	The set of moves.
const move_set_type &	moves_get () const
	Return the moves (const).
move_set_type &	moves_get ()
	Return the moves (non-const).
const misc::timer &	timer_get () const
	Get the liveness timer.
virtual std::ostream &	epilogue_print (std::ostream &ostr) const
	Include the move related edges in the output.
virtual std::ostream &	vertex_print (vertex_descriptor v, std::ostream &ostr) const override
	Print the label of vertex of a graph.

Detailed Description

Provide liveness analysis.

The liveness of variables in control-flow is analyzed, producing an InterferenceGraph.

Member Typedef Documentation

typedef boost::graph_traits<self_type>::edge_iterator misc::graph< boost::undirectedS , temp::Temp , empty >::edge_iter_type

inherited

Iterator on the edges of a graph.

typedef misc::set<move_type> liveness::InterferenceGraph::move_set_type

Sets of moves.

typedef std::pair<vertex_descriptor, vertex_descriptor> liveness::InterferenceGraph::move_type

A move is a pair (src, dst).

Moves are not oriented, we chose to have pairs such that 1st <= 2nd.

typedef graph<boost::undirectedS , temp::Temp , empty > misc::graph< boost::undirectedS , temp::Temp , empty >::self_type

inherited

typedef graph<boost::undirectedS, temp::Temp , empty > misc::undirected_graph< temp::Temp , empty >::super_type

inherited

typedef std::map<const temp::Temp, vertex_descriptor> liveness::InterferenceGraph::temp2vertex

private

Converting a temp::Temp into a unique integer.

typedef super_type::vertex_descriptor misc::undirected_graph< temp::Temp , empty >::vertex_descriptor

inherited

typedef boost::graph_traits<self_type>::vertex_iterator misc::graph< boost::undirectedS , temp::Temp , empty >::vertex_iter_type

inherited

Iterators.

Iterator on the vertices of a graph.

Constructor & Destructor Documentation

liveness::InterferenceGraph::InterferenceGraph	(	const std::string &	name,
		const assem::Instrs &	instrs,
		const temp::TempMap &	tempmap,
		bool	trace = `false`
	)

Construct an InterferenceGraph.

Parameters

name	its name, hopefully based on the function name
instrs	the code snippet to study
tempmap	current Temp mapping
trace	trace flag

References compute_liveness(), misc::graph< boost::undirectedS, temp::Temp, empty >::name_set(), misc::graph< Orientation, VertexLabel, EdgeLabel >::print(), misc::graph< boost::undirectedS, temp::Temp, empty >::print(), timer_, liveness::FlowGraph< EdgeLabel >::timer_get(), and trace_.

liveness::InterferenceGraph::~InterferenceGraph ( )

virtual

Member Function Documentation

void liveness::InterferenceGraph::compute_liveness ( const liveness::Liveness & liveness )

protected

References misc::timer::pop(), misc::timer::push(), timer_, and trace_.

Referenced by InterferenceGraph().

virtual void misc::undirected_graph< temp::Temp , empty >::edge_add	(	const vertex_descriptor &	v1,
		const vertex_descriptor &	v2
	)

overridevirtualinherited

Add an edge between two vertices.

Use this method instead of boost::add_edge directly to keep the order between the ends of an edge.

Implements misc::graph< boost::undirectedS, temp::Temp, empty >.

std::ostream & liveness::InterferenceGraph::epilogue_print ( std::ostream & ostr ) const

protectedvirtual

Include the move related edges in the output.

Reimplemented from misc::graph< boost::undirectedS, temp::Temp, empty >.

References moves_.

bool liveness::InterferenceGraph::has ( const temp::Temp & t ) const

Is the Temp t already part of the InterferenceGraph?

References temp2node.

const InterferenceGraph::move_set_type & liveness::InterferenceGraph::moves_get ( ) const

inline

Return the moves (const).

References moves_.

Referenced by regalloc::Color::import_moves().

InterferenceGraph::move_set_type & liveness::InterferenceGraph::moves_get ( )

inline

Return the moves (non-const).

References moves_.

const std::string& misc::graph< boost::undirectedS , temp::Temp , empty >::name_get ( ) const

inherited

Graph name.

void misc::graph< boost::undirectedS , temp::Temp , empty >::name_set ( const std::string & name )

inherited

Referenced by InterferenceGraph().

InterferenceGraph::vertex_descriptor liveness::InterferenceGraph::node_of ( const temp::Temp & t )

From Temp to vertex_descriptor. If t is not know yet, insert it.

References temp2node, tempmap_, and misc::graph< boost::undirectedS, temp::Temp, empty >::vertex_add().

virtual std::ostream& misc::graph< boost::undirectedS , temp::Temp , empty >::print ( std::ostream & ostr ) const

virtualinherited

Graph pretty printing.

Referenced by InterferenceGraph().

virtual void misc::graph< boost::undirectedS , temp::Temp , empty >::print ( std::string file ) const

virtualinherited

const misc::timer & liveness::InterferenceGraph::timer_get ( ) const

inline

Get the liveness timer.

References timer_.

Referenced by regalloc::Color::Color().

vertex_descriptor misc::graph< boost::undirectedS , temp::Temp , empty >::vertex_add ( const temp::Temp & l )

inherited

Add a vertex to the graph.

Graph manipulation.Just a wrapper around boost::add_vertex.

Referenced by node_of().

std::ostream & liveness::InterferenceGraph::vertex_print	(	vertex_descriptor	v,
		std::ostream &	ostr
	)		const

overrideprotectedvirtual

Print the label of vertex of a graph.

Implements misc::graph< boost::undirectedS, temp::Temp, empty >.

Member Data Documentation

move_set_type liveness::InterferenceGraph::moves_

protected

The set of moves.

Referenced by epilogue_print(), and moves_get().

temp2vertex liveness::InterferenceGraph::temp2node

private

The mapping from temp::Temp to vertex_descriptor (= integer).

Referenced by has(), and node_of().

const temp::TempMap& liveness::InterferenceGraph::tempmap_

private

The mapping from pseudos to actual registers.

Referenced by node_of().

misc::timer liveness::InterferenceGraph::timer_

private

Interference timer.

Referenced by compute_liveness(), InterferenceGraph(), and timer_get().

bool liveness::InterferenceGraph::trace_

protected

trace flag.

Referenced by compute_liveness(), and InterferenceGraph().

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

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Attributes

Mapping from unique node decoration (the Temp) to

Moves.

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation