[LLVMdev] graph abstraction proposal

[Jochen Wilhelmy]

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