# [LLVMdev] graph abstraction proposal

Jochen Wilhelmy j.wilhelmy at arcor.de
Wed Apr 7 11:10:02 PDT 2010

```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

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

```