Hi!

while trying to use llvm::DominatorTreeBase on a custom graph that

has nothing to do with llvm::BasicBlock I ran into some difficulties,

because llvm::DominatorTreeBase calls e.g. getParent()->front()

directly on the nodes and uses llvm::Inverse which forced me to

implement my GraphTraits also for Inverse.

This could be solved using a compile time abstraction of Graph

instread of GraphTraits.

the abstraction has to provide some typedefs and methods

(and would be quite similar to GraphTraits):

typedef XXX NodeType;

typedef XXX ChildIteratorType;

typedef XXX NodesIteratorType;

getRoots(); // return all roots

getRoot(); // return the root if it is only one, othewise NULL

child_begin(NodeType* node); // iterators for children of a node

child_end(NodeType* node);

nodes_begin(); // iterators for the nodes of a node

nodes_end();

A concrete graph needs a constructor that stores a reference to the data

that is to look like a graph.

e.g.

struct BasicBlockGraph

{

Function& f;

BasicBlockGraph(Function& f) : f(f) {}

typedef BasicBlock NodeType;

...

child_begin(NodeType* node) {return succ_begin(node);}

child_begin(NodeType* node) {return succ_end(node);}

...

};

An invese graph is just another implementation

e.g.

struct BasicBlockInverseGraph

{

...

child_begin(NodeType* node) {return pred_begin(node);}

child_begin(NodeType* node) {return pred_end(node);}

...

};

And finally, the goal of the whole stuff, the simplification of

DominatorTreeBase::recalculate with some pseudocode:

void recalculate(Graph& graph) {

reset();

this->Vertex.push_back(0);

// Initialize roots

this->Roots = graph.getRoots();

iterate over roots {

this->IDoms[root] = 0;

this->DomTreeNodes[root] = 0;

}

Calculate(*this, graph);

}

Note that the flag IsPostDominators is gone.

Where necessary it can be replaced by checking if

the graph has exactly one root.

-Jochen