Calculate the Dominator Tree. More...

Inheritance diagram for cacao::jit::compiler2::DominatorPass:

Public Member Functions
	DominatorPass ()

virtual bool	run (JITData &JD)
	Run the Pass. More...

virtual PassUsage &	get_PassUsage (PassUsage &PU) const
	Set the requirements for the pass. More...

Public Member Functions inherited from cacao::jit::compiler2::Pass
	Pass ()

void	set_PassManager (PassManager *PM)

template<class _PassClass >
_PassClass *	get_Pass () const
	Get the result of a previous compiler pass. More...

template<class _PassClass >
_PassClass *	get_Pass_if_available () const
	Get the result of a previous compiler pass. More...

virtual void	initialize ()
	Initialize the Pass. More...

virtual void	finalize ()
	Finalize the Pass. More...

virtual bool	verify () const
	Verify the Result. More...

virtual	~Pass ()
	Destructor. More...

Public Member Functions inherited from cacao::jit::compiler2::DominatorTree
bool	dominates (NodeTy a, NodeTy b) const
	True if a dominates b. More...

bool	is_dominated_by (NodeTy b, NodeTy a) const
	True if b is dominated by b. More...

NodeTy *	get_idominator (NodeTy *a) const
	Get the immediate dominator. More...

NodeTy *	find_nearest_common_dom (NodeTy a, NodeTy b) const
	Find the nearest common dominator. More...

int	depth (NodeTy *node) const
	Depth of a tree node. More...

Static Public Attributes
static char	ID = 0

Private Types
typedef BeginInst	NodeTy

typedef alloc::set< NodeTy * > ::type	NodeListTy

typedef alloc::map< NodeTy *, NodeListTy >::type	NodeListMapTy

typedef alloc::vector< NodeTy * > ::type	NodeMapTy

typedef alloc::map< NodeTy *, int >::type	IndexMapTy

typedef alloc::map< NodeTy , NodeTy >::type	EdgeMapTy

Private Member Functions
NodeListTy &	succ (NodeTy *v, NodeListTy &list)

void	DFS (NodeTy *v)

void	Link (NodeTy v, NodeTy w)

NodeTy *	Eval (NodeTy *v)

void	Compress (NodeTy *v)

Private Attributes
EdgeMapTy	parent

NodeListMapTy	pred

IndexMapTy	semi

NodeMapTy	vertex

NodeListMapTy	bucket

int	n

EdgeMapTy	ancestor

EdgeMapTy	label

Additional Inherited Members
Public Types inherited from cacao::jit::compiler2::DominatorTree
typedef BeginInst	NodeTy

typedef alloc::map< NodeTy , NodeTy >::type	EdgeMapTy

Static Public Member Functions inherited from cacao::jit::compiler2::memory::ManagerMixin< DominatorPass >
static void *	operator new (std::size_t size) throw (std::bad_alloc)
	normal new More...

static void *	operator new (std::size_t size, void *ptr) throw ()
	placement new More...

static void *	operator new (std::size_t size, const std::nothrow_t &nt) throw ()
	nothrow new More...

static void	operator delete (void *pMemory) throw ()
	normal delete More...

static void	operator delete (void pMemory, void ptr) throw ()
	placement delete More...

static void	operator delete (void *pMemory, const std::nothrow_t &) throw ()
	nothrow delete More...

static void *	operator new[] (std::size_t size) throw (std::bad_alloc)
	normal new[] More...

static void *	operator new[] (std::size_t size, void *ptr) throw ()
	placement new[] More...

static void *	operator new[] (std::size_t size, const std::nothrow_t &nt) throw ()
	nothrow new[] More...

static void	operator delete[] (void *pMemory) throw ()
	normal delete[] More...

static void	operator delete[] (void pMemory, void ptr) throw ()
	placement delete[] More...

static void	operator delete[] (void *pMemory, const std::nothrow_t &) throw ()
	nothrow delete[] More...

Protected Attributes inherited from cacao::jit::compiler2::DominatorTree
EdgeMapTy	dom

Detailed Description

Calculate the Dominator Tree.

This Pass implements the algorithm proposed by Lengauer and Tarjan. The variable and function are named accoring to the paper. Currently the 'simple' version is implemented. The 'sophisticated' version is left for future work.

A Fast Algorithm for Finding Dominators in a Flowgraph, by Lengauer and Tarjan, 1979 [4].

Definition at line 103 of file DominatorPass.hpp.

Member Typedef Documentation

typedef alloc::map<NodeTy *,NodeTy *>::type cacao::jit::compiler2::DominatorPass::EdgeMapTy

private

Definition at line 110 of file DominatorPass.hpp.

typedef alloc::map<NodeTy *,int>::type cacao::jit::compiler2::DominatorPass::IndexMapTy

private

Definition at line 109 of file DominatorPass.hpp.

typedef alloc::map<NodeTy *,NodeListTy>::type cacao::jit::compiler2::DominatorPass::NodeListMapTy

private

Definition at line 107 of file DominatorPass.hpp.

typedef alloc::set<NodeTy *>::type cacao::jit::compiler2::DominatorPass::NodeListTy

private

Definition at line 106 of file DominatorPass.hpp.

typedef alloc::vector<NodeTy *>::type cacao::jit::compiler2::DominatorPass::NodeMapTy

private

Definition at line 108 of file DominatorPass.hpp.

typedef BeginInst cacao::jit::compiler2::DominatorPass::NodeTy

private

Definition at line 105 of file DominatorPass.hpp.

Constructor & Destructor Documentation

cacao::jit::compiler2::DominatorPass::DominatorPass ( )

inline

Definition at line 130 of file DominatorPass.hpp.

Member Function Documentation

void cacao::jit::compiler2::DominatorPass::Compress ( NodeTy * v )

private

Definition at line 121 of file DominatorPass.cpp.

void cacao::jit::compiler2::DominatorPass::DFS ( NodeTy * v )

private

Definition at line 89 of file DominatorPass.cpp.

DominatorPass::NodeTy * cacao::jit::compiler2::DominatorPass::Eval ( NodeTy * v )

private

Definition at line 113 of file DominatorPass.cpp.

PassUsage & cacao::jit::compiler2::DominatorPass::get_PassUsage ( PassUsage & PU ) const

virtual

Set the requirements for the pass.

Reimplemented from cacao::jit::compiler2::Pass.

Definition at line 207 of file DominatorPass.cpp.

void cacao::jit::compiler2::DominatorPass::Link	(	NodeTy *	v,
		NodeTy *	w
	)

private

Definition at line 109 of file DominatorPass.cpp.

bool cacao::jit::compiler2::DominatorPass::run ( JITData & JD )

virtual

Run the Pass.

This method implements the compiler pass.

Returns: false if a problem occurred, true otherwise

Implements cacao::jit::compiler2::Pass.

Definition at line 133 of file DominatorPass.cpp.

DominatorPass::NodeListTy & cacao::jit::compiler2::DominatorPass::succ	(	NodeTy *	v,
		NodeListTy &	list
	)

private

Definition at line 79 of file DominatorPass.cpp.

Field Documentation

EdgeMapTy cacao::jit::compiler2::DominatorPass::ancestor

private

Definition at line 119 of file DominatorPass.hpp.

NodeListMapTy cacao::jit::compiler2::DominatorPass::bucket

private

Definition at line 116 of file DominatorPass.hpp.

char cacao::jit::compiler2::DominatorPass::ID = 0

static

Definition at line 129 of file DominatorPass.hpp.

EdgeMapTy cacao::jit::compiler2::DominatorPass::label

private

Definition at line 120 of file DominatorPass.hpp.

int cacao::jit::compiler2::DominatorPass::n

private

Definition at line 117 of file DominatorPass.hpp.

EdgeMapTy cacao::jit::compiler2::DominatorPass::parent

private

Definition at line 112 of file DominatorPass.hpp.

NodeListMapTy cacao::jit::compiler2::DominatorPass::pred

private

Definition at line 113 of file DominatorPass.hpp.

IndexMapTy cacao::jit::compiler2::DominatorPass::semi

private

Definition at line 114 of file DominatorPass.hpp.

NodeMapTy cacao::jit::compiler2::DominatorPass::vertex

private

Definition at line 115 of file DominatorPass.hpp.

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

/home/bbc/buildbot/slave/doxygen-compiler2/source/cacao/src/vm/jit/compiler2/DominatorPass.hpp
/home/bbc/buildbot/slave/doxygen-compiler2/source/cacao/src/vm/jit/compiler2/DominatorPass.cpp

Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation