• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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/ADT/STLExtras.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/Analysis/TargetLibraryInfo.h"
19 #include "llvm/Analysis/ValueTracking.h"
20 #include "llvm/IR/DataLayout.h"
21 #include "llvm/IR/GlobalVariable.h"
22 #include "llvm/IR/Instructions.h"
23 #include "llvm/IR/Intrinsics.h"
24 #include "llvm/IR/Metadata.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/MathExtras.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include "llvm/Transforms/Utils/Local.h"
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "memory-builtins"
33 
34 enum AllocType : uint8_t {
35   OpNewLike          = 1<<0, // allocates; never returns null
36   MallocLike         = 1<<1 | OpNewLike, // allocates; may return null
37   CallocLike         = 1<<2, // allocates + bzero
38   ReallocLike        = 1<<3, // reallocates
39   StrDupLike         = 1<<4,
40   AllocLike          = MallocLike | CallocLike | StrDupLike,
41   AnyAlloc           = AllocLike | ReallocLike
42 };
43 
44 struct AllocFnsTy {
45   AllocType AllocTy;
46   unsigned NumParams;
47   // First and Second size parameters (or -1 if unused)
48   int FstParam, SndParam;
49 };
50 
51 // FIXME: certain users need more information. E.g., SimplifyLibCalls needs to
52 // know which functions are nounwind, noalias, nocapture parameters, etc.
53 static const std::pair<LibFunc::Func, AllocFnsTy> AllocationFnData[] = {
54   {LibFunc::malloc,              {MallocLike,  1, 0,  -1}},
55   {LibFunc::valloc,              {MallocLike,  1, 0,  -1}},
56   {LibFunc::Znwj,                {OpNewLike,   1, 0,  -1}}, // new(unsigned int)
57   {LibFunc::ZnwjRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new(unsigned int, nothrow)
58   {LibFunc::Znwm,                {OpNewLike,   1, 0,  -1}}, // new(unsigned long)
59   {LibFunc::ZnwmRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new(unsigned long, nothrow)
60   {LibFunc::Znaj,                {OpNewLike,   1, 0,  -1}}, // new[](unsigned int)
61   {LibFunc::ZnajRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new[](unsigned int, nothrow)
62   {LibFunc::Znam,                {OpNewLike,   1, 0,  -1}}, // new[](unsigned long)
63   {LibFunc::ZnamRKSt9nothrow_t,  {MallocLike,  2, 0,  -1}}, // new[](unsigned long, nothrow)
64   {LibFunc::msvc_new_int,         {OpNewLike,   1, 0,  -1}}, // new(unsigned int)
65   {LibFunc::msvc_new_int_nothrow, {MallocLike,  2, 0,  -1}}, // new(unsigned int, nothrow)
66   {LibFunc::msvc_new_longlong,         {OpNewLike,   1, 0,  -1}}, // new(unsigned long long)
67   {LibFunc::msvc_new_longlong_nothrow, {MallocLike,  2, 0,  -1}}, // new(unsigned long long, nothrow)
68   {LibFunc::msvc_new_array_int,         {OpNewLike,   1, 0,  -1}}, // new[](unsigned int)
69   {LibFunc::msvc_new_array_int_nothrow, {MallocLike,  2, 0,  -1}}, // new[](unsigned int, nothrow)
70   {LibFunc::msvc_new_array_longlong,         {OpNewLike,   1, 0,  -1}}, // new[](unsigned long long)
71   {LibFunc::msvc_new_array_longlong_nothrow, {MallocLike,  2, 0,  -1}}, // new[](unsigned long long, nothrow)
72   {LibFunc::calloc,              {CallocLike,  2, 0,   1}},
73   {LibFunc::realloc,             {ReallocLike, 2, 1,  -1}},
74   {LibFunc::reallocf,            {ReallocLike, 2, 1,  -1}},
75   {LibFunc::strdup,              {StrDupLike,  1, -1, -1}},
76   {LibFunc::strndup,             {StrDupLike,  2, 1,  -1}}
77   // TODO: Handle "int posix_memalign(void **, size_t, size_t)"
78 };
79 
80 
getCalledFunction(const Value * V,bool LookThroughBitCast)81 static Function *getCalledFunction(const Value *V, bool LookThroughBitCast) {
82   if (LookThroughBitCast)
83     V = V->stripPointerCasts();
84 
85   CallSite CS(const_cast<Value*>(V));
86   if (!CS.getInstruction())
87     return nullptr;
88 
89   if (CS.isNoBuiltin())
90     return nullptr;
91 
92   Function *Callee = CS.getCalledFunction();
93   if (!Callee || !Callee->isDeclaration())
94     return nullptr;
95   return Callee;
96 }
97 
98 /// Returns the allocation data for the given value if it's either a call to a
99 /// known allocation function, or a call to a function with the allocsize
100 /// attribute.
getAllocationData(const Value * V,AllocType AllocTy,const TargetLibraryInfo * TLI,bool LookThroughBitCast=false)101 static Optional<AllocFnsTy> getAllocationData(const Value *V, AllocType AllocTy,
102                                               const TargetLibraryInfo *TLI,
103                                               bool LookThroughBitCast = false) {
104   // Skip intrinsics
105   if (isa<IntrinsicInst>(V))
106     return None;
107 
108   const Function *Callee = getCalledFunction(V, LookThroughBitCast);
109   if (!Callee)
110     return None;
111 
112   // If it has allocsize, we can skip checking if it's a known function.
113   //
114   // MallocLike is chosen here because allocsize makes no guarantees about the
115   // nullness of the result of the function, nor does it deal with strings, nor
116   // does it require that the memory returned is zeroed out.
117   LLVM_CONSTEXPR auto AllocSizeAllocTy = MallocLike;
118   if ((AllocTy & AllocSizeAllocTy) == AllocSizeAllocTy &&
119       Callee->hasFnAttribute(Attribute::AllocSize)) {
120     Attribute Attr = Callee->getFnAttribute(Attribute::AllocSize);
121     std::pair<unsigned, Optional<unsigned>> Args = Attr.getAllocSizeArgs();
122 
123     AllocFnsTy Result;
124     Result.AllocTy = AllocSizeAllocTy;
125     Result.NumParams = Callee->getNumOperands();
126     Result.FstParam = Args.first;
127     Result.SndParam = Args.second.getValueOr(-1);
128     return Result;
129   }
130 
131   // Make sure that the function is available.
132   StringRef FnName = Callee->getName();
133   LibFunc::Func TLIFn;
134   if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
135     return None;
136 
137   const auto *Iter =
138       std::find_if(std::begin(AllocationFnData), std::end(AllocationFnData),
139                    [TLIFn](const std::pair<LibFunc::Func, AllocFnsTy> &P) {
140                      return P.first == TLIFn;
141                    });
142 
143   if (Iter == std::end(AllocationFnData))
144     return None;
145 
146   const AllocFnsTy *FnData = &Iter->second;
147   if ((FnData->AllocTy & AllocTy) != FnData->AllocTy)
148     return None;
149 
150   // Check function prototype.
151   int FstParam = FnData->FstParam;
152   int SndParam = FnData->SndParam;
153   FunctionType *FTy = Callee->getFunctionType();
154 
155   if (FTy->getReturnType() == Type::getInt8PtrTy(FTy->getContext()) &&
156       FTy->getNumParams() == FnData->NumParams &&
157       (FstParam < 0 ||
158        (FTy->getParamType(FstParam)->isIntegerTy(32) ||
159         FTy->getParamType(FstParam)->isIntegerTy(64))) &&
160       (SndParam < 0 ||
161        FTy->getParamType(SndParam)->isIntegerTy(32) ||
162        FTy->getParamType(SndParam)->isIntegerTy(64)))
163     return *FnData;
164   return None;
165 }
166 
hasNoAliasAttr(const Value * V,bool LookThroughBitCast)167 static bool hasNoAliasAttr(const Value *V, bool LookThroughBitCast) {
168   ImmutableCallSite CS(LookThroughBitCast ? V->stripPointerCasts() : V);
169   return CS && CS.paramHasAttr(AttributeSet::ReturnIndex, Attribute::NoAlias);
170 }
171 
172 
173 /// \brief Tests if a value is a call or invoke to a library function that
174 /// allocates or reallocates memory (either malloc, calloc, realloc, or strdup
175 /// like).
isAllocationFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)176 bool llvm::isAllocationFn(const Value *V, const TargetLibraryInfo *TLI,
177                           bool LookThroughBitCast) {
178   return getAllocationData(V, AnyAlloc, TLI, LookThroughBitCast).hasValue();
179 }
180 
181 /// \brief Tests if a value is a call or invoke to a function that returns a
182 /// NoAlias pointer (including malloc/calloc/realloc/strdup-like functions).
isNoAliasFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)183 bool llvm::isNoAliasFn(const Value *V, const TargetLibraryInfo *TLI,
184                        bool LookThroughBitCast) {
185   // it's safe to consider realloc as noalias since accessing the original
186   // pointer is undefined behavior
187   return isAllocationFn(V, TLI, LookThroughBitCast) ||
188          hasNoAliasAttr(V, LookThroughBitCast);
189 }
190 
191 /// \brief Tests if a value is a call or invoke to a library function that
192 /// allocates uninitialized memory (such as malloc).
isMallocLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)193 bool llvm::isMallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
194                           bool LookThroughBitCast) {
195   return getAllocationData(V, MallocLike, TLI, LookThroughBitCast).hasValue();
196 }
197 
198 /// \brief Tests if a value is a call or invoke to a library function that
199 /// allocates zero-filled memory (such as calloc).
isCallocLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)200 bool llvm::isCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
201                           bool LookThroughBitCast) {
202   return getAllocationData(V, CallocLike, TLI, LookThroughBitCast).hasValue();
203 }
204 
205 /// \brief Tests if a value is a call or invoke to a library function that
206 /// allocates memory (either malloc, calloc, or strdup like).
isAllocLikeFn(const Value * V,const TargetLibraryInfo * TLI,bool LookThroughBitCast)207 bool llvm::isAllocLikeFn(const Value *V, const TargetLibraryInfo *TLI,
208                          bool LookThroughBitCast) {
209   return getAllocationData(V, AllocLike, TLI, LookThroughBitCast).hasValue();
210 }
211 
212 /// extractMallocCall - Returns the corresponding CallInst if the instruction
213 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
214 /// ignore InvokeInst here.
extractMallocCall(const Value * I,const TargetLibraryInfo * TLI)215 const CallInst *llvm::extractMallocCall(const Value *I,
216                                         const TargetLibraryInfo *TLI) {
217   return isMallocLikeFn(I, TLI) ? dyn_cast<CallInst>(I) : nullptr;
218 }
219 
computeArraySize(const CallInst * CI,const DataLayout & DL,const TargetLibraryInfo * TLI,bool LookThroughSExt=false)220 static Value *computeArraySize(const CallInst *CI, const DataLayout &DL,
221                                const TargetLibraryInfo *TLI,
222                                bool LookThroughSExt = false) {
223   if (!CI)
224     return nullptr;
225 
226   // The size of the malloc's result type must be known to determine array size.
227   Type *T = getMallocAllocatedType(CI, TLI);
228   if (!T || !T->isSized())
229     return nullptr;
230 
231   unsigned ElementSize = DL.getTypeAllocSize(T);
232   if (StructType *ST = dyn_cast<StructType>(T))
233     ElementSize = DL.getStructLayout(ST)->getSizeInBytes();
234 
235   // If malloc call's arg can be determined to be a multiple of ElementSize,
236   // return the multiple.  Otherwise, return NULL.
237   Value *MallocArg = CI->getArgOperand(0);
238   Value *Multiple = nullptr;
239   if (ComputeMultiple(MallocArg, ElementSize, Multiple, LookThroughSExt))
240     return Multiple;
241 
242   return nullptr;
243 }
244 
245 /// getMallocType - Returns the PointerType resulting from the malloc call.
246 /// The PointerType depends on the number of bitcast uses of the malloc call:
247 ///   0: PointerType is the calls' return type.
248 ///   1: PointerType is the bitcast's result type.
249 ///  >1: Unique PointerType cannot be determined, return NULL.
getMallocType(const CallInst * CI,const TargetLibraryInfo * TLI)250 PointerType *llvm::getMallocType(const CallInst *CI,
251                                  const TargetLibraryInfo *TLI) {
252   assert(isMallocLikeFn(CI, TLI) && "getMallocType and not malloc call");
253 
254   PointerType *MallocType = nullptr;
255   unsigned NumOfBitCastUses = 0;
256 
257   // Determine if CallInst has a bitcast use.
258   for (Value::const_user_iterator UI = CI->user_begin(), E = CI->user_end();
259        UI != E;)
260     if (const BitCastInst *BCI = dyn_cast<BitCastInst>(*UI++)) {
261       MallocType = cast<PointerType>(BCI->getDestTy());
262       NumOfBitCastUses++;
263     }
264 
265   // Malloc call has 1 bitcast use, so type is the bitcast's destination type.
266   if (NumOfBitCastUses == 1)
267     return MallocType;
268 
269   // Malloc call was not bitcast, so type is the malloc function's return type.
270   if (NumOfBitCastUses == 0)
271     return cast<PointerType>(CI->getType());
272 
273   // Type could not be determined.
274   return nullptr;
275 }
276 
277 /// getMallocAllocatedType - Returns the Type allocated by malloc call.
278 /// The Type depends on the number of bitcast uses of the malloc call:
279 ///   0: PointerType is the malloc calls' return type.
280 ///   1: PointerType is the bitcast's result type.
281 ///  >1: Unique PointerType cannot be determined, return NULL.
getMallocAllocatedType(const CallInst * CI,const TargetLibraryInfo * TLI)282 Type *llvm::getMallocAllocatedType(const CallInst *CI,
283                                    const TargetLibraryInfo *TLI) {
284   PointerType *PT = getMallocType(CI, TLI);
285   return PT ? PT->getElementType() : nullptr;
286 }
287 
288 /// getMallocArraySize - Returns the array size of a malloc call.  If the
289 /// argument passed to malloc is a multiple of the size of the malloced type,
290 /// then return that multiple.  For non-array mallocs, the multiple is
291 /// constant 1.  Otherwise, return NULL for mallocs whose array size cannot be
292 /// determined.
getMallocArraySize(CallInst * CI,const DataLayout & DL,const TargetLibraryInfo * TLI,bool LookThroughSExt)293 Value *llvm::getMallocArraySize(CallInst *CI, const DataLayout &DL,
294                                 const TargetLibraryInfo *TLI,
295                                 bool LookThroughSExt) {
296   assert(isMallocLikeFn(CI, TLI) && "getMallocArraySize and not malloc call");
297   return computeArraySize(CI, DL, TLI, LookThroughSExt);
298 }
299 
300 
301 /// extractCallocCall - Returns the corresponding CallInst if the instruction
302 /// is a calloc call.
extractCallocCall(const Value * I,const TargetLibraryInfo * TLI)303 const CallInst *llvm::extractCallocCall(const Value *I,
304                                         const TargetLibraryInfo *TLI) {
305   return isCallocLikeFn(I, TLI) ? cast<CallInst>(I) : nullptr;
306 }
307 
308 
309 /// isFreeCall - Returns non-null if the value is a call to the builtin free()
isFreeCall(const Value * I,const TargetLibraryInfo * TLI)310 const CallInst *llvm::isFreeCall(const Value *I, const TargetLibraryInfo *TLI) {
311   const CallInst *CI = dyn_cast<CallInst>(I);
312   if (!CI || isa<IntrinsicInst>(CI))
313     return nullptr;
314   Function *Callee = CI->getCalledFunction();
315   if (Callee == nullptr)
316     return nullptr;
317 
318   StringRef FnName = Callee->getName();
319   LibFunc::Func TLIFn;
320   if (!TLI || !TLI->getLibFunc(FnName, TLIFn) || !TLI->has(TLIFn))
321     return nullptr;
322 
323   unsigned ExpectedNumParams;
324   if (TLIFn == LibFunc::free ||
325       TLIFn == LibFunc::ZdlPv || // operator delete(void*)
326       TLIFn == LibFunc::ZdaPv || // operator delete[](void*)
327       TLIFn == LibFunc::msvc_delete_ptr32 || // operator delete(void*)
328       TLIFn == LibFunc::msvc_delete_ptr64 || // operator delete(void*)
329       TLIFn == LibFunc::msvc_delete_array_ptr32 || // operator delete[](void*)
330       TLIFn == LibFunc::msvc_delete_array_ptr64)   // operator delete[](void*)
331     ExpectedNumParams = 1;
332   else if (TLIFn == LibFunc::ZdlPvj ||              // delete(void*, uint)
333            TLIFn == LibFunc::ZdlPvm ||              // delete(void*, ulong)
334            TLIFn == LibFunc::ZdlPvRKSt9nothrow_t || // delete(void*, nothrow)
335            TLIFn == LibFunc::ZdaPvj ||              // delete[](void*, uint)
336            TLIFn == LibFunc::ZdaPvm ||              // delete[](void*, ulong)
337            TLIFn == LibFunc::ZdaPvRKSt9nothrow_t || // delete[](void*, nothrow)
338            TLIFn == LibFunc::msvc_delete_ptr32_int ||      // delete(void*, uint)
339            TLIFn == LibFunc::msvc_delete_ptr64_longlong || // delete(void*, ulonglong)
340            TLIFn == LibFunc::msvc_delete_ptr32_nothrow || // delete(void*, nothrow)
341            TLIFn == LibFunc::msvc_delete_ptr64_nothrow || // delete(void*, nothrow)
342            TLIFn == LibFunc::msvc_delete_array_ptr32_int ||      // delete[](void*, uint)
343            TLIFn == LibFunc::msvc_delete_array_ptr64_longlong || // delete[](void*, ulonglong)
344            TLIFn == LibFunc::msvc_delete_array_ptr32_nothrow || // delete[](void*, nothrow)
345            TLIFn == LibFunc::msvc_delete_array_ptr64_nothrow)   // delete[](void*, nothrow)
346     ExpectedNumParams = 2;
347   else
348     return nullptr;
349 
350   // Check free prototype.
351   // FIXME: workaround for PR5130, this will be obsolete when a nobuiltin
352   // attribute will exist.
353   FunctionType *FTy = Callee->getFunctionType();
354   if (!FTy->getReturnType()->isVoidTy())
355     return nullptr;
356   if (FTy->getNumParams() != ExpectedNumParams)
357     return nullptr;
358   if (FTy->getParamType(0) != Type::getInt8PtrTy(Callee->getContext()))
359     return nullptr;
360 
361   return CI;
362 }
363 
364 
365 
366 //===----------------------------------------------------------------------===//
367 //  Utility functions to compute size of objects.
368 //
getSizeWithOverflow(const SizeOffsetType & Data)369 static APInt getSizeWithOverflow(const SizeOffsetType &Data) {
370   if (Data.second.isNegative() || Data.first.ult(Data.second))
371     return APInt(Data.first.getBitWidth(), 0);
372   return Data.first - Data.second;
373 }
374 
375 /// \brief Compute the size of the object pointed by Ptr. Returns true and the
376 /// object size in Size if successful, and false otherwise.
377 /// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
378 /// byval arguments, and global variables.
getObjectSize(const Value * Ptr,uint64_t & Size,const DataLayout & DL,const TargetLibraryInfo * TLI,bool RoundToAlign,llvm::ObjSizeMode Mode)379 bool llvm::getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL,
380                          const TargetLibraryInfo *TLI, bool RoundToAlign,
381                          llvm::ObjSizeMode Mode) {
382   ObjectSizeOffsetVisitor Visitor(DL, TLI, Ptr->getContext(),
383                                   RoundToAlign, Mode);
384   SizeOffsetType Data = Visitor.compute(const_cast<Value*>(Ptr));
385   if (!Visitor.bothKnown(Data))
386     return false;
387 
388   Size = getSizeWithOverflow(Data).getZExtValue();
389   return true;
390 }
391 
392 STATISTIC(ObjectVisitorArgument,
393           "Number of arguments with unsolved size and offset");
394 STATISTIC(ObjectVisitorLoad,
395           "Number of load instructions with unsolved size and offset");
396 
397 
align(APInt Size,uint64_t Align)398 APInt ObjectSizeOffsetVisitor::align(APInt Size, uint64_t Align) {
399   if (RoundToAlign && Align)
400     return APInt(IntTyBits, alignTo(Size.getZExtValue(), Align));
401   return Size;
402 }
403 
ObjectSizeOffsetVisitor(const DataLayout & DL,const TargetLibraryInfo * TLI,LLVMContext & Context,bool RoundToAlign,ObjSizeMode Mode)404 ObjectSizeOffsetVisitor::ObjectSizeOffsetVisitor(const DataLayout &DL,
405                                                  const TargetLibraryInfo *TLI,
406                                                  LLVMContext &Context,
407                                                  bool RoundToAlign,
408                                                  ObjSizeMode Mode)
409     : DL(DL), TLI(TLI), RoundToAlign(RoundToAlign), Mode(Mode) {
410   // Pointer size must be rechecked for each object visited since it could have
411   // a different address space.
412 }
413 
compute(Value * V)414 SizeOffsetType ObjectSizeOffsetVisitor::compute(Value *V) {
415   IntTyBits = DL.getPointerTypeSizeInBits(V->getType());
416   Zero = APInt::getNullValue(IntTyBits);
417 
418   V = V->stripPointerCasts();
419   if (Instruction *I = dyn_cast<Instruction>(V)) {
420     // If we have already seen this instruction, bail out. Cycles can happen in
421     // unreachable code after constant propagation.
422     if (!SeenInsts.insert(I).second)
423       return unknown();
424 
425     if (GEPOperator *GEP = dyn_cast<GEPOperator>(V))
426       return visitGEPOperator(*GEP);
427     return visit(*I);
428   }
429   if (Argument *A = dyn_cast<Argument>(V))
430     return visitArgument(*A);
431   if (ConstantPointerNull *P = dyn_cast<ConstantPointerNull>(V))
432     return visitConstantPointerNull(*P);
433   if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V))
434     return visitGlobalAlias(*GA);
435   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
436     return visitGlobalVariable(*GV);
437   if (UndefValue *UV = dyn_cast<UndefValue>(V))
438     return visitUndefValue(*UV);
439   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
440     if (CE->getOpcode() == Instruction::IntToPtr)
441       return unknown(); // clueless
442     if (CE->getOpcode() == Instruction::GetElementPtr)
443       return visitGEPOperator(cast<GEPOperator>(*CE));
444   }
445 
446   DEBUG(dbgs() << "ObjectSizeOffsetVisitor::compute() unhandled value: " << *V
447         << '\n');
448   return unknown();
449 }
450 
visitAllocaInst(AllocaInst & I)451 SizeOffsetType ObjectSizeOffsetVisitor::visitAllocaInst(AllocaInst &I) {
452   if (!I.getAllocatedType()->isSized())
453     return unknown();
454 
455   APInt Size(IntTyBits, DL.getTypeAllocSize(I.getAllocatedType()));
456   if (!I.isArrayAllocation())
457     return std::make_pair(align(Size, I.getAlignment()), Zero);
458 
459   Value *ArraySize = I.getArraySize();
460   if (const ConstantInt *C = dyn_cast<ConstantInt>(ArraySize)) {
461     Size *= C->getValue().zextOrSelf(IntTyBits);
462     return std::make_pair(align(Size, I.getAlignment()), Zero);
463   }
464   return unknown();
465 }
466 
visitArgument(Argument & A)467 SizeOffsetType ObjectSizeOffsetVisitor::visitArgument(Argument &A) {
468   // No interprocedural analysis is done at the moment.
469   if (!A.hasByValOrInAllocaAttr()) {
470     ++ObjectVisitorArgument;
471     return unknown();
472   }
473   PointerType *PT = cast<PointerType>(A.getType());
474   APInt Size(IntTyBits, DL.getTypeAllocSize(PT->getElementType()));
475   return std::make_pair(align(Size, A.getParamAlignment()), Zero);
476 }
477 
visitCallSite(CallSite CS)478 SizeOffsetType ObjectSizeOffsetVisitor::visitCallSite(CallSite CS) {
479   Optional<AllocFnsTy> FnData =
480       getAllocationData(CS.getInstruction(), AnyAlloc, TLI);
481   if (!FnData)
482     return unknown();
483 
484   // Handle strdup-like functions separately.
485   if (FnData->AllocTy == StrDupLike) {
486     APInt Size(IntTyBits, GetStringLength(CS.getArgument(0)));
487     if (!Size)
488       return unknown();
489 
490     // Strndup limits strlen.
491     if (FnData->FstParam > 0) {
492       ConstantInt *Arg =
493           dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
494       if (!Arg)
495         return unknown();
496 
497       APInt MaxSize = Arg->getValue().zextOrSelf(IntTyBits);
498       if (Size.ugt(MaxSize))
499         Size = MaxSize + 1;
500     }
501     return std::make_pair(Size, Zero);
502   }
503 
504   ConstantInt *Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->FstParam));
505   if (!Arg)
506     return unknown();
507 
508   // When we're compiling N-bit code, and the user uses parameters that are
509   // greater than N bits (e.g. uint64_t on a 32-bit build), we can run into
510   // trouble with APInt size issues. This function handles resizing + overflow
511   // checks for us.
512   auto CheckedZextOrTrunc = [&](APInt &I) {
513     // More bits than we can handle. Checking the bit width isn't necessary, but
514     // it's faster than checking active bits, and should give `false` in the
515     // vast majority of cases.
516     if (I.getBitWidth() > IntTyBits && I.getActiveBits() > IntTyBits)
517       return false;
518     if (I.getBitWidth() != IntTyBits)
519       I = I.zextOrTrunc(IntTyBits);
520     return true;
521   };
522 
523   APInt Size = Arg->getValue();
524   if (!CheckedZextOrTrunc(Size))
525     return unknown();
526 
527   // Size is determined by just 1 parameter.
528   if (FnData->SndParam < 0)
529     return std::make_pair(Size, Zero);
530 
531   Arg = dyn_cast<ConstantInt>(CS.getArgument(FnData->SndParam));
532   if (!Arg)
533     return unknown();
534 
535   APInt NumElems = Arg->getValue();
536   if (!CheckedZextOrTrunc(NumElems))
537     return unknown();
538 
539   bool Overflow;
540   Size = Size.umul_ov(NumElems, Overflow);
541   return Overflow ? unknown() : std::make_pair(Size, Zero);
542 
543   // TODO: handle more standard functions (+ wchar cousins):
544   // - strdup / strndup
545   // - strcpy / strncpy
546   // - strcat / strncat
547   // - memcpy / memmove
548   // - strcat / strncat
549   // - memset
550 }
551 
552 SizeOffsetType
visitConstantPointerNull(ConstantPointerNull &)553 ObjectSizeOffsetVisitor::visitConstantPointerNull(ConstantPointerNull&) {
554   return std::make_pair(Zero, Zero);
555 }
556 
557 SizeOffsetType
visitExtractElementInst(ExtractElementInst &)558 ObjectSizeOffsetVisitor::visitExtractElementInst(ExtractElementInst&) {
559   return unknown();
560 }
561 
562 SizeOffsetType
visitExtractValueInst(ExtractValueInst &)563 ObjectSizeOffsetVisitor::visitExtractValueInst(ExtractValueInst&) {
564   // Easy cases were already folded by previous passes.
565   return unknown();
566 }
567 
visitGEPOperator(GEPOperator & GEP)568 SizeOffsetType ObjectSizeOffsetVisitor::visitGEPOperator(GEPOperator &GEP) {
569   SizeOffsetType PtrData = compute(GEP.getPointerOperand());
570   APInt Offset(IntTyBits, 0);
571   if (!bothKnown(PtrData) || !GEP.accumulateConstantOffset(DL, Offset))
572     return unknown();
573 
574   return std::make_pair(PtrData.first, PtrData.second + Offset);
575 }
576 
visitGlobalAlias(GlobalAlias & GA)577 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalAlias(GlobalAlias &GA) {
578   if (GA.isInterposable())
579     return unknown();
580   return compute(GA.getAliasee());
581 }
582 
visitGlobalVariable(GlobalVariable & GV)583 SizeOffsetType ObjectSizeOffsetVisitor::visitGlobalVariable(GlobalVariable &GV){
584   if (!GV.hasDefinitiveInitializer())
585     return unknown();
586 
587   APInt Size(IntTyBits, DL.getTypeAllocSize(GV.getType()->getElementType()));
588   return std::make_pair(align(Size, GV.getAlignment()), Zero);
589 }
590 
visitIntToPtrInst(IntToPtrInst &)591 SizeOffsetType ObjectSizeOffsetVisitor::visitIntToPtrInst(IntToPtrInst&) {
592   // clueless
593   return unknown();
594 }
595 
visitLoadInst(LoadInst &)596 SizeOffsetType ObjectSizeOffsetVisitor::visitLoadInst(LoadInst&) {
597   ++ObjectVisitorLoad;
598   return unknown();
599 }
600 
visitPHINode(PHINode &)601 SizeOffsetType ObjectSizeOffsetVisitor::visitPHINode(PHINode&) {
602   // too complex to analyze statically.
603   return unknown();
604 }
605 
visitSelectInst(SelectInst & I)606 SizeOffsetType ObjectSizeOffsetVisitor::visitSelectInst(SelectInst &I) {
607   SizeOffsetType TrueSide  = compute(I.getTrueValue());
608   SizeOffsetType FalseSide = compute(I.getFalseValue());
609   if (bothKnown(TrueSide) && bothKnown(FalseSide)) {
610     if (TrueSide == FalseSide) {
611         return TrueSide;
612     }
613 
614     APInt TrueResult = getSizeWithOverflow(TrueSide);
615     APInt FalseResult = getSizeWithOverflow(FalseSide);
616 
617     if (TrueResult == FalseResult) {
618       return TrueSide;
619     }
620     if (Mode == ObjSizeMode::Min) {
621       if (TrueResult.slt(FalseResult))
622         return TrueSide;
623       return FalseSide;
624     }
625     if (Mode == ObjSizeMode::Max) {
626       if (TrueResult.sgt(FalseResult))
627         return TrueSide;
628       return FalseSide;
629     }
630   }
631   return unknown();
632 }
633 
visitUndefValue(UndefValue &)634 SizeOffsetType ObjectSizeOffsetVisitor::visitUndefValue(UndefValue&) {
635   return std::make_pair(Zero, Zero);
636 }
637 
visitInstruction(Instruction & I)638 SizeOffsetType ObjectSizeOffsetVisitor::visitInstruction(Instruction &I) {
639   DEBUG(dbgs() << "ObjectSizeOffsetVisitor unknown instruction:" << I << '\n');
640   return unknown();
641 }
642 
ObjectSizeOffsetEvaluator(const DataLayout & DL,const TargetLibraryInfo * TLI,LLVMContext & Context,bool RoundToAlign)643 ObjectSizeOffsetEvaluator::ObjectSizeOffsetEvaluator(
644     const DataLayout &DL, const TargetLibraryInfo *TLI, LLVMContext &Context,
645     bool RoundToAlign)
646     : DL(DL), TLI(TLI), Context(Context), Builder(Context, TargetFolder(DL)),
647       RoundToAlign(RoundToAlign) {
648   // IntTy and Zero must be set for each compute() since the address space may
649   // be different for later objects.
650 }
651 
compute(Value * V)652 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute(Value *V) {
653   // XXX - Are vectors of pointers possible here?
654   IntTy = cast<IntegerType>(DL.getIntPtrType(V->getType()));
655   Zero = ConstantInt::get(IntTy, 0);
656 
657   SizeOffsetEvalType Result = compute_(V);
658 
659   if (!bothKnown(Result)) {
660     // Erase everything that was computed in this iteration from the cache, so
661     // that no dangling references are left behind. We could be a bit smarter if
662     // we kept a dependency graph. It's probably not worth the complexity.
663     for (const Value *SeenVal : SeenVals) {
664       CacheMapTy::iterator CacheIt = CacheMap.find(SeenVal);
665       // non-computable results can be safely cached
666       if (CacheIt != CacheMap.end() && anyKnown(CacheIt->second))
667         CacheMap.erase(CacheIt);
668     }
669   }
670 
671   SeenVals.clear();
672   return Result;
673 }
674 
compute_(Value * V)675 SizeOffsetEvalType ObjectSizeOffsetEvaluator::compute_(Value *V) {
676   ObjectSizeOffsetVisitor Visitor(DL, TLI, Context, RoundToAlign);
677   SizeOffsetType Const = Visitor.compute(V);
678   if (Visitor.bothKnown(Const))
679     return std::make_pair(ConstantInt::get(Context, Const.first),
680                           ConstantInt::get(Context, Const.second));
681 
682   V = V->stripPointerCasts();
683 
684   // Check cache.
685   CacheMapTy::iterator CacheIt = CacheMap.find(V);
686   if (CacheIt != CacheMap.end())
687     return CacheIt->second;
688 
689   // Always generate code immediately before the instruction being
690   // processed, so that the generated code dominates the same BBs.
691   BuilderTy::InsertPointGuard Guard(Builder);
692   if (Instruction *I = dyn_cast<Instruction>(V))
693     Builder.SetInsertPoint(I);
694 
695   // Now compute the size and offset.
696   SizeOffsetEvalType Result;
697 
698   // Record the pointers that were handled in this run, so that they can be
699   // cleaned later if something fails. We also use this set to break cycles that
700   // can occur in dead code.
701   if (!SeenVals.insert(V).second) {
702     Result = unknown();
703   } else if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
704     Result = visitGEPOperator(*GEP);
705   } else if (Instruction *I = dyn_cast<Instruction>(V)) {
706     Result = visit(*I);
707   } else if (isa<Argument>(V) ||
708              (isa<ConstantExpr>(V) &&
709               cast<ConstantExpr>(V)->getOpcode() == Instruction::IntToPtr) ||
710              isa<GlobalAlias>(V) ||
711              isa<GlobalVariable>(V)) {
712     // Ignore values where we cannot do more than ObjectSizeVisitor.
713     Result = unknown();
714   } else {
715     DEBUG(dbgs() << "ObjectSizeOffsetEvaluator::compute() unhandled value: "
716           << *V << '\n');
717     Result = unknown();
718   }
719 
720   // Don't reuse CacheIt since it may be invalid at this point.
721   CacheMap[V] = Result;
722   return Result;
723 }
724 
visitAllocaInst(AllocaInst & I)725 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitAllocaInst(AllocaInst &I) {
726   if (!I.getAllocatedType()->isSized())
727     return unknown();
728 
729   // must be a VLA
730   assert(I.isArrayAllocation());
731   Value *ArraySize = I.getArraySize();
732   Value *Size = ConstantInt::get(ArraySize->getType(),
733                                  DL.getTypeAllocSize(I.getAllocatedType()));
734   Size = Builder.CreateMul(Size, ArraySize);
735   return std::make_pair(Size, Zero);
736 }
737 
visitCallSite(CallSite CS)738 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitCallSite(CallSite CS) {
739   Optional<AllocFnsTy> FnData =
740       getAllocationData(CS.getInstruction(), AnyAlloc, TLI);
741   if (!FnData)
742     return unknown();
743 
744   // Handle strdup-like functions separately.
745   if (FnData->AllocTy == StrDupLike) {
746     // TODO
747     return unknown();
748   }
749 
750   Value *FirstArg = CS.getArgument(FnData->FstParam);
751   FirstArg = Builder.CreateZExt(FirstArg, IntTy);
752   if (FnData->SndParam < 0)
753     return std::make_pair(FirstArg, Zero);
754 
755   Value *SecondArg = CS.getArgument(FnData->SndParam);
756   SecondArg = Builder.CreateZExt(SecondArg, IntTy);
757   Value *Size = Builder.CreateMul(FirstArg, SecondArg);
758   return std::make_pair(Size, Zero);
759 
760   // TODO: handle more standard functions (+ wchar cousins):
761   // - strdup / strndup
762   // - strcpy / strncpy
763   // - strcat / strncat
764   // - memcpy / memmove
765   // - strcat / strncat
766   // - memset
767 }
768 
769 SizeOffsetEvalType
visitExtractElementInst(ExtractElementInst &)770 ObjectSizeOffsetEvaluator::visitExtractElementInst(ExtractElementInst&) {
771   return unknown();
772 }
773 
774 SizeOffsetEvalType
visitExtractValueInst(ExtractValueInst &)775 ObjectSizeOffsetEvaluator::visitExtractValueInst(ExtractValueInst&) {
776   return unknown();
777 }
778 
779 SizeOffsetEvalType
visitGEPOperator(GEPOperator & GEP)780 ObjectSizeOffsetEvaluator::visitGEPOperator(GEPOperator &GEP) {
781   SizeOffsetEvalType PtrData = compute_(GEP.getPointerOperand());
782   if (!bothKnown(PtrData))
783     return unknown();
784 
785   Value *Offset = EmitGEPOffset(&Builder, DL, &GEP, /*NoAssumptions=*/true);
786   Offset = Builder.CreateAdd(PtrData.second, Offset);
787   return std::make_pair(PtrData.first, Offset);
788 }
789 
visitIntToPtrInst(IntToPtrInst &)790 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitIntToPtrInst(IntToPtrInst&) {
791   // clueless
792   return unknown();
793 }
794 
visitLoadInst(LoadInst &)795 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitLoadInst(LoadInst&) {
796   return unknown();
797 }
798 
visitPHINode(PHINode & PHI)799 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitPHINode(PHINode &PHI) {
800   // Create 2 PHIs: one for size and another for offset.
801   PHINode *SizePHI   = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
802   PHINode *OffsetPHI = Builder.CreatePHI(IntTy, PHI.getNumIncomingValues());
803 
804   // Insert right away in the cache to handle recursive PHIs.
805   CacheMap[&PHI] = std::make_pair(SizePHI, OffsetPHI);
806 
807   // Compute offset/size for each PHI incoming pointer.
808   for (unsigned i = 0, e = PHI.getNumIncomingValues(); i != e; ++i) {
809     Builder.SetInsertPoint(&*PHI.getIncomingBlock(i)->getFirstInsertionPt());
810     SizeOffsetEvalType EdgeData = compute_(PHI.getIncomingValue(i));
811 
812     if (!bothKnown(EdgeData)) {
813       OffsetPHI->replaceAllUsesWith(UndefValue::get(IntTy));
814       OffsetPHI->eraseFromParent();
815       SizePHI->replaceAllUsesWith(UndefValue::get(IntTy));
816       SizePHI->eraseFromParent();
817       return unknown();
818     }
819     SizePHI->addIncoming(EdgeData.first, PHI.getIncomingBlock(i));
820     OffsetPHI->addIncoming(EdgeData.second, PHI.getIncomingBlock(i));
821   }
822 
823   Value *Size = SizePHI, *Offset = OffsetPHI, *Tmp;
824   if ((Tmp = SizePHI->hasConstantValue())) {
825     Size = Tmp;
826     SizePHI->replaceAllUsesWith(Size);
827     SizePHI->eraseFromParent();
828   }
829   if ((Tmp = OffsetPHI->hasConstantValue())) {
830     Offset = Tmp;
831     OffsetPHI->replaceAllUsesWith(Offset);
832     OffsetPHI->eraseFromParent();
833   }
834   return std::make_pair(Size, Offset);
835 }
836 
visitSelectInst(SelectInst & I)837 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitSelectInst(SelectInst &I) {
838   SizeOffsetEvalType TrueSide  = compute_(I.getTrueValue());
839   SizeOffsetEvalType FalseSide = compute_(I.getFalseValue());
840 
841   if (!bothKnown(TrueSide) || !bothKnown(FalseSide))
842     return unknown();
843   if (TrueSide == FalseSide)
844     return TrueSide;
845 
846   Value *Size = Builder.CreateSelect(I.getCondition(), TrueSide.first,
847                                      FalseSide.first);
848   Value *Offset = Builder.CreateSelect(I.getCondition(), TrueSide.second,
849                                        FalseSide.second);
850   return std::make_pair(Size, Offset);
851 }
852 
visitInstruction(Instruction & I)853 SizeOffsetEvalType ObjectSizeOffsetEvaluator::visitInstruction(Instruction &I) {
854   DEBUG(dbgs() << "ObjectSizeOffsetEvaluator unknown instruction:" << I <<'\n');
855   return unknown();
856 }
857