[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
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
More information about the llvm-dev
mailing list