| //===-- PAMultipleGlobalPool.cpp - Multiple Global Pool Allocation Pass ---===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file was developed by the LLVM research group and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // A minimal poolallocator that assignes all allocation to multiple global |
| // pools. |
| // |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "poolalloc" |
| |
| #include "dsa/DataStructure.h" |
| #include "dsa/DSGraph.h" |
| #include "dsa/CallTargets.h" |
| #include "poolalloc/PoolAllocate.h" |
| #include "llvm/Constants.h" |
| #include "llvm/DerivedTypes.h" |
| #include "llvm/Instructions.h" |
| #include "llvm/Module.h" |
| #include "llvm/Constants.h" |
| #include "llvm/Support/CFG.h" |
| #include "llvm/Support/TypeBuilder.h" |
| #include "llvm/Target/TargetData.h" |
| #include "llvm/Transforms/Utils/BasicBlockUtils.h" |
| #include "llvm/Transforms/Utils/Cloning.h" |
| #include "llvm/ADT/DepthFirstIterator.h" |
| #include "llvm/ADT/Statistic.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/Support/CommandLine.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/Support/FormattedStream.h" |
| #include "llvm/Support/Timer.h" |
| |
| #include <iostream> |
| |
| using namespace llvm; |
| using namespace PA; |
| |
| char llvm::PoolAllocateMultipleGlobalPool::ID = 0; |
| |
| namespace { |
| RegisterPass<PoolAllocateMultipleGlobalPool> |
| X("poolalloc-multi-global-pool", "Pool allocate objects into multiple global pools"); |
| |
| RegisterAnalysisGroup<PoolAllocateGroup> PAGroup1(X); |
| } |
| |
| static inline Value * |
| castTo (Value * V, const Type * Ty, const std::string & Name, Instruction * InsertPt) { |
| // |
| // Don't bother creating a cast if it's already the correct type. |
| // |
| if (V->getType() == Ty) |
| return V; |
| |
| // |
| // If it's a constant, just create a constant expression. |
| // |
| if (Constant * C = dyn_cast<Constant>(V)) { |
| Constant * CE = ConstantExpr::getZExtOrBitCast (C, Ty); |
| return CE; |
| } |
| |
| // |
| // Otherwise, insert a cast instruction. |
| // |
| return CastInst::CreateZExtOrBitCast (V, Ty, Name, InsertPt); |
| } |
| |
| void PoolAllocateMultipleGlobalPool::getAnalysisUsage(AnalysisUsage &AU) const { |
| AU.addRequired<TargetData>(); |
| AU.addRequiredTransitive<SteensgaardDataStructures>(); |
| // It is a big lie. |
| AU.setPreservesAll(); |
| } |
| |
| bool PoolAllocateMultipleGlobalPool::runOnModule(Module &M) { |
| currentModule = &M; |
| if (M.begin() == M.end()) return false; |
| |
| // |
| // Get pointers to 8 and 32 bit LLVM integer types. |
| // |
| VoidType = Type::getVoidTy(getGlobalContext()); |
| Int8Type = IntegerType::getInt8Ty(getGlobalContext()); |
| Int32Type = IntegerType::getInt32Ty(getGlobalContext()); |
| |
| Graphs = &getAnalysis<SteensgaardDataStructures>(); |
| assert (Graphs && "No DSA pass available!\n"); |
| |
| TargetData & TD = getAnalysis<TargetData>(); |
| |
| // Add the pool* prototypes to the module |
| AddPoolPrototypes(&M); |
| |
| // |
| // Create the global pool. |
| // |
| CreateGlobalPool(32, 1, M); |
| |
| // |
| // Now that all call targets are available, rewrite the function bodies of the |
| // clones. |
| for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { |
| std::string name = I->getName(); |
| if (name == "__poolalloc_init") continue; |
| if (!(I->isDeclaration())) |
| ProcessFunctionBodySimple(*I, TD); |
| } |
| |
| return true; |
| } |
| |
| void |
| PoolAllocateMultipleGlobalPool::ProcessFunctionBodySimple (Function& F, TargetData & TD) { |
| std::vector<Instruction*> toDelete; |
| std::vector<ReturnInst*> Returns; |
| |
| // |
| // Create a silly Function Info structure for this function. |
| // |
| FuncInfo FInfo(F); |
| FunctionInfo.insert (std::make_pair(&F, FInfo)); |
| |
| // |
| // Get the DSGraph for this function. |
| // |
| DSGraph* ECG = Graphs->getDSGraph(F); |
| DSScalarMap & SM = ECG->getScalarMap(); |
| |
| for (Function::iterator i = F.begin(), e = F.end(); i != e; ++i) |
| for (BasicBlock::iterator ii = i->begin(), ee = i->end(); ii != ee; ++ii) { |
| //FIXME: Handle malloc here |
| if (false) { //MallocInst * MI = dyn_cast<MallocInst>(ii)) { |
| #if 0 |
| // Associate the global pool decriptor with the DSNode |
| DSNode * Node = ECG->getNodeForValue(MI).getNode(); |
| GlobalVariable * Pool = PoolMap[Node]; |
| FInfo.PoolDescriptors.insert(std::make_pair(Node,Pool)); |
| |
| // Mark the malloc as an instruction to delete |
| toDelete.push_back(ii); |
| |
| // Create instructions to calculate the size of the allocation in |
| // bytes |
| Value * AllocSize; |
| if (MI->isArrayAllocation()) { |
| Value * NumElements = MI->getArraySize(); |
| Value * ElementSize = ConstantInt::get(Int32Type, |
| TD.getTypeAllocSize(MI->getAllocatedType())); |
| AllocSize = BinaryOperator::Create (Instruction::Mul, |
| ElementSize, |
| NumElements, |
| "sizetmp", |
| MI); |
| } else { |
| AllocSize = ConstantInt::get(Int32Type, |
| TD.getTypeAllocSize(MI->getAllocatedType())); |
| } |
| |
| Value* args[] = {Pool, AllocSize}; |
| Instruction* x = CallInst::Create(PoolAlloc, &args[0], &args[2], MI->getName(), ii); |
| Value * casted = castTo(x, ii->getType(), "", ii); |
| ii->replaceAllUsesWith(casted); |
| |
| // Update scalar map |
| DSNodeHandle NH = SM[ii]; |
| SM.erase(ii); |
| SM[casted] = SM[x] = NH; |
| #endif |
| } else if (CallInst * CI = dyn_cast<CallInst>(ii)) { |
| CallSite CS(CI); |
| Function *CF = CS.getCalledFunction(); |
| if (ConstantExpr *CE = dyn_cast<ConstantExpr>(CS.getCalledValue())) |
| if (CE->getOpcode() == Instruction::BitCast && |
| isa<Function>(CE->getOperand(0))) |
| CF = cast<Function>(CE->getOperand(0)); |
| if (CF && (CF->isDeclaration()) && (CF->getName() == "realloc")) { |
| // Associate the global pool decriptor with the DSNode |
| DSNode * Node = ECG->getNodeForValue(CI).getNode(); |
| GlobalVariable * Pool = PoolMap[Node]; |
| |
| FInfo.PoolDescriptors.insert(std::make_pair(Node,Pool)); |
| |
| // Mark the realloc as an instruction to delete |
| toDelete.push_back(ii); |
| |
| // Insertion point - Instruction before which all our instructions go |
| Instruction *InsertPt = CI; |
| Value *OldPtr = CS.getArgument(0); |
| Value *Size = CS.getArgument(1); |
| |
| // Ensure the size and pointer arguments are of the correct type |
| if (Size->getType() != Int32Type) |
| Size = CastInst::CreateIntegerCast (Size, |
| Int32Type, |
| false, |
| Size->getName(), |
| InsertPt); |
| |
| static Type *VoidPtrTy = PointerType::getUnqual(Int8Type); |
| if (OldPtr->getType() != VoidPtrTy) |
| OldPtr = CastInst::CreatePointerCast (OldPtr, |
| VoidPtrTy, |
| OldPtr->getName(), |
| InsertPt); |
| |
| std::string Name = CI->getName(); CI->setName(""); |
| Value* Opts[3] = {Pool, OldPtr, Size}; |
| Instruction *V = CallInst::Create (PoolRealloc, |
| Opts, |
| Opts + 3, |
| Name, |
| InsertPt); |
| Value *Casted = castTo(V, CI->getType(), V->getName(), InsertPt); |
| |
| // Update def-use info |
| CI->replaceAllUsesWith(Casted); |
| |
| // Update scalar map |
| DSNodeHandle NH = SM[CI]; |
| SM.erase(CI); |
| SM[Casted] = SM[V] = NH; |
| } else if (CF && (CF->isDeclaration()) && (CF->getName() == "calloc")) { |
| // Associate the global pool decriptor with the DSNode |
| DSNode * Node = ECG->getNodeForValue(CI).getNode(); |
| GlobalVariable * Pool = PoolMap[Node]; |
| FInfo.PoolDescriptors.insert(std::make_pair(Node,Pool)); |
| |
| // Mark the realloc as an instruction to delete |
| toDelete.push_back(ii); |
| |
| // Insertion point - Instruction before which all our instructions go |
| Instruction *InsertPt = CI; |
| Value *NumElements = CS.getArgument(0); |
| Value *Size = CS.getArgument(1); |
| |
| // Ensure the size and pointer arguments are of the correct type |
| if (Size->getType() != Int32Type) |
| Size = CastInst::CreateIntegerCast (Size, |
| Int32Type, |
| false, |
| Size->getName(), |
| InsertPt); |
| |
| if (NumElements->getType() != Int32Type) |
| NumElements = CastInst::CreateIntegerCast (Size, |
| Int32Type, |
| false, |
| NumElements->getName(), |
| InsertPt); |
| |
| std::string Name = CI->getName(); CI->setName(""); |
| Value* Opts[3] = {Pool, NumElements, Size}; |
| Instruction *V = CallInst::Create (PoolCalloc, |
| Opts, |
| Opts + 3, |
| Name, |
| InsertPt); |
| |
| Value *Casted = castTo(V, CI->getType(), V->getName(), InsertPt); |
| |
| // Update def-use info |
| CI->replaceAllUsesWith(Casted); |
| |
| // Update scalar map |
| DSNodeHandle NH = SM[CI]; |
| SM.erase(CI); |
| SM[Casted] = SM[V] = NH; |
| } else if (CF && (CF->isDeclaration()) && (CF->getName() == "strdup")) { |
| // Associate the global pool decriptor with the DSNode |
| DSNode * Node = ECG->getNodeForValue(CI).getNode(); |
| GlobalVariable * Pool = PoolMap[Node]; |
| FInfo.PoolDescriptors.insert(std::make_pair(Node, Pool)); |
| |
| // Mark the realloc as an instruction to delete |
| toDelete.push_back(ii); |
| |
| // Insertion point - Instruction before which all our instructions go |
| Instruction *InsertPt = CI; |
| Value *OldPtr = CS.getArgument(0); |
| |
| // Ensure the size and pointer arguments are of the correct type |
| static Type *VoidPtrTy = PointerType::getUnqual(Int8Type); |
| if (OldPtr->getType() != VoidPtrTy) |
| OldPtr = CastInst::CreatePointerCast (OldPtr, |
| VoidPtrTy, |
| OldPtr->getName(), |
| InsertPt); |
| |
| std::string Name = CI->getName(); CI->setName(""); |
| Value* Opts[2] = {Pool, OldPtr}; |
| Instruction *V = CallInst::Create (PoolStrdup, |
| Opts, |
| Opts + 2, |
| Name, |
| InsertPt); |
| Value *Casted = castTo(V, CI->getType(), V->getName(), InsertPt); |
| |
| // Update def-use info |
| CI->replaceAllUsesWith(Casted); |
| |
| // Update scalar map |
| DSNodeHandle NH = SM[CI]; |
| SM.erase(CI); |
| SM[Casted] = SM[V] = NH; |
| } |
| //FIXME: handle Frees |
| #if 0 |
| } else if (FreeInst * FI = dyn_cast<FreeInst > (ii)) { |
| Type * VoidPtrTy = PointerType::getUnqual(Int8Type); |
| Value * FreedNode = castTo (FI->getPointerOperand(), VoidPtrTy, "cast", ii); |
| DSNode * Node = ECG->getNodeForValue(FI->getPointerOperand()).getNode(); |
| GlobalVariable * Pool = PoolMap[Node]; |
| assert (Pool && "No Pool Handle for poolfree()!"); |
| toDelete.push_back(ii); |
| Value* args[] = {Pool, FreedNode}; |
| CallInst * CI = CallInst::Create(PoolFree, &args[0], &args[2], "", ii); |
| // Update scalar map |
| DSNodeHandle NH = SM[ii]; |
| SM.erase(ii); |
| SM[CI] = NH; |
| #endif |
| } else if (isa<ReturnInst>(ii)) { |
| Returns.push_back(cast<ReturnInst>(ii)); |
| } |
| } |
| |
| //delete malloc and alloca insts |
| for (unsigned x = 0; x < toDelete.size(); ++x) |
| toDelete[x]->eraseFromParent(); |
| } |
| |
| /// CreateGlobalPool - Create a global pool descriptor object, and insert a |
| /// poolinit for it into poolalloc.init |
| void |
| PoolAllocateMultipleGlobalPool::CreateGlobalPool (unsigned RecSize, |
| unsigned Align, |
| Module& M) { |
| |
| Function *InitFunc = Function::Create |
| (FunctionType::get(VoidType, std::vector<const Type*>(), false), |
| GlobalValue::ExternalLinkage, "__poolalloc_init", &M); |
| |
| // put it into llvm.used so that it won't get killed. |
| |
| Type * VoidPtrTy = PointerType::getUnqual(Int8Type); |
| ArrayType * LLVMUsedTy = ArrayType::get(VoidPtrTy, 1); |
| Constant * C = ConstantExpr::getBitCast (cast<Constant>(InitFunc), VoidPtrTy); |
| std::vector<Constant*> UsedFunctions(1,C); |
| Constant * NewInit = ConstantArray::get(LLVMUsedTy, UsedFunctions); |
| |
| new GlobalVariable (M, LLVMUsedTy, false, |
| GlobalValue::AppendingLinkage, |
| NewInit, "llvm.used"); |
| |
| |
| BasicBlock * BB = BasicBlock::Create(getGlobalContext(), "entry", InitFunc); |
| |
| SteensgaardDataStructures * DS = (SteensgaardDataStructures*)Graphs; |
| |
| assert (DS && "PoolAllocateMultipleGlobalPools requires Steensgaard Data Structure!"); |
| |
| // |
| // Create a pool for each node within the DSGraph. |
| // |
| DSGraph * G = DS->getResultGraph(); |
| for (DSGraph::node_const_iterator I = G->node_begin(), |
| E = G->node_end(); I != E; ++I) { |
| generatePool (I->getSize(), Align, M, BB, I); |
| } |
| |
| DSGraph * GG = DS->getGlobalsGraph(); |
| for(DSGraph::node_const_iterator I = GG->node_begin(), |
| E = GG->node_end(); I != E; ++I) { |
| if (I->globals_begin() != I->globals_end()) { |
| const GlobalValue * GV = *(I->globals_begin()); |
| DSNodeHandle NH = G->getNodeForValue(GV); |
| if (!NH.isNull()) { |
| PoolMap[&*I] = PoolMap[NH.getNode()]; |
| } else { |
| generatePool(I->getSize(), Align, M, BB, I); |
| } |
| } |
| } |
| |
| ReturnInst::Create(getGlobalContext(), BB); |
| } |
| |
| void |
| PoolAllocateMultipleGlobalPool::generatePool(unsigned RecSize, |
| unsigned Align, |
| Module& M, |
| BasicBlock * InsertAtEnd, |
| const DSNode * Node) { |
| |
| if (!PoolMap[Node]) { |
| GlobalVariable *GV = |
| new GlobalVariable |
| (M, |
| getPoolType(&M.getContext()), false, GlobalValue::ExternalLinkage, |
| ConstantAggregateZero::get(getPoolType(&M.getContext())), "__poolalloc_GlobalPool"); |
| |
| Value *ElSize = ConstantInt::get(Int32Type, RecSize); |
| Value *AlignV = ConstantInt::get(Int32Type, Align); |
| Value* Opts[3] = {GV, ElSize, AlignV}; |
| |
| CallInst::Create(PoolInit, Opts, Opts + 3, "", InsertAtEnd); |
| PoolMap[Node] = GV; |
| } |
| } |
| |
| |
| Value * |
| PoolAllocateMultipleGlobalPool::getGlobalPool (const DSNode * Node) { |
| Value * Pool = PoolMap[Node]; |
| assert (Pool && "Every DSNode corresponds to a pool handle!"); |
| return Pool; |
| } |
| |
| Value * |
| PoolAllocateMultipleGlobalPool::getPool (const DSNode * N, Function & F) { |
| return getGlobalPool(N); |
| } |
| |
| void |
| PoolAllocateMultipleGlobalPool::print(llvm::raw_ostream &OS, const Module * M) const { |
| for (PoolMapTy::const_iterator I = PoolMap.begin(), E = PoolMap.end(); I != E; ++I) { |
| OS << I->first << " -> " << I->second->getName() << "\n"; |
| } |
| } |
| |
| void |
| PoolAllocateMultipleGlobalPool::dump() const { |
| print (errs(), currentModule); |
| } |
| |
| PoolAllocateMultipleGlobalPool::~PoolAllocateMultipleGlobalPool() {} |