<div dir="ltr">Hi there,<br clear="all"><div><br></div><div style>I'm currently writing an analysis (for now) pass for LLVM that kind of need some information from the CallGraph of the program. This info would be extremely easy to get if I could build the DominatorTree information about the CallGraph. I even checked out and saw the declarations of GraphTraits templates for CallGraph and CallGraphNode, which might indicate that all algorithms that work with graphs in LLVM should work with CallGraphs, right?</div>
<div style><br></div><div style>Well, it doesn't; at least, not for the combination CallGraph & DominatorTree. Besides the fact that there is no implementation of inverse GraphTraits accesses for this graph (I don't mind at all about it -- I just wanted access the nodes on their standard order), I'm getting the set of compiler-time errors listed at the end of this email.</div>
<div style><br></div><div style>So, does anyone know if I could use the algorithms from DominatorTree in whichever GraphTraits templated classes? If not, could be possible to adapt at least the CallGraph to it?</div><div style>
<br></div><div style><div>Oh, and btw, my module pass has only this in its body (I just assumed I'm using it right, but maybe the problem is here):</div><div><br></div><div><p class=""><font color="#cc0000"><span class="">virtual</span> <span class="">bool</span> runOnModule(<span class="">Module</span> &M) {</font></p>
<p class=""><font color="#cc0000"><span class=""> </span>CallGraph<span class="">& cg = </span>getAnalysis<span class=""><</span>CallGraph<span class="">>();</span></font></p><p class=""><font color="#cc0000"><span class=""> </span>DominatorTreeBase<span class=""><</span>CallGraphNode<span class="">> *DTB;</span></font></p>
<p class=""><font color="#cc0000"><span class=""> DTB = </span><span class="">new</span><span class=""> </span>DominatorTreeBase<span class=""><</span>CallGraphNode<span class="">>(</span><span class="">false</span><span class="">);</span></font></p>
<p class=""><font color="#cc0000"> DTB-><span class="">recalculate</span>(cg);</font></p><p class=""><font color="#cc0000"><span class=""> </span><span class="">errs</span><span class="">() << </span>"DomTreeBase:"<span class="">;</span></font></p>
<p class=""><font color="#cc0000"> DTB-><span class="">print</span>(<span class="">errs</span>());</font></p><p class=""><font color="#cc0000"><span class=""> </span>return<span class=""> </span>false<span class="">;</span></font></p>
<p class=""><font color="#cc0000"> }</font></p><p class=""><br></p><p class=""><font color="#cc0000"> <span class="">virtual</span> <span class="">void</span> getAnalysisUsage(<span class="">AnalysisUsage</span> &AU) <span class="">const</span> {</font></p>
<p class=""><font color="#cc0000"><span class=""> AU.</span>addRequired<span class=""><</span>CallGraph<span class="">>();</span></font></p><p class=""><font color="#cc0000"><span class=""> </span></font><span style="color:rgb(204,0,0)">}</span></p>
<p class=""><font color="#cc0000"><br></font></p></div><div style>Error list:</div></div><div style>
<p class=""><font color="#0b5394">/Developer/llvm/include/llvm/Analysis/Dominators.h:666:35: error: no viable conversion from 'typename TraitsTy::nodes_iterator' (aka 'mapped_iterator<CallGraph::iterator, DerefFun>') to 'NodeType *' (aka 'llvm::CallGraphNode *')</font></p>
<p class=""><font color="#0b5394"> if (TraitsTy::child_begin(I) == TraitsTy::child_end(I))<br></font></p><p class=""><font color="#0b5394"> ^<br></font></p><p class=""><font color="#0b5394">/Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:59:10: note: in instantiation of function template specialization 'llvm::DominatorTreeBase<llvm::CallGraphNode>::recalculate<llvm::CallGraph>' requested here<br>
</font></p><p class=""><font color="#0b5394"> DTB->recalculate(cg);<br></font></p><p class=""><font color="#0b5394"> ^<br></font></p><p class=""><font color="#0b5394">/Developer/llvm/include/llvm/Analysis/CallGraph.h:319:57: note: passing argument to parameter 'N' here<br>
</font></p><p class=""><font color="#0b5394"> static inline ChildIteratorType child_begin(NodeType *N) {<br></font></p><p class=""><font color="#0b5394"> ^<br></font></p>
<p class=""><font color="#0b5394">In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.cpp:16:<br></font></p><p class=""><font color="#0b5394">In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:20:<br>
</font></p><p class=""><font color="#0b5394">In file included from /Developer/llvm/include/llvm/Analysis/PostDominators.h:17:<br></font></p><p class=""><font color="#0b5394">/Developer/llvm/include/llvm/Analysis/Dominators.h:670:9: error: no viable overloaded operator[] for type 'DenseMap<llvm::CallGraphNode *, llvm::CallGraphNode *>'<br>
</font></p><p class=""><font color="#0b5394"> this->IDoms[I] = 0;<br></font></p><p class=""><font color="#0b5394"> ^~~~~~~~~~~ ~<br></font></p><p class=""><font color="#0b5394">/Developer/llvm/include/llvm/ADT/DenseMap.h:215:11: note: candidate function not viable: no known conversion from 'typename TraitsTy::nodes_iterator' (aka 'mapped_iterator<CallGraph::iterator, DerefFun>') to 'llvm::CallGraphNode *const' for 1st argument; <br>
</font></p><p class=""><font color="#0b5394"> ValueT &operator[](const KeyT &Key) {<br></font></p><p class=""><font color="#0b5394"> ^<br></font></p><p class=""><font color="#0b5394">In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.cpp:16:<br>
</font></p><p class=""><font color="#0b5394">In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:20:<br></font></p><p class=""><font color="#0b5394">In file included from /Developer/llvm/include/llvm/Analysis/PostDominators.h:17:<br>
</font></p><p class=""><font color="#0b5394">/Developer/llvm/include/llvm/Analysis/Dominators.h:671:9: error: no viable overloaded operator[] for type 'DomTreeNodeMapType' (aka 'DenseMap<llvm::CallGraphNode *, DomTreeNodeBase<llvm::CallGraphNode> *>')<br>
</font></p><p class=""><font color="#0b5394"> this->DomTreeNodes[I] = 0;<br></font></p><p class=""><font color="#0b5394"> ^~~~~~~~~~~~~~~~~~ ~<br></font></p><p class=""><font color="#0b5394">/Developer/llvm/include/llvm/ADT/DenseMap.h:215:11: note: candidate function not viable: no known conversion from 'typename TraitsTy::nodes_iterator' (aka 'mapped_iterator<CallGraph::iterator, DerefFun>') to 'llvm::CallGraphNode *const' for 1st argument; <br>
</font></p><p class=""><font color="#0b5394"> ValueT &operator[](const KeyT &Key) {<br></font></p><p class=""><font color="#0b5394"> ^<br></font></p><p class=""><font color="#0b5394">In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.cpp:16:<br>
</font></p><p class=""><font color="#0b5394">In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:20:<br></font></p><p class=""><font color="#0b5394">In file included from /Developer/llvm/include/llvm/Analysis/PostDominators.h:17:<br>
</font></p><p class=""><font color="#0b5394">/Developer/llvm/include/llvm/Analysis/Dominators.h:158:5: error: use of undeclared identifier 'WriteAsOperand'<br></font></p><p class=""><font color="#0b5394"> WriteAsOperand(o, Node->getBlock(), false);<br>
</font></p><p class=""><font color="#0b5394"> ^<br></font></p><p class=""><font color="#0b5394">/Developer/llvm/include/llvm/Analysis/Dominators.h:170:41: note: in instantiation of function template specialization 'llvm::operator<<<llvm::CallGraphNode>' requested here</font></p>
<p class=""><font color="#0b5394"> o.indent(2*Lev) << "[" << Lev << "] " << N;</font></p><p class=""><font color="#0b5394"> ^</font></p>
<p class="">
<font color="#0b5394">/Developer/llvm/include/llvm/Analysis/Dominators.h:558:7: note: in instantiation of function template specialization 'llvm::PrintDomTree<llvm::CallGraphNode>' requested here</font></p>
<p class="">
<font color="#0b5394"> PrintDomTree<NodeT>(getRootNode(), o, 1);</font></p><p class=""><font color="#0b5394"> ^</font></p><p class=""><font color="#0b5394">/Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:61:10: note: in instantiation of member function 'llvm::DominatorTreeBase<llvm::CallGraphNode>::print' requested here</font></p>
<p class=""><font color="#0b5394"> DTB->print(errs());</font></p><p class=""><font color="#0b5394"> ^</font></p><p class=""><font color="#0b5394">4 errors generated.</font></p><p class=""><br></p></div><div style>
Cheers,<br></div><div><br>--<br>Cristianno Martins<br>PhD Student of Computer Science<br>University of Campinas<br><a href="mailto:cmartins@ic.unicamp.br" target="_blank">cmartins@ic.unicamp.br</a><br><a href="mailto:cristiannomartins@hotmail.com" target="_blank"></a></div>
</div>