otawa::dfa::IterativeDFA< Problem, Set, Iter > Class Template Reference

This class provides a generic facility to implement iterative Data Flow Analysis (DFA) as presented in "Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, Addison Wesley 1986". More...

#include <otawa/dfa/IterativeDFA.h>

Public Member Functions
	IterativeDFA (Problem &problem, CFG &cfg)
	~IterativeDFA (void)
void	compute (void)
	Perform the iterative DFA analysis. More...
Set *	inSet (BasicBlock *bb)
	Get the IN(BB) set. More...
Set *	outSet (BasicBlock *bb)
	Get the OUT(BB) set. More...
Set *	genSet (BasicBlock *bb)
	Get the GEN(BB) set. More...
Set *	killSet (BasicBlock *bb)
	Get the KILL(BB) set. More...

Private Attributes
Problem &	prob
CFG &	_cfg
int	cnt
Set **	ins
Set **	outs
Set **	gens
Set **	kills

Detailed Description

template<class Problem, class Set, class Iter = Predecessor>
class otawa::dfa::IterativeDFA< Problem, Set, Iter >

This class provides a generic facility to implement iterative Data Flow Analysis (DFA) as presented in "Aho, Sethi, Ullman, Compilers: Principles, Techniques, and Tools, Addison Wesley 1986".

An iterative DFA perform a static analysis that computes for each BB of a CFG two value sets (the set may be whatever value handled in the analyzed program):

• IN set before the BB execution (union of previous BB sets),
• OUT set after the BB execution (IN after update of the BB).

To compute IN and OUT, the recursive formulae below are used:

    IN(BB) = U(BBi) / BBi is predecessor of BB

            OUT(BB) = IN(BB) - KILL(BB) U GEN(BB)

Where KILL(BB) represents the items removed by the execution of BB and GEN(BB) the added items. Finally, we need default set value to initialize the OUT of the BB and to perform a fixpoint computation on the whole CFG.

The final algorithm is described below:

foreach BB do OUT(BB) <- INIT(BB)
change <- true
while change do
     change <- false
     foreach BB do
        old_out <- OUT(bb)
        IN(BB) = U(BBi) / BBi is predecessor of BB
                OUT(BB) = IN(BB) - KILL(BB) U GEN(BB)
        if OUT(BB) <> old_out then change <- true
     done
done

Notice that thanks to Iter type paremeter, we may have forward or backward traversal of the CFG (IN may be union of predecessors or of successors).

An efficient way to implement the handled set is provided by the otawa::dfa::BitSet class.

Parameters

Problem	DFA problem to solve. It must implements the concept otawa::concept::IterativeDFAProblem.
Set	Type of set used to implements the problem (depends on the problem).
Iter	Kind of iterator to get predecessor sets of the current computation (default to Predecessor for forward traversal, possibly Successor for backward traversal).

Constructor & Destructor Documentation

template<class Problem , class Set , class Iter >

otawa::dfa::IterativeDFA< Problem, Set, Iter >::IterativeDFA ( Problem &  problem, CFG &  cfg  )

inline

Parameters

problem	Problem to work on.
cfg	CFG to work on.

References otawa::dfa::IterativeDFA< Problem, Set, Iter >::_cfg, otawa::cfgio::bb(), otawa::dfa::IterativeDFA< Problem, Set, Iter >::cnt, otawa::dfa::IterativeDFA< Problem, Set, Iter >::gens, otawa::dfa::INDEX, otawa::dfa::IterativeDFA< Problem, Set, Iter >::ins, otawa::dfa::IterativeDFA< Problem, Set, Iter >::kills, otawa::dfa::IterativeDFA< Problem, Set, Iter >::outs, and otawa::dfa::IterativeDFA< Problem, Set, Iter >::prob.

template<class Problem , class Set , class Iter >

otawa::dfa::IterativeDFA< Problem, Set, Iter >::~IterativeDFA ( void  )

inline

Member Function Documentation

template<class Problem , class Set , class Iter >

void otawa::dfa::IterativeDFA< Problem, Set, Iter >::compute ( void  )

inline

Perform the iterative DFA analysis.

References otawa::cfgio::bb(), elm::genstruct::VectorQueue< T, class >::get(), otawa::BasicBlock::number(), OTAWA_IDFA_DUMP, OTAWA_IDFA_TRACE, and elm::genstruct::VectorQueue< T, class >::put().

Referenced by otawa::PostDominance::processCFG(), and otawa::Dominance::processCFG().

template<class Problem , class Set , class Iter >

Set * otawa::dfa::IterativeDFA< Problem, Set, Iter >::genSet ( BasicBlock *  bb )

inline

Get the GEN(BB) set.

Parameters

bb	Examined BB.

Returns

GEN(BB).

References otawa::dfa::INDEX.

template<class Problem , class Set , class Iter >

Set * otawa::dfa::IterativeDFA< Problem, Set, Iter >::inSet ( BasicBlock *  bb )

inline

Get the IN(BB) set.

Parameters

bb	Examined BB.

Returns

IN(BB).

References otawa::dfa::INDEX.

template<class Problem , class Set , class Iter >

Set * otawa::dfa::IterativeDFA< Problem, Set, Iter >::killSet ( BasicBlock *  bb )

inline

Get the KILL(BB) set.

Parameters

bb	Examined BB.

Returns

KILL(BB).

References otawa::dfa::INDEX.

template<class Problem , class Set , class Iter >

Set * otawa::dfa::IterativeDFA< Problem, Set, Iter >::outSet ( BasicBlock *  bb )

inline

Get the OUT(BB) set.

Parameters

bb	Examined BB.

Returns

OUT(BB).

References otawa::dfa::INDEX.

Referenced by otawa::PostDominance::processCFG(), and otawa::Dominance::processCFG().

Member Data Documentation

template<class Problem, class Set, class Iter = Predecessor>

CFG& otawa::dfa::IterativeDFA< Problem, Set, Iter >::_cfg

private

Referenced by otawa::dfa::IterativeDFA< Problem, Set, Iter >::IterativeDFA().

template<class Problem, class Set, class Iter = Predecessor>

int otawa::dfa::IterativeDFA< Problem, Set, Iter >::cnt

private

Referenced by otawa::dfa::IterativeDFA< Problem, Set, Iter >::IterativeDFA().

template<class Problem, class Set, class Iter = Predecessor>

Set ** otawa::dfa::IterativeDFA< Problem, Set, Iter >::gens

private

Referenced by otawa::dfa::IterativeDFA< Problem, Set, Iter >::IterativeDFA().

template<class Problem, class Set, class Iter = Predecessor>

Set** otawa::dfa::IterativeDFA< Problem, Set, Iter >::ins

private

Referenced by otawa::dfa::IterativeDFA< Problem, Set, Iter >::IterativeDFA().

template<class Problem, class Set, class Iter = Predecessor>

Set ** otawa::dfa::IterativeDFA< Problem, Set, Iter >::kills

private

Referenced by otawa::dfa::IterativeDFA< Problem, Set, Iter >::IterativeDFA().

template<class Problem, class Set, class Iter = Predecessor>

Set ** otawa::dfa::IterativeDFA< Problem, Set, Iter >::outs

private

Referenced by otawa::dfa::IterativeDFA< Problem, Set, Iter >::IterativeDFA().

template<class Problem, class Set, class Iter = Predecessor>

Problem& otawa::dfa::IterativeDFA< Problem, Set, Iter >::prob

private

Referenced by otawa::dfa::IterativeDFA< Problem, Set, Iter >::IterativeDFA().

---

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

• include/otawa/dfa/IterativeDFA.h
• src/prog/dfa_IterativeDFA.cpp