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
