include/llvm/Analysis/PointerTracking.h

   1 //===- PointerTracking.h - 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 // It knows that the libc functions "calloc" and "realloc" allocate memory, thus
  12 // you should avoid using this pass if they mean something else for your
  13 // language.
  14 //
  15 // All methods assume that the pointer is not NULL, if it is then the returned
  16 // allocation size is wrong, and the result from checkLimits is wrong too.
  17 // It also assumes that pointers are valid, and that it is not analyzing a
  18 // use-after-free scenario.
  19 // Due to these limitations the "size" returned by these methods should be
  20 // considered as either 0 or the returned size.
  21 //
  22 // Another analysis pass should be used to find use-after-free/NULL dereference
  23 // bugs.
  24 //
  25 //===----------------------------------------------------------------------===//
  26
  27 #ifndef LLVM_ANALYSIS_POINTERTRACKING_H
  28 #define LLVM_ANALYSIS_POINTERTRACKING_H
  29
  30 #include "llvm/ADT/SmallSet.h"
  31 #include "llvm/Analysis/Dominators.h"
  32 #include "llvm/Instructions.h"
  33 #include "llvm/Pass.h"
  34 #include "llvm/Support/PredIteratorCache.h"
  35
  36 namespace llvm {
  37   class DominatorTree;
  38   class ScalarEvolution;
  39   class SCEV;
  40   class Loop;
  41   class LoopInfo;
  42   class TargetData;
  43
  44   // Result from solver, assuming pointer is not NULL,
  45   // and it is not a use-after-free situation.
  46   enum SolverResult {
  47     AlwaysFalse,// always false with above constraints
  48     AlwaysTrue,// always true with above constraints
  49     Unknown // it can sometimes be true, sometimes false, or it is undecided
  50   };
  51
  52   class PointerTracking : public FunctionPass {
  53   public:
  54     typedef ICmpInst::Predicate Predicate;
  55     static char ID;
  56     PointerTracking();
  57
  58     virtual bool doInitialization(Module &M);
  59
  60     // If this pointer directly points to an allocation, return
  61     // the number of elements of type Ty allocated.
  62     // Otherwise return CouldNotCompute.
  63     // Since allocations can fail by returning NULL, the real element count
  64     // for every allocation is either 0 or the value returned by this function.
  65     const SCEV *getAllocationElementCount(Value *P) const;
  66
  67     // Same as getAllocationSize() but returns size in bytes.
  68     // We consider one byte as 8 bits.
  69     const SCEV *getAllocationSizeInBytes(Value *V) const;
  70
  71     // Given a Pointer, determine a base pointer of known size, and an offset
  72     // therefrom.
  73     // When unable to determine, sets Base to NULL, and Limit/Offset to
  74     // CouldNotCompute.
  75     // BaseSize, and Offset are in bytes: Pointer == Base + Offset
  76     void getPointerOffset(Value *Pointer, Value *&Base, const SCEV *& BaseSize,
  77                           const SCEV *&Offset) const;
  78
  79     // Compares the 2 scalar evolution expressions according to predicate,
  80     // and if it can prove that the result is always true or always false
  81     // return AlwaysTrue/AlwaysFalse. Otherwise it returns Unknown.
  82     enum SolverResult compareSCEV(const SCEV *A, Predicate Pred, const SCEV *B,
  83                                   const Loop *L);
  84
  85     // Determines whether the condition LHS <Pred> RHS is sufficient
  86     // for the condition A <Pred> B to hold.
  87     // Currently only ULT/ULE is supported.
  88     // This errs on the side of returning false.
  89     bool conditionSufficient(const SCEV *LHS, Predicate Pred1, const SCEV *RHS,
  90                              const SCEV *A, Predicate Pred2, const SCEV *B,
  91                              const Loop *L);
  92
  93     // Determines whether Offset is known to be always in [0, Limit) bounds.
  94     // This errs on the side of returning Unknown.
  95     enum SolverResult checkLimits(const SCEV *Offset, const SCEV *Limit,
  96                                   BasicBlock *BB);
  97
  98     virtual bool runOnFunction(Function &F);
  99     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
 100     void print(raw_ostream &OS, const Module* = 0) const;
 101     virtual void print(std::ostream &OS, const Module* = 0) const;
 102   private:
 103     Function *FF;
 104     TargetData *TD;
 105     ScalarEvolution *SE;
 106     LoopInfo *LI;
 107     DominatorTree *DT;
 108
 109     Function *callocFunc;
 110     Function *reallocFunc;
 111     PredIteratorCache predCache;
 112
 113     SmallPtrSet<const SCEV*, 1> analyzing;
 114
 115     enum SolverResult isLoopGuardedBy(const Loop *L, Predicate Pred,
 116                                       const SCEV *A, const SCEV *B) const;
 117     static bool isMonotonic(const SCEV *S);
 118     bool scevPositive(const SCEV *A, const Loop *L, bool strict=true) const;
 119     bool conditionSufficient(Value *Cond, bool negated,
 120                              const SCEV *A, Predicate Pred, const SCEV *B);
 121     Value *getConditionToReach(BasicBlock *A,
 122                                DomTreeNodeBase<BasicBlock> *B,
 123                                bool &negated);
 124     Value *getConditionToReach(BasicBlock *A,
 125                                BasicBlock *B,
 126                                bool &negated);
 127     const SCEV *computeAllocationCount(Value *P, const Type *&Ty) const;
 128     const SCEV *computeAllocationCountForType(Value *P, const Type *Ty) const;
 129   };
 130 }
 131 #endif
 132