lib/Analysis/MemoryBuiltins.cpp

   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"
  20 using 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.
  28 bool llvm::isMalloc(const Value *I) {
  29   return extractMallocCall(I) || extractMallocCallFromBitCast(I);
  30 }
  31
  32 static 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.
  58 const CallInst *llvm::extractMallocCall(const Value *I) {
  59   const CallInst *CI = dyn_cast<CallInst>(I);
  60   return (isMallocCall(CI)) ? CI : NULL;
  61 }
  62
  63 CallInst *llvm::extractMallocCall(Value *I) {
  64   CallInst *CI = dyn_cast<CallInst>(I);
  65   return (isMallocCall(CI)) ? CI : NULL;
  66 }
  67
  68 static 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.
  77 CallInst *llvm::extractMallocCallFromBitCast(Value *I) {
  78   BitCastInst *BCI = dyn_cast<BitCastInst>(I);
  79   return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0))
  80                                       : NULL;
  81 }
  82
  83 const 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.
  90 static bool isConstantOne(Value *val) {
  91   return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne();
  92 }
  93
  94 static 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.
 181 CallInst *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
 194 const 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.
 210 const 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.
 237 const 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.
 247 Value *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()
 257 bool 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 }