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