lib/Analysis/MallocFreeHelper.cpp

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