| //===-- 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 "llvm/DerivedTypes.h" |
| #include "llvm/Support/CallSite.h" |
| #include "Support/EquivalenceClasses.h" |
| #include "Support/VectorExtras.h" |
| #include "Support/hash_set" |
| #include <set> |
| |
| namespace llvm { |
| |
| class CompleteBUDataStructures; |
| class DSNode; |
| class DSGraph; |
| class Type; |
| class AllocaInst; |
| |
| 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 { |
| FuncInfo() : Clone(0) {} |
| |
| /// MarkedNodes - The set of nodes which are not locally pool allocatable in |
| /// the current function. |
| /// |
| hash_set<DSNode*> 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<DSNode*> ArgNodes; |
| |
| /// 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<DSNode*, Value*> 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<Value*, const Value*> NewToOldValueMap; |
| }; |
| |
| struct EquivClassInfo { |
| // FuncsInClass - This is a list of all of the functions in this equiv |
| // class. |
| std::vector<Function*> FuncsInClass; |
| |
| // G - The DSGraph which contains a union of all of the nodes in this |
| // equivalence class. |
| DSGraph *G; |
| |
| // ECGraphToPrivateMap - This map, given a DSNode in the ECI DSGraph and a |
| // function, will tell you which DS node in the function DS graph this node |
| // corresponds to (or null if none). |
| std::map<std::pair<Function*,DSNode*>, DSNode*> ECGraphToPrivateMap; |
| |
| // ArgNodes - The list of DSNodes which require arguments to be passed in |
| // for all members of this equivalence class. |
| std::vector<DSNode*> ArgNodes; |
| |
| EquivClassInfo() : G(0) {} |
| }; |
| } |
| |
| |
| |
| /// PoolAllocate - The main pool allocation pass |
| /// |
| class PoolAllocate : public Pass { |
| Module *CurModule; |
| CompleteBUDataStructures *BU; |
| |
| std::map<Function*, PA::FuncInfo> FunctionInfo; |
| |
| // Equivalence class where functions that can potentially be called via the |
| // same function pointer are in the same class. |
| EquivalenceClasses<Function*> FuncECs; |
| |
| // Each equivalence class leader has an EquivClassInfo object. This map holds |
| // them. |
| typedef std::map<Function*, PA::EquivClassInfo> ECInfoForLeadersMapTy; |
| ECInfoForLeadersMapTy ECInfoForLeadersMap; |
| |
| /// OneCalledFunction - For each indirect function call, we keep track of one |
| /// target of the call. This is used to find the equivalence class called by |
| /// a call site. |
| std::map<Instruction*, Function *> OneCalledFunction; |
| |
| public: |
| |
| Function *PoolInit, *PoolDestroy, *PoolAlloc, *PoolAllocArray, *PoolFree; |
| static const Type *PoolDescPtrTy; |
| |
| const PA::EquivClassInfo &getECIForIndirectCallSite(CallSite CS); |
| |
| /// GlobalNodes - For each node (with an H marker) in the globals graph, this |
| /// map contains the global variable that holds the pool descriptor for the |
| /// node. |
| std::map<DSNode*, Value*> GlobalNodes; |
| public: |
| bool run(Module &M); |
| |
| virtual void getAnalysisUsage(AnalysisUsage &AU) const; |
| |
| CompleteBUDataStructures &getBUDataStructures() const { return *BU; } |
| |
| //Dinakar to get function info for all (cloned functions) |
| PA::FuncInfo *getFunctionInfo(Function *F) { |
| //If it is cloned or not check it out |
| if (FunctionInfo.count(F)) |
| return &FunctionInfo[F]; |
| else { |
| //Probably cloned |
| std::map<Function *, PA::FuncInfo>::iterator fI = FunctionInfo.begin(), |
| fE = FunctionInfo.end(); |
| for (; fI != fE; ++fI) |
| if (fI->second.Clone == F) |
| return &fI->second; |
| return 0; |
| } |
| } |
| |
| PA::FuncInfo *getFuncInfo(Function &F) { |
| std::map<Function*, PA::FuncInfo>::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(); |
| |
| /// BuildIndirectFunctionSets - Iterate over the module looking for indirect |
| /// calls to functions |
| void BuildIndirectFunctionSets(Module &M); |
| |
| /// SetupGlobalPools - Create global pools for all DSNodes in the globals |
| /// graph which contain heap objects. If a global variable points to a piece |
| /// of memory allocated from the heap, this pool gets a global lifetime. |
| /// |
| /// This method returns true if correct pool allocation of the module cannot |
| /// be performed because there is no main function for the module and there |
| /// are global pools. |
| bool SetupGlobalPools(Module &M); |
| |
| void FindFunctionPoolArgs(Function &F); |
| |
| /// 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 inserts alloca instruction in the function for all |
| /// pools specified in the NodesToPA list. This adds an entry to the |
| /// PoolDescriptors map for each DSNode. |
| /// |
| void CreatePools(Function &F, const std::vector<DSNode*> &NodesToPA, |
| std::map<DSNode*, Value*> &PoolDescriptors); |
| |
| void TransformBody(DSGraph &g, PA::FuncInfo &fi, |
| std::set<std::pair<AllocaInst*, Instruction*> > &poolUses, |
| std::set<std::pair<AllocaInst*, CallInst*> > &poolFrees, |
| Function &F); |
| |
| /// InitializeAndDestroyPools - This inserts calls to poolinit and pooldestroy |
| /// into the function to initialize and destroy the pools in the NodesToPA |
| /// list. |
| void InitializeAndDestroyPools(Function &F, |
| const std::vector<DSNode*> &NodesToPA, |
| std::map<DSNode*, Value*> &PoolDescriptors, |
| std::set<std::pair<AllocaInst*, Instruction*> > &PoolUses, |
| std::set<std::pair<AllocaInst*, CallInst*> > &PoolFrees); |
| |
| void CalculateLivePoolFreeBlocks(std::set<BasicBlock*> &LiveBlocks,Value *PD); |
| }; |
| |
| } |
| |
| #endif |