# graph abstraction proposal

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

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

or just add these methods to GraphTraits?

or just add these methods to GraphTraits?

in an actual implementation one would add them to GraphTraits,
but I would also suggest renaming e.g. GraphTraits<BasicBlock> to
BaicBlockGraph since traits are used to get properies of types
while I suggest a compile time abstraction (which is a class
that contains all data or has a reference to it, just like a runtime
abstraction where the methods would be virtual).

what do you think of this suggestion?

-Jochen