LLVM API Documentation
00001 //===- PointerTracking.cpp - Pointer Bounds Tracking ------------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements tracking of pointer bounds. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 #include "llvm/Analysis/ConstantFolding.h" 00014 #include "llvm/Analysis/Dominators.h" 00015 #include "llvm/Analysis/LoopInfo.h" 00016 #include "llvm/Analysis/PointerTracking.h" 00017 #include "llvm/Analysis/ScalarEvolution.h" 00018 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 00019 #include "llvm/Constants.h" 00020 #include "llvm/Module.h" 00021 #include "llvm/Value.h" 00022 #include "llvm/Support/CallSite.h" 00023 #include "llvm/Support/InstIterator.h" 00024 #include "llvm/Support/raw_ostream.h" 00025 #include "llvm/Target/TargetData.h" 00026 00027 namespace llvm { 00028 char PointerTracking::ID=0; 00029 PointerTracking::PointerTracking() : FunctionPass(&ID) {} 00030 00031 bool PointerTracking::runOnFunction(Function &F) { 00032 predCache.clear(); 00033 assert(analyzing.empty()); 00034 FF = &F; 00035 TD = getAnalysisIfAvailable<TargetData>(); 00036 SE = &getAnalysis<ScalarEvolution>(); 00037 LI = &getAnalysis<LoopInfo>(); 00038 DT = &getAnalysis<DominatorTree>(); 00039 return false; 00040 } 00041 00042 void PointerTracking::getAnalysisUsage(AnalysisUsage &AU) const { 00043 AU.addRequiredTransitive<DominatorTree>(); 00044 AU.addRequiredTransitive<LoopInfo>(); 00045 AU.addRequiredTransitive<ScalarEvolution>(); 00046 AU.setPreservesAll(); 00047 } 00048 00049 bool PointerTracking::doInitialization(Module &M) { 00050 const Type *PTy = PointerType::getUnqual(Type::getInt8Ty(M.getContext())); 00051 00052 // Find calloc(i64, i64) or calloc(i32, i32). 00053 callocFunc = M.getFunction("calloc"); 00054 if (callocFunc) { 00055 const FunctionType *Ty = callocFunc->getFunctionType(); 00056 00057 std::vector<const Type*> args, args2; 00058 args.push_back(Type::getInt64Ty(M.getContext())); 00059 args.push_back(Type::getInt64Ty(M.getContext())); 00060 args2.push_back(Type::getInt32Ty(M.getContext())); 00061 args2.push_back(Type::getInt32Ty(M.getContext())); 00062 const FunctionType *Calloc1Type = 00063 FunctionType::get(PTy, args, false); 00064 const FunctionType *Calloc2Type = 00065 FunctionType::get(PTy, args2, false); 00066 if (Ty != Calloc1Type && Ty != Calloc2Type) 00067 callocFunc = 0; // Give up 00068 } 00069 00070 // Find realloc(i8*, i64) or realloc(i8*, i32). 00071 reallocFunc = M.getFunction("realloc"); 00072 if (reallocFunc) { 00073 const FunctionType *Ty = reallocFunc->getFunctionType(); 00074 std::vector<const Type*> args, args2; 00075 args.push_back(PTy); 00076 args.push_back(Type::getInt64Ty(M.getContext())); 00077 args2.push_back(PTy); 00078 args2.push_back(Type::getInt32Ty(M.getContext())); 00079 00080 const FunctionType *Realloc1Type = 00081 FunctionType::get(PTy, args, false); 00082 const FunctionType *Realloc2Type = 00083 FunctionType::get(PTy, args2, false); 00084 if (Ty != Realloc1Type && Ty != Realloc2Type) 00085 reallocFunc = 0; // Give up 00086 } 00087 return false; 00088 } 00089 00090 // Calculates the number of elements allocated for pointer P, 00091 // the type of the element is stored in Ty. 00092 const SCEV *PointerTracking::computeAllocationCount(Value *P, 00093 const Type *&Ty) const { 00094 Value *V = P->stripPointerCasts(); 00095 if (AllocationInst *AI = dyn_cast<AllocationInst>(V)) { 00096 Value *arraySize = AI->getArraySize(); 00097 Ty = AI->getAllocatedType(); 00098 // arraySize elements of type Ty. 00099 return SE->getSCEV(arraySize); 00100 } 00101 00102 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 00103 if (GV->hasDefinitiveInitializer()) { 00104 Constant *C = GV->getInitializer(); 00105 if (const ArrayType *ATy = dyn_cast<ArrayType>(C->getType())) { 00106 Ty = ATy->getElementType(); 00107 return SE->getConstant(Type::getInt32Ty(P->getContext()), 00108 ATy->getNumElements()); 00109 } 00110 } 00111 Ty = GV->getType(); 00112 return SE->getConstant(Type::getInt32Ty(P->getContext()), 1); 00113 //TODO: implement more tracking for globals 00114 } 00115 00116 if (CallInst *CI = dyn_cast<CallInst>(V)) { 00117 CallSite CS(CI); 00118 Function *F = dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts()); 00119 const Loop *L = LI->getLoopFor(CI->getParent()); 00120 if (F == callocFunc) { 00121 Ty = Type::getInt8Ty(P->getContext()); 00122 // calloc allocates arg0*arg1 bytes. 00123 return SE->getSCEVAtScope(SE->getMulExpr(SE->getSCEV(CS.getArgument(0)), 00124 SE->getSCEV(CS.getArgument(1))), 00125 L); 00126 } else if (F == reallocFunc) { 00127 Ty = Type::getInt8Ty(P->getContext()); 00128 // realloc allocates arg1 bytes. 00129 return SE->getSCEVAtScope(CS.getArgument(1), L); 00130 } 00131 } 00132 00133 return SE->getCouldNotCompute(); 00134 } 00135 00136 // Calculates the number of elements of type Ty allocated for P. 00137 const SCEV *PointerTracking::computeAllocationCountForType(Value *P, 00138 const Type *Ty) 00139 const { 00140 const Type *elementTy; 00141 const SCEV *Count = computeAllocationCount(P, elementTy); 00142 if (isa<SCEVCouldNotCompute>(Count)) 00143 return Count; 00144 if (elementTy == Ty) 00145 return Count; 00146 00147 if (!TD) // need TargetData from this point forward 00148 return SE->getCouldNotCompute(); 00149 00150 uint64_t elementSize = TD->getTypeAllocSize(elementTy); 00151 uint64_t wantSize = TD->getTypeAllocSize(Ty); 00152 if (elementSize == wantSize) 00153 return Count; 00154 if (elementSize % wantSize) //fractional counts not possible 00155 return SE->getCouldNotCompute(); 00156 return SE->getMulExpr(Count, SE->getConstant(Count->getType(), 00157 elementSize/wantSize)); 00158 } 00159 00160 const SCEV *PointerTracking::getAllocationElementCount(Value *V) const { 00161 // We only deal with pointers. 00162 const PointerType *PTy = cast<PointerType>(V->getType()); 00163 return computeAllocationCountForType(V, PTy->getElementType()); 00164 } 00165 00166 const SCEV *PointerTracking::getAllocationSizeInBytes(Value *V) const { 00167 return computeAllocationCountForType(V, Type::getInt8Ty(V->getContext())); 00168 } 00169 00170 // Helper for isLoopGuardedBy that checks the swapped and inverted predicate too 00171 enum SolverResult PointerTracking::isLoopGuardedBy(const Loop *L, 00172 Predicate Pred, 00173 const SCEV *A, 00174 const SCEV *B) const { 00175 if (SE->isLoopGuardedByCond(L, Pred, A, B)) 00176 return AlwaysTrue; 00177 Pred = ICmpInst::getSwappedPredicate(Pred); 00178 if (SE->isLoopGuardedByCond(L, Pred, B, A)) 00179 return AlwaysTrue; 00180 00181 Pred = ICmpInst::getInversePredicate(Pred); 00182 if (SE->isLoopGuardedByCond(L, Pred, B, A)) 00183 return AlwaysFalse; 00184 Pred = ICmpInst::getSwappedPredicate(Pred); 00185 if (SE->isLoopGuardedByCond(L, Pred, A, B)) 00186 return AlwaysTrue; 00187 return Unknown; 00188 } 00189 00190 enum SolverResult PointerTracking::checkLimits(const SCEV *Offset, 00191 const SCEV *Limit, 00192 BasicBlock *BB) 00193 { 00194 //FIXME: merge implementation 00195 return Unknown; 00196 } 00197 00198 void PointerTracking::getPointerOffset(Value *Pointer, Value *&Base, 00199 const SCEV *&Limit, 00200 const SCEV *&Offset) const 00201 { 00202 Pointer = Pointer->stripPointerCasts(); 00203 Base = Pointer->getUnderlyingObject(); 00204 Limit = getAllocationSizeInBytes(Base); 00205 if (isa<SCEVCouldNotCompute>(Limit)) { 00206 Base = 0; 00207 Offset = Limit; 00208 return; 00209 } 00210 00211 Offset = SE->getMinusSCEV(SE->getSCEV(Pointer), SE->getSCEV(Base)); 00212 if (isa<SCEVCouldNotCompute>(Offset)) { 00213 Base = 0; 00214 Limit = Offset; 00215 } 00216 } 00217 00218 void PointerTracking::print(raw_ostream &OS, const Module* M) const { 00219 // Calling some PT methods may cause caches to be updated, however 00220 // this should be safe for the same reason its safe for SCEV. 00221 PointerTracking &PT = *const_cast<PointerTracking*>(this); 00222 for (inst_iterator I=inst_begin(*FF), E=inst_end(*FF); I != E; ++I) { 00223 if (!isa<PointerType>(I->getType())) 00224 continue; 00225 Value *Base; 00226 const SCEV *Limit, *Offset; 00227 getPointerOffset(&*I, Base, Limit, Offset); 00228 if (!Base) 00229 continue; 00230 00231 if (Base == &*I) { 00232 const SCEV *S = getAllocationElementCount(Base); 00233 OS << *Base << " ==> " << *S << " elements, "; 00234 OS << *Limit << " bytes allocated\n"; 00235 continue; 00236 } 00237 OS << &*I << " -- base: " << *Base; 00238 OS << " offset: " << *Offset; 00239 00240 enum SolverResult res = PT.checkLimits(Offset, Limit, I->getParent()); 00241 switch (res) { 00242 case AlwaysTrue: 00243 OS << " always safe\n"; 00244 break; 00245 case AlwaysFalse: 00246 OS << " always unsafe\n"; 00247 break; 00248 case Unknown: 00249 OS << " <<unknown>>\n"; 00250 break; 00251 } 00252 } 00253 } 00254 00255 void PointerTracking::print(std::ostream &o, const Module* M) const { 00256 raw_os_ostream OS(o); 00257 print(OS, M); 00258 } 00259 00260 static RegisterPass<PointerTracking> X("pointertracking", 00261 "Track pointer bounds", false, true); 00262 }