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   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.
  60 const CallInst *llvm::extractMallocCall(const Value *I) {
  61   const CallInst *CI = dyn_cast<CallInst>(I);
  62   return (isMallocCall(CI)) ? CI : NULL;
  63 }
  64
  65 CallInst *llvm::extractMallocCall(Value *I) {
  66   CallInst *CI = dyn_cast<CallInst>(I);
  67   return (isMallocCall(CI)) ? CI : NULL;
  68 }
  69
  70 static 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.
  79 CallInst *llvm::extractMallocCallFromBitCast(Value *I) {
  80   BitCastInst *BCI = dyn_cast<BitCastInst>(I);
  81   return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0))
  82                                       : NULL;
  83 }
  84
  85 const 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
  91 /// isConstantOne - Return true only if val is constant int 1.
  92 static bool isConstantOne(Value *val) {
  93   return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne();
  94 }
  95
  96 static Value *isArrayMallocHelper(const CallInst *CI, LLVMContext &Context,
  97                                   const TargetData *TD) {
  98   if (!CI)
  99     return NULL;
 100
 101   // Type must be known to determine array size.
 102   const Type *T = getMallocAllocatedType(CI);
 103   if (!T)
 104     return NULL;
 105
 106   Value *MallocArg = CI->getOperand(1);
 107   ConstantExpr *CO = dyn_cast<ConstantExpr>(MallocArg);
 108   BinaryOperator *BO = dyn_cast<BinaryOperator>(MallocArg);
 109
 110   Constant *ElementSize = ConstantExpr::getSizeOf(T);
 111   ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize,
 112                                                 MallocArg->getType());
 113   Constant *FoldedElementSize =
 114    ConstantFoldConstantExpression(cast<ConstantExpr>(ElementSize), Context, TD);
 115
 116   // First, check if CI is a non-array malloc.
 117   if (CO && ((CO == ElementSize) ||
 118              (FoldedElementSize && (CO == FoldedElementSize))))
 119     // Match CreateMalloc's use of constant 1 array-size for non-array mallocs.
 120     return ConstantInt::get(MallocArg->getType(), 1);
 121
 122   // Second, check if CI is an array malloc whose array size can be determined.
 123   if (isConstantOne(ElementSize) ||
 124       (FoldedElementSize && isConstantOne(FoldedElementSize)))
 125     return MallocArg;
 126
 127   if (!CO && !BO)
 128     return NULL;
 129
 130   Value *Op0 = NULL;
 131   Value *Op1 = NULL;
 132   unsigned Opcode = 0;
 133   if (CO && ((CO->getOpcode() == Instruction::Mul) ||
 134              (CO->getOpcode() == Instruction::Shl))) {
 135     Op0 = CO->getOperand(0);
 136     Op1 = CO->getOperand(1);
 137     Opcode = CO->getOpcode();
 138   }
 139   if (BO && ((BO->getOpcode() == Instruction::Mul) ||
 140              (BO->getOpcode() == Instruction::Shl))) {
 141     Op0 = BO->getOperand(0);
 142     Op1 = BO->getOperand(1);
 143     Opcode = BO->getOpcode();
 144   }
 145
 146   // Determine array size if malloc's argument is the product of a mul or shl.
 147   if (Op0) {
 148     if (Opcode == Instruction::Mul) {
 149       if ((Op1 == ElementSize) ||
 150           (FoldedElementSize && (Op1 == FoldedElementSize)))
 151         // ArraySize * ElementSize
 152         return Op0;
 153       if ((Op0 == ElementSize) ||
 154           (FoldedElementSize && (Op0 == FoldedElementSize)))
 155         // ElementSize * ArraySize
 156         return Op1;
 157     }
 158     if (Opcode == Instruction::Shl) {
 159       ConstantInt *Op1CI = dyn_cast<ConstantInt>(Op1);
 160       if (!Op1CI) return NULL;
 161
 162       APInt Op1Int = Op1CI->getValue();
 163       uint64_t BitToSet = Op1Int.getLimitedValue(Op1Int.getBitWidth() - 1);
 164       Value *Op1Pow = ConstantInt::get(Context,
 165                                   APInt(Op1Int.getBitWidth(), 0).set(BitToSet));
 166       if (Op0 == ElementSize || (FoldedElementSize && Op0 == FoldedElementSize))
 167         // ArraySize << log2(ElementSize)
 168         return Op1Pow;
 169       if (Op1Pow == ElementSize ||
 170           (FoldedElementSize && Op1Pow == FoldedElementSize))
 171         // ElementSize << log2(ArraySize)
 172         return Op0;
 173     }
 174   }
 175
 176   // We could not determine the malloc array size from MallocArg.
 177   return NULL;
 178 }
 179
 180 /// isArrayMalloc - Returns the corresponding CallInst if the instruction
 181 /// is a call to malloc whose array size can be determined and the array size
 182 /// is not constant 1.  Otherwise, return NULL.
 183 CallInst *llvm::isArrayMalloc(Value *I, LLVMContext &Context,
 184                               const TargetData *TD) {
 185   CallInst *CI = extractMallocCall(I);
 186   Value *ArraySize = isArrayMallocHelper(CI, Context, TD);
 187
 188   if (ArraySize &&
 189       ArraySize != ConstantInt::get(CI->getOperand(1)->getType(), 1))
 190     return CI;
 191
 192   // CI is a non-array malloc or we can't figure out that it is an array malloc.
 193   return NULL;
 194 }
 195
 196 const CallInst *llvm::isArrayMalloc(const Value *I, LLVMContext &Context,
 197                                     const TargetData *TD) {
 198   const CallInst *CI = extractMallocCall(I);
 199   Value *ArraySize = isArrayMallocHelper(CI, Context, TD);
 200
 201   if (ArraySize &&
 202       ArraySize != ConstantInt::get(CI->getOperand(1)->getType(), 1))
 203     return CI;
 204
 205   // CI is a non-array malloc or we can't figure out that it is an array malloc.
 206   return NULL;
 207 }
 208
 209 /// getMallocType - Returns the PointerType resulting from the malloc call.
 210 /// This PointerType is the result type of the call's only bitcast use.
 211 /// If there is no unique bitcast use, then return NULL.
 212 const PointerType *llvm::getMallocType(const CallInst *CI) {
 213   assert(isMalloc(CI) && "GetMallocType and not malloc call");
 214
 215   const BitCastInst *BCI = NULL;
 216
 217   // Determine if CallInst has a bitcast use.
 218   for (Value::use_const_iterator UI = CI->use_begin(), E = CI->use_end();
 219        UI != E; )
 220     if ((BCI = dyn_cast<BitCastInst>(cast<Instruction>(*UI++))))
 221       break;
 222
 223   // Malloc call has 1 bitcast use and no other uses, so type is the bitcast's
 224   // destination type.
 225   if (BCI && CI->hasOneUse())
 226     return cast<PointerType>(BCI->getDestTy());
 227
 228   // Malloc call was not bitcast, so type is the malloc function's return type.
 229   if (!BCI)
 230     return cast<PointerType>(CI->getType());
 231
 232   // Type could not be determined.
 233   return NULL;
 234 }
 235
 236 /// getMallocAllocatedType - Returns the Type allocated by malloc call. This
 237 /// Type is the result type of the call's only bitcast use. If there is no
 238 /// unique bitcast use, then return NULL.
 239 const Type *llvm::getMallocAllocatedType(const CallInst *CI) {
 240   const PointerType *PT = getMallocType(CI);
 241   return PT ? PT->getElementType() : NULL;
 242 }
 243
 244 /// getMallocArraySize - Returns the array size of a malloc call.  If the
 245 /// argument passed to malloc is a multiple of the size of the malloced type,
 246 /// then return that multiple.  For non-array mallocs, the multiple is
 247 /// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
 248 /// determined.
 249 Value *llvm::getMallocArraySize(CallInst *CI, LLVMContext &Context,
 250                                 const TargetData *TD) {
 251   return isArrayMallocHelper(CI, Context, TD);
 252 }
 253
 254 //===----------------------------------------------------------------------===//
 255 //  free Call Utility Functions.
 256 //
 257
 258 /// isFreeCall - Returns true if the the value is a call to the builtin free()
 259 bool llvm::isFreeCall(const Value *I) {
 260   const CallInst *CI = dyn_cast<CallInst>(I);
 261   if (!CI)
 262     return false;
 263
 264   const Module *M = CI->getParent()->getParent()->getParent();
 265   Function *FreeFunc = M->getFunction("free");
 266
 267   if (CI->getOperand(0) != FreeFunc)
 268     return false;
 269
 270   // Check free prototype.
 271   // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
 272   // attribute will exist.
 273   const FunctionType *FTy = FreeFunc->getFunctionType();
 274   if (FTy->getReturnType() != Type::getVoidTy(M->getContext()))
 275     return false;
 276   if (FTy->getNumParams() != 1)
 277     return false;
 278   if (FTy->param_begin()->get() != Type::getInt8PtrTy(M->getContext()))
 279     return false;
 280
 281   return true;
 282 }