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 static bool isArrayMallocHelper(const CallInst *CI, LLVMContext &Context,
  92                                 const TargetData* TD) {
  93   if (!CI)
  94     return false;
  95
  96   const Type* T = getMallocAllocatedType(CI);
  97
  98   // We can only indentify an array malloc if we know the type of the malloc
  99   // call.
 100   if (!T) return false;
 101
 102   Value* MallocArg = CI->getOperand(1);
 103   Constant *ElementSize = ConstantExpr::getSizeOf(T);
 104   ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize,
 105                                                 MallocArg->getType());
 106   Constant *FoldedElementSize = ConstantFoldConstantExpression(
 107                                        cast<ConstantExpr>(ElementSize),
 108                                        Context, TD);
 109
 110
 111   if (isa<ConstantExpr>(MallocArg))
 112     return (MallocArg != ElementSize);
 113
 114   BinaryOperator *BI = dyn_cast<BinaryOperator>(MallocArg);
 115   if (!BI)
 116     return false;
 117
 118   if (BI->getOpcode() == Instruction::Mul)
 119     // ArraySize * ElementSize
 120     if (BI->getOperand(1) == ElementSize ||
 121         (FoldedElementSize && BI->getOperand(1) == FoldedElementSize))
 122       return true;
 123
 124   // TODO: Detect case where MallocArg mul has been transformed to shl.
 125
 126   return false;
 127 }
 128
 129 /// isArrayMalloc - Returns the corresponding CallInst if the instruction
 130 /// matches the malloc call IR generated by CallInst::CreateMalloc().  This
 131 /// means that it is a malloc call with one bitcast use AND the malloc call's
 132 /// size argument is:
 133 ///  1. a constant not equal to the size of the malloced type
 134 /// or
 135 ///  2. the result of a multiplication by the size of the malloced type
 136 /// Otherwise it returns NULL.
 137 /// The unique bitcast is needed to determine the type/size of the array
 138 /// allocation.
 139 CallInst* llvm::isArrayMalloc(Value* I, LLVMContext &Context,
 140                               const TargetData* TD) {
 141   CallInst *CI = extractMallocCall(I);
 142   return (isArrayMallocHelper(CI, Context, TD)) ? CI : NULL;
 143 }
 144
 145 const CallInst* llvm::isArrayMalloc(const Value* I, LLVMContext &Context,
 146                                     const TargetData* TD) {
 147   const CallInst *CI = extractMallocCall(I);
 148   return (isArrayMallocHelper(CI, Context, TD)) ? CI : NULL;
 149 }
 150
 151 /// getMallocType - Returns the PointerType resulting from the malloc call.
 152 /// This PointerType is the result type of the call's only bitcast use.
 153 /// If there is no unique bitcast use, then return NULL.
 154 const PointerType* llvm::getMallocType(const CallInst* CI) {
 155   assert(isMalloc(CI) && "GetMallocType and not malloc call");
 156
 157   const BitCastInst* BCI = NULL;
 158
 159   // Determine if CallInst has a bitcast use.
 160   for (Value::use_const_iterator UI = CI->use_begin(), E = CI->use_end();
 161        UI != E; )
 162     if ((BCI = dyn_cast<BitCastInst>(cast<Instruction>(*UI++))))
 163       break;
 164
 165   // Malloc call has 1 bitcast use and no other uses, so type is the bitcast's
 166   // destination type.
 167   if (BCI && CI->hasOneUse())
 168     return cast<PointerType>(BCI->getDestTy());
 169
 170   // Malloc call was not bitcast, so type is the malloc function's return type.
 171   if (!BCI)
 172     return cast<PointerType>(CI->getType());
 173
 174   // Type could not be determined.
 175   return NULL;
 176 }
 177
 178 /// getMallocAllocatedType - Returns the Type allocated by malloc call. This
 179 /// Type is the result type of the call's only bitcast use. If there is no
 180 /// unique bitcast use, then return NULL.
 181 const Type* llvm::getMallocAllocatedType(const CallInst* CI) {
 182   const PointerType* PT = getMallocType(CI);
 183   return PT ? PT->getElementType() : NULL;
 184 }
 185
 186 /// isSafeToGetMallocArraySize - Returns true if the array size of a malloc can
 187 /// be determined.  It can be determined in these 3 cases of malloc codegen:
 188 /// 1. non-array malloc: The malloc's size argument is a constant and equals the ///    size of the type being malloced.
 189 /// 2. array malloc: This is a malloc call with one bitcast use AND the malloc
 190 ///    call's size argument is a constant multiple of the size of the malloced
 191 ///    type.
 192 /// 3. array malloc: This is a malloc call with one bitcast use AND the malloc
 193 ///    call's size argument is the result of a multiplication by the size of the
 194 ///    malloced type.
 195 /// Otherwise returns false.
 196 static bool isSafeToGetMallocArraySize(const CallInst *CI,
 197                                        LLVMContext &Context,
 198                                        const TargetData* TD) {
 199   if (!CI)
 200     return false;
 201
 202   // Type must be known to determine array size.
 203   const Type* T = getMallocAllocatedType(CI);
 204   if (!T) return false;
 205
 206   Value* MallocArg = CI->getOperand(1);
 207   Constant *ElementSize = ConstantExpr::getSizeOf(T);
 208   ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize,
 209                                                 MallocArg->getType());
 210
 211   // First, check if it is a non-array malloc.
 212   if (isa<ConstantExpr>(MallocArg) && (MallocArg == ElementSize))
 213     return true;
 214
 215   // Second, check if it can be determined that this is an array malloc.
 216   return isArrayMallocHelper(CI, Context, TD);
 217 }
 218
 219 /// isConstantOne - Return true only if val is constant int 1.
 220 static bool isConstantOne(Value *val) {
 221   return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne();
 222 }
 223
 224 /// getMallocArraySize - Returns the array size of a malloc call.  For array
 225 /// mallocs, the size is computated in 1 of 3 ways:
 226 ///  1. If the element type is of size 1, then array size is the argument to
 227 ///     malloc.
 228 ///  2. Else if the malloc's argument is a constant, the array size is that
 229 ///     argument divided by the element type's size.
 230 ///  3. Else the malloc argument must be a multiplication and the array size is
 231 ///     the first operand of the multiplication.
 232 /// For non-array mallocs, the computed size is constant 1.
 233 /// This function returns NULL for all mallocs whose array size cannot be
 234 /// determined.
 235 Value* llvm::getMallocArraySize(CallInst* CI, LLVMContext &Context,
 236                                 const TargetData* TD) {
 237   if (!isSafeToGetMallocArraySize(CI, Context, TD))
 238     return NULL;
 239
 240   // Match CreateMalloc's use of constant 1 array-size for non-array mallocs.
 241   if (!isArrayMalloc(CI, Context, TD))
 242     return ConstantInt::get(CI->getOperand(1)->getType(), 1);
 243
 244   Value* MallocArg = CI->getOperand(1);
 245   assert(getMallocAllocatedType(CI) && "getMallocArraySize and no type");
 246   Constant *ElementSize = ConstantExpr::getSizeOf(getMallocAllocatedType(CI));
 247   ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize,
 248                                                 MallocArg->getType());
 249
 250   Constant* CO = dyn_cast<Constant>(MallocArg);
 251   BinaryOperator* BO = dyn_cast<BinaryOperator>(MallocArg);
 252   assert((isConstantOne(ElementSize) || CO || BO) &&
 253          "getMallocArraySize and malformed malloc IR");
 254
 255   if (isConstantOne(ElementSize))
 256     return MallocArg;
 257
 258   if (CO)
 259     return CO->getOperand(0);
 260
 261   // TODO: Detect case where MallocArg mul has been transformed to shl.
 262
 263   assert(BO && "getMallocArraySize not constant but not multiplication either");
 264   return BO->getOperand(0);
 265 }
 266
 267 //===----------------------------------------------------------------------===//
 268 //  free Call Utility Functions.
 269 //
 270
 271 /// isFreeCall - Returns true if the the value is a call to the builtin free()
 272 bool llvm::isFreeCall(const Value* I) {
 273   const CallInst *CI = dyn_cast<CallInst>(I);
 274   if (!CI)
 275     return false;
 276
 277   const Module* M = CI->getParent()->getParent()->getParent();
 278   Function *FreeFunc = M->getFunction("free");
 279
 280   if (CI->getOperand(0) != FreeFunc)
 281     return false;
 282
 283   // Check free prototype.
 284   // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
 285   // attribute will exist.
 286   const FunctionType *FTy = FreeFunc->getFunctionType();
 287   if (FTy->getReturnType() != Type::getVoidTy(M->getContext()))
 288     return false;
 289   if (FTy->getNumParams() != 1)
 290     return false;
 291   if (FTy->param_begin()->get() != Type::getInt8PtrTy(M->getContext()))
 292     return false;
 293
 294   return true;
 295 }