<br><br><div class="gmail_quote">On Thu, Apr 8, 2010 at 2:10 AM, Jochen Wilhelmy <span dir="ltr"><<a href="mailto:j.wilhelmy@arcor.de">j.wilhelmy@arcor.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
Hi!<br>
<br>
while trying to use llvm::DominatorTreeBase on a custom graph that<br>
has nothing to do with llvm::BasicBlock I ran into some difficulties,<br>
because llvm::DominatorTreeBase calls e.g. getParent()->front()<br>
directly on the nodes and uses llvm::Inverse which forced me to<br>
implement my GraphTraits also for Inverse.<br>
<br>
This could be solved using a compile time abstraction of Graph<br>
instread of GraphTraits.<br>
<br>
the abstraction has to provide some typedefs and methods<br>
(and would be quite similar to GraphTraits):<br>
<br>
typedef XXX NodeType;<br>
typedef XXX ChildIteratorType;<br>
typedef XXX NodesIteratorType;<br>
<br>
getRoots(); // return all roots<br>
getRoot(); // return the root if it is only one, othewise NULL<br></blockquote><div>or just add these methods to  GraphTraits?</div><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">

<br>
child_begin(NodeType* node); // iterators for children of a node<br>
child_end(NodeType* node);<br>
<br>
nodes_begin(); // iterators for the nodes of a node<br>
nodes_end();<br>
<br>
<br>
A concrete graph needs a constructor that stores a reference to the data<br>
that is to look like a graph.<br>
e.g.<br>
struct BasicBlockGraph<br>
{<br>
     Function& f;<br>
<br>
     BasicBlockGraph(Function& f) : f(f) {}<br>
<br>
     typedef BasicBlock NodeType;<br>
<br>
     ...<br>
   child_begin(NodeType* node) {return succ_begin(node);}<br>
   child_begin(NodeType* node) {return succ_end(node);}<br>
<br>
     ...<br>
};<br>
<br>
An invese graph is just another implementation<br>
e.g.<br>
struct BasicBlockInverseGraph<br>
{<br>
     ...<br>
<br>
   child_begin(NodeType* node) {return pred_begin(node);}<br>
   child_begin(NodeType* node) {return pred_end(node);}<br>
<br>
     ...<br>
};<br>
<br>
<br>
<br>
And finally, the goal of the whole stuff, the simplification of<br>
DominatorTreeBase::recalculate with some pseudocode:<br>
<br>
void recalculate(Graph& graph) {<br>
     reset();<br>
     this->Vertex.push_back(0);<br>
<br>
       // Initialize roots<br>
       this->Roots = graph.getRoots(); <br></blockquote><blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
     iterate over roots {<br>
       this->IDoms[root] = 0;<br>
       this->DomTreeNodes[root] = 0;<br>
     }<br>
<br>
       Calculate(*this, graph);<br>
   }<br>
<br>
<br>
Note that the flag IsPostDominators is gone.<br>
Where necessary it can be replaced by checking if<br>
the graph has exactly one root.<br>
<br>
-Jochen<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</blockquote></div><br>