[LLVMdev] graph abstraction proposal

[ether zhhb]

On Thu, Apr 8, 2010 at 2:10 AM, Jochen Wilhelmy <j.wilhelmy at arcor.de> 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 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
>
or just add these methods to  GraphTraits?

>
> 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
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100408/a4d45e45/attachment.html>