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