lib/Transforms/IPO/OldPoolAllocate.cpp

   1 //===-- PoolAllocate.cpp - Pool Allocation Pass ---------------------------===//
   2 //
   3 // This transform changes programs so that disjoint data structures are
   4 // allocated out of different pools of memory, increasing locality and shrinking
   5 // pointer size.
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Transforms/IPO/PoolAllocate.h"
  10 #include "llvm/Analysis/DataStructure.h"
  11 #include "llvm/Pass.h"
  12 #include "llvm/Module.h"
  13 #include "llvm/Function.h"
  14 #include "llvm/iMemory.h"
  15 #include <algorithm>
  16
  17 // Define the pass class that we implement...
  18 namespace {
  19   class PoolAllocate : public Pass {
  20     // PoolTy - The type of a scalar value that contains a pool pointer.
  21     PointerType *PoolTy;
  22   public:
  23
  24     PoolAllocate() {
  25       // Initialize the PoolTy instance variable, since the type never changes.
  26       vector<const Type*> PoolElements;
  27       PoolElements.push_back(PointerType::get(Type::SByteTy));
  28       PoolElements.push_back(Type::UIntTy);
  29       PoolTy = PointerType::get(StructType::get(PoolElements));
  30       // PoolTy = { sbyte*, uint }*
  31
  32       CurModule = 0; DS = 0;
  33       PoolInit = PoolDestroy = PoolAlloc = PoolFree = 0;
  34     }
  35
  36     bool run(Module *M);
  37
  38     // getAnalysisUsageInfo - This function requires data structure information
  39     // to be able to see what is pool allocatable.
  40     //
  41     virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Required,
  42                                       Pass::AnalysisSet &,Pass::AnalysisSet &) {
  43       Required.push_back(DataStructure::ID);
  44     }
  45
  46   private:
  47     // CurModule - The module being processed.
  48     Module *CurModule;
  49
  50     // DS - The data structure graph for the module being processed.
  51     DataStructure *DS;
  52
  53     // Prototypes that we add to support pool allocation...
  54     Function *PoolInit, *PoolDestroy, *PoolAlloc, *PoolFree;
  55
  56     // addPoolPrototypes - Add prototypes for the pool methods to the specified
  57     // module and update the Pool* instance variables to point to them.
  58     //
  59     void addPoolPrototypes(Module *M);
  60
  61     // processFunction - Convert a function to use pool allocation where
  62     // available.
  63     //
  64     bool processFunction(Function *F);
  65   };
  66 }
  67
  68
  69
  70 // isNotPoolableAlloc - This is a predicate that returns true if the specified
  71 // allocation node in a data structure graph is eligable for pool allocation.
  72 //
  73 static bool isNotPoolableAlloc(const AllocDSNode *DS) {
  74   if (DS->isAllocaNode()) return false;  // Do not pool allocate alloca's.
  75
  76   MallocInst *MI = cast<MallocInst>(DS->getAllocation());
  77   if (MI->isArrayAllocation() && !isa<Constant>(MI->getArraySize()))
  78     return false;   // Do not allow variable size allocations...
  79
  80   return true;
  81 }
  82
  83
  84 // processFunction - Convert a function to use pool allocation where
  85 // available.
  86 //
  87 bool PoolAllocate::processFunction(Function *F) {
  88   // Get the closed datastructure graph for the current function... if there are
  89   // any allocations in this graph that are not escaping, we need to pool
  90   // allocate them here!
  91   //
  92   FunctionDSGraph &IPGraph = DS->getClosedDSGraph(F);
  93
  94   // Get all of the allocations that do not escape the current function.  Since
  95   // they are still live (they exist in the graph at all), this means we must
  96   // have scalar references to these nodes, but the scalars are never returned.
  97   //
  98   std::vector<AllocDSNode*> Allocs;
  99   IPGraph.getNonEscapingAllocations(Allocs);
 100
 101   // Filter out allocations that we cannot handle.  Currently, this includes
 102   // variable sized array allocations and alloca's (which we do not want to
 103   // pool allocate)
 104   //
 105   Allocs.erase(remove_if(Allocs.begin(), Allocs.end(), isNotPoolableAlloc),
 106                Allocs.end());
 107
 108
 109   if (Allocs.empty()) return false;  // Nothing to do.
 110
 111   // Loop through the value map looking for scalars that refer to nonescaping
 112   // allocations.
 113   //
 114   map<Value*, PointerValSet> &ValMap = IPGraph.getValueMap();
 115   vector<pair<Value*, AllocDSNode*> > Scalars;
 116
 117   for (map<Value*, PointerValSet>::iterator I = ValMap.begin(),
 118          E = ValMap.end(); I != E; ++I) {
 119     const PointerValSet &PVS = I->second;  // Set of things pointed to by scalar
 120     // Check to see if the scalar points to anything that is an allocation...
 121     for (unsigned i = 0, e = PVS.size(); i != e; ++i)
 122       if (AllocDSNode *Alloc = dyn_cast<AllocDSNode>(PVS[i].Node)) {
 123         assert(PVS[i].Index == 0 && "Nonzero not handled yet!");
 124
 125         // If the allocation is in the nonescaping set...
 126         if (find(Allocs.begin(), Allocs.end(), Alloc) != Allocs.end())
 127           // Add it to the list of scalars we have
 128           Scalars.push_back(make_pair(I->first, Alloc));
 129       }
 130   }
 131
 132   cerr << "In '" << F->getName()
 133        << "': Found the following values that point to poolable nodes:\n";
 134
 135   for (unsigned i = 0, e = Scalars.size(); i != e; ++i)
 136     Scalars[i].first->dump();
 137   return false;
 138 }
 139
 140
 141 // Prototypes that we add to support pool allocation...
 142 Function *PoolInit, *PoolDestroy, *PoolAlloc, *PoolFree;
 143
 144 // addPoolPrototypes - Add prototypes for the pool methods to the specified
 145 // module and update the Pool* instance variables to point to them.
 146 //
 147 void PoolAllocate::addPoolPrototypes(Module *M) {
 148   //M->getOrCreate...
 149
 150 }
 151
 152
 153 bool PoolAllocate::run(Module *M) {
 154   addPoolPrototypes(M);
 155   CurModule = M;
 156
 157   DS = &getAnalysis<DataStructure>();
 158   bool Changed = false;
 159   for (Module::iterator I = M->begin(); I != M->end(); ++I)
 160     if (!(*I)->isExternal())
 161       Changed |= processFunction(*I);
 162
 163   CurModule = 0;
 164   DS = 0;
 165   return false;
 166 }
 167
 168
 169 // createPoolAllocatePass - Global function to access the functionality of this
 170 // pass...
 171 //
 172 Pass *createPoolAllocatePass() { return new PoolAllocate(); }