lib/Analysis/MallocHelper.cpp

   1 //===-- MallocHelper.cpp - Functions to identify malloc calls -------------===//
   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.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/MallocHelper.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: this will be obsolete when nobuiltin attribute will exist.
  44   const FunctionType *FTy = MallocFunc->getFunctionType();
  45   if (FTy->getNumParams() != 1)
  46     return false;
  47   if (IntegerType *ITy = dyn_cast<IntegerType>(FTy->param_begin()->get())) {
  48     if (ITy->getBitWidth() != 32 && ITy->getBitWidth() != 64)
  49       return false;
  50     return true;
  51   }
  52
  53   return false;
  54 }
  55
  56 /// extractMallocCall - Returns the corresponding CallInst if the instruction
  57 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
  58 /// ignore InvokeInst here.
  59 const CallInst* llvm::extractMallocCall(const Value* I) {
  60   const CallInst *CI = dyn_cast<CallInst>(I);
  61   return (isMallocCall(CI)) ? CI : NULL;
  62 }
  63
  64 CallInst* llvm::extractMallocCall(Value* I) {
  65   CallInst *CI = dyn_cast<CallInst>(I);
  66   return (isMallocCall(CI)) ? CI : NULL;
  67 }
  68
  69 static bool isBitCastOfMallocCall(const BitCastInst* BCI) {
  70   if (!BCI)
  71     return false;
  72
  73   return isMallocCall(dyn_cast<CallInst>(BCI->getOperand(0)));
  74 }
  75
  76 /// extractMallocCallFromBitCast - Returns the corresponding CallInst if the
  77 /// instruction is a bitcast of the result of a malloc call.
  78 CallInst* llvm::extractMallocCallFromBitCast(Value* I) {
  79   BitCastInst *BCI = dyn_cast<BitCastInst>(I);
  80   return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0))
  81                                       : NULL;
  82 }
  83
  84 const CallInst* llvm::extractMallocCallFromBitCast(const Value* I) {
  85   const BitCastInst *BCI = dyn_cast<BitCastInst>(I);
  86   return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0))
  87                                       : NULL;
  88 }
  89
  90 static bool isArrayMallocHelper(const CallInst *CI, LLVMContext &Context,
  91                                 const TargetData* TD) {
  92   if (!CI)
  93     return false;
  94
  95   const Type* T = getMallocAllocatedType(CI);
  96
  97   // We can only indentify an array malloc if we know the type of the malloc
  98   // call.
  99   if (!T) return false;
 100
 101   Value* MallocArg = CI->getOperand(1);
 102   Constant *ElementSize = ConstantExpr::getSizeOf(T);
 103   ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize,
 104                                                 MallocArg->getType());
 105   Constant *FoldedElementSize = ConstantFoldConstantExpression(
 106                                        cast<ConstantExpr>(ElementSize),
 107                                        Context, TD);
 108
 109
 110   if (isa<ConstantExpr>(MallocArg))
 111     return (MallocArg != ElementSize);
 112
 113   BinaryOperator *BI = dyn_cast<BinaryOperator>(MallocArg);
 114   if (!BI)
 115     return false;
 116
 117   if (BI->getOpcode() == Instruction::Mul)
 118     // ArraySize * ElementSize
 119     if (BI->getOperand(1) == ElementSize ||
 120         (FoldedElementSize && BI->getOperand(1) == FoldedElementSize))
 121       return true;
 122
 123   // TODO: Detect case where MallocArg mul has been transformed to shl.
 124
 125   return false;
 126 }
 127
 128 /// isArrayMalloc - Returns the corresponding CallInst if the instruction
 129 /// matches the malloc call IR generated by CallInst::CreateMalloc().  This
 130 /// means that it is a malloc call with one bitcast use AND the malloc call's
 131 /// size argument is:
 132 ///  1. a constant not equal to the malloc's allocated type
 133 /// or
 134 ///  2. the result of a multiplication by the malloc's allocated type
 135 /// Otherwise it returns NULL.
 136 /// The unique bitcast is needed to determine the type/size of the array
 137 /// allocation.
 138 CallInst* llvm::isArrayMalloc(Value* I, LLVMContext &Context,
 139                               const TargetData* TD) {
 140   CallInst *CI = extractMallocCall(I);
 141   return (isArrayMallocHelper(CI, Context, TD)) ? CI : NULL;
 142 }
 143
 144 const CallInst* llvm::isArrayMalloc(const Value* I, LLVMContext &Context,
 145                                     const TargetData* TD) {
 146   const CallInst *CI = extractMallocCall(I);
 147   return (isArrayMallocHelper(CI, Context, TD)) ? CI : NULL;
 148 }
 149
 150 /// getMallocType - Returns the PointerType resulting from the malloc call.
 151 /// This PointerType is the result type of the call's only bitcast use.
 152 /// If there is no unique bitcast use, then return NULL.
 153 const PointerType* llvm::getMallocType(const CallInst* CI) {
 154   assert(isMalloc(CI) && "GetMallocType and not malloc call");
 155
 156   const BitCastInst* BCI = NULL;
 157
 158   // Determine if CallInst has a bitcast use.
 159   for (Value::use_const_iterator UI = CI->use_begin(), E = CI->use_end();
 160        UI != E; )
 161     if ((BCI = dyn_cast<BitCastInst>(cast<Instruction>(*UI++))))
 162       break;
 163
 164   // Malloc call has 1 bitcast use and no other uses, so type is the bitcast's
 165   // destination type.
 166   if (BCI && CI->hasOneUse())
 167     return cast<PointerType>(BCI->getDestTy());
 168
 169   // Malloc call was not bitcast, so type is the malloc function's return type.
 170   if (!BCI)
 171     return cast<PointerType>(CI->getType());
 172
 173   // Type could not be determined.
 174   return NULL;
 175 }
 176
 177 /// getMallocAllocatedType - Returns the Type allocated by malloc call. This
 178 /// Type is the result type of the call's only bitcast use. If there is no
 179 /// unique bitcast use, then return NULL.
 180 const Type* llvm::getMallocAllocatedType(const CallInst* CI) {
 181   const PointerType* PT = getMallocType(CI);
 182   return PT ? PT->getElementType() : NULL;
 183 }
 184
 185 /// isConstantOne - Return true only if val is constant int 1.
 186 static bool isConstantOne(Value *val) {
 187   return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne();
 188 }
 189
 190 /// getMallocArraySize - Returns the array size of a malloc call.  The array
 191 /// size is computated in 1 of 3 ways:
 192 ///  1. If the element type if of size 1, then array size is the argument to
 193 ///     malloc.
 194 ///  2. Else if the malloc's argument is a constant, the array size is that
 195 ///     argument divided by the element type's size.
 196 ///  3. Else the malloc argument must be a multiplication and the array size is
 197 ///     the first operand of the multiplication.
 198 /// This function returns constant 1 if:
 199 ///  1. The malloc call's allocated type cannot be determined.
 200 ///  2. IR wasn't created by a call to CallInst::CreateMalloc() with a non-NULL
 201 ///     ArraySize.
 202 Value* llvm::getMallocArraySize(CallInst* CI, LLVMContext &Context,
 203                                 const TargetData* TD) {
 204   // Match CreateMalloc's use of constant 1 array-size for non-array mallocs.
 205   if (!isArrayMalloc(CI, Context, TD))
 206     return ConstantInt::get(CI->getOperand(1)->getType(), 1);
 207
 208   Value* MallocArg = CI->getOperand(1);
 209   assert(getMallocAllocatedType(CI) && "getMallocArraySize and no type");
 210   Constant *ElementSize = ConstantExpr::getSizeOf(getMallocAllocatedType(CI));
 211   ElementSize = ConstantExpr::getTruncOrBitCast(ElementSize,
 212                                                 MallocArg->getType());
 213
 214   Constant* CO = dyn_cast<Constant>(MallocArg);
 215   BinaryOperator* BO = dyn_cast<BinaryOperator>(MallocArg);
 216   assert((isConstantOne(ElementSize) || CO || BO) &&
 217          "getMallocArraySize and malformed malloc IR");
 218
 219   if (isConstantOne(ElementSize))
 220     return MallocArg;
 221
 222   if (CO)
 223     return CO->getOperand(0);
 224
 225   // TODO: Detect case where MallocArg mul has been transformed to shl.
 226
 227   assert(BO && "getMallocArraySize not constant but not multiplication either");
 228   return BO->getOperand(0);
 229 }