diff options
Diffstat (limited to 'lib/Transforms/IPO/OldPoolAllocate.cpp')
| -rw-r--r-- | lib/Transforms/IPO/OldPoolAllocate.cpp | 1759 |
1 files changed, 0 insertions, 1759 deletions
diff --git a/lib/Transforms/IPO/OldPoolAllocate.cpp b/lib/Transforms/IPO/OldPoolAllocate.cpp deleted file mode 100644 index bf86403d86..0000000000 --- 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 <algorithm> -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<PtrSize> -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<bool> -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<PointerType>(Ty)) { - return POINTERTYPE; - } else if (const StructType *STy = dyn_cast<StructType>(Ty)) { - vector<const Type *> 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<ArrayType>(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<CallArgInfo> 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<DSNode*, PoolInfo> &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<DSNode*, PoolInfo> &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<const Type*> 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<DataStructure>(); - } - - 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<TransformFunctionInfo, Function*> TransformedFunctions; - - // getTransformedFunction - Get a transformed function, or return null if - // the function specified hasn't been transformed yet. - // - Function *getTransformedFunction(TransformFunctionInfo &TFI) const { - map<TransformFunctionInfo, Function*>::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<AllocDSNode*> &Allocs, - map<DSNode*, PoolInfo> &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<DSNode*, PoolInfo> &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<DSNode*, PoolInfo> &PoolDescs); - - }; - - RegisterOpt<PoolAllocate> 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<AllocDSNode*> 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<DSNode*, PoolInfo> 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<NewInstructionCreator> { - PoolAllocate &PoolAllocator; - vector<ScalarInfo> &Scalars; - map<CallInst*, TransformFunctionInfo> &CallMap; - map<Value*, Value*> &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<RefToUpdate> 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<Value*> 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<ScalarInfo> &S, - map<CallInst*, TransformFunctionInfo> &C, - map<Value*, Value*> &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<Constant>(Ref.OldVal) && // Refering to a null ptr? - cast<Constant>(Ref.OldVal)->isNullValue()) { - // Transform the null pointer into a null index... caching in XFormMap - XFormMap[Ref.OldVal] = NewVal = Constant::getNullValue(POINTERTYPE); - //} else if (isa<Argument>(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<Instruction *> 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<Value*> 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<PointerType>(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<Instruction*> AfterInsts; - - Instruction *IdxInst = - BinaryOperator::create(Instruction::Add, *I.idx_begin(), Index, "idx"); - AfterInsts.push_back(IdxInst); - - vector<Value*> 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<Value*> 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<Value*> 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<Value*> 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<PoolBaseLoadEliminator> { - // PoolDescValues - Keep track of the values in the current function that are - // pool descriptors (loads from which we want to eliminate). - // - vector<Value*> PoolDescValues; - - // PoolDescMap - As we are analyzing a BB, keep track of which load to use - // when referencing a pool descriptor. - // - map<Value*, LoadInst*> 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<DSNode*, PoolInfo> &PoolDescs) { - Eliminated = Remaining = 0; - for (map<DSNode*, PoolInfo>::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<Value*, LoadInst*>::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<DSNode*, PointerValSet> &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<DSNode*, PointerValSet> &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<DSNode*, PoolInfo> &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<DSNode*> 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<DSNode*> &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<DSNode*, PoolInfo> &PoolDescs) { - // FIXME: This does not work for indirect function cal |