MemoryBuiltins.cpp revision 198892
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 Function *Callee = CI->getCalledFunction(); 37 if (Callee == 0 || !Callee->isDeclaration() || Callee->getName() != "malloc") 38 return false; 39 40 // Check malloc prototype. 41 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin 42 // attribute will exist. 43 const FunctionType *FTy = Callee->getFunctionType(); 44 if (FTy->getNumParams() != 1) 45 return false; 46 if (IntegerType *ITy = dyn_cast<IntegerType>(FTy->param_begin()->get())) { 47 if (ITy->getBitWidth() != 32 && ITy->getBitWidth() != 64) 48 return false; 49 return true; 50 } 51 52 return false; 53} 54 55/// extractMallocCall - Returns the corresponding CallInst if the instruction 56/// is a malloc call. Since CallInst::CreateMalloc() only creates calls, we 57/// ignore InvokeInst here. 58const CallInst *llvm::extractMallocCall(const Value *I) { 59 const CallInst *CI = dyn_cast<CallInst>(I); 60 return (isMallocCall(CI)) ? CI : NULL; 61} 62 63CallInst *llvm::extractMallocCall(Value *I) { 64 CallInst *CI = dyn_cast<CallInst>(I); 65 return (isMallocCall(CI)) ? CI : NULL; 66} 67 68static bool isBitCastOfMallocCall(const BitCastInst *BCI) { 69 if (!BCI) 70 return false; 71 72 return isMallocCall(dyn_cast<CallInst>(BCI->getOperand(0))); 73} 74 75/// extractMallocCallFromBitCast - Returns the corresponding CallInst if the 76/// instruction is a bitcast of the result of a malloc call. 77CallInst *llvm::extractMallocCallFromBitCast(Value *I) { 78 BitCastInst *BCI = dyn_cast<BitCastInst>(I); 79 return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0)) 80 : NULL; 81} 82 83const CallInst *llvm::extractMallocCallFromBitCast(const Value *I) { 84 const BitCastInst *BCI = dyn_cast<BitCastInst>(I); 85 return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0)) 86 : NULL; 87} 88 89/// isConstantOne - Return true only if val is constant int 1. 90static bool isConstantOne(Value *val) { 91 return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne(); 92} 93 94static Value *isArrayMallocHelper(const CallInst *CI, LLVMContext &Context, 95 const TargetData *TD) { 96 if (!CI) 97 return NULL; 98 99 // Type must be known to determine array size. 100 const Type *T = getMallocAllocatedType(CI); 101 if (!T) 102 return NULL; 103 104 Value *MallocArg = CI->getOperand(1); 105 ConstantExpr *CO = dyn_cast<ConstantExpr>(MallocArg); 106 BinaryOperator *BO = dyn_cast<BinaryOperator>(MallocArg); 107 108 Constant *ElementSize = ConstantExpr::getSizeOf(T); 109 ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize, 110 MallocArg->getType()); 111 Constant *FoldedElementSize = 112 ConstantFoldConstantExpression(cast<ConstantExpr>(ElementSize), Context, TD); 113 114 // First, check if CI is a non-array malloc. 115 if (CO && ((CO == ElementSize) || 116 (FoldedElementSize && (CO == FoldedElementSize)))) 117 // Match CreateMalloc's use of constant 1 array-size for non-array mallocs. 118 return ConstantInt::get(MallocArg->getType(), 1); 119 120 // Second, check if CI is an array malloc whose array size can be determined. 121 if (isConstantOne(ElementSize) || 122 (FoldedElementSize && isConstantOne(FoldedElementSize))) 123 return MallocArg; 124 125 if (!CO && !BO) 126 return NULL; 127 128 Value *Op0 = NULL; 129 Value *Op1 = NULL; 130 unsigned Opcode = 0; 131 if (CO && ((CO->getOpcode() == Instruction::Mul) || 132 (CO->getOpcode() == Instruction::Shl))) { 133 Op0 = CO->getOperand(0); 134 Op1 = CO->getOperand(1); 135 Opcode = CO->getOpcode(); 136 } 137 if (BO && ((BO->getOpcode() == Instruction::Mul) || 138 (BO->getOpcode() == Instruction::Shl))) { 139 Op0 = BO->getOperand(0); 140 Op1 = BO->getOperand(1); 141 Opcode = BO->getOpcode(); 142 } 143 144 // Determine array size if malloc's argument is the product of a mul or shl. 145 if (Op0) { 146 if (Opcode == Instruction::Mul) { 147 if ((Op1 == ElementSize) || 148 (FoldedElementSize && (Op1 == FoldedElementSize))) 149 // ArraySize * ElementSize 150 return Op0; 151 if ((Op0 == ElementSize) || 152 (FoldedElementSize && (Op0 == FoldedElementSize))) 153 // ElementSize * ArraySize 154 return Op1; 155 } 156 if (Opcode == Instruction::Shl) { 157 ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1); 158 if (!Op1CI) return NULL; 159 160 APInt Op1Int = Op1CI->getValue(); 161 uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1); 162 Value *Op1Pow = ConstantInt::get(Context, 163 APInt(Op1Int.getBitWidth(), 0).set(BitToSet)); 164 if (Op0 == ElementSize || (FoldedElementSize && Op0 == FoldedElementSize)) 165 // ArraySize << log2(ElementSize) 166 return Op1Pow; 167 if (Op1Pow == ElementSize || 168 (FoldedElementSize && Op1Pow == FoldedElementSize)) 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/// This PointerType is the result type of the call's only bitcast use. 209/// If there is no unique bitcast use, then return NULL. 210const PointerType *llvm::getMallocType(const CallInst *CI) { 211 assert(isMalloc(CI) && "GetMallocType and not malloc call"); 212 213 const BitCastInst *BCI = NULL; 214 215 // Determine if CallInst has a bitcast use. 216 for (Value::use_const_iterator UI = CI->use_begin(), E = CI->use_end(); 217 UI != E; ) 218 if ((BCI = dyn_cast<BitCastInst>(cast<Instruction>(*UI++)))) 219 break; 220 221 // Malloc call has 1 bitcast use and no other uses, so type is the bitcast's 222 // destination type. 223 if (BCI && CI->hasOneUse()) 224 return cast<PointerType>(BCI->getDestTy()); 225 226 // Malloc call was not bitcast, so type is the malloc function's return type. 227 if (!BCI) 228 return cast<PointerType>(CI->getType()); 229 230 // Type could not be determined. 231 return NULL; 232} 233 234/// getMallocAllocatedType - Returns the Type allocated by malloc call. This 235/// Type is the result type of the call's only bitcast use. If there is no 236/// unique bitcast use, then return NULL. 237const Type *llvm::getMallocAllocatedType(const CallInst *CI) { 238 const PointerType *PT = getMallocType(CI); 239 return PT ? PT->getElementType() : NULL; 240} 241 242/// getMallocArraySize - Returns the array size of a malloc call. If the 243/// argument passed to malloc is a multiple of the size of the malloced type, 244/// then return that multiple. For non-array mallocs, the multiple is 245/// constant 1. Otherwise, return NULL for mallocs whose array size cannot be 246/// determined. 247Value *llvm::getMallocArraySize(CallInst *CI, LLVMContext &Context, 248 const TargetData *TD) { 249 return isArrayMallocHelper(CI, Context, TD); 250} 251 252//===----------------------------------------------------------------------===// 253// free Call Utility Functions. 254// 255 256/// isFreeCall - Returns true if the the value is a call to the builtin free() 257bool llvm::isFreeCall(const Value *I) { 258 const CallInst *CI = dyn_cast<CallInst>(I); 259 if (!CI) 260 return false; 261 Function *Callee = CI->getCalledFunction(); 262 if (Callee == 0 || !Callee->isDeclaration() || Callee->getName() != "free") 263 return false; 264 265 // Check free prototype. 266 // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin 267 // attribute will exist. 268 const FunctionType *FTy = Callee->getFunctionType(); 269 if (!FTy->getReturnType()->isVoidTy()) 270 return false; 271 if (FTy->getNumParams() != 1) 272 return false; 273 if (FTy->param_begin()->get() != Type::getInt8PtrTy(Callee->getContext())) 274 return false; 275 276 return true; 277} 278