llvm dev - Apr 2010 - [LLVMdev] 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 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

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

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>

> or just add these methods to  GraphTraits?
in an actual implementation one would add them to GraphTraits,
but I would also suggest renaming e.g. GraphTraits<BasicBlock> to
BaicBlockGraph since traits are used to get properies of types
while I suggest a compile time abstraction (which is a class
that contains all data or has a reference to it, just like a runtime
abstraction where the methods would be virtual).

what do you think of this suggestion?

-Jochen