From 478b3a9682c888d17abef1b19f779852ebba213b Mon Sep 17 00:00:00 2001 From: John Criswell Date: Wed, 13 Aug 2003 15:36:15 +0000 Subject: [PATCH] Removing the pool allocator from the main CVS tree. Use the poolalloc module in CVS from now on. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@7810 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Transforms/PoolAllocate.h | 156 -- lib/Transforms/IPO/OldPoolAllocate.cpp | 1759 ----------------- lib/Transforms/IPO/PoolAllocate.cpp | 1204 ----------- runtime/GCCLibraries/libpoolalloc/Makefile | 4 - .../libpoolalloc/PoolAllocatorChained.c | 461 ----- 5 files changed, 3584 deletions(-) delete mode 100644 include/llvm/Transforms/PoolAllocate.h delete mode 100644 lib/Transforms/IPO/OldPoolAllocate.cpp delete mode 100644 lib/Transforms/IPO/PoolAllocate.cpp delete mode 100644 runtime/GCCLibraries/libpoolalloc/Makefile delete mode 100644 runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c diff --git a/include/llvm/Transforms/PoolAllocate.h b/include/llvm/Transforms/PoolAllocate.h deleted file mode 100644 index b6806c12a1b..00000000000 --- a/include/llvm/Transforms/PoolAllocate.h +++ /dev/null @@ -1,156 +0,0 @@ -//===-- PoolAllocate.h - Pool allocation pass -------------------*- C++ -*-===// -// -// This transform changes programs so that disjoint data structures are -// allocated out of different pools of memory, increasing locality. This header -// file exposes information about the pool allocation itself so that follow-on -// passes may extend or use the pool allocation for analysis. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TRANSFORMS_POOLALLOCATE_H -#define LLVM_TRANSFORMS_POOLALLOCATE_H - -#include "llvm/Pass.h" -#include "Support/hash_set" -#include "Support/EquivalenceClasses.h" -class BUDataStructures; -class TDDataStructures; -class DSNode; -class DSGraph; -class CallInst; - -namespace PA { - /// FuncInfo - Represent the pool allocation information for one function in - /// the program. Note that many functions must actually be cloned in order - /// for pool allocation to add arguments to the function signature. In this - /// case, the Clone and NewToOldValueMap information identify how the clone - /// maps to the original function... - /// - struct FuncInfo { - /// MarkedNodes - The set of nodes which are not locally pool allocatable in - /// the current function. - /// - hash_set MarkedNodes; - - /// Clone - The cloned version of the function, if applicable. - Function *Clone; - - /// ArgNodes - The list of DSNodes which have pools passed in as arguments. - /// - std::vector ArgNodes; - - /// In order to handle indirect functions, the start and end of the - /// arguments that are useful to this function. - /// The pool arguments useful to this function are PoolArgFirst to - /// PoolArgLast not inclusive. - int PoolArgFirst, PoolArgLast; - - /// PoolDescriptors - The Value* (either an argument or an alloca) which - /// defines the pool descriptor for this DSNode. Pools are mapped one to - /// one with nodes in the DSGraph, so this contains a pointer to the node it - /// corresponds to. In addition, the pool is initialized by calling the - /// "poolinit" library function with a chunk of memory allocated with an - /// alloca instruction. This entry contains a pointer to that alloca if the - /// pool is locally allocated or the argument it is passed in through if - /// not. - /// Note: Does not include pool arguments that are passed in because of - /// indirect function calls that are not used in the function. - std::map PoolDescriptors; - - /// NewToOldValueMap - When and if a function needs to be cloned, this map - /// contains a mapping from all of the values in the new function back to - /// the values they correspond to in the old function. - /// - std::map NewToOldValueMap; - }; -} - -/// PoolAllocate - The main pool allocation pass -/// -class PoolAllocate : public Pass { - Module *CurModule; - BUDataStructures *BU; - - TDDataStructures *TDDS; - - hash_set InlinedFuncs; - - std::map FunctionInfo; - - void buildIndirectFunctionSets(Module &M); - - void FindFunctionPoolArgs(Function &F); - - // Debug function to print the FuncECs - void printFuncECs(); - - public: - Function *PoolInit, *PoolDestroy, *PoolAlloc, *PoolAllocArray, *PoolFree; - - // Equivalence class where functions that can potentially be called via - // the same function pointer are in the same class. - EquivalenceClasses FuncECs; - - // Map from an Indirect CallInst to the set of Functions that it can point to - std::multimap CallInstTargets; - - // This maps an equivalence class to the last pool argument number for that - // class. This is used because the pool arguments for all functions within - // an equivalence class is passed to all the functions in that class. - // If an equivalence class does not require pool arguments, it is not - // on this map. - std::map EqClass2LastPoolArg; - - // Exception flags - // CollapseFlag set if all data structures are not pool allocated, due to - // collapsing of nodes in the DS graph - unsigned CollapseFlag; - - public: - bool run(Module &M); - - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - - BUDataStructures &getBUDataStructures() const { return *BU; } - - PA::FuncInfo *getFuncInfo(Function &F) { - std::map::iterator I = FunctionInfo.find(&F); - return I != FunctionInfo.end() ? &I->second : 0; - } - - Module *getCurModule() { return CurModule; } - - private: - - /// AddPoolPrototypes - Add prototypes for the pool functions to the - /// specified module and update the Pool* instance variables to point to - /// them. - /// - void AddPoolPrototypes(); - - /// MakeFunctionClone - If the specified function needs to be modified for - /// pool allocation support, make a clone of it, adding additional arguments - /// as neccesary, and return it. If not, just return null. - /// - Function *MakeFunctionClone(Function &F); - - /// ProcessFunctionBody - Rewrite the body of a transformed function to use - /// pool allocation where appropriate. - /// - void ProcessFunctionBody(Function &Old, Function &New); - - /// CreatePools - This creates the pool initialization and destruction code - /// for the DSNodes specified by the NodesToPA list. This adds an entry to - /// the PoolDescriptors map for each DSNode. - /// - void CreatePools(Function &F, const std::vector &NodesToPA, - std::map &PoolDescriptors); - - void TransformFunctionBody(Function &F, Function &OldF, - DSGraph &G, PA::FuncInfo &FI); - - void InlineIndirectCalls(Function &F, DSGraph &G, - hash_set &visited); -}; - -#endif diff --git a/lib/Transforms/IPO/OldPoolAllocate.cpp b/lib/Transforms/IPO/OldPoolAllocate.cpp deleted file mode 100644 index bf86403d86b..00000000000 --- a/lib/Transforms/IPO/OldPoolAllocate.cpp +++ /dev/null @@ -1,1759 +0,0 @@ -//===-- PoolAllocate.cpp - Pool Allocation Pass ---------------------------===// -// -// This transform changes programs so that disjoint data structures are -// allocated out of different pools of memory, increasing locality and shrinking -// pointer size. -// -//===----------------------------------------------------------------------===// - -#if 0 -#include "llvm/Transforms/IPO.h" -#include "llvm/Transforms/Utils/Cloning.h" -#include "llvm/Analysis/DataStructure.h" -#include "llvm/Module.h" -#include "llvm/iMemory.h" -#include "llvm/iTerminators.h" -#include "llvm/iPHINode.h" -#include "llvm/iOther.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Constants.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Support/InstVisitor.h" -#include "Support/DepthFirstIterator.h" -#include "Support/STLExtras.h" -#include -using std::vector; -using std::cerr; -using std::map; -using std::string; -using std::set; - -// DEBUG_CREATE_POOLS - Enable this to turn on debug output for the pool -// creation phase in the top level function of a transformed data structure. -// -//#define DEBUG_CREATE_POOLS 1 - -// DEBUG_TRANSFORM_PROGRESS - Enable this to get lots of debug output on what -// the transformation is doing. -// -//#define DEBUG_TRANSFORM_PROGRESS 1 - -// DEBUG_POOLBASE_LOAD_ELIMINATOR - Turn this on to get statistics about how -// many static loads were eliminated from a function... -// -#define DEBUG_POOLBASE_LOAD_ELIMINATOR 1 - -#include "Support/CommandLine.h" -enum PtrSize { - Ptr8bits, Ptr16bits, Ptr32bits -}; - -static cl::opt -ReqPointerSize("poolalloc-ptr-size", - cl::desc("Set pointer size for -poolalloc pass"), - cl::values( - clEnumValN(Ptr32bits, "32", "Use 32 bit indices for pointers"), - clEnumValN(Ptr16bits, "16", "Use 16 bit indices for pointers"), - clEnumValN(Ptr8bits , "8", "Use 8 bit indices for pointers"), - 0)); - -static cl::opt -DisableRLE("no-pool-load-elim", cl::Hidden, - cl::desc("Disable pool load elimination after poolalloc pass")); - -const Type *POINTERTYPE; - -// FIXME: This is dependant on the sparc backend layout conventions!! -static TargetData TargetData("test"); - -static const Type *getPointerTransformedType(const Type *Ty) { - if (const PointerType *PT = dyn_cast(Ty)) { - return POINTERTYPE; - } else if (const StructType *STy = dyn_cast(Ty)) { - vector NewElTypes; - NewElTypes.reserve(STy->getElementTypes().size()); - for (StructType::ElementTypes::const_iterator - I = STy->getElementTypes().begin(), - E = STy->getElementTypes().end(); I != E; ++I) - NewElTypes.push_back(getPointerTransformedType(*I)); - return StructType::get(NewElTypes); - } else if (const ArrayType *ATy = dyn_cast(Ty)) { - return ArrayType::get(getPointerTransformedType(ATy->getElementType()), - ATy->getNumElements()); - } else { - assert(Ty->isPrimitiveType() && "Unknown derived type!"); - return Ty; - } -} - -namespace { - struct PoolInfo { - DSNode *Node; // The node this pool allocation represents - Value *Handle; // LLVM value of the pool in the current context - const Type *NewType; // The transformed type of the memory objects - const Type *PoolType; // The type of the pool - - const Type *getOldType() const { return Node->getType(); } - - PoolInfo() { // Define a default ctor for map::operator[] - cerr << "Map subscript used to get element that doesn't exist!\n"; - abort(); // Invalid - } - - PoolInfo(DSNode *N, Value *H, const Type *NT, const Type *PT) - : Node(N), Handle(H), NewType(NT), PoolType(PT) { - // Handle can be null... - assert(N && NT && PT && "Pool info null!"); - } - - PoolInfo(DSNode *N) : Node(N), Handle(0), NewType(0), PoolType(0) { - assert(N && "Invalid pool info!"); - - // The new type of the memory object is the same as the old type, except - // that all of the pointer values are replaced with POINTERTYPE values. - NewType = getPointerTransformedType(getOldType()); - } - }; - - // ScalarInfo - Information about an LLVM value that we know points to some - // datastructure we are processing. - // - struct ScalarInfo { - Value *Val; // Scalar value in Current Function - PoolInfo Pool; // The pool the scalar points into - - ScalarInfo(Value *V, const PoolInfo &PI) : Val(V), Pool(PI) { - assert(V && "Null value passed to ScalarInfo ctor!"); - } - }; - - // CallArgInfo - Information on one operand for a call that got expanded. - struct CallArgInfo { - int ArgNo; // Call argument number this corresponds to - DSNode *Node; // The graph node for the pool - Value *PoolHandle; // The LLVM value that is the pool pointer - - CallArgInfo(int Arg, DSNode *N, Value *PH) - : ArgNo(Arg), Node(N), PoolHandle(PH) { - assert(Arg >= -1 && N && PH && "Illegal values to CallArgInfo ctor!"); - } - - // operator< when sorting, sort by argument number. - bool operator<(const CallArgInfo &CAI) const { - return ArgNo < CAI.ArgNo; - } - }; - - // TransformFunctionInfo - Information about how a function eeds to be - // transformed. - // - struct TransformFunctionInfo { - // ArgInfo - Maintain information about the arguments that need to be - // processed. Each CallArgInfo corresponds to an argument that needs to - // have a pool pointer passed into the transformed function with it. - // - // As a special case, "argument" number -1 corresponds to the return value. - // - vector ArgInfo; - - // Func - The function to be transformed... - Function *Func; - - // The call instruction that is used to map CallArgInfo PoolHandle values - // into the new function values. - CallInst *Call; - - // default ctor... - TransformFunctionInfo() : Func(0), Call(0) {} - - bool operator<(const TransformFunctionInfo &TFI) const { - if (Func < TFI.Func) return true; - if (Func > TFI.Func) return false; - if (ArgInfo.size() < TFI.ArgInfo.size()) return true; - if (ArgInfo.size() > TFI.ArgInfo.size()) return false; - return ArgInfo < TFI.ArgInfo; - } - - void finalizeConstruction() { - // Sort the vector so that the return value is first, followed by the - // argument records, in order. Note that this must be a stable sort so - // that the entries with the same sorting criteria (ie they are multiple - // pool entries for the same argument) are kept in depth first order. - std::stable_sort(ArgInfo.begin(), ArgInfo.end()); - } - - // addCallInfo - For a specified function call CI, figure out which pool - // descriptors need to be passed in as arguments, and which arguments need - // to be transformed into indices. If Arg != -1, the specified call - // argument is passed in as a pointer to a data structure. - // - void addCallInfo(DataStructure *DS, CallInst *CI, int Arg, - DSNode *GraphNode, map &PoolDescs); - - // Make sure that all dependant arguments are added to this transformation - // info. For example, if we call foo(null, P) and foo treats it's first and - // second arguments as belonging to the same data structure, the we MUST add - // entries to know that the null needs to be transformed into an index as - // well. - // - void ensureDependantArgumentsIncluded(DataStructure *DS, - map &PoolDescs); - }; - - - // Define the pass class that we implement... - struct PoolAllocate : public Pass { - PoolAllocate() { - switch (ReqPointerSize) { - case Ptr32bits: POINTERTYPE = Type::UIntTy; break; - case Ptr16bits: POINTERTYPE = Type::UShortTy; break; - case Ptr8bits: POINTERTYPE = Type::UByteTy; break; - } - - CurModule = 0; DS = 0; - PoolInit = PoolDestroy = PoolAlloc = PoolFree = 0; - } - - // getPoolType - Get the type used by the backend for a pool of a particular - // type. This pool record is used to allocate nodes of type NodeType. - // - // Here, PoolTy = { NodeType*, sbyte*, uint }* - // - const StructType *getPoolType(const Type *NodeType) { - vector PoolElements; - PoolElements.push_back(PointerType::get(NodeType)); - PoolElements.push_back(PointerType::get(Type::SByteTy)); - PoolElements.push_back(Type::UIntTy); - StructType *Result = StructType::get(PoolElements); - - // Add a name to the symbol table to correspond to the backend - // representation of this pool... - assert(CurModule && "No current module!?"); - string Name = CurModule->getTypeName(NodeType); - if (Name.empty()) Name = CurModule->getTypeName(PoolElements[0]); - CurModule->addTypeName(Name+"oolbe", Result); - - return Result; - } - - bool run(Module &M); - - // getAnalysisUsage - This function requires data structure information - // to be able to see what is pool allocatable. - // - virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); - } - - public: - // CurModule - The module being processed. - Module *CurModule; - - // DS - The data structure graph for the module being processed. - DataStructure *DS; - - // Prototypes that we add to support pool allocation... - Function *PoolInit, *PoolDestroy, *PoolAlloc, *PoolAllocArray, *PoolFree; - - // The map of already transformed functions... note that the keys of this - // map do not have meaningful values for 'Call' or the 'PoolHandle' elements - // of the ArgInfo elements. - // - map TransformedFunctions; - - // getTransformedFunction - Get a transformed function, or return null if - // the function specified hasn't been transformed yet. - // - Function *getTransformedFunction(TransformFunctionInfo &TFI) const { - map::const_iterator I = - TransformedFunctions.find(TFI); - if (I != TransformedFunctions.end()) return I->second; - return 0; - } - - - // addPoolPrototypes - Add prototypes for the pool functions to the - // specified module and update the Pool* instance variables to point to - // them. - // - void addPoolPrototypes(Module &M); - - - // CreatePools - Insert instructions into the function we are processing to - // create all of the memory pool objects themselves. This also inserts - // destruction code. Add an alloca for each pool that is allocated to the - // PoolDescs map. - // - void CreatePools(Function *F, const vector &Allocs, - map &PoolDescs); - - // processFunction - Convert a function to use pool allocation where - // available. - // - bool processFunction(Function *F); - - // transformFunctionBody - This transforms the instruction in 'F' to use the - // pools specified in PoolDescs when modifying data structure nodes - // specified in the PoolDescs map. IPFGraph is the closed data structure - // graph for F, of which the PoolDescriptor nodes come from. - // - void transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph, - map &PoolDescs); - - // transformFunction - Transform the specified function the specified way. - // It we have already transformed that function that way, don't do anything. - // The nodes in the TransformFunctionInfo come out of callers data structure - // graph, and the PoolDescs passed in are the caller's. - // - void transformFunction(TransformFunctionInfo &TFI, - FunctionDSGraph &CallerIPGraph, - map &PoolDescs); - - }; - - RegisterOpt X("poolalloc", - "Pool allocate disjoint datastructures"); -} - -// isNotPoolableAlloc - This is a predicate that returns true if the specified -// allocation node in a data structure graph is eligable for pool allocation. -// -static bool isNotPoolableAlloc(const AllocDSNode *DS) { - if (DS->isAllocaNode()) return true; // Do not pool allocate alloca's. - return false; -} - -// processFunction - Convert a function to use pool allocation where -// available. -// -bool PoolAllocate::processFunction(Function *F) { - // Get the closed datastructure graph for the current function... if there are - // any allocations in this graph that are not escaping, we need to pool - // allocate them here! - // - FunctionDSGraph &IPGraph = DS->getClosedDSGraph(F); - - // Get all of the allocations that do not escape the current function. Since - // they are still live (they exist in the graph at all), this means we must - // have scalar references to these nodes, but the scalars are never returned. - // - vector Allocs; - IPGraph.getNonEscapingAllocations(Allocs); - - // Filter out allocations that we cannot handle. Currently, this includes - // variable sized array allocations and alloca's (which we do not want to - // pool allocate) - // - Allocs.erase(std::remove_if(Allocs.begin(), Allocs.end(), isNotPoolableAlloc), - Allocs.end()); - - - if (Allocs.empty()) return false; // Nothing to do. - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "Transforming Function: " << F->getName() << "\n"; -#endif - - // Insert instructions into the function we are processing to create all of - // the memory pool objects themselves. This also inserts destruction code. - // This fills in the PoolDescs map to associate the alloc node with the - // allocation of the memory pool corresponding to it. - // - map PoolDescs; - CreatePools(F, Allocs, PoolDescs); - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "Transformed Entry Function: \n" << F; -#endif - - // Now we need to figure out what called functions we need to transform, and - // how. To do this, we look at all of the scalars, seeing which functions are - // either used as a scalar value (so they return a data structure), or are - // passed one of our scalar values. - // - transformFunctionBody(F, IPGraph, PoolDescs); - - return true; -} - - -//===----------------------------------------------------------------------===// -// -// NewInstructionCreator - This class is used to traverse the function being -// modified, changing each instruction visit'ed to use and provide pointer -// indexes instead of real pointers. This is what changes the body of a -// function to use pool allocation. -// -class NewInstructionCreator : public InstVisitor { - PoolAllocate &PoolAllocator; - vector &Scalars; - map &CallMap; - map &XFormMap; // Map old pointers to new indexes - - struct RefToUpdate { - Instruction *I; // Instruction to update - unsigned OpNum; // Operand number to update - Value *OldVal; // The old value it had - - RefToUpdate(Instruction *i, unsigned o, Value *ov) - : I(i), OpNum(o), OldVal(ov) {} - }; - vector ReferencesToUpdate; - - const ScalarInfo &getScalarRef(const Value *V) { - for (unsigned i = 0, e = Scalars.size(); i != e; ++i) - if (Scalars[i].Val == V) return Scalars[i]; - - cerr << "Could not find scalar " << V << " in scalar map!\n"; - assert(0 && "Scalar not found in getScalar!"); - abort(); - return Scalars[0]; - } - - const ScalarInfo *getScalar(const Value *V) { - for (unsigned i = 0, e = Scalars.size(); i != e; ++i) - if (Scalars[i].Val == V) return &Scalars[i]; - return 0; - } - - BasicBlock::iterator ReplaceInstWith(Instruction &I, Instruction *New) { - BasicBlock *BB = I.getParent(); - BasicBlock::iterator RI = &I; - BB->getInstList().remove(RI); - BB->getInstList().insert(RI, New); - XFormMap[&I] = New; - return New; - } - - Instruction *createPoolBaseInstruction(Value *PtrVal) { - const ScalarInfo &SC = getScalarRef(PtrVal); - vector Args(3); - Args[0] = ConstantUInt::get(Type::UIntTy, 0); // No pointer offset - Args[1] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of pool descriptr - Args[2] = ConstantUInt::get(Type::UByteTy, 0); // Field #0 of poolalloc val - return new LoadInst(SC.Pool.Handle, Args, PtrVal->getName()+".poolbase"); - } - - -public: - NewInstructionCreator(PoolAllocate &PA, vector &S, - map &C, - map &X) - : PoolAllocator(PA), Scalars(S), CallMap(C), XFormMap(X) {} - - - // updateReferences - The NewInstructionCreator is responsible for creating - // new instructions to replace the old ones in the function, and then link up - // references to values to their new values. For it to do this, however, it - // keeps track of information about the value mapping of old values to new - // values that need to be patched up. Given this value map and a set of - // instruction operands to patch, updateReferences performs the updates. - // - void updateReferences() { - for (unsigned i = 0, e = ReferencesToUpdate.size(); i != e; ++i) { - RefToUpdate &Ref = ReferencesToUpdate[i]; - Value *NewVal = XFormMap[Ref.OldVal]; - - if (NewVal == 0) { - if (isa(Ref.OldVal) && // Refering to a null ptr? - cast(Ref.OldVal)->isNullValue()) { - // Transform the null pointer into a null index... caching in XFormMap - XFormMap[Ref.OldVal] = NewVal = Constant::getNullValue(POINTERTYPE); - //} else if (isa(Ref.OldVal)) { - } else { - cerr << "Unknown reference to: " << Ref.OldVal << "\n"; - assert(XFormMap[Ref.OldVal] && - "Reference to value that was not updated found!"); - } - } - - Ref.I->setOperand(Ref.OpNum, NewVal); - } - ReferencesToUpdate.clear(); - } - - //===--------------------------------------------------------------------===// - // Transformation methods: - // These methods specify how each type of instruction is transformed by the - // NewInstructionCreator instance... - //===--------------------------------------------------------------------===// - - void visitGetElementPtrInst(GetElementPtrInst &I) { - assert(0 && "Cannot transform get element ptr instructions yet!"); - } - - // Replace the load instruction with a new one. - void visitLoadInst(LoadInst &I) { - vector BeforeInsts; - - // Cast our index to be a UIntTy so we can use it to index into the pool... - CastInst *Index = new CastInst(Constant::getNullValue(POINTERTYPE), - Type::UIntTy, I.getOperand(0)->getName()); - BeforeInsts.push_back(Index); - ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I.getOperand(0))); - - // Include the pool base instruction... - Instruction *PoolBase = createPoolBaseInstruction(I.getOperand(0)); - BeforeInsts.push_back(PoolBase); - - Instruction *IdxInst = - BinaryOperator::create(Instruction::Add, *I.idx_begin(), Index, - I.getName()+".idx"); - BeforeInsts.push_back(IdxInst); - - vector Indices(I.idx_begin(), I.idx_end()); - Indices[0] = IdxInst; - Instruction *Address = new GetElementPtrInst(PoolBase, Indices, - I.getName()+".addr"); - BeforeInsts.push_back(Address); - - Instruction *NewLoad = new LoadInst(Address, I.getName()); - - // Replace the load instruction with the new load instruction... - BasicBlock::iterator II = ReplaceInstWith(I, NewLoad); - - // Add all of the instructions before the load... - NewLoad->getParent()->getInstList().insert(II, BeforeInsts.begin(), - BeforeInsts.end()); - - // If not yielding a pool allocated pointer, use the new load value as the - // value in the program instead of the old load value... - // - if (!getScalar(&I)) - I.replaceAllUsesWith(NewLoad); - } - - // Replace the store instruction with a new one. In the store instruction, - // the value stored could be a pointer type, meaning that the new store may - // have to change one or both of it's operands. - // - void visitStoreInst(StoreInst &I) { - assert(getScalar(I.getOperand(1)) && - "Store inst found only storing pool allocated pointer. " - "Not imp yet!"); - - Value *Val = I.getOperand(0); // The value to store... - - // Check to see if the value we are storing is a data structure pointer... - //if (const ScalarInfo *ValScalar = getScalar(I.getOperand(0))) - if (isa(I.getOperand(0)->getType())) - Val = Constant::getNullValue(POINTERTYPE); // Yes, store a dummy - - Instruction *PoolBase = createPoolBaseInstruction(I.getOperand(1)); - - // Cast our index to be a UIntTy so we can use it to index into the pool... - CastInst *Index = new CastInst(Constant::getNullValue(POINTERTYPE), - Type::UIntTy, I.getOperand(1)->getName()); - ReferencesToUpdate.push_back(RefToUpdate(Index, 0, I.getOperand(1))); - - // Instructions to add after the Index... - vector AfterInsts; - - Instruction *IdxInst = - BinaryOperator::create(Instruction::Add, *I.idx_begin(), Index, "idx"); - AfterInsts.push_back(IdxInst); - - vector Indices(I.idx_begin(), I.idx_end()); - Indices[0] = IdxInst; - Instruction *Address = new GetElementPtrInst(PoolBase, Indices, - I.getName()+"storeaddr"); - AfterInsts.push_back(Address); - - Instruction *NewStore = new StoreInst(Val, Address); - AfterInsts.push_back(NewStore); - if (Val != I.getOperand(0)) // Value stored was a pointer? - ReferencesToUpdate.push_back(RefToUpdate(NewStore, 0, I.getOperand(0))); - - - // Replace the store instruction with the cast instruction... - BasicBlock::iterator II = ReplaceInstWith(I, Index); - - // Add the pool base calculator instruction before the index... - II = ++Index->getParent()->getInstList().insert(II, PoolBase); - ++II; - - // Add the instructions that go after the index... - Index->getParent()->getInstList().insert(II, AfterInsts.begin(), - AfterInsts.end()); - } - - - // Create call to poolalloc for every malloc instruction - void visitMallocInst(MallocInst &I) { - const ScalarInfo &SCI = getScalarRef(&I); - vector Args; - - CallInst *Call; - if (!I.isArrayAllocation()) { - Args.push_back(SCI.Pool.Handle); - Call = new CallInst(PoolAllocator.PoolAlloc, Args, I.getName()); - } else { - Args.push_back(I.getArraySize()); - Args.push_back(SCI.Pool.Handle); - Call = new CallInst(PoolAllocator.PoolAllocArray, Args, I.getName()); - } - - ReplaceInstWith(I, Call); - } - - // Convert a call to poolfree for every free instruction... - void visitFreeInst(FreeInst &I) { - // Create a new call to poolfree before the free instruction - vector Args; - Args.push_back(Constant::getNullValue(POINTERTYPE)); - Args.push_back(getScalarRef(I.getOperand(0)).Pool.Handle); - Instruction *NewCall = new CallInst(PoolAllocator.PoolFree, Args); - ReplaceInstWith(I, NewCall); - ReferencesToUpdate.push_back(RefToUpdate(NewCall, 1, I.getOperand(0))); - } - - // visitCallInst - Create a new call instruction with the extra arguments for - // all of the memory pools that the call needs. - // - void visitCallInst(CallInst &I) { - TransformFunctionInfo &TI = CallMap[&I]; - - // Start with all of the old arguments... - vector Args(I.op_begin()+1, I.op_end()); - - for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i) { - // Replace all of the pointer arguments with our new pointer typed values. - if (TI.ArgInfo[i].ArgNo != -1) - Args[TI.ArgInfo[i].ArgNo] = Constant::getNullValue(POINTERTYPE); - - // Add all of the pool arguments... - Args.push_back(TI.ArgInfo[i].PoolHandle); - } - - Function *NF = PoolAllocator.getTransformedFunction(TI); - Instruction *NewCall = new CallInst(NF, Args, I.getName()); - ReplaceInstWith(I, NewCall); - - // Keep track of the mapping of operands so that we can resolve them to real - // values later. - Value *RetVal = NewCall; - for (unsigned i = 0, e = TI.ArgInfo.size(); i != e; ++i) - if (TI.ArgInfo[i].ArgNo != -1) - ReferencesToUpdate.push_back(RefToUpdate(NewCall, TI.ArgInfo[i].ArgNo+1, - I.getOperand(TI.ArgInfo[i].ArgNo+1))); - else - RetVal = 0; // If returning a pointer, don't change retval... - - // If not returning a pointer, use the new call as the value in the program - // instead of the old call... - // - if (RetVal) - I.replaceAllUsesWith(RetVal); - } - - // visitPHINode - Create a new PHI node of POINTERTYPE for all of the old Phi - // nodes... - // - void visitPHINode(PHINode &PN) { - Value *DummyVal = Constant::getNullValue(POINTERTYPE); - PHINode *NewPhi = new PHINode(POINTERTYPE, PN.getName()); - for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) { - NewPhi->addIncoming(DummyVal, PN.getIncomingBlock(i)); - ReferencesToUpdate.push_back(RefToUpdate(NewPhi, i*2, - PN.getIncomingValue(i))); - } - - ReplaceInstWith(PN, NewPhi); - } - - // visitReturnInst - Replace ret instruction with a new return... - void visitReturnInst(ReturnInst &I) { - Instruction *Ret = new ReturnInst(Constant::getNullValue(POINTERTYPE)); - ReplaceInstWith(I, Ret); - ReferencesToUpdate.push_back(RefToUpdate(Ret, 0, I.getOperand(0))); - } - - // visitSetCondInst - Replace a conditional test instruction with a new one - void visitSetCondInst(SetCondInst &SCI) { - BinaryOperator &I = (BinaryOperator&)SCI; - Value *DummyVal = Constant::getNullValue(POINTERTYPE); - BinaryOperator *New = BinaryOperator::create(I.getOpcode(), DummyVal, - DummyVal, I.getName()); - ReplaceInstWith(I, New); - - ReferencesToUpdate.push_back(RefToUpdate(New, 0, I.getOperand(0))); - ReferencesToUpdate.push_back(RefToUpdate(New, 1, I.getOperand(1))); - - // Make sure branches refer to the new condition... - I.replaceAllUsesWith(New); - } - - void visitInstruction(Instruction &I) { - cerr << "Unknown instruction to FunctionBodyTransformer:\n" << I; - } -}; - - -// PoolBaseLoadEliminator - Every load and store through a pool allocated -// pointer causes a load of the real pool base out of the pool descriptor. -// Iterate through the function, doing a local elimination pass of duplicate -// loads. This attempts to turn the all too common: -// -// %reg109.poolbase22 = load %root.pool* %root.pool, uint 0, ubyte 0, ubyte 0 -// %reg207 = load %root.p* %reg109.poolbase22, uint %reg109, ubyte 0, ubyte 0 -// %reg109.poolbase23 = load %root.pool* %root.pool, uint 0, ubyte 0, ubyte 0 -// store double %reg207, %root.p* %reg109.poolbase23, uint %reg109, ... -// -// into: -// %reg109.poolbase22 = load %root.pool* %root.pool, uint 0, ubyte 0, ubyte 0 -// %reg207 = load %root.p* %reg109.poolbase22, uint %reg109, ubyte 0, ubyte 0 -// store double %reg207, %root.p* %reg109.poolbase22, uint %reg109, ... -// -// -class PoolBaseLoadEliminator : public InstVisitor { - // PoolDescValues - Keep track of the values in the current function that are - // pool descriptors (loads from which we want to eliminate). - // - vector PoolDescValues; - - // PoolDescMap - As we are analyzing a BB, keep track of which load to use - // when referencing a pool descriptor. - // - map PoolDescMap; - - // These two fields keep track of statistics of how effective we are, if - // debugging is enabled. - // - unsigned Eliminated, Remaining; -public: - // Compact the pool descriptor map into a list of the pool descriptors in the - // current context that we should know about... - // - PoolBaseLoadEliminator(const map &PoolDescs) { - Eliminated = Remaining = 0; - for (map::const_iterator I = PoolDescs.begin(), - E = PoolDescs.end(); I != E; ++I) - PoolDescValues.push_back(I->second.Handle); - - // Remove duplicates from the list of pool values - sort(PoolDescValues.begin(), PoolDescValues.end()); - PoolDescValues.erase(unique(PoolDescValues.begin(), PoolDescValues.end()), - PoolDescValues.end()); - } - -#ifdef DEBUG_POOLBASE_LOAD_ELIMINATOR - void visitFunction(Function &F) { - cerr << "Pool Load Elim '" << F.getName() << "'\t"; - } - ~PoolBaseLoadEliminator() { - unsigned Total = Eliminated+Remaining; - if (Total) - cerr << "removed " << Eliminated << "[" - << Eliminated*100/Total << "%] loads, leaving " - << Remaining << ".\n"; - } -#endif - - // Loop over the function, looking for loads to eliminate. Because we are a - // local transformation, we reset all of our state when we enter a new basic - // block. - // - void visitBasicBlock(BasicBlock &) { - PoolDescMap.clear(); // Forget state. - } - - // Starting with an empty basic block, we scan it looking for loads of the - // pool descriptor. When we find a load, we add it to the PoolDescMap, - // indicating that we have a value available to recycle next time we see the - // poolbase of this instruction being loaded. - // - void visitLoadInst(LoadInst &LI) { - Value *LoadAddr = LI.getPointerOperand(); - map::iterator VIt = PoolDescMap.find(LoadAddr); - if (VIt != PoolDescMap.end()) { // We already have a value for this load? - LI.replaceAllUsesWith(VIt->second); // Make the current load dead - ++Eliminated; - } else { - // This load might not be a load of a pool pointer, check to see if it is - if (LI.getNumOperands() == 4 && // load pool, uint 0, ubyte 0, ubyte 0 - find(PoolDescValues.begin(), PoolDescValues.end(), LoadAddr) != - PoolDescValues.end()) { - - assert("Make sure it's a load of the pool base, not a chaining field" && - LI.getOperand(1) == Constant::getNullValue(Type::UIntTy) && - LI.getOperand(2) == Constant::getNullValue(Type::UByteTy) && - LI.getOperand(3) == Constant::getNullValue(Type::UByteTy)); - - // If it is a load of a pool base, keep track of it for future reference - PoolDescMap.insert(std::make_pair(LoadAddr, &LI)); - ++Remaining; - } - } - } - - // If we run across a function call, forget all state... Calls to - // poolalloc/poolfree can invalidate the pool base pointer, so it should be - // reloaded the next time it is used. Furthermore, a call to a random - // function might call one of these functions, so be conservative. Through - // more analysis, this could be improved in the future. - // - void visitCallInst(CallInst &) { - PoolDescMap.clear(); - } -}; - -static void addNodeMapping(DSNode *SrcNode, const PointerValSet &PVS, - map &NodeMapping) { - for (unsigned i = 0, e = PVS.size(); i != e; ++i) - if (NodeMapping[SrcNode].add(PVS[i])) { // Not in map yet? - assert(PVS[i].Index == 0 && "Node indexing not supported yet!"); - DSNode *DestNode = PVS[i].Node; - - // Loop over all of the outgoing links in the mapped graph - for (unsigned l = 0, le = DestNode->getNumOutgoingLinks(); l != le; ++l) { - PointerValSet &SrcSet = SrcNode->getOutgoingLink(l); - const PointerValSet &DestSet = DestNode->getOutgoingLink(l); - - // Add all of the node mappings now! - for (unsigned si = 0, se = SrcSet.size(); si != se; ++si) { - assert(SrcSet[si].Index == 0 && "Can't handle node offset!"); - addNodeMapping(SrcSet[si].Node, DestSet, NodeMapping); - } - } - } -} - -// CalculateNodeMapping - There is a partial isomorphism between the graph -// passed in and the graph that is actually used by the function. We need to -// figure out what this mapping is so that we can transformFunctionBody the -// instructions in the function itself. Note that every node in the graph that -// we are interested in must be both in the local graph of the called function, -// and in the local graph of the calling function. Because of this, we only -// define the mapping for these nodes [conveniently these are the only nodes we -// CAN define a mapping for...] -// -// The roots of the graph that we are transforming is rooted in the arguments -// passed into the function from the caller. This is where we start our -// mapping calculation. -// -// The NodeMapping calculated maps from the callers graph to the called graph. -// -static void CalculateNodeMapping(Function *F, TransformFunctionInfo &TFI, - FunctionDSGraph &CallerGraph, - FunctionDSGraph &CalledGraph, - map &NodeMapping) { - int LastArgNo = -2; - for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) { - // Figure out what nodes in the called graph the TFI.ArgInfo[i].Node node - // corresponds to... - // - // Only consider first node of sequence. Extra nodes may may be added - // to the TFI if the data structure requires more nodes than just the - // one the argument points to. We are only interested in the one the - // argument points to though. - // - if (TFI.ArgInfo[i].ArgNo != LastArgNo) { - if (TFI.ArgInfo[i].ArgNo == -1) { - addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getRetNodes(), - NodeMapping); - } else { - // Figure out which node argument # ArgNo points to in the called graph. - Function::aiterator AI = F->abegin(); - std::advance(AI, TFI.ArgInfo[i].ArgNo); - addNodeMapping(TFI.ArgInfo[i].Node, CalledGraph.getValueMap()[AI], - NodeMapping); - } - LastArgNo = TFI.ArgInfo[i].ArgNo; - } - } -} - - - - -// addCallInfo - For a specified function call CI, figure out which pool -// descriptors need to be passed in as arguments, and which arguments need to be -// transformed into indices. If Arg != -1, the specified call argument is -// passed in as a pointer to a data structure. -// -void TransformFunctionInfo::addCallInfo(DataStructure *DS, CallInst *CI, - int Arg, DSNode *GraphNode, - map &PoolDescs) { - assert(CI->getCalledFunction() && "Cannot handle indirect calls yet!"); - assert(Func == 0 || Func == CI->getCalledFunction() && - "Function call record should always call the same function!"); - assert(Call == 0 || Call == CI && - "Call element already filled in with different value!"); - Func = CI->getCalledFunction(); - Call = CI; - //FunctionDSGraph &CalledGraph = DS->getClosedDSGraph(Func); - - // For now, add the entire graph that is pointed to by the call argument. - // This graph can and should be pruned to only what the function itself will - // use, because often this will be a dramatically smaller subset of what we - // are providing. - // - // FIXME: This should use pool links instead of extra arguments! - // - for (df_iterator I = df_begin(GraphNode), E = df_end(GraphNode); - I != E; ++I) - ArgInfo.push_back(CallArgInfo(Arg, *I, PoolDescs[*I].Handle)); -} - -static void markReachableNodes(const PointerValSet &Vals, - set &ReachableNodes) { - for (unsigned n = 0, ne = Vals.size(); n != ne; ++n) { - DSNode *N = Vals[n].Node; - if (ReachableNodes.count(N) == 0) // Haven't already processed node? - ReachableNodes.insert(df_begin(N), df_end(N)); // Insert all - } -} - -// Make sure that all dependant arguments are added to this transformation info. -// For example, if we call foo(null, P) and foo treats it's first and second -// arguments as belonging to the same data structure, the we MUST add entries to -// know that the null needs to be transformed into an index as well. -// -void TransformFunctionInfo::ensureDependantArgumentsIncluded(DataStructure *DS, - map &PoolDescs) { - // FIXME: This does not work for indirect function calls!!! - if (Func == 0) return; // FIXME! - - // Make sure argument entries are sorted. - finalizeConstruction(); - - // Loop over the function signature, checking to see if there are any pointer - // arguments that we do not convert... if there is something we haven't - // converted, set done to false. - // - unsigned PtrNo = 0; - bool Done = true; - if (isa(Func->getReturnType())) // Make sure we convert retval - if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == -1) { - // We DO transform the ret val... skip all possible entries for retval - while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == -1) - PtrNo++; - } else { - Done = false; - } - - unsigned i = 0; - for (Function::aiterator I = Func->abegin(), E = Func->aend(); I!=E; ++I,++i){ - if (isa(I->getType())) { - if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == (int)i) { - // We DO transform this arg... skip all possible entries for argument - while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == (int)i) - PtrNo++; - } else { - Done = false; - break; - } - } - } - - // If we already have entries for all pointer arguments and retvals, there - // certainly is no work to do. Bail out early to avoid building relatively - // expensive data structures. - // - if (Done) return; - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "Must ensure dependant arguments for: " << Func->getName() << "\n"; -#endif - - // Otherwise, we MIGHT have to add the arguments/retval if they are part of - // the same datastructure graph as some other argument or retval that we ARE - // processing. - // - // Get the data structure graph for the called function. - // - FunctionDSGraph &CalledDS = DS->getClosedDSGraph(Func); - - // Build a mapping between the nodes in our current graph and the nodes in the - // called function's graph. We build it based on our _incomplete_ - // transformation information, because it contains all of the info that we - // should need. - // - map NodeMapping; - CalculateNodeMapping(Func, *this, - DS->getClosedDSGraph(Call->getParent()->getParent()), - CalledDS, NodeMapping); - - // Build the inverted version of the node mapping, that maps from a node in - // the called functions graph to a single node in the caller graph. - // - map InverseNodeMap; - for (map::iterator I = NodeMapping.begin(), - E = NodeMapping.end(); I != E; ++I) { - PointerValSet &CalledNodes = I->second; - for (unsigned i = 0, e = CalledNodes.size(); i != e; ++i) - InverseNodeMap[CalledNodes[i].Node] = I->first; - } - NodeMapping.clear(); // Done with information, free memory - - // Build a set of reachable nodes from the arguments/retval that we ARE - // passing in... - set ReachableNodes; - - // Loop through all of the arguments, marking all of the reachable data - // structure nodes reachable if they are from this pointer... - // - for (unsigned i = 0, e = ArgInfo.size(); i != e; ++i) { - if (ArgInfo[i].ArgNo == -1) { - if (i == 0) // Only process retvals once (performance opt) - markReachableNodes(CalledDS.getRetNodes(), ReachableNodes); - } else { // If it's an argument value... - Function::aiterator AI = Func->abegin(); - std::advance(AI, ArgInfo[i].ArgNo); - if (isa(AI->getType())) - markReachableNodes(CalledDS.getValueMap()[AI], ReachableNodes); - } - } - - // Now that we know which nodes are already reachable, see if any of the - // arguments that we are not passing values in for can reach one of the - // existing nodes... - // - - // IN THEORY, we should allow arbitrary paths from the argument to - // nodes we know about. The problem is that if we do this, then I don't know - // how to get pool pointers for this head list. Since we are completely - // deadline driven, I'll just allow direct accesses to the graph. - // - - PtrNo = 0; - if (isa(Func->getReturnType())) // Make sure we convert retval - if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == -1) { - // We DO transform the ret val... skip all possible entries for retval - while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == -1) - PtrNo++; - } else { - // See what the return value points to... - - // FIXME: This should generalize to any number of nodes, just see if any - // are reachable. - assert(CalledDS.getRetNodes().size() == 1 && - "Assumes only one node is returned"); - DSNode *N = CalledDS.getRetNodes()[0].Node; - - // If the return value is not marked as being passed in, but it NEEDS to - // be transformed, then make it known now. - // - if (ReachableNodes.count(N)) { -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "ensure dependant arguments adds return value entry!\n"; -#endif - addCallInfo(DS, Call, -1, InverseNodeMap[N], PoolDescs); - - // Keep sorted! - finalizeConstruction(); - } - } - - i = 0; - for (Function::aiterator I = Func->abegin(), E = Func->aend(); I!=E; ++I, ++i) - if (isa(I->getType())) { - if (PtrNo < ArgInfo.size() && ArgInfo[PtrNo++].ArgNo == (int)i) { - // We DO transform this arg... skip all possible entries for argument - while (PtrNo < ArgInfo.size() && ArgInfo[PtrNo].ArgNo == (int)i) - PtrNo++; - } else { - // This should generalize to any number of nodes, just see if any are - // reachable. - assert(CalledDS.getValueMap()[I].size() == 1 && - "Only handle case where pointing to one node so far!"); - - // If the arg is not marked as being passed in, but it NEEDS to - // be transformed, then make it known now. - // - DSNode *N = CalledDS.getValueMap()[I][0].Node; - if (ReachableNodes.count(N)) { -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "ensure dependant arguments adds for arg #" << i << "\n"; -#endif - addCallInfo(DS, Call, i, InverseNodeMap[N], PoolDescs); - - // Keep sorted! - finalizeConstruction(); - } - } - } -} - - -// transformFunctionBody - This transforms the instruction in 'F' to use the -// pools specified in PoolDescs when modifying data structure nodes specified in -// the PoolDescs map. Specifically, scalar values specified in the Scalars -// vector must be remapped. IPFGraph is the closed data structure graph for F, -// of which the PoolDescriptor nodes come from. -// -void PoolAllocate::transformFunctionBody(Function *F, FunctionDSGraph &IPFGraph, - map &PoolDescs) { - - // Loop through the value map looking for scalars that refer to nonescaping - // allocations. Add them to the Scalars vector. Note that we may have - // multiple entries in the Scalars vector for each value if it points to more - // than one object. - // - map &ValMap = IPFGraph.getValueMap(); - vector Scalars; - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "Building scalar map for fn '" << F->getName() << "' body:\n"; -#endif - - for (map::iterator I = ValMap.begin(), - E = ValMap.end(); I != E; ++I) { - const PointerValSet &PVS = I->second; // Set of things pointed to by scalar - - // Check to see if the scalar points to a data structure node... - for (unsigned i = 0, e = PVS.size(); i != e; ++i) { - if (PVS[i].Index) { cerr << "Problem in " << F->getName() << " for " << I->first << "\n"; } - assert(PVS[i].Index == 0 && "Nonzero not handled yet!"); - - // If the allocation is in the nonescaping set... - map::iterator AI = PoolDescs.find(PVS[i].Node); - if (AI != PoolDescs.end()) { // Add it to the list of scalars - Scalars.push_back(ScalarInfo(I->first, AI->second)); -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "\nScalar Mapping from:" << I->first - << "Scalar Mapping to: "; PVS.print(cerr); -#endif - } - } - } - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "\nIn '" << F->getName() - << "': Found the following values that point to poolable nodes:\n"; - - for (unsigned i = 0, e = Scalars.size(); i != e; ++i) - cerr << Scalars[i].Val; - cerr << "\n"; -#endif - - // CallMap - Contain an entry for every call instruction that needs to be - // transformed. Each entry in the map contains information about what we need - // to do to each call site to change it to work. - // - map CallMap; - - // Now we need to figure out what called functions we need to transform, and - // how. To do this, we look at all of the scalars, seeing which functions are - // either used as a scalar value (so they return a data structure), or are - // passed one of our scalar values. - // - for (unsigned i = 0, e = Scalars.size(); i != e; ++i) { - Value *ScalarVal = Scalars[i].Val; - - // Check to see if the scalar _IS_ a call... - if (CallInst *CI = dyn_cast(ScalarVal)) - // If so, add information about the pool it will be returning... - CallMap[CI].addCallInfo(DS, CI, -1, Scalars[i].Pool.Node, PoolDescs); - - // Check to see if the scalar is an operand to a call... - for (Value::use_iterator UI = ScalarVal->use_begin(), - UE = ScalarVal->use_end(); UI != UE; ++UI) { - if (CallInst *CI = dyn_cast(*UI)) { - // Find out which operand this is to the call instruction... - User::op_iterator OI = find(CI->op_begin(), CI->op_end(), ScalarVal); - assert(OI != CI->op_end() && "Call on use list but not an operand!?"); - assert(OI != CI->op_begin() && "Pointer operand is call destination?"); - - // FIXME: This is broken if the same pointer is passed to a call more - // than once! It will get multiple entries for the first pointer. - - // Add the operand number and pool handle to the call table... - CallMap[CI].addCallInfo(DS, CI, OI-CI->op_begin()-1, - Scalars[i].Pool.Node, PoolDescs); - } - } - } - - // Make sure that all dependant arguments are added as well. For example, if - // we call foo(null, P) and foo treats it's first and second arguments as - // belonging to the same data structure, the we MUST set up the CallMap to - // know that the null needs to be transformed into an index as well. - // - for (map::iterator I = CallMap.begin(); - I != CallMap.end(); ++I) - I->second.ensureDependantArgumentsIncluded(DS, PoolDescs); - -#ifdef DEBUG_TRANSFORM_PROGRESS - // Print out call map... - for (map::iterator I = CallMap.begin(); - I != CallMap.end(); ++I) { - cerr << "For call: " << I->first; - cerr << I->second.Func->getName() << " must pass pool pointer for args #"; - for (unsigned i = 0; i < I->second.ArgInfo.size(); ++i) - cerr << I->second.ArgInfo[i].ArgNo << ", "; - cerr << "\n\n"; - } -#endif - - // Loop through all of the call nodes, recursively creating the new functions - // that we want to call... This uses a map to prevent infinite recursion and - // to avoid duplicating functions unneccesarily. - // - for (map::iterator I = CallMap.begin(), - E = CallMap.end(); I != E; ++I) { - // Transform all of the functions we need, or at least ensure there is a - // cached version available. - transformFunction(I->second, IPFGraph, PoolDescs); - } - - // Now that all of the functions that we want to call are available, transform - // the local function so that it uses the pools locally and passes them to the - // functions that we just hacked up. - // - - // First step, find the instructions to be modified. - vector InstToFix; - for (unsigned i = 0, e = Scalars.size(); i != e; ++i) { - Value *ScalarVal = Scalars[i].Val; - - // Check to see if the scalar _IS_ an instruction. If so, it is involved. - if (Instruction *Inst = dyn_cast(ScalarVal)) - InstToFix.push_back(Inst); - - // All all of the instructions that use the scalar as an operand... - for (Value::use_iterator UI = ScalarVal->use_begin(), - UE = ScalarVal->use_end(); UI != UE; ++UI) - InstToFix.push_back(cast(*UI)); - } - - // Make sure that we get return instructions that return a null value from the - // function... - // - if (!IPFGraph.getRetNodes().empty()) { - assert(IPFGraph.getRetNodes().size() == 1 && "Can only return one node?"); - PointerVal RetNode = IPFGraph.getRetNodes()[0]; - assert(RetNode.Index == 0 && "Subindexing not implemented yet!"); - - // Only process return instructions if the return value of this function is - // part of one of the data structures we are transforming... - // - if (PoolDescs.count(RetNode.Node)) { - // Loop over all of the basic blocks, adding return instructions... - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) - if (ReturnInst *RI = dyn_cast(I->getTerminator())) - InstToFix.push_back(RI); - } - } - - - - // Eliminate duplicates by sorting, then removing equal neighbors. - sort(InstToFix.begin(), InstToFix.end()); - InstToFix.erase(unique(InstToFix.begin(), InstToFix.end()), InstToFix.end()); - - // Loop over all of the instructions to transform, creating the new - // replacement instructions for them. This also unlinks them from the - // function so they can be safely deleted later. - // - map XFormMap; - NewInstructionCreator NIC(*this, Scalars, CallMap, XFormMap); - - // Visit all instructions... creating the new instructions that we need and - // unlinking the old instructions from the function... - // -#ifdef DEBUG_TRANSFORM_PROGRESS - for (unsigned i = 0, e = InstToFix.size(); i != e; ++i) { - cerr << "Fixing: " << InstToFix[i]; - NIC.visit(*InstToFix[i]); - } -#else - NIC.visit(InstToFix.begin(), InstToFix.end()); -#endif - - // Make all instructions we will delete "let go" of their operands... so that - // we can safely delete Arguments whose types have changed... - // - for_each(InstToFix.begin(), InstToFix.end(), - std::mem_fun(&Instruction::dropAllReferences)); - - // Loop through all of the pointer arguments coming into the function, - // replacing them with arguments of POINTERTYPE to match the function type of - // the function. - // - FunctionType::ParamTypes::const_iterator TI = - F->getFunctionType()->getParamTypes().begin(); - for (Function::aiterator I = F->abegin(), E = F->aend(); I != E; ++I, ++TI) { - if (I->getType() != *TI) { - assert(isa(I->getType()) && *TI == POINTERTYPE); - Argument *NewArg = new Argument(*TI, I->getName()); - XFormMap[I] = NewArg; // Map old arg into new arg... - - // Replace the old argument and then delete it... - I = F->getArgumentList().erase(I); - I = F->getArgumentList().insert(I, NewArg); - } - } - - // Now that all of the new instructions have been created, we can update all - // of the references to dummy values to be references to the actual values - // that are computed. - // - NIC.updateReferences(); - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "TRANSFORMED FUNCTION:\n" << F; -#endif - - // Delete all of the "instructions to fix" - for_each(InstToFix.begin(), InstToFix.end(), deleter); - - // Eliminate pool base loads that we can easily prove are redundant - if (!DisableRLE) - PoolBaseLoadEliminator(PoolDescs).visit(F); - - // Since we have liberally hacked the function to pieces, we want to inform - // the datastructure pass that its internal representation is out of date. - // - DS->invalidateFunction(F); -} - - - -// transformFunction - Transform the specified function the specified way. It -// we have already transformed that function that way, don't do anything. The -// nodes in the TransformFunctionInfo come out of callers data structure graph. -// -void PoolAllocate::transformFunction(TransformFunctionInfo &TFI, - FunctionDSGraph &CallerIPGraph, - map &CallerPoolDesc) { - if (getTransformedFunction(TFI)) return; // Function xformation already done? - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "********** Entering transformFunction for " - << TFI.Func->getName() << ":\n"; - for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) - cerr << " ArgInfo[" << i << "] = " << TFI.ArgInfo[i].ArgNo << "\n"; - cerr << "\n"; -#endif - - const FunctionType *OldFuncType = TFI.Func->getFunctionType(); - - assert(!OldFuncType->isVarArg() && "Vararg functions not handled yet!"); - - // Build the type for the new function that we are transforming - vector ArgTys; - ArgTys.reserve(OldFuncType->getNumParams()+TFI.ArgInfo.size()); - for (unsigned i = 0, e = OldFuncType->getNumParams(); i != e; ++i) - ArgTys.push_back(OldFuncType->getParamType(i)); - - const Type *RetType = OldFuncType->getReturnType(); - - // Add one pool pointer for every argument that needs to be supplemented. - for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) { - if (TFI.ArgInfo[i].ArgNo == -1) - RetType = POINTERTYPE; // Return a pointer - else - ArgTys[TFI.ArgInfo[i].ArgNo] = POINTERTYPE; // Pass a pointer - ArgTys.push_back(PointerType::get(CallerPoolDesc.find(TFI.ArgInfo[i].Node) - ->second.PoolType)); - } - - // Build the new function type... - const FunctionType *NewFuncType = FunctionType::get(RetType, ArgTys, - OldFuncType->isVarArg()); - - // The new function is internal, because we know that only we can call it. - // This also helps subsequent IP transformations to eliminate duplicated pool - // pointers (which look like the same value is always passed into a parameter, - // allowing it to be easily eliminated). - // - Function *NewFunc = new Function(NewFuncType, true, - TFI.Func->getName()+".poolxform"); - CurModule->getFunctionList().push_back(NewFunc); - - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "Created function prototype: " << NewFunc << "\n"; -#endif - - // Add the newly formed function to the TransformedFunctions table so that - // infinite recursion does not occur! - // - TransformedFunctions[TFI] = NewFunc; - - // Add arguments to the function... starting with all of the old arguments - vector ArgMap; - for (Function::const_aiterator I = TFI.Func->abegin(), E = TFI.Func->aend(); - I != E; ++I) { - Argument *NFA = new Argument(I->getType(), I->getName()); - NewFunc->getArgumentList().push_back(NFA); - ArgMap.push_back(NFA); // Keep track of the arguments - } - - // Now add all of the arguments corresponding to pools passed in... - for (unsigned i = 0, e = TFI.ArgInfo.size(); i != e; ++i) { - CallArgInfo &AI = TFI.ArgInfo[i]; - string Name; - if (AI.ArgNo == -1) - Name = "ret"; - else - Name = ArgMap[AI.ArgNo]->getName(); // Get the arg name - const Type *Ty = PointerType::get(CallerPoolDesc[AI.Node].PoolType); - Argument *NFA = new Argument(Ty, Name+".pool"); - NewFunc->getArgumentList().push_back(NFA); - } - - // Now clone the body of the old function into the new function... - CloneFunctionInto(NewFunc, TFI.Func, ArgMap); - - // Okay, now we have a function that is identical to the old one, except that - // it has extra arguments for the pools coming in. Now we have to get the - // data structure graph for the function we are replacing, and figure out how - // our graph nodes map to the graph nodes in the dest function. - // - FunctionDSGraph &DSGraph = DS->getClosedDSGraph(NewFunc); - - // NodeMapping - Multimap from callers graph to called graph. We are - // guaranteed that the called function graph has more nodes than the caller, - // or exactly the same number of nodes. This is because the called function - // might not know that two nodes are merged when considering the callers - // context, but the caller obviously does. Because of this, a single node in - // the calling function's data structure graph can map to multiple nodes in - // the called functions graph. - // - map NodeMapping; - - CalculateNodeMapping(NewFunc, TFI, CallerIPGraph, DSGraph, - NodeMapping); - - // Print out the node mapping... -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "\nNode mapping for call of " << NewFunc->getName() << "\n"; - for (map::iterator I = NodeMapping.begin(); - I != NodeMapping.end(); ++I) { - cerr << "Map: "; I->first->print(cerr); - cerr << "To: "; I->second.print(cerr); - cerr << "\n"; - } -#endif - - // Fill in the PoolDescriptor information for the transformed function so that - // it can determine which value holds the pool descriptor for each data - // structure node that it accesses. - // - map PoolDescs; - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "\nCalculating the pool descriptor map:\n"; -#endif - - // Calculate as much of the pool descriptor map as possible. Since we have - // the node mapping between the caller and callee functions, and we have the - // pool descriptor information of the caller, we can calculate a partical pool - // descriptor map for the called function. - // - // The nodes that we do not have complete information for are the ones that - // are accessed by loading pointers derived from arguments passed in, but that - // are not passed in directly. In this case, we have all of the information - // except a pool value. If the called function refers to this pool, the pool - // value will be loaded from the pool graph and added to the map as neccesary. - // - for (map::iterator I = NodeMapping.begin(); - I != NodeMapping.end(); ++I) { - DSNode *CallerNode = I->first; - PoolInfo &CallerPI = CallerPoolDesc[CallerNode]; - - // Check to see if we have a node pointer passed in for this value... - Value *CalleeValue = 0; - for (unsigned a = 0, ae = TFI.ArgInfo.size(); a != ae; ++a) - if (TFI.ArgInfo[a].Node == CallerNode) { - // Calculate the argument number that the pool is to the function - // call... The call instruction should not have the pool operands added - // yet. - unsigned ArgNo = TFI.Call->getNumOperands()-1+a; -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "Should be argument #: " << ArgNo << "[i = " << a << "]\n"; -#endif - assert(ArgNo < NewFunc->asize() && - "Call already has pool arguments added??"); - - // Map the pool argument into the called function... - Function::aiterator AI = NewFunc->abegin(); - std::advance(AI, ArgNo); - CalleeValue = AI; - break; // Found value, quit loop - } - - // Loop over all of the data structure nodes that this incoming node maps to - // Creating a PoolInfo structure for them. - for (unsigned i = 0, e = I->second.size(); i != e; ++i) { - assert(I->second[i].Index == 0 && "Doesn't handle subindexing yet!"); - DSNode *CalleeNode = I->second[i].Node; - - // Add the descriptor. We already know everything about it by now, much - // of it is the same as the caller info. - // - PoolDescs.insert(std::make_pair(CalleeNode, - PoolInfo(CalleeNode, CalleeValue, - CallerPI.NewType, - CallerPI.PoolType))); - } - } - - // We must destroy the node mapping so that we don't have latent references - // into the data structure graph for the new function. Otherwise we get - // assertion failures when transformFunctionBody tries to invalidate the - // graph. - // - NodeMapping.clear(); - - // Now that we know everything we need about the function, transform the body - // now! - // - transformFunctionBody(NewFunc, DSGraph, PoolDescs); - -#ifdef DEBUG_TRANSFORM_PROGRESS - cerr << "Function after transformation:\n" << NewFunc; -#endif -} - -static unsigned countPointerTypes(const Type *Ty) { - if (isa(Ty)) { - return 1; - } else if (const StructType *STy = dyn_cast(Ty)) { - unsigned Num = 0; - for (unsigned i = 0, e = STy->getElementTypes().size(); i != e; ++i) - Num += countPointerTypes(STy->getElementTypes()[i]); - return Num; - } else if (const ArrayType *ATy = dyn_cast(Ty)) { - return countPointerTypes(ATy->getElementType()); - } else { - assert(Ty->isPrimitiveType() && "Unknown derived type!"); - return 0; - } -} - -// CreatePools - Insert instructions into the function we are processing to -// create all of the memory pool objects themselves. This also inserts -// destruction code. Add an alloca for each pool that is allocated to the -// PoolDescs vector. -// -void PoolAllocate::CreatePools(Function *F, const vector &Allocs, - map &PoolDescs) { - // Find all of the return nodes in the function... - vector ReturnNodes; - for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) - if (isa(I->getTerminator())) - ReturnNodes.push_back(I); - -#ifdef DEBUG_CREATE_POOLS - cerr << "Allocs that we are pool allocating:\n"; - for (unsigned i = 0, e = Allocs.size(); i != e; ++i) - Allocs[i]->dump(); -#endif - - map AbsPoolTyMap; - - // First pass over the allocations to process... - for (unsigned i = 0, e = Allocs.size(); i != e; ++i) { - // Create the pooldescriptor mapping... with null entries for everything - // except the node & NewType fields. - // - map::iterator PI = - PoolDescs.insert(std::make_pair(Allocs[i], PoolInfo(Allocs[i]))).first; - - // Add a symbol table entry for the new type if there was one for the old - // type... - string OldName = CurModule->getTypeName(Allocs[i]->getType()); - if (OldName.empty()) OldName = "node"; - CurModule->addTypeName(OldName+".p", PI->second.NewType); - - // Create the abstract pool types that will need to be resolved in a second - // pass once an abstract type is created for each pool. - // - // Can only handle limited shapes for now... - const Type *OldNodeTy = Allocs[i]->getType(); - vector PoolTypes; - - // Pool type is the first element of the pool descriptor type... - PoolTypes.push_back(getPoolType(PoolDescs[Allocs[i]].NewType)); - - unsigned NumPointers = countPointerTypes(OldNodeTy); - while (NumPointers--) // Add a different opaque type for each pointer - PoolTypes.push_back(OpaqueType::get()); - - assert(Allocs[i]->getNumLinks() == PoolTypes.size()-1 && - "Node should have same number of pointers as pool!"); - - StructType *PoolType = StructType::get(PoolTypes); - - // Add a symbol table entry for the pooltype if possible... - CurModule->addTypeName(OldName+".pool", PoolType); - - // Create the pool type, with opaque values for pointers... - AbsPoolTyMap.insert(std::make_pair(Allocs[i], PoolType)); -#ifdef DEBUG_CREATE_POOLS - cerr << "POOL TY: " << AbsPoolTyMap.find(Allocs[i])->second.get() << "\n"; -#endif - } - - // Now that we have types for all of the pool types, link them all together. - for (unsigned i = 0, e = Allocs.size(); i != e; ++i) { - PATypeHolder &PoolTyH = AbsPoolTyMap.find(Allocs[i])->second; - - // Resolve all of the outgoing pointer types of this pool node... - for (unsigned p = 0, pe = Allocs[i]->getNumLinks(); p != pe; ++p) { - PointerValSet &PVS = Allocs[i]->getLink(p); - assert(!PVS.empty() && "Outgoing edge is empty, field unused, can" - " probably just leave the type opaque or something dumb."); - unsigned Out; - for (Out = 0; AbsPoolTyMap.count(PVS[Out].Node) == 0; ++Out) - assert(Out != PVS.size() && "No edge to an outgoing allocation node!?"); - - assert(PVS[Out].Index == 0 && "Subindexing not implemented yet!"); - - // The actual struct type could change each time through the loop, so it's - // NOT loop invariant. - const StructType *PoolTy = cast(PoolTyH.get()); - - // Get the opaque type... - DerivedType *ElTy = (DerivedType*)(PoolTy->getElementTypes()[p+1].get()); - -#ifdef DEBUG_CREATE_POOLS - cerr << "Refining " << ElTy << " of " << PoolTy << " to " - << AbsPoolTyMap.find(PVS[Out].Node)->second.get() << "\n"; -#endif - - const Type *RefPoolTy = AbsPoolTyMap.find(PVS[Out].Node)->second.get(); - ElTy->refineAbstractTypeTo(PointerType::get(RefPoolTy)); - -#ifdef DEBUG_CREATE_POOLS - cerr << "Result pool type is: " << PoolTyH.get() << "\n"; -#endif - } - } - - // Create the code that goes in the entry and exit nodes for the function... - vector EntryNodeInsts; - for (unsigned i = 0, e = Allocs.size(); i != e; ++i) { - PoolInfo &PI = PoolDescs[Allocs[i]]; - - // Fill in the pool type for this pool... - PI.PoolType = AbsPoolTyMap.find(Allocs[i])->second.get(); - assert(!PI.PoolType->isAbstract() && - "Pool type should not be abstract anymore!"); - - // Add an allocation and a free for each pool... - AllocaInst *PoolAlloc = new AllocaInst(PI.PoolType, 0, - CurModule->getTypeName(PI.PoolType)); - PI.Handle = PoolAlloc; - EntryNodeInsts.push_back(PoolAlloc); - AllocationInst *AI = Allocs[i]->getAllocation(); - - // Initialize the pool. We need to know how big each allocation is. For - // our purposes here, we assume we are allocating a scalar, or array of - // constant size. - // - unsigned ElSize = TargetData.getTypeSize(PI.NewType); - - vector Args; - Args.push_back(ConstantUInt::get(Type::UIntTy, ElSize)); - Args.push_back(PoolAlloc); // Pool to initialize - EntryNodeInsts.push_back(new CallInst(PoolInit, Args)); - - // Add code to destroy the pool in all of the exit nodes of the function... - Args.clear(); - Args.push_back(PoolAlloc); // Pool to initialize - - for (unsigned EN = 0, ENE = ReturnNodes.size(); EN != ENE; ++EN) { - Instruction *Destroy = new CallInst(PoolDestroy, Args); - - // Insert it before the return instruction... - BasicBlock *RetNode = ReturnNodes[EN]; - RetNode->getInstList().insert(RetNode->end()--, Destroy); - } - } - - // Now that all of the pool descriptors have been created, link them together - // so that called functions can get links as neccesary... - // - for (unsigned i = 0, e = Allocs.size(); i != e; ++i) { - PoolInfo &PI = PoolDescs[Allocs[i]]; - - // For every pointer in the data structure, initialize a link that - // indicates which pool to access... - // - vector Indices(2); - Indices[0] = ConstantUInt::get(Type::UIntTy, 0); - for (unsigned l = 0, le = PI.Node->getNumLinks(); l != le; ++l) - // Only store an entry for the field if the field is used! - if (!PI.Node->getLink(l).empty()) { - assert(PI.Node->getLink(l).size() == 1 && "Should have only one link!"); - PointerVal PV = PI.Node->getLink(l)[0]; - assert(PV.Index == 0 && "Subindexing not supported yet!"); - PoolInfo &LinkedPool = PoolDescs[PV.Node]; - Indices[1] = ConstantUInt::get(Type::UByteTy, 1+l); - - EntryNodeInsts.push_back(new StoreInst(LinkedPool.Handle, PI.Handle, - Indices)); - } - } - - // Insert the entry node code into the entry block... - F->getEntryNode().getInstList().insert(++F->getEntryNode().begin(), - EntryNodeInsts.begin(), - EntryNodeInsts.end()); -} - - -// addPoolPrototypes - Add prototypes for the pool functions to the specified -// module and update the Pool* instance variables to point to them. -// -void PoolAllocate::addPoolPrototypes(Module &M) { - // Get poolinit function... - vector Args; - Args.push_back(Type::UIntTy); // Num bytes per element - FunctionType *PoolInitTy = FunctionType::get(Type::VoidTy, Args, true); - PoolInit = M.getOrInsertFunction("poolinit", PoolInitTy); - - // Get pooldestroy function... - Args.pop_back(); // Only takes a pool... - FunctionType *PoolDestroyTy = FunctionType::get(Type::VoidTy, Args, true); - PoolDestroy = M.getOrInsertFunction("pooldestroy", PoolDestroyTy); - - // Get the poolalloc function... - FunctionType *PoolAllocTy = FunctionType::get(POINTERTYPE, Args, true); - PoolAlloc = M.getOrInsertFunction("poolalloc", PoolAllocTy); - - // Get the poolfree function... - Args.push_back(POINTERTYPE); // Pointer to free - FunctionType *PoolFreeTy = FunctionType::get(Type::VoidTy, Args, true); - PoolFree = M.getOrInsertFunction("poolfree", PoolFreeTy); - - Args[0] = Type::UIntTy; // Number of slots to allocate - FunctionType *PoolAllocArrayTy = FunctionType::get(POINTERTYPE, Args, true); - PoolAllocArray = M.getOrInsertFunction("poolallocarray", PoolAllocArrayTy); -} - - -bool PoolAllocate::run(Module &M) { - addPoolPrototypes(M); - CurModule = &M; - - DS = &getAnalysis(); - bool Changed = false; - - for (Module::iterator I = M.begin(); I != M.end(); ++I) - if (!I->isExternal()) { - Changed |= processFunction(I); - if (Changed) { - cerr << "Only processing one function\n"; - break; - } - } - - CurModule = 0; - DS = 0; - return false; -} - -// createPoolAllocatePass - Global function to access the functionality of this -// pass... -// -Pass *createPoolAllocatePass() { - assert(0 && "Pool allocator disabled!"); - return 0; - //return new PoolAllocate(); -} -#endif diff --git a/lib/Transforms/IPO/PoolAllocate.cpp b/lib/Transforms/IPO/PoolAllocate.cpp deleted file mode 100644 index 337c4adee38..00000000000 --- a/lib/Transforms/IPO/PoolAllocate.cpp +++ /dev/null @@ -1,1204 +0,0 @@ -//===-- PoolAllocate.cpp - Pool Allocation Pass ---------------------------===// -// -// This transform changes programs so that disjoint data structures are -// allocated out of different pools of memory, increasing locality. -// -//===----------------------------------------------------------------------===// - -#define DEBUG_TYPE "PoolAllocation" -#include "llvm/Transforms/PoolAllocate.h" -#include "llvm/Transforms/Utils/Cloning.h" -#include "llvm/Analysis/DataStructure.h" -#include "llvm/Analysis/DSGraph.h" -#include "llvm/Module.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/Target/TargetData.h" -#include "llvm/Support/InstVisitor.h" -#include "Support/Debug.h" -#include "Support/VectorExtras.h" -using namespace PA; - -namespace { - const Type *VoidPtrTy = PointerType::get(Type::SByteTy); - - // The type to allocate for a pool descriptor: { sbyte*, uint, uint } - // void *Data (the data) - // unsigned NodeSize (size of an allocated node) - // unsigned FreeablePool (are slabs in the pool freeable upon calls to - // poolfree?) - const Type *PoolDescType = - StructType::get(make_vector(VoidPtrTy, Type::UIntTy, - Type::UIntTy, 0)); - - const PointerType *PoolDescPtr = PointerType::get(PoolDescType); - - RegisterOpt - X("poolalloc", "Pool allocate disjoint data structures"); -} - -void PoolAllocate::getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); -} - -// Prints out the functions mapped to the leader of the equivalence class they -// belong to. -void PoolAllocate::printFuncECs() { - std::map &leaderMap = FuncECs.getLeaderMap(); - std::cerr << "Indirect Function Map \n"; - for (std::map::iterator LI = leaderMap.begin(), - LE = leaderMap.end(); LI != LE; ++LI) { - std::cerr << LI->first->getName() << ": leader is " - << LI->second->getName() << "\n"; - } -} - -static void printNTOMap(std::map &NTOM) { - std::cerr << "NTOM MAP\n"; - for (std::map::iterator I = NTOM.begin(), - E = NTOM.end(); I != E; ++I) { - if (!isa(I->first) && !isa(I->first)) - std::cerr << *I->first << " to " << *I->second << "\n"; - } -} - -void PoolAllocate::buildIndirectFunctionSets(Module &M) { - // Iterate over the module looking for indirect calls to functions - - // Get top down DSGraph for the functions - TDDS = &getAnalysis(); - - for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) { - - DEBUG(std::cerr << "Processing indirect calls function:" << MI->getName() << "\n"); - - if (MI->isExternal()) - continue; - - DSGraph &TDG = TDDS->getDSGraph(*MI); - - std::vector callSites = TDG.getFunctionCalls(); - - // For each call site in the function - // All the functions that can be called at the call site are put in the - // same equivalence class. - for (std::vector::iterator CSI = callSites.begin(), - CSE = callSites.end(); CSI != CSE ; ++CSI) { - if (CSI->isIndirectCall()) { - DSNode *DSN = CSI->getCalleeNode(); - if (DSN->isIncomplete()) - std::cerr << "Incomplete node " << CSI->getCallInst(); - // assert(DSN->isGlobalNode()); - const std::vector &Callees = DSN->getGlobals(); - if (Callees.size() > 0) { - Function *firstCalledF = dyn_cast(*Callees.begin()); - FuncECs.addElement(firstCalledF); - CallInstTargets.insert(std::pair - (&CSI->getCallInst(), - firstCalledF)); - if (Callees.size() > 1) { - for (std::vector::const_iterator CalleesI = - Callees.begin()+1, CalleesE = Callees.end(); - CalleesI != CalleesE; ++CalleesI) { - Function *calledF = dyn_cast(*CalleesI); - FuncECs.unionSetsWith(firstCalledF, calledF); - CallInstTargets.insert(std::pair - (&CSI->getCallInst(), calledF)); - } - } - } else { - std::cerr << "No targets " << CSI->getCallInst(); - } - } - } - } - - // Print the equivalence classes - DEBUG(printFuncECs()); -} - -bool PoolAllocate::run(Module &M) { - if (M.begin() == M.end()) return false; - CurModule = &M; - - AddPoolPrototypes(); - BU = &getAnalysis(); - - buildIndirectFunctionSets(M); - - std::map FuncMap; - - // Loop over the functions in the original program finding the pool desc. - // arguments necessary for each function that is indirectly callable. - // For each equivalence class, make a list of pool arguments and update - // the PoolArgFirst and PoolArgLast values for each function. - Module::iterator LastOrigFunction = --M.end(); - for (Module::iterator I = M.begin(); ; ++I) { - if (!I->isExternal()) - FindFunctionPoolArgs(*I); - if (I == LastOrigFunction) break; - } - - // Now clone a function using the pool arg list obtained in the previous - // pass over the modules. - // Loop over only the function initially in the program, don't traverse newly - // added ones. If the function uses memory, make its clone. - for (Module::iterator I = M.begin(); ; ++I) { - if (!I->isExternal()) - if (Function *R = MakeFunctionClone(*I)) - FuncMap[I] = R; - if (I == LastOrigFunction) break; - } - - ++LastOrigFunction; - - // Now that all call targets are available, rewrite the function bodies of the - // clones. - for (Module::iterator I = M.begin(); I != LastOrigFunction; ++I) - if (!I->isExternal()) { - std::map::iterator FI = FuncMap.find(I); - ProcessFunctionBody(*I, FI != FuncMap.end() ? *FI->second : *I); - } - - if (CollapseFlag) - std::cerr << "Pool Allocation successful! However all data structures may not be pool allocated\n"; - - return true; -} - - -// AddPoolPrototypes - Add prototypes for the pool functions to the specified -// module and update the Pool* instance variables to point to them. -// -void PoolAllocate::AddPoolPrototypes() { - CurModule->addTypeName("PoolDescriptor", PoolDescType); - - // Get poolinit function... - FunctionType *PoolInitTy = - FunctionType::get(Type::VoidTy, - make_vector(PoolDescPtr, Type::UIntTy, 0), - false); - PoolInit = CurModule->getOrInsertFunction("poolinit", PoolInitTy); - - // Get pooldestroy function... - std::vector PDArgs(1, PoolDescPtr); - FunctionType *PoolDestroyTy = - FunctionType::get(Type::VoidTy, PDArgs, false); - PoolDestroy = CurModule->getOrInsertFunction("pooldestroy", PoolDestroyTy); - - // Get the poolalloc function... - FunctionType *PoolAllocTy = FunctionType::get(VoidPtrTy, PDArgs, false); - PoolAlloc = CurModule->getOrInsertFunction("poolalloc", PoolAllocTy); - - // Get the poolfree function... - PDArgs.push_back(VoidPtrTy); // Pointer to free - FunctionType *PoolFreeTy = FunctionType::get(Type::VoidTy, PDArgs, false); - PoolFree = CurModule->getOrInsertFunction("poolfree", PoolFreeTy); - - // The poolallocarray function - FunctionType *PoolAllocArrayTy = - FunctionType::get(VoidPtrTy, - make_vector(PoolDescPtr, Type::UIntTy, 0), - false); - PoolAllocArray = CurModule->getOrInsertFunction("poolallocarray", - PoolAllocArrayTy); - -} - -// Inline the DSGraphs of functions corresponding to the potential targets at -// indirect call sites into the DS Graph of the callee. -// This is required to know what pools to create/pass at the call site in the -// caller -// -void PoolAllocate::InlineIndirectCalls(Function &F, DSGraph &G, - hash_set &visited) { - std::vector callSites = G.getFunctionCalls(); - - visited.insert(&F); - - // For each indirect call site in the function, inline all the potential - // targets - for (std::vector::iterator CSI = callSites.begin(), - CSE = callSites.end(); CSI != CSE; ++CSI) { - if (CSI->isIndirectCall()) { - CallInst &CI = CSI->getCallInst(); - std::pair::iterator, - std::multimap::iterator> Targets = - CallInstTargets.equal_range(&CI); - for (std::multimap::iterator TFI = Targets.first, - TFE = Targets.second; TFI != TFE; ++TFI) { - DSGraph &TargetG = BU->getDSGraph(*TFI->second); - // Call the function recursively if the callee is not yet inlined - // and if it hasn't been visited in this sequence of calls - // The latter is dependent on the fact that the graphs of all functions - // in an SCC are actually the same - if (InlinedFuncs.find(TFI->second) == InlinedFuncs.end() && - visited.find(TFI->second) == visited.end()) { - InlineIndirectCalls(*TFI->second, TargetG, visited); - } - G.mergeInGraph(*CSI, *TFI->second, TargetG, DSGraph::KeepModRefBits | - DSGraph::KeepAllocaBit | DSGraph::DontCloneCallNodes | - DSGraph::DontCloneAuxCallNodes); - } - } - } - - // Mark this function as one whose graph is inlined with its indirect - // function targets' DS Graphs. This ensures that every function is inlined - // exactly once - InlinedFuncs.insert(&F); -} - -void PoolAllocate::FindFunctionPoolArgs(Function &F) { - - DSGraph &G = BU->getDSGraph(F); - - // Inline the potential targets of indirect calls - hash_set visitedFuncs; - InlineIndirectCalls(F, G, visitedFuncs); - - // The DSGraph is merged with the globals graph. - G.mergeInGlobalsGraph(); - - // The nodes reachable from globals need to be recognized as potential - // arguments. This is required because, upon merging in the globals graph, - // the nodes pointed to by globals that are not live are not marked - // incomplete. - hash_set NodesFromGlobals; - for (DSGraph::ScalarMapTy::iterator I = G.getScalarMap().begin(), - E = G.getScalarMap().end(); I != E; ++I) - if (isa(I->first)) { // Found a global - DSNodeHandle &GH = I->second; - GH.getNode()->markReachableNodes(NodesFromGlobals); - } - - // At this point the DS Graphs have been modified in place including - // information about globals as well as indirect calls, making it useful - // for pool allocation - std::vector &Nodes = G.getNodes(); - if (Nodes.empty()) return ; // No memory activity, nothing is required - - FuncInfo &FI = FunctionInfo[&F]; // Create a new entry for F - - FI.Clone = 0; - - // Initialize the PoolArgFirst and PoolArgLast for the function depending - // on whether there have been other functions in the equivalence class - // that have pool arguments so far in the analysis. - if (!FuncECs.findClass(&F)) { - FI.PoolArgFirst = FI.PoolArgLast = 0; - } else { - if (EqClass2LastPoolArg.find(FuncECs.findClass(&F)) != - EqClass2LastPoolArg.end()) - FI.PoolArgFirst = FI.PoolArgLast = - EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1; - else - FI.PoolArgFirst = FI.PoolArgLast = 0; - } - - // Find DataStructure nodes which are allocated in pools non-local to the - // current function. This set will contain all of the DSNodes which require - // pools to be passed in from outside of the function. - hash_set &MarkedNodes = FI.MarkedNodes; - - // Mark globals and incomplete nodes as live... (this handles arguments) - if (F.getName() != "main") - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) { - if (Nodes[i]->isGlobalNode() && !Nodes[i]->isIncomplete()) - DEBUG(std::cerr << "Global node is not Incomplete\n"); - if ((Nodes[i]->isIncomplete() || Nodes[i]->isGlobalNode() || - NodesFromGlobals.count(Nodes[i])) && Nodes[i]->isHeapNode()) - Nodes[i]->markReachableNodes(MarkedNodes); - } - - // Marked the returned node as alive... - if (DSNode *RetNode = G.getReturnNodeFor(F).getNode()) - if (RetNode->isHeapNode()) - RetNode->markReachableNodes(MarkedNodes); - - if (MarkedNodes.empty()) // We don't need to clone the function if there - return; // are no incoming arguments to be added. - - // Erase any marked node that is not a heap node - - for (hash_set::iterator I = MarkedNodes.begin(), - E = MarkedNodes.end(); I != E; ) { - // erase invalidates hash_set iterators if the iterator points to the - // element being erased - if (!(*I)->isHeapNode()) - MarkedNodes.erase(I++); - else - ++I; - } - - FI.PoolArgLast += MarkedNodes.size(); - - - if (FuncECs.findClass(&F)) { - // Update the equivalence class last pool argument information - // only if there actually were pool arguments to the function. - // Also, there is no entry for the Eq. class in EqClass2LastPoolArg - // if there are no functions in the equivalence class with pool arguments. - if (FI.PoolArgLast != FI.PoolArgFirst) - EqClass2LastPoolArg[FuncECs.findClass(&F)] = FI.PoolArgLast - 1; - } - -} - -// MakeFunctionClone - If the specified function needs to be modified for pool -// allocation support, make a clone of it, adding additional arguments as -// neccesary, and return it. If not, just return null. -// -Function *PoolAllocate::MakeFunctionClone(Function &F) { - - DSGraph &G = BU->getDSGraph(F); - - std::vector &Nodes = G.getNodes(); - if (Nodes.empty()) - return 0; - - FuncInfo &FI = FunctionInfo[&F]; - - hash_set &MarkedNodes = FI.MarkedNodes; - - if (!FuncECs.findClass(&F)) { - // Not in any equivalence class - if (MarkedNodes.empty()) - return 0; - } else { - // No need to clone if there are no pool arguments in any function in the - // equivalence class - if (!EqClass2LastPoolArg.count(FuncECs.findClass(&F))) - return 0; - } - - // Figure out what the arguments are to be for the new version of the function - const FunctionType *OldFuncTy = F.getFunctionType(); - std::vector ArgTys; - if (!FuncECs.findClass(&F)) { - ArgTys.reserve(OldFuncTy->getParamTypes().size() + MarkedNodes.size()); - FI.ArgNodes.reserve(MarkedNodes.size()); - for (hash_set::iterator I = MarkedNodes.begin(), - E = MarkedNodes.end(); I != E; ++I) { - ArgTys.push_back(PoolDescPtr); // Add the appropriate # of pool descs - FI.ArgNodes.push_back(*I); - } - if (FI.ArgNodes.empty()) return 0; // No nodes to be pool allocated! - - } - else { - // This function is a member of an equivalence class and needs to be cloned - ArgTys.reserve(OldFuncTy->getParamTypes().size() + - EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1); - FI.ArgNodes.reserve(EqClass2LastPoolArg[FuncECs.findClass(&F)] + 1); - - for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i) { - ArgTys.push_back(PoolDescPtr); // Add the appropriate # of pool - // descs - } - - for (hash_set::iterator I = MarkedNodes.begin(), - E = MarkedNodes.end(); I != E; ++I) { - FI.ArgNodes.push_back(*I); - } - - assert ((FI.ArgNodes.size() == (unsigned) (FI.PoolArgLast - - FI.PoolArgFirst)) && - "Number of ArgNodes equal to the number of pool arguments used by this function"); - - if (FI.ArgNodes.empty()) return 0; - } - - - ArgTys.insert(ArgTys.end(), OldFuncTy->getParamTypes().begin(), - OldFuncTy->getParamTypes().end()); - - - // Create the new function prototype - FunctionType *FuncTy = FunctionType::get(OldFuncTy->getReturnType(), ArgTys, - OldFuncTy->isVarArg()); - // Create the new function... - Function *New = new Function(FuncTy, GlobalValue::InternalLinkage, - F.getName(), F.getParent()); - - // Set the rest of the new arguments names to be PDa and add entries to the - // pool descriptors map - std::map &PoolDescriptors = FI.PoolDescriptors; - Function::aiterator NI = New->abegin(); - - if (FuncECs.findClass(&F)) { - // If the function belongs to an equivalence class - for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i, - ++NI) - NI->setName("PDa"); - - NI = New->abegin(); - if (FI.PoolArgFirst > 0) - for (int i = 0; i < FI.PoolArgFirst; ++NI, ++i) - ; - - for (unsigned i = 0, e = FI.ArgNodes.size(); i != e; ++i, ++NI) - PoolDescriptors.insert(std::make_pair(FI.ArgNodes[i], NI)); - - NI = New->abegin(); - if (EqClass2LastPoolArg.count(FuncECs.findClass(&F))) - for (int i = 0; i <= EqClass2LastPoolArg[FuncECs.findClass(&F)]; ++i, ++NI) - ; - } else { - // If the function does not belong to an equivalence class - if (FI.ArgNodes.size()) - for (unsigned i = 0, e = FI.ArgNodes.size(); i != e; ++i, ++NI) { - NI->setName("PDa"); // Add pd entry - PoolDescriptors.insert(std::make_pair(FI.ArgNodes[i], NI)); - } - NI = New->abegin(); - if (FI.ArgNodes.size()) - for (unsigned i = 0; i < FI.ArgNodes.size(); ++NI, ++i) - ; - } - - // Map the existing arguments of the old function to the corresponding - // arguments of the new function. - std::map ValueMap; - if (NI != New->aend()) - for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I, ++NI) { - ValueMap[I] = NI; - NI->setName(I->getName()); - } - - // Populate the value map with all of the globals in the program. - // FIXME: This should be unneccesary! - Module &M = *F.getParent(); - for (Module::iterator I = M.begin(), E=M.end(); I!=E; ++I) ValueMap[I] = I; - for (Module::giterator I = M.gbegin(), E=M.gend(); I!=E; ++I) ValueMap[I] = I; - - // Perform the cloning. - std::vector Returns; - CloneFunctionInto(New, &F, ValueMap, Returns); - - // Invert the ValueMap into the NewToOldValueMap - std::map &NewToOldValueMap = FI.NewToOldValueMap; - for (std::map::iterator I = ValueMap.begin(), - E = ValueMap.end(); I != E; ++I) - NewToOldValueMap.insert(std::make_pair(I->second, I->first)); - - return FI.Clone = New; -} - - -// processFunction - Pool allocate any data structures which are contained in -// the specified function... -// -void PoolAllocate::ProcessFunctionBody(Function &F, Function &NewF) { - DSGraph &G = BU->getDSGraph(F); - - std::vector &Nodes = G.getNodes(); - if (Nodes.empty()) return; // Quick exit if nothing to do... - - FuncInfo &FI = FunctionInfo[&F]; // Get FuncInfo for F - hash_set &MarkedNodes = FI.MarkedNodes; - - DEBUG(std::cerr << "[" << F.getName() << "] Pool Allocate: "); - - // Loop over all of the nodes which are non-escaping, adding pool-allocatable - // ones to the NodesToPA vector. - std::vector NodesToPA; - for (unsigned i = 0, e = Nodes.size(); i != e; ++i) - if (Nodes[i]->isHeapNode() && // Pick nodes with heap elems - !MarkedNodes.count(Nodes[i])) // Can't be marked - NodesToPA.push_back(Nodes[i]); - - DEBUG(std::cerr << NodesToPA.size() << " nodes to pool allocate\n"); - if (!NodesToPA.empty()) { - // Create pool construction/destruction code - std::map &PoolDescriptors = FI.PoolDescriptors; - CreatePools(NewF, NodesToPA, PoolDescriptors); - } - - // Transform the body of the function now... - TransformFunctionBody(NewF, F, G, FI); -} - - -// CreatePools - This creates the pool initialization and destruction code for -// the DSNodes specified by the NodesToPA list. This adds an entry to the -// PoolDescriptors map for each DSNode. -// -void PoolAllocate::CreatePools(Function &F, - const std::vector &NodesToPA, - std::map &PoolDescriptors) { - // Find all of the return nodes in the CFG... - std::vector ReturnNodes; - for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) - if (isa(I->getTerminator())) - ReturnNodes.push_back(I); - - TargetData &TD = getAnalysis(); - - // Loop over all of the pools, inserting code into the entry block of the - // function for the initialization and code in the exit blocks for - // destruction. - // - Instruction *InsertPoint = F.front().begin(); - for (unsigned i = 0, e = NodesToPA.size(); i != e; ++i) { - DSNode *Node = NodesToPA[i]; - - // Create a new alloca instruction for the pool... - Value *AI = new AllocaInst(PoolDescType, 0, "PD", InsertPoint); - - Value *ElSize; - - // Void types in DS graph are never used - if (Node->getType() != Type::VoidTy) - ElSize = ConstantUInt::get(Type::UIntTy, TD.getTypeSize(Node->getType())); - else { - DEBUG(std::cerr << "Potential node collapsing in " << F.getName() - << ". All Data Structures may not be pool allocated\n"); - ElSize = ConstantUInt::get(Type::UIntTy, 0); - } - - // Insert the call to initialize the pool... - new CallInst(PoolInit, make_vector(AI, ElSize, 0), "", InsertPoint); - - // Update the PoolDescriptors map - PoolDescriptors.insert(std::make_pair(Node, AI)); - - // Insert a call to pool destroy before each return inst in the function - for (unsigned r = 0, e = ReturnNodes.size(); r != e; ++r) - new CallInst(PoolDestroy, make_vector(AI, 0), "", - ReturnNodes[r]->getTerminator()); - } -} - - -namespace { - /// FuncTransform - This class implements transformation required of pool - /// allocated functions. - struct FuncTransform : public InstVisitor { - PoolAllocate &PAInfo; - DSGraph &G; // The Bottom-up DS Graph - DSGraph &TDG; // The Top-down DS Graph - FuncInfo &FI; - - FuncTransform(PoolAllocate &P, DSGraph &g, DSGraph &tdg, FuncInfo &fi) - : PAInfo(P), G(g), TDG(tdg), FI(fi) { - } - - void visitMallocInst(MallocInst &MI); - void visitFreeInst(FreeInst &FI); - void visitCallInst(CallInst &CI); - - // The following instructions are never modified by pool allocation - void visitBranchInst(BranchInst &I) { } - void visitBinaryOperator(Instruction &I) { } - void visitShiftInst (ShiftInst &I) { } - void visitSwitchInst (SwitchInst &I) { } - void visitCastInst (CastInst &I) { } - void visitAllocaInst(AllocaInst &I) { } - void visitLoadInst(LoadInst &I) { } - void visitGetElementPtrInst (GetElementPtrInst &I) { } - - void visitReturnInst(ReturnInst &I); - void visitStoreInst (StoreInst &I); - void visitPHINode(PHINode &I); - - void visitInstruction(Instruction &I) { - std::cerr << "PoolAllocate does not recognize this instruction\n"; - abort(); - } - - private: - DSNodeHandle& getDSNodeHFor(Value *V) { - // if (isa(V)) - // return DSNodeHandle(); - - if (!FI.NewToOldValueMap.empty()) { - // If the NewToOldValueMap is in effect, use it. - std::map::iterator I = FI.NewToOldValueMap.find(V); - if (I != FI.NewToOldValueMap.end()) - V = (Value*)I->second; - } - - return G.getScalarMap()[V]; - } - - DSNodeHandle& getTDDSNodeHFor(Value *V) { - if (!FI.NewToOldValueMap.empty()) { - // If the NewToOldValueMap is in effect, use it. - std::map::iterator I = FI.NewToOldValueMap.find(V); - if (I != FI.NewToOldValueMap.end()) - V = (Value*)I->second; - } - - return TDG.getScalarMap()[V]; - } - - Value *getPoolHandle(Value *V) { - DSNode *Node = getDSNodeHFor(V).getNode(); - // Get the pool handle for this DSNode... - std::map::iterator I = FI.PoolDescriptors.find(Node); - - if (I != FI.PoolDescriptors.end()) { - // Check that the node pointed to by V in the TD DS graph is not - // collapsed - DSNode *TDNode = getTDDSNodeHFor(V).getNode(); - if (TDNode->getType() != Type::VoidTy) - return I->second; - else { - PAInfo.CollapseFlag = 1; - return 0; - } - } - else - return 0; - - } - - bool isFuncPtr(Value *V); - - Function* getFuncClass(Value *V); - - Value* retCloneIfFunc(Value *V); - }; -} - -void PoolAllocate::TransformFunctionBody(Function &F, Function &OldF, - DSGraph &G, FuncInfo &FI) { - FuncTransform(*this, G, TDDS->getDSGraph(OldF), FI).visit(F); -} - -// Returns true if V is a function pointer -bool FuncTransform::isFuncPtr(Value *V) { - if (const PointerType *PTy = dyn_cast(V->getType())) - return isa(PTy->getElementType()); - return false; -} - -// Given a function pointer, return the function eq. class if one exists -Function* FuncTransform::getFuncClass(Value *V) { - // Look at DSGraph and see if the set of of functions it could point to - // are pool allocated. - - if (!isFuncPtr(V)) - return 0; - - // Two cases: - // if V is a constant - if (Function *theFunc = dyn_cast(V)) { - if (!PAInfo.FuncECs.findClass(theFunc)) - // If this function does not belong to any equivalence class - return 0; - if (PAInfo.EqClass2LastPoolArg.count(PAInfo.FuncECs.findClass(theFunc))) - return PAInfo.FuncECs.findClass(theFunc); - else - return 0; - } - - // if V is not a constant - DSNode *DSN = TDG.getNodeForValue(V).getNode(); - if (!DSN) { - return 0; - } - const std::vector &Callees = DSN->getGlobals(); - if (Callees.size() > 0) { - Function *calledF = dyn_cast(*Callees.begin()); - assert(PAInfo.FuncECs.findClass(calledF) && "should exist in some eq. class"); - if (PAInfo.EqClass2LastPoolArg.count(PAInfo.FuncECs.findClass(calledF))) - return PAInfo.FuncECs.findClass(calledF); - } - - return 0; -} - -// Returns the clone if V is a static function (not a pointer) and belongs -// to an equivalence class i.e. is pool allocated -Value* FuncTransform::retCloneIfFunc(Value *V) { - if (Function *fixedFunc = dyn_cast(V)) - if (getFuncClass(V)) - return PAInfo.getFuncInfo(*fixedFunc)->Clone; - - return 0; -} - -void FuncTransform::visitReturnInst (ReturnInst &RI) { - if (RI.getNumOperands()) - if (Value *clonedFunc = retCloneIfFunc(RI.getOperand(0))) { - // Cast the clone of RI.getOperand(0) to the non-pool-allocated type - CastInst *CastI = new CastInst(clonedFunc, RI.getOperand(0)->getType(), - "tmp", &RI); - // Insert return instruction that returns the casted value - ReturnInst *RetI = new ReturnInst(CastI, &RI); - - // Remove original return instruction - RI.getParent()->getInstList().erase(&RI); - - if (!FI.NewToOldValueMap.empty()) { - std::map::iterator II = - FI.NewToOldValueMap.find(&RI); - assert(II != FI.NewToOldValueMap.end() && - "RI not found in clone?"); - FI.NewToOldValueMap.insert(std::make_pair(RetI, II->second)); - FI.NewToOldValueMap.erase(II); - } - } -} - -void FuncTransform::visitStoreInst (StoreInst &SI) { - // Check if a constant function is being stored - if (Value *clonedFunc = retCloneIfFunc(SI.getOperand(0))) { - CastInst *CastI = new CastInst(clonedFunc, SI.getOperand(0)->getType(), - "tmp", &SI); - StoreInst *StoreI = new StoreInst(CastI, SI.getOperand(1), &SI); - SI.getParent()->getInstList().erase(&SI); - - // Update the NewToOldValueMap if this is a clone - if (!FI.NewToOldValueMap.empty()) { - std::map::iterator II = - FI.NewToOldValueMap.find(&SI); - assert(II != FI.NewToOldValueMap.end() && - "SI not found in clone?"); - FI.NewToOldValueMap.insert(std::make_pair(StoreI, II->second)); - FI.NewToOldValueMap.erase(II); - } - } -} - -void FuncTransform::visitPHINode(PHINode &PI) { - // If any of the operands of the PHI node is a constant function pointer - // that is cloned, the cast instruction has to be inserted at the end of the - // previous basic block - - if (isFuncPtr(&PI)) { - PHINode *V = new PHINode(PI.getType(), PI.getName(), &PI); - for (unsigned i = 0 ; i < PI.getNumIncomingValues(); ++i) { - if (Value *clonedFunc = retCloneIfFunc(PI.getIncomingValue(i))) { - // Insert CastInst at the end of PI.getIncomingBlock(i) - BasicBlock::iterator BBI = --PI.getIncomingBlock(i)->end(); - // BBI now points to the terminator instruction of the basic block. - CastInst *CastI = new CastInst(clonedFunc, PI.getType(), "tmp", BBI); - V->addIncoming(CastI, PI.getIncomingBlock(i)); - } else { - V->addIncoming(PI.getIncomingValue(i), PI.getIncomingBlock(i)); - } - - } - PI.replaceAllUsesWith(V); - PI.getParent()->getInstList().erase(&PI); - - DSGraph::ScalarMapTy &SM = G.getScalarMap(); - DSGraph::ScalarMapTy::iterator PII = SM.find(&PI); - - // Update Scalar map of DSGraph if this is one of the original functions - // Otherwise update the NewToOldValueMap - if (PII != SM.end()) { - SM.insert(std::make_pair(V, PII->second)); - SM.erase(PII); // Destroy the PHINode - } else { - std::map::iterator II = - FI.NewToOldValueMap.find(&PI); - assert(II != FI.NewToOldValueMap.end() && - "PhiI not found in clone?"); - FI.NewToOldValueMap.insert(std::make_pair(V, II->second)); - FI.NewToOldValueMap.erase(II); - } - } -} - -void FuncTransform::visitMallocInst(MallocInst &MI) { - // Get the pool handle for the node that this contributes to... - Value *PH = getPoolHandle(&MI); - - // NB: PH is zero even if the node is collapsed - if (PH == 0) return; - - // Insert a call to poolalloc - Value *V; - if (MI.isArrayAllocation()) - V = new CallInst(PAInfo.PoolAllocArray, - make_vector(PH, MI.getOperand(0), 0), - MI.getName(), &MI); - else - V = new CallInst(PAInfo.PoolAlloc, make_vector(PH, 0), - MI.getName(), &MI); - - MI.setName(""); // Nuke MIs name - - Value *Casted = V; - - // Cast to the appropriate type if necessary - if (V->getType() != MI.getType()) { - Casted = new CastInst(V, MI.getType(), V->getName(), &MI); - } - - // Update def-use info - MI.replaceAllUsesWith(Casted); - - // Remove old malloc instruction - MI.getParent()->getInstList().erase(&MI); - - DSGraph::ScalarMapTy &SM = G.getScalarMap(); - DSGraph::ScalarMapTy::iterator MII = SM.find(&MI); - - // If we are modifying the original function, update the DSGraph... - if (MII != SM.end()) { - // V and Casted now point to whatever the original malloc did... - SM.insert(std::make_pair(V, MII->second)); - if (V != Casted) - SM.insert(std::make_pair(Casted, MII->second)); - SM.erase(MII); // The malloc is now destroyed - } else { // Otherwise, update the NewToOldValueMap - std::map::iterator MII = - FI.NewToOldValueMap.find(&MI); - assert(MII != FI.NewToOldValueMap.end() && "MI not found in clone?"); - FI.NewToOldValueMap.insert(std::make_pair(V, MII->second)); - if (V != Casted) - FI.NewToOldValueMap.insert(std::make_pair(Casted, MII->second)); - FI.NewToOldValueMap.erase(MII); - } -} - -void FuncTransform::visitFreeInst(FreeInst &FrI) { - Value *Arg = FrI.getOperand(0); - Value *PH = getPoolHandle(Arg); // Get the pool handle for this DSNode... - if (PH == 0) return; - // Insert a cast and a call to poolfree... - Value *Casted = Arg; - if (Arg->getType() != PointerType::get(Type::SByteTy)) - Casted = new CastInst(Arg, PointerType::get(Type::SByteTy), - Arg->getName()+".casted", &FrI); - - CallInst *FreeI = new CallInst(PAInfo.PoolFree, make_vector(PH, Casted, 0), - "", &FrI); - // Delete the now obsolete free instruction... - FrI.getParent()->getInstList().erase(&FrI); - - // Update the NewToOldValueMap if this is a clone - if (!FI.NewToOldValueMap.empty()) { - std::map::iterator II = - FI.NewToOldValueMap.find(&FrI); - assert(II != FI.NewToOldValueMap.end() && - "FrI not found in clone?"); - FI.NewToOldValueMap.insert(std::make_pair(FreeI, II->second)); - FI.NewToOldValueMap.erase(II); - } -} - -static void CalcNodeMapping(DSNodeHandle& Caller, DSNodeHandle& Callee, - std::map &NodeMapping) { - DSNode *CalleeNode = Callee.getNode(); - DSNode *CallerNode = Caller.getNode(); - - unsigned CalleeOffset = Callee.getOffset(); - unsigned CallerOffset = Caller.getOffset(); - - if (CalleeNode == 0) return; - - // If callee has a node and caller doesn't, then a constant argument was - // passed by the caller - if (CallerNode == 0) { - NodeMapping.insert(NodeMapping.end(), std::make_pair(CalleeNode, - (DSNode *) 0)); - } - - // Map the callee node to the caller node. - // NB: The callee node could be of a different type. Eg. if it points to the - // field of a struct that the caller points to - std::map::iterator I = NodeMapping.find(CalleeNode); - if (I != NodeMapping.end()) { // Node already in map... - assert(I->second == CallerNode && - "Node maps to different nodes on paths?"); - } else { - NodeMapping.insert(I, std::make_pair(CalleeNode, CallerNode)); - - if (CalleeNode->getType() != CallerNode->getType() && CallerOffset == 0) - DEBUG(std::cerr << "NB: Mapping of nodes between different types\n"); - - // Recursively map the callee links to the caller links starting from the - // offset in the node into which they are mapped. - // Being a BU Graph, the callee ought to have smaller number of links unless - // there is collapsing in the caller - unsigned numCallerLinks = CallerNode->getNumLinks() - CallerOffset; - unsigned numCalleeLinks = CalleeNode->getNumLinks() - CalleeOffset; - - if (numCallerLinks > 0) { - if (numCallerLinks < numCalleeLinks) { - DEBUG(std::cerr << "Potential node collapsing in caller\n"); - for (unsigned i = 0, e = numCalleeLinks; i != e; ++i) - CalcNodeMapping(CallerNode->getLink(((i%numCallerLinks) << DS::PointerShift) + CallerOffset), CalleeNode->getLink((i << DS::PointerShift) + CalleeOffset), NodeMapping); - } else { - for (unsigned i = 0, e = numCalleeLinks; i != e; ++i) - CalcNodeMapping(CallerNode->getLink((i << DS::PointerShift) + CallerOffset), CalleeNode->getLink((i << DS::PointerShift) + CalleeOffset), NodeMapping); - } - } else if (numCalleeLinks > 0) { - DEBUG(std::cerr << - "Caller has unexpanded node, due to indirect call perhaps!\n"); - } - } -} - -void FuncTransform::visitCallInst(CallInst &CI) { - Function *CF = CI.getCalledFunction(); - - // optimization for function pointers that are basically gotten from a cast - // with only one use and constant expressions with casts in them - if (!CF) { - if (CastInst* CastI = dyn_cast(CI.getCalledValue())) { - if (isa(CastI->getOperand(0)) && - CastI->getOperand(0)->getType() == CastI->getType()) - CF = dyn_cast(CastI->getOperand(0)); - } else if (ConstantExpr *CE = dyn_cast(CI.getOperand(0))) { - if (CE->getOpcode() == Instruction::Cast) { - if (isa(CE->getOperand(0))) - return; - else - assert(0 && "Function pointer cast not handled as called function\n"); - } - } - - } - - DSGraph &CallerG = G; - - std::vector Args; - if (!CF) { // Indirect call - DEBUG(std::cerr << " Handling call: " << CI); - - std::map PoolArgs; - Function *FuncClass; - - std::pair::iterator, - std::multimap::iterator> Targets = - PAInfo.CallInstTargets.equal_range(&CI); - for (std::multimap::iterator TFI = Targets.first, - TFE = Targets.second; TFI != TFE; ++TFI) { - if (TFI == Targets.first) { - FuncClass = PAInfo.FuncECs.findClass(TFI->second); - // Nothing to transform if there are no pool arguments in this - // equivalence class of functions. - if (!PAInfo.EqClass2LastPoolArg.count(FuncClass)) - return; - } - - FuncInfo *CFI = PAInfo.getFuncInfo(*TFI->second); - - if (!CFI->ArgNodes.size()) continue; // Nothing to transform... - - DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*TFI->second); - std::map NodeMapping; - - Function::aiterator AI = TFI->second->abegin(), AE = TFI->second->aend(); - unsigned OpNum = 1; - for ( ; AI != AE; ++AI, ++OpNum) { - if (!isa(CI.getOperand(OpNum))) - CalcNodeMapping(getDSNodeHFor(CI.getOperand(OpNum)), - CG.getScalarMap()[AI], NodeMapping); - } - assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!"); - - if (CI.getType() != Type::VoidTy) - CalcNodeMapping(getDSNodeHFor(&CI), - CG.getReturnNodeFor(*TFI->second), NodeMapping); - - // Map the nodes that are pointed to by globals. - // For all globals map getDSNodeForGlobal(g)->CG.getDSNodeForGlobal(g) - for (DSGraph::ScalarMapTy::iterator SMI = G.getScalarMap().begin(), - SME = G.getScalarMap().end(); SMI != SME; ++SMI) - if (isa(SMI->first)) { - CalcNodeMapping(SMI->second, - CG.getScalarMap()[SMI->first], NodeMapping); - } - - unsigned idx = CFI->PoolArgFirst; - - // The following loop determines the pool pointers corresponding to - // CFI. - for (unsigned i = 0, e = CFI->ArgNodes.size(); i != e; ++i, ++idx) { - if (NodeMapping.count(CFI->ArgNodes[i])) { - assert(NodeMapping.count(CFI->ArgNodes[i]) && "Node not in mapping!"); - DSNode *LocalNode = NodeMapping.find(CFI->ArgNodes[i])->second; - if (LocalNode) { - assert(FI.PoolDescriptors.count(LocalNode) && - "Node not pool allocated?"); - PoolArgs[idx] = FI.PoolDescriptors.find(LocalNode)->second; - } - else - // LocalNode is null when a constant is passed in as a parameter - PoolArgs[idx] = Constant::getNullValue(PoolDescPtr); - } else { - PoolArgs[idx] = Constant::getNullValue(PoolDescPtr); - } - } - } - - // Push the pool arguments into Args. - if (PAInfo.EqClass2LastPoolArg.count(FuncClass)) { - for (int i = 0; i <= PAInfo.EqClass2LastPoolArg[FuncClass]; ++i) { - if (PoolArgs.find(i) != PoolArgs.end()) - Args.push_back(PoolArgs[i]); - else - Args.push_back(Constant::getNullValue(PoolDescPtr)); - } - - assert(Args.size()== (unsigned) PAInfo.EqClass2LastPoolArg[FuncClass] + 1 - && "Call has same number of pool args as the called function"); - } - - // Add the rest of the arguments (the original arguments of the function)... - Args.insert(Args.end(), CI.op_begin()+1, CI.op_end()); - - std::string Name = CI.getName(); - - Value *NewCall; - if (Args.size() > CI.getNumOperands() - 1) { - // If there are any pool arguments - CastInst *CastI = - new CastInst(CI.getOperand(0), - PAInfo.getFuncInfo(*FuncClass)->Clone->getType(), "tmp", - &CI); - NewCall = new CallInst(CastI, Args, Name, &CI); - } else { - NewCall = new CallInst(CI.getOperand(0), Args, Name, &CI); - } - - CI.replaceAllUsesWith(NewCall); - DEBUG(std::cerr << " Result Call: " << *NewCall); - - if (CI.getType() != Type::VoidTy) { - // If we are modifying the original function, update the DSGraph... - DSGraph::ScalarMapTy &SM = G.getScalarMap(); - DSGraph::ScalarMapTy::iterator CII = SM.find(&CI); - if (CII != SM.end()) { - SM.insert(std::make_pair(NewCall, CII->second)); - SM.erase(CII); // Destroy the CallInst - } else { - // Otherwise update the NewToOldValueMap with the new CI return value - std::map::iterator CII = - FI.NewToOldValueMap.find(&CI); - assert(CII != FI.NewToOldValueMap.end() && "CI not found in clone?"); - FI.NewToOldValueMap.insert(std::make_pair(NewCall, CII->second)); - FI.NewToOldValueMap.erase(CII); - } - } else if (!FI.NewToOldValueMap.empty()) { - std::map::iterator II = - FI.NewToOldValueMap.find(&CI); - assert(II != FI.NewToOldValueMap.end() && - "CI not found in clone?"); - FI.NewToOldValueMap.insert(std::make_pair(NewCall, II->second)); - FI.NewToOldValueMap.erase(II); - } - } - else { - - FuncInfo *CFI = PAInfo.getFuncInfo(*CF); - - if (CFI == 0 || CFI->Clone == 0) return; // Nothing to transform... - - DEBUG(std::cerr << " Handling call: " << CI); - - DSGraph &CG = PAInfo.getBUDataStructures().getDSGraph(*CF); // Callee graph - - // We need to figure out which local pool descriptors correspond to the pool - // descriptor arguments passed into the function call. Calculate a mapping - // from callee DSNodes to caller DSNodes. We construct a partial isomophism - // between the graphs to figure out which pool descriptors need to be passed - // in. The roots of this mapping is found from arguments and return values. - // - std::map NodeMapping; - - Function::aiterator AI = CF->abegin(), AE = CF->aend(); - unsigned OpNum = 1; - for (; AI != AE; ++AI, ++OpNum) { - Value *callOp = CI.getOperand(OpNum); - if (!isa(callOp)) - CalcNodeMapping(getDSNodeHFor(callOp), CG.getScalarMap()[AI], - NodeMapping); - } - assert(OpNum == CI.getNumOperands() && "Varargs calls not handled yet!"); - - // Map the return value as well... - if (CI.getType() != Type::VoidTy) - CalcNodeMapping(getDSNodeHFor(&CI), CG.getReturnNodeFor(*CF), - NodeMapping); - - // Map the nodes that are pointed to by globals. - // For all globals map getDSNodeForGlobal(g)->CG.getDSNodeForGlobal(g) - for (DSGraph::ScalarMapTy::iterator SMI = G.getScalarMap().begin(), - SME = G.getScalarMap().end(); SMI != SME; ++SMI) - if (isa(SMI->first)) { - CalcNodeMapping(SMI->second, - CG.getScalarMap()[SMI->first], NodeMapping); - } - - // Okay, now that we have established our mapping, we can figure out which - // pool descriptors to pass in... - - // Add an argument for each pool which must be passed in... - if (CFI->PoolArgFirst != 0) { - for (int i = 0; i < CFI->PoolArgFirst; ++i) - Args.push_back(Constant::getNullValue(PoolDescPtr)); - } - - for (unsigned i = 0, e = CFI->ArgNodes.size(); i != e; ++i) { - if (NodeMapping.count(CFI->ArgNodes[i])) { - - DSNode *LocalNode = NodeMapping.find(CFI->ArgNodes[i])->second; - if (LocalNode) { - assert(FI.PoolDescriptors.count(LocalNode) && - "Node not pool allocated?"); - Args.push_back(FI.PoolDescriptors.find(LocalNode)->second); - } else - Args.push_back(Constant::getNullValue(PoolDescPtr)); - } else { - Args.push_back(Constant::getNullValue(PoolDescPtr)); - } - } - - Function *FuncClass = PAInfo.FuncECs.findClass(CF); - - if (PAInfo.EqClass2LastPoolArg.count(FuncClass)) - for (int i = CFI->PoolArgLast; - i <= PAInfo.EqClass2LastPoolArg[FuncClass]; ++i) - Args.push_back(Constant::getNullValue(PoolDescPtr)); - - // Add the rest of the arguments... - Args.insert(Args.end(), CI.op_begin()+1, CI.op_end()); - - std::string Name = CI.getName(); - - std::map::iterator CNewII; - - Value *NewCall = new CallInst(CFI->Clone, Args, Name, &CI); - - CI.replaceAllUsesWith(NewCall); - DEBUG(std::cerr << " Result Call: " << *NewCall); - - if (CI.getType() != Type::VoidTy) { - // If we are modifying the original function, update the DSGraph... - DSGraph::ScalarMapTy &SM = G.getScalarMap(); - DSGraph::ScalarMapTy::iterator CII = SM.find(&CI); - if (CII != SM.end()) { - SM.insert(std::make_pair(NewCall, CII->second)); - SM.erase(CII); // Destroy the CallInst - } else { - // Otherwise update the NewToOldValueMap with the new CI return value - std::map::iterator CNII = - FI.NewToOldValueMap.find(&CI); - assert(CNII != FI.NewToOldValueMap.end() && CNII->second && - "CI not found in clone?"); - FI.NewToOldValueMap.insert(std::make_pair(NewCall, CNII->second)); - FI.NewToOldValueMap.erase(CNII); - } - } else if (!FI.NewToOldValueMap.empty()) { - std::map::iterator II = - FI.NewToOldValueMap.find(&CI); - assert(II != FI.NewToOldValueMap.end() && "CI not found in clone?"); - FI.NewToOldValueMap.insert(std::make_pair(NewCall, II->second)); - FI.NewToOldValueMap.erase(II); - } - } - - CI.getParent()->getInstList().erase(&CI); -} diff --git a/runtime/GCCLibraries/libpoolalloc/Makefile b/runtime/GCCLibraries/libpoolalloc/Makefile deleted file mode 100644 index 2788fb27309..00000000000 --- a/runtime/GCCLibraries/libpoolalloc/Makefile +++ /dev/null @@ -1,4 +0,0 @@ -LEVEL = ../../.. -LIBNAME = poolalloc -include ../Makefile.libs - diff --git a/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c b/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c deleted file mode 100644 index 4fa0aedecff..00000000000 --- a/runtime/GCCLibraries/libpoolalloc/PoolAllocatorChained.c +++ /dev/null @@ -1,461 +0,0 @@ -#include -#include -#include - -#undef assert -#define assert(X) - - -/* In the current implementation, each slab in the pool has NODES_PER_SLAB - * nodes unless the isSingleArray flag is set in which case it contains a - * single array of size ArraySize. Small arrays (size <= NODES_PER_SLAB) are - * still allocated in the slabs of size NODES_PER_SLAB - */ -#define NODES_PER_SLAB 512 - -typedef struct PoolTy { - void *Data; - unsigned NodeSize; - unsigned FreeablePool; /* Set to false if the memory from this pool cannot be - freed before destroy*/ - -} PoolTy; - -/* PoolSlab Structure - Hold NODES_PER_SLAB objects of the current node type. - * Invariants: FirstUnused <= LastUsed+1 - */ -typedef struct PoolSlab { - unsigned FirstUnused; /* First empty node in slab */ - int LastUsed; /* Last allocated node in slab */ - struct PoolSlab *Next; - unsigned char AllocatedBitVector[NODES_PER_SLAB/8]; - unsigned char StartOfAllocation[NODES_PER_SLAB/8]; - - unsigned isSingleArray; /* If this slab is used for exactly one array */ - /* The array is allocated from the start to the end of the slab */ - unsigned ArraySize; /* The size of the array allocated */ - - char Data[1]; /* Buffer to hold data in this slab... variable sized */ - -} PoolSlab; - -#define NODE_ALLOCATED(POOLSLAB, NODENUM) \ - ((POOLSLAB)->AllocatedBitVector[(NODENUM) >> 3] & (1 << ((NODENUM) & 7))) -#define MARK_NODE_ALLOCATED(POOLSLAB, NODENUM) \ - (POOLSLAB)->AllocatedBitVector[(NODENUM) >> 3] |= 1 << ((NODENUM) & 7) -#define MARK_NODE_FREE(POOLSLAB, NODENUM) \ - (POOLSLAB)->AllocatedBitVector[(NODENUM) >> 3] &= ~(1 << ((NODENUM) & 7)) -#define ALLOCATION_BEGINS(POOLSLAB, NODENUM) \ - ((POOLSLAB)->StartOfAllocation[(NODENUM) >> 3] & (1 << ((NODENUM) & 7))) -#define SET_START_BIT(POOLSLAB, NODENUM) \ - (POOLSLAB)->StartOfAllocation[(NODENUM) >> 3] |= 1 << ((NODENUM) & 7) -#define CLEAR_START_BIT(POOLSLAB, NODENUM) \ - (POOLSLAB)->StartOfAllocation[(NODENUM) >> 3] &= ~(1 << ((NODENUM) & 7)) - - -/* poolinit - Initialize a pool descriptor to empty - */ -void poolinit(PoolTy *Pool, unsigned NodeSize) { - if (!Pool) { - printf("Null pool pointer passed into poolinit!\n"); - exit(1); - } - - Pool->NodeSize = NodeSize; - Pool->Data = 0; - - Pool->FreeablePool = 1; - -} - -void poolmakeunfreeable(PoolTy *Pool) { - if (!Pool) { - printf("Null pool pointer passed in to poolmakeunfreeable!\n"); - exit(1); - } - - Pool->FreeablePool = 0; -} - -/* pooldestroy - Release all memory allocated for a pool - */ -void pooldestroy(PoolTy *Pool) { - PoolSlab *PS; - if (!Pool) { - printf("Null pool pointer passed in to pooldestroy!\n"); - exit(1); - } - - PS = (PoolSlab*)Pool->Data; - while (PS) { - PoolSlab *Next = PS->Next; - free(PS); - PS = Next; - } -} - -static void *FindSlabEntry(PoolSlab *PS, unsigned NodeSize) { - /* Loop through all of the slabs looking for one with an opening */ - for (; PS; PS = PS->Next) { - - /* If the slab is a single array, go on to the next slab */ - /* Don't allocate single nodes in a SingleArray slab */ - if (PS->isSingleArray) - continue; - - /* Check to see if there are empty entries at the end of the slab... */ - if (PS->LastUsed < NODES_PER_SLAB-1) { - /* Mark the returned entry used */ - MARK_NODE_ALLOCATED(PS, PS->LastUsed+1); - SET_START_BIT(PS, PS->LastUsed+1); - - /* If we are allocating out the first unused field, bump its index also */ - if (PS->FirstUnused == PS->LastUsed+1) - PS->FirstUnused++; - - /* Return the entry, increment LastUsed field. */ - return &PS->Data[0] + ++PS->LastUsed * NodeSize; - } - - /* If not, check to see if this node has a declared "FirstUnused" value that - * is less than the number of nodes allocated... - */ - if (PS->FirstUnused < NODES_PER_SLAB) { - /* Successfully allocate out the first unused node */ - unsigned Idx = PS->FirstUnused; - - MARK_NODE_ALLOCATED(PS, Idx); - SET_START_BIT(PS, Idx); - - /* Increment FirstUnused to point to the new first unused value... */ - do { - ++PS->FirstUnused; - } while (PS->FirstUnused < NODES_PER_SLAB && - NODE_ALLOCATED(PS, PS->FirstUnused)); - - return &PS->Data[0] + Idx*NodeSize; - } - } - - /* No empty nodes available, must grow # slabs! */ - return 0; -} - -char *poolalloc(PoolTy *Pool) { - unsigned NodeSize; - PoolSlab *PS; - void *Result; - - if (!Pool) { - printf("Null pool pointer passed in to poolalloc!\n"); - exit(1); - } - - NodeSize = Pool->NodeSize; - // Return if this pool has size 0 - if (NodeSize == 0) - return 0; - - PS = (PoolSlab*)Pool->Data; - - if ((Result = FindSlabEntry(PS, NodeSize))) - return Result; - - /* Otherwise we must allocate a new slab and add it to the list */ - PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*NODES_PER_SLAB-1); - - if (!PS) { - printf("poolalloc: Could not allocate memory!"); - exit(1); - } - - /* Initialize the slab to indicate that the first element is allocated */ - PS->FirstUnused = 1; - PS->LastUsed = 0; - /* This is not a single array */ - PS->isSingleArray = 0; - PS->ArraySize = 0; - - MARK_NODE_ALLOCATED(PS, 0); - SET_START_BIT(PS, 0); - - /* Add the slab to the list... */ - PS->Next = (PoolSlab*)Pool->Data; - Pool->Data = PS; - return &PS->Data[0]; -} - -void poolfree(PoolTy *Pool, char *Node) { - unsigned NodeSize, Idx; - PoolSlab *PS; - PoolSlab **PPS; - unsigned idxiter; - - if (!Pool) { - printf("Null pool pointer passed in to poolfree!\n"); - exit(1); - } - - NodeSize = Pool->NodeSize; - - // Return if this pool has size 0 - if (NodeSize == 0) - return; - - PS = (PoolSlab*)Pool->Data; - PPS = (PoolSlab**)&Pool->Data; - - /* Search for the slab that contains this node... */ - while (&PS->Data[0] > Node || &PS->Data[NodeSize*NODES_PER_SLAB-1] < Node) { - if (!PS) { - printf("poolfree: node being free'd not found in allocation pool specified!\n"); - exit(1); - } - - PPS = &PS->Next; - PS = PS->Next; - } - - /* PS now points to the slab where Node is */ - - Idx = (Node-&PS->Data[0])/NodeSize; - assert(Idx < NODES_PER_SLAB && "Pool slab searching loop broken!"); - - if (PS->isSingleArray) { - - /* If this slab is a SingleArray */ - - if (Idx != 0) { - printf("poolfree: Attempt to free middle of allocated array\n"); - exit(1); - } - if (!NODE_ALLOCATED(PS,0)) { - printf("poolfree: Attempt to free node that is already freed\n"); - exit(1); - } - /* Mark this SingleArray slab as being free by just marking the first - entry as free*/ - MARK_NODE_FREE(PS, 0); - } else { - - /* If this slab is not a SingleArray */ - - if (!ALLOCATION_BEGINS(PS, Idx)) { - printf("poolfree: Attempt to free middle of allocated array\n"); - exit(1); - } - - /* Free the first node */ - if (!NODE_ALLOCATED(PS, Idx)) { - printf("poolfree: Attempt to free node that is already freed\n"); - exit(1); - } - CLEAR_START_BIT(PS, Idx); - MARK_NODE_FREE(PS, Idx); - - // Free all nodes - idxiter = Idx + 1; - while (idxiter < NODES_PER_SLAB && (!ALLOCATION_BEGINS(PS,idxiter)) && - (NODE_ALLOCATED(PS, idxiter))) { - MARK_NODE_FREE(PS, idxiter); - ++idxiter; - } - - /* Update the first free field if this node is below the free node line */ - if (Idx < PS->FirstUnused) PS->FirstUnused = Idx; - - /* If we are not freeing the last element in a slab... */ - if (idxiter - 1 != PS->LastUsed) { - return; - } - - /* Otherwise we are freeing the last element in a slab... shrink the - * LastUsed marker down to last used node. - */ - PS->LastUsed = Idx; - do { - --PS->LastUsed; - /* Fixme, this should scan the allocated array an entire byte at a time - * for performance! - */ - } while (PS->LastUsed >= 0 && (!NODE_ALLOCATED(PS, PS->LastUsed))); - - assert(PS->FirstUnused <= PS->LastUsed+1 && - "FirstUnused field was out of date!"); - } - - /* Ok, if this slab is empty, we unlink it from the of slabs and either move - * it to the head of the list, or free it, depending on whether or not there - * is already an empty slab at the head of the list. - */ - /* Do this only if the pool is freeable */ - if (Pool->FreeablePool) { - if (PS->isSingleArray) { - /* If it is a SingleArray, just free it */ - *PPS = PS->Next; - free(PS); - } else if (PS->LastUsed == -1) { /* Empty slab? */ - PoolSlab *HeadSlab; - *PPS = PS->Next; /* Unlink from the list of slabs... */ - - HeadSlab = (PoolSlab*)Pool->Data; - if (HeadSlab && HeadSlab->LastUsed == -1){/*List already has empty slab?*/ - free(PS); /*Free memory for slab */ - } else { - PS->Next = HeadSlab; /*No empty slab yet, add this*/ - Pool->Data = PS; /*one to the head of the list */ - } - } - } else { - /* Pool is not freeable for safety reasons */ - /* Leave it in the list of PoolSlabs as an empty PoolSlab */ - if (!PS->isSingleArray) - if (PS->LastUsed == -1) { - PS->FirstUnused = 0; - - /* Do not free the pool, but move it to the head of the list if there is - no empty slab there already */ - PoolSlab *HeadSlab; - HeadSlab = (PoolSlab*)Pool->Data; - if (HeadSlab && HeadSlab->LastUsed != -1) { - PS->Next = HeadSlab; - Pool->Data = PS; - } - } - } -} - -/* The poolallocarray version of FindSlabEntry */ -static void *FindSlabEntryArray(PoolSlab *PS, unsigned NodeSize, - unsigned Size) { - unsigned i; - - /* Loop through all of the slabs looking for one with an opening */ - for (; PS; PS = PS->Next) { - - /* For large array allocation */ - if (Size > NODES_PER_SLAB) { - /* If this slab is a SingleArray that is free with size > Size, use it */ - if (PS->isSingleArray && !NODE_ALLOCATED(PS,0) && PS->ArraySize >= Size) { - /* Allocate the array in this slab */ - MARK_NODE_ALLOCATED(PS,0); /* In a single array, only the first node - needs to be marked */ - return &PS->Data[0]; - } else - continue; - } else if (PS->isSingleArray) - continue; /* Do not allocate small arrays in SingleArray slabs */ - - /* For small array allocation */ - /* Check to see if there are empty entries at the end of the slab... */ - if (PS->LastUsed < NODES_PER_SLAB-Size) { - /* Mark the returned entry used and set the start bit*/ - SET_START_BIT(PS, PS->LastUsed + 1); - for (i = PS->LastUsed + 1; i <= PS->LastUsed + Size; ++i) - MARK_NODE_ALLOCATED(PS, i); - - /* If we are allocating out the first unused field, bump its index also */ - if (PS->FirstUnused == PS->LastUsed+1) - PS->FirstUnused += Size; - - /* Increment LastUsed */ - PS->LastUsed += Size; - - /* Return the entry */ - return &PS->Data[0] + (PS->LastUsed - Size + 1) * NodeSize; - } - - /* If not, check to see if this node has a declared "FirstUnused" value - * starting which Size nodes can be allocated - */ - if (PS->FirstUnused < NODES_PER_SLAB - Size + 1 && - (PS->LastUsed < PS->FirstUnused || - PS->LastUsed - PS->FirstUnused >= Size)) { - unsigned Idx = PS->FirstUnused, foundArray; - - /* Check if there is a continuous array of Size nodes starting - FirstUnused */ - foundArray = 1; - for (i = Idx; (i < Idx + Size) && foundArray; ++i) - if (NODE_ALLOCATED(PS, i)) - foundArray = 0; - - if (foundArray) { - /* Successfully allocate starting from the first unused node */ - SET_START_BIT(PS, Idx); - for (i = Idx; i < Idx + Size; ++i) - MARK_NODE_ALLOCATED(PS, i); - - PS->FirstUnused += Size; - while (PS->FirstUnused < NODES_PER_SLAB && - NODE_ALLOCATED(PS, PS->FirstUnused)) { - ++PS->FirstUnused; - } - return &PS->Data[0] + Idx*NodeSize; - } - - } - } - - /* No empty nodes available, must grow # slabs! */ - return 0; -} - -char* poolallocarray(PoolTy* Pool, unsigned Size) { - unsigned NodeSize; - PoolSlab *PS; - void *Result; - unsigned i; - - if (!Pool) { - printf("Null pool pointer passed to poolallocarray!\n"); - exit(1); - } - - NodeSize = Pool->NodeSize; - - // Return if this pool has size 0 - if (NodeSize == 0) - return 0; - - PS = (PoolSlab*)Pool->Data; - - if ((Result = FindSlabEntryArray(PS, NodeSize,Size))) - return Result; - - /* Otherwise we must allocate a new slab and add it to the list */ - if (Size > NODES_PER_SLAB) { - /* Allocate a new slab of size Size */ - PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*Size-1); - if (!PS) { - printf("poolallocarray: Could not allocate memory!\n"); - exit(1); - } - PS->isSingleArray = 1; - PS->ArraySize = Size; - MARK_NODE_ALLOCATED(PS, 0); - } else { - PS = (PoolSlab*)malloc(sizeof(PoolSlab)+NodeSize*NODES_PER_SLAB-1); - if (!PS) { - printf("poolallocarray: Could not allocate memory!\n"); - exit(1); - } - - /* Initialize the slab to indicate that the first element is allocated */ - PS->FirstUnused = Size; - PS->LastUsed = Size - 1; - - PS->isSingleArray = 0; - PS->ArraySize = 0; - - SET_START_BIT(PS, 0); - for (i = 0; i < Size; ++i) { - MARK_NODE_ALLOCATED(PS, i); - } - } - - /* Add the slab to the list... */ - PS->Next = (PoolSlab*)Pool->Data; - Pool->Data = PS; - return &PS->Data[0]; -} -- 2.34.1