refactor the MemoryBuiltin analysis:

 - provide more extensive set of functions to detect library allocation functions (e.g., malloc, calloc, strdup, etc)
 - provide an API to compute the size and offset of an object pointed by

Move a few clients (GVN, AA, instcombine, ...) to the new API.
This implementation is a lot more aggressive than each of the custom implementations being replaced.

Patch reviewed by Nick Lewycky and Chandler Carruth, thanks.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@158919 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 164 insertions, 8 deletions

diff --git a/include/llvm/Analysis/MemoryBuiltins.h b/include/llvm/Analysis/MemoryBuiltins.h
index e7dcbf3..ab4a3f3 100644
--- a/include/llvm/Analysis/MemoryBuiltins.h
+++ b/include/llvm/Analysis/MemoryBuiltins.h
@@ -15,6 +15,14 @@
 #ifndef LLVM_ANALYSIS_MEMORYBUILTINS_H
 #define LLVM_ANALYSIS_MEMORYBUILTINS_H
 
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/Operator.h"
+#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/InstVisitor.h"
+#include "llvm/Support/IRBuilder.h"
+#include "llvm/Support/TargetFolder.h"
+
 namespace llvm {
 class CallInst;
 class PointerType;
@@ -22,24 +30,50 @@ class TargetData;
 class Type;
 class Value;
 
+
+/// \brief Tests if a value is a call to a library function that allocates or
+/// reallocates memory (either malloc, calloc, realloc, or strdup like).
+bool isAllocationFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call to a function that returns a NoAlias
+/// pointer (including malloc/calloc/strdup-like functions).
+bool isNoAliasFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call to a library function that allocates
+/// uninitialized memory (such as malloc).
+bool isMallocLikeFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call to a library function that allocates
+/// zero-filled memory (such as calloc).
+bool isCallocLikeFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call to a library function that allocates
+/// memory (either malloc, calloc, or strdup like).
+bool isAllocLikeFn(const Value *V, bool LookThroughBitCast = false);
+
+/// \brief Tests if a value is a call to a library function that reallocates
+/// memory (such as realloc).
+bool isReallocLikeFn(const Value *V, bool LookThroughBitCast = false);
+
+
 //===----------------------------------------------------------------------===//
 //  malloc Call Utility Functions.
 //
 
-/// isMalloc - Returns true if the value is either a malloc call or a bitcast of 
-/// the result of a malloc call
-bool isMalloc(const Value *I);
-
 /// extractMallocCall - Returns the corresponding CallInst if the instruction
 /// is a malloc call.  Since CallInst::CreateMalloc() only creates calls, we
 /// ignore InvokeInst here.
 const CallInst *extractMallocCall(const Value *I);
-CallInst *extractMallocCall(Value *I);
+static inline CallInst *extractMallocCall(Value *I) {
+  return const_cast<CallInst*>(extractMallocCall((const Value*)I));
+}
 
 /// extractMallocCallFromBitCast - Returns the corresponding CallInst if the
 /// instruction is a bitcast of the result of a malloc call.
 const CallInst *extractMallocCallFromBitCast(const Value *I);
-CallInst *extractMallocCallFromBitCast(Value *I);
+static inline CallInst *extractMallocCallFromBitCast(Value *I) {
+  return const_cast<CallInst*>(extractMallocCallFromBitCast((const Value*)I));
+}
 
 /// isArrayMalloc - Returns the corresponding CallInst if the instruction 
 /// is a call to malloc whose array size can be determined and the array size
@@ -67,7 +101,7 @@ Type *getMallocAllocatedType(const CallInst *CI);
 /// determined.
 Value *getMallocArraySize(CallInst *CI, const TargetData *TD,
                           bool LookThroughSExt = false);
-                          
+
 
 //===----------------------------------------------------------------------===//
 //  calloc Call Utility Functions.
@@ -76,7 +110,9 @@ Value *getMallocArraySize(CallInst *CI, const TargetData *TD,
 /// extractCallocCall - Returns the corresponding CallInst if the instruction
 /// is a calloc call.
 const CallInst *extractCallocCall(const Value *I);
-CallInst *extractCallocCall(Value *I);
+static inline CallInst *extractCallocCall(Value *I) {
+  return const_cast<CallInst*>(extractCallocCall((const Value*)I));
+}
 
 
 //===----------------------------------------------------------------------===//
@@ -90,6 +126,126 @@ static inline CallInst *isFreeCall(Value *I) {
   return const_cast<CallInst*>(isFreeCall((const Value*)I));
 }
 
+  
+//===----------------------------------------------------------------------===//
+//  Utility functions to compute size of objects.
+//
+
+/// \brief Compute the size of the object pointed by Ptr. Returns true and the
+/// object size in Size if successful, and false otherwise.
+/// If RoundToAlign is true, then Size is rounded up to the aligment of allocas,
+/// byval arguments, and global variables.
+bool getObjectSize(const Value *Ptr, uint64_t &Size, const TargetData *TD,
+                   bool RoundToAlign = false);
+
+
+
+typedef std::pair<APInt, APInt> SizeOffsetType;
+
+/// \brief Evaluate the size and offset of an object ponted by a Value*
+/// statically. Fails if size or offset are not known at compile time.
+class ObjectSizeOffsetVisitor
+  : public InstVisitor<ObjectSizeOffsetVisitor, SizeOffsetType> {
+
+  const TargetData *TD;
+  bool RoundToAlign;
+  unsigned IntTyBits;
+  APInt Zero;
+
+  APInt align(APInt Size, uint64_t Align);
+
+  SizeOffsetType unknown() {
+    return std::make_pair(APInt(), APInt());
+  }
+
+public:
+  ObjectSizeOffsetVisitor(const TargetData *TD, LLVMContext &Context,
+                          bool RoundToAlign = false);
+
+  SizeOffsetType compute(Value *V);
+
+  bool knownSize(SizeOffsetType &SizeOffset) {
+    return SizeOffset.first.getBitWidth() > 1;
+  }
+
+  bool knownOffset(SizeOffsetType &SizeOffset) {
+    return SizeOffset.second.getBitWidth() > 1;
+  }
+
+  bool bothKnown(SizeOffsetType &SizeOffset) {
+    return knownSize(SizeOffset) && knownOffset(SizeOffset);
+  }
+
+  SizeOffsetType visitAllocaInst(AllocaInst &I);
+  SizeOffsetType visitArgument(Argument &A);
+  SizeOffsetType visitCallSite(CallSite CS);
+  SizeOffsetType visitConstantPointerNull(ConstantPointerNull&);
+  SizeOffsetType visitExtractValueInst(ExtractValueInst &I);
+  SizeOffsetType visitGEPOperator(GEPOperator &GEP);
+  SizeOffsetType visitGlobalVariable(GlobalVariable &GV);
+  SizeOffsetType visitIntToPtrInst(IntToPtrInst&);
+  SizeOffsetType visitLoadInst(LoadInst &I);
+  SizeOffsetType visitPHINode(PHINode&);
+  SizeOffsetType visitSelectInst(SelectInst &I);
+  SizeOffsetType visitUndefValue(UndefValue&);
+  SizeOffsetType visitInstruction(Instruction &I);
+};
+
+typedef std::pair<Value*, Value*> SizeOffsetEvalType;
+typedef IRBuilder<true, TargetFolder> BuilderTy;
+typedef DenseMap<const Value*, SizeOffsetEvalType> CacheMapTy;
+typedef SmallPtrSet<const Value*, 8> PtrSetTy;
+
+
+/// \brief Evaluate the size and offset of an object ponted by a Value*.
+/// May create code to compute the result at run-time.
+class ObjectSizeOffsetEvaluator
+  : public InstVisitor<ObjectSizeOffsetEvaluator, SizeOffsetEvalType> {
+
+  const TargetData *TD;
+  LLVMContext &Context;
+  BuilderTy Builder;
+  ObjectSizeOffsetVisitor Visitor;
+  IntegerType *IntTy;
+  Value *Zero;
+  CacheMapTy CacheMap;
+  PtrSetTy SeenVals;
+
+  SizeOffsetEvalType unknown() {
+    return std::make_pair((Value*)0, (Value*)0);
+  }
+  SizeOffsetEvalType compute_(Value *V);
+
+public:
+  ObjectSizeOffsetEvaluator(const TargetData *TD, LLVMContext &Context);
+  SizeOffsetEvalType compute(Value *V);
+
+  bool knownSize(SizeOffsetEvalType &SizeOffset) {
+    return SizeOffset.first;
+  }
+
+  bool knownOffset(SizeOffsetEvalType &SizeOffset) {
+    return SizeOffset.second;
+  }
+
+  bool anyKnown(SizeOffsetEvalType &SizeOffset) {
+    return knownSize(SizeOffset) || knownOffset(SizeOffset);
+  }
+
+  bool bothKnown(SizeOffsetEvalType &SizeOffset) {
+    return knownSize(SizeOffset) && knownOffset(SizeOffset);
+  }
+
+  SizeOffsetEvalType visitAllocaInst(AllocaInst &I);
+  SizeOffsetEvalType visitCallSite(CallSite CS);
+  SizeOffsetEvalType visitGEPOperator(GEPOperator &GEP);
+  SizeOffsetEvalType visitIntToPtrInst(IntToPtrInst&);
+  SizeOffsetEvalType visitLoadInst(LoadInst &I);
+  SizeOffsetEvalType visitPHINode(PHINode &PHI);
+  SizeOffsetEvalType visitSelectInst(SelectInst &I);
+  SizeOffsetEvalType visitInstruction(Instruction &I);
+};
+
 } // End llvm namespace
 
 #endif