lib/Analysis/PointerTracking.cpp

   1 //===- PointerTracking.cpp - Pointer Bounds Tracking ------------*- C++ -*-===//
   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 file implements tracking of pointer bounds.
  11 //
  12 //===----------------------------------------------------------------------===//
  13 #include "llvm/Analysis/ConstantFolding.h"
  14 #include "llvm/Analysis/Dominators.h"
  15 #include "llvm/Analysis/LoopInfo.h"
  16 #include "llvm/Analysis/MemoryBuiltins.h"
  17 #include "llvm/Analysis/PointerTracking.h"
  18 #include "llvm/Analysis/ScalarEvolution.h"
  19 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  20 #include "llvm/Constants.h"
  21 #include "llvm/Module.h"
  22 #include "llvm/Value.h"
  23 #include "llvm/Support/CallSite.h"
  24 #include "llvm/Support/InstIterator.h"
  25 #include "llvm/Support/raw_ostream.h"
  26 #include "llvm/Target/TargetData.h"
  27 using namespace llvm;
  28
  29 char PointerTracking::ID = 0;
  30 PointerTracking::PointerTracking() : FunctionPass(&ID) {}
  31
  32 bool PointerTracking::runOnFunction(Function &F) {
  33   predCache.clear();
  34   assert(analyzing.empty());
  35   FF = &F;
  36   TD = getAnalysisIfAvailable<TargetData>();
  37   SE = &getAnalysis<ScalarEvolution>();
  38   LI = &getAnalysis<LoopInfo>();
  39   DT = &getAnalysis<DominatorTree>();
  40   return false;
  41 }
  42
  43 void PointerTracking::getAnalysisUsage(AnalysisUsage &AU) const {
  44   AU.addRequiredTransitive<DominatorTree>();
  45   AU.addRequiredTransitive<LoopInfo>();
  46   AU.addRequiredTransitive<ScalarEvolution>();
  47   AU.setPreservesAll();
  48 }
  49
  50 bool PointerTracking::doInitialization(Module &M) {
  51   const Type *PTy = Type::getInt8PtrTy(M.getContext());
  52
  53   // Find calloc(i64, i64) or calloc(i32, i32).
  54   callocFunc = M.getFunction("calloc");
  55   if (callocFunc) {
  56     const FunctionType *Ty = callocFunc->getFunctionType();
  57
  58     std::vector<const Type*> args, args2;
  59     args.push_back(Type::getInt64Ty(M.getContext()));
  60     args.push_back(Type::getInt64Ty(M.getContext()));
  61     args2.push_back(Type::getInt32Ty(M.getContext()));
  62     args2.push_back(Type::getInt32Ty(M.getContext()));
  63     const FunctionType *Calloc1Type =
  64       FunctionType::get(PTy, args, false);
  65     const FunctionType *Calloc2Type =
  66       FunctionType::get(PTy, args2, false);
  67     if (Ty != Calloc1Type && Ty != Calloc2Type)
  68       callocFunc = 0; // Give up
  69   }
  70
  71   // Find realloc(i8*, i64) or realloc(i8*, i32).
  72   reallocFunc = M.getFunction("realloc");
  73   if (reallocFunc) {
  74     const FunctionType *Ty = reallocFunc->getFunctionType();
  75     std::vector<const Type*> args, args2;
  76     args.push_back(PTy);
  77     args.push_back(Type::getInt64Ty(M.getContext()));
  78     args2.push_back(PTy);
  79     args2.push_back(Type::getInt32Ty(M.getContext()));
  80
  81     const FunctionType *Realloc1Type =
  82       FunctionType::get(PTy, args, false);
  83     const FunctionType *Realloc2Type =
  84       FunctionType::get(PTy, args2, false);
  85     if (Ty != Realloc1Type && Ty != Realloc2Type)
  86       reallocFunc = 0; // Give up
  87   }
  88   return false;
  89 }
  90
  91 // Calculates the number of elements allocated for pointer P,
  92 // the type of the element is stored in Ty.
  93 const SCEV *PointerTracking::computeAllocationCount(Value *P,
  94                                                     const Type *&Ty) const {
  95   Value *V = P->stripPointerCasts();
  96   if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
  97     Value *arraySize = AI->getArraySize();
  98     Ty = AI->getAllocatedType();
  99     // arraySize elements of type Ty.
 100     return SE->getSCEV(arraySize);
 101   }
 102
 103   if (CallInst *CI = extractMallocCall(V)) {
 104     Value *arraySize = getMallocArraySize(CI, P->getContext(), TD);
 105     const Type* AllocTy = getMallocAllocatedType(CI);
 106     if (!AllocTy || !arraySize) return SE->getCouldNotCompute();
 107     Ty = AllocTy;
 108     // arraySize elements of type Ty.
 109     return SE->getSCEV(arraySize);
 110   }
 111
 112   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
 113     if (GV->hasDefinitiveInitializer()) {
 114       Constant *C = GV->getInitializer();
 115       if (const ArrayType *ATy = dyn_cast<ArrayType>(C->getType())) {
 116         Ty = ATy->getElementType();
 117         return SE->getConstant(Type::getInt32Ty(P->getContext()),
 118                                ATy->getNumElements());
 119       }
 120     }
 121     Ty = GV->getType();
 122     return SE->getConstant(Type::getInt32Ty(P->getContext()), 1);
 123     //TODO: implement more tracking for globals
 124   }
 125
 126   if (CallInst *CI = dyn_cast<CallInst>(V)) {
 127     CallSite CS(CI);
 128     Function *F = dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
 129     const Loop *L = LI->getLoopFor(CI->getParent());
 130     if (F == callocFunc) {
 131       Ty = Type::getInt8Ty(P->getContext());
 132       // calloc allocates arg0*arg1 bytes.
 133       return SE->getSCEVAtScope(SE->getMulExpr(SE->getSCEV(CS.getArgument(0)),
 134                                                SE->getSCEV(CS.getArgument(1))),
 135                                 L);
 136     } else if (F == reallocFunc) {
 137       Ty = Type::getInt8Ty(P->getContext());
 138       // realloc allocates arg1 bytes.
 139       return SE->getSCEVAtScope(CS.getArgument(1), L);
 140     }
 141   }
 142
 143   return SE->getCouldNotCompute();
 144 }
 145
 146 // Calculates the number of elements of type Ty allocated for P.
 147 const SCEV *PointerTracking::computeAllocationCountForType(Value *P,
 148                                                            const Type *Ty)
 149   const {
 150     const Type *elementTy;
 151     const SCEV *Count = computeAllocationCount(P, elementTy);
 152     if (isa<SCEVCouldNotCompute>(Count))
 153       return Count;
 154     if (elementTy == Ty)
 155       return Count;
 156
 157     if (!TD) // need TargetData from this point forward
 158       return SE->getCouldNotCompute();
 159
 160     uint64_t elementSize = TD->getTypeAllocSize(elementTy);
 161     uint64_t wantSize = TD->getTypeAllocSize(Ty);
 162     if (elementSize == wantSize)
 163       return Count;
 164     if (elementSize % wantSize) //fractional counts not possible
 165       return SE->getCouldNotCompute();
 166     return SE->getMulExpr(Count, SE->getConstant(Count->getType(),
 167                                                  elementSize/wantSize));
 168 }
 169
 170 const SCEV *PointerTracking::getAllocationElementCount(Value *V) const {
 171   // We only deal with pointers.
 172   const PointerType *PTy = cast<PointerType>(V->getType());
 173   return computeAllocationCountForType(V, PTy->getElementType());
 174 }
 175
 176 const SCEV *PointerTracking::getAllocationSizeInBytes(Value *V) const {
 177   return computeAllocationCountForType(V, Type::getInt8Ty(V->getContext()));
 178 }
 179
 180 // Helper for isLoopGuardedBy that checks the swapped and inverted predicate too
 181 enum SolverResult PointerTracking::isLoopGuardedBy(const Loop *L,
 182                                                    Predicate Pred,
 183                                                    const SCEV *A,
 184                                                    const SCEV *B) const {
 185   if (SE->isLoopGuardedByCond(L, Pred, A, B))
 186     return AlwaysTrue;
 187   Pred = ICmpInst::getSwappedPredicate(Pred);
 188   if (SE->isLoopGuardedByCond(L, Pred, B, A))
 189     return AlwaysTrue;
 190
 191   Pred = ICmpInst::getInversePredicate(Pred);
 192   if (SE->isLoopGuardedByCond(L, Pred, B, A))
 193     return AlwaysFalse;
 194   Pred = ICmpInst::getSwappedPredicate(Pred);
 195   if (SE->isLoopGuardedByCond(L, Pred, A, B))
 196     return AlwaysTrue;
 197   return Unknown;
 198 }
 199
 200 enum SolverResult PointerTracking::checkLimits(const SCEV *Offset,
 201                                                const SCEV *Limit,
 202                                                BasicBlock *BB)
 203 {
 204   //FIXME: merge implementation
 205   return Unknown;
 206 }
 207
 208 void PointerTracking::getPointerOffset(Value *Pointer, Value *&Base,
 209                                        const SCEV *&Limit,
 210                                        const SCEV *&Offset) const
 211 {
 212     Pointer = Pointer->stripPointerCasts();
 213     Base = Pointer->getUnderlyingObject();
 214     Limit = getAllocationSizeInBytes(Base);
 215     if (isa<SCEVCouldNotCompute>(Limit)) {
 216       Base = 0;
 217       Offset = Limit;
 218       return;
 219     }
 220
 221     Offset = SE->getMinusSCEV(SE->getSCEV(Pointer), SE->getSCEV(Base));
 222     if (isa<SCEVCouldNotCompute>(Offset)) {
 223       Base = 0;
 224       Limit = Offset;
 225     }
 226 }
 227
 228 void PointerTracking::print(raw_ostream &OS, const Module* M) const {
 229   // Calling some PT methods may cause caches to be updated, however
 230   // this should be safe for the same reason its safe for SCEV.
 231   PointerTracking &PT = *const_cast<PointerTracking*>(this);
 232   for (inst_iterator I=inst_begin(*FF), E=inst_end(*FF); I != E; ++I) {
 233     if (!isa<PointerType>(I->getType()))
 234       continue;
 235     Value *Base;
 236     const SCEV *Limit, *Offset;
 237     getPointerOffset(&*I, Base, Limit, Offset);
 238     if (!Base)
 239       continue;
 240
 241     if (Base == &*I) {
 242       const SCEV *S = getAllocationElementCount(Base);
 243       OS << *Base << " ==> " << *S << " elements, ";
 244       OS << *Limit << " bytes allocated\n";
 245       continue;
 246     }
 247     OS << &*I << " -- base: " << *Base;
 248     OS << " offset: " << *Offset;
 249
 250     enum SolverResult res = PT.checkLimits(Offset, Limit, I->getParent());
 251     switch (res) {
 252     case AlwaysTrue:
 253       OS << " always safe\n";
 254       break;
 255     case AlwaysFalse:
 256       OS << " always unsafe\n";
 257       break;
 258     case Unknown:
 259       OS << " <<unknown>>\n";
 260       break;
 261     }
 262   }
 263 }
 264
 265 static RegisterPass<PointerTracking> X("pointertracking",
 266                                        "Track pointer bounds", false, true);