[LLVMdev] graph abstraction proposal

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


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

A concrete graph needs a constructor that stores a reference to the data
that is to look like a graph.
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
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) {

       // 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.


More information about the llvm-dev mailing list