FlowGraph labeled with live Temp. More...

#include <liveness.hh>

Inheritance diagram for liveness::Liveness:

Collaboration diagram for liveness::Liveness:

Public Types
typedef FlowGraph < temp::temp_set_type >	super_type
	Superclass.
typedef std::map < vertex_descriptor, temp::temp_set_type >	livemap_type
typedef FlowGraph < temp::temp_set_type >	self_type
	Shorthand for the current class type.
typedef super_type::vertex_descriptor	vertex_descriptor
typedef boost::graph_traits < self_type >::vertex_iterator	vertex_iter_type
	Iterator on the vertices of a directed_graph.
typedef boost::graph_traits < self_type > ::adjacency_iterator	neighb_iter_type
	Iterator on the neighbors of the vertex of a directed_graph.

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

Public Member Functions
	Liveness (const std::string &name, const assem::Instrs &instrs, const temp::TempMap &tempmap)
	Compute the liveness of variables in the flow-graph by iteration.
const livemap_type &	liveout_get () const
const livemap_type &	livein_get () const
const misc::timer &	timer_get () const

virtual void	edge_add (const vertex_descriptor &v1, const vertex_descriptor &v2) override
	Add an edge between two vertices.

std::list< vertex_descriptor >	topological_sort () const
	Topological sort.

vertex_descriptor	vertex_add (const const assem::Instr *&l)
	Add a vertex to the graph.

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

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

Protected Member Functions
virtual std::ostream &	vertex_print (vertex_descriptor v, std::ostream &ostr) const
	Print the label of vertex of a graph.

Protected Attributes
Timer member.
misc::timer	timer_
	Flowgraph timer.

Private Attributes
livemap_type	in
livemap_type	out

Detailed Description

FlowGraph labeled with live Temp.

Member Typedef Documentation

typedef boost::graph_traits<self_type>::edge_iterator misc::graph< boost::bidirectionalS , const assem::Instr * , temp::temp_set_type >::edge_iter_type

inherited

Iterator on the edges of a graph.

typedef std::map<vertex_descriptor, temp::temp_set_type> liveness::Liveness::livemap_type

typedef boost::graph_traits<self_type>::adjacency_iterator misc::directed_graph< const assem::Instr * , temp::temp_set_type >::neighb_iter_type

inherited

Iterator on the neighbors of the vertex of a directed_graph.

typedef FlowGraph<temp::temp_set_type > liveness::FlowGraph< temp::temp_set_type >::self_type

inherited

Shorthand for the current class type.

typedef FlowGraph<temp::temp_set_type> liveness::Liveness::super_type

Superclass.

typedef super_type::vertex_descriptor liveness::FlowGraph< temp::temp_set_type >::vertex_descriptor

inherited

typedef boost::graph_traits<self_type>::vertex_iterator misc::directed_graph< const assem::Instr * , temp::temp_set_type >::vertex_iter_type

inherited

Iterator on the vertices of a directed_graph.

Constructor & Destructor Documentation

liveness::Liveness::Liveness	(	const std::string &	name,
		const assem::Instrs &	instrs,
		const temp::TempMap &	tempmap
	)

Compute the liveness of variables in the flow-graph by iteration.

This implementation is based on the algorithm 17.6 described in Modern Compiler Implementation in Java written by A. Appel. This is a work-list algorithm which keeps track of what must be recalculated.

Attention: When displayed, the Liveness graph is a good means to check that the compiler works properly, including after the register allocation: we want to check that the liveness of the hard registers is properly understood. But the Liveness graph is built thanks to the def and use of the instructions which are composed of temporaries (not hard registers). So to be able to use the Liveness graph after register allocation, we must take the temp::tasks::tempmap into account below.

Parameters

name	name of this graph, hopefully based on the function name
instrs	the assembly program of which compute the liveness graph
tempmap	a mapping to apply on instrs.

References in, out, misc::timer::pop(), misc::timer::push(), misc::set_intersection(), boost::target(), and liveness::FlowGraph< temp::temp_set_type >::timer_.

Member Function Documentation

virtual void misc::directed_graph< const assem::Instr * , temp::temp_set_type >::edge_add	(	const vertex_descriptor &	v1,
		const vertex_descriptor &	v2
	)

overridevirtualinherited

Add an edge between two vertices.

Iterators.This is just a wrapper around boost::add_edge.

Implements misc::graph< boost::bidirectionalS, const assem::Instr *, temp::temp_set_type >.

virtual std::ostream& misc::graph< boost::bidirectionalS , const assem::Instr * , temp::temp_set_type >::epilogue_print ( std::ostream & ostr ) const

virtualinherited

const Liveness::livemap_type & liveness::Liveness::livein_get ( ) const

References in.

const Liveness::livemap_type & liveness::Liveness::liveout_get ( ) const

References out.

const std::string& misc::graph< boost::bidirectionalS , const assem::Instr * , temp::temp_set_type >::name_get ( ) const

inherited

Graph name.

void misc::graph< boost::bidirectionalS , const assem::Instr * , temp::temp_set_type >::name_set ( const std::string & name )

inherited

virtual std::ostream& misc::graph< boost::bidirectionalS , const assem::Instr * , temp::temp_set_type >::print ( std::ostream & ostr ) const

virtualinherited

Graph pretty printing.

virtual void misc::graph< boost::bidirectionalS , const assem::Instr * , temp::temp_set_type >::print ( std::string file ) const

virtualinherited

const misc::timer& liveness::FlowGraph< temp::temp_set_type >::timer_get ( ) const

inherited

std::list<vertex_descriptor> misc::directed_graph< const assem::Instr * , temp::temp_set_type >::topological_sort ( ) const

inherited

Topological sort.

This version (algorithm 17.5 in Modern Compiler Implementation in ML, p. 390) is not the same as boost::topological_sort since the former works on directed acyclic graphs (DAGs) and the latter doesn't.

vertex_descriptor misc::graph< boost::bidirectionalS , const assem::Instr * , temp::temp_set_type >::vertex_add ( const const assem::Instr * & l )