[LLVMdev] graph abstraction proposal

[Tobias Grosser]

On 04/07/2010 08:10 PM, Jochen Wilhelmy wrote:
> 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