diff options
author | Anna Zaks <ganna@apple.com> | 2011-12-05 19:17:04 +0000 |
---|---|---|
committer | Anna Zaks <ganna@apple.com> | 2011-12-05 19:17:04 +0000 |
commit | e15402f92b6949d2474cc82648239fe22e5a2209 (patch) | |
tree | 3a8d9b6a4490722e9480b6fba1c0617086a3fd45 | |
parent | fef3f9aed38950877deff6c55331f42dfd852c1c (diff) | |
download | llvm-e15402f92b6949d2474cc82648239fe22e5a2209.tar.gz llvm-e15402f92b6949d2474cc82648239fe22e5a2209.tar.bz2 llvm-e15402f92b6949d2474cc82648239fe22e5a2209.tar.xz |
Change the Dominators recalculate() function to only rely on GraphTraits
This is a patch by Guoping Long!
As part of utilizing LLVM Dominator computation in Clang, made two changes to LLVM dominators tree implementation:
- (1) Change the recalculate() template function to only rely on GraphTraits.
- (2) Add a size() method to GraphTraits template class to query the number of nodes in the graph.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@145837 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/ADT/GraphTraits.h | 5 | ||||
-rw-r--r-- | include/llvm/Analysis/DominatorInternals.h | 2 | ||||
-rw-r--r-- | include/llvm/Analysis/Dominators.h | 15 | ||||
-rw-r--r-- | include/llvm/CodeGen/MachineFunction.h | 4 | ||||
-rw-r--r-- | include/llvm/Support/CFG.h | 2 |
5 files changed, 20 insertions, 8 deletions
diff --git a/include/llvm/ADT/GraphTraits.h b/include/llvm/ADT/GraphTraits.h index 0fd1f5022a..823caef764 100644 --- a/include/llvm/ADT/GraphTraits.h +++ b/include/llvm/ADT/GraphTraits.h @@ -43,9 +43,12 @@ struct GraphTraits { // typedef ...iterator nodes_iterator; // static nodes_iterator nodes_begin(GraphType *G) // static nodes_iterator nodes_end (GraphType *G) - // // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + // static unsigned size (GraphType *G) + // Return total number of nodes in the graph + // + // If anyone tries to use this class without having an appropriate // specialization, make an error. If you get this error, it's because you diff --git a/include/llvm/Analysis/DominatorInternals.h b/include/llvm/Analysis/DominatorInternals.h index ae552b05ab..0c29236dde 100644 --- a/include/llvm/Analysis/DominatorInternals.h +++ b/include/llvm/Analysis/DominatorInternals.h @@ -171,7 +171,7 @@ void Calculate(DominatorTreeBase<typename GraphTraits<NodeT>::NodeType>& DT, // it might be that some blocks did not get a DFS number (e.g., blocks of // infinite loops). In these cases an artificial exit node is required. - MultipleRoots |= (DT.isPostDominator() && N != F.size()); + MultipleRoots |= (DT.isPostDominator() && N != GraphTraits<FuncT*>::size(&F)); // When naively implemented, the Lengauer-Tarjan algorithm requires a separate // bucket for each vertex. However, this is unnecessary, because each vertex diff --git a/include/llvm/Analysis/Dominators.h b/include/llvm/Analysis/Dominators.h index 230e83d301..15db2d1418 100644 --- a/include/llvm/Analysis/Dominators.h +++ b/include/llvm/Analysis/Dominators.h @@ -653,21 +653,24 @@ public: /// recalculate - compute a dominator tree for the given function template<class FT> void recalculate(FT& F) { + typedef GraphTraits<FT*> TraitsTy; reset(); this->Vertex.push_back(0); if (!this->IsPostDominators) { // Initialize root - this->Roots.push_back(&F.front()); - this->IDoms[&F.front()] = 0; - this->DomTreeNodes[&F.front()] = 0; + NodeT *entry = TraitsTy::getEntryNode(&F); + this->Roots.push_back(entry); + this->IDoms[entry] = 0; + this->DomTreeNodes[entry] = 0; Calculate<FT, NodeT*>(*this, F); } else { // Initialize the roots list - for (typename FT::iterator I = F.begin(), E = F.end(); I != E; ++I) { - if (std::distance(GraphTraits<FT*>::child_begin(I), - GraphTraits<FT*>::child_end(I)) == 0) + for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), + E = TraitsTy::nodes_end(&F); I != E; ++I) { + if (std::distance(TraitsTy::child_begin(I), + TraitsTy::child_end(I)) == 0) addRoot(I); // Prepopulate maps so that we don't get iterator invalidation issues later. diff --git a/include/llvm/CodeGen/MachineFunction.h b/include/llvm/CodeGen/MachineFunction.h index 6e08f7b050..61cebff375 100644 --- a/include/llvm/CodeGen/MachineFunction.h +++ b/include/llvm/CodeGen/MachineFunction.h @@ -437,6 +437,7 @@ template <> struct GraphTraits<MachineFunction*> : typedef MachineFunction::iterator nodes_iterator; static nodes_iterator nodes_begin(MachineFunction *F) { return F->begin(); } static nodes_iterator nodes_end (MachineFunction *F) { return F->end(); } + static unsigned size (MachineFunction *F) { return F->size(); } }; template <> struct GraphTraits<const MachineFunction*> : public GraphTraits<const MachineBasicBlock*> { @@ -452,6 +453,9 @@ template <> struct GraphTraits<const MachineFunction*> : static nodes_iterator nodes_end (const MachineFunction *F) { return F->end(); } + static unsigned size (const MachineFunction *F) { + return F->size(); + } }; diff --git a/include/llvm/Support/CFG.h b/include/llvm/Support/CFG.h index 29313ef900..6e354f9a1e 100644 --- a/include/llvm/Support/CFG.h +++ b/include/llvm/Support/CFG.h @@ -314,6 +314,7 @@ template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> { typedef Function::iterator nodes_iterator; static nodes_iterator nodes_begin(Function *F) { return F->begin(); } static nodes_iterator nodes_end (Function *F) { return F->end(); } + static unsigned size (Function *F) { return F->size(); } }; template <> struct GraphTraits<const Function*> : public GraphTraits<const BasicBlock*> { @@ -323,6 +324,7 @@ template <> struct GraphTraits<const Function*> : typedef Function::const_iterator nodes_iterator; static nodes_iterator nodes_begin(const Function *F) { return F->begin(); } static nodes_iterator nodes_end (const Function *F) { return F->end(); } + static unsigned size (const Function *F) { return F->size(); } }; |