MemoryBuiltins.cpp revision f006b183e2d2bebcf6968d1dd7350397c95b0325
1//===------ MemoryBuiltins.cpp - Identify calls to memory builtins --------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This family of functions identifies calls to builtin functions that allocate 11// or free memory. 12// 13//===----------------------------------------------------------------------===// 14 15#include "llvm/Analysis/MemoryBuiltins.h" 16#include "llvm/Constants.h" 17#include "llvm/Instructions.h" 18#include "llvm/Module.h" 19#include "llvm/Analysis/ConstantFolding.h" 20using namespace llvm; 21 22//===----------------------------------------------------------------------===// 23// malloc Call Utility Functions. 24// 25 26/// isMalloc - Returns true if the the value is either a malloc call or a 27/// bitcast of the result of a malloc call. 28bool llvm::isMalloc(const Value* I) { 29 return extractMallocCall(I) || extractMallocCallFromBitCast(I); 30} 31 32static bool isMallocCall(const CallInst *CI) { 33 if (!CI) 34 return false; 35 36 const Module* M = CI->getParent()->getParent()->getParent(); 37 Function *MallocFunc = M->getFunction("malloc"); 38 39 if (CI->getOperand(0) != MallocFunc) 40 return false; 41 42 // Check malloc prototype. 43 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin 44 // attribute will exist. 45 const FunctionType *FTy = MallocFunc->getFunctionType(); 46 if (FTy->getNumParams() != 1) 47 return false; 48 if (IntegerType *ITy = dyn_cast<IntegerType>(FTy->param_begin()->get())) { 49 if (ITy->getBitWidth() != 32 && ITy->getBitWidth() != 64) 50 return false; 51 return true; 52 } 53 54 return false; 55} 56 57/// extractMallocCall - Returns the corresponding CallInst if the instruction 58/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 59/// ignore InvokeInst here. 60const CallInst* llvm::extractMallocCall(const Value* I) { 61 const CallInst *CI = dyn_cast<CallInst>(I); 62 return (isMallocCall(CI)) ? CI : NULL; 63} 64 65CallInst* llvm::extractMallocCall(Value* I) { 66 CallInst *CI = dyn_cast<CallInst>(I); 67 return (isMallocCall(CI)) ? CI : NULL; 68} 69 70static bool isBitCastOfMallocCall(const BitCastInst* BCI) { 71 if (!BCI) 72 return false; 73 74 return isMallocCall(dyn_cast<CallInst>(BCI->getOperand(0))); 75} 76 77/// extractMallocCallFromBitCast - Returns the corresponding CallInst if the 78/// instruction is a bitcast of the result of a malloc call. 79CallInst* llvm::extractMallocCallFromBitCast(Value* I) { 80 BitCastInst *BCI = dyn_cast<BitCastInst>(I); 81 return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0)) 82 : NULL; 83} 84 85const CallInst* llvm::extractMallocCallFromBitCast(const Value* I) { 86 const BitCastInst *BCI = dyn_cast<BitCastInst>(I); 87 return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0)) 88 : NULL; 89} 90 91static bool isArrayMallocHelper(const CallInst *CI, LLVMContext &Context, 92 const TargetData* TD) { 93 if (!CI) 94 return false; 95 96 const Type* T = getMallocAllocatedType(CI); 97 98 // We can only indentify an array malloc if we know the type of the malloc 99 // call. 100 if (!T) return false; 101 102 Value* MallocArg = CI->getOperand(1); 103 Constant *ElementSize = ConstantExpr::getSizeOf(T); 104 ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize, 105 MallocArg->getType()); 106 Constant *FoldedElementSize = ConstantFoldConstantExpression( 107 cast<ConstantExpr>(ElementSize), 108 Context, TD); 109 110 111 if (isa<ConstantExpr>(MallocArg)) 112 return (MallocArg != ElementSize); 113 114 BinaryOperator *BI = dyn_cast<BinaryOperator>(MallocArg); 115 if (!BI) 116 return false; 117 118 if (BI->getOpcode() == Instruction::Mul) 119 // ArraySize * ElementSize 120 if (BI->getOperand(1) == ElementSize || 121 (FoldedElementSize && BI->getOperand(1) == FoldedElementSize)) 122 return true; 123 124 // TODO: Detect case where MallocArg mul has been transformed to shl. 125 126 return false; 127} 128 129/// isArrayMalloc - Returns the corresponding CallInst if the instruction 130/// matches the malloc call IR generated by CallInst::CreateMalloc(). This 131/// means that it is a malloc call with one bitcast use AND the malloc call's 132/// size argument is: 133/// 1. a constant not equal to the size of the malloced type 134/// or 135/// 2. the result of a multiplication by the size of the malloced type 136/// Otherwise it returns NULL. 137/// The unique bitcast is needed to determine the type/size of the array 138/// allocation. 139CallInst* llvm::isArrayMalloc(Value* I, LLVMContext &Context, 140 const TargetData* TD) { 141 CallInst *CI = extractMallocCall(I); 142 return (isArrayMallocHelper(CI, Context, TD)) ? CI : NULL; 143} 144 145const CallInst* llvm::isArrayMalloc(const Value* I, LLVMContext &Context, 146 const TargetData* TD) { 147 const CallInst *CI = extractMallocCall(I); 148 return (isArrayMallocHelper(CI, Context, TD)) ? CI : NULL; 149} 150 151/// getMallocType - Returns the PointerType resulting from the malloc call. 152/// This PointerType is the result type of the call's only bitcast use. 153/// If there is no unique bitcast use, then return NULL. 154const PointerType* llvm::getMallocType(const CallInst* CI) { 155 assert(isMalloc(CI) && "GetMallocType and not malloc call"); 156 157 const BitCastInst* BCI = NULL; 158 159 // Determine if CallInst has a bitcast use. 160 for (Value::use_const_iterator UI = CI->use_begin(), E = CI->use_end(); 161 UI != E; ) 162 if ((BCI = dyn_cast<BitCastInst>(cast<Instruction>(*UI++)))) 163 break; 164 165 // Malloc call has 1 bitcast use and no other uses, so type is the bitcast's 166 // destination type. 167 if (BCI && CI->hasOneUse()) 168 return cast<PointerType>(BCI->getDestTy()); 169 170 // Malloc call was not bitcast, so type is the malloc function's return type. 171 if (!BCI) 172 return cast<PointerType>(CI->getType()); 173 174 // Type could not be determined. 175 return NULL; 176} 177 178/// getMallocAllocatedType - Returns the Type allocated by malloc call. This 179/// Type is the result type of the call's only bitcast use. If there is no 180/// unique bitcast use, then return NULL. 181const Type* llvm::getMallocAllocatedType(const CallInst* CI) { 182 const PointerType* PT = getMallocType(CI); 183 return PT ? PT->getElementType() : NULL; 184} 185 186/// isSafeToGetMallocArraySize - Returns true if the array size of a malloc can 187/// be determined. It can be determined in these 3 cases of malloc codegen: 188/// 1. non-array malloc: The malloc's size argument is a constant and equals the /// size of the type being malloced. 189/// 2. array malloc: This is a malloc call with one bitcast use AND the malloc 190/// call's size argument is a constant multiple of the size of the malloced 191/// type. 192/// 3. array malloc: This is a malloc call with one bitcast use AND the malloc 193/// call's size argument is the result of a multiplication by the size of the 194/// malloced type. 195/// Otherwise returns false. 196static bool isSafeToGetMallocArraySize(const CallInst *CI, 197 LLVMContext &Context, 198 const TargetData* TD) { 199 if (!CI) 200 return false; 201 202 // Type must be known to determine array size. 203 const Type* T = getMallocAllocatedType(CI); 204 if (!T) return false; 205 206 Value* MallocArg = CI->getOperand(1); 207 Constant *ElementSize = ConstantExpr::getSizeOf(T); 208 ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize, 209 MallocArg->getType()); 210 211 // First, check if it is a non-array malloc. 212 if (isa<ConstantExpr>(MallocArg) && (MallocArg == ElementSize)) 213 return true; 214 215 // Second, check if it can be determined that this is an array malloc. 216 return isArrayMallocHelper(CI, Context, TD); 217} 218 219/// isConstantOne - Return true only if val is constant int 1. 220static bool isConstantOne(Value *val) { 221 return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne(); 222} 223 224/// getMallocArraySize - Returns the array size of a malloc call. For array 225/// mallocs, the size is computated in 1 of 3 ways: 226/// 1. If the element type is of size 1, then array size is the argument to 227/// malloc. 228/// 2. Else if the malloc's argument is a constant, the array size is that 229/// argument divided by the element type's size. 230/// 3. Else the malloc argument must be a multiplication and the array size is 231/// the first operand of the multiplication. 232/// For non-array mallocs, the computed size is constant 1. 233/// This function returns NULL for all mallocs whose array size cannot be 234/// determined. 235Value* llvm::getMallocArraySize(CallInst* CI, LLVMContext &Context, 236 const TargetData* TD) { 237 if (!isSafeToGetMallocArraySize(CI, Context, TD)) 238 return NULL; 239 240 // Match CreateMalloc's use of constant 1 array-size for non-array mallocs. 241 if (!isArrayMalloc(CI, Context, TD)) 242 return ConstantInt::get(CI->getOperand(1)->getType(), 1); 243 244 Value* MallocArg = CI->getOperand(1); 245 assert(getMallocAllocatedType(CI) && "getMallocArraySize and no type"); 246 Constant *ElementSize = ConstantExpr::getSizeOf(getMallocAllocatedType(CI)); 247 ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize, 248 MallocArg->getType()); 249 250 Constant* CO = dyn_cast<Constant>(MallocArg); 251 BinaryOperator* BO = dyn_cast<BinaryOperator>(MallocArg); 252 assert((isConstantOne(ElementSize) || CO || BO) && 253 "getMallocArraySize and malformed malloc IR"); 254 255 if (isConstantOne(ElementSize)) 256 return MallocArg; 257 258 if (CO) 259 return CO->getOperand(0); 260 261 // TODO: Detect case where MallocArg mul has been transformed to shl. 262 263 assert(BO && "getMallocArraySize not constant but not multiplication either"); 264 return BO->getOperand(0); 265} 266 267//===----------------------------------------------------------------------===// 268// free Call Utility Functions. 269// 270 271/// isFreeCall - Returns true if the the value is a call to the builtin free() 272bool llvm::isFreeCall(const Value* I) { 273 const CallInst *CI = dyn_cast<CallInst>(I); 274 if (!CI) 275 return false; 276 277 const Module* M = CI->getParent()->getParent()->getParent(); 278 Function *FreeFunc = M->getFunction("free"); 279 280 if (CI->getOperand(0) != FreeFunc) 281 return false; 282 283 // Check free prototype. 284 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin 285 // attribute will exist. 286 const FunctionType *FTy = FreeFunc->getFunctionType(); 287 if (FTy->getReturnType() != Type::getVoidTy(M->getContext())) 288 return false; 289 if (FTy->getNumParams() != 1) 290 return false; 291 if (FTy->param_begin()->get() != Type::getInt8PtrTy(M->getContext())) 292 return false; 293 294 return true; 295} 296