Correct IDF calculator for ReverseIDF

[• dberlin]

Summary

Need to use predecessors for reverse graph, successors for forward graph.
succ_iterator/pred_iterator are not compatible, this patch is all the work necessary to work around that (which is what everywhere else does). Not sure if there is a better way, so cc'ing some random folks to take a gander :)

[qcolombet]

Hi Daniel,

Looks reasonable to me.
Maybe a typedef to add a bit of syntactic sugar.

Cheers,
-Quentin

lib/Analysis/IteratedDominanceFrontier.cpp

103

Perhaps typedef those so that clients explicitly use forward or reverse IDF?

[• dberlin]

Update with typedefs

include/llvm/Analysis/IteratedDominanceFrontier.h

 /// \brief Determine the iterated dominance frontier, given a set of defining
 /// blocks, and optionally, a set of live-in blocks.
 ///
 /// In turn, the results can be used to place phi nodes.
 ///
 /// 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:
   IDFCalculator(DominatorTreeBase<BasicBlock> &DT) : DT(DT), useLiveIn(false) {}
 
   /// \brief Give the IDF calculator the set of blocks in which the value is
   /// defined.  This is equivalent to the set of starting blocks it should be
   /// calculating the IDF for (though later gets pruned based on liveness).

 private:
   DominatorTreeBase<BasicBlock> &DT;
   bool useLiveIn;
   DenseMap<DomTreeNode *, unsigned> DomLevels;
   const SmallPtrSetImpl<BasicBlock *> *LiveInBlocks;
   const SmallPtrSetImpl<BasicBlock *> *DefBlocks;
   SmallVector<BasicBlock *, 32> PHIBlocks;
 };
+typedef IDFCalculator<BasicBlock *> ForwardIDFCalculator;
+typedef IDFCalculator<Inverse<BasicBlock *>> ReverseIDFCalculator;
 }
 #endif

lib/Analysis/IteratedDominanceFrontier.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/IR/CFG.h"
 #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());
          DFI != DFE; ++DFI) {
       DomLevels[*DFI] = DFI.getPathLength() - 1;
     }
   }
 
while (!PQ.empty()) {
 
     Worklist.clear();
     Worklist.push_back(Root);
     VisitedWorklist.insert(Root);
 
     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
         // of catching them below.
         if (SuccNode->getIDom() == Node)
           continue;
 
         unsigned SuccLevel = DomLevels.lookup(SuccNode);
while (!Worklist.empty()) {
 
       for (auto DomChild : *Node) {
         if (VisitedWorklist.insert(DomChild).second)
           Worklist.push_back(DomChild);
       }
     }
   }
 }
+
+template class IDFCalculator<BasicBlock *>;
+template class IDFCalculator<Inverse<BasicBlock *>>;
+}

lib/Transforms/Utils/MemorySSA.cpp

if (!LiveInBlocks.insert(BB).second)
       continue;
 
     // Since the value is live into BB, it is either defined in a predecessor or
     // live into it to.
     LiveInBlockWorklist.append(pred_begin(BB), pred_end(BB));
   }
 
   // Determine where our MemoryPhi's should go
-  IDFCalculator IDFs(*DT);
+  ForwardIDFCalculator IDFs(*DT);
   IDFs.setDefiningBlocks(DefiningBlocks);
   IDFs.setLiveInBlocks(LiveInBlocks);
   SmallVector<BasicBlock *, 32> IDFBlocks;
   IDFs.calculate(IDFBlocks);
 
   // Now place MemoryPhi nodes.
   for (auto &BB : IDFBlocks) {
     // Insert phi node

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

void PromoteMem2Reg::run() {
   Function &F = *DT.getRoot()->getParent();
 
   if (AST)
     PointerAllocaValues.resize(Allocas.size());
   AllocaDbgDeclares.resize(Allocas.size());
 
   AllocaInfo Info;
   LargeBlockInfo LBI;
-  IDFCalculator IDF(DT);
+  ForwardIDFCalculator IDF(DT);
 
   for (unsigned AllocaNum = 0; AllocaNum != Allocas.size(); ++AllocaNum) {
     AllocaInst *AI = Allocas[AllocaNum];
 
     assert(isAllocaPromotable(AI) && "Cannot promote non-promotable alloca!");
     assert(AI->getParent()->getParent() == &F &&
            "All allocas should be in the same function, which is same as DF!");