CallGraph, GraphTraits and DominatorTree

Hi there,

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?

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.

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?

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):

virtual bool runOnModule(Module &M) {

CallGraph& cg = getAnalysis();

DominatorTreeBase *DTB;

DTB = new DominatorTreeBase(false);

DTB->recalculate(cg);

errs() << “DomTreeBase:”;

DTB->print(errs());

return false;

}

virtual void getAnalysisUsage(AnalysisUsage &AU) const {

AU.addRequired();

}

Error list:

/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 *’)

if (TraitsTy::child_begin(I) == TraitsTy::child_end(I))

^

/Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:59:10: note: in instantiation of function template specialization ‘llvm::DominatorTreeBasellvm::CallGraphNode::recalculatellvm::CallGraph’ requested here

DTB->recalculate(cg);

^

/Developer/llvm/include/llvm/Analysis/CallGraph.h:319:57: note: passing argument to parameter ‘N’ here

static inline ChildIteratorType child_begin(NodeType *N) {

^

In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.cpp:16:

In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:20:

In file included from /Developer/llvm/include/llvm/Analysis/PostDominators.h:17:

/Developer/llvm/include/llvm/Analysis/Dominators.h:670:9: error: no viable overloaded operator for type ‘DenseMap<llvm::CallGraphNode *, llvm::CallGraphNode *>’

this->IDoms[I] = 0;

^~~~~~~~~~~ ~

/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;

ValueT &operator(const KeyT &Key) {

^

In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.cpp:16:

In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:20:

In file included from /Developer/llvm/include/llvm/Analysis/PostDominators.h:17:

/Developer/llvm/include/llvm/Analysis/Dominators.h:671:9: error: no viable overloaded operator for type ‘DomTreeNodeMapType’ (aka ‘DenseMap<llvm::CallGraphNode *, DomTreeNodeBasellvm::CallGraphNode *>’)

this->DomTreeNodes[I] = 0;

^~~~~~~~~~~~~~~~~~ ~

/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;

ValueT &operator(const KeyT &Key) {

^

In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.cpp:16:

In file included from /Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:20:

In file included from /Developer/llvm/include/llvm/Analysis/PostDominators.h:17:

/Developer/llvm/include/llvm/Analysis/Dominators.h:158:5: error: use of undeclared identifier ‘WriteAsOperand’

WriteAsOperand(o, Node->getBlock(), false);

^

/Developer/llvm/include/llvm/Analysis/Dominators.h:170:41: note: in instantiation of function template specialization ‘llvm::operator<<llvm::CallGraphNode’ requested here

o.indent(2*Lev) << “[” << Lev << "] " << N;

^

/Developer/llvm/include/llvm/Analysis/Dominators.h:558:7: note: in instantiation of function template specialization ‘llvm::PrintDomTreellvm::CallGraphNode’ requested here

PrintDomTree(getRootNode(), o, 1);

^

/Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:61:10: note: in instantiation of member function ‘llvm::DominatorTreeBasellvm::CallGraphNode::print’ requested here

DTB->print(errs());

^

4 errors generated.

Cheers,