Skip to content

DominatorTreesAndDominanceFrontiers::TemplatedDominatorTree

TemplatedDominatorTree constructs a dominator/postdominator tree for a cfg. For the template parameter any cfg following Jeremias interface may be used

Synopsis

Declared in <src/midend/programAnalysis/dominanceAnalysis/DominatorTree.h>

template<typename CFGFilterFunction>
class TemplatedDominatorTree
    : public DominatorForwardBackwardWrapperClass<CFGFilterFunction>

Base Classes

Name Description
DominatorForwardBackwardWrapperClass<CFGFilterFunction> This class provides a uniform view of the CFG dissregarding the direction of the CFG-traversal (forward/backward)

Member Functions

Name Description
TemplatedDominatorTree
TemplatedDominatorTree( SgNode* head, Direction d = DominatorForwardBackwardWrapperClass< CFGFilterFunction>::PRE_DOMINATOR); [constructor]
constructor for the DT. Head is the start point for the DT construction. DT works for SgFunctionDefintion nodes, unexpected behaviour for non-SgFunctionDefinition!!!
dominates
bool dominates( int a, int b);
dominates overloads
getCFGNodeFromID
VirtualCFG::FilteredCFGNode<CFGFilterFunction> getCFGNodeFromID(unsigned int id);
getDirectDominatedSet
std::set<int> getDirectDominatedSet(int nodeID);
returns the set of nodes directly dominated by nodeID
getID
int getID(VirtualCFG::FilteredCFGNode<CFGFilterFunction> node);
getImDomID
int getImDomID(int i);
get the ImDomID for given SgNode, returns negative for non-cfg-node
getSize
int getSize();
writeDot
void writeDot(char const* filename);
writes the DT in DOT-notation to the file given in filename

Private Member Functions

Name Description
calculateImmediateDominators
void calculateImmediateDominators();
calculate immediate dominators
depthFirstSearch
void depthFirstSearch();
create the dfs-order of the cfg
eval
int eval(int node);
helperfunction according to lingauer&tarjan
link
void link( int source, int target);
create the forrest of parents

Private Data Members

Name Description
ancestor internal variables
buckets
cfgRoot
dfsParent internal variables
idToNode
idom internal variables
nodeToIdMap
semi internal variables

Created with MrDocs