diff options
4 files changed, 21 insertions, 7 deletions
diff --git a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h index f606e8d23c9..37da5617b91 100644 --- a/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h +++ b/llvm/include/llvm/Analysis/IteratedDominanceFrontier.h @@ -40,6 +40,9 @@ namespace llvm { /// This algorithm is a linear time computation of Iterated Dominance Frontiers, /// pruned using the live-in set. /// By default, liveness is not used to prune the IDF computation. +/// The template parameters should be either BasicBlock* or Inverse<BasicBlock +/// *>, depending on if you want the forward or reverse IDF. +template <class NodeTy> class IDFCalculator { public: @@ -88,5 +91,7 @@ private: const SmallPtrSetImpl<BasicBlock *> *DefBlocks; SmallVector<BasicBlock *, 32> PHIBlocks; }; +typedef IDFCalculator<BasicBlock *> ForwardIDFCalculator; +typedef IDFCalculator<Inverse<BasicBlock *>> ReverseIDFCalculator; } #endif diff --git a/llvm/lib/Analysis/IteratedDominanceFrontier.cpp b/llvm/lib/Analysis/IteratedDominanceFrontier.cpp index 9f1edd21820..3ab6b5d6090 100644 --- a/llvm/lib/Analysis/IteratedDominanceFrontier.cpp +++ b/llvm/lib/Analysis/IteratedDominanceFrontier.cpp @@ -16,9 +16,10 @@ #include "llvm/IR/Dominators.h" #include <queue> -using namespace llvm; - -void IDFCalculator::calculate(SmallVectorImpl<BasicBlock *> &PHIBlocks) { +namespace llvm { +template <class NodeTy> +void IDFCalculator<NodeTy>::calculate( + SmallVectorImpl<BasicBlock *> &PHIBlocks) { // If we haven't computed dominator tree levels, do so now. if (DomLevels.empty()) { for (auto DFI = df_begin(DT.getRootNode()), DFE = df_end(DT.getRootNode()); @@ -61,8 +62,12 @@ void IDFCalculator::calculate(SmallVectorImpl<BasicBlock *> &PHIBlocks) { while (!Worklist.empty()) { DomTreeNode *Node = Worklist.pop_back_val(); BasicBlock *BB = Node->getBlock(); - - for (auto Succ : successors(BB)) { + // Succ is the successor in the direction we are calculating IDF, so it is + // successor for IDF, and predecessor for Reverse IDF. + for (auto SuccIter = GraphTraits<NodeTy>::child_begin(BB), + End = GraphTraits<NodeTy>::child_end(BB); + SuccIter != End; ++SuccIter) { + BasicBlock *Succ = *SuccIter; DomTreeNode *SuccNode = DT.getNode(Succ); // Quickly skip all CFG edges that are also dominator tree edges instead @@ -93,3 +98,7 @@ void IDFCalculator::calculate(SmallVectorImpl<BasicBlock *> &PHIBlocks) { } } } + +template class IDFCalculator<BasicBlock *>; +template class IDFCalculator<Inverse<BasicBlock *>>; +} diff --git a/llvm/lib/Transforms/Utils/MemorySSA.cpp b/llvm/lib/Transforms/Utils/MemorySSA.cpp index 82248d1e8f3..e873c9e4c04 100644 --- a/llvm/lib/Transforms/Utils/MemorySSA.cpp +++ b/llvm/lib/Transforms/Utils/MemorySSA.cpp @@ -304,7 +304,7 @@ MemorySSAWalker *MemorySSA::buildMemorySSA(AliasAnalysis *AA, } // Determine where our MemoryPhi's should go - IDFCalculator IDFs(*DT); + ForwardIDFCalculator IDFs(*DT); IDFs.setDefiningBlocks(DefiningBlocks); IDFs.setLiveInBlocks(LiveInBlocks); SmallVector<BasicBlock *, 32> IDFBlocks; diff --git a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp index fba09e1a28c..cbf385d5633 100644 --- a/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ b/llvm/lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -523,7 +523,7 @@ void PromoteMem2Reg::run() { AllocaInfo Info; LargeBlockInfo LBI; - IDFCalculator IDF(DT); + ForwardIDFCalculator IDF(DT); for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { AllocaInst *AI = Allocas[AllocaNum]; |
