1 //===- PointerTracking.cpp - Pointer Bounds Tracking ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements tracking of pointer bounds.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Analysis/ConstantFolding.h"
15 #include "llvm/Analysis/Dominators.h"
16 #include "llvm/Analysis/LoopInfo.h"
17 #include "llvm/Analysis/MemoryBuiltins.h"
18 #include "llvm/Analysis/PointerTracking.h"
19 #include "llvm/Analysis/ScalarEvolution.h"
20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
21 #include "llvm/Constants.h"
22 #include "llvm/Module.h"
23 #include "llvm/Value.h"
24 #include "llvm/Support/CallSite.h"
25 #include "llvm/Support/InstIterator.h"
26 #include "llvm/Support/raw_ostream.h"
27 #include "llvm/Target/TargetData.h"
30 char PointerTracking::ID = 0;
31 PointerTracking::PointerTracking() : FunctionPass(&ID) {}
33 bool PointerTracking::runOnFunction(Function &F) {
35 assert(analyzing.empty());
37 TD = getAnalysisIfAvailable<TargetData>();
38 SE = &getAnalysis<ScalarEvolution>();
39 LI = &getAnalysis<LoopInfo>();
40 DT = &getAnalysis<DominatorTree>();
44 void PointerTracking::getAnalysisUsage(AnalysisUsage &AU) const {
45 AU.addRequiredTransitive<DominatorTree>();
46 AU.addRequiredTransitive<LoopInfo>();
47 AU.addRequiredTransitive<ScalarEvolution>();
51 bool PointerTracking::doInitialization(Module &M) {
52 const Type *PTy = Type::getInt8PtrTy(M.getContext());
54 // Find calloc(i64, i64) or calloc(i32, i32).
55 callocFunc = M.getFunction("calloc");
57 const FunctionType *Ty = callocFunc->getFunctionType();
59 std::vector<const Type*> args, args2;
60 args.push_back(Type::getInt64Ty(M.getContext()));
61 args.push_back(Type::getInt64Ty(M.getContext()));
62 args2.push_back(Type::getInt32Ty(M.getContext()));
63 args2.push_back(Type::getInt32Ty(M.getContext()));
64 const FunctionType *Calloc1Type =
65 FunctionType::get(PTy, args, false);
66 const FunctionType *Calloc2Type =
67 FunctionType::get(PTy, args2, false);
68 if (Ty != Calloc1Type && Ty != Calloc2Type)
69 callocFunc = 0; // Give up
72 // Find realloc(i8*, i64) or realloc(i8*, i32).
73 reallocFunc = M.getFunction("realloc");
75 const FunctionType *Ty = reallocFunc->getFunctionType();
76 std::vector<const Type*> args, args2;
78 args.push_back(Type::getInt64Ty(M.getContext()));
80 args2.push_back(Type::getInt32Ty(M.getContext()));
82 const FunctionType *Realloc1Type =
83 FunctionType::get(PTy, args, false);
84 const FunctionType *Realloc2Type =
85 FunctionType::get(PTy, args2, false);
86 if (Ty != Realloc1Type && Ty != Realloc2Type)
87 reallocFunc = 0; // Give up
92 // Calculates the number of elements allocated for pointer P,
93 // the type of the element is stored in Ty.
94 const SCEV *PointerTracking::computeAllocationCount(Value *P,
95 const Type *&Ty) const {
96 Value *V = P->stripPointerCasts();
97 if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
98 Value *arraySize = AI->getArraySize();
99 Ty = AI->getAllocatedType();
100 // arraySize elements of type Ty.
101 return SE->getSCEV(arraySize);
104 if (CallInst *CI = extractMallocCall(V)) {
105 Value *arraySize = getMallocArraySize(CI, TD);
106 const Type* AllocTy = getMallocAllocatedType(CI);
107 if (!AllocTy || !arraySize) return SE->getCouldNotCompute();
109 // arraySize elements of type Ty.
110 return SE->getSCEV(arraySize);
113 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
114 if (GV->hasDefinitiveInitializer()) {
115 Constant *C = GV->getInitializer();
116 if (const ArrayType *ATy = dyn_cast<ArrayType>(C->getType())) {
117 Ty = ATy->getElementType();
118 return SE->getConstant(Type::getInt32Ty(P->getContext()),
119 ATy->getNumElements());
123 return SE->getConstant(Type::getInt32Ty(P->getContext()), 1);
124 //TODO: implement more tracking for globals
127 if (CallInst *CI = dyn_cast<CallInst>(V)) {
129 Function *F = dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
130 const Loop *L = LI->getLoopFor(CI->getParent());
131 if (F == callocFunc) {
132 Ty = Type::getInt8Ty(P->getContext());
133 // calloc allocates arg0*arg1 bytes.
134 return SE->getSCEVAtScope(SE->getMulExpr(SE->getSCEV(CS.getArgument(0)),
135 SE->getSCEV(CS.getArgument(1))),
137 } else if (F == reallocFunc) {
138 Ty = Type::getInt8Ty(P->getContext());
139 // realloc allocates arg1 bytes.
140 return SE->getSCEVAtScope(CS.getArgument(1), L);
144 return SE->getCouldNotCompute();
147 // Calculates the number of elements of type Ty allocated for P.
148 const SCEV *PointerTracking::computeAllocationCountForType(Value *P,
151 const Type *elementTy;
152 const SCEV *Count = computeAllocationCount(P, elementTy);
153 if (isa<SCEVCouldNotCompute>(Count))
158 if (!TD) // need TargetData from this point forward
159 return SE->getCouldNotCompute();
161 uint64_t elementSize = TD->getTypeAllocSize(elementTy);
162 uint64_t wantSize = TD->getTypeAllocSize(Ty);
163 if (elementSize == wantSize)
165 if (elementSize % wantSize) //fractional counts not possible
166 return SE->getCouldNotCompute();
167 return SE->getMulExpr(Count, SE->getConstant(Count->getType(),
168 elementSize/wantSize));
171 const SCEV *PointerTracking::getAllocationElementCount(Value *V) const {
172 // We only deal with pointers.
173 const PointerType *PTy = cast<PointerType>(V->getType());
174 return computeAllocationCountForType(V, PTy->getElementType());
177 const SCEV *PointerTracking::getAllocationSizeInBytes(Value *V) const {
178 return computeAllocationCountForType(V, Type::getInt8Ty(V->getContext()));
181 // Helper for isLoopGuardedBy that checks the swapped and inverted predicate too
182 enum SolverResult PointerTracking::isLoopGuardedBy(const Loop *L,
185 const SCEV *B) const {
186 if (SE->isLoopEntryGuardedByCond(L, Pred, A, B))
188 Pred = ICmpInst::getSwappedPredicate(Pred);
189 if (SE->isLoopEntryGuardedByCond(L, Pred, B, A))
192 Pred = ICmpInst::getInversePredicate(Pred);
193 if (SE->isLoopEntryGuardedByCond(L, Pred, B, A))
195 Pred = ICmpInst::getSwappedPredicate(Pred);
196 if (SE->isLoopEntryGuardedByCond(L, Pred, A, B))
201 enum SolverResult PointerTracking::checkLimits(const SCEV *Offset,
205 //FIXME: merge implementation
209 void PointerTracking::getPointerOffset(Value *Pointer, Value *&Base,
211 const SCEV *&Offset) const
213 Pointer = Pointer->stripPointerCasts();
214 Base = Pointer->getUnderlyingObject();
215 Limit = getAllocationSizeInBytes(Base);
216 if (isa<SCEVCouldNotCompute>(Limit)) {
222 Offset = SE->getMinusSCEV(SE->getSCEV(Pointer), SE->getSCEV(Base));
223 if (isa<SCEVCouldNotCompute>(Offset)) {
229 void PointerTracking::print(raw_ostream &OS, const Module* M) const {
230 // Calling some PT methods may cause caches to be updated, however
231 // this should be safe for the same reason its safe for SCEV.
232 PointerTracking &PT = *const_cast<PointerTracking*>(this);
233 for (inst_iterator I=inst_begin(*FF), E=inst_end(*FF); I != E; ++I) {
234 if (!I->getType()->isPointerTy())
237 const SCEV *Limit, *Offset;
238 getPointerOffset(&*I, Base, Limit, Offset);
243 const SCEV *S = getAllocationElementCount(Base);
244 OS << *Base << " ==> " << *S << " elements, ";
245 OS << *Limit << " bytes allocated\n";
248 OS << &*I << " -- base: " << *Base;
249 OS << " offset: " << *Offset;
251 enum SolverResult res = PT.checkLimits(Offset, Limit, I->getParent());
254 OS << " always safe\n";
257 OS << " always unsafe\n";
260 OS << " <<unknown>>\n";
266 static RegisterPass<PointerTracking> X("pointertracking",
267 "Track pointer bounds", false, true);