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
  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"
  28 using namespace llvm;
  29
  30 char PointerTracking::ID = 0;
  31 PointerTracking::PointerTracking() : FunctionPass(&ID) {}
  32
  33 bool PointerTracking::runOnFunction(Function &F) {
  34   predCache.clear();
  35   assert(analyzing.empty());
  36   FF = &F;
  37   TD = getAnalysisIfAvailable<TargetData>();
  38   SE = &getAnalysis<ScalarEvolution>();
  39   LI = &getAnalysis<LoopInfo>();
  40   DT = &getAnalysis<DominatorTree>();
  41   return false;
  42 }
  43
  44 void PointerTracking::getAnalysisUsage(AnalysisUsage &AU) const {
  45   AU.addRequiredTransitive<DominatorTree>();
  46   AU.addRequiredTransitive<LoopInfo>();
  47   AU.addRequiredTransitive<ScalarEvolution>();
  48   AU.setPreservesAll();
  49 }
  50
  51 bool PointerTracking::doInitialization(Module &M) {
  52   const Type *PTy = Type::getInt8PtrTy(M.getContext());
  53
  54   // Find calloc(i64, i64) or calloc(i32, i32).
  55   callocFunc = M.getFunction("calloc");
  56   if (callocFunc) {
  57     const FunctionType *Ty = callocFunc->getFunctionType();
  58
  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
  70   }
  71
  72   // Find realloc(i8*, i64) or realloc(i8*, i32).
  73   reallocFunc = M.getFunction("realloc");
  74   if (reallocFunc) {
  75     const FunctionType *Ty = reallocFunc->getFunctionType();
  76     std::vector<const Type*> args, args2;
  77     args.push_back(PTy);
  78     args.push_back(Type::getInt64Ty(M.getContext()));
  79     args2.push_back(PTy);
  80     args2.push_back(Type::getInt32Ty(M.getContext()));
  81
  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
  88   }
  89   return false;
  90 }
  91
  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);
 102   }
 103
 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();
 108     Ty = AllocTy;
 109     // arraySize elements of type Ty.
 110     return SE->getSCEV(arraySize);
 111   }
 112
 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());
 120       }
 121     }
 122     Ty = GV->getType();
 123     return SE->getConstant(Type::getInt32Ty(P->getContext()), 1);
 124     //TODO: implement more tracking for globals
 125   }
 126
 127   if (CallInst *CI = dyn_cast<CallInst>(V)) {
 128     CallSite CS(CI);
 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))),
 136                                 L);
 137     } else if (F == reallocFunc) {
 138       Ty = Type::getInt8Ty(P->getContext());
 139       // realloc allocates arg1 bytes.
 140       return SE->getSCEVAtScope(CS.getArgument(1), L);
 141     }
 142   }
 143
 144   return SE->getCouldNotCompute();
 145 }
 146
 147 // Calculates the number of elements of type Ty allocated for P.
 148 const SCEV *PointerTracking::computeAllocationCountForType(Value *P,
 149                                                            const Type *Ty)
 150   const {
 151     const Type *elementTy;
 152     const SCEV *Count = computeAllocationCount(P, elementTy);
 153     if (isa<SCEVCouldNotCompute>(Count))
 154       return Count;
 155     if (elementTy == Ty)
 156       return Count;
 157
 158     if (!TD) // need TargetData from this point forward
 159       return SE->getCouldNotCompute();
 160
 161     uint64_t elementSize = TD->getTypeAllocSize(elementTy);
 162     uint64_t wantSize = TD->getTypeAllocSize(Ty);
 163     if (elementSize == wantSize)
 164       return Count;
 165     if (elementSize % wantSize) //fractional counts not possible
 166       return SE->getCouldNotCompute();
 167     return SE->getMulExpr(Count, SE->getConstant(Count->getType(),
 168                                                  elementSize/wantSize));
 169 }
 170
 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());
 175 }
 176
 177 const SCEV *PointerTracking::getAllocationSizeInBytes(Value *V) const {
 178   return computeAllocationCountForType(V, Type::getInt8Ty(V->getContext()));
 179 }
 180
 181 // Helper for isLoopGuardedBy that checks the swapped and inverted predicate too
 182 enum SolverResult PointerTracking::isLoopGuardedBy(const Loop *L,
 183                                                    Predicate Pred,
 184                                                    const SCEV *A,
 185                                                    const SCEV *B) const {
 186   if (SE->isLoopEntryGuardedByCond(L, Pred, A, B))
 187     return AlwaysTrue;
 188   Pred = ICmpInst::getSwappedPredicate(Pred);
 189   if (SE->isLoopEntryGuardedByCond(L, Pred, B, A))
 190     return AlwaysTrue;
 191
 192   Pred = ICmpInst::getInversePredicate(Pred);
 193   if (SE->isLoopEntryGuardedByCond(L, Pred, B, A))
 194     return AlwaysFalse;
 195   Pred = ICmpInst::getSwappedPredicate(Pred);
 196   if (SE->isLoopEntryGuardedByCond(L, Pred, A, B))
 197     return AlwaysTrue;
 198   return Unknown;
 199 }
 200
 201 enum SolverResult PointerTracking::checkLimits(const SCEV *Offset,
 202                                                const SCEV *Limit,
 203                                                BasicBlock *BB)
 204 {
 205   //FIXME: merge implementation
 206   return Unknown;
 207 }
 208
 209 void PointerTracking::getPointerOffset(Value *Pointer, Value *&Base,
 210                                        const SCEV *&Limit,
 211                                        const SCEV *&Offset) const
 212 {
 213     Pointer = Pointer->stripPointerCasts();
 214     Base = Pointer->getUnderlyingObject();
 215     Limit = getAllocationSizeInBytes(Base);
 216     if (isa<SCEVCouldNotCompute>(Limit)) {
 217       Base = 0;
 218       Offset = Limit;
 219       return;
 220     }
 221
 222     Offset = SE->getMinusSCEV(SE->getSCEV(Pointer), SE->getSCEV(Base));
 223     if (isa<SCEVCouldNotCompute>(Offset)) {
 224       Base = 0;
 225       Limit = Offset;
 226     }
 227 }
 228
 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())
 235       continue;
 236     Value *Base;
 237     const SCEV *Limit, *Offset;
 238     getPointerOffset(&*I, Base, Limit, Offset);
 239     if (!Base)
 240       continue;
 241
 242     if (Base == &*I) {
 243       const SCEV *S = getAllocationElementCount(Base);
 244       OS << *Base << " ==> " << *S << " elements, ";
 245       OS << *Limit << " bytes allocated\n";
 246       continue;
 247     }
 248     OS << &*I << " -- base: " << *Base;
 249     OS << " offset: " << *Offset;
 250
 251     enum SolverResult res = PT.checkLimits(Offset, Limit, I->getParent());
 252     switch (res) {
 253     case AlwaysTrue:
 254       OS << " always safe\n";
 255       break;
 256     case AlwaysFalse:
 257       OS << " always unsafe\n";
 258       break;
 259     case Unknown:
 260       OS << " <<unknown>>\n";
 261       break;
 262     }
 263   }
 264 }
 265
 266 INITIALIZE_PASS(PointerTracking, "pointertracking",
 267                 "Track pointer bounds", false, true);