LLVM API Documentation
00001 //===- PointerTracking.h - 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 // It knows that the libc functions "calloc" and "realloc" allocate memory, thus 00012 // you should avoid using this pass if they mean something else for your 00013 // language. 00014 // 00015 // All methods assume that the pointer is not NULL, if it is then the returned 00016 // allocation size is wrong, and the result from checkLimits is wrong too. 00017 // It also assumes that pointers are valid, and that it is not analyzing a 00018 // use-after-free scenario. 00019 // Due to these limitations the "size" returned by these methods should be 00020 // considered as either 0 or the returned size. 00021 // 00022 // Another analysis pass should be used to find use-after-free/NULL dereference 00023 // bugs. 00024 // 00025 //===----------------------------------------------------------------------===// 00026 00027 #ifndef LLVM_ANALYSIS_POINTERTRACKING_H 00028 #define LLVM_ANALYSIS_POINTERTRACKING_H 00029 00030 #include "llvm/ADT/SmallSet.h" 00031 #include "llvm/Analysis/Dominators.h" 00032 #include "llvm/Instructions.h" 00033 #include "llvm/Pass.h" 00034 #include "llvm/Support/PredIteratorCache.h" 00035 00036 namespace llvm { 00037 class DominatorTree; 00038 class ScalarEvolution; 00039 class SCEV; 00040 class Loop; 00041 class LoopInfo; 00042 class TargetData; 00043 00044 // Result from solver, assuming pointer is not NULL, 00045 // and it is not a use-after-free situation. 00046 enum SolverResult { 00047 AlwaysFalse,// always false with above constraints 00048 AlwaysTrue,// always true with above constraints 00049 Unknown // it can sometimes be true, sometimes false, or it is undecided 00050 }; 00051 00052 class PointerTracking : public FunctionPass { 00053 public: 00054 typedef ICmpInst::Predicate Predicate; 00055 static char ID; 00056 PointerTracking(); 00057 00058 virtual bool doInitialization(Module &M); 00059 00060 // If this pointer directly points to an allocation, return 00061 // the number of elements of type Ty allocated. 00062 // Otherwise return CouldNotCompute. 00063 // Since allocations can fail by returning NULL, the real element count 00064 // for every allocation is either 0 or the value returned by this function. 00065 const SCEV *getAllocationElementCount(Value *P) const; 00066 00067 // Same as getAllocationSize() but returns size in bytes. 00068 // We consider one byte as 8 bits. 00069 const SCEV *getAllocationSizeInBytes(Value *V) const; 00070 00071 // Given a Pointer, determine a base pointer of known size, and an offset 00072 // therefrom. 00073 // When unable to determine, sets Base to NULL, and Limit/Offset to 00074 // CouldNotCompute. 00075 // BaseSize, and Offset are in bytes: Pointer == Base + Offset 00076 void getPointerOffset(Value *Pointer, Value *&Base, const SCEV *& BaseSize, 00077 const SCEV *&Offset) const; 00078 00079 // Compares the 2 scalar evolution expressions according to predicate, 00080 // and if it can prove that the result is always true or always false 00081 // return AlwaysTrue/AlwaysFalse. Otherwise it returns Unknown. 00082 enum SolverResult compareSCEV(const SCEV *A, Predicate Pred, const SCEV *B, 00083 const Loop *L); 00084 00085 // Determines whether the condition LHS <Pred> RHS is sufficient 00086 // for the condition A <Pred> B to hold. 00087 // Currently only ULT/ULE is supported. 00088 // This errs on the side of returning false. 00089 bool conditionSufficient(const SCEV *LHS, Predicate Pred1, const SCEV *RHS, 00090 const SCEV *A, Predicate Pred2, const SCEV *B, 00091 const Loop *L); 00092 00093 // Determines whether Offset is known to be always in [0, Limit) bounds. 00094 // This errs on the side of returning Unknown. 00095 enum SolverResult checkLimits(const SCEV *Offset, const SCEV *Limit, 00096 BasicBlock *BB); 00097 00098 virtual bool runOnFunction(Function &F); 00099 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 00100 void print(raw_ostream &OS, const Module* = 0) const; 00101 virtual void print(std::ostream &OS, const Module* = 0) const; 00102 private: 00103 Function *FF; 00104 TargetData *TD; 00105 ScalarEvolution *SE; 00106 LoopInfo *LI; 00107 DominatorTree *DT; 00108 00109 Function *callocFunc; 00110 Function *reallocFunc; 00111 PredIteratorCache predCache; 00112 00113 SmallPtrSet<const SCEV*, 1> analyzing; 00114 00115 enum SolverResult isLoopGuardedBy(const Loop *L, Predicate Pred, 00116 const SCEV *A, const SCEV *B) const; 00117 static bool isMonotonic(const SCEV *S); 00118 bool scevPositive(const SCEV *A, const Loop *L, bool strict=true) const; 00119 bool conditionSufficient(Value *Cond, bool negated, 00120 const SCEV *A, Predicate Pred, const SCEV *B); 00121 Value *getConditionToReach(BasicBlock *A, 00122 DomTreeNodeBase<BasicBlock> *B, 00123 bool &negated); 00124 Value *getConditionToReach(BasicBlock *A, 00125 BasicBlock *B, 00126 bool &negated); 00127 const SCEV *computeAllocationCount(Value *P, const Type *&Ty) const; 00128 const SCEV *computeAllocationCountForType(Value *P, const Type *Ty) const; 00129 }; 00130 } 00131 #endif 00132