Index: include/llvm/Analysis/IteratedDominanceFrontier.h =================================================================== --- include/llvm/Analysis/IteratedDominanceFrontier.h +++ include/llvm/Analysis/IteratedDominanceFrontier.h @@ -40,6 +40,9 @@ /// 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, depending on if you want the forward or reverse IDF. +template class IDFCalculator { public: @@ -88,5 +91,7 @@ const SmallPtrSetImpl *DefBlocks; SmallVector PHIBlocks; }; +typedef IDFCalculator ForwardIDFCalculator; +typedef IDFCalculator> ReverseIDFCalculator; } #endif Index: lib/Analysis/IteratedDominanceFrontier.cpp =================================================================== --- lib/Analysis/IteratedDominanceFrontier.cpp +++ lib/Analysis/IteratedDominanceFrontier.cpp @@ -16,9 +16,10 @@ #include "llvm/IR/Dominators.h" #include -using namespace llvm; - -void IDFCalculator::calculate(SmallVectorImpl &PHIBlocks) { +namespace llvm { +template +void IDFCalculator::calculate( + SmallVectorImpl &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 @@ 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::child_begin(BB), + End = GraphTraits::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 @@ } } } + +template class IDFCalculator; +template class IDFCalculator>; +} Index: lib/Transforms/Utils/MemorySSA.cpp =================================================================== --- lib/Transforms/Utils/MemorySSA.cpp +++ lib/Transforms/Utils/MemorySSA.cpp @@ -304,7 +304,7 @@ } // Determine where our MemoryPhi's should go - IDFCalculator IDFs(*DT); + ForwardIDFCalculator IDFs(*DT); IDFs.setDefiningBlocks(DefiningBlocks); IDFs.setLiveInBlocks(LiveInBlocks); SmallVector IDFBlocks; Index: lib/Transforms/Utils/PromoteMemoryToRegister.cpp =================================================================== --- lib/Transforms/Utils/PromoteMemoryToRegister.cpp +++ lib/Transforms/Utils/PromoteMemoryToRegister.cpp @@ -523,7 +523,7 @@ AllocaInfo Info; LargeBlockInfo LBI; - IDFCalculator IDF(DT); + ForwardIDFCalculator IDF(DT); for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) { AllocaInst *AI = Allocas[AllocaNum];