X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FMemoryBuiltins.h;h=805a43dfb0705780e7e681c43ad66d6c40ce4db9;hb=92989cbe8452a9406f6e0d3c5709b5745f27158a;hp=6944564b8fa0722c5106149914edc5709f9c4c59;hpb=9d0b704e3ea418441001dac4d1a56c2c224cdbf5;p=oota-llvm.git diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h index 6944564b8fa..805a43dfb07 100644 --- a/include/llvm/Analysis/MemoryBuiltins.h +++ b/include/llvm/Analysis/MemoryBuiltins.h @@ -8,73 +8,259 @@ //===----------------------------------------------------------------------===// // // This family of functions identifies calls to builtin functions that allocate -// or free memory. +// or free memory. // //===----------------------------------------------------------------------===// #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H #define LLVM_ANALYSIS_MEMORYBUILTINS_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/Analysis/TargetFolder.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/InstVisitor.h" +#include "llvm/IR/Operator.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/DataTypes.h" + namespace llvm { class CallInst; class PointerType; -class TargetData; +class DataLayout; +class TargetLibraryInfo; class Type; class Value; + +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates or reallocates memory (either malloc, calloc, realloc, or strdup +/// like). +bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast = false); + +/// \brief Tests if a value is a call or invoke to a function that returns a +/// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions). +bool isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast = false); + +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates uninitialized memory (such as malloc). +bool isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast = false); + +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates zero-filled memory (such as calloc). +bool isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast = false); + +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates memory (either malloc, calloc, or strdup like). +bool isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast = false); + +/// \brief Tests if a value is a call or invoke to a library function that +/// reallocates memory (such as realloc). +bool isReallocLikeFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast = false); + +/// \brief Tests if a value is a call or invoke to a library function that +/// allocates memory and never returns null (such as operator new). +bool isOperatorNewLikeFn(const Value *V, const TargetLibraryInfo *TLI, + bool LookThroughBitCast = false); + //===----------------------------------------------------------------------===// // malloc Call Utility Functions. // -/// isMalloc - Returns true if the value is either a malloc call or a bitcast of -/// the result of a malloc call -bool isMalloc(const Value *I); - /// extractMallocCall - Returns the corresponding CallInst if the instruction /// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we /// ignore InvokeInst here. -const CallInst *extractMallocCall(const Value *I); -CallInst *extractMallocCall(Value *I); - -/// extractMallocCallFromBitCast - Returns the corresponding CallInst if the -/// instruction is a bitcast of the result of a malloc call. -const CallInst *extractMallocCallFromBitCast(const Value *I); -CallInst *extractMallocCallFromBitCast(Value *I); - -/// isArrayMalloc - Returns the corresponding CallInst if the instruction -/// is a call to malloc whose array size can be determined and the array size -/// is not constant 1. Otherwise, return NULL. -CallInst *isArrayMalloc(Value *I, const TargetData *TD); -const CallInst *isArrayMalloc(const Value *I, - const TargetData *TD); +const CallInst *extractMallocCall(const Value *I, const TargetLibraryInfo *TLI); +static inline CallInst *extractMallocCall(Value *I, + const TargetLibraryInfo *TLI) { + return const_cast(extractMallocCall((const Value*)I, TLI)); +} /// getMallocType - Returns the PointerType resulting from the malloc call. /// The PointerType depends on the number of bitcast uses of the malloc call: /// 0: PointerType is the malloc calls' return type. /// 1: PointerType is the bitcast's result type. /// >1: Unique PointerType cannot be determined, return NULL. -const PointerType *getMallocType(const CallInst *CI); +PointerType *getMallocType(const CallInst *CI, const TargetLibraryInfo *TLI); /// getMallocAllocatedType - Returns the Type allocated by malloc call. /// The Type depends on the number of bitcast uses of the malloc call: /// 0: PointerType is the malloc calls' return type. /// 1: PointerType is the bitcast's result type. /// >1: Unique PointerType cannot be determined, return NULL. -const Type *getMallocAllocatedType(const CallInst *CI); +Type *getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI); -/// getMallocArraySize - Returns the array size of a malloc call. If the +/// getMallocArraySize - Returns the array size of a malloc call. If the /// argument passed to malloc is a multiple of the size of the malloced type, /// then return that multiple. For non-array mallocs, the multiple is /// constant 1. Otherwise, return NULL for mallocs whose array size cannot be /// determined. -Value *getMallocArraySize(CallInst *CI, const TargetData *TD); - +Value *getMallocArraySize(CallInst *CI, const DataLayout &DL, + const TargetLibraryInfo *TLI, + bool LookThroughSExt = false); + +//===----------------------------------------------------------------------===// +// calloc Call Utility Functions. +// + +/// extractCallocCall - Returns the corresponding CallInst if the instruction +/// is a calloc call. +const CallInst *extractCallocCall(const Value *I, const TargetLibraryInfo *TLI); +static inline CallInst *extractCallocCall(Value *I, + const TargetLibraryInfo *TLI) { + return const_cast(extractCallocCall((const Value*)I, TLI)); +} + + //===----------------------------------------------------------------------===// // free Call Utility Functions. // -/// isFreeCall - Returns true if the the value is a call to the builtin free() -bool isFreeCall(const Value *I); +/// isFreeCall - Returns non-null if the value is a call to the builtin free() +const CallInst *isFreeCall(const Value *I, const TargetLibraryInfo *TLI); + +static inline CallInst *isFreeCall(Value *I, const TargetLibraryInfo *TLI) { + return const_cast(isFreeCall((const Value*)I, TLI)); +} + + +//===----------------------------------------------------------------------===// +// Utility functions to compute size of objects. +// + +/// \brief Compute the size of the object pointed by Ptr. Returns true and the +/// object size in Size if successful, and false otherwise. In this context, by +/// object we mean the region of memory starting at Ptr to the end of the +/// underlying object pointed to by Ptr. +/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas, +/// byval arguments, and global variables. +bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, + const TargetLibraryInfo *TLI, bool RoundToAlign = false); + +typedef std::pair SizeOffsetType; + +/// \brief Evaluate the size and offset of an object pointed to by a Value* +/// statically. Fails if size or offset are not known at compile time. +class ObjectSizeOffsetVisitor + : public InstVisitor { + + const DataLayout &DL; + const TargetLibraryInfo *TLI; + bool RoundToAlign; + unsigned IntTyBits; + APInt Zero; + SmallPtrSet SeenInsts; + + APInt align(APInt Size, uint64_t Align); + + SizeOffsetType unknown() { + return std::make_pair(APInt(), APInt()); + } + +public: + ObjectSizeOffsetVisitor(const DataLayout &DL, const TargetLibraryInfo *TLI, + LLVMContext &Context, bool RoundToAlign = false); + + SizeOffsetType compute(Value *V); + + bool knownSize(SizeOffsetType &SizeOffset) { + return SizeOffset.first.getBitWidth() > 1; + } + + bool knownOffset(SizeOffsetType &SizeOffset) { + return SizeOffset.second.getBitWidth() > 1; + } + + bool bothKnown(SizeOffsetType &SizeOffset) { + return knownSize(SizeOffset) && knownOffset(SizeOffset); + } + + // These are "private", except they can't actually be made private. Only + // compute() should be used by external users. + SizeOffsetType visitAllocaInst(AllocaInst &I); + SizeOffsetType visitArgument(Argument &A); + SizeOffsetType visitCallSite(CallSite CS); + SizeOffsetType visitConstantPointerNull(ConstantPointerNull&); + SizeOffsetType visitExtractElementInst(ExtractElementInst &I); + SizeOffsetType visitExtractValueInst(ExtractValueInst &I); + SizeOffsetType visitGEPOperator(GEPOperator &GEP); + SizeOffsetType visitGlobalAlias(GlobalAlias &GA); + SizeOffsetType visitGlobalVariable(GlobalVariable &GV); + SizeOffsetType visitIntToPtrInst(IntToPtrInst&); + SizeOffsetType visitLoadInst(LoadInst &I); + SizeOffsetType visitPHINode(PHINode&); + SizeOffsetType visitSelectInst(SelectInst &I); + SizeOffsetType visitUndefValue(UndefValue&); + SizeOffsetType visitInstruction(Instruction &I); +}; + +typedef std::pair SizeOffsetEvalType; + + +/// \brief Evaluate the size and offset of an object pointed to by a Value*. +/// May create code to compute the result at run-time. +class ObjectSizeOffsetEvaluator + : public InstVisitor { + + typedef IRBuilder BuilderTy; + typedef std::pair WeakEvalType; + typedef DenseMap CacheMapTy; + typedef SmallPtrSet PtrSetTy; + + const DataLayout &DL; + const TargetLibraryInfo *TLI; + LLVMContext &Context; + BuilderTy Builder; + IntegerType *IntTy; + Value *Zero; + CacheMapTy CacheMap; + PtrSetTy SeenVals; + bool RoundToAlign; + + SizeOffsetEvalType unknown() { + return std::make_pair(nullptr, nullptr); + } + SizeOffsetEvalType compute_(Value *V); + +public: + ObjectSizeOffsetEvaluator(const DataLayout &DL, const TargetLibraryInfo *TLI, + LLVMContext &Context, bool RoundToAlign = false); + SizeOffsetEvalType compute(Value *V); + + bool knownSize(SizeOffsetEvalType SizeOffset) { + return SizeOffset.first; + } + + bool knownOffset(SizeOffsetEvalType SizeOffset) { + return SizeOffset.second; + } + + bool anyKnown(SizeOffsetEvalType SizeOffset) { + return knownSize(SizeOffset) || knownOffset(SizeOffset); + } + + bool bothKnown(SizeOffsetEvalType SizeOffset) { + return knownSize(SizeOffset) && knownOffset(SizeOffset); + } + + // The individual instruction visitors should be treated as private. + SizeOffsetEvalType visitAllocaInst(AllocaInst &I); + SizeOffsetEvalType visitCallSite(CallSite CS); + SizeOffsetEvalType visitExtractElementInst(ExtractElementInst &I); + SizeOffsetEvalType visitExtractValueInst(ExtractValueInst &I); + SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP); + SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&); + SizeOffsetEvalType visitLoadInst(LoadInst &I); + SizeOffsetEvalType visitPHINode(PHINode &PHI); + SizeOffsetEvalType visitSelectInst(SelectInst &I); + SizeOffsetEvalType visitInstruction(Instruction &I); +}; } // End llvm namespace