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/ADT/APInt.h"
  20 #include "llvm/Analysis/ConstantFolding.h"
  21 using namespace llvm;
  22
  23 //===----------------------------------------------------------------------===//
  24 //  malloc Call Utility Functions.
  25 //
  26
  27 /// isMalloc - Returns true if the the value is either a malloc call or a
  28 /// bitcast of the result of a malloc call.
  29 bool llvm::isMalloc(const Value* I) {
  30   return extractMallocCall(I) || extractMallocCallFromBitCast(I);
  31 }
  32
  33 static bool isMallocCall(const CallInst *CI) {
  34   if (!CI)
  35     return false;
  36
  37   const Module* M = CI->getParent()->getParent()->getParent();
  38   Function *MallocFunc = M->getFunction("malloc");
  39
  40   if (CI->getOperand(0) != MallocFunc)
  41     return false;
  42
  43   // Check malloc prototype.
  44   // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
  45   // attribute will exist.
  46   const FunctionType *FTy = MallocFunc->getFunctionType();
  47   if (FTy->getNumParams() != 1)
  48     return false;
  49   if (IntegerType *ITy = dyn_cast<IntegerType>(FTy->param_begin()->get())) {
  50     if (ITy->getBitWidth() != 32 && ITy->getBitWidth() != 64)
  51       return false;
  52     return true;
  53   }
  54
  55   return false;
  56 }
  57
  58 /// extractMallocCall - Returns the corresponding CallInst if the instruction
  59 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
  60 /// ignore InvokeInst here.
  61 const CallInst* llvm::extractMallocCall(const Value* I) {
  62   const CallInst *CI = dyn_cast<CallInst>(I);
  63   return (isMallocCall(CI)) ? CI : NULL;
  64 }
  65
  66 CallInst* llvm::extractMallocCall(Value* I) {
  67   CallInst *CI = dyn_cast<CallInst>(I);
  68   return (isMallocCall(CI)) ? CI : NULL;
  69 }
  70
  71 static bool isBitCastOfMallocCall(const BitCastInst* BCI) {
  72   if (!BCI)
  73     return false;
  74
  75   return isMallocCall(dyn_cast<CallInst>(BCI->getOperand(0)));
  76 }
  77
  78 /// extractMallocCallFromBitCast - Returns the corresponding CallInst if the
  79 /// instruction is a bitcast of the result of a malloc call.
  80 CallInst* llvm::extractMallocCallFromBitCast(Value* I) {
  81   BitCastInst *BCI = dyn_cast<BitCastInst>(I);
  82   return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0))
  83                                       : NULL;
  84 }
  85
  86 const CallInst* llvm::extractMallocCallFromBitCast(const Value* I) {
  87   const BitCastInst *BCI = dyn_cast<BitCastInst>(I);
  88   return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0))
  89                                       : NULL;
  90 }
  91
  92 /// isConstantOne - Return true only if val is constant int 1.
  93 static bool isConstantOne(Value *val) {
  94   return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne();
  95 }
  96
  97 static Value* isArrayMallocHelper(const CallInst *CI, LLVMContext &Context,
  98                                   const TargetData* TD) {
  99   if (!CI)
 100     return NULL;
 101
 102   // Type must be known to determine array size.
 103   const Type* T = getMallocAllocatedType(CI);
 104   if (!T)
 105     return NULL;
 106
 107   Value* MallocArg = CI->getOperand(1);
 108   ConstantExpr* CO = dyn_cast<ConstantExpr>(MallocArg);
 109   BinaryOperator* BO = dyn_cast<BinaryOperator>(MallocArg);
 110
 111   Constant* ElementSize = ConstantExpr::getSizeOf(T);
 112   ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize,
 113                                                 MallocArg->getType());
 114   Constant *FoldedElementSize =
 115    ConstantFoldConstantExpression(cast<ConstantExpr>(ElementSize), Context, TD);
 116
 117   // First, check if CI is a non-array malloc.
 118   if (CO && ((CO == ElementSize) ||
 119              (FoldedElementSize && (CO == FoldedElementSize))))
 120     // Match CreateMalloc's use of constant 1 array-size for non-array mallocs.
 121     return ConstantInt::get(MallocArg->getType(), 1);
 122
 123   // Second, check if CI is an array malloc whose array size can be determined.
 124   if (isConstantOne(ElementSize) ||
 125       (FoldedElementSize && isConstantOne(FoldedElementSize)))
 126     return MallocArg;
 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           (FoldedElementSize && (Op1 == FoldedElementSize)))
 152         // ArraySize * ElementSize
 153         return Op0;
 154       if ((Op0 == ElementSize) ||
 155           (FoldedElementSize && (Op0 == FoldedElementSize)))
 156         // ElementSize * ArraySize
 157         return Op1;
 158     }
 159     if (Opcode == Instruction::Shl) {
 160       ConstantInt* Op1CI = dyn_cast<ConstantInt>(Op1);
 161       if (!Op1CI) return NULL;
 162
 163       APInt Op1Int = Op1CI->getValue();
 164       unsigned Op1Width = Op1Int.getBitWidth();
 165       // check for overflow
 166       if (Op1Int.getActiveBits() > 64 || Op1Int.getZExtValue() > Op1Width)
 167         return NULL;
 168       Value* Op1Pow = ConstantInt::get(Context,
 169                                  APInt(Op1Width, 0).set(Op1Int.getZExtValue()));
 170
 171       if (Op0 == ElementSize || (FoldedElementSize && Op0 == FoldedElementSize))
 172         // ArraySize << log2(ElementSize)
 173         return Op1Pow;
 174       if (Op1Pow == ElementSize ||
 175           (FoldedElementSize && Op1Pow == FoldedElementSize))
 176         // ElementSize << log2(ArraySize)
 177         return Op0;
 178     }
 179   }
 180
 181   // We could not determine the malloc array size from MallocArg.
 182   return NULL;
 183 }
 184
 185 /// isArrayMalloc - Returns the corresponding CallInst if the instruction
 186 /// is a call to malloc whose array size can be determined and the array size
 187 /// is not constant 1.  Otherwise, return NULL.
 188 CallInst* llvm::isArrayMalloc(Value* I, LLVMContext &Context,
 189                               const TargetData* TD) {
 190   CallInst *CI = extractMallocCall(I);
 191   Value* ArraySize = isArrayMallocHelper(CI, Context, TD);
 192
 193   if (ArraySize &&
 194       ArraySize != ConstantInt::get(CI->getOperand(1)->getType(), 1))
 195     return CI;
 196
 197   // CI is a non-array malloc or we can't figure out that it is an array malloc.
 198   return NULL;
 199 }
 200
 201 const CallInst* llvm::isArrayMalloc(const Value* I, LLVMContext &Context,
 202                                     const TargetData* TD) {
 203   const CallInst *CI = extractMallocCall(I);
 204   Value* ArraySize = isArrayMallocHelper(CI, Context, TD);
 205
 206   if (ArraySize &&
 207       ArraySize != ConstantInt::get(CI->getOperand(1)->getType(), 1))
 208     return CI;
 209
 210   // CI is a non-array malloc or we can't figure out that it is an array malloc.
 211   return NULL;
 212 }
 213
 214 /// getMallocType - Returns the PointerType resulting from the malloc call.
 215 /// This PointerType is the result type of the call's only bitcast use.
 216 /// If there is no unique bitcast use, then return NULL.
 217 const PointerType* llvm::getMallocType(const CallInst* CI) {
 218   assert(isMalloc(CI) && "GetMallocType and not malloc call");
 219
 220   const BitCastInst* BCI = NULL;
 221
 222   // Determine if CallInst has a bitcast use.
 223   for (Value::use_const_iterator UI = CI->use_begin(), E = CI->use_end();
 224        UI != E; )
 225     if ((BCI = dyn_cast<BitCastInst>(cast<Instruction>(*UI++))))
 226       break;
 227
 228   // Malloc call has 1 bitcast use and no other uses, so type is the bitcast's
 229   // destination type.
 230   if (BCI && CI->hasOneUse())
 231     return cast<PointerType>(BCI->getDestTy());
 232
 233   // Malloc call was not bitcast, so type is the malloc function's return type.
 234   if (!BCI)
 235     return cast<PointerType>(CI->getType());
 236
 237   // Type could not be determined.
 238   return NULL;
 239 }
 240
 241 /// getMallocAllocatedType - Returns the Type allocated by malloc call. This
 242 /// Type is the result type of the call's only bitcast use. If there is no
 243 /// unique bitcast use, then return NULL.
 244 const Type* llvm::getMallocAllocatedType(const CallInst* CI) {
 245   const PointerType* PT = getMallocType(CI);
 246   return PT ? PT->getElementType() : NULL;
 247 }
 248
 249 /// getMallocArraySize - Returns the array size of a malloc call.  If the
 250 /// argument passed to malloc is a multiple of the size of the malloced type,
 251 /// then return that multiple.  For non-array mallocs, the multiple is
 252 /// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
 253 /// determined.
 254 Value* llvm::getMallocArraySize(CallInst* CI, LLVMContext &Context,
 255                                 const TargetData* TD) {
 256   return isArrayMallocHelper(CI, Context, TD);
 257 }
 258
 259 //===----------------------------------------------------------------------===//
 260 //  free Call Utility Functions.
 261 //
 262
 263 /// isFreeCall - Returns true if the the value is a call to the builtin free()
 264 bool llvm::isFreeCall(const Value* I) {
 265   const CallInst *CI = dyn_cast<CallInst>(I);
 266   if (!CI)
 267     return false;
 268
 269   const Module* M = CI->getParent()->getParent()->getParent();
 270   Function *FreeFunc = M->getFunction("free");
 271
 272   if (CI->getOperand(0) != FreeFunc)
 273     return false;
 274
 275   // Check free prototype.
 276   // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
 277   // attribute will exist.
 278   const FunctionType *FTy = FreeFunc->getFunctionType();
 279   if (FTy->getReturnType() != Type::getVoidTy(M->getContext()))
 280     return false;
 281   if (FTy->getNumParams() != 1)
 282     return false;
 283   if (FTy->param_begin()->get() != Type::getInt8PtrTy(M->getContext()))
 284     return false;
 285
 286   return true;
 287 }