Add iterator and iterator range to PredIteratorCache

[• dberlin]

Summary

This lets us use range based for loops, and generally makes the interface much closer to
normal pred iterators.

[• dberlin]

Update to make interface more consistent with normal pred interface

[dblaikie]

Looks reasonable.

Optional: Rather than having range access as a free function and begin/end as member functions, I'd be inclined to put them at the same level, or possibly even go without begin/end entirely and just have:

PredCache.predecessors(BB);

(or s/predecessors/cached_predecessors/ - though of course both names are somewhat redundant with the name of the object... - maybe it should just be PredCache.get(BB); or something? )

[• dberlin]

The redundancy is why i made it a free function, but happy to make it
a member function.

The liklihood we would ever have cached_predecessors(something else) seems low.
:)

I don't see any loops that use begin()/end(), so i'll delete them for now.

I'll make cached_predecessors a member function named get, and if we
find a use for begin/end later, we can add them then.

llvm/trunk/include/llvm/Analysis/MemoryDependenceAnalysis.h

 #ifndef LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H
 #define LLVM_ANALYSIS_MEMORYDEPENDENCEANALYSIS_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/PredIteratorCache.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 
 namespace llvm {
   class Function;
   class FunctionPass;
   class Instruction;
   class CallSite;
private:
 
     // A reverse mapping from dependencies to the non-local dependees.
     ReverseDepMapType ReverseNonLocalDeps;
 
     /// Current AA implementation, just a cache.
     AliasAnalysis *AA;
     DominatorTree *DT;
     AssumptionCache *AC;
-    std::unique_ptr<PredIteratorCache> PredCache;
+    PredIteratorCache PredCache;
 
   public:
     MemoryDependenceAnalysis();
     ~MemoryDependenceAnalysis() override;
     static char ID;
 
     /// Pass Implementation stuff.  This doesn't do any analysis eagerly.
     bool runOnFunction(Function &) override;

llvm/trunk/include/llvm/IR/PredIteratorCache.h

 //===- PredIteratorCache.h - pred_iterator Cache ----------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the PredIteratorCache class.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_PREDITERATORCACHE_H
 #define LLVM_IR_PREDITERATORCACHE_H
 
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/Support/Allocator.h"
 
 namespace llvm {
 
-  /// PredIteratorCache - This class is an extremely trivial cache for
-  /// predecessor iterator queries.  This is useful for code that repeatedly
-  /// wants the predecessor list for the same blocks.
-  class PredIteratorCache {
-    /// BlockToPredsMap - Pointer to null-terminated list.
-    DenseMap<BasicBlock*, BasicBlock**> BlockToPredsMap;
-    DenseMap<BasicBlock*, unsigned> BlockToPredCountMap;
+  DenseMap<BasicBlock *, BasicBlock **> BlockToPredsMap;
+  DenseMap<BasicBlock *, unsigned> BlockToPredCountMap;
 
-    /// Memory - This is the space that holds cached preds.
-    BumpPtrAllocator Memory;
-  public:
 
-    /// GetPreds - Get a cached list for the null-terminated predecessor list of
-    /// the specified block.  This can be used in a loop like this:
-    ///   for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI)
-    ///      use(*PI);
-    /// instead of:
-    /// for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
-    BasicBlock **GetPreds(BasicBlock *BB) {
-      BasicBlock **&Entry = BlockToPredsMap[BB];
-      if (Entry) return Entry;
+private:
+    if (Entry)
+      return Entry;
 
-      SmallVector<BasicBlock*, 32> PredCache(pred_begin(BB), pred_end(BB));
-      PredCache.push_back(nullptr); // null terminator.
-      
-      BlockToPredCountMap[BB] = PredCache.size()-1;
+    SmallVector<BasicBlock *, 32> PredCache(pred_begin(BB), pred_end(BB));
+    BlockToPredCountMap[BB] = PredCache.size() - 1;
 
-      Entry = Memory.Allocate<BasicBlock*>(PredCache.size());
-      std::copy(PredCache.begin(), PredCache.end(), Entry);
-      return Entry;
-    }
-    
-    unsigned GetNumPreds(BasicBlock *BB) {
-      GetPreds(BB);
-      return BlockToPredCountMap[BB];
-    }
+    Entry = Memory.Allocate<BasicBlock *>(PredCache.size());
 
-    /// clear - Remove all information.
-    void clear() {
-      BlockToPredsMap.clear();
-      BlockToPredCountMap.clear();
-      Memory.Reset();
-    }
-  };
+public:
+  size_t size(BasicBlock *BB) { return GetNumPreds(BB); }
+  ArrayRef<BasicBlock *> get(BasicBlock *BB) {
+    return makeArrayRef(GetPreds(BB), GetNumPreds(BB));
+  }
+
+
 } // end namespace llvm
 
 #endif

llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp

 INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
                 "Memory Dependence Analysis", false, true)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
 INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
                       "Memory Dependence Analysis", false, true)
 
 MemoryDependenceAnalysis::MemoryDependenceAnalysis()
-    : FunctionPass(ID), PredCache() {
+    : FunctionPass(ID) {
   initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry());
 }
 MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
 }
 
 /// Clean up memory in between runs
 void MemoryDependenceAnalysis::releaseMemory() {
   LocalDeps.clear();
   NonLocalDeps.clear();
   NonLocalPointerDeps.clear();
   ReverseLocalDeps.clear();
   ReverseNonLocalDeps.clear();
   ReverseNonLocalPtrDeps.clear();
-  PredCache->clear();
+  PredCache.clear();
 }
 
 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
 ///
 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequiredTransitive<AliasAnalysis>();
 }
 
 bool MemoryDependenceAnalysis::runOnFunction(Function &F) {
   AA = &getAnalysis<AliasAnalysis>();
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
   DominatorTreeWrapperPass *DTWP =
       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
   DT = DTWP ? &DTWP->getDomTree() : nullptr;
-  if (!PredCache)
-    PredCache.reset(new PredIteratorCache());
   return false;
 }
 
 /// RemoveFromReverseMap - This is a helper function that removes Val from
 /// 'Inst's set in ReverseMap.  If the set becomes empty, remove Inst's entry.
 template <typename KeyTy>
 static void RemoveFromReverseMap(DenseMap<Instruction*,
                                  SmallPtrSet<KeyTy, 4> > &ReverseMap,
if (!Cache.empty()) {
     std::sort(Cache.begin(), Cache.end());
 
     ++NumCacheDirtyNonLocal;
     //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
     //     << Cache.size() << " cached: " << *QueryInst;
   } else {
     // Seed DirtyBlocks with each of the preds of QueryInst's block.
     BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
-    for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
-      DirtyBlocks.push_back(*PI);
+    for (BasicBlock *Pred : PredCache.get(QueryBB))
+      DirtyBlocks.push_back(Pred);
     ++NumUncacheNonLocal;
   }
 
   // isReadonlyCall - If this is a read-only call, we can be more aggressive.
   bool isReadonlyCall = AA->onlyReadsMemory(QueryCS);
 
   SmallPtrSet<BasicBlock*, 64> Visited;
 
if (!Dep.isNonLocal()) {
       // Keep the ReverseNonLocalDeps map up to date so we can efficiently
       // update this when we remove instructions.
       if (Instruction *Inst = Dep.getInst())
         ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction());
     } else {
 
       // If the block *is* completely transparent to the load, we need to check
       // the predecessors of this block.  Add them to our worklist.
-      for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI)
-        DirtyBlocks.push_back(*PI);
+      for (BasicBlock *Pred : PredCache.get(DirtyBB))
+        DirtyBlocks.push_back(Pred);
     }
   }
 
   return Cache;
 }
 
 /// getNonLocalPointerDependency - Perform a full dependency query for an
 /// access to the specified (non-volatile) memory location, returning the
while (!Worklist.empty()) {
 
     // If 'Pointer' is an instruction defined in this block, then we need to do
     // phi translation to change it into a value live in the predecessor block.
     // If not, we just add the predecessors to the worklist and scan them with
     // the same Pointer.
     if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
       SkipFirstBlock = false;
       SmallVector<BasicBlock*, 16> NewBlocks;
-      for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
+      for (BasicBlock *Pred : PredCache.get(BB)) {
         // Verify that we haven't looked at this block yet.
         std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
-          InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr()));
+          InsertRes = Visited.insert(std::make_pair(Pred, Pointer.getAddr()));
         if (InsertRes.second) {
           // First time we've looked at *PI.
-          NewBlocks.push_back(*PI);
+          NewBlocks.push_back(Pred);
           continue;
         }
 
         // If we have seen this block before, but it was with a different
         // pointer then we have a phi translation failure and we have to treat
         // this as a clobber.
         if (InsertRes.first->second != Pointer.getAddr()) {
           // Make sure to clean up the Visited map before continuing on to
while (!Worklist.empty()) {
     // value will only see properly sorted cache arrays.
     if (Cache && NumSortedEntries != Cache->size()) {
       SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
       NumSortedEntries = Cache->size();
     }
     Cache = nullptr;
 
     PredList.clear();
-    for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
-      BasicBlock *Pred = *PI;
+    for (BasicBlock *Pred : PredCache.get(BB)) {
       PredList.push_back(std::make_pair(Pred, Pointer));
 
       // Get the PHI translated pointer in this predecessor.  This can fail if
       // not translatable, in which case the getAddr() returns null.
       PHITransAddr &PredPointer = PredList.back().second;
       PredPointer.PHITranslateValue(BB, Pred, nullptr);
 
       Value *PredPtrVal = PredPointer.getAddr();
void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) {
   // Flush load info for the pointer.
   RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
 }
 
 /// invalidateCachedPredecessors - Clear the PredIteratorCache info.
 /// This needs to be done when the CFG changes, e.g., due to splitting
 /// critical edges.
 void MemoryDependenceAnalysis::invalidateCachedPredecessors() {
-  PredCache->clear();
+  PredCache.clear();
 }
 
 /// removeInstruction - Remove an instruction from the dependence analysis,
 /// updating the dependence of instructions that previously depended on it.
 /// This method attempts to keep the cache coherent using the reverse map.
 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
   // Walk through the Non-local dependencies, removing this one as the value
   // for any cached queries.

llvm/trunk/lib/Transforms/Scalar/LICM.cpp

class LoopPromoter : public LoadAndStorePromoter {
 
     Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
       if (Instruction *I = dyn_cast<Instruction>(V))
         if (Loop *L = LI.getLoopFor(I->getParent()))
           if (!L->contains(BB)) {
             // We need to create an LCSSA PHI node for the incoming value and
             // store that.
             PHINode *PN = PHINode::Create(
-                I->getType(), PredCache.GetNumPreds(BB),
+                I->getType(), PredCache.size(BB),
                 I->getName() + ".lcssa", BB->begin());
-            for (BasicBlock **PI = PredCache.GetPreds(BB); *PI; ++PI)
-              PN->addIncoming(I, *PI);
+            for (BasicBlock *Pred : PredCache.get(BB))
+              PN->addIncoming(I, Pred);
             return PN;
           }
       return V;
     }
 
   public:
     LoopPromoter(Value *SP, const SmallVectorImpl<Instruction *> &Insts,
                  SSAUpdater &S, SmallPtrSetImpl<Value *> &PMA,

llvm/trunk/lib/Transforms/Utils/LCSSA.cpp

for (SmallVectorImpl<BasicBlock *>::const_iterator BBI = ExitBlocks.begin(),
     BasicBlock *ExitBB = *BBI;
     if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
       continue;
 
     // If we already inserted something for this BB, don't reprocess it.
     if (SSAUpdate.HasValueForBlock(ExitBB))
       continue;
 
-    PHINode *PN = PHINode::Create(Inst.getType(), PredCache.GetNumPreds(ExitBB),
+    PHINode *PN = PHINode::Create(Inst.getType(), PredCache.size(ExitBB),
                                   Inst.getName() + ".lcssa", ExitBB->begin());
 
     // Add inputs from inside the loop for this PHI.
-    for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) {
-      PN->addIncoming(&Inst, *PI);
+    for (BasicBlock *Pred : PredCache.get(ExitBB)) {
+      PN->addIncoming(&Inst, Pred);
 
       // If the exit block has a predecessor not within the loop, arrange for
       // the incoming value use corresponding to that predecessor to be
       // rewritten in terms of a different LCSSA PHI.
-      if (!L.contains(*PI))
+      if (!L.contains(Pred))
         UsesToRewrite.push_back(
             &PN->getOperandUse(PN->getOperandNumForIncomingValue(
                  PN->getNumIncomingValues() - 1)));
     }
 
     AddedPHIs.push_back(PN);
 
     // Remember that this phi makes the value alive in this block.