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 Value *PointerTracking::computeAllocationCountValue(Value *P, const Type *&Ty) const
 148 {
 149   Value *V = P->stripPointerCasts();
 150   if (AllocaInst *AI = dyn_cast<AllocaInst>(V)) {
 151     Ty = AI->getAllocatedType();
 152     // arraySize elements of type Ty.
 153     return AI->getArraySize();
 154   }
 155
 156   if (CallInst *CI = extractMallocCall(V)) {
 157     Ty = getMallocAllocatedType(CI);
 158     if (!Ty)
 159       return 0;
 160     Value *arraySize = getMallocArraySize(CI, TD);
 161     if (!arraySize) {
 162       Ty = Type::getInt8Ty(P->getContext());
 163       return CI->getArgOperand(0);
 164     }
 165     // arraySize elements of type Ty.
 166     return arraySize;
 167   }
 168
 169   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
 170     if (GV->hasDefinitiveInitializer()) {
 171       Constant *C = GV->getInitializer();
 172       if (const ArrayType *ATy = dyn_cast<ArrayType>(C->getType())) {
 173         Ty = ATy->getElementType();
 174         return ConstantInt::get(Type::getInt32Ty(P->getContext()),
 175                                ATy->getNumElements());
 176       }
 177     }
 178     Ty = cast<PointerType>(GV->getType())->getElementType();
 179     return ConstantInt::get(Type::getInt32Ty(P->getContext()), 1);
 180     //TODO: implement more tracking for globals
 181   }
 182
 183   if (CallInst *CI = dyn_cast<CallInst>(V)) {
 184     CallSite CS(CI);
 185     Function *F = dyn_cast<Function>(CS.getCalledValue()->stripPointerCasts());
 186     if (F == reallocFunc) {
 187       Ty = Type::getInt8Ty(P->getContext());
 188       // realloc allocates arg1 bytes.
 189       return CS.getArgument(1);
 190     }
 191   }
 192
 193   return 0;
 194 }
 195
 196 // Calculates the number of elements of type Ty allocated for P.
 197 const SCEV *PointerTracking::computeAllocationCountForType(Value *P,
 198                                                            const Type *Ty)
 199   const {
 200     const Type *elementTy;
 201     const SCEV *Count = computeAllocationCount(P, elementTy);
 202     if (isa<SCEVCouldNotCompute>(Count))
 203       return Count;
 204     if (elementTy == Ty)
 205       return Count;
 206
 207     if (!TD) // need TargetData from this point forward
 208       return SE->getCouldNotCompute();
 209
 210     uint64_t elementSize = TD->getTypeAllocSize(elementTy);
 211     uint64_t wantSize = TD->getTypeAllocSize(Ty);
 212     if (elementSize == wantSize)
 213       return Count;
 214     if (elementSize % wantSize) //fractional counts not possible
 215       return SE->getCouldNotCompute();
 216     return SE->getMulExpr(Count, SE->getConstant(Count->getType(),
 217                                                  elementSize/wantSize));
 218 }
 219
 220 const SCEV *PointerTracking::getAllocationElementCount(Value *V) const {
 221   // We only deal with pointers.
 222   const PointerType *PTy = cast<PointerType>(V->getType());
 223   return computeAllocationCountForType(V, PTy->getElementType());
 224 }
 225
 226 const SCEV *PointerTracking::getAllocationSizeInBytes(Value *V) const {
 227   return computeAllocationCountForType(V, Type::getInt8Ty(V->getContext()));
 228 }
 229
 230 // Helper for isLoopGuardedBy that checks the swapped and inverted predicate too
 231 enum SolverResult PointerTracking::isLoopGuardedBy(const Loop *L,
 232                                                    Predicate Pred,
 233                                                    const SCEV *A,
 234                                                    const SCEV *B) const {
 235   if (SE->isLoopEntryGuardedByCond(L, Pred, A, B))
 236     return AlwaysTrue;
 237   Pred = ICmpInst::getSwappedPredicate(Pred);
 238   if (SE->isLoopEntryGuardedByCond(L, Pred, B, A))
 239     return AlwaysTrue;
 240
 241   Pred = ICmpInst::getInversePredicate(Pred);
 242   if (SE->isLoopEntryGuardedByCond(L, Pred, B, A))
 243     return AlwaysFalse;
 244   Pred = ICmpInst::getSwappedPredicate(Pred);
 245   if (SE->isLoopEntryGuardedByCond(L, Pred, A, B))
 246     return AlwaysTrue;
 247   return Unknown;
 248 }
 249
 250 enum SolverResult PointerTracking::checkLimits(const SCEV *Offset,
 251                                                const SCEV *Limit,
 252                                                BasicBlock *BB)
 253 {
 254   //FIXME: merge implementation
 255   return Unknown;
 256 }
 257
 258 void PointerTracking::getPointerOffset(Value *Pointer, Value *&Base,
 259                                        const SCEV *&Limit,
 260                                        const SCEV *&Offset) const
 261 {
 262     Pointer = Pointer->stripPointerCasts();
 263     Base = Pointer->getUnderlyingObject();
 264     Limit = getAllocationSizeInBytes(Base);
 265     if (isa<SCEVCouldNotCompute>(Limit)) {
 266       Base = 0;
 267       Offset = Limit;
 268       return;
 269     }
 270
 271     Offset = SE->getMinusSCEV(SE->getSCEV(Pointer), SE->getSCEV(Base));
 272     if (isa<SCEVCouldNotCompute>(Offset)) {
 273       Base = 0;
 274       Limit = Offset;
 275     }
 276 }
 277
 278 void PointerTracking::print(raw_ostream &OS, const Module* M) const {
 279   // Calling some PT methods may cause caches to be updated, however
 280   // this should be safe for the same reason its safe for SCEV.
 281   PointerTracking &PT = *const_cast<PointerTracking*>(this);
 282   for (inst_iterator I=inst_begin(*FF), E=inst_end(*FF); I != E; ++I) {
 283     if (!I->getType()->isPointerTy())
 284       continue;
 285     Value *Base;
 286     const SCEV *Limit, *Offset;
 287     getPointerOffset(&*I, Base, Limit, Offset);
 288     if (!Base)
 289       continue;
 290
 291     if (Base == &*I) {
 292       const SCEV *S = getAllocationElementCount(Base);
 293       OS << *Base << " ==> " << *S << " elements, ";
 294       OS << *Limit << " bytes allocated\n";
 295       continue;
 296     }
 297     OS << &*I << " -- base: " << *Base;
 298     OS << " offset: " << *Offset;
 299
 300     enum SolverResult res = PT.checkLimits(Offset, Limit, I->getParent());
 301     switch (res) {
 302     case AlwaysTrue:
 303       OS << " always safe\n";
 304       break;
 305     case AlwaysFalse:
 306       OS << " always unsafe\n";
 307       break;
 308     case Unknown:
 309       OS << " <<unknown>>\n";
 310       break;
 311     }
 312   }
 313 }
 314
 315 INITIALIZE_PASS(PointerTracking, "pointertracking",
 316                 "Track pointer bounds", false, true);