[LLVMdev] CallGraph, GraphTraits and DominatorTree

[Cristianno Martins]

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<CallGraph>();

    DominatorTreeBase<CallGraphNode> *DTB;

    DTB = new DominatorTreeBase<CallGraphNode>(false);

    DTB->recalculate(cg);

    errs() << "DomTreeBase:";

    DTB->print(errs());

    return false;

  }


  virtual void getAnalysisUsage(AnalysisUsage &AU) const {

    AU.addRequired<CallGraph>();

  }


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::DominatorTreeBase<llvm::CallGraphNode>::recalculate<llvm::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 *, DomTreeNodeBase<llvm::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::PrintDomTree<llvm::CallGraphNode>' requested here

      PrintDomTree<NodeT>(getRootNode(), o, 1);

      ^

/Developer/llvm/lib/Transforms/ThreadBufferOptimizer/ThreadBufferOptimizer.h:61:10:
note: in instantiation of member function
'llvm::DominatorTreeBase<llvm::CallGraphNode>::print' requested here

    DTB->print(errs());

         ^

4 errors generated.


Cheers,

--
Cristianno Martins
PhD Student of Computer Science
University of Campinas
cmartins at ic.unicamp.br
<cristiannomartins at hotmail.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130605/e2917c8f/attachment.html>