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

Yes this is a problem. However how is it related to your proposal? Do you want to add a getParent call to your graph class?

and uses llvm::Inverse which forced me to
implement my GraphTraits also for Inverse.

Yes.

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):

I definitely support adding multiple tree roots to the graph interface. This will allow the DOTGraphTraits based printers to not only print trees.

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);}

      ...
};

But here you also have to implement the inverse. Not for GraphTraits but for your Graph class.

Like ether I do not understand why GraphTraits cannot be extended to also implement:

getRoots(); // return all roots

What is the advantage of your approach? Are you thinking to port all the other GraphTraits implementations. I would not like to have to graph interfaces in LLVM.

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.

I am not sure about this.

Something not yet implemented are postdominator trees for infinite loops. At the moment these basic blocks are just not part of the postdominator tree. I believe a solution will require to add some virtual edges to some of the basic blocks that are not touched by the dfs of the dominator tree algorithm. As this is only required for postdominance trees the isPostDominators() might be necessary to check if the edges have to be added.
Using the number of roots to check if this is a post dominance analysis does not seem sufficient. There are inverse CFGs that have just one root, no?
Otherwise we might be able to get rid of the isPostDominators. I would love this.

Looking forward to your feedback. PostDominators and GraphTraits really needs some discussion

Tobi