Replace custom getNumPreds/etc with PredIteratorCache that does the same thing

[• dberlin]

Summary

Replace getting predecessors and predecessor counts with predcache.

Dunno whether it makes sense to be fully lazy, but if we are, we might as well
do it the "standard" way.

[qcolombet]

Hi Daniel,

Don’t know either if that makes sense, but LGTM ;).

Cheers,
-Quentin

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

269

Period at the end of the comment ;).

[• dberlin]

FWIW, while I did not speed test *this* change, In timings elsewhere,
i've found that PredIteratorCache is often slower than the pred
iterator for counting preds
(because it copies the pred list), and only faster in really
degenerate cases for walking preds.

So i'm not going to submit this.

[Eugene.Zelenko]

Should it be abandoned?

lib/Transforms/Utils/PromoteMemoryToRegister.cpp

 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/PredIteratorCache.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 using namespace llvm;
 
 #define DEBUG_TYPE "mem2reg"
 
 STATISTIC(NumLocalPromoted, "Number of alloca's promoted within one block");
 STATISTIC(NumSingleStore,   "Number of alloca's promoted with a single store");
struct PromoteMem2Reg {
   /// The set of basic blocks the renamer has already visited.
   ///
   SmallPtrSet<BasicBlock *, 16> Visited;
 
   /// Contains a stable numbering of basic blocks to avoid non-determinstic
   /// behavior.
   DenseMap<BasicBlock *, unsigned> BBNumbers;
 
-  /// Lazily compute the number of predecessors a block has.
-  DenseMap<const BasicBlock *, unsigned> BBNumPreds;
+  /// Cache of predecessor info
+  PredIteratorCache PredCache;
 
 public:
   PromoteMem2Reg(ArrayRef<AllocaInst *> Allocas, DominatorTree &DT,
                  AliasSetTracker *AST, AssumptionCache *AC)
       : Allocas(Allocas.begin(), Allocas.end()), DT(DT),
         DIB(*DT.getRoot()->getParent()->getParent(), /*AllowUnresolved*/ false),
         AST(AST), AC(AC) {}
 
   void run();
 
 private:
   void RemoveFromAllocasList(unsigned &AllocaIdx) {
     Allocas[AllocaIdx] = Allocas.back();
     Allocas.pop_back();
     --AllocaIdx;
   }
 
-  unsigned getNumPreds(const BasicBlock *BB) {
-    unsigned &NP = BBNumPreds[BB];
-    if (NP == 0)
-      NP = std::distance(pred_begin(BB), pred_end(BB)) + 1;
-    return NP - 1;
-  }
-
   void ComputeLiveInBlocks(AllocaInst *AI, AllocaInfo &Info,
                            const SmallPtrSetImpl<BasicBlock *> &DefBlocks,
                            SmallPtrSetImpl<BasicBlock *> &LiveInBlocks);
   void RenamePass(BasicBlock *BB, BasicBlock *Pred,
                   RenamePassData::ValVector &IncVals,
                   std::vector<RenamePassData> &Worklist);
   bool QueuePhiNode(BasicBlock *BB, unsigned AllocaIdx, unsigned &Version);
 };
for (DenseMap<std::pair<unsigned, unsigned>, PHINode *>::iterator
     PHINode *SomePHI = I->second;
     BasicBlock *BB = SomePHI->getParent();
     if (&BB->front() != SomePHI)
       continue;
 
     // Only do work here if there the PHI nodes are missing incoming values.  We
     // know that all PHI nodes that were inserted in a block will have the same
     // number of incoming values, so we can just check any of them.
-    if (SomePHI->getNumIncomingValues() == getNumPreds(BB))
+    if (SomePHI->getNumIncomingValues() == PredCache.GetNumPreds(BB))
       continue;
 
     // Get the preds for BB.
-    SmallVector<BasicBlock *, 16> Preds(pred_begin(BB), pred_end(BB));
+    ArrayRef<BasicBlock *> PredRef =
+        makeArrayRef(PredCache.GetPreds(BB), PredCache.GetNumPreds(BB));
+    SmallVector<BasicBlock *, 16> Preds(PredRef.begin(), PredRef.end());
 
     // Ok, now we know that all of the PHI nodes are missing entries for some
     // basic blocks.  Start by sorting the incoming predecessors for efficient
     // access.
     std::sort(Preds.begin(), Preds.end());
 
     // Now we loop through all BB's which have entries in SomePHI and remove
     // them from the Preds list.
while (!LiveInBlockWorklist.empty()) {
     // The block really is live in here, insert it into the set.  If already in
     // the set, then it has already been processed.
     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.  Add the preds to the worklist unless they are a
     // defining block.
-    for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+    for (BasicBlock **PI = PredCache.GetPreds(BB); *PI; ++PI) {
       BasicBlock *P = *PI;
 
       // The value is not live into a predecessor if it defines the value.
       if (DefBlocks.count(P))
         continue;
 
       // Otherwise it is, add to the worklist.
       LiveInBlockWorklist.push_back(P);
bool PromoteMem2Reg::QueuePhiNode(BasicBlock *BB, unsigned AllocaNo,
   PHINode *&PN = NewPhiNodes[std::make_pair(BBNumbers[BB], AllocaNo)];
 
   // If the BB already has a phi node added for the i'th alloca then we're done!
   if (PN)
     return false;
 
   // Create a PhiNode using the dereferenced type... and add the phi-node to the
   // BasicBlock.
-  PN = PHINode::Create(Allocas[AllocaNo]->getAllocatedType(), getNumPreds(BB),
-                       Allocas[AllocaNo]->getName() + "." + Twine(Version++),
-                       BB->begin());
+  PN = PHINode::Create(
+      Allocas[AllocaNo]->getAllocatedType(), PredCache.GetNumPreds(BB),
+      Allocas[AllocaNo]->getName() + "." + Twine(Version++), BB->begin());
   ++NumPHIInsert;
   PhiToAllocaMap[PN] = AllocaNo;
 
   if (AST && PN->getType()->isPointerTy())
     AST->copyValue(PointerAllocaValues[AllocaNo], PN);
 
   return true;
 }