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 using namespace llvm;
  20
  21 //===----------------------------------------------------------------------===//
  22 //  malloc Call Utility Functions.
  23 //
  24
  25 /// isMalloc - Returns true if the the value is either a malloc call or a
  26 /// bitcast of the result of a malloc call.
  27 bool llvm::isMalloc(Value* I) {
  28   return extractMallocCall(I) || extractMallocCallFromBitCast(I);
  29 }
  30
  31 bool llvm::isMalloc(const Value* I) {
  32   return extractMallocCall(I) || extractMallocCallFromBitCast(I);
  33 }
  34
  35 static bool isMallocCall(const CallInst *CI) {
  36   if (!CI)
  37     return false;
  38
  39   const Module* M = CI->getParent()->getParent()->getParent();
  40   Constant *MallocFunc = M->getFunction("malloc");
  41
  42   if (CI->getOperand(0) != MallocFunc)
  43     return false;
  44
  45   return true;
  46 }
  47
  48 /// extractMallocCall - Returns the corresponding CallInst if the instruction
  49 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
  50 /// ignore InvokeInst here.
  51 const CallInst* llvm::extractMallocCall(const Value* I) {
  52   const CallInst *CI = dyn_cast<CallInst>(I);
  53   return (isMallocCall(CI)) ? CI : NULL;
  54 }
  55
  56 CallInst* llvm::extractMallocCall(Value* I) {
  57   CallInst *CI = dyn_cast<CallInst>(I);
  58   return (isMallocCall(CI)) ? CI : NULL;
  59 }
  60
  61 static bool isBitCastOfMallocCall(const BitCastInst* BCI) {
  62   if (!BCI)
  63     return false;
  64
  65   return isMallocCall(dyn_cast<CallInst>(BCI->getOperand(0)));
  66 }
  67
  68 /// extractMallocCallFromBitCast - Returns the corresponding CallInst if the
  69 /// instruction is a bitcast of the result of a malloc call.
  70 CallInst* llvm::extractMallocCallFromBitCast(Value* I) {
  71   BitCastInst *BCI = dyn_cast<BitCastInst>(I);
  72   return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0))
  73                                       : NULL;
  74 }
  75
  76 const CallInst* llvm::extractMallocCallFromBitCast(const Value* I) {
  77   const BitCastInst *BCI = dyn_cast<BitCastInst>(I);
  78   return (isBitCastOfMallocCall(BCI)) ? cast<CallInst>(BCI->getOperand(0))
  79                                       : NULL;
  80 }
  81
  82 static bool isArrayMallocHelper(const CallInst *CI) {
  83   if (!CI)
  84     return false;
  85
  86   // Only identify array mallocs for mallocs with 1 bitcast use.  The unique
  87   // bitcast is needed to determine the type/size of the array allocation.
  88   if (!CI->hasOneUse()) return false;
  89
  90   for (Value::use_const_iterator UI = CI->use_begin(), E = CI->use_end();
  91        UI != E; )
  92     if (!isa<BitCastInst>(cast<Instruction>(*UI++)))
  93       return false;
  94
  95   // malloc arg
  96   Value* MallocArg = CI->getOperand(1);
  97   // element size
  98   const Type* T = getMallocAllocatedType(CI);
  99   if (!T) return false;
 100   Constant *ElementSize = ConstantExpr::getSizeOf(T);
 101
 102   if (isa<ConstantExpr>(MallocArg))
 103     return (MallocArg == ElementSize) ? false : true;
 104
 105   BinaryOperator *BI = dyn_cast<BinaryOperator>(MallocArg);
 106   if (!BI)
 107     return false;
 108
 109   if (BI->getOpcode() != Instruction::Mul)
 110     return false;
 111
 112   if (BI->getOperand(1) != ElementSize)
 113     return false;
 114
 115   return true;
 116 }
 117
 118 /// isArrayMalloc - Returns the corresponding CallInst if the instruction
 119 /// matches the malloc call IR generated by CallInst::CreateMalloc().  This
 120 /// means that it is a malloc call with one bitcast use AND the malloc call's
 121 /// size argument is:
 122 ///  1. a constant not equal to the malloc's allocated type
 123 /// or
 124 ///  2. the result of a multiplication by the malloc's allocated type
 125 /// Otherwise it returns NULL.
 126 /// The unique bitcast is needed to determine the type/size of the array
 127 /// allocation.
 128 CallInst* llvm::isArrayMalloc(Value* I) {
 129   CallInst *CI = extractMallocCall(I);
 130   return (isArrayMallocHelper(CI)) ? CI : NULL;
 131 }
 132
 133 const CallInst* llvm::isArrayMalloc(const Value* I) {
 134   const CallInst *CI = extractMallocCall(I);
 135   return (isArrayMallocHelper(CI)) ? CI : NULL;
 136 }
 137
 138 /// getMallocType - Returns the PointerType resulting from the malloc call.
 139 /// This PointerType is the result type of the call's only bitcast use.
 140 /// If there is no unique bitcast use, then return NULL.
 141 const PointerType* llvm::getMallocType(const CallInst* CI) {
 142   assert(isMalloc(CI) && "GetMallocType and not malloc call");
 143
 144   const BitCastInst* BCI = NULL;
 145
 146   // Determine type only if there is only 1 bitcast use of CI.
 147   if (CI->hasOneUse())
 148     for (Value::use_const_iterator UI = CI->use_begin(), E = CI->use_end();
 149          UI != E; )
 150       BCI = dyn_cast<BitCastInst>(cast<Instruction>(*UI++));
 151
 152   return BCI ? reinterpret_cast<const PointerType*>(BCI->getDestTy()) : NULL;
 153 }
 154
 155 /// getMallocAllocatedType - Returns the Type allocated by malloc call. This
 156 /// Type is the result type of the call's only bitcast use. If there is no
 157 /// unique bitcast use, then return NULL.
 158 const Type* llvm::getMallocAllocatedType(const CallInst* CI) {
 159   const PointerType* PT = getMallocType(CI);
 160   return PT ? PT->getElementType() : NULL;
 161 }
 162
 163 /// isConstantOne - Return true only if val is constant int 1.
 164 static bool isConstantOne(Value *val) {
 165   return isa<ConstantInt>(val) && cast<ConstantInt>(val)->isOne();
 166 }
 167
 168 /// getMallocArraySize - Returns the array size of a malloc call.  The array
 169 /// size is computated in 1 of 3 ways:
 170 ///  1. If the element type if of size 1, then array size is the argument to
 171 ///     malloc.
 172 ///  2. Else if the malloc's argument is a constant, the array size is that
 173 ///     argument divided by the element type's size.
 174 ///  3. Else the malloc argument must be a multiplication and the array size is
 175 ///     the first operand of the multiplication.
 176 /// This function returns constant 1 if:
 177 ///  1. The malloc call's allocated type cannot be determined.
 178 ///  2. IR wasn't created by a call to CallInst::CreateMalloc() with a non-NULL
 179 ///     ArraySize.
 180 Value* llvm::getMallocArraySize(CallInst* CI) {
 181   // Match CreateMalloc's use of constant 1 array-size for non-array mallocs.
 182   if (!isArrayMalloc(CI))
 183     return ConstantInt::get(CI->getOperand(1)->getType(), 1);
 184
 185   Value* MallocArg = CI->getOperand(1);
 186   assert(getMallocAllocatedType(CI) && "getMallocArraySize and no type");
 187   Constant *ElementSize = ConstantExpr::getSizeOf(getMallocAllocatedType(CI));
 188   ElementSize = ConstantExpr::getTruncOrBitCast(cast<Constant>(ElementSize),
 189                                                 MallocArg->getType());
 190
 191   Constant* CO = dyn_cast<Constant>(MallocArg);
 192   BinaryOperator* BO = dyn_cast<BinaryOperator>(MallocArg);
 193   assert((isConstantOne(ElementSize) || CO || BO) &&
 194          "getMallocArraySize and malformed malloc IR");
 195
 196   if (isConstantOne(ElementSize))
 197     return MallocArg;
 198
 199   if (CO)
 200     return ConstantExpr::getUDiv(CO, ElementSize);
 201
 202   assert(BO && "getMallocArraySize not constant but not multiplication either");
 203   return BO->getOperand(0);
 204 }