| //===-- TransformFunctionBody.cpp - Pool Function Transformer -------------===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file was developed by the LLVM research group and is distributed under |
| // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defines the PoolAllocate::TransformBody method. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #define DEBUG_TYPE "PoolAllocator" |
| |
| #include "dsa/DataStructure.h" |
| #include "dsa/DSGraph.h" |
| #include "dsa/CallTargets.h" |
| #include "poolalloc/PoolAllocate.h" |
| #include "poolalloc/RuntimeChecks.h" |
| #include "llvm/IR/Module.h" |
| #include "llvm/IR/DerivedTypes.h" |
| #include "llvm/IR/Constants.h" |
| #include "llvm/IR/Instructions.h" |
| #include "llvm/IR/DataLayout.h" |
| #include "llvm/IR/InstVisitor.h" |
| #include "llvm/Support/FormattedStream.h" |
| #include "llvm/Support/Debug.h" |
| #include "llvm/ADT/StringMap.h" |
| |
| #include <iostream> |
| using namespace llvm; |
| using namespace PA; |
| |
| namespace { |
| /// FuncTransform - This class implements transformation required of pool |
| /// allocated functions. |
| struct FuncTransform : public InstVisitor<FuncTransform> { |
| PoolAllocate &PAInfo; |
| DSGraph* G; // The Bottom-up DS Graph |
| FuncInfo &FI; |
| |
| // PoolUses - For each pool (identified by the pool descriptor) keep track |
| // of which blocks require the memory in the pool to not be freed. This |
| // does not include poolfree's. Note that this is only tracked for pools |
| // for which the given function is the pool's home i.e., the pool is an |
| // alloca instruction because it is allocated within the current function. |
| std::multimap<AllocaInst*, Instruction*> &PoolUses; |
| |
| // PoolFrees - For each pool, keep track of the actual poolfree calls |
| // inserted into the code. This is seperated out from PoolUses. |
| std::multimap<AllocaInst*, CallInst*> &PoolFrees; |
| |
| FuncTransform(PoolAllocate &P, DSGraph* g, FuncInfo &fi, |
| std::multimap<AllocaInst*, Instruction*> &poolUses, |
| std::multimap<AllocaInst*, CallInst*> &poolFrees) |
| : PAInfo(P), G(g), FI(fi), |
| PoolUses(poolUses), PoolFrees(poolFrees) { |
| } |
| |
| template <typename InstType, typename SetType> |
| void AddPoolUse(InstType &I, Value *PoolHandle, SetType &Set) { |
| if (AllocaInst *AI = dyn_cast<AllocaInst>(PoolHandle->stripPointerCasts())) |
| Set.insert(std::make_pair(AI, &I)); |
| } |
| |
| // FIXME: Factor out assumptions about c stdlib function names |
| void visitInstruction(Instruction &I); |
| void visitAllocaInst(AllocaInst &MI); |
| void visitMallocCall(CallSite & CS); |
| void visitCallocCall(CallSite CS); |
| void visitReallocCall(CallSite CS); |
| void visitMemAlignCall(CallSite CS); |
| void visitStrdupCall(CallSite CS); |
| void visitRuntimeCheck(CallSite CS, const unsigned PoolArgc); |
| void visitFreeCall(CallSite &CS); |
| void visitCallSite(CallSite &CS); |
| void visitCallInst(CallInst &CI) { |
| CallSite CS(&CI); |
| visitCallSite(CS); |
| } |
| void visitInvokeInst(InvokeInst &II) { |
| CallSite CS(&II); |
| visitCallSite(CS); |
| } |
| void visitLoadInst(LoadInst &I); |
| void visitStoreInst (StoreInst &I); |
| |
| private: |
| Instruction *TransformAllocationInstr(Instruction *I, Value *Size); |
| Instruction *InsertPoolFreeInstr(Value *V, Instruction *Where); |
| |
| // |
| // Method: UpdateNewToOldValueMap() |
| // |
| // Description: |
| // This method removes the old mapping indexed by OldVal and inserts one |
| // or two new mappings mapping NewV1 and NewV2 to the value that was |
| // indexed by OldVal. |
| // |
| void UpdateNewToOldValueMap(Value *OldVal, Value *NewV1, Value *NewV2 = 0) { |
| std::map<Value*, const Value*>::iterator I = |
| FI.NewToOldValueMap.find(OldVal); |
| assert(I != FI.NewToOldValueMap.end() && "OldVal not found in clone?"); |
| FI.NewToOldValueMap.insert(std::make_pair(NewV1, I->second)); |
| if (NewV2) |
| FI.NewToOldValueMap.insert(std::make_pair(NewV2, I->second)); |
| FI.NewToOldValueMap.erase(I); |
| } |
| |
| Value* getOldValueIfAvailable(Value* V) { |
| if (!FI.NewToOldValueMap.empty()) { |
| // If the NewToOldValueMap is in effect, use it. |
| std::map<Value*,const Value*>::iterator I = FI.NewToOldValueMap.find(V); |
| if (I != FI.NewToOldValueMap.end()) |
| V = const_cast<Value*>(I->second); |
| } |
| return V; |
| } |
| |
| DSNodeHandle& getDSNodeHFor(Value *V) { |
| return G->getScalarMap()[getOldValueIfAvailable(V)]; |
| } |
| |
| // FIXME: Does this get global (or just local) pools? |
| Value *getPoolHandle(Value *V) { |
| DSNode *Node = getDSNodeHFor(V).getNode(); |
| // Get the pool handle for this DSNode... |
| std::map<const DSNode*, Value*>::iterator I = |
| FI.PoolDescriptors.find(Node); |
| return I != FI.PoolDescriptors.end() ? I->second : 0; |
| } |
| |
| Function* retCloneIfFunc(Value *V); |
| |
| void verifyCallees (const std::vector<const Function *> & Functions); |
| }; |
| } |
| |
| static inline Value * |
| castTo (Value * V, Type * Ty, std::string Name, Instruction * InsertPt) { |
| // |
| // Don't bother creating a cast if it's already the correct type. |
| // |
| if (V->getType() == Ty) |
| return V; |
| |
| // |
| // If it's a constant, just create a constant expression. |
| // |
| if (Constant * C = dyn_cast<Constant>(V)) { |
| Constant * CE = ConstantExpr::getZExtOrBitCast (C, Ty); |
| return CE; |
| } |
| |
| // |
| // Otherwise, insert a cast instruction. |
| // |
| return CastInst::CreateZExtOrBitCast (V, Ty, Name, InsertPt); |
| } |
| |
| void |
| PoolAllocate::TransformBody (DSGraph* g, PA::FuncInfo &fi, |
| std::multimap<AllocaInst*,Instruction*> &poolUses, |
| std::multimap<AllocaInst*, CallInst*> &poolFrees, |
| Function &F) { |
| FuncTransform(*this, g, fi, poolUses, poolFrees).visit(F); |
| } |
| |
| // |
| // Method: verifyCallees() |
| // |
| // Description: |
| // This method performs various sanity checks on targets of indirect function |
| // calls. |
| // |
| void |
| FuncTransform::verifyCallees (const std::vector<const Function *> & Functions) { |
| #ifndef NDEBUG |
| // |
| // There's nothing to do if there's no function call targets at all. |
| // |
| if (Functions.size() == 0) |
| return; |
| |
| // |
| // Get the number of pool arguments for the first function. |
| // |
| unsigned numPoolArgs = PAInfo.getFuncInfo(*Functions[0])->ArgNodes.size(); |
| |
| // |
| // Get the DSGraph of the first function. |
| // |
| DataStructures& Graphs = PAInfo.getGraphs(); |
| DSGraph * firstGraph = Graphs.getDSGraph (*Functions[0]); |
| |
| // |
| // Scan through all other indirect function call targets. Ensure that these |
| // functions have the same number of pool arguments and the same DSGraph as |
| // the first function. |
| // |
| for (unsigned index = 1; index < Functions.size(); ++index) { |
| // |
| // Get the function information for the function. |
| // |
| const Function * F = Functions[index]; |
| FuncInfo *FI = PAInfo.getFuncInfo(*F); |
| |
| // |
| // Get the DSGraph. |
| // |
| DSGraph * G = Graphs.getDSGraph (*Functions[index]); |
| |
| // |
| // Assert that the graph and number of pool arguments are consistent. |
| // |
| assert (G == firstGraph); |
| assert (FI->ArgNodes.size() == numPoolArgs); |
| } |
| #endif |
| |
| return; |
| } |
| |
| // Returns the clone if V is a static function (not a pointer) and belongs |
| // to an equivalence class i.e. is pool allocated |
| // FIXME: Rename this to 'getCloneIfFunc' (or similar)? |
| // FIXME: Strip pointer casts |
| // FIXME: Comment this? |
| Function* FuncTransform::retCloneIfFunc(Value *V) { |
| if (Function *F = dyn_cast<Function>(V)) |
| if (FuncInfo *FI = PAInfo.getFuncInfo(*F)) |
| return FI->Clone; |
| |
| return 0; |
| } |
| |
| void FuncTransform::visitLoadInst(LoadInst &LI) { |
| // |
| // Record the use of the pool handle for the pointer being dereferenced. |
| // |
| if (Value *PH = getPoolHandle(LI.getOperand(0))) |
| AddPoolUse(LI, PH, PoolUses); |
| |
| // |
| // If this is a volatile load, then record a use of the pool handle for the |
| // loaded value, even if it is never used. |
| // |
| if (LI.isVolatile()) { |
| if (Value *PH = getPoolHandle(&LI)) |
| AddPoolUse (LI, PH, PoolUses); |
| } |
| |
| visitInstruction(LI); |
| } |
| |
| void FuncTransform::visitStoreInst(StoreInst &SI) { |
| if (Value *PH = getPoolHandle(SI.getOperand(1))) |
| AddPoolUse(SI, PH, PoolUses); |
| visitInstruction(SI); |
| } |
| |
| Instruction *FuncTransform::TransformAllocationInstr(Instruction *I, |
| Value *Size) { |
| // Ensure that the new instruction has the same name as the old one |
| // and the that the old one has no name. |
| std::string Name = I->getName(); I->setName(""); |
| |
| // |
| // FIXME: Don't assume allocation sizes are 32-bit; different architectures |
| // have different limits on the size of memory objects that they can |
| // allocate. |
| // |
| if (!Size->getType()->isIntegerTy(32)) |
| Size = CastInst::CreateIntegerCast(Size, Type::getInt32Ty(Size->getType()->getContext()), false, Size->getName(), I); |
| |
| |
| // Get the pool handle-- |
| // Do not change the instruction into a poolalloc() call unless we have a |
| // real pool descriptor |
| Value *PH = getPoolHandle(I); |
| if (PH == 0 || isa<ConstantPointerNull>(PH)) return I; |
| |
| // Create call to poolalloc, and record the use of the pool |
| Value* Opts[2] = {PH, Size}; |
| Instruction *V = CallInst::Create(PAInfo.PoolAlloc, Opts, Name, I); |
| AddPoolUse(*V, PH, PoolUses); |
| |
| // Cast to the appropriate type if necessary |
| // FIXME: Make use of "castTo" utility function |
| Instruction *Casted = V; |
| if (V->getType() != I->getType()) |
| Casted = CastInst::CreatePointerCast(V, I->getType(), V->getName(), I); |
| |
| // Update def-use info |
| I->replaceAllUsesWith(Casted); |
| |
| // If we are modifying the original function, update the DSGraph. |
| if (!FI.Clone) { |
| // V and Casted now point to whatever the original allocation did. |
| G->getScalarMap().replaceScalar(I, V); |
| if (V != Casted) |
| G->getScalarMap()[Casted] = G->getScalarMap()[V]; |
| } else { // Otherwise, update the NewToOldValueMap |
| UpdateNewToOldValueMap(I, V, V != Casted ? Casted : 0); |
| } |
| |
| // If this was an invoke, fix up the CFG. |
| if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { |
| // FIXME: Assert out since we potentially don't handle "invoke" correctly |
| BranchInst::Create (II->getNormalDest(), I); |
| II->getUnwindDest()->removePredecessor(II->getParent(), true); |
| } |
| |
| // Remove old allocation instruction. |
| I->eraseFromParent(); |
| return Casted; |
| } |
| |
| void FuncTransform::visitAllocaInst(AllocaInst &MI) { |
| #if 0 |
| if (MI.getType() != PoolAllocate::PoolDescPtrTy) { |
| Value *PH = getPoolHandle(&MI); |
| assert (PH && "Alloca has no pool handle!\n"); |
| } |
| #endif |
| |
| // FIXME: We should remove SAFECode-specific functionality (and comments) |
| // SAFECode will register alloca instructions with the run-time, so do not |
| // do that here. |
| // |
| // FIXME: |
| // There is a chance that we may need to update PoolUses to make sure that |
| // the pool handle is available in this function. |
| // |
| return; |
| } |
| |
| // |
| // Method: InsertPoolFreeInstr() |
| // |
| // Description: |
| // Insert a call to poolfree() at the specified point to free the specified |
| // value. |
| // |
| // Inputs: |
| // Arg - The value that should be freed by the call to poolfree(). |
| // Where - The instruction before which the poolfree() call should be |
| // inserted. |
| // |
| // Return value: |
| // NULL - No call to poolfree() was inserted. |
| // This may be possible if PoolAlloc has decided not to pool-allocate this. |
| // Otherwise, a pointer to the call instruction that calls poolfree() will be |
| // returned. |
| // |
| Instruction * |
| FuncTransform::InsertPoolFreeInstr (Value *Arg, Instruction *Where){ |
| // |
| // Attempt to get the pool handle of the specified value. If there is no |
| // pool handle, then just return NULL. |
| // |
| Value *PH = getPoolHandle(Arg); // Get the pool handle for this DSNode... |
| if (PH == 0 || isa<ConstantPointerNull>(PH)) return 0; |
| |
| // |
| // Cast the pointer to be freed to a void pointer type if necessary. |
| // |
| // FIXME: Change this to make use of "castTo" utility. |
| Value *Casted = Arg; |
| if (Arg->getType() != PointerType::getUnqual(Type::getInt8Ty(Arg->getContext()))) { |
| Casted = CastInst::CreatePointerCast(Arg, PointerType::getUnqual(Type::getInt8Ty(Arg->getContext())), |
| Arg->getName()+".casted", Where); |
| G->getScalarMap()[Casted] = G->getScalarMap()[Arg]; |
| } |
| |
| // |
| // Insert a call to poolfree(), and mark that memory was deallocated from the pool. |
| // |
| Value* Opts[2] = {PH, Casted}; |
| CallInst *FreeI = CallInst::Create(PAInfo.PoolFree, Opts, "", Where); |
| AddPoolUse(*FreeI, PH, PoolFrees); |
| return FreeI; |
| } |
| |
| #if 0 |
| void FuncTransform::visitFreeInst(FreeInst &FrI) { |
| if (Instruction *I = InsertPoolFreeInstr(FrI.getOperand(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<Value*,const Value*>::iterator II = |
| FI.NewToOldValueMap.find(&FrI); |
| assert(II != FI.NewToOldValueMap.end() && |
| "FrI not found in clone?"); |
| FI.NewToOldValueMap.insert(std::make_pair(I, II->second)); |
| FI.NewToOldValueMap.erase(II); |
| } |
| } |
| } |
| #endif |
| |
| void |
| FuncTransform::visitFreeCall (CallSite & CS) { |
| // |
| // Replace the call to the free() function with a call to poolfree(). |
| // |
| Instruction * InsertPt = CS.getInstruction(); |
| if (Instruction *I = InsertPoolFreeInstr (CS.getArgument(0), InsertPt)) { |
| // Delete the now obsolete free instruction... |
| // FIXME: use "eraseFromParent"? (Note this might require a refactoring) |
| InsertPt->getParent()->getInstList().erase(InsertPt); |
| |
| // Update the NewToOldValueMap if this is a clone |
| // FIXME: Use of utility function UpdateNewToOldValueMap |
| if (!FI.NewToOldValueMap.empty()) { |
| std::map<Value*,const Value*>::iterator II = |
| FI.NewToOldValueMap.find(InsertPt); |
| assert(II != FI.NewToOldValueMap.end() && |
| "free call not found in clone?"); |
| FI.NewToOldValueMap.insert(std::make_pair(I, II->second)); |
| FI.NewToOldValueMap.erase(II); |
| } |
| } |
| } |
| |
| void |
| FuncTransform::visitMallocCall(CallSite &CS) { |
| // |
| // Get the instruction to which the call site refers |
| // |
| Instruction * MI = CS.getInstruction(); |
| |
| // |
| // Get the pool handle for the node that this contributes to... |
| // |
| // FIXME: This check may be redundant |
| Value *PH = getPoolHandle(MI); |
| if (PH == 0 || isa<ConstantPointerNull>(PH)) return; |
| |
| // |
| // Find the size of the allocation. |
| // |
| Value *AllocSize = CS.getArgument(0); |
| |
| // |
| // Transform the allocation site to use poolalloc(). |
| // |
| TransformAllocationInstr(MI, AllocSize); |
| } |
| |
| // |
| // Method: visitCallocCall() |
| // |
| // Description: |
| // Transform a call to calloc() to use a pool-allocation version of calloc. |
| // We do this because pool_calloc() must check for a NULL return value before |
| // zeroing out the memory. |
| // |
| void |
| FuncTransform::visitCallocCall (CallSite CS) { |
| // |
| // Ensure that the calloc call has the correct number of arugments. |
| // |
| assert(CS.arg_end()-CS.arg_begin() == 2 && "calloc takes two arguments!"); |
| |
| // |
| // Ensure that the new instruction has the same name as the old one. This is |
| // done by removing the name of the old instruction. |
| // |
| Instruction * I = CS.getInstruction(); |
| std::string Name = I->getName(); I->setName(""); |
| |
| Type* Int32Type = Type::getInt32Ty(CS.getInstruction()->getContext()); |
| |
| // FIXME: Ensure that we use 32/64-bit object length sizes consistently |
| // FIXME: Introduce 'ObjectAllocationSize' variable |
| // or similar instead of repeatedly using same expression |
| |
| Value *V1 = CS.getArgument(0); |
| Value *V2 = CS.getArgument(1); |
| V1 = CastInst::CreateIntegerCast(V1, Int32Type, false, V1->getName(), I); |
| V2 = CastInst::CreateIntegerCast(V2, Int32Type, false, V2->getName(), I); |
| |
| // Get the pool handle-- |
| // Do not change the instruction into a poolalloc() call unless we have a |
| // real pool descriptor |
| Value *PH = getPoolHandle(CS.getInstruction()); |
| if (PH == 0 || isa<ConstantPointerNull>(PH)) |
| return; |
| |
| // |
| // Create call to poolcalloc, and record the use of the pool |
| // |
| Value* Opts[3] = {PH, V1, V2}; |
| Instruction *V = CallInst::Create(PAInfo.PoolCalloc, Opts, Name, I); |
| AddPoolUse(*V, PH, PoolUses); |
| |
| // Cast to the appropriate type if necessary |
| // FIXME: Make use of "castTo" utility function |
| Instruction *Casted = V; |
| if (V->getType() != I->getType()) |
| Casted = CastInst::CreatePointerCast(V, I->getType(), V->getName(), I); |
| |
| // Update def-use info |
| I->replaceAllUsesWith(Casted); |
| |
| // If we are modifying the original function, update the DSGraph. |
| if (!FI.Clone) { |
| // V and Casted now point to whatever the original allocation did. |
| G->getScalarMap().replaceScalar(I, V); |
| if (V != Casted) |
| G->getScalarMap()[Casted] = G->getScalarMap()[V]; |
| } else { // Otherwise, update the NewToOldValueMap |
| UpdateNewToOldValueMap(I, V, V != Casted ? Casted : 0); |
| } |
| |
| // If this was an invoke, fix up the CFG. |
| if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { |
| // FIXME: Assert out since we potentially don't handle "invoke" correctly |
| BranchInst::Create (II->getNormalDest(), I); |
| II->getUnwindDest()->removePredecessor(II->getParent(), true); |
| } |
| |
| // Remove old allocation instruction. |
| I->eraseFromParent(); |
| return; |
| } |
| |
| |
| void FuncTransform::visitReallocCall(CallSite CS) { |
| assert(CS.arg_end()-CS.arg_begin() == 2 && "realloc takes two arguments!"); |
| Instruction *I = CS.getInstruction(); |
| Value *PH = getPoolHandle(I); |
| Value *OldPtr = CS.getArgument(0); |
| Value *Size = CS.getArgument(1); |
| |
| // Don't poolallocate if we have no pool handle |
| if (PH == 0 || isa<ConstantPointerNull>(PH)) return; |
| |
| if (Size->getType() != Type::getInt32Ty(CS.getInstruction()->getContext())) |
| Size = CastInst::CreateIntegerCast(Size, Type::getInt32Ty(CS.getInstruction()->getContext()), false, Size->getName(), I); |
| |
| static Type *VoidPtrTy = PointerType::getUnqual(Type::getInt8Ty(CS.getInstruction()->getContext())); |
| if (OldPtr->getType() != VoidPtrTy) |
| OldPtr = CastInst::CreatePointerCast(OldPtr, VoidPtrTy, OldPtr->getName(), I); |
| |
| std::string Name = I->getName(); I->setName(""); |
| Value* Opts[3] = {PH, OldPtr, Size}; |
| Instruction *V = CallInst::Create(PAInfo.PoolRealloc, Opts, Name, I); |
| Instruction *Casted = V; |
| if (V->getType() != I->getType()) |
| Casted = CastInst::CreatePointerCast(V, I->getType(), V->getName(), I); |
| |
| // Update def-use info |
| I->replaceAllUsesWith(Casted); |
| |
| // If we are modifying the original function, update the DSGraph. |
| if (!FI.Clone) { |
| // V and Casted now point to whatever the original allocation did. |
| G->getScalarMap().replaceScalar(I, V); |
| if (V != Casted) |
| G->getScalarMap()[Casted] = G->getScalarMap()[V]; |
| } else { // Otherwise, update the NewToOldValueMap |
| UpdateNewToOldValueMap(I, V, V != Casted ? Casted : 0); |
| } |
| |
| // If this was an invoke, fix up the CFG. |
| if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { |
| BranchInst::Create (II->getNormalDest(), I); |
| II->getUnwindDest()->removePredecessor(II->getParent(), true); |
| } |
| |
| // Remove old allocation instruction. |
| I->eraseFromParent(); |
| } |
| |
| |
| /// visitMemAlignCall - Handle memalign and posix_memalign. |
| /// |
| void FuncTransform::visitMemAlignCall(CallSite CS) { |
| Instruction *I = CS.getInstruction(); |
| Value *ResultDest = 0; |
| Value *Align = 0; |
| Value *Size = 0; |
| Value *PH; |
| |
| Type* Int8Type = Type::getInt8Ty(CS.getInstruction()->getContext()); |
| Type* Int32Type = Type::getInt32Ty(CS.getInstruction()->getContext()); |
| |
| |
| if (CS.getCalledFunction()->getName() == "memalign") { |
| Align = CS.getArgument(0); |
| Size = CS.getArgument(1); |
| PH = getPoolHandle(I); |
| } else { |
| assert(CS.getCalledFunction()->getName() == "posix_memalign"); |
| ResultDest = CS.getArgument(0); |
| Align = CS.getArgument(1); |
| Size = CS.getArgument(2); |
| |
| assert(0 && "posix_memalign not implemented fully!"); |
| // We need to get the pool descriptor corresponding to *ResultDest. |
| PH = getPoolHandle(I); |
| |
| // Return success always. |
| PointerType * PT = dyn_cast<PointerType>(I->getType()); |
| assert (PT && "memalign() does not return pointer type!\n"); |
| Value *RetVal = ConstantPointerNull::get(PT); |
| I->replaceAllUsesWith(RetVal); |
| |
| static Type *PtrPtr=PointerType::getUnqual(PointerType::getUnqual(Int8Type)); |
| if (ResultDest->getType() != PtrPtr) |
| ResultDest = CastInst::CreatePointerCast(ResultDest, PtrPtr, ResultDest->getName(), I); |
| } |
| |
| if (!Align->getType()->isIntegerTy(32)) |
| Align = CastInst::CreateIntegerCast(Align, Int32Type, false, Align->getName(), I); |
| if (!Size->getType()->isIntegerTy(32)) |
| Size = CastInst::CreateIntegerCast(Size, Int32Type, false, Size->getName(), I); |
| |
| std::string Name = I->getName(); I->setName(""); |
| Value* Opts[3] = {PH, Align, Size}; |
| Instruction *V = CallInst::Create(PAInfo.PoolMemAlign, Opts, Name, I); |
| |
| Instruction *Casted = V; |
| if (V->getType() != I->getType()) |
| Casted = CastInst::CreatePointerCast(V, I->getType(), V->getName(), I); |
| |
| if (ResultDest) |
| new StoreInst(V, ResultDest, I); |
| else |
| I->replaceAllUsesWith(Casted); |
| |
| // If we are modifying the original function, update the DSGraph. |
| if (!FI.Clone) { |
| // V and Casted now point to whatever the original allocation did. |
| G->getScalarMap().replaceScalar(I, V); |
| if (V != Casted) |
| G->getScalarMap()[Casted] = G->getScalarMap()[V]; |
| } else { // Otherwise, update the NewToOldValueMap |
| UpdateNewToOldValueMap(I, V, V != Casted ? Casted : 0); |
| } |
| |
| // If this was an invoke, fix up the CFG. |
| if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { |
| BranchInst::Create (II->getNormalDest(), I); |
| II->getUnwindDest()->removePredecessor(II->getParent(), true); |
| } |
| |
| // Remove old allocation instruction. |
| I->eraseFromParent(); |
| } |
| |
| /// visitStrdupCall - Handle strdup(). |
| /// |
| void FuncTransform::visitStrdupCall(CallSite CS) { |
| assert(CS.arg_end()-CS.arg_begin() == 1 && "strdup takes one argument!"); |
| Instruction *I = CS.getInstruction(); |
| assert (getDSNodeHFor(I).getNode() && "strdup has NULL DSNode!\n"); |
| Value *PH = getPoolHandle(I); |
| |
| Type* Int8Type = Type::getInt8Ty(CS.getInstruction()->getContext()); |
| |
| |
| #if 0 |
| assert (PH && "PH for strdup is null!\n"); |
| #else |
| if (!PH) { |
| errs() << "strdup: NoPH\n"; |
| return; |
| } |
| #endif |
| Value *OldPtr = CS.getArgument(0); |
| |
| static Type *VoidPtrTy = PointerType::getUnqual(Int8Type); |
| if (OldPtr->getType() != VoidPtrTy) |
| OldPtr = CastInst::CreatePointerCast(OldPtr, VoidPtrTy, OldPtr->getName(), I); |
| |
| std::string Name = I->getName(); I->setName(""); |
| Value* Opts[3] = {PH, OldPtr, 0}; |
| Instruction *V = CallInst::Create(PAInfo.PoolStrdup, Opts, Name, I); |
| Instruction *Casted = V; |
| if (V->getType() != I->getType()) |
| Casted = CastInst::CreatePointerCast(V, I->getType(), V->getName(), I); |
| |
| // Update def-use info |
| I->replaceAllUsesWith(Casted); |
| |
| // If we are modifying the original function, update the DSGraph. |
| if (!FI.Clone) { |
| // V and Casted now point to whatever the original allocation did. |
| G->getScalarMap().replaceScalar(I, V); |
| if (V != Casted) |
| G->getScalarMap()[Casted] = G->getScalarMap()[V]; |
| } else { // Otherwise, update the NewToOldValueMap |
| UpdateNewToOldValueMap(I, V, V != Casted ? Casted : 0); |
| } |
| |
| // If this was an invoke, fix up the CFG. |
| if (InvokeInst *II = dyn_cast<InvokeInst>(I)) { |
| BranchInst::Create (II->getNormalDest(), I); |
| II->getUnwindDest()->removePredecessor(II->getParent(), true); |
| } |
| |
| // Remove old allocation instruction. |
| I->eraseFromParent(); |
| } |
| |
| // |
| // Method: visitRuntimeCheck() |
| // |
| // Description: |
| // Visit a call to a run-time check (or related function) and insert pool |
| // arguments where needed. PoolArgc is the number of initial pool arguments |
| // that should be filled at the call site with pool handles for the |
| // corresponding pointer arguments. |
| // |
| void |
| FuncTransform::visitRuntimeCheck (CallSite CS, const unsigned PoolArgc) { |
| // A call to the runtime check should have positions for each pool argument |
| // and the corresponding pointer. |
| assert ((CS.arg_size() >= 2 * PoolArgc) && |
| "Not enough arguments to call of a runtime check!"); |
| |
| for (unsigned PoolIndex = 0; PoolIndex < PoolArgc; ++PoolIndex) { |
| // |
| // Get the pool handle for the pointer argument. |
| // |
| Value *PH = |
| getPoolHandle(CS.getArgument(PoolArgc + PoolIndex)->stripPointerCasts()); |
| |
| // |
| // Insert the pool handle into the run-time check. |
| // |
| if (PH) { |
| Type * Int8Type = Type::getInt8Ty(CS.getInstruction()->getContext()); |
| Type * VoidPtrTy = PointerType::getUnqual(Int8Type); |
| PH = castTo (PH, VoidPtrTy, PH->getName(), CS.getInstruction()); |
| CS.setArgument (PoolIndex, PH); |
| |
| // |
| // Record that we've used the pool here. |
| // |
| AddPoolUse (*(CS.getInstruction()), PH, PoolUses); |
| } |
| } |
| } |
| |
| // |
| // Method: visitCallSite() |
| // |
| // Description: |
| // This method transforms a call site. A call site may either be a call |
| // instruction or an invoke instruction. |
| // |
| // Inputs: |
| // CS - The call site representing the instruction that should be transformed. |
| // |
| void FuncTransform::visitCallSite(CallSite& CS) { |
| const Function *CF = CS.getCalledFunction(); |
| Instruction *TheCall = CS.getInstruction(); |
| bool thread_creation_point = false; |
| |
| // |
| // Get the value that is called at this call site. Strip away any pointer |
| // casts that do not change the representation of the data (i.e., are |
| // lossless casts). |
| // |
| Value * CalledValue = CS.getCalledValue()->stripPointerCasts(); |
| |
| // |
| // The CallSite::getCalledFunction() method is not guaranteed to strip off |
| // pointer casts. If no called function was found, manually strip pointer |
| // casts off of the called value and see if we get a function. If so, this |
| // is a direct call, and we want to update CF accordingly. |
| // |
| if (!CF) CF = dyn_cast<Function>(CalledValue); |
| |
| // |
| // Do not change any inline assembly code. |
| // |
| if (isa<InlineAsm>(TheCall->getOperand(0))) { |
| errs() << "INLINE ASM: ignoring. Hoping that's safe.\n"; |
| return; |
| } |
| |
| // |
| // Ignore calls to NULL pointers or undefined values. |
| // |
| if ((isa<ConstantPointerNull>(CalledValue)) || |
| (isa<UndefValue>(CalledValue))) { |
| errs() << "WARNING: Ignoring call using NULL/Undef function pointer.\n"; |
| return; |
| } |
| |
| // If this function is one of the memory manipulating functions built into |
| // libc, emulate it with pool calls as appropriate. |
| if (CF && CF->isDeclaration()) { |
| std::string Name = CF->getName(); |
| |
| if (Name == "free" || Name == "cfree") { |
| visitFreeCall(CS); |
| return; |
| } else if (Name == "malloc") { |
| visitMallocCall(CS); |
| return; |
| } else if (Name == "calloc") { |
| visitCallocCall(CS); |
| return; |
| } else if (Name == "realloc") { |
| visitReallocCall(CS); |
| return; |
| } else if (Name == "memalign" || Name == "posix_memalign") { |
| visitMemAlignCall(CS); |
| return; |
| } else if (Name == "strdup") { |
| visitStrdupCall(CS); |
| return; |
| } else if (Name == "valloc") { |
| errs() << "VALLOC USED BUT NOT HANDLED!\n"; |
| abort(); |
| } else if (unsigned PoolArgc = PAInfo.getNumInitialPoolArguments(Name)) { |
| visitRuntimeCheck(CS, PoolArgc); |
| return; |
| } else if (Name == "pthread_create") { |
| thread_creation_point = true; |
| |
| // |
| // Get DSNode representing the DSNode of the function pointer Value of |
| // the pthread_create call |
| // |
| DSNode* thread_callee_node = G->getNodeForValue(CS.getArgument(2)).getNode(); |
| if (!thread_callee_node) { |
| assert(0 && "apparently you need this code"); |
| FuncInfo *CFI = PAInfo.getFuncInfo(*CF); |
| thread_callee_node = G->getNodeForValue(CFI->MapValueToOriginal(CS.getArgument(2))).getNode(); |
| } |
| |
| // Fill in CF with the name of one of the functions in thread_callee_node |
| CF = const_cast<Function*>(dyn_cast<Function>(*thread_callee_node->globals_begin())); |
| } |
| } |
| |
| // |
| // 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. |
| // |
| DataStructures& Graphs = PAInfo.getGraphs(); |
| DSGraph::NodeMapTy NodeMapping; |
| Instruction *NewCall; |
| Value *NewCallee; |
| std::vector<const DSNode*> ArgNodes; |
| DSGraph *CalleeGraph; // The callee graph |
| |
| // For indirect callees, find any callee since all DS graphs have been |
| // merged. |
| if (CF) { // Direct calls are nice and simple. |
| DEBUG(errs() << " Handling direct call: " << *TheCall << "\n"); |
| |
| // |
| // Do not try to add pool handles to the function if it: |
| // a) Already calls a cloned function; or |
| // b) Calls a function which was never cloned. |
| // |
| // For such a call, just replace any arguments that take original functions |
| // with their cloned function poiner values. |
| // |
| FuncInfo *CFI = PAInfo.getFuncInfo(*CF); |
| if (CFI == 0 || CFI->Clone == 0) { // Nothing to transform... |
| visitInstruction(*TheCall); |
| return; |
| } |
| |
| // |
| // Oh, dear. We must add pool descriptors to this direct call. |
| // |
| NewCallee = CFI->Clone; |
| ArgNodes = CFI->ArgNodes; |
| |
| assert ((Graphs.hasDSGraph (*CF)) && "Function has no ECGraph!\n"); |
| CalleeGraph = Graphs.getDSGraph(*CF); |
| } else { |
| DEBUG(errs() << " Handling indirect call: " << *TheCall << "\n"); |
| DSGraph *G = Graphs.getGlobalsGraph(); |
| DSGraph::ScalarMapTy& SM = G->getScalarMap(); |
| |
| // Here we fill in CF with one of the possible called functions. Because we |
| // merged together all of the arguments to all of the functions in the |
| // equivalence set, it doesn't really matter which one we pick. |
| // (If the function was cloned, we have to map the cloned call instruction |
| // in CS back to the original call instruction.) |
| Instruction *OrigInst = |
| cast<Instruction>(getOldValueIfAvailable(CS.getInstruction())); |
| |
| // |
| // Attempt to get one of the function targets of this indirect call site by |
| // looking at the call graph constructed by the points-to analysis. Be |
| // sure to use the original call site from the original function; the |
| // points-to analysis has no information on the clones we've created. |
| // |
| // Also, look for the target that has the greatest number of arguments that |
| // have associated DSNodes. This ensures that we pass the maximum number |
| // of pools possible and prevents us from eliding a pool because we're |
| // examining a target that doesn't need it. |
| // |
| const DSCallGraph & callGraph = Graphs.getCallGraph(); |
| |
| DSCallGraph::callee_iterator I = callGraph.callee_begin(OrigInst); |
| for (; I != callGraph.callee_end(OrigInst); ++I) { |
| for(DSCallGraph::scc_iterator sccii = callGraph.scc_begin(*I), |
| sccee = callGraph.scc_end(*I); sccii != sccee; ++sccii){ |
| if(SM.find(SM.getLeaderForGlobal(*sccii)) == SM.end()) |
| continue; |
| // |
| // Get the information for this function. Since this is coming from |
| // DSA, it should be an original function. |
| // |
| // This call site calls a function, that is not defined in this module |
| if (!(Graphs.hasDSGraph(**sccii))) return; |
| |
| // For all other cases Func Info must exist. |
| PAInfo.getFuncInfo(**sccii); |
| |
| // |
| // If this target takes more DSNodes than the last one we found, then |
| // make *this* target our canonical target. |
| // |
| CF = *sccii; |
| break; |
| } |
| } |
| if(!CF){ |
| const Function *F1 = OrigInst->getParent()->getParent(); |
| F1 = callGraph.sccLeader(&*F1); |
| |
| for(DSCallGraph::scc_iterator sccii = callGraph.scc_begin(F1), |
| sccee = callGraph.scc_end(F1); sccii != sccee; ++sccii){ |
| if(SM.find(SM.getLeaderForGlobal(*sccii)) == SM.end()) |
| continue; |
| // |
| // Get the information for this function. Since this is coming from DSA, |
| // it should be an original function. |
| // |
| // This call site calls a function, that is not defined in this module |
| if (!(Graphs.hasDSGraph(**sccii))) return; |
| // For all other cases Func Info must exist. |
| PAInfo.getFuncInfo(**sccii); |
| |
| // |
| // If this target takes more DSNodes than the last one we found, then |
| // make *this* target our canonical target. |
| // |
| CF = *sccii; |
| } |
| } |
| |
| // Assuming the call graph is always correct. And if the call graph reports, |
| // no callees, we can assume that it is right. |
| // |
| // If we didn't find the callee in the constructed call graph, try |
| // checking in the DSNode itself. |
| // This isn't ideal as it means that this call site didn't have inlining |
| // happen. |
| // |
| |
| // |
| // If we still haven't been able to find a target function of the call site |
| // to transform, do nothing. |
| // |
| // One may be tempted to think that we should always have at least one |
| // target, but this is not true. There are perfectly acceptable (but |
| // strange) programs for which no function targets exist. Function |
| // pointers loaded from undef values, for example, will have no targets. |
| // |
| if (!CF) return; |
| |
| // |
| // It's possible that this program has indirect call targets that are |
| // not defined in this module. Do not transformation for such functions. |
| // |
| if (!(Graphs.hasDSGraph(*CF))) return; |
| |
| // |
| // Get the common graph for the set of functions this call may invoke. |
| // |
| assert ((Graphs.hasDSGraph(*CF)) && "Function has no DSGraph!\n"); |
| CalleeGraph = Graphs.getDSGraph(*CF); |
| |
| #ifndef NDEBUG |
| // Verify that all potential callees at call site have the same DS graph. |
| DSCallGraph::callee_iterator E = Graphs.getCallGraph().callee_end(OrigInst); |
| for (; I != E; ++I) { |
| const Function * F = *I; |
| assert (F); |
| if (!(F)->isDeclaration()) |
| assert(CalleeGraph == Graphs.getDSGraph(**I) && |
| "Callees at call site do not have a common graph!"); |
| } |
| #endif |
| |
| // Find the DS nodes for the arguments that need to be added, if any. |
| FuncInfo *CFI = PAInfo.getFuncInfo(*CF); |
| assert(CFI && "No function info for callee at indirect call?"); |
| ArgNodes = CFI->ArgNodes; |
| |
| if (ArgNodes.empty()) |
| return; // No arguments to add? Transformation is a noop! |
| |
| // Cast the function pointer to an appropriate type! |
| std::vector<Type*> ArgTys(ArgNodes.size(), |
| PoolAllocate::PoolDescPtrTy); |
| for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); |
| I != E; ++I) |
| ArgTys.push_back((*I)->getType()); |
| |
| FunctionType *FTy = FunctionType::get(TheCall->getType(), ArgTys, false); |
| PointerType *PFTy = PointerType::getUnqual(FTy); |
| |
| // If there are any pool arguments cast the func ptr to the right type. |
| NewCallee = CastInst::CreatePointerCast(CS.getCalledValue(), PFTy, "tmp", TheCall); |
| } |
| |
| // |
| // FIXME: Why do we disable strict checking when calling the |
| // DSGraph::computeNodeMapping() method? |
| // |
| Function::const_arg_iterator FAI = CF->arg_begin(), E = CF->arg_end(); |
| CallSite::arg_iterator AI = CS.arg_begin() + (thread_creation_point ? 3 : 0); |
| CallSite::arg_iterator AE = CS.arg_end(); |
| for ( ; FAI != E && AI != AE; ++FAI, ++AI) |
| if (!isa<Constant>(*AI)) { |
| DSGraph::computeNodeMapping(CalleeGraph->getNodeForValue(FAI), |
| getDSNodeHFor(*AI), NodeMapping, false); |
| } |
| |
| //assert(AI == AE && "Varargs calls not handled yet!"); |
| |
| // Map the return value as well... |
| if (isa<PointerType>(TheCall->getType())) |
| DSGraph::computeNodeMapping(CalleeGraph->getReturnNodeFor(*CF), |
| getDSNodeHFor(TheCall), NodeMapping, false); |
| |
| // This code seems redundant (and crashes occasionally) |
| // There is no reason to map globals here, since they are not passed as |
| // arguments |
| |
| // // Map the nodes that are pointed to by globals. |
| // DSScalarMap &CalleeSM = CalleeGraph->getScalarMap(); |
| // for (DSScalarMap::global_iterator GI = G.getScalarMap().global_begin(), |
| // E = G.getScalarMap().global_end(); GI != E; ++GI) |
| // if (CalleeSM.count(*GI)) |
| // DSGraph::computeNodeMapping(CalleeGraph->getNodeForValue(*GI), |
| // getDSNodeHFor(*GI), |
| // NodeMapping, false); |
| |
| // |
| // Okay, now that we have established our mapping, we can figure out which |
| // pool descriptors to pass in... |
| // |
| // Note: |
| // There used to be code here that would create a new pool before the |
| // function call and destroy it after the function call. This could would |
| // get triggered if bounds checking was disbled or the DSNode for the |
| // argument was an array value. |
| // |
| // I believe that code was incorrect; an argument may have a NULL pool handle |
| // (i.e., no pool handle) because the pool allocation heuristic used simply |
| // decided not to assign that value a pool. The argument may alias data |
| // that should not be freed after the function call is complete, so calling |
| // pooldestroy() after the call would free data, causing dangling pointer |
| // dereference errors. |
| // |
| std::vector<Value*> Args; |
| for (unsigned i = 0, e = ArgNodes.size(); i != e; ++i) { |
| Value *ArgVal = Constant::getNullValue(PoolAllocate::PoolDescPtrTy); |
| if (NodeMapping.count(ArgNodes[i])) { |
| if (DSNode *LocalNode = NodeMapping[ArgNodes[i]].getNode()) |
| if (FI.PoolDescriptors.count(LocalNode)) |
| ArgVal = FI.PoolDescriptors.find(LocalNode)->second; |
| } |
| Args.push_back(ArgVal); |
| } |
| |
| // Add the rest of the arguments unless we're a thread creation point, in which case we only need the pools |
| if(!thread_creation_point) |
| Args.insert(Args.end(), CS.arg_begin(), CS.arg_end()); |
| |
| // |
| // There are circumstances where a function is casted to another type and |
| // then called (que horible). We need to perform a similar cast if the |
| // type doesn't match the number of arguments. |
| // |
| if (Function * NewFunction = dyn_cast<Function>(NewCallee)) { |
| FunctionType * NewCalleeType = NewFunction->getFunctionType(); |
| if (NewCalleeType->getNumParams() != Args.size()) { |
| std::vector<Type *> Types; |
| Type * FuncTy = FunctionType::get (NewCalleeType->getReturnType(), |
| Types, |
| true); |
| FuncTy = PointerType::getUnqual (FuncTy); |
| NewCallee = new BitCastInst (NewCallee, FuncTy, "", TheCall); |
| } |
| } |
| |
| std::string Name = TheCall->getName(); TheCall->setName(""); |
| |
| if(thread_creation_point) { |
| Module *M = CS.getInstruction()->getParent()->getParent()->getParent(); |
| Value* pthread_replacement = M->getFunction("poolalloc_pthread_create"); |
| std::vector<Value*> thread_args; |
| |
| //Push back original thread arguments through the callee |
| thread_args.push_back(CS.getArgument(0)); |
| thread_args.push_back(CS.getArgument(1)); |
| thread_args.push_back(CS.getArgument(2)); |
| |
| //Push back the integer argument saying how many uses there are |
| thread_args.push_back(Constant::getIntegerValue(llvm::Type::getInt32Ty(M->getContext()),APInt(32,Args.size()))); |
| thread_args.insert(thread_args.end(),Args.begin(),Args.end()); |
| thread_args.push_back(CS.getArgument(3)); |
| |
| //Make the thread creation call |
| NewCall = CallInst::Create(pthread_replacement, |
| thread_args, |
| Name,TheCall); |
| } |
| else if (InvokeInst *II = dyn_cast<InvokeInst>(TheCall)) { |
| NewCall = InvokeInst::Create (NewCallee, II->getNormalDest(), |
| II->getUnwindDest(), |
| Args, Name, TheCall); |
| } else { |
| NewCall = CallInst::Create (NewCallee, Args, Name, |
| TheCall); |
| } |
| |
| // Add all of the uses of the pool descriptor |
| for (unsigned i = 0, e = ArgNodes.size(); i != e; ++i) |
| AddPoolUse(*NewCall, Args[i], PoolUses); |
| |
| TheCall->replaceAllUsesWith(NewCall); |
| DEBUG(errs() << " Result Call: " << *NewCall << "\n"); |
| |
| if (!TheCall->getType()->isVoidTy()) { |
| // If we are modifying the original function, update the DSGraph... |
| DSGraph::ScalarMapTy &SM = G->getScalarMap(); |
| DSGraph::ScalarMapTy::iterator CII = SM.find(TheCall); |
| if (CII != SM.end()) { |
| SM[NewCall] = CII->second; |
| SM.erase(CII); // Destroy the CallInst |
| } else if (!FI.NewToOldValueMap.empty()) { |
| // Otherwise, if this is a clone, update the NewToOldValueMap with the new |
| // CI return value. |
| UpdateNewToOldValueMap(TheCall, NewCall); |
| } |
| } else if (!FI.NewToOldValueMap.empty()) { |
| UpdateNewToOldValueMap(TheCall, NewCall); |
| } |
| |
| // |
| // Copy over the calling convention and attributes of the original call |
| // instruction to the new call instruction. |
| // |
| CallSite(NewCall).setCallingConv(CallSite(TheCall).getCallingConv()); |
| |
| TheCall->eraseFromParent(); |
| visitInstruction(*NewCall); |
| } |
| |
| // |
| // visitInstruction - For all instructions in the transformed function bodies, |
| // replace any references to the original calls with references to the |
| // transformed calls. Many instructions can "take the address of" a function, |
| // and we must make sure to catch each of these uses, and transform it into a |
| // reference to the new, transformed, function. |
| // FIXME: Don't rename uses of function names that escape |
| // FIXME: Special-case when external user is pthread_create (or similar)? |
| // |
| void FuncTransform::visitInstruction(Instruction &I) { |
| for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) |
| if (Function *clonedFunc = retCloneIfFunc(I.getOperand(i))) { |
| Constant *CF = clonedFunc; |
| I.setOperand(i, ConstantExpr::getPointerCast(CF, I.getOperand(i)->getType())); |
| } |
| } |