include/llvm/Support/PredIteratorCache.h

   1 //===- llvm/Support/PredIteratorCache.h - pred_iterator Cache ---*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the PredIteratorCache class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Support/Allocator.h"
  15 #include "llvm/Support/CFG.h"
  16 #include "llvm/ADT/DenseMap.h"
  17 #include "llvm/ADT/SmallVector.h"
  18
  19 namespace llvm {
  20
  21   /// PredIteratorCache - This class is an extremely trivial cache for
  22   /// predecessor iterator queries.  This is useful for code that repeatedly
  23   /// wants the predecessor list for the same blocks.
  24   class PredIteratorCache {
  25     /// BlockToPredsMap - Pointer to null-terminated list.
  26     DenseMap<BasicBlock*, BasicBlock**> BlockToPredsMap;
  27
  28     /// Memory - This is the space that holds cached preds.
  29     BumpPtrAllocator Memory;
  30   public:
  31
  32     /// GetPreds - Get a cached list for the null-terminated predecessor list of
  33     /// the specified block.  This can be used in a loop like this:
  34     ///   for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI)
  35     ///      use(*PI);
  36     /// instead of:
  37     /// for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
  38     BasicBlock **GetPreds(BasicBlock *BB) {
  39       BasicBlock **&Entry = BlockToPredsMap[BB];
  40       if (Entry) return Entry;
  41
  42       SmallVector<BasicBlock*, 32> PredCache(pred_begin(BB), pred_end(BB));
  43       PredCache.push_back(0); // null terminator.
  44
  45       Entry = Memory.Allocate<BasicBlock*>(PredCache.size());
  46       std::copy(PredCache.begin(), PredCache.end(), Entry);
  47       return Entry;
  48     }
  49
  50     /// clear - Remove all information.
  51     void clear() {
  52       BlockToPredsMap.clear();
  53       Memory.Reset();
  54     }
  55   };
  56 } // end namespace llvm
  57