Otawa  0.10
Public Member Functions | Private Attributes | List of all members
otawa::dfa::XIterativeDFA< V > Class Template Reference

The DFAEngine implements an extended Iterative Data Flow Algorithm, that is, it work on graphs with any forms. More...

#include <otawa/dfa/XIterativeDFA.h>

Public Member Functions

 XIterativeDFA (V &visitor)
 Build an iterative DFA with the given visitor. More...
 
 ~XIterativeDFA (void)
 
void process (void)
 
void nextPred (int pred)
 This functions is used internally to communicate with the visitor. More...
 
V::domain_t * in (const typename V::key_t &key)
 
V::domain_t * out (const typename V::key_t &key)
 
V::domain_t * gen (const typename V::key_t &key)
 
V::domain_t * preserve (const typename V::key_t &key)
 

Private Attributes

V & visit
 
int size
 
V::domain_t ** outs
 
V::domain_t ** gens
 
V::domain_t ** preserves
 
V::domain_t * new_out
 
V::domain_t ** ins
 

Detailed Description

template<class V>
class otawa::dfa::XIterativeDFA< V >

The DFAEngine implements an extended Iterative Data Flow Algorithm, that is, it work on graphs with any forms.

Basically, it just apply the GEN/KILL computation to a set of nodes until reaching a fix point.

OUT = union(IN) inter KILL union GEN
But, to traverse the graph, it uses a visitor giving the next nodes to process. With a visitor like dfa::XCFGVisitor, it may applied on a whole CFG hierarchy to perform inter-procedure analysis.
Parameters
Vthe used visitor type. It must have the following signature (nodes are identified by an integer index).

The V parameter must implement the following concept:

class V {
public:
typedef domain_t; // domain type
domain_t *empty(void); // return an empty domain
domain_t *gen(int node); // return the GEN value
domain_t *kill(int node); // return the KILL value
void free(domain_t *d); // free the given domain
typedef key_t; // node key
int index(const key_t& key); // get index of the given key
int size(void); // count of graph nodes
void visitPreds(XIterativeDFA<> engine, int node);
// visit the predecessors of a node, call nextPred(int node) on engine.
void visitSuccs(XIterativeDFA<> engine, int node);
// visit the successors of a node, call nextSucc(int node) on engine.
};

The V::domain_t type must implements the following concept :

class domain_t {
void reset(void); // reset the domain
void join(domain_t *d); // join between current domain and given one.
void meet(domain_t *d); // meet between current domain and given one.
bool equals(domain_t *d); // test if both domains are equals
};

Known visitors includes:

Constructor & Destructor Documentation

template<class V >
otawa::dfa::XIterativeDFA< V >::XIterativeDFA ( V &  visitor)
inline

Build an iterative DFA with the given visitor.

Parameters
visitorVisitor to use.

References otawa::dfa::XIterativeDFA< V >::gens, otawa::dfa::XIterativeDFA< V >::ins, otawa::dfa::XIterativeDFA< V >::outs, otawa::dfa::XIterativeDFA< V >::preserves, otawa::dfa::XIterativeDFA< V >::size, and otawa::dfa::XIterativeDFA< V >::visit.

template<class V >
otawa::dfa::XIterativeDFA< V >::~XIterativeDFA ( void  )
inline

Member Function Documentation

template<class V >
V::domain_t* otawa::dfa::XIterativeDFA< V >::gen ( const typename V::key_t &  key)
inline

References otawa::dfa::XIterativeDFA< V >::gens, and otawa::dfa::XIterativeDFA< V >::visit.

template<class V >
V::domain_t* otawa::dfa::XIterativeDFA< V >::in ( const typename V::key_t &  key)
inline

References otawa::dfa::XIterativeDFA< V >::ins, and otawa::dfa::XIterativeDFA< V >::visit.

Referenced by otawa::cat::CATBuilder::processLBlockSet(), and otawa::ccg::Builder::processLBlockSet().

template<class V >
void otawa::dfa::XIterativeDFA< V >::nextPred ( int  pred)
inline

This functions is used internally to communicate with the visitor.

When the visitor function visitPreds() is called, the visitor will call this functione each time a predecessor is found.

Parameters
predCurrent predecessor.
template<class V >
V::domain_t* otawa::dfa::XIterativeDFA< V >::out ( const typename V::key_t &  key)
inline

References otawa::dfa::XIterativeDFA< V >::outs, and otawa::dfa::XIterativeDFA< V >::visit.

template<class V >
V::domain_t* otawa::dfa::XIterativeDFA< V >::preserve ( const typename V::key_t &  key)
inline

References otawa::dfa::XIterativeDFA< V >::preserves, and otawa::dfa::XIterativeDFA< V >::visit.

template<class V >
void otawa::dfa::XIterativeDFA< V >::process ( void  )
inline

Referenced by otawa::cat::CATBuilder::processLBlockSet(), and otawa::ccg::Builder::processLBlockSet().

Member Data Documentation

template<class V >
V::domain_t ** otawa::dfa::XIterativeDFA< V >::gens
private

Referenced by otawa::dfa::XIterativeDFA< V >::gen(), and otawa::dfa::XIterativeDFA< V >::XIterativeDFA().

template<class V >
V::domain_t ** otawa::dfa::XIterativeDFA< V >::ins
private

Referenced by otawa::dfa::XIterativeDFA< V >::in(), and otawa::dfa::XIterativeDFA< V >::XIterativeDFA().

template<class V >
V::domain_t * otawa::dfa::XIterativeDFA< V >::new_out
private
template<class V >
V::domain_t** otawa::dfa::XIterativeDFA< V >::outs
private

Referenced by otawa::dfa::XIterativeDFA< V >::out(), and otawa::dfa::XIterativeDFA< V >::XIterativeDFA().

template<class V >
V::domain_t ** otawa::dfa::XIterativeDFA< V >::preserves
private

Referenced by otawa::dfa::XIterativeDFA< V >::preserve(), and otawa::dfa::XIterativeDFA< V >::XIterativeDFA().

template<class V >
int otawa::dfa::XIterativeDFA< V >::size
private

Referenced by otawa::dfa::XIterativeDFA< V >::XIterativeDFA().

template<class V >
V& otawa::dfa::XIterativeDFA< V >::visit
private

Referenced by otawa::dfa::XIterativeDFA< V >::gen(), otawa::dfa::XIterativeDFA< V >::in(), otawa::dfa::XIterativeDFA< V >::out(), otawa::dfa::XIterativeDFA< V >::preserve(), and otawa::dfa::XIterativeDFA< V >::XIterativeDFA().

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