LLVM API Documentation

PointerTracking.cpp

Go to the documentation of this file.
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 }