[LLVMdev] Dominator Trees

Speziale Ettore speziale.ettore at gmail.com
Fri Oct 31 17:42:45 PDT 2014

Hello everyone,

I would like to implement a query to check if a node in the CallGraph
dominates another CallGraph node. I thus started specializing
DomTreeNodeBase and DominatorTreeBase such as I can have
CallGraphDomTreeNode and CallGraphDominatorTree.

After allocating the tree, I call
DomTreeNode<CallGraphNode>::recalculate(CallGraph &). However, I cannot
instantiate the template as it does seem the part of that function dealing
with initializing the post-dominator roots:

00692       // Initialize the roots list
00693       for (typename TraitsTy::nodes_iterator I =
00694                                         E = TraitsTy::nodes_end(&F);
I != E; ++I) {
00695         if (TraitsTy::child_begin(I) == TraitsTy::child_end(I))
00696           addRoot(I);
00698         // Prepopulate maps so that we don't get iterator
invalidation issues later.
00699         this->IDoms[I] = nullptr;
00700         this->DomTreeNodes[I] = nullptr;
00701       }

implicitly assumes that it should be possible to convert a
TraitsTy::nodes_iterator into a NodeT *.

In my case, TraitsTy is GraphTraits<CallGraph *> and NodeT is
CallGraphNode. I was able to understand that this works fine for the
DominatorTree class, as the corresponding TraitsTy::nodes_iterator is a
iplist<BasicBlock>::iterator, which provides a type-cast operator to
BasicBlock *. I was also able to understand the error I got, since the same
operator is missing for GraphTraits<CallGraph *>::nodes_iterator.

My question is whether the ability of casting a
GraphTraits<Ty>::nodes_iterator into a NodeT * is a mandatory requirement
for using DominatorTreeBase.

Ettore Speziale
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141031/a7a7d18d/attachment.html>

More information about the llvm-dev mailing list