[LLVMdev] graph abstraction proposal
ether zhhb
etherzhhb at gmail.com
Wed Apr 7 19:34:40 PDT 2010
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>
More information about the llvm-dev
mailing list